23. C3 (COL) Let \( n \) be a positive integer. A sequence of \( n \) positive integers (not necessarily distinct) is called full if it satisfies the following condition: For each positive integer \( k \geq 2 \), if the number \( k \) appears in the sequence, then so does the number \( k-1 \), and moreover, the first occurrence of \( k-1 \) comes before the last occurrence of \( k \). For each \( n \), how many full sequences are there?
23. We claim that there are $n$! full sequences. To show this, we construct a bijection with the set of permutations of $\{1,2, \ldots, n\}$. Consider a full sequence $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$, and let $m$ be the greatest of the numbers $a_{1}, \ldots, a_{n}$. Let $S_{k}, 1 \leq k \leq m$, be the set of those indices $i$ for which $a_{i}=k$. Then $S_{1}, \ldots S_{m}$ are nonempty and form a partition of the set $\{1,2, \ldots, n\}$. Now we write down the elements of $S_{1}$ in descending order, then the elements of $S_{2}$ in descending order and so on. This maps the full sequence to a permutation of $\{1,2, \ldots, n\}$. Moreover, this map is reversible, since each permutation uniquely breaks apart into decreasing sequences $S_{1}^{\prime}, S_{2}^{\prime}, \ldots, S_{m}^{\prime}$, so that $\max S_{i}^{\prime}>\min S_{i-1}^{\prime}$. Therefore the full sequences are in bijection with the permutations of $\{1,2, \ldots, n\}$. Second solution. Let there be given a full sequence of length $n$. Removing from it the first occurrence of the highest number, we obtain a full sequence of length $n-1$. On the other hand, each full sequence of length $n-1$ can be obtained from exactly $n$ full sequences of length $n$. Therefore, if $x_{n}$ is the number of full sequences of length $n$, we deduce $x_{n}=n x_{n-1}$.