Illinois State University Mathematics Department


MAT 305: Combinatorics Topics for K-8 Teachers

Spring 2003
Dr. Roger Day (day@math.ilstu.edu)



Possible Solutions: Test #2

Please write your solutions on one side only of each piece of paper you use, and please begin each solution on a new sheet of paper. You may use factorial notation as well as combination and permutation notation where appropriate (i.e., there is no need to expand 24!).

You are to work alone on this test. You may not use anyone else's work nor may you refer to any materials as you complete the test. You may ask me questions.

Evaluation Criteria

You may earn up to 10 points on each of questions 1 through 6. For each question:

  • 6 points count toward a correct solution to the problem. I will evaluate the mathematics you use:
    • Is it accurate and appropriate?
    • Have you provided adequate justification?
  • 4 points count toward how you express your solution. I will evaluate how you communicate your results:
    • Is your solution clear and complete?
    • Have you expressed logical connections among components of your solution?

1.

Respond to each question below by placing your solution in the blank. While you may show steps leading to your solution, you do not need to generate written explanations for questions (a) through (e) on this page.

a) How many distinct arrangements exist for the letters in the word TRANSFERRERS? (2 points)

Solution: (12!)/(4!2!2!)

The numerator represents the number of ways to arrange the letters in the given word. The denominator represents the accounting for duplication in arrangements due to duplicate letters.

b) Consider the expansion of (k + j + m + n)^13.

(i) State the number of uncollected terms. (1 point)

(ii) State the value of the coefficient C in the collected term Ck^2j^3m^5n^3. (1 point)

Solutions: (i) 4^13 (ii) (13!)/(2!3!5!3!)

(i) There are 13 opportunities to choose exactly one letter from among the four k,j,m,n.

(ii) Imagine a 13-letter word made up of 2 letters k, 3 letters j, 5 letters m, and 3 letters n. Now follow the process used in Problem (1a) above. 

c) Use Pascal's Formula to express C(21,8) &endash; C(20,7) as a single combination. (2 points)

Solution: C(20,8)

By Pascal's Formula, we know that C(21,8)=C(20,8)+C(20,7). Now subtract C(20,7) from each side to get the desired result.

d) Suppose that S(k) represents the sum of the elements in the kth row of Pascal's Triangle. For instance, S(0) = 1 and S(1) = 2. Express S(9) + S(10) as a multiple of S(9). (2 points)

Solution: 3*S(9)

We know that the sum of the terms in row k is 2^k. Therefor, S(9)=2^9 and S(10)=2^10. The sum S(9)+S(10)=2^9+2^10. We factor the right side to get S(9)+S(10)=2^9(1+2)=3*2^9. 

e) For the equation A+B+C+D+E+F=4, how many possible solutions exist if the variables can take on values that are non-negative integers? (2 points)

Solution:C(9,5)

This problem is analogous to the problem of determining the number of ways to distribute 4 objects among 6 categories, with the certainly the one or more categories will have no objects. 

2.

Jack needed to arrange 12 hats on a display shelf. Seven of the hats were red and the other five were blue. The hats were distinguishable only by color.

a) If it was required that none of the blue hats could be adjacent to one another, how many unique arrangements were there of hats on the shelf? (5 points)

Solution: C(8,5) unique arrangements

First, arrange the red hats. This can be done in exactly one way, for they are indistinguishablefrom one another. The seven red hats create 8 places among them whereby blue hats can be places and have blue hats remain non-adjacent. We therefore choose 5 of these 8 positions for the blue hats. Because the blue hats are not distinguishable from one another, we need account no further for their arrangement.

b) Instead of (a), suppose it was required that all the blue hats must be kept together. How many unique arrangements of hats on the shelf are there under this restriction? (5 points)

Solution: 8!/7! = 8 ways

Treat the blue hats as one unit. Together with the 7 red hats, there are 8 objects to place.These objects can be arranged in 8! ways, but we divide by 7! to account for the 7 non-distinguishable red hats.

3.

My in-laws live in a retirement community. Among all individual residents within the community, we know that::

  • 38 play golf
  • 21 play tennis
  • 56 play bridge
  • 8 play golf and tennis
  • 17 play golf and bridge
  • 13 play tennis and bridge
  • 5 play golf, tennis, and bridge
  • 72 do not play golf, tennis, nor bridge

a) How many individual residents are there in this retirement community? (5 points)

Solution: 154 people

The Venn diagram here shows a picture of the information provided. The eight numerical values in the diagram represent all those in the community, so the total population is just the sum of those eight values.

b) How many of the individual residents participate in only and exactly one of the three activities? (5 points)

Solution: 54 people

From the diagram, we see that 18 play only golf, 5 play only tennis, and 31 play only bridge. The sum of these three values is the solution we seek.

4.

Consider the letters in the word INSURRECTIONISTS.

a) How many unique arrangements are there for the letters in this word? (3 points)

Solution: (16!)/(3!3!2!2!2!)

The numerator represents the number of ways to arrange the letters in the given word. The denominator represents the accounting for duplication in arrangements due to duplicate letters.

b) How many unique arrangements exist if each arrangement must begin and end with the letter R? (3 points)

Solution: (14!)/(3!3!2!2!)

There are exactly 2 Rs, and because they are identical, they can be placed in only one way. There now remain 14 letters to place. The numerator represents the number of ways to arrange those 14 letters. The denominator represents the accounting for duplication in arrangements due to duplicate letters.

c) How many unique arrangements exist if all the letters I must be kept together and they may not appear at either end of the word? (4 points)

Solution: (i) 14!/(3!2!2!2!)-(2*13!)/(3!2!2!2!) or (ii) (12*13!)/(3!2!2!2!)

The identical letters I can now be treated as one unit. There remain 14 objects (13 letters and the I-group) to arrange.

(i) Arrange all 14 objects and subtract those with the I-group at either end.

(ii) Arrange the remaining 13 letters and place the I-group in one of the 12 slots among the 13 letters (not on the ends).

We can show that expressions (i) and (ii) are identical.

5.

Iamso Piceune has a particular love for the chocolate-chip cookies served at Blaise's Bistro. Every weekday, Monday through Friday, Iamso has coffee at the Bistro and may or may not eat one or more chocolate-chip cookies.

a) Iamso decided he would consume exactly 15 chocolate-chip cookies per week at the Bistro, and would always eat at least one each day. Determine the maximum number of weeks Iamso could do this without repeating the same 5-day cookie-eating pattern. (5 points)

Solution: C(14,4) weeks

This is analogous to determining the number of positive integer solutions to the equation M+T+W+R+F=15. There are C(15-1,5-1) such solutions.

b) For a long time, Iamso followed the cookie-consumption pattern described in (a). Later, upon advice from his doctor, he changed his cookie-eating pattern. He decided to eat only and exactly 5 cookies per week, with two conditions:

  • (i) It was okay, on one or more days of the week, to eat no cookies, and
  • (ii) He could never eat all 5 cookies in one day.

How many different weekly cookie-eating patterns could Iamso follow under these conditions?

Solution: C(9,4)-5 weekly patterns

By condition (i), this is analogous to solving the equation M+T+W+R+F=5 over the non-negative integers. There are C(5+5-1,5-1)=C(9,4) such ways. By (ii) we must eliminate from the C(i,4) ways those with 5 as the value of one variable. There are 5 such ways to eliminate.

6.

At a local opera, patrons can check their hats prior to entering the auditorium.

a) Suppose that 6 people each check a hat prior to a performance. Those same 6 people are now in line to retrieve the hats. If the 6 hats are returned at random to the 6 people, with no attention paid to whether a hat is returned to its rightful owner, what portion of all possible ways to return the hats will result in no one receiving the correct hat? Here's another way to pose this question: What is the probability that no one receives a correct hat? (5 points)

Solution: D(6)/6!=265/720=53/144 (approximately 0.3681)

We need the ratio of the number of derangements of 6 distinct objects to the total number of ways to arrange 6 distinct objects.

b) Generalize the problem above to answer the question for n people. What value does the probability approach as n grows larger and larger? (5 points)

Solution:

D(n)/n! = [n!(1-1+(1/2!)-1/3!)+...+(-1)^n*(1/n!)] / n! = 1-1+(1/2!)-1/3!)+...+(-1)^n*(1/n!) which approaches approximately 0.367879441171... or exactly 1/e, where e is the natural exponential.


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