<< . .

. 6
( : 20)



. . >>

(b) How many of the ways would give the same number of stu-
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.

<< . .

. 6
( : 20)



. . >>