Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8
Teachers 
Possible Solutions: Supplementary Problems Set H 
For questions (1) through (3), consider the word expenseless. 

1. 
Assuming that identical letters are indistinguishable, how many unique arrangements are there of the letters in the word? 11!/(4!3!) 

2. 
How many ways can the letters in the word be arranged that result in no detectable difference in the resulting arrangement, assuming that identical letters are indistinguishable? 4!3! 

3. 
How many ways are there to arrange these letters so that no vowels are adjacent? (7!/3!)*C(8,4) 



4. 
John manages an RS6000 computer with a tape drive. Thursday he was given a backup tape that contained 500,000 "words," each word created from four or fewer lowercase letters and each word separated by a single blank character. Argue that at least one of the "words" must be repeated among the 500,000 entries on the tape, or prove that there could be no repeats. There are 26 possible 1letter words, 26^2 possible 2letter words, 26^3 possible 3letter words, and 26^4 possible 4letter words. 26 + 26^2 + 26^3 + 26^4 = 475,254. This is less than 500,000. By the pigeonhole principle, after 475,255 words have been read, there will be at least one pair of identical words. 

For questions (5) through (8), focus on the expansion of . 

5. 
Determine the number of uncollected terms in the expansion. 7^26 

6. 
Determine the number of collected terms in the expansion. C(32,6) 

7. 
Determine the coefficient K for the collected term . 26!/(2!4!6!10!1!0!3!) 

8. 
How many collected terms are of the form , m,n from among {a,b,c,d,e,f,g} and 0 <= k <= 26? C(7,2)*C(27,1) 

For questions (9) and (10), Pat Punchlormer is a friend of Sandy Softknuckle's. Pat obsesses about the myriad ways to create work outfits comprised of a shirt, a pair of slacks, and a pair of shoes. 

9. 
From a closet with 20 different shirts, 15 different pairs of slacks, and 10 different pairs of shoes, how many different outfits can be created? 20*15*10 

10. 
If 6 different shirts and 8 different pairs of slacks are available, how many different pairs of shoes are required so that a different outfit can be worn each day during a typical working year? At least 6 pairs of
shoes are required. 

For questions (11) through (13), use the following information. A survey was taken of Chicagoarea businesses to determine the number of fulltime permanent employees maintained in each business. Among other requests, respondents were asked to complete the sentence below. Exactly 1240 businesses responded to the survey. 

11. 
When the results are tallied, how many different responses are possible from the combined group of 1240 businesses? C(1244,4) 

12. 
If no less than 10% of the businesses are in each employee categorization shown in the box, how many different ways could the group of businesses respond to the item? C(624,4) 

13. 
If a response to the survey question is recorded and identified with each of the 1240 businesses, how many different sets of responses are possible? 5^(1240) 

For questions (14) through (19), use the following information. Gauss's Gentle Grove is a romantic restaurant on the outskirts of the Black Forest. Gauss selects from the same 32 varieties of wine for each night's menu, and each night's wine list has exactly 8 entries. 

14. 
How many different wine lists can be created? Solve the problem assuming the order of appearance on the list does matter. P(32,8) 

15. 
If 20 of the wines are red and 12 are white, how many ways can a list be created to include 5 reds and 3 whites? Solve the problem assuming the order of appearance on the list does matter. C(20,5)*C(12,3)*P(8,8) 

16. 
At the Grove, as the locals call the restaurant, Gauss has 28 German wines and 4 French wines. If an evening's wine list includes no more than one French wine, how many different wine lists can be written? Solve the problem assuming the order of appearance on the list does matter. C(28,7)*C(4,1)*P(8,8) + C(28,8)*P(8,8) 

17. 
Fourteen of Gauss's wines are dry and 18 are semidry. If no dry wine is listed as the first or last wine on an evening's list, how many different wine lists can be written? [C(18,2)*P(2,2)]*[C(30,6)*P(6,6)] 

18. 
If each of the 32 wines can be classified as red or white, German or French, and dry or semidry, can an evening's list contain wines each of a different classification? Yes. 

19. 
Suppose we know that 12 of Gauss's 32 wines are red German semidry wines. Determine how many varieties there are of each of the other wine types, or alternatively, argue that more information is needed. We assume the accuracy of the information about the numbers of red/white, German/French, and dry/semidry wines presented in previous problems. More information is needed to solve this problem, for there are at least two unique solutions that satisfy the known information. Use R/W, G/F, and D/S to represent the characteristics in question.
These two solutions satisfy all problem condition but clearly are not equivalent. 

For questions (20) through (23), my nephew Seth has a modest collection of football cards from 28 professional NFL teams. He selects one card from each team. No two players are the same. 

20. 
After Seth has selected one card from each team, how many ways can he arrange them in a single line? 28! 

21. 
How many ways can Seth arrange the 28 cards in a circle? 28!/28 

22. 
If 16 of the cards represent defensive players, 10 represent offensive players, and 2 represent place kickers, how many ways are there to arrange the 28 cards in a single line so that all players of the same group (defense, offence, kicker) are together? 6(10!16!2!) 

23. 
Seth decided to categorize the 28 players according to the home state of residence listed on the back of the card. Assuming all players are from the United States, how many different categorizations are there? C(77,49) 



24. 
Write an inductive proof to justify the following conjecture. Conjecture: iii) Show true for n = k+1: Show that By assumption (ii), the first k terms sum to , so we have the sum of the first (k+1) terms as This last relationship is just the result we were trying to establish. iv) Summarize results: We have shown by induction that . 

25. 
Write the next 6 terms in the following recursion relation. a(n) = 2a(n1)  3a(n2), a(0 )= 2, a(1) = 5 a(0)=2, a(1)=5, a(2)=4, a(3)=7, a(4)=26, a(5)=31, a(6)=16, a(7)=125 

26. 
Write both a recursive and an explicit representation for the following sequence of values. 5,17,41,89,185, . . .





