2002 IMO Shortlist Problems/C3
Problem
Let be a positive integer. A sequence of positive integers (not necessarily distinct) is called full if it satisfies the following conditions: for each positive integers , if the number appears in the sequence then so does the number , and moreover the first occurrance of comes before the last occurrance of . For each , how many full sequences are there?
Solution
We claim that there is a bijection between the permutations of the numbers and the full sequences of length .
To obtain a full sequence from a permutation of the first positive integers, begin by letting be 1. Then, if is and , let be , but if , let be . This ensures that if appears in the sequence, then the first appearance of occurs before the last appearance of , 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 full sequences of length , 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.