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: Test #2

1.

Respond to each of these questions 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) of question (1).

a. Express C(10,4) in terms of P(10,6).

C(10,4)=C(10,6), and C(10,6)=P(10,6)/6! so C(10,4)=P(10,6)/6!.

b. How many distinct arrangements exist for the letters in the word ATTESTANT?

9!/(2!4!)

c. In the expansion of (m + n + p)^10, determine the number of:

(i) uncollected terms

3^10

(ii) collected terms

C(12,2)

d. Express C(n,k) + C(n,k + 1) as a single combination.

C(n+1,k+1)

e. Let S(k) represent the sum of the elements in row k of Pascal's Triangle. For example, S(0) = 1 and S(1) = 2. Express S(12) - S(10) in terms of S(10).

S(12)=2^12 and S(10)=2^10, so
S(12)-S(10)=2^12-2^10=2^10(2^2-1)=3*(2^10)=3*S(10).

.

2.

Members of a mathematics department will take a one-day course on using the TI-89 calculator in collegiate mathematics instruction. All 36 instructors in the department must take the course and can take the course only once. The course will be offered on the Monday, Tuesday, Wednesday, and Thursday immediately after spring semester graduation. Faculty must sign-up in advance for the day they wish to complete the course.

In the following questions, we are not concerned about who among the faculty members take the course on a certain day, but about how many take the course each day.

a. If there are no restrictions about how many take the course on any one day, how many ways exist for the department to sign up for the courses?

C(36+4-1,4-1)=C(39,3)

b. If at least one faculty member must sign-up for each of the days the course is offered, how many ways exist for the department to sign up for the courses?

C(36-1,4-1)=C(35,3)

c. Because of availability of course leaders, it is necessary to assure that certain enrollments are met for specific days the course is offered. Administrators determined that at least 5 faculty members must take the Monday course, at least 4 faculty members must take the course on Tuesday and at least 4 on Wednesday, and there must be more than 5 enrolled for the Thursday version. How many ways now exist for the department to sign up for the courses?

With the stated restrictions, placement of 19 faculty is assured. This leaves 17 to distribute, with possibility that one or more days may have no more enrollees. C(17+4-1,4-1)=C(20,3).

.

3.

Members of a 7th-grade class recently identified their interests in collecting things. Among those enrolled in the class, 15 collect stamps, 14 collect coins, and 18 collect hobby cards. Exactly 8 of the students collect both stamps and coins, 7 of them collect both coins and hobby cards, and 9 of them collect stamps and hobby cards. In the class, there are 6 students who collect stamps, coins, and hobby cards.

If at least one student enrolled in this 7th-grade class does not collect any of the items listed above, what is the smallest number of students enrolled in this class?

Using a Venn diagram we can count those students accounted for according to the description of their collecting interests. With at least one student who does not collect any of the three items listed, there must be at least 30 students enrolled in the class.

.

4.

In the expansion of (a + b + e + d + e)^21, determine the number of different ways a coefficient of 21 appears among the collected terms.

We want to determine the number of times K=21 when we examine the collected terms of the form Ka^Ab^Bc^Cd^De^E where A+B+C+D+E=21 over the nonnegative integers.

We know that K=(21!)/(A!B!C!D!E!), the multinomial coefficient. For K to be 21, it must be the case that A!B!C!D!E!=20! [Why is that?] For that to be true, two conditions must be met: (i) We must have exactly one of A, B, C, D, or E equal to 20 and (ii) the remaining 4 values must sum to 1.

There are 5 ways for the first condition to be met: A or B or C or D or E must be 20. There are 4 ways for the second condition to be met: one of the four remaining values from among A,B,C,D,E must be 1 and the other three must be 0.

By the multiplication principle, there are 5*4=20 total ways for a coefficient of 21 to appear.

.

5.

How many ways can the letters in the word adequateness be arranged so that three consonants start the arrangement and three consonants end the arrangement?

Here is a sequence of steps that develops the elements we need in order to solve the problem.

  • Choose and permute three of the six consonants, to be placed in front: P(6,3)
  • Permute the remaining three consonants to be placed at the end: Multiply by P(3,3)=3!
  • Correct for duplication caused by appearance of 2 Ss: Divide by 2!
  • Permute the 6 vowels: Multiply by P(6,6)=6!
  • Correct for duplication caused by appearance of multiple vowels: Divide by 2!3!

This results in this solution: [P(6,3)*3!*6!] / [2!2!3!] = [P(6,3)*6!] / [2!2!]

.

6.

My friend Michael Link posed this problem when we met as part of an NCTM committee. It seems that while at school one day, he met a locksmith who was trying to fix a door lock. The lock was a type you may have seen before, where the user presses buttons in a certain sequence to open the lock.

This particular lock had four pads arranged vertically, each labeled with a different letter A, B, C, and D. A valid combination for the lock met the following restrictions:

  • The combination must have exactly two inputs.
  • An input means to press from one, two, or three letters simultaneously.
  • No letter could be pressed more than once.
  • Input order is important. For example, to press "A" and then the pair "B/D" represents a different combination than to press "B/D" and then "A." However, the single input "B/D" is the same as the single input "D/B" because the two letters are pressed simultaneously.

How many different combinations exist for the lock described here?

From the restrictions on a valid combination that are provided with the question, there are exactly six different ways to create exactly two inputs, as shown in the table below.

1 letter, 1 letter

1 letter, 2 letters
2 letters, 1 letter

1 letter, 3 letters
2 letters, 2 letters
3 letters, 1 letter

The entries in the table show the number of letters contained in the first input and the number of letters contained in the second input. For example, "1 letter, 3 letters" means that the two-input combination was made up of the first input being one letter and the second input being three letters. The combination A,C/B/D is such a combination.

For each of the six entries in the table, we now need to determine how many distinct combinations can be created. The next table shows this.

1 letter, 1 letter

C(4,1)*C(3,1)=12

1 letter, 2 letters

C(4,1)*C(3,2)=12

2 letters, 1 letter

C(4,2)*C(2,1)=12

1 letter, 3 letters

C(4,1)*C(3,3)=4

2 letters, 2 letters

C(4,2)*C(2,2)=6

3 letters, 1 letter

C(4,3)*C(1,1)=4

For each case, a product of two combinations is shown. The first factor calculates the number of ways to create the first input for the combination and the second factor shows the number of ways to create the second input for the combination. For example, For a 2-letter, 1-letter combination, the first input, consisting of two letters, can be created in C(4,2) ways, and the second input, consisting of one letter, can be created in C(2,1) ways.

Two important points need to be emphasized in these calculations. First, combinations are used based on the fourth entry in the retstrictions list above: When two or three letters comprise an input, they are pressed simultaneously, so the order does not matter. Second, the second factor in each product represents a selection made from the letters remaining after the first input of the combination has been created.

Because the six cases described above are disjoint, we add the individual results to calculate the desired number of combinations possible. This total is 50 combinations.

.

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