Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8
Teachers 
Possible Solutions: Supplementary Problems Set D 
return to problems 

1. 
Determine the number of 50digit 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 positiveinteger 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(n1,k1) = C(501,101) = C(49,9) solutions. 

2. 
How many 100letter 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(1001,261) = 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 nonnegativeinteger 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 20letter 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 threeletter 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 nonnegativeinteger solutions to the equation x1 + x2 + x3 + x4 + x5 = 3, so n = 3 and k = 5. The number of threeletter sets is C(3 + 5  1, 5  1) = C(7,4). 

6. 
How many nelement 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 nonnegativeinteger 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 8letter 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 123456 is the same
as the selection 654321, 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 lineup 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 10letter 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. 




