Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers

Supplement C: Possible Solutions

1. (5!*6!)/3!
Place the 5 consonants first. This can be done in 5! ways. Now select 3 of the 6 open spots between the consonants. This can be done in P(6,3) ways.

2. 5 socks
The worst case scenario is that Judy draws 4 socks, each of a different color. By the Pigeonhole Principle, however, the fifth sock, must match the color of one of the first four socks.

3. 5^15
Let v=t=u=v=w=1. Each uncollected term in the expansion is the product of 15 factors each equal to 1. This expansion will sum to (1+1+1+1+1)^15 = 5^15.

4. 13 + (13*12)/2 = 13 + C(13,2)
Represent the pair of numbers on a domino by (a,b), where There are 13 dominoes of the form (c,c). There are 13*12 dominoes of the form (a,b) with a not equal to b, but half of those are repeats, i.e., (a,b) = (b,a).

5. 20!/(9!11!) = C(20,9)
There are 20! ways to arrange the 9 xs and 11 ys. We divide by (9!11!) to account for the duplicates of each letter.

6. C(17,5)
There are six possible outcomes with each die. Any one of the six possible outcome could occur as few as 0 times and as frequently as 12 times. Therefore, we seek the number of solutions to the equation A+B+C+D+E+F=12, solved over the nonnegative integers, where A represents the number of 1s, B represents the number of 2s, and so on. There are C(17,5) possible solutions.

7. C(15,5)
Each possible selection consisting of one marble from each bag will contain 10 marbles with from 0 to 10 marbles of any one of the six colors. Because marbles of the same color are not distinguishable, the choice B B B W W W B B W W drawn in that order is the same as the choice W W W W W B B B B B drawn in that order. We need to determine the number of ways to draw each of the many possible color combinations.

Relate this to the expansion of (r+w+b+g+p+y)^10. When all like terms are collected, every term will be of the form K*[r^R*w^W*b^B*g^G*p^P*y^Y], where K=[10!/(R!W!B!G!P!Y!)] represents any value possible for R+W+B+G+P+Y=10 and R,W,B,G,P,Y being nonnegative integers. We need to determine the number of solutions to the equation R+W+B+G+P+Y=10 solved over the nonnegative integers. There are C(15,5) possible solutions.

8. (8!/8)*P(8,5)=7!*P(8,5)
Arrange the Patriots around the table with only 8 chairs available at the table. This can be done in 8! ways, and we divide by 8 to account for duplicate arrangements caused only by rotation around the table, i.e., no change in relative position. There are now 8 open "places" between the Patriots. Choose 5 of them for the Minutemen, slide a chair into each place, and arrange the Minutemen in these 5 chairs. This can be done in P(8,5) ways.

9. 1504
Use the inclusion-exclusion principle. From the 2000 integers, subtract (333+200+57)=590, the number of values divisible by one of 6, 10, or 35. Now add (66+9+28)=103, the number of values divisible commonly by 6 and 10, 6 and 35, or 10 and 35. Now subtract 9, the number of values divisible commonly by 6, 10, and 35.

10. Part 1: C(19,9); Part 2: C(29,9)
Part 1: Consider the money in $5 chunks. Mary has 20 chunks to distribute so that 10 charities receive at least one chunk. We seek the number of solutions to a+b+c+d+e+f+g+h+i+j=20 solved over the positive integers. Now line up the 20 chunks and place 9 dividers somewhere among the 19 locations that exist between the chunks. There are C(19,9) ways to place such dividers.

If the money is distributed to at most 10 charities, we solve a+b+c+d+e+f+g+h+i+j=20 solved over the non-negative integers. We now have 20 chunks of money and 9 dividers to arrange. This can be done in C(29,9) ways.

11. C(9,4)
Line up the 8 Qs with a space between each pair of letters. There are now 9 locations to place the 4 Ms to be sure no two Ms are adjacent. The Ms can be placed in C(9,4) ways. Note that we assume the Qs are indistinguishable from one another as are the Ms.

12. C(33,5)
An example for the second part of the question is 0+2+5+0+21+0.

13. Part 1: 15!/(1!2!3!4!5!); Part 2: 9!/(2!3!4!)*C(10,1)*C(9,5)
Part 1: The 15 letters can be arranged in 15! ways, but we divide by (1!2!3!4!5!) to account for the duplicate arrangements resulting from identical letters being indistinguishable.

Part 2: Begin by arranging the 9 consonants. The can be done in 9!/(2!3!4!) ways. There are now 10 available slots around these letters. Choose 1 for the a. This can be done in C(10,1) ways. Now choose 5 of the remaining 9 slots for the letters e. This can be done in C(9,5) ways.

14. C(10,5)
See problem 6.

15. C(5,3) + C(6,3)

16. 10!/(4!1!0!2!0!3!)

Relate this to the expansion of (a+b+c+d+e+f)^10. What is the coefficient of the term that contains the factor a^4*b^1*c^0*d^2*e^0*f^3 ?

17. 2^23

18. 8^20

19. a^3*b^5*c^2, a^3*b^2*c^5, a^5*b^3*c^2,
a^5*b^2*c^3, a^2*b^3*c^5, a^2*b^5*c^3

20. 2^14
Terms in row 14 sum to 2^14 and terms in row 15 sum to 2^15. The absolute difference is 2^15-2^14=2^14(2-1)=2^14.

Visualize the 4 cards. There are 13 choices for the first card, 13 choices for the second, and so on.

22. 2^5

23. C(20,2)+C(21,2)
An even-number sum results from addition of two even numbers and from addition of two odd numbers. In the set there are 20 even numbers and 21 odd numbers. Therefore, there are C(20,2) pairs of even numbers and C(21,2) pairs of odd numbers.

24. 6*C(27,6)
From the 27 students, select a group of 6. This can be done in C(27,6) ways. Now, there are 6 ways to select a captain from this group.

25. Suppose Roger chooses the word banana.This is a six-letter word with three distinct letters, namely a, b, and n. We know there are 6!/(3!1!2!)=60 different arrangements of the letters {b,a,n,a,n,a}. This word qualifies as one Roger is seeking because there are no more than 1000 different arrangements of the letters.

In general, Roger's word will have T!/(A!B!C!) arrangements, where A+B+C=T and there are A occurrences of one letter, B occurrences of a second letter, and C occurrences of a third letter. Note that A, B, and C are positive integers.

You may enjoy going on to show that

26. Ralph should say that each group has exactly the same number of subsets, based on the result apparent in Pascal's Triangle and justified using the binomial expansion:

C(30,0) + C(30,2) + . . . + C(30,30) = C(30,1) + C(30,3) + . . . + C(30,29)

27. 19*2*24!
In an arrangement with 26 spaces, there are 19 ways to place c to the left of d so there are 6 spaces between the two letters. Likewise for d to the left of c. Having placed c and d, there are 24! ways to arrange the remaining letters.

28. C(13,5)*C(8,3)*C(5,2)
From 13, choose 5 for the first committee. This can be done in C(13,5) ways. Now select 3 from the remaining 8 for the second committee, done in C(8,3) ways. Finally, choose 2 from the remaining 5 people to form the third committee. This can be done in C(5,2) ways. You may think of a meaningless fourth committee being formed with the three members not chosen for the first three committees.

29. 13
It is possible to assemble 12 humans and each have a different birth month. A 13th human, however, assures us of at least one pair of humans sharing a birth month.

30. 10^3*9
Represent the 7-digit number as a b c D c b a, where position D is the middle digit. There are 10 choices for D, 10 for c, 10 for b, and 9 for a.

31. [20!/(14!6!)]*2^6