Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K-8
Teachers |
Possible Solutions: Supplementary Problems Set D |
return to problems |
||||||||||||||||||||||||||||||||||||||||||
1. |
Determine the number of 50-digit sets we can create, choosing from {0,1,...9} and assuring that all digits are represented. This problem is analogous to determining the number of positive-integer solutions to the equation x0+x1+...+x9 = 50. We refer to 50 as the total number of items (in general represented by n) and 10 as the number of different types of items (in general represented by k). There are C(n-1,k-1) = C(50-1,10-1) = C(49,9) solutions. |
|||||||||||||||||||||||||||||||||||||||||
2. |
How many 100-letter sets can be made using letters from {A,B,...,Z}, assuring that each letter occurs at least once? Similar to Question 1, with n = 100 and k = 26. We get C(100-1,26-1) = C(99,25) such sets. |
|||||||||||||||||||||||||||||||||||||||||
3. |
Repeat problem (1) from Set D with the additional requirement that each digit occur at least twice. If each digit is to occur at least twice, then we essentially have already accounted for 20 of the objects, i.e., 10 digits each appearing twice. This leaves us n = 30 total objects to place, still having k = 10 different types of objects. Now, however, with the 20 objects accounted for, we no longer need to assure that each digit is further represented. We thus are solving a new problem: Determine the number of nonnegative-integer solutions to the equation x0+x1+...+x9 = 30. In general, this is C(n + k - 1, k - 1), so here we have C(30 + 10 - 1, 10 - 1) = C(39,9) sets that can be created. |
|||||||||||||||||||||||||||||||||||||||||
4. |
How many 20-letter sets can be made using letters from {A,B,C} and requiring that there be at least one A, at least two Bs, and at least three Cs? With n = 20 and k = 3, we use 6 of the 20 objects to meet the requirements for appearances of A, B, and C. We are left with 14 total objects to place of 3 different types, solved over the nonnegative integers. This is C(14 + 3 - 1,3 - 1) different sets. |
|||||||||||||||||||||||||||||||||||||||||
5. |
Determine the number of three-letter sets that can be made choosing from among {A,B,C,D,E} and allowing repetition. Note that missing elements are allowed. We are determining the number of nonnegative-integer solutions to the equation x1 + x2 + x3 + x4 + x5 = 3, so n = 3 and k = 5. The number of three-letter sets is C(3 + 5 - 1, 5 - 1) = C(7,4). |
|||||||||||||||||||||||||||||||||||||||||
6. |
How many n-element sets can be created from among {a1, a2,...,ak}, allowing repetition as well as missing elements? This is the generalization to several of the questions posed already. The number of sets is C(n+ k - 1, k - 1). |
|||||||||||||||||||||||||||||||||||||||||
7. |
Devise a scenario that can be completed in exactly 1001 ways. Many solutions exist for this. We note that 1001 = 7*11*13 and that 1001 = C(14,4). We can show that there are 1001 nonnegative-integer solutions to the equation a + b + c + d + e = 10. |
|||||||||||||||||||||||||||||||||||||||||
8. |
Five pairs of shoes are displayed. (a) C(10,3) |
|||||||||||||||||||||||||||||||||||||||||
9. |
Seven coins are flipped simultaneously. What portion of the possible results include getting three heads and four tails? Row 7 of Pascal's Triangle shows ways to get various combinations of heads and tails:
Reading from the left, the table shows there is 1 way to getting 7H, 0T, 7 ways to get 6H,1T, 21 ways to get 5H,2T, and so on. The sum of these entries is 1+7+21+...+1=2^7=128. Exactly 35 of these result in 3H,4T. Thus, the desired ratio is 35/128. |
|||||||||||||||||||||||||||||||||||||||||
10. |
(a) Consider the expansion of (x+y)^13. What is the
coefficient of the collected term containing x^8y^5 ? (a) C(13,5) = C(13,8) |
|||||||||||||||||||||||||||||||||||||||||
11. |
Determine the number of 8-letter words that use letters from {A,B,C} and contain exactly three As. With exactly 3 As among the 8 letters in each word, the Bs and Cs together represent 5 letters in each word. The table here shows the possible number of Bs and Cs to go with the 3 As.
The answer to our question is the sum of the values in the right column of the table. |
|||||||||||||||||||||||||||||||||||||||||
12. |
A certain state lottery requires participants to select 6
distinct numbers from the set {1,2,...,50}. (a) Assuming that the selection 1-2-3-4-5-6 is the same
as the selection 6-5-4-3-2-1, there are C(50,6) selections a
participant can make. Note that C(50,6) is 15,890,700.
|
|||||||||||||||||||||||||||||||||||||||||
13. |
We know that m dogs and n cats are to be arranged in a row. How many ways can this be done so that the cats are separated from each other? We assume that the dogs are distinguishable from one another as are the cats. Begin by arranging the m dogs. This can be done in P(m,m) = m! ways. Now imagine the (m + 1) spots among and outside the line-up of dogs. Permute the n cats within these (m + 1) spots. This can be done in P(m + 1, n) ways. Note that this result is positive only when (m + 1) is greater than or equal to n. If that condition does not hold, the cats cannot be separated from each other. |
|||||||||||||||||||||||||||||||||||||||||
14. |
Determine the number of 10-letter sets, with repetition
allowed, from the set {X,Y,Z} that contain: (a) C(10 - 1,3 - 1) = C(9,2) |
|||||||||||||||||||||||||||||||||||||||||
15. |
Show that C(2n,n) is divisible by n+1. |
|
|
|
|
|