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.

  • $\begingroup$ I don't think your formula is correct. I came up with the first five values of $S_n^2$ as $1, 2, 5, 16, 61$. But $S_5^2$ would be $5\cdot 16-3^2=71$ using your recursion. However, feel free to check the value of $S_5^2$ $\endgroup$ – paw88789 Sep 27 '14 at 9:24

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.