IMO 2002 SL C3

Origin: COL | Category: Combinatorics

Problem

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?

Solution

We claim that there are n! full sequences. To show this, we construct a bijection with the set of permutations of {1, 2, . . ., n}. Consider a full sequence (a1, a2, . . . , an), and let m be the greatest of the numbers a1, . . . , an. Let Sk, 1 \leqk \leqm, be the set of those indices i for which ai = k. Then S1, . . . Sm are nonempty and form a partition of the set {1, 2, . . ., n}. Now we write down the elements of S1 in descending order, then the elements of S2 in descending order and so on. This maps the full sequence to a permutation of {1, 2, . . ., n}. Moreover, this map is reversible, since each permutation uniquely breaks apart into decreasing sequences S′ 1, S′ 2, . . . , S′ m, so that max S′ i > min S′ i−1. Therefore the full sequences are in bijection with the permutations of {1, 2, . . ., 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 xn is the number of full sequences of length n, we deduce xn = nxn−1.