2002 IMO Shortlist S17

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 ?

令 $n$ 为正整数。如果满足以下条件，则 $n$ 个正整数(不一定不同)的序列称为 **full**：对于每个正整数 $k\geq2$ ，如果数字 $k$ 出现在序列中，则数字 $k-1$ 也会出现，而且 $k-1$ 的第一次出现位于 $k$ 最后一次出现之前。对于每个$n$，有多少个完整序列？