Illinois State University Mathematics Department

 MAT 305: Combinatorics Topics for K-8 Teachers

### Supplementary Problem Sets

Set A
Set B
Set C
Set D
Set E
Set F
Set G
Set H

 Problem Set A Set A possible solutions 1. Show that for any set of five points chosen within an equilateral triangle with sides of length 1 unit, there must be two points whose distance apart is at most 0.5 units. 2. In a group of 5 people, show that there are two who have the same number of acquaintances in the group. Generalize your result to show that in a group of n people, there are two who have the same number of acquaintances. Note: In this situation, two people either are acquainted or they are not acquainted. 3. Show that for any gathering of 6 people, there must be three in the group who are mutual friends or three who are mutual enemies. Note: In this situation, two people either are mutual friends or they are mutual enemies. 4. A friend of mine claimed that no matter what year it was, there had to be at least one Friday the 13th during the year. Is my friend correct? Provide evidence to support my friend's claim or to refute it. 5. Georgette works and lives in a downtown metropolitan area whose streets are laid out in a rectangular grid. Georgette's apartment is 6 blocks north and 9 blocks west of her work site, and Georgette walks to work every day by traversing one of the 15-block paths leading from her apartment to her work site. How many different 15-block paths are there for Georgette to walk? 6. As a special gift for my nephew Seth, I allowed him to select 5 collector football cards from my stock of 10 all-time great running backs. Seth could select all 5 of the very same card, 5 different cards, or any other combination resulting in 5 cards being selected. How many different ways could Seth make his selection? If I had allowed Seth to select no more than one of any one card, how many selections could he have made? 7. In the Mathematics Department office there are 50 mailboxes for faculty. During a recent sorting of the mail, a member of the office staff claimed she stuffed one box with 5 letters. What is the least number of letters there would have to be in the sort box to assure that at least one faculty member got at least 5 letters?

 Problem Set B Set B possible solutions 1. How many different pizzas can be ordered at Blaise's Bistro? 2. Blaise decides to select three sodas (from his existing soda menu) to list as Specials each day. How many different displays of soda names could Blaise create on his menu board? 3. In the dentist's reception area are 5 adult men, 6 adult women, 2 boys, and 4 girls. (a) How many choices are there for the next patient to be called? (b) How many ways are there to select a group of four people that contains one adult man, one adult woman, one boy, and one girl? (c) How many ways are there to simultaneously arrange four people, consisting of one adult man, one adult woman, one boy, and one girl, in the four examination rooms in the office? 4. How many odd integers from 1000 to 9999 (inclusive) have distinct digits? 5. (a) How many ways can a 5-card poker hand be dealt? (b) How many different 5-card poker hands exist? 6. How many ways exist to place the integers {1,2,3,...,15} on an 8-by-8 checkerboard? 7. How many 7-digit numbers exist such that the following three conditions all hold: the digits 5 and 6 do not appear consecutively, in either order, and we can use the digits 1,2,3,...,9 and the number's digits are distinct? 8. You are given 25 points in a plane, no three collinear. (a) How many straight lines are determined? (b) How many triangles are determined? 9. A classroom has 2 rows, each with 8 seats. Of 14 students, 5 always sit in the front row, 4 always sit in the back row, and the rest sit in either row. How many ways can the students be seated? 10. Mayville State College (ND) has 750 students. How many unique 10-student committees can be formed from the student body? 11. An ISU campus organization includes 30 faculty and 30 students. (a) How many ways can a committee of 8 people be selected so that it includes at least three faculty and at least three students? (b) How many ways can a committee of 8 people be selected so that at least one of the eight is a faculty? 12. How many consecutive zeros (0) are immediately to the left of the decimal point in 52! ? 13. Provided an adequate supply of flags in each of seven colors, how many ways are there to arrange a 5-flag set? 14. How many arrangements are there for three men and three women at a round table?
 Problem Set C Set C possible solutions 1. In how many ways can the letters in the word computer be arranged so that there are no adjacent vowels? 2. Judy returns from the laundromat with a big bag of socks. There are 7 identical red socks, 9 identical white socks, 6 identical green socks, and 12 identical blue socks. If Judy reaches in the bag and grabs socks without knowing the colors, how many must she grab to be sure of selecting a matched pair? 3. What is the sum of the coefficients in the expansion of ? 4. A domino shows a pair of numbers, each from 0 to 12. How many different dominoes could there be if we consider the pairs of numbers (b,a) and (a,b) to be the same domino? 5. What is the coefficient of 6. Twelve identical dice are rolled once. Considering the number showing on the top of each die, how many sets of outcomes are there? 7. In each of 10 identical bags are 6 marbles, one each of red, white, blue, green, pink, and yellow. Marbles of the same color are not distinguishable. In how many ways can we create a collection consisting of one marble from each bag? 8. Five Minutemen and eight Patriots are to be seated at a round table with 13 chairs. If no two Minutemen may be seated together, how many ways can the group be seated? 9. Determine the number of integers from 1 to 2000 inclusive that are not divisible by any of 6, 10, and 35. 10. MaryBeth has budgeted \$100 to give to local charities this year, spent in multiples of \$5. If MaryBeth gives at least \$5 to each of 10 local charities, how many ways can her donations be made? What if MaryBeth gives at least \$5 to each of at most 10 local charities? 11. In how many ways can 8 Qs and 4 Ms be arranged so that no two Ms are adjacent? 12. How many non-negative integer solutions exist for the equation z + y + x + a + b + c = 28? Provide an example of a solution to this equation that is NOT a solution to the same equation over only the positive integers. 13. Suppose you have the nonsense word abbcccddddeeeee, where identical letters are indistinguishable. How many distinct arrangements are there for the letters of this word? How many ways can the letters in the word be arranged so that no two vowels are adjacent? 14. In a certain game 5 dice are rolled together. Two sample outcomes are (1,2,1,2,1) and (1,1,1,2,2), where each digit represents the face-up value on a die. Each of these has the same outcome: three 1s and two 2s. How many different outcomes are possible in this game? 15. In how many ways can three balls of the same color be selected from an urn containing 5 red balls and 6 green balls? 16. In how many ways can you get three 6s, two 4s, four 1s, and one 2 in the roll of 10 distinct dice? 17. Determine the sum of the coefficients in the expansion of . 18. How many uncollected terms are there in ? 19. Which collected terms in the expansion of have coefficients ? 20. What is the absolute difference of the sum of the elements in rows 14 and 15 of Pascal's Triangle? 21. From a standard deck of 52 playing cards, how many ways are there to have a set of 4 cards all of different suits? 22. Seth had his choice from among 5 baseball cards labeled Mantle, Marris, Mays, Mitchell, and Morris. If Seth could choose from 0 to 5 cards, how many ways could he make his selection? 23. In how many ways can two integers be selected from the set {1,2,...,41} such that the sum of the two integers in an even number? 24. From a class of 27 students, a team of 6 is chosen, with one of the 6 designated as team captain. How many such teams are possible? 25. Roger is writing a MAT 305 exam and is looking for a word with exactly three distinct letters with the property that there are no more than 1000 different arrangements of the letters in the word. Describe the composition of such a word, or explain the impossibility of its existence. 26. Uncle David passed away and bequeathed 30 antique pliers to his nephew and niece, Ralph and Sophie. Sophie, a combinatorics prof at Redbird U, agreed to give Ralph all 30 pliers if he could answer this question: If we count all the subsets of the 30 pliers that have an even number of pliers, and count all the subsets that have an odd number of pliers, which group will have more subsets? Ralph really wants the pliers. How should he respond? 27. In how many ways can the 26 letters of the alphabet be arranged so that there are always exactly six letters between the letters c and d? 28. Three committees are to be chosen from 13 eligible members. If the committees must have 5, 3, and 2 people, respectively, and no person may serve on more than one committee, how many ways can the committees be formed? 29. What is the minimum number of human beings that must be assembled to insure that at least two of them share the same birth month? 30. A palindrome is a number that reads the same left to right as right to left, such as 32423. How many 7-digit palindromes are there? Assume that the number 0675760 is not a 7-digit number, because its left-most digit is 0. 31. What is the coefficient of in the expansion of ?
 Problem Set D Set D possible solutions 1. Determine the number of 50-digit sets we can create, choosing from {0,1,...9} and assuring that all digits are represented. 2. How many 100-letter sets can be made using letters from {A,B,...,Z}, assuring that each letter occurs at least once? 3. Repeat problem (1) from Set D with the additional requirement that each digit occur at least twice. 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? 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. 6. How many n-element sets can be created from among {a1, a2,...,ak}, allowing repetition as well as missing elements? 7. Devise a scenario that can be completed in exactly 1001 ways. 8. Five pairs of shoes are displayed. (a) How many ways can three shoes be selected? (b) How many of those in (a) contain a matched pair? (c) When four shoes are selected from the five pairs, what portion of the selections include two matched pairs? 9. Seven coins are flipped simultaneously. What portion of the possible results include getting three heads and four tails? 10. (a) Consider the expansion of (x+y)^13. What is the coefficient of the collected term containing x^8y^5 ? (b) Repeat the question in (a) for (2x-y)^13. 11. Determine the number of 8-letter words that use letters from {A,B,C} and contain exactly three As. 12. A certain state lottery requires participants to select 6 distinct numbers from the set {1,2,...,50}. (a) How many ways can such a selection take place? (b) Determine the probability that a participant has selected exactly k winning numbers, where k ranges from 0 to 6. 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? 14. Determine the number of 10-letter sets, with repetition allowed, from the set {X,Y,Z} that contain: (a) at least one of each letter; (b) at least two of each letter; (c) at least one Z, two Ys, and three Xs; (d) any number of each letter; (e) at least one Y and at least two Xs. 15. Show that C(2n,n) is divisible by n+1.

Problem Set E
Look at possible solutions to Set E problems.

For questions (1) through (5), determine s(5).

1.

s(n)=3*s(n-1) - 9, n>=1, s(0)=5

2.

s(n)=2*s(n-1) + 3n, n>=1, s(0)=5

3.

s(n)=2*s(n-1) + s(n-2), n>=2, s(0)=2, s(1)=-3

4.

s(n)=-s(n-1) +n*s(n-2) - 1, n>=2, s(0)=3, s(1)=4

5.

s(n)=-s(n-1) + 2*s(n-2) + s(n-3) + n, n>=3, s(0)=1, s(1)=2, s(2)=5

6.

Membership dues at Pine Valley Tennis Club were \$50 in 1970 and have increased \$5 per year since then. Write a recurrence relation with initial conditions for m(n), the membership fee n years after 1970.

7.

A passbook savings account earns 5% interest compounded annually. If no additions or withdrawals are made to the account, write a recurrence relation with initial conditions for b(n), the balance in the account after n years.

8.

Each day Freddie buys exactly one item from the following list:

 tape \$1 ruler \$1 pens \$2 pencils \$2 paper \$2 loose-leaf binder \$3

Write a recurrence relation with initial conditions for s(n), the number of different sequences by which Freddie could spend exactly n dollars.

9.

Lolita has an unending supply of identical 2-cent stamps, identical 3-cent stamps, and identical 5-cent stamps. Write a recurrence relation with initial conditions for p(n), the number of different ways in which Lolita could attach exactly n-cents worth of stamps to an envelop, assuming that order of placement on the envelop matters.

10.

Let a(n) represent the number of arrangements of the integers 1,2,...,n, with n>=1. State a recurrence relation with initial conditions for a(n).

11.

Let s(n) represent the number of subsets for a set with n elements, with n>=1. State a recurrence relation with initial conditions for s(n).

12.

Write a recurrence relation with initial conditions for c(n), the number of sequences of nickels, dimes, and quarters inserted into a vending machine to purchase a soft drink costing 5n cents. How many sequences are there for a 50-cent drink?

13.

Write a recurrence relation with initial conditions for s(n), the number of squares of any size that can be found on an n-by-n checkerboard. How many squares are there for an 8-by-8 board?

101.

A child is allowed to take two items from a basket that contains an apple, an orange, a pear, a banana, and a plum. How many different fruit pairs can the child select?

102.

A senior citizen is asked to take two items from a basket that contains two apples, one orange, one pear, and one banana. How many different fruit pairs can the senior select?

103.

Each of r people wants a fruit Danish from the bakery. The bakery has only the following Danish available: 3 cheese Danish, 2 apricot Danish, and 4 raspberry Danish. Determine d(r), the number of fillable orders for r pastries. What is d(7)?

104.

A mountain ski chalet sells a grilled cheese sandwich for \$2 and a bowl of noodle soup for \$3. Determine m(r), the number of ways to order \$r of soup and sandwiches.

Problem Set F
Look at possible solutions to Set F problems.

1.

Generate a difference table for the linear function y = 3x - 5 for 1 <= x <= 8.

2.

Generate a difference table for the general linear polynomial y = ax + b for 1 <= x <= 8.

3.

Repeat problem 1 for the cubic polynomial y = 2x^3 - x^2 + 3x + 1 for 1 <= x <= 8.

4.

Repeat problem 2 for the general cubic polynomial y = ax^3 + bx^2 + cx + d for 1 <= x <= 8.

5.

Complete the difference table for the values in the function y = f(x) shown here.

 x 1 2 3 4 5 6 f(x) 12 28 50 78 112 152 D1 ---> . . . . . . D2 ---> . . . . . D3 ---> . . . .

What type of function is this? How do you know?

6.

Determine an explicit representation for the relationship defined in problem 5.

7.

The table here shows values for x greater than 2. Use the method of constant differences to determine an explicit representation for the relationship shown and then use it to determine f(1) and f(2), assuming the explicit relationship holds for f(1) and f(2).

 x 3 4 5 6 7 8 . f(x) 64 141 266 451 708 1049

8.

Determine an explicit representation for the relationship shown in the table below.

 x 1 2 3 4 5 6 . h(x) 4 23 86 247 584 1199

9.

The standard multiplication table appears to the left below. The pattern to the right is formed by rotating the multiplication table 45 degrees clockwise. Continue the pattern in the right-hand table for at least two more rows. Then determine a function that can be used to calculate the sum of any row in the right-hand table. Use it to determine the sum of the 100th row in that table.

 1 2 3 4 5 6 2 4 6 8 10 12 3 6 9 12 15 18 4 8 12 16 20 24 5 10 15 20 25 30 6 12 18 24 30 36
 1 2 2 3 4 3 4 6 6 4 5 8 9 8 5

10.

Determine an explicit representation for the sum of any row in the infinite array whose first three lines are shown here.

```(1 x 2) =

(1 x 2) + (2 x 3) =

(1 x 2) + (2 x 3) + (3 x 4) =```

Problem Set G
Set G possible solutions

Use the following generating functions and simplify each expression in (1) and (2).

1.

 (a) A + B (b) B + C (c) B + D (d) C + F

2.

 (a) AB (b) AC (c) AD (d) DE

3.

Write a generating function to determine the number of ways of choosing d drinks from a refrigerator that has 3 colas and 5 root beers. Expand your function through the 6th power.

4.

Write a generating function to determine the number of ways of choosing j jelly beans from a basket that has 3 licorice, 4 strawberry, and 2 lemon jelly beans. Expand your function through the 6th power.

5.

Write a generating function to determine the number of ways of buying p chicken parts at a grocery has 4 wings, 3 breasts, and 5 drumsticks, if the drumsticks are wrapped in a package of 2 and a package of 3 and the packages cannot be divided. Expand your function through the 6th power.

6.

Write a generating function to determine the number of ways of ordering g glasses of liquid, if 3 glasses of milk and and unlimited supply of water are available. Expand your function through the 6th power.

7.

A bakery has an unlimited supply of apple danish pastries but only three cream cheese danish pastries and only four strawberry danish pastries. The strawberry danish must be purchased two at a time.

(a) Write a generating function for the number of ways to buy r pastries under these conditions.

(b) Expand (a) through the 8th power.

(c) How many ways are there to buy 7 pastries?

8.

Genny has a large supply of 1-cent, 2-cent, and 3-cent stamps. The stamps of each denomination are identical.

(a) Write a generating function that will determine the number of ways to arrange exactly three of the stamps in a row on an envelope so that their total value is c cents.

(b) Repeat (a) if four stamps can be used.

(c) Repeat (a) if three or four stamps can be used.

(d) Repeat (a) if any positive number of stamps can be used.

(e) Use (d) to show the number of ways to arrange 4 cents worth of stamps.

9.

Write a generating function to determine the number of ways to make change for a \$1 bill, given an adequate supply of nickels, dimes, quarters, and half-dollars. Do not expand your function, but do explain how you would use it to determine a solution.

Problem Set H

Look at possible solutions to Set H problems.

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?

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?

3.

How many ways are there to arrange these letters so that no vowels are adjacent?

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.

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

5.

Determine the number of uncollected terms in the expansion.

6.

Determine the number of collected terms in the expansion.

7.

Determine the coefficient K for the collected term .

8.

How many collected terms are of the form , m,n from among {a,b,c,d,e,f,g} and 0 <= k <= 26?

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?

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?

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?

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?

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?

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.

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.

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.

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?

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?

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.

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?

21.

How many ways can Seth arrange the 28 cards in a circle?

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?

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?

24.

Write an inductive proof to justify the following conjecture.

25.

Write the next 6 terms in the following recurrence relation.

• a(n) = 2a(n-1) - 3a(n-2), a(0 )= 2, a(1) = 5

26.

Write both a recursive and an explicit representation for the following sequence of values.

• 5,17,41,89,185

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