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.