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.

21.13^4

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

- all words containing three distinct letters and less than nine letters in all meet Roger's criteria;
- only certain 9-letter words do not meet his criteria; and
- it is not until we look at 33-letter words that we can be mathematically sure of not meeting Roger's criteria.

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