dents in each class?

[Ans. 756,756.]

6. A college professor anticipates teaching the same course for the

next 35 years. So as not to become bored with his or her jokes, he

or she decides to tell exactly three jokes every year and in no two

years to tell exactly the same three jokes. What is the minimum

number of jokes that will accomplish this? What is the minimum

number if he or she determines never to tell the same joke twice?

55

3.4. COUNTING PARTITIONS

7. How many ways can you answer a ten-question true-false exam,

marking the same number of answers true as you do false? How

many if it is desired to have no two consecutive answers the same?

8. From three Republicans and three Democrats, ¬nd the number

of committees of three which can be formed

(a) With no restrictions.

[Ans. 20.]

(b) With three Republicans and no Democrats.

[Ans. 1.]

(c) With two Republicans and one Democrat.

[Ans. 9.]

(d) With one Republican and two Democrats.

[Ans. 9.]

(e) With no Republicans and three Democrats.

[Ans. 1.]

What is the relation between your answers to the ¬ve parts of

this question?

9. Exercise 8 suggests that the following should be true.

2n n n n n n n n n

= + + +. . .+ .

n’1 n’2

n 0 n 1 2 n 0

Show that it is true.

10. A student needs to choose two electives from six possible courses.

(a) How many ways can he or she make his or her choice?

[Ans. 15.]

(b) How many ways can he or she choose if two of the courses

meet at the same time?

[Ans. 14.]

56 CHAPTER 3. PARTITIONS AND COUNTING

(c) How many ways can he or she choose if two of the courses

meet at 10 o™clock, two at 11 o™clock, and there are no other

con¬‚icts among the courses?

[Ans. 13.]

Supplementary exercises.

11. Consider a town in which there are three plumbers, A, B, and

C. On a certain day six residents of the town telephone for a

plumber. If each resident selects a plumber from the telephone

directory, in how many ways can it happen that

(a) Three residents call A, two residents call B, and one resident

calls C?

[Ans. 60.]

(b) The distribution of calls to the plumbers is three, two, and

one?

[Ans. 360.]

12. Two committees (a labor relations committee and a quality con-

trol committee) are to be selected from a board of nine men. The

only rules are (1) the two committees must have no members in

common, and (2) each committee must have at least four men.

In how many ways can the two committees be appointed?

13. A group of ten people is to be divided into three committees of

three, three, and six members, respectively. The chair of the

group is to serve on all three committees and is the only member

of the group who serves on more than one committee. In how

many ways can the committee assignments be made?

[Ans. 756.]

14. In a class of 20 students, grades of A, B, C, D, and F are to be

assigned. Omit arithmetic details in answering the following.

(a) In how many ways can this be done if there are no restric-

tions?

[Ans. 520.]

N

57

3.5. SOME PROPERTIES OF THE NUMBERS .

J

(b) In how many ways can this be done if the grades are assigned

as follows: 2 A™s, 3 B™s, 10 C™s, 3 D™s, and 2 F™s?

(c) In how many ways can this be done if the following rules are

to be satis¬ed: exactly 10 C™s; the same number of A™s as

F™s; the same number of B™s as D™s; always more B™s than

A™s?

20 20 20

[Ans. + + .]

5,10,5 1,4,10,4,1 2,3,10,3,2

15. Establish the identity

n’k

n r n

=

r’k

r k k

for n ≥ r ≥ k in two ways, as follows:

(a) Replace each expression by a ratio of factorials and show

that the two sides are equal.

(b) Consider the following problem: From a set of n people a

committee of r is to be chosen, and from these r people a

steering subcommittee of k people is to be selected. Show

that the two sides of the identity give two di¬erent ways of

counting the possibilities for this problem.

n

3.5 Some properties of the numbers .

j

The numbers n introduced in the previous section will play an impor-

j

tant role in our future work. We give here some of the more important

properties of these numbers.

A convenient way to obtain these numbers is given by the famous

Pascal triangle, shown in Figure 3.5. To obtain the triangle we ¬rst

write the 1™s down the sides. Any of the other numbers in the triangle

has the property that it is the sum of the two adjacent numbers in the

row just above. Thus the next row in the triangle is 1, 6, 15, 20, 15,

6, 1. To ¬nd the number n we look in the row corresponding to the

j

number n and see where the diagonal line corresponding to the value of

j intersects this row. For example, 4 = 6 is in the row marked n = 4

2

and on the diagonal marked j = 2.

The property of the numbers n upon which the triangle is based

j

is

n+1 n n

= + .

j’1

j j

58 CHAPTER 3. PARTITIONS AND COUNTING

Figure 3.5: ™¦

This fact can be veri¬ed directly (see Exercise 6), but the following

argument is interesting in itself. The number n+1 is the number of

j

subsets with j elements that can be formed from a set of n+1 elements.

Select one of the n+1 elements, x. The n+1 subsets can be partitioned

j

into those that contain x and those that do not. The latter are subsets

of j elements formed from n objects, and hence there are n such j

subsets. The former are constructed by adding x to a subset of j ’ 1

n

elements formed from n elements, and hence there are j’1 of them.

Thus

n+1 n n

= + .

j’1

j j

If we look again at the Pascal triangle, we observe that the numbers

in a given row increase for a while, and then decrease. We can prove

this fact in general by considering the ratio of two successive terms,

n

j!(n ’ j)! n’j

n!

j+1

·

= = .

(j + 1)!(n ’ j ’ 1)!

n n! j+1

j

The numbers increase as long as the ratio is greater than 1, i.e., n ’ j >

j + 1. This means that j < 1 (n ’ 1). We must distinguish the case

2

of an even n from an odd n. For example, if n = 10, j must be less

N

59

3.5. SOME PROPERTIES OF THE NUMBERS .

J

than 1 (10 ’ 1) = 4.5. Hence for j up to 4 the terms are increasing,

2

from j = 5 on, the terms decrease. For n = 11, j must be less than

1

(11 ’ 1) = 5. For j = 5, (11 ’ j)/(j + 1) = 1. Hence, up to j = 5 the

2

terms increase, then 11 = 11 , and then the terms decrease.

5 6

Exercises

1. Extend the Pascal triangle to n = 16. Save the result for later

use.

2. Prove that

n n n n

= 2n ,

+ + +...+

0 1 2 n

using the fact that a set with n elements has 2n subsets.

3. For a set of ten elements prove that there are more subsets with

¬ve elements than there are subsets with any other ¬xed number

of elements.

n n’r n 30

·

4. Using the fact that = , compute for s = 1, 2, 3, 4

r+1 r+1 r s

30

from the fact that = 1.

0

[Ans. 30; 435; 4060; 27,405.]

5. There are 52 di¬erent possible bridge hands. Assume that a list

13

is made showing all these hands, and that in this list the ¬rst

card in every hand is crossed out. This leaves us with a list of

twelve-card hands. Prove that at least two hands in the latter list

contain exactly the same cards.

6. Prove that

n+1 n n

= +

j’1

j j

using only the fact that

n n!

= .

j!(n ’ j)!

j

60 CHAPTER 3. PARTITIONS AND COUNTING

7. Construct a triangle in the same way that the Pascal triangle

was constructed, except that whenever you add two numbers, use

parity addition (table (a) in Figure 2.12). Construct the triangle

for 16 rows. What does this triangle tell you about the numbers

in the Pascal triangle? Use this result to check your triangle in

Exercise 1.

8. In the triangle obtained in Exercise 7, what property do the rows

1, 2, 4, 8, and 16 have in common? What does this say about the

numbers in the corresponding rows of the Pascal triangle? What

would you predict for the terms in the 32nd row of the Pascal

triangle?

9. For the following table state how one row is obtained from the

preceding row and give the relation of this table to the Pascal

triangle.

11 1 1 1 1 1

12 3 4 5 6 7

1 3 6 10 15 21 28

1 4 10 20 35 56 84

1 5 15 35 70 126 210

1 6 21 56 126 252 462

1 7 28 84 210 462 924

10. Referring to the table in Exercise 9, number the columns starting

with 0, 1, 2, . . . and number the rows starting with 1, 2, 3, . . .. Let

f (n, r) be the element in the nth column and the rth row. The

table was constructed by the rule

f (n, r) = f (n ’ 1, r) + f (n, r ’ 1)

for n > 0 and r > 1, and f (n, 1) = f (0, r) = 1 for all n and r.

Verify that

n+r’1

f (n, r) =

n

satis¬es these conditions and is in fact the only choice for f (n, r)

which will satisfy the conditions.

11. Consider a set {a1 , a2 , a3 } of three objects which cannot be distin-

guished from one another. Then the ordered partitions with two

cells which could be distinguished are: [{a1 , a2 , a3 }, …], [{a1 , a2 }, {a3 }],

[{a1 }, {a2 , a3 }], […, {a1 , a2 , a3 }]. List all such ordered partitions

with three cells. How many are there?

N

61

3.5. SOME PROPERTIES OF THE NUMBERS .

J

[Ans. 10.]

12. Let f (n, r) be the number of distinguishable ordered partitions

with r cells which can be formed from a set of n indistinguishable

objects. Show that f (n, r) satis¬es the conditions

f (n, r) = f (n ’ 1, r) + f (n, r ’ 1)

for n > 0 and r > 1, and f (n, 1) = f (0, r) = 1 for all n and r.

[Hint: Show that f (n, r ’ 1) is the number of partitions which

have the last cell empty and f (n ’ 1, r) is the number which have

at least one element in the last cell.]

13. Using the results of Exercises 10 and 12, show that the number

of distinguishable ordered partitions with r cells which can be

formed from a set of n indistinguishable objects is

n+r’1

.

n

14. Assume that a mail carrier has seven letters to put in three mail

boxes. How many ways can this be done if the letters are not

distinguished?

[Ans. 36.]

15. For n ≥ r ≥ k ≥ s show that the identity

n’s n’k

n r k n

= .

k’s r’k

r k s s

holds by replacing each binomial coe¬cient by a ratio of factorials.

16. Establish the identity in Exercise 15 in another way by showing

that the two sides of the expression are simply two di¬erent ways

of counting the number of solutions to the following problem:

From a set of n people a subset of r is to be chosen; from the set

of r people a subset of k is to be chosen; and from the set of k

people a subset of s people is to be chosen.

17. Generalize the identity in Exercises 15 and 16 to solve the problem

of ¬nding the number of ways of selecting a t-element subset from

an s-element subset from a k-element subset from an r-element

subset of an n-element set, where n ≥ r ≥ k ≥ s ≥ t.

62 CHAPTER 3. PARTITIONS AND COUNTING

3.6 Binomial and multinomial theorems

It is sometimes necessary to expand products of the form (x + y)3 ,

(x + 2y + 11z)5 , etc. In this section we shall consider systematic ways

of carrying out such expansions.

Consider ¬rst the special case (x + y)3 . We write this as

(x + y)3 = (x + y)(x + y)(x + y).

To perform the multiplication, we choose either an x or a y from each

of the three factors and multiply our choices together; we do this for

all possible choices and add the results. We represent a particular set

of choices by a two-cell partition of the numbers 1, 2, 3. In the ¬rst

cell we put the numbers which correspond to factors from which we

chose an x. In the second cell we put the numbers which correspond to

factors from which we chose a y. For example, the partition [{1, 3}, {2}]

corresponds to a choice of x from the ¬rst and third factors and y from

the second. The product so obtained is xyx = x2 y. The coe¬cient of

x2 y in the expansion of (x + y)3 will be the number of partitions which

lead to a choice of two x™s and one y, that is, the number of two-cell

partitions of three elements with two elements in the ¬rst cell and one

in the second, which is 3 = 3. More generally, the coe¬cient of the

2

3

term of the form xj y 3’j will be for j = 0, 1, 2, 3. Thus we can write

j

the desired expansion as

33 32 3 33

(x + y)3 = xy 2 +

x+ x y+ y

3 2 1 0

= x3 + 3x2 y + 3xy 2 + y 3 .

The same argument carried out for the expansion (x + y)n leads to

the binomial theorem of algebra.

Binomial theorem. The expansion of (x + y)n is given by

nn n n n nn

xn’1 y + xn’2 y 2 + . . . + xy n’1 +

x+ y.

n’1 n’2

n 1 0

Example 3.16 Let us ¬nd the expansion for (a ’ 2b)3 . To ¬t this into

the binomial theorem, we think of x as being a and y as being ’2b.

Then we have

(a ’ 2b)3 = a3 + 3a2 (’2b) + 3a(’2b)2 + (’2b)3

= a3 ’ 6a2 b + 12ab2 ’ 8b3 .

63

3.6. BINOMIAL AND MULTINOMIAL THEOREMS

™¦

We turn now to the problem of expanding the trinomial (x + y + z)3 .

Again we write

(x + y + z)3 = (x + y + z)(x + y + z)(x + y + z).

This time we choose either an x or y or z from each of the three factors.

Our choice is now represented by a three-cell partition of the set of num-

bers {1, 2, 3}. The ¬rst cell has the numbers corresponding to factors

from which we choose an x, the second cell the numbers corresponding

to factors from which we choose a y, and the third those from which

we choose a z. For example, the partition [{1, 3}, …, {2}] corresponds to

a choice of x from the ¬rst and third factors, no y™s, and a z from the

second factor. The term obtained is xzx = x2 z. The coe¬cient of the

term x2 z in the expansion is thus the number of three-cell partitions

with two elements in the ¬rst cell, none in the second, and one in the

3

third. There are 2,0,1 = 3 such partitions. In general, the coe¬cient

of the term of the form xa y b z c in the expansion of (x + y + z)3 will be

3 3!

= .

a, b, c a!b!c!

Finding this way the coe¬cient for each possible a, b, and c, we obtain

(x+y+z)3 = x3 +y 3 +x3 +3x2 y+3xy 2 +3yz 2 +3y 2 z+3xz 2 +3x2 z+6xyz.