ISL 2002 C3

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\geq2$ , 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 ?

Attachments: