Illinois State University Mathematics Department


MAT 305: Combinatorics Topics for K-8 Teachers

Spring 1999
6:00 - 8:50 pm Tuesday STV 332
Dr. Roger Day (day@math.ilstu.edu)



Possible Solutions: Semester Exam

1.

a. If we label the rows of Pascal's Triangle starting with n = 0 and the columns starting with k = 0, what is the value of the entry in row 14, column 11?

C(14,11)

b. Express P(18,3) in three different ways: (i) as the product of three consecutive integers; (ii) using factorial notation; and (iii) in terms of C(18,3).

(i) 18*17*16

(ii) 18!/15!

(iii) C(18,3)*3!

c. In how many ways can 12 donuts be distributed to 6 people, allowing that some may receive no donuts or that one person may get them all?

The problem reduces to determining the number of non-negative integer solutions to the equation x1 + x2 + x3 + x4 + x5 + x6 = 12. There are C(12 + 6 - 1,6 - 1) = C(17,5) such ways.

d. A biologist plans to complete an experiment with 14 mice, aptly numbered 1 through 14. Six of the mice will receive a double dose of Vitamin E, 5 of the mice will receive a single dose of Vitamin E, and the rest will receive no doses of Vitamin E. In how many ways can this distribution take place?

C(14,6)*C(8,5)*C(3,3) = 14!/(6!5!3!)

e. A committee of three is to be formed from among four men (Adam, Bill, Cal, and Dan) and four women (Eve, Fran, Gert, and Hanna). In how many ways can this be done if Adam and Eve refuse to serve on it together?

There are three disjoint cases to consider:

I) Neither Adam nor Eve are on the committee: In this case, we must select 3 from the remaining 6 possible committee members: C(6,3).

II) Eve is on the committee, Adam is not: We need to select 2 more committee members from the 6 remaining people: C(6,2).

III) Eve is not on the committee, Adam is: Same reasoning as for (II): C(6,2).

This results in C(6,3) + 2*C(6,2) different ways to create the committee.

2.

The following conjecture is to be proven true by induction or shown to be false using a counterexample: 1 + 2 + . . . + (n-1) + n + (n-1) + . . . + 2 + 1 = n^2.

a. Describe and carry out the first step in the induction process.

We need to show that the result holds for the case n=1. Here, when n = 1, we have 1 = 1^2, which is a true statement.

b. Describe and carry out the second step in the induction process.

We assume that the result holds for the case when n = k. for this problem, then, we assume that 1 + 2 + . . . + (k-1) + k + (k-1) + . . . + 2 + 1 = k^2.

c. Describe but do not carry out the third step in the induction process.

In this step, we show that, based on the assumption made in Step 2, the result holds for the case when n = k+1.

3.

There are 6 men and 5 women on a committee. A subcommittee of 6 is to be formed. The subcommittee must have no less than two men and two women. In how many ways can such a subcommittee be formed?

We must consider three disjoint cases that represent all possible compositions of the committee.

I) There are 2 men and 4 women on the committee. For this case, we choose 2 men from 6 and 4 women from 5. We then match each possible group of men with each possible group of women. This can be done in C(6,2)*C(5,4) ways.

I) There are 3 men and 3 women on the committee. For this case, we choose 3 men from 6 and 3 women from 5. We then match each possible group of men with each possible group of women. This can be done in C(6,3)*C(5,3) ways.

I) There are 4 men and 2 women on the committee. For this case, we choose 4 men from 6 and 2 women from 5. We then match each possible group of men with each possible group of women. This can be done in C(6,4)*C(5,2) ways.

This gives us C(6,2)*C(5,4) + C(6,3)*C(5,3) + C(6,4)*C(5,2) ways to form the committee.

4.

A domino is a rectangle formed by two congruent squares. Each square contains an orderly pattern of "pips" or dots representing a number from zero through six. How many different dominoes can be made under these restraints?

We consider two different cases that are disjoint.

I) The domino has a different number of pips in each of the two squares. In this case, there are 7 numbers possible for one square and 7 for the other. This yields 42 dominoes. Note, however, that the domino 5:6 is not distinguishable from the domino 6:5. Therefore, therefore half of the 42 dominoes counted here will be duplicates. We have 21 different dominoes each with a different pair of numbers.

II) The domino has the same number of pips in each of the two squares. There are seven such dominoes, from 0:0 to 6:6.

We have a total of 28 dominoes that can be created under the described conditions.

5.

For some positive integer n, how many integers between 0 and 2n inclusive must you pick to be sure that at least one of them is odd?

The set in question is {0,1,2,3,4,...,2n-1,2n}. There are n+1 even numbers in the set, consisting of 0,2,4,...,2n. Thus, it is possible we could pick n+1 values from the original set and still have no even number. The next pick, however, would have to be an odd number.

By the pigeonhole principle, we need n+2 values to assure that at least one of them is odd.

6.

Suppose that Jay Cool and the Gingos are playing at the Starlite Theatre. The theatre has one section of seats, arranged with 70 seats in the first (front) row, 72 seats in the second row, 74 seats in the third row, and so on, for a total of 30 rows. The seats are numbered from left to right, with the first seat in the first row being #1, the first seat in the second row #71, and so on.

a. Write a recurrence relation and an explicit formula for R(n), the number of seats in Row n. Be sure to include information about initial conditions. Use your results to determine the number of seats in the last (30th) row.

Recurrence Relation: Each successive row contains 2 more seats than the previous row. So if we begin with R(1) = 70 as the initial condition, we get R(n) = R(n-1) + 2 as the recurrence relation.

Explicit Formula: This is a linear pattern, noting the constant difference of 2 seats between each consecutive pair of rows. The explicit formula is R(n) = 68 + 2n, where n is the row number and n spans the positive integers from 1 through 30.

Either relationship yields the value R(30) = 128 seats.

b. Write either an explicit formula or a recurrence relation for S(n), the sum of all seats through Row n. Use that to determine the total number of seats in the theatre.

Recurrence Relation: We begin with S(1) = 70 as the initial condition. Each successive sum will contain all the seats prior to that row plus all the seats in that row. The number of seats in any particular row was determined above: R(n) = 68 + 2n. This leads to S(n) = S(n-1) + (68 + 2n) as a recurrence relation for the row sums.

Explicit Formula: This is a quadratic pattern, determined using a difference table and observing that the first constant difference occurs in the second differences, that is, in line D2 of the table. Associating this specific difference table with the difference table for the general quadratic results in an explicit formula of S(n) = n^2 + 69n.

Either relationship yields the value S(30) = 2970 seats.

7.

The set of letters {A,A,A,B,B,B,B,C,C} is to be used to create k-element subsets.

a. State the range of values for k that is possible for this situation.

Allowing for a subset that is empty as well as a subset containing all elements for the set, k could be any value in the set {0,1,2,...,9}.

b. How many subsets in all can be created?

If we allow for duplicate letters to be used as appear in the original set (i.e., one A is different from another) there are 2^9 subsets.

If we do not allow for this, for example, only one subset exists of the form {A,B,C,C} no matter which of the As and Bs are chosen, then there are 60 unique subsets. This can be determined by brute force listing of all unique subsets and can also be determined by summing the coefficients of an appropriate generating function.


Create a generating function that can be used to determine the number of 6&endash;element subsets that will have at least one A and at least two Bs.

c. Show the factors of the generating function before expanding them. Explain what each factor represents within the context of this problem.

The factors are (x+x^2+x^3)(x^2+x^3+x^4)(1+x+x^2). Concentrate on the exponents in the terms of each factor. The first factor represents the possible number of As we could include: 1,2, or 3. The second factor represents the possible number of Bs to include: 2,3, or 4. The last factor represents the possible number of Cs we could include: 0, 1, or 2.

d. Expand your response to part (c).

x^3 + 3x^4 + 6x^5 + 7x^6 + 6x^7 + 3x^8 + x^9

e. Use part (d) to determine the number of 6-element subsets that will have at least one A and at least two Bs. Include a brief explanation for how you used part (d).

According to the expansion in (d), there are 7 6-element subsets of {A,A,A,B,B,B,B,C,C} that include at least one A and at least two Bs. This value is the coefficient of the term in the expansion for which x is raised to the 6th power, where the 6 represents the number of elements in the subset.

8.

Determine numerical values for x, y, and z that make a collected term in the expansion of .

We must have x+y+z=k and we must have k!/(x!y!z!)=210. By trial and error, one set of values that satisfies these conditions is k=7 and x,y,z matched with elements of the set {2,2,3}. Can you come up with other sets, or show that this is the only solution?

9.

a. How many positive integers are there that are composed of n digits such that each digit is 1, 2, or 3?

For an n-digit number, each digit could be one of three values, either 1, 2, or 3. This means there are 3^n positive integers that meet the desired condition.

b. Of these, how many contain all three of the digits 1, 2, and 3 at least once?

We apply the inclusion/exclusion principle here to eliminate the positive integers counted above that DO NOT contain each of 1, 2, and 3 at least once. We consider ways to create n-digit numbers that are missing at least one of 1, 2, and 3.

Begin by answering the following question: How many ways are there to create an n-digit number composed of no more than two of the values 1, 2, or 3?

Each of the n values in such a number can be selected from only two choices, so there are 2^n such numbers. Thus, if we want an n-digit number with only 1s or 2s in it (i.e., 3 is not included), there are 2^n ways to create it. This would be true for an n-digit number with only 1s or 3s in it (i.e., 2 is not included), as well as for an n-digit number with only 2s or 3s in it (i.e., 1 is not included). Therefore, there are 3*2^n n-digit numbers, from the set determined in (a) above, that have at most two different digits in them.

But this collection of n-digit numbers includes some duplication, for some of the n-digit numbers have only one unique digit in them, and we have counted those twice. So we must add back the number of n-digit positive integers that contain only one unique digit from the set {1,2,3}. There are just three such numbers, an n-digit number composed of all 1s, an n-digit number composed of all 2s, and an n-digit number composed of all 3s.

So, by the inclusion/exclusion principle, we have 3^n - 3*2^n + 3 n-digit numbers that contain each of the three digits 1,2, and 3, at least once.

10.

My nephew Seth noticed that Kellogg's cereals offers a set of 5 cartoon characters in its current cereal selections. One cartoon character is in each specially marked box of cereal and the cartoon characters are equally distributed among the cereal boxes currently coming off the production line.

Seth has been around me enough so that he can figure out some probabilities. He knows that the probability of getting a complete set by purchasing less than five boxes is 0. He also explained how to determine the probability he could get a complete set by buying exactly 5 boxes of cereal. He said that there are 5! ways he could buy 5 boxes and get all different characters. He also told me that there were 5^5 different ways to get a set of 5 characters, not necessarily all different. The probability of getting a complete set in the first five purchases is 5!/(5^5).

Here's where he needs your help: What's the probability that it takes exactly 6 boxes of cereal to collect a complete set of 5 cartoon characters?

For it to require exactly 6 boxes to assemble a complete set of 5 cartoon characters, two conditions must hold.

  • Among the first 5 boxes purchased, there must be exactly 4 different cartoon characters. This means there are two of one type and one each of three other types.
  • The sixth box purchased must contain the missing, or fifth, character.

We determine in how many ways each of these conditions can occur.

The second condition is straightforward in determination: There are 5 different characters that could occupy the last position in the line up, that is, be in the sixth box.

For each of those 5 possibilities in the last position, we now determine ways to meet the first condition. Two things need to be considered: (a) Which or the four remaining letters will be repeated among the first five boxes opened? (b) What is the arrangement of the five letters (four unique letters) once (a) has been determined?

For (a), there are 4 choices, because one letter has already been used as the last (sixth box). For (b), a way to think of this is to determine the number of arrangements of a 5-letter word composed of 4 different letters, such as 5-letter words composed on 4 letters from the set {A,B,C,D}. One such word is ABCDA, and another is DCBBA. This is a problem we've solved several times. We know there are 5!/(2!1!1!1!) arrangements of those letters.

Associating the results from considering these conditions, we have 5*4*[5!/(2!1!1!1!)] or 1200 such arrangements of the cartoon characters.

In all, there are 5^6 different ways to get cartoon characters in the first six boxes, for with each box there are 5 items than could be in it.

Our desired probability is 5*4*[5!/(2!1!1!1!)]/(5^6) or 1200/(5^6), approximately 7.65%. This is just less than double the probability Seth determined for the first 5 boxes, which was 3.84%.

BONUS!

Each week two World Professional Tennis Organizations determine who are the #1 players in the world for both womens' and mens' professional tennis.

a. Steffi Graf was #1 in womens' tennis without interruption over the period Monday, August 17, 1987, until Sunday, March 10, 1991. This is the greatest number of consecutive weeks that any woman or man has been #1 in the professional rankings. How many consecutive weeks were there in Steffi Graf's record? Clearly show your work in solving the problem.

b.Steffi Graf was also ranked #1 during these time periods:

  • August 5 to August 11, 1991
  • August 19 to September 8, 1991
  • June 7, 1993, to February 5, 1995
  • February 20 to February 26, 1995
  • April 10 to April 30, 1995

Including your response to (a), for how many total weeks of her career, through 30 April 1995, was Steffi Graf ranked #1?

The solution to this problem will appear soon. Keep trying!

 

 

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