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.
![$\mathrm{(A) \ }9\cdot 7! \qquad \mathrm{(B) \ } 8! \qquad \mathrm{(C) \ }5!4! \qquad \mathrm{(D) \ }8!4! \qquad \mathrm{(E) \ }8!+6!+4!$](http://latex.artofproblemsolving.com/e/c/7/ec73868eb5d35d371c3578d6d7e3eae1b1b2d23d.png)
Solution
There are (the factorial of 9) total permutations of the elements of that set. 1 is to the left of 2 in exactly half of these. 3 is also to the left of 4 in exactly half of the permutations, and 5 is to the left of 6 in exactly half of the permutations. These three events are totally independent of each other, so the number we want to calculate is
which is answer choice
.
Alternatively, note that we can choose places for the 1 and 2, then
places for the 3 and 4, then
places for the 5 and 6, and the arrange the 7, 8 and 9 in
ways, giving us a total of
.