Number of possible sequences with at most 2 repetitions and entry $a_i \in\{1,2,3,\dots,i\}$

Question

We denote the first $k$ natural numbers (not including 0) by $N_k = \{1,2,3,4,\dots, k\}$.
Consider a length $n$ sequence, $S=(s_1,s_2,s_3,\dots,s_n)$ such that $s_1 \in N_1$, $s_2 \in N_2$ and more generally $s_i \in N_i$.

Let $S_n$ denote the set of such sequences. The number of possible different sequences, $\lvert S_n \rvert$ of length $n$ is $n!$ since there are 1 choices for $s_1$ 2 choices for $s_2$ and so on.

Let $S^2_n$ denote the set of sequences $$ S^2_n = \{ S \in S_n : \text{no number occurs more than twice in $S$} \} $$

For example $S = (1,1,1,2,3) \in S_5$ but not in $S^{2}_5$ since 1 occurs 3 times in $S$.

Question: Calculate $\lvert S_n^2 \rvert$ for each $n$.

I have tried to find a suitable recurrence and by observation it appears that $$ \lvert S_n^2 \rvert = n\lvert S_{n-1}^2 \rvert - (n-2)^2 $$ Unfortunately I do not know how to prove this and help would be greatly appreciated.

Answer 1

We begin with $|S_1^2| = 1$

For $n=2$, $|S_2^2| = 2$, for which $1$ case already has two repeated numbers.

For $n=3$, $|S_3^2| = 3+2$, $3$ cases that result from the previous element that has no repeated elements and 2 that come from the element which already had one repeated element. Observe that from this $5$ elements $2+2=4$ have at least one repeated element ($2$ from the one that already had a repeated element and $2$ which come from repeating a number from the one that didn't have a repeated element.

With these observations I think that:

$$|S_n^2|= n + \sum_{K=1}^{\lfloor\frac{n}{2}\rfloor}(\text{number of elements of $S_{n-1}$ with $K$ repeated elements})\cdot(K-1)$$

where if $K\leq \lfloor\frac{n}{2}\rfloor$ then,

$$(\text{number of elements of $S_{n}$ with $K$ repeated elements}) = (\text{number of elements of $S_{n-1}$ with $K-1$ repeated element}) + (n-K)$$

Finally, observe that if $K= \lfloor\frac{n}{2}\rfloor$ then $(\text{number of elements of $S_{n}$ with $K$ repeated elements}) = 1$.

I think this should be enough to get your formula.