University of South Carolina High School Math Contest/1993 Exam/Problem 14
Problem
How many permutations of 1, 2, 3, 4, 5, 6, 7, 8, 9 have:
- 1 appearing somewhere to the left of 2,
- 3 somewhere to the left of 4, and
- 5 somewhere to the left of 6?
For example, 8 1 5 7 2 3 9 4 6 would be such a permutation.
Solution
For the nine slots, we have to choose two spots for each of our pairs 
. There are 
ways to do this, but we must multiply this by 
because there are three different pairs that we can choose in different "orders" for the 
. We also need to multiply by again for the remaining three slots for 
. Thus the total number of ways is 
, which after simplifying is choice 
.
