Sum Rule Principle: Suppose A and B are disjoint sets. Then:
This chapter develops some techniques for determining, without direct enumeration, the number of possible outcomes of a particular experiment or event or the number of elements in a particular set. Such sophisticated counting is sometimes called combinatorial analysis.
There are two basic counting principles which are used throughout this chapter. One involves addition and the other involves multiplication.
The first counting principle follows:
This principle can be stated in terms of sets, and it is simply a restatement of Lemma 1.4.
Sum Rule Principle: Suppose A and B are disjoint sets. Then:
Clearly, this principle can be extended to three or more events. That is, suppose an event E1 can occur in n1 ways, a second event E2 can occur in n2 ways, a third event E3 can occur in n3 ways, and so on, and suppose no two of the events can occur at the same time. Then one of the events can occur in 
ways.
EXAMPLE 2.1
(a) Suppose there are 8 male professors and 5 female professors teaching a calculus class. A student can choose a calculus professor in 
ways.
(b) Suppose there are 3 different mystery novels, 5 different romance novels, and 4 different adventure novels on a bookshelf. Then there are
ways to choose one of the novels.
The second counting principle follows:
This principle can also be stated in terms of sets, and it is simply a restatement of Theorem 1.11.
Product Rule Principle: Suppose A and B are finite sets. Then:
Clearly, this principle can also be extended to three or more events. That is, suppose an event E1 can occur in n1 ways, then a second event E2 can occur in n2 ways, then a third event E3 can occur in n3 ways, and so on. Then all of the events can occur in 
… ways.
EXAMPLE 2.2
(a) Suppose a restaurant has 3 different appetizers and 4 different entrees. Then there are
different ways to order an appetizer and an entree.
(b) Suppose airline A has 3 daily flights between Boston and Chicago, and airline B has 2 daily flights between Boston and Chicago.
(1) There are 
ways to fly airline A from Boston to Chicago, and then airline B from Chicago back to Boston.
(2) There are 
ways to fly from Boston to Chicago; and hence 
ways to fly from Boston to Chicago and then back again.
(c) Suppose a college has 3 different history courses, 4 different literature courses, and 2 different science courses (with no prerequisites).
(1) Suppose a student has to choose one of each of the courses. The number of ways to do this is:
(2) Suppose a student only needs to choose one of the courses. Clearly, there are
courses, and so the student will have 9 choices. In other words, here the sum rule is used rather than the multiplication rule since only one of the courses is chosen.
The product of the positive integers from 1 to n inclusive occurs very often in mathematics and hence it is denoted by the special symbol n!, read “n factorial”. That is,
In other words, n! may be defined by
It is also convenient to define 
EXAMPLE 2.3
; 
; 
; 
(e) Using (d), we get:
A direct evaluation of n! when n is very large is impossible, even with modern-day computers. Accordingly, one frequently uses the approximation formula
(Here 
….) The symbol ~ means that as n gets larger and larger (that is, as 
, the ratio of both sides approaches 1.
The symbol 
, where r and n are positive integers with 
[read: “nCr” or “n choose r”], is defined as follows:
The equivalence of the two formulas is shown in Example 2.3(e).
Note that 
. This yields the following important relation:
Lemma 2.1: 
or, equivalently, 
where 
.
Remark: Motivated by the second formula for and the fact that 0! = 1, we define:
EXAMPLE 2.4
Note that has exactly r factors in both the numerator and the denominator.
(b) Suppose we want to compute 
. By definition,
On the other hand, 
hence using Lemma 2.1 we get:
Observe that the second method saves both space and time.
The numbers are called the binomial coefficients since they appear as the coefficients in the expansion of 
. Specifically, the following Binomial Theorem gives the general expression for the expansion of :
Theorem 2.2 (Bionomial Theorem): 
This theorem is proved in Problem 2.34 using mathematical induction.
The coefficients of the successive powers of a + b can be arranged in a triangular array of numbers, called Pascal’s triangle, as pictured in Fig. 2-1. The numbers in Pascal’s triangle have the following interesting properties:
(i) The first and last number in each row is 1.
(ii) Every other number in the array can be obtained by adding the two numbers appearing directly above it. For example, 
, 
, 
Since the numbers appearing in Pascal’s triangle are the binomial coefficients, property (ii) of Pascal’s triangle comes from the following theorem (proved in Problem 2.7):
Theorem 2.3: 
Any arrangement of a set of n objects in a given order is called a permutation of the objects (taken all at a time). Any arrangement of any 
of these objects in a given order is called an r permutation or a permutation of the n objects taken r at a time. Consider, for example, the set of letters a, b, c, d. Then:
(i) bdca, dcba, acdb are permutations of the four letters (taken all at a time).
(ii) bad, adb, cbd, bca are permutations of the four letters taken three at a time.
(iii) ad, cb, da, bd are permutations of the four letters taken two at a time.
The number of permutations of n objects taken r at a time will be denoted by
P(n, r)
Before we derive the general formula for P(n, r) we consider a particular case.
EXAMPLE 2.5 Find the number of permutations of six objects, say A, B, C, D, E, F, taken three at a time. In other words, find the number of “three-letter words” using only the given six letters without repetitions.
Let the general three-letter word be represented by the following three boxes:
The first letter can be chosen in 6 different ways; following this, the second letter can be chosen in 5 different ways; and, following this, the last letter can be chosen in 4 different ways. Write each number in the appropriate box as follows:
Accordingly, by the product rule principle, there are 
possible three-letter words without repetitions from the six letters, or there are 120 permutations of six objects taken three at a time. Thus, we have shown that
The derivation of the formula for the number of permutations of n objects taken r at a time, or the number of r permutations of n objects, P(n, r), follows the procedure in the preceding example. The first element in an r permutation of n objects can be chosen in n different ways; following this, the second element in the permutation can be chosen in n- 1 ways; and, following this, the third element in the permutation can be chosen in n- 2 ways. Continuing in this manner, we have that the rth (last) element in the r permutation can be chosen in 
ways. Thus, by the fundamental principle of counting, we have
By Example 2.3(e), we see that
Thus, we have proven the following theorem.
Theorem 2.4: 
Consider the case that 
. We get
Accordingly,
Corollary 2.5: There are n! permutations of n objects (taken all at a time).
For example, there are 
permutations of the three letters a, b, c. These are
abc, acb, bac, bca, cab, cba
Frequently we want to know the number of permutations of a multiset, that is, a set of objects some of which are alike. We will let
P(n; n1, n2, …, nr)
denote the number of permutations of n objects of which n1 are alike, n2 are alike, …, nr are alike. The general formula follows:
Theorem 2.6: 
We indicate the proof of the above theorem by a particular example. Suppose we want to form all possible five-letter “words” using the letters from the word “BABBY”. Now there are 5! = 120 permutations of the objects B1, A, B2, B3, Y, where we have distinguished the three B’s. Observe that the following 6 permutations produce the same word when the subscripts are removed:
B1B2B3AY, B1B3B2AY, B2B1B3AY, B2B3B1AY, B3B1B2AY, B3B2B1AY
The 6 comes from the fact that there are 
different ways of placing the three B’s in the first three positions in the permutation. This is true for each set of three positions in which the three B’s can appear. Accordingly, there are
different five-letter words that can be formed using the letters from the word “BABBY”.
(a) Find the number m of seven-letter words that can be formed using the letters of the word “BENZENE”.
We seek the number of permutations of seven objects of which three are alike, the three E’s, and two are alike, the two N’s. By Theorem 2.6,
(b) Find the number m of different signals, each consisting of eight flags in a vertical line, that can be formed from four indistinguishable red flags, three indistinguishable white flags, and a blue flag.
We seek the number of permutations of eight objects of which four are alike, the red flags, and three are alike, the white flags. By Theorem 2.6,
Many problems in combinatorial analysis and, in particular, probability are concerned with choosing an element from a set S containing n elements (or a card from a deck or a person from a population). When we choose one element after another from the set S, say r times, we call the choice an ordered sample of size r. We consider two cases:
(i) Sampling with Replacement: Here the element is replaced in the set S before the next element is chosen. Since there are n different ways to choose each element (repetitions are allowed), the product rule principle tells us that there are
different ordered samples with replacement of size r.
(ii) Sampling without Replacement: Here the element is not replaced in the set S before the next element is chosen. Thus, there are no repetitions in the ordered sample. Accordingly, an ordered sample of size r without replacement is simply an r permutation of the elements in the set S with n elements. Thus, there are
different ordered samples without replacement of size r from a population (set) with n elements. In other words, by the product rule, the first element can be chosen in n ways, the second in n- 1 ways, and so on.
EXAMPLE 2.7 Three cards are chosen in succession from a deck with 52 cards. Find the number of ways this can be done: (a) with replacement, (b) without replacement.
(a) Since each card is replaced before the next card is chosen, each card can be chosen in 52 ways. Thus,
is the number of different ordered samples of size 
with replacement.
(b) Since there is no replacement, the first card can be chosen in 52 ways, the second card in 51 ways, and the last card in 50 ways. Thus,
is the number of different ordered samples of size r = 3 without replacement.
Suppose we have a collection of n objects. A combination of these n objects taken r at a time is any selection of r of the objects where order doesn’t count. In other words, an r combination of a set of n objects is any subset of r elements. For example, the combinations of the letters a, b, c, d taken three at a time are
{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d} or simply abc, abd, acd, bcd
Observe that the following combinations are equal:
abc, acb, bac, bca, cab, cba
That is, each denotes the same set {a, b, c}.
The number of combinations of n objects taken r at a time will be denoted by
C(n, r)
Before we derive the general formula for C(n, r), we consider a particular case.
EXAMPLE 2.8 Find the number of combinations of four objects, a, b, c, d, taken three at a time.
Each combination consisting of three objects determines 
permutations of the objects in the combination as pictured in Fig. 2-2. Thus, the number of combinations multiplied by 3! equals the number of permutations. That is,
But 
and 
. Thus, 
, which is noted in Fig. 2-2.
Formula for C(n, r)
Since any combination of n objects taken r at a time determines r! permutations of the objects in the combination, we can conclude that
Thus, we obtain the following formula for C(n, r):
Theorem 2.7: 
Recall that the binomial coefficient was defined to be 
Accordingly,
We shall use C(n, r) and interchangeably.
EXAMPLE 2.9
(a) Find the number m of committees of 3 that can be formed from 8 people.
Each committee is, essentially, a combination of the 8 people taken 3 at a time. Thus
(b) A farmer buys 3 cows, 2 pigs, and 4 hens from a person who has 6 cows, 5 pigs, and 8 hens. How many choices does the farmer have?
The farmer can choose the cows in 
ways, the pigs in 
ways, and the hens in 
ways. Accordingly, altogether the farmer can choose the animals in
EXAMPLE 2.10 Find the number m of ways that 9 toys can be divided between 4 children if the youngest is to receive 3 toys and each of the others 2 toys.
There are 
ways to first choose 3 toys for the youngest. Then there are 
ways to choose 2 of the remaining 6 toys for the oldest. Next, there are 
ways to choose 2 of the remaining 4 toys for the second oldest. The third oldest receives the remaining 2 toys. Thus, by the product rule,
Alternately, by Problem 2.37,
EXAMPLE 2.11 Find the number m of ways that 12 students can be partitioned into 3 teams, T1, T2, T3, so that each team contains 4 students.
Method 1: Let A be one of the students. Then there are C(11, 3) ways to choose 3 other students to be on the same team as A. Now let B denote a student who is not on the same team as A; then there are C(7, 3) ways to choose 3 students out of the remaining students to be on the same team as B. The remaining 4 students constitute the third team. Thus, altogether, the number m of ways to partition the students is as follows:
Method 2: Each partition [T1, T2, T3] of the students can be arranged in 
ways as an ordered partition. By Problem 2.37 (or using the method in Example 2.10), there are
such ordered partitions. Thus, there are 
(unordered) partitions.
A tree diagram is a device used to enumerate all the possible outcomes of a sequence of experiments or events where each event can occur in a finite number of ways. The construction of tree diagrams is illustrated in the following examples.
EXAMPLE 2.12 Find the product set A × B × C where
The tree diagram for the A × B × C appears in Fig. 2-3. Observe that the tree is constructed from left to right and that the number of branches at each point corresponds to the number of possible outcomes of the next event. Each endpoint of the tree is labeled by the corresponding element of A × B × C. As expected from Theorem 1.11, A × B × C contains 
elements.
EXAMPLE 2.13 Marc and Erik are to play a tennis tournament. The first person to win 2 games in a row or who wins a total of 3 games wins the tournament. Find the number of ways the tournament can occur.
The tree diagram showing the possible outcomes of the tournament appears in Fig. 2-4. Specifically, there are 10 endpoints which correspond to the following 10 ways that the tournament can occur:
MM, MEMM, MEMEM, MEMEE, MEE, EMM, EMEMM, EMEME, EMEE, EE
The path from the beginning of the tree to the endpoint describes who won which game in the individual tournament.
2.1. Compute: (a) 4!, 5!, 6!, 7!, 8!, 9!, 10!; (b) 50!
(a) Use 
! after calculating 4! and 5!:
(b) Since n is very large, we use Stirling’s approximation that 
(where 
). Let
Evaluating N using a calculator, we get 
(which has 65 digits).
Alternately, using (base 10) logarithms, we get
The antilog yields 
.
Alternately, this could be solved as follows:
2.3. Simplify: 
or simply 
or simply 
2.4. Compute: 
Recall that there are as many factors in the numerator as in the denominator.
2.5. Compute: 
or, since 
, we can use Lemma 2.1 to obtain:
(b) Since 
, Lemma 2.1 tells us that
Now 
Multiply the first fraction by 
and the second by 
to obtain the same denominator in both fractions; and then add:
2.7. Prove Theorem 2.3: 
(The technique in this proof is similar to that of the preceding problem.)
Now 
To obtain the same denominator in both fractions, multiply the first fraction by 
and the second fraction by 
Hence
2.8. Suppose a bookcase shelf has 5 history texts, 3 sociology texts, 6 anthropology texts, and 4 psychology texts. Find the number n of ways a student can choose: (a) one of the texts; (b) one of each type of text.
(a) Here the sum rule applies; hence 
(b) Here the product rule applies; hence 
2.9. A restaurant has a menu with 4 appetizers, 5 entrees, and 2 desserts. Find the number n of ways a customer can order an appetizer, entree, and dessert.
Here the product rule applies since the customer orders one of each. Thus 
2.10. A history class contains 8 male students and 6 female students. Find the number n of ways that the class can elect: (a) 1 class representative; (b) 2 class representatives, 1 male and 1 female; (c) 1 president and 1 vice-president.
(a) Here the sum rule is used; hence 
(b) Here the product rule is used; hence 
(c) There are 14 ways to elect the president, and then 13 ways to elect the vice-president. Thus, 
2.11. There are 5 bus lines from city A to city B and 4 bus lines from city B to city C. Find the number n of ways a person can travel by bus:
(a) from A to C by way of B, (b) round-trip from A to C by way of B,
(c) round-trip from A to C by way of B, without using a bus line more than once.
(a) There are 5 ways to go from A to B and 4 ways to go from B to C; hence, by the product rule, 
(b) There are 20 ways to go from A to C by way of B and 20 ways to return. Thus, by the product rule, 
(c) The person will travel from A to B to C to B to A. Enter these letters with connecting arrows as follows:
There are 5 ways to go from A to B and 4 ways to go from B to C. Since a bus line is not to be used more than once, there are only 3 ways to go from C back to B and only 4 ways to go from B back to A. Enter these numbers above the corresponding arrows as follows:
Thus, by the product rule, 
2.12. Suppose there are 12 married couples at a party. Find the number n of ways of choosing a man and a woman from the party such that the two are: (a) married to each other, (b) not married to each other.
(a) There are 12 married couples and hence there are 
ways to choose one of the couples.
(b) There are 12 ways to choose, say, one of the men. Once the man is chosen, there are 11 ways to choose the women, anyone other than his wife. Thus, 
2.13. Suppose a password consists of 4 characters, the first 2 being letters in the (English) alphabet and the last 2 being digits. Find the number n of:
(a) passwords, (b) passwords beginning with a vowel
(a) There are 26 ways to choose each of the first 2 characters and 10 ways to choose each of the last 2 characters. Thus, by the product rule,
(b) Here there are only 5 ways to choose the first character. Hence 
2.14. State the essential difference between permutations and combinations, with examples.
Order counts with permutations, such as words, sitting in a row, and electing a president, vice-president, and treasurer. Order does not count with combinations, such as committees and teams (without counting positions). The product rule is usually used with permutations since the choice for each of the ordered positions may be viewed as a sequence of events.
2.15. Find the number n of ways that 4 people can sit in a row of 4 seats.
The 4 empty seats may be pictured by
———, ———, ———, ———.
The first seat can be occupied by any one of the 4 people, that is, there are 4 ways to fill the first seat. After the first person sits down, there are only 3 people left and so there are 3 ways to fill the second seat. Similarly, the third seat can be filled in 2 ways, and the last seat in 1 way. This is pictured by
Thus, by the product rule, 
Alternately, n is the number of permutations of 4 things taken 4 at a time, and so
2.16. A family has 3 boys and 2 girls. (a) Find the number of ways they can sit in a row. (b) How many ways are there if the boys and girls are each to sit together?
(a) The 5 children can sit in a row in 
ways.
(b) There are 2 ways to distribute them according to sex: BBBGG or GGBBB. In each case, the boys can sit in 
ways and the girls can sit in 
ways. Thus, altogether, there are 
ways.
2.17. Find the number n of distinct permutations that can be formed from all the letters of each word: (a) THOSE, (b) UNUSUAL, (c) SOCIOLOGICAL.
This problem concerns permutations with repetitions.
, since there are 5 letters and no repetitions.
since there are 7 letters of which 3 are U and no other letter is repeated.
since there are 12 letters of which 3 are O, 2 are C, 2 are I, and 2 are L.
2.18. Find the number n of different signals, each consisting of 6 flags hung in a vertical line, that can be formed from 4 identical red flags and 2 identical blue flags.
This problem concerns permutations with repetitions. Thus, 
since there are 6 flags of which 4 are red and 2 are blue.
2.19. Find the number n of ways that 7 people can arrange themselves: (a) in a row of 7 chairs, (b) around a circular table.
(a) The 7 people can arrange themselves in a row in 
! ways.
(b) One person can sit at any place at the circular table. The other 6 people can then arrange themselves in 
! ways around the table.
This is an example of a circular permutation. In general, n objects can be arranged in a circle in 
! ways.
2.20. Suppose repetitions are not allowed. (a) Find the number n of three-digit numbers that can be formed from the six digits: 2, 3, 5, 6, 7, 9. (b) How many of them are even? (c) How many of them exceed 400?
There are 6 digits, and the three-digit number may be pictured by
———, ———, ———.
In each case, write down the number of ways that one can fill each of the positions.
(a) There are 6 ways to fill the first position, 5 ways for the second position, and 3 ways for the third position. This may be pictured by: 
, 
, 
. Thus, 
Alternately, n is the number of permutations of 6 things taken 3 at a time, and so
(b) Since the numbers must be even, the last digit must be either 2 or 4. Thus, the third position is filled first and it can be done in 2 ways. Then there are now 5 ways to fill the middle position and 4 ways to fill the first position. This may be pictured by: , , 
. Thus, 
of the numbers are even.
(c) Since the numbers must exceed 400, they must begin with 5, 6, 7, or 9. Thus, we first fill the first position and it can be done in 4 ways. Then there are 5 ways to fill the second position and 4 ways to fill the third position. This may be pictured by: , , . Thus, 
of the numbers exceed 400.
2.21. A class contains 8 students. Find the number of ordered samples of size 3: (a) with replacement, (b) without replacement.
(a) Each student in the ordered sample can be chosen in 8 ways; hence there are 
samples of size 3 with replacement.
(b) The first student in the sample can be chosen in 8 ways, the second in 7 ways, and the last in 6 ways. Thus, there are 
samples of size 3 without replacement.
2.22. Find n if: 
, 
; hence
Since n must be positive, the only answer is 
.
and 
. Hence:
Since n must be positive, the only answer is 
.
2.23. There are 12 students who are eligible to attend the National Student Association annual meeting. Find the number n of ways a delegation of 4 students can be selected from the 12 eligible students.
This concerns combinations, not permutations, since order does not count in a delegation. There are “12 choose 4” such delegations. That is,
2.24. A student is to answer 8 out of 10 questions on an exam.
(a) Find the number n of ways the student can choose the eight questions.
(b) Find n if the student must answer the first three questions.
(a) The 8 questions can be selected “10 choose 8” ways. That is,
(b) If the first 3 questions are answered, then the student must choose the other 5 questions from the remaining 7 questions. Hence
2.25. A class contains 10 students with 6 men and 4 women. Find the number n of ways:
(a) A 4-member committee can be selected from the students.
(b) A 4-member committee with 2 men and 2 women.
(c) The class can elect a president, vice-president, treasurer, and secretary.
(a) This concerns combinations, not permutations, since order does not count in a committee. There are “10 choose 4” such committees. That is,
(b) The 2 men can be chosen from the 6 men in 
ways and the 2 women can be chosen from the 4 women in 
ways. Thus, by the product rule,
(c) This concerns permutations, not combinations, since order does count. Thus,
2.26. A box contains 7 blue socks and 5 red socks. Find the number n of ways two socks can be drawn from the box if: (a) They can be any color; (b) They must be the same color.
(a) There are “12 choose 2” ways to select 2 of the 12 socks. That is,
(b) There are 
ways to choose 2 of the 7 blue socks and 
ways to choose 2 of the 5 red socks. By the sum rule, 
.
2.27. Let A, B, …, L be 12 given points in the plane R2 such that no 3 of the points lie on the same line. Find the number n of:
(a) Lines in R2 where each line contains two of the points.
(b) Lines in R2 containing A and one of the other points.
(c) Triangles whose vertices come from the given points.
(d) Triangles whose vertices are A and two of the other points.
Since order does not count, this problem involves combinations.
(a) Each pair of points determines a line; hence
(b) We need only choose one of the 11 remaining points; hence 
.
(c) Each triple of points determines a triangle; hence
(d) We need only choose two of the 11 remaining points; hence 
. (Alternately, there are 
triangles without A as a vertex; hence 
of the triangles do have A as a vertex.)
2.28. There are 12 students in a class. Find the number n of ways that 12 students can take 3 different tests if 4 students are to take each test.
There are 
ways to choose 4 students to take the first test; following this, there are 
ways to choose 4 students to take the second test. The remaining students take the third test. Thus
2.29. Find the number n of ways 12 students can be partitioned into 3 teams A1, A2, A3, so that each team contains 4 students. (Compare with the preceding Problem 2.28.)
Let A denote one of the students. There are 
ways to choose 3 other students to be on the same team as A. Now let B be a student who is not on the same team as A. Then there are 
ways to choose 3 from the remaining students to be on the same team as B. The remaining 4 students form the third team. Thus, 
.
Alternately, each partition [A1, A2, A3] can be arranged in 
ways as an ordered partition. By the preceding Problem 2.28, there are 34,650 such ordered partitions. Thus, 
.
2.30. Find the number n of committees of 5 with a given chairperson that can be selected from 12 persons.
Method 1: The chairperson can be chosen in 12 ways and, following this, the other 4 on the committee can be chosen from the remaining 11 people in 
ways. Thus,
Method 2: The 5-member committee can be chosen from the 12 persons in 
ways. Each committee can then select a chairman in 5 ways. Thus,
2.31. There are n married couples at a party. (a) Find the number N of (unordered) pairs at the party. (b) Suppose every person shakes hands with every other person other than his or her spouse. Find the number M of handshakes.
(a) There are 2n people at the party, and so there are “2 n choose 2” pairs. That is,
(b) M is equal to the number of pairs who are not married. There are n married pairs. Thus, using (a),
2.32. Construct the tree diagram that gives the permutations of {a, b, c}.
The tree diagram, drawn downward with the “root” on the top, appears in Fig. 2-5. Each path from the root to an endpoint (“leaf”) of the tree represents a permutation. There are 6 such paths which yield the following 6 permutations:
abc, acb, bac, bca, cab, cba
2.33. Audrey has time to play roulette at most 5 times. At each play she wins or loses $1. She begins with $1 and will stop playing before 5 plays if she loses all her money.
(a) Find the number of ways the betting can occur.
(b) How many cases will she stop before playing 5 times?
(c) How many cases will she leave without any money?
Construct the appropriate tree diagram as shown in Fig. 2-6. Each number in the diagram denotes the number of dollars she has at that moment in time. Thus, the root, which is circled, is labeled with the number 1.
(a) There are 14 paths from the root of the tree to an endpoint (“leaf”), so the betting can occur in 14 different ways.
(b) There are only 2 paths with less than 5 edges, so Audrey will not play 5 times in only 2 of the cases.
(c) There are 4 paths which end in 0 or, in other words, only 4 of the leaves are labeled with 0. Thus, Audrey will leave without any money in 4 of the cases.
2.34. Prove Theorem 2.2 (binomial theorem): 
The theorem is true for n = 1, since
We assume the theorem holds for 
and prove it is true for 
Now the term in the product which contains br is obtained from
But, by Theorem 2.3 
Thus, the term containing br is
Note that 
is a polynomial of degree n + 1 in b. Consequently,
2.35. Prove 
Note that 
. Expanding (1 + 1)4, using the binomial theorem, yields:
2.36. Let n and n1, n2, …, nr be nonnegative integers such that 
. The multi-nomial coefficients are denoted and defined by
Compute the following multinomial coefficients:
, 
, 
Use the above formula to obtain:
,
,
(Here we use the act that 0! = 1.)
(c) The expression 
has no meaning, since 
.
2.37. Suppose S contains n elements, and let n1, n2, …, nr be positive integers such that
Prove there exists
different ordered partitions of S of the form [A1, A2, …, Ar where A1 contains n1 elements, A2 contains n2 elements, …, Ar contains nr elements.
We begin with n elements in S; hence there are 
ways of selecting the cell A1. Following this, there are n-n1 elements left in S, that is, in S\A1; hence there are 
ways of selecting the cell A2. Similarly, for 
, 4, …, r, there are 
ways of selecting the cell Ai.
Accordingly, there are
different ordered partitions of S. Now (*) is equal to
But this is equal to
since each numerator after the first is cancelled by the second term in the preceding denominator and since 
. Thus, the theorem is proved.
2.38. Find: (a) 10!, 11!, 12! (b) 60! (Hint: Use Stirling’s approximation to n!.)
2.39. Compute: 
2.40. Simplify: 
2.41. Compute: 
2.42. Show that: 
,
2.43. Evaluate the following multinomial coefficients (defined in Problem 2.36):
2.44. Find the (a) ninth and (b) tenth rows of Pascal’s triangle, assuming the following is the eighth row:
1 8 28 70 56 28 8 1
2.45. A store sells clothes for men. It has 3 different kinds of jackets, 7 different kinds of shirts, and 5 different kinds of pants. Find the number of ways a person can buy:
(a) one of the items for a present, (b) one of each of the items for a present.
2.46. A restaurant has, on its dessert menu, 4 kinds of cakes, 2 kinds of cookies, and 3 kinds of ice cream. Find the number of ways a person can select: (a) one of the desserts, (b) one of each kind of dessert.
2.47. A class contains 8 male students and 6 female students. Find the number of ways that the class can elect: (a) a class representative; (b) 2 class representatives, 1 male and 1 female; (c) a president and a vice-president.
2.48. Suppose a password consists of 4 characters where the first character must be a letter of the (English) alphabet, but each of the other characters may be a letter or a digit. Find the number of:
(a) passwords, (b) passwords beginning with one of the 5 vowels.
2.49. Suppose a code consists of 2 letters followed by 3 digits. Find the number of:
(a) codes, (b) codes with distinct letters, (c) codes with the same letters.
2.50. There are 6 roads between A and B and 4 roads between B and C. Find the number n of ways a person can drive: (a) from A to C by way of B, (b) round-trip from A to C by way of B, (c) round-trip from A to C by way of B without using the same road more than once.
2.51. Find the number n of ways a judge can award first, second, and third places in a contest with 18 contestants.
2.52. Find the number n of ways 6 people can ride a toboggan where: (a) anyone can drive, (b) one of 3 must drive.
2.53. A debating team consists of 3 boys and 3 girls. Find the number n of ways they can sit in a row where: (a) there are no restrictions, (b) the boys and girls are each to sit together, (c) just the girls are to sit together.
2.54. Find the number n of permutations that can be formed from all the letters of each word: (a) QUEUE, (b) COMMITTEE, (c) PROPOSITION, (d) BASEBALL.
2.55. Find the number n of different signals, each consisting of 8 flags hung in a vertical line, that can be formed from 4 identical red flags, 2 identical blue flags, and 2 identical green flags.
2.56. Find the number n of ways 5 large books, 4 medium-size books, and 3 small books can be placed on a shelf so that all books of the same size are together.
2.57. A box contains 12 light bulbs. Find the number n of ordered samples of size 3: (a) with replacement, (b) without replacement.
2.58. A class contains 10 students. Find the number n of ordered samples of size 4: (a) with replacement, (b) without replacement.
2.59. A restaurant has 6 different desserts. Find the number of ways a customer can choose 2 of the desserts.
2.60. A store has 8 different mystery books. Find the number of ways a customer can buy 3 of the books.
2.61. A box contains 6 blue socks and 4 white socks. Find the number of ways two socks can be drawn from the box where: (a) there are no restrictions, (b) they are different colors, (c) they are to be the same color.
2.62. A class contains 9 boys and 3 girls. Find the number of ways a teacher can select a committee of 4.
2.63. Repeat Problem 2.62, but where: (a) there are to be 2 boys and 2 girls, (b) there is to be exactly 1 girl, (c) there is to be at least 1 girl.
2.64. A woman has 11 close friends. Find the number of ways she can invite 5 of them to dinner.
2.65. Repeat Problem 2.64, but where 2 of the friends are married and will not attend separately.
2.66. Repeat Problem 2.64, but where 2 of the friends are not on speaking terms and will not attend together.
2.67. A person is dealt a poker hand (5 cards) from an ordinary deck with 52 cards. Find the number of ways the person can be dealt: (a) four of a kind, (b) a flush.
2.68. A student must answer 10 out of 13 questions. (a) How many choices are there? (b) How many if the student must answer the first 2 questions? (c) How many if the student must answer the first or second question but not both?
2.69. Find the number of ways 6 toys may be divided evenly among 3 children.
2.70. Find the number of ways 6 students can be partitioned into 3 teams containing 2 students each. (Compare with Problem 2.69.)
2.71. Find the number of ways 6 students can be partitioned into 2 teams where each team contains 2 or more students.
2.72. Find the number of ways 9 toys may be divided among 4 children if the youngest is to receive 3 toys and each of the others 2 toys.
2.73. There are 9 students in a class. Find the number of ways the students can take 3 tests if 3 students are to take each test.
2.74. There are 9 students in a class. Find the number of ways the students can be partitioned into 3 teams containing 3 students each. (Compare with Problem 2.73.)
2.75. Teams A and B play in the world series of baseball where the team that first wins 4 games wins the series. Suppose A wins the first game and that the team that wins the second game also wins the fourth game. (a) Find the number n of ways the series can occur, and list the n ways the series can occur. (b) How many ways will B win the series? (c) How many ways will the series last 7 games?
2.76. Suppose A, B, …, F in Fig. 2-7 denote islands, and the lines connecting them bridges. A person begins at A and walks from island to island. The person stops for lunch when he or she cannot continue to walk without crossing the same bridge twice. (a) Construct the appropriate tree diagram, and find the number of ways the person can walk before eating lunch. (b) At which islands can he or she eat lunch?
2.38. (a) 3,628,800; 39,916,800; 479,001,600. 
, so 
.
2.39. (a) 240; (b) 2184; (c) 1/90; (d) 1/1716.
2.40. (a) n + 1; 
; 
; 
.
2.41. (a) 10; (b) 35; (c) 91; (d) 15; (e) 1140; (f) 816.
2.42. Hint: Expand (a) (1 + 1)n; (b) (1 - 1)n.
2.43. (a) 60; (b) 210; (c) 504; (d) Not defined.
2.44. (a) 1, 9, 36, 84, 126, 126, 84, 36, 9, 1; (b) 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1.
2.45. (a) 15; (b) 105.
2.46. (a) 9; (b) 24.
2.47. (a) 14; (b) 48; (c) 182.
2.48. 
; 
.
2.49. 
; 
; 
.
2.50. (a) 24; 
; (c) 360.
2.52. 
; 
2.53. 
; 
; 
2.54. (a) 30; 
; 
; 
2.56. 
.
2.57. 
; (b) 1320.
2.58. 
; 
2.60. 
.
2.61. 
; 
; 
; 
.
2.62. 
.
2.63. 
; 
;
or 
.
2.64. 
.
2.65. 210.
2.66. 252.
2.67. 
; 
.
2.68. 
; 
.
2.69. 90.
2.70. 15.
2.71. (Hint: The number of subsets excluding Ø and the 6 singleton subsets.) 
.
2.72. 
.
2.73. 
.
2.74. 
.
2.75. Construct the appropriate tree diagram as in Fig. 2-8. Note that the tree begins at A, the winner of the first game, and that there is only one choice in the fourth game, the winner of the second game. (a) The diagram shows that 
and that the series can occur in the following 15 ways:
AAAA, AABAA, AABABA, AABABBA, AABABBB, ABABAA, ABABABA, ABABABB, ABABBAA, ABABBAB, ABABBB, ABBBAAA, ABBBAAB, ABBBAB, ABBBB
(b) 6; (c) 8.
2.76. (a) See Fig. 2-9. There are 11 ways to take his walk. (b) B, D, or E.
, 
