Difference between revisions of "University of South Carolina High School Math Contest/1993 Exam/Problem 14"
Line 1: | Line 1: | ||
== Problem == | == 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. | ||
− | <center><math> \mathrm{(A) \ } \qquad \mathrm{(B) \ } \qquad \mathrm{(C) \ } \qquad \mathrm{(D) \ } \qquad \mathrm{(E) \ } </math></center> | + | <center><math> \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! </math></center> |
== Solution == | == Solution == | ||
+ | For the nine slots, we have to choose two spots for each of our pairs <math>(1,2), (3,4), (5,6)</math>. There are <math>{9\choose 2}{7\choose 2}{5\choose 2}</math> ways to do this, but we must multiply this by <math>3!</math> because there are three different pairs that we can choose in different "orders" for the <math>{9\choose 2}, {7\choose 2}, {5\choose 2}</math>. We also need to multiply by <math>3!</math> again for the remaining three slots for <math>7,8,9</math>. Thus the total number of ways is <math>3!{9\choose 2}{7\choose 2}{5\choose 2}3!</math>, which after simplifying is choice <math>(a)</math>. | ||
== See also == | == See also == | ||
* [[University of South Carolina High School Math Contest/1993 Exam]] | * [[University of South Carolina High School Math Contest/1993 Exam]] | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] |
Revision as of 20:25, 22 July 2006
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 .