Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8 Teachers Spring 1999 
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 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 
. 

2. 
Members of a mathematics department will take a oneday course on using the TI89 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 signup 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+41,41)=C(39,3) b. If at least one faculty member must signup for each of the days the course is offered, how many ways exist for the department to sign up for the courses? C(361,41)=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+41,41)=C(20,3). 
. 

3. 
Members of a 7thgrade 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 7thgrade 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. 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:
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. 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
twoinput 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. C(4,1)*C(3,1)=12 C(4,1)*C(3,2)=12 C(4,2)*C(2,1)=12 C(4,1)*C(3,3)=4 C(4,2)*C(2,2)=6 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 2letter, 1letter 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. 
. 




