Question 23
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?