Illinois State University Mathematics Department

 MAT 305: Combinatorics Topics for K-8 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 back-up 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 1-letter words, 26^2 possible 2-letter words, 26^3 possible 3-letter words, and 26^4 possible 4-letter 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)
This is the number of solutions to the equation A+B+C+D+E+F+G=26 solved over the nonnegative integers.

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)
First select a pair of variables for the expression. This can be done in C(7,2) ways. Now determine the number of solutions to A+B=26, in order to determine the number of ways each pair of variables can have exponents sum to 26. There are C(27,1) such solutions. Each pair of variables is matched with each set of possible exponent arrangements, so we multiply.

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.
Assume that a typical work year contains 50 weeks at 5 days per week. Thus we need at least 250 different outfits. We need 6*8*p to be at least 250. Any value p greater than or equal to 6 satisfies this requirement.

For questions (11) through (13), use the following information.

A survey was taken of Chicago-area 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.
 Our business maintains (check one): + less than 26 employees + 26-49 employees + 50-99 employees + 100-999 employees + 1000 or more employees

11.

When the results are tallied, how many different responses are possible from the combined group of 1240 businesses?

C(1244,4)
This assumes each of the 1240 businesses selected exactly one of these five alternatives.

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)
We have 10% of 1240 or 124 businesses at a minimum responding to each of the five employee categorizations. This leaves 1240 - 5(124) = 620 to spread over the five categories. We seek the number of solutions to A+B+C+D+E=620, solved over the nonnegative integers.

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)
Select 5 of the 20 reds and 3 of the 12 whites. This done in C(20,5)*C(12,3) ways, we now have a set of 8 wines to place on the list. The actual arrangement on the list can be done in 8! = P(8,8) ways. This placement is unique to this set of 8 wines, so we multiply the number of 8-bottle sets by 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 semi-dry. 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)]
First choose two of the semi-dry wines to be used at the top and bottom of the list and permute them to determine the top and bottom items on the list. Now choose 6 of the remaining 30 wines to fill the middle six positions on the list and permute those 6.

18.

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

Yes.
There are two characteristics in each of three categories, so there are 2^3=8 unique wine characterizations possible. We don't know if Gauss has appropriate inventory to provide this, but it is possible in theory.

19.

Suppose we know that 12 of Gauss's 32 wines are red German semi-dry 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/semi-dry 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.

• Situation I: Given: 12 RGS. Then suppose 1 RFD, 1RFS, 1 WFS, 1 WFD, leading to 6 RGD, 4 WGS, and 6 WGD.
Situation II: Given: 12 RGS. Then suppose 1 RFD, 1RFS, 0 WFS, 2 WFD, leading to 6 RGD, 5 WGS, and 5 WGD.

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!)
There are 10! ways to arrange the offensive players, 16! ways to arrange the defensive players, and 2! ways to arrange the kickers. There are then P(3,3)=6 ways to arrange the three intact groups.

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)
There are 50 possible categories for the players, and 28 players to categorize. Some categories will have 0 entries. This gives us C(28+50-1,50-1) ways.

.

24.

Write an inductive proof to justify the following conjecture. Conjecture: i) Show true for n = 1: ii) Assume true for n = k: 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(n-1) - 3a(n-2), 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, . . .

• Recursive: a(1) = 5, a(n) = 2a(n-1) + 7
• Explicit: 12(2^(n-1)) - 7

 Syllabus Grades & Grading Session Notes Assignments and Problem Sets Tests and Quizzes