# 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.*