2002 IMO Shortlist Problems/C3

Problem

Let $\displaystyle n$ be a positive integer. A sequence of $\displaystyle n$ positive integers (not necessarily distinct) is called full if it satisfies the following conditions: for each positive integers $\displaystyle k \ge 2$, if the number $\displaystyle k$ appears in the sequence then so does the number $\displaystyle k-1$, and moreover the first occurrance of $\displaystyle k-1$ comes before the last occurrance of $\displaystyle k$. For each $\displaystyle n$, how many full sequences are there?

Solution

We claim that there is a bijection between the permutations of the numbers $\displaystyle 1, \ldots , n$ and the full sequences of length $\displaystyle n$.

To obtain a full sequence $\displaystyle a_1, \ldots a_n$ from a permutation $\displaystyle \sigma$ of the first $\displaystyle n$ positive integers, begin by letting $\displaystyle a_{\sigma(1)}$ be 1. Then, if $\displaystyle a_{\sigma(j)}$ is $\displaystyle i$ and $\displaystyle \sigma(j+1) < \sigma(j)$, let $\displaystyle a_{\sigma(j+1)}$ be $\displaystyle i$, but if $\displaystyle \sigma(j+1) > \sigma(j)$, let $\displaystyle a_{\sigma(j+1)}$ be $\displaystyle i+1$. This ensures that if $\displaystyle k > 2$ appears in the sequence, then the first appearance of $\displaystyle k-1$ occurs before the last appearance of $\displaystyle k$, as desired.

To obtain a permutation from a full sequence, list the labels of the terms of the sequence that are 1 in decreasing order, followed by the labels of the terms of the sequence that are 2 in decreasing order, etc. This produces a permutation which will map back to our full sequence as described above. Thus the bijection is established; therefore there are $\displaystyle n!$ full sequences of length $\displaystyle n$, Q.E.D.

Note: There is also a recursive solution, but it is very similar to the bijective solution given here.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources