<<

. 2
( 6)



>>

take history.
42 CHAPTER 3. PARTITIONS AND COUNTING

[Ans. 12.]
(b) The number that take exactly two of the three courses.
(c) The number that take one or none of the courses.
2. In a chemistry class there are 20 students, and in a psychology
class there are 30 students. Find the number in either the psy-
chology class or the chemistry class if
(a) The two classes meet at the same hour.
[Ans. 50.]
(b) The two classes meet at di¬erent hours and 10 students are
enrolled in both courses.
[Ans. 40.]
3. If the truth set of a statement p has 10 elements, and the truth
set of a statement q has 20 elements, ¬nd the number of elements
in the truth set of p ∨ q if
(a) p and q are inconsistent.
(b) p and q are consistent and there are two elements in the
truth set of p § q.
4. If p is a statement that is true in ten cases, and q is a statement
that is true in ¬ve cases, ¬nd the number of cases in which both
p and q are true if p ∨ q is true in ten cases. What relation holds
between p and q?
5. Assume that the incidence of lung cancer is 16 per 100,000, and
that it is estimated that 75 per cent of those with lung cancer
smoke and 60 per cent of those without lung cancer smoke. (These
numbers are ¬ctitious.) Estimate the fraction of smokers with
lung cancer, and the fraction of nonsmokers with lung cancer.

[Ans. 20 and 10 per 100,000.]

6. Let A, B, and C be any three sets of a universal set U . Draw a
Venn diagram and show that
n(A ∪ B ∪ C) = n(A) + n(B) + n(C)
’n(A © B) ’ n(A © C) ’ n(B © C)
+n(A © B © C).
43
3.2. THE NUMBER OF ELEMENTS IN A SET

7. Analyze the data given below and draw a Venn diagram like that
in Figure 3.2. Assuming that every student in the school takes
one of the courses, ¬nd the total number of students in the school.

(a) First case:
28 students take English.
23 students take French.
23 students take German.
12 students take English and French.
11 students take English and German.
8 students take French and German.
5 students take all three courses.
(b) Second case:
36 students take English.
23 students take French.
13 students take German.
6 students take English and French.
11 students take English and German.
4 students take French and German.
1 students take all three courses.
(Comment on this result.)

8. Suppose that in a survey concerning the reading habits of students
it is found that:
60 per cent read magazine A; 50 per cent read magazine B; 50
per cent read magazine C; 30 per cent read magazines A and B;
20 per cent read magazines B and C; 30 per cent read magazines
A and C; 10 per cent read all three magazines.

(a) What per cent read exactly two magazines?
[Ans. 50.]
(b) What per cent do not read any of the magazines?
[Ans. 10.]

9. If p and q are equivalent statements and n(P ) = 10, what is
n(P ∪ Q)?
˜ ˜
10. If p implies q, prove that n(P ∪ Q) = n(P ) + n(Q).
44 CHAPTER 3. PARTITIONS AND COUNTING

11. On a transcontinental airliner, there are 9 boys, 5 American chil-
dren, 9 men, 7 foreign boys, 14 Americans, 6 American males, and
7 foreign females. What is the number of people on the plane?

[Ans. 33.]

Supplementary exercises.

˜
12. Prove that n(A) = n(U ) ’ n(A).

˜˜ ˜
13. Show that n(A © B) = n(A ∪ B) = n(U ) ’ n(A ∪ B).

14. In a collection of baseball players there are ten who can play
only out¬eld positions, ¬ve who can play only in¬eld positions
but cannot pitch, three who can pitch, four who can play any
position but pitcher, and two who can play any position at all.
How many players are there in all?

[Ans. 22.]

15. Ivyten College awarded 38 varsity letters in football, 15 in bas-
ketball, and 20 in baseball. If these letters went to a total of 58
men and only three of these men lettered in all three sports, how
many men received letters in exactly two of the three sports?

[Ans. 9.]

16. Let U be a ¬nite set. For any two sets A and B de¬ne the “dis-
˜ ˜
tance” from A to B to be d(A, B) = n(A © B) + n(A © B).

(a) Show that d(A, B) ≥ 0. When is d(A, B) = 0?
(b) If A, B, and C are nonintersecting sets, show that

d(A, C) ¤ d(A, B) + d(B, C).

(c) Show that for any three sets A, B, and C

d(A, C) ¤ d(A, B) + d(B, C).
45
3.3. PERMUTATIONS




Figure 3.4: ™¦

3.3 Permutations
We wish to consider here the number of ways in which a group of n
di¬erent objects can be arranged. A listing of n di¬erent objects in
a certain order is called a permutation of the n objects. We consider
¬rst the case of three objects, a, b, and c. We can exhibit all possible
permutations of these three objects as paths of a tree, as shown in
Figure 3.4. Each path exhibits a possible permutation, and there are
six such paths. We could also list these permutations as follows: abc,
bca, acb, cab, bac, cba. If we were to construct a similar tree for n
objects, we would ¬nd that the number of paths could be found by
multiplying together the numbers n, n ’ 1, n ’ 2, continuing down to
the number 1. The number obtained in this way occurs so often that
we give it a symbol, namely n!, which is read “n factorial”. Thus, for
example, 3! = 3 · 2 · 1 = 6, 4! = 4 · 3 · 2 · 1 = 24, etc. For reasons
which will be clear later, we de¬ne 0! = 1. Thus we can say there are
n! di¬erent permutations of n distinct objects.

Example 3.7 In the game of Scrabble, suppose there are seven let-
tered blocks from which we try to form a seven-letter word. If the
seven letters are all di¬erent, we must consider 7! = 5040 di¬erent
™¦
orders.

Example 3.8 A quarterback has a sequence of ten plays. Suppose his
or her coach instructs him or her to run through the ten-play sequence
without repetition. How much freedom is left to the quarterback? He
or she may choose any one of 10! = 3, 628, 800 orders in which to call
™¦
the plays.
46 CHAPTER 3. PARTITIONS AND COUNTING

Example 3.9 How many ways can n people be seated around a cir-
cular table? When this question is asked, it is usually understood that
two arrangements are di¬erent only if at least one person has a di¬erent
person on the right in the two arrangements. Consider then one person
in a ¬xed position. There are (n ’ 1)! ways in which the other people
may be seated. We have now counted all the arrangements we wish to
™¦
consider di¬erent.
A general principle. There are many counting problems for
which it is not possible to give a simple formula for the number of
possible cases. In many of these the only way to ¬nd the number
of cases is to draw a tree and count them (see Exercise 4). In some
problems, the following general principle is useful.
If one thing can be done in exactly r di¬erent ways, for each of
these a second thing can be done in exactly s di¬erent ways, for each
of the ¬rst two, a third can be done in exactly t ways, etc., then the
sequence of things can be done in the product of the numbers of ways
in which the individual things can be done, i.e., r · s · t ways.
The validity of the above general principle can be established by
thinking of a tree representing all the ways in which the sequence of
things can be done. There would be r branches from the starting posi-
tion. From the ends of each of these r branches there would be s new
branches, and from each of these t new branches, etc. The number of
paths through the tree would be given by the product r · s · t.

Example 3.10 The number of permutations of n distinct objects is
a special case of this principle. If we were to list all the possible per-
mutations, there would be n possibilities for the ¬rst, for each of these
n ’ 1 for the second, etc., until we came to the last object, and for
which there is only one possibility. Thus there are n(n ’ 1) . . . 1 = n!
™¦
possibilities in all.


Example 3.11 If there are three roads from city x to city y and two
roads from city y to city z, then there are 3 · 2 = 6 ways that a person
™¦
can drive from city x to city z passing through city y.


Example 3.12 Suppose there are n applicants for a certain job. Three
interviewers are asked independently to rank the applicants according
to their suitability for the job. It is decided that an applicant will be
hired if he or she is ranked ¬rst by at least two of the three interviewers.
47
3.3. PERMUTATIONS

What fraction of the possible reports would lead to the acceptance of
some candidate? We shall solve this problem by ¬nding the fraction
of the reports which do not lead to an acceptance and subtract this
answer from 1. Frequently, an indirect attack of this kind on a problem
is easier than the direct approach. The total number of reports possible
is (n!)3 since each interviewer can rank the men in n! di¬erent ways.
If a particular report does not lead to the acceptance of a candidate,
it must be true that each interviewer has put a di¬erent applicant in
¬rst place. This can be done in n(n ’ 1)(n ’ 2) di¬erent ways by our
general principle. For each possible ¬rst choices, there are [(n ’ 1)!]3
ways in which the remaining men can be ranked by the interviewers.
Thus the number of reports which do not lead to acceptance is n(n ’
1)(n ’ 2)[(n ’ 1)!]3 . Dividing this number by (n!)3 we obtain

(n ’ 1)(n ’ 2)
n2
as the fraction of reports which fail to accept a candidate. The fraction
which leads to acceptance is found by subtracting this fraction from 1
which gives
3n ’ 2
n2
7
For the case of three applicants, we see that 9 of the possibilities lead to
acceptance. Here the procedure might be criticized on the grounds that
even if the interviewers are completely ine¬ective and are essentially
guessing there is a good chance that a candidate will be accepted on
the basis of the reports. For n equal to ten, the fraction of acceptances
is only .28, so that it is possible to attach more signi¬cance to the
™¦
interviewers ratings, if they reach a decision.

Exercises
1. In how many ways can ¬ve people be lined up in a row for a group
picture? In how many ways if it is desired to have three in the
front row and two in the back row?

[Ans. 120;120.]

2. Assuming that a baseball team is determined by the players and
the position each is playing, how many teams can be made from
13 players if
48 CHAPTER 3. PARTITIONS AND COUNTING

(a) Each player can play any position?
(b) Two of the players can be used only as pitchers?
3. Grades of A, B, C, D, or F are assigned to a class of ¬ve students.
(a) How many ways may this be done, if no two students receive
the same grade?
[Ans. 120.]
(b) Two of the students are named Smith and Jones. How many
ways can grades be assigned if no two students receive the
same grade and Smith must receive a higher grade than
Jones?
[Ans. 60.]
(c) How many ways may grades be assigned if only grades of A
and F are assigned?
[Ans. 32.]
4. A certain club wishes to admit seven new members, four of whom
are Republicans and three of whom are Democrats. Suppose the
club wishes to admit them one at a time and in such a way that
there are always more Republicans among the new members than
there are Democrats. Draw a tree to represent all possible ways
in which new members can be admitted, distinguishing members
by their party only.
5. There are three di¬erent routes connecting city A to city B. How
many ways can a round trip be made from A to B and back?
How many ways if it is desired to take a di¬erent route on the
way back?

[Ans. 9;6.]

6. How many di¬erent ways can a ten-question multiple-choice exam
be answered if each question has three possibilities, a, b, and c?
How many if no two consecutive answers are the same?
7. Modify Example 3.12 so that, to be accepted, an applicant must
be ¬rst in two of the interviewers™ ratings and must be either ¬rst
or second in the third interviewers™ rating. What fraction of the
possible reports lead to acceptance in the case of three applicants?
In the case of n?
49
3.3. PERMUTATIONS

[Ans. 4 ; n2 .]
4
9


8. A town has 1240 registered Republicans. It is desired to contact
each of these by phone to announce a meeting. A committee of
r people devise a method of phoning s people each and asking
each of these to call t new people. If the method is such that no
person is called twice,

(a) How many people know about the meeting after the phon-
ing?
(b) If the committee has 40 members and it is desired that all
1240 Republicans be informed of the meeting and that s and
t should be the same, what should they be?

9. In the Scrabble example (Example 3.7), suppose the letters are
Q, Q, U, F, F, F, A. How many distinguishable arrangements are
there for these seven letters?

[Ans. 420.]

10. How many di¬erent necklaces can be made

(a) If seven di¬erent sized beads are available?
[Ans. 360.]
(b) If six of the beads are the same size and one is larger?
[Ans. 1.]
(c) If the beads are of two sizes, ¬ve of the smaller size and two
of the larger size?
[Ans. 3.]

11. Prove that two people in Columbus, Ohio, have the same initials.

12. Find the number of distinguishable arrangements for each of the
following collections of ¬ve symbols. (The same letters with dif-
ferent subscripts indicate distinguishable objects.)

(a) A1 , A2 , B1 , B2 , B3 .
[Ans. 120.]
50 CHAPTER 3. PARTITIONS AND COUNTING

(b) A, A, B1 , B2 , B3 .
[Ans. 60.]
(c) A, A, B, B, B.

13. Show that the number of distinguishable arrangements possible
for n objects, n1 of type 1, n2 of type 2, etc., for r di¬erent types
is
n!
.
n1 !n2 ! · · · nr !
Supplementary exercises.

14. (a) How many four digit numbers can be formed from the digits
1, 2, 3, 4, using each digit only once?
(b) How many of these numbers are less than 3000?
[Ans. 12.]

15. How many license plates can be made if they are to contain ¬ve
symbols, the ¬rst two being letters and the last three digits?

16. How many signals can a ship show if it has seven ¬‚ags and a signal
consists of ¬ve ¬‚ags hoisted vertically on a rope?

[Ans. 2520.]

17. We must arrange three green, two red, and four blue books on a
single shelf.

(a) In how many ways can this be done if there are no restric-
tions?
(b) In how many ways if books of the same color must be grouped
together?
(c) In how many ways if, in addition to the restriction in 17b,
the red books must be to the left of the blue books?
(d) In how many ways if, in addition to the restrictions in 17b
and 17c, the red and blue books must not be next to each
other?
[Ans. 288.]
51
3.4. COUNTING PARTITIONS

18. A youngster has three shades of nail polish with which to paint
his or her ¬ngernails. In how many ways can he or she do this
(each nail being one solid color) if there are no more than two
di¬erent shades on each hand?

[Ans. 8649.]


3.4 Counting partitions
Up to now we have not had occasion to consider the partitions [{1, 2}, {3, 4}]
and [{3, 4}, {1, 2}] of the integers from 1 to 4 as being di¬erent parti-
tions. Here it will be convenient to do so, and to indicate this distinc-
tion we shall use the term ordered partition. An ordered partition with
r cells is a partition with r cells (some of which may be empty), with
a particular order speci¬ed for the cells.
We are interested in counting the number of possible ordered par-
titions with r cells that can be formed from a set of n objects having a
prescribed number of elements in each cell. We consider ¬rst a special
case to illustrate the general procedure.
Suppose that we have eight students, A, B, C, D, E, F, G, and H,
and we wish to assign these to three rooms, Room 1, which is a triple
room, Room 2, a triple room, and Room 3, a double room. In how
many di¬erent ways can the assignment be made? One way to assign
the students is to put them in the rooms in the order in which they
arrive, putting the ¬rst three in Room 1, the next three in Room 2,
and the last two in Room 3. There are 8! ways in which the students
can arrive, but not all of these lead to di¬erent assignments. We can
represent the assignment corresponding to a particular order of arrival
as follows,
|BCA|DF E|HG|.
In this case, B, C, and A are assigned to Room 1, D, F, and E to Room
2, and H and G to Room 3. Notice that orders of arrival which simply
change the order within the rooms lead to the same assignment. The
number of di¬erent orders of arrival which lead to the same assignment
as the one above is the number of arrangements which di¬er from the
given one only in that the arrangement within the rooms is di¬erent.
There are 3! · 3! · 2! such orders of arrival, since we can arrange the
three in Room 1 in 3! di¬erent ways, for each of these the ones in
Room 2 in 3! di¬erent ways, and for each of these, the ones in Room
52 CHAPTER 3. PARTITIONS AND COUNTING

3 in 2! ways. Thus we can divide the 8! di¬erent orders of arrival into
groups of 3! · 3! · 2! di¬erent orders such that all the orders of arrival
in a single group lead to the same room assignment. Since there are
3! · 3! · 2! elements in each group and 8! elements altogether, there are
8!
groups, or this many di¬erent room assignments.
3!3!2!
The same argument could be carried out for n elements and r rooms,
with n1 in the ¬rst, n2 in the second, etc. This would lead to the
following result. Let n1 , n2 , . . . , nr be nonnegative integers with

n1 + n2 + . . . + nr = n.

Then:
The number of ordered partitions with r cells [A1 , A2 , . . . , Ar ] of a
set of n elements with n1 in the ¬rst cell, n2 in the second, etc. is
n!
n1 !n2 ! . . . nr !

We shall denote this number by the symbol
n!
.
n1 !, n2 !, . . . , nr !
Note that this symbol is de¬ned only if n1 + n2 + . . . + nr = n.
The special case of two cells is particularly important. Here the
problem can be stated equivalently as the problem of ¬nding the num-
ber of subsets with r elements that can be chosen from a set of n
˜
elements. This is true because any choice de¬nes a partition [A, A],
˜
where A is the set of elements chosen and A is the set of remaining
elements.
n!
The number of such partitions is r!(n’r)! and hence this is also the
n
number of subsets with r elements. Our notation for this case
r,n’r
n
is shortened to .
r
n
Notice that n’r is the number of subsets with n ’ r elements
which can be chosen from n, which is the number of partitions of the
˜ ˜
form [A, A] above. Clearly, this is the same as the number of [A, A]
partitions. Hence n = n’r .
n
r

Example 3.13 A college has scheduled six football games during a
season. How many ways can the season end in two wins, three losses,
and one tie? From each possible outcome of the season, we form a
53
3.4. COUNTING PARTITIONS

partition, with three cells, of the opposing teams. In the ¬rst cell
we put the teams which our college defeats, in the second the teams
to which our college loses, and in the third cell the teams which our
6
college ties. There are 2,3,1 = 60 such partitions, and hence 60 ways
in which the season can end with two wins, three losses, and one tie. ™¦

Example 3.14 In the game of bridge, the hands N, E, S, and W deter-
mine a partition of the 52 cards having four cells, each with 13 elements.
52!
Thus there are 13!13!13!13! di¬erent bridge deals. This number is about
5.3645 · 1028 , or approximately 54 billion billion billion deals. ™¦

Example 3.15 The following example will be important in probability
theory, which we take up in the next chapter. If a coin is thrown six
times, there are 26 possibilities for the outcome of the six throws, since
each throw can result in either a head or a tail. How many of these
possibilities result in four heads and two tails? Each sequence of six
heads and tails determines a two-cell partition of the numbers from
one to six as follows: In the ¬rst cell put the numbers corresponding
to throws which resulted in a head, and in the second put the numbers
corresponding to throws which resulted in tails. We require that the
¬rst cell should contain four elements and the second two elements.
Hence the number of the 26 possibilities which lead to four heads and
two tails is the number of two-cell partitions of six elements which have
four elements in the ¬rst cell and two in the second cell. The answer is
6
= 15. For n throws of a coin, a similar analysis shows that there are
4
n
di¬erent sequences of H™s and T™s of length n which have exactly r
r
heads and n ’ r tails. ™¦

Exercises
1. Compute the following numbers.
7
(a) 5

[Ans. 21.]
3
(b) 2
7
(c) 2
250
(d) 249
54 CHAPTER 3. PARTITIONS AND COUNTING

[Ans. 250.]
5
(e) 0
5
(f) 1,2,2
4
(g) 2,0,2

[Ans. 6.]
2
(h) 1,1,1


2. Give an interpretation for n and also for n
. Can you now give
0 n
a reason for making 0! = 1?
3. How many ways can nine students be assigned to three triple
rooms? How many ways if one particular pair of students refuse
to room together?

[Ans. 1680; 1260.]

4. A group of seven boys and ten girls attends a dance. If all the
boys dance in a particular dance, how many choices are there for
the girls who dance? For the girls who do not dance? How many
choices are there for the girls who do not dance, if three of the
girls are sure to be asked to dance?
5. Suppose that a course is given at three di¬erent hours. If ¬fteen
students sign up for the course,
(a) How many possibilities are there for the ways the students
could distribute themselves in the classes?
[Ans. 315 .]
(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.

The same method can be carried out in general for ¬nding the ex-
pansion of (x1 + x2 + . . . + xr )n . From each factor we choose either an
x1 , or x2 , . . . , or xr , form the product and add these products for all
possible choices. We will have r n products, but many will be equal. A
particular choice of one term from each factor determines an r-cell par-
tition of the numbers from 1 to n. In the ¬rst cell we put the numbers
of the factors from which we choose an x1 , in the second cell those from
which we choose x2 , etc. A particular choice gives us a term of the form
xn1 xn2 . . . xnr with n1 + n2 + . . . + nr = n. The corresponding partition
1 2 r
has n1 elements in the ¬rst cell, n2 in the second, etc. For each such
partition we obtain one such term. Hence the number of these terms
which we obtain is the number of such partitions, which is

n n!
= .
n1 , n2 , . . . , n r n1 !n2 ! . . . nr !
64 CHAPTER 3. PARTITIONS AND COUNTING

Thus we have the multinomial theorem.
Multinomial theorem. The expansion of (x1 + x2 + . . . + xr )n is
found by adding all terms of the form

n
xn 1 xn 2 . . . x n r
n1 , n2 , . . . , n r 1 2 r


where n1 + n2 + . . . + nr = n.

Exercises
1. Expand by the binomial theorem

(a) (x + y)4 .
(b) (1 + x)5 .
(c) (x ’ y)3 .
(d) (2x + a)4 .
(e) (2x ’ 3y)3 .
(f) (100 ’ 1)5 .

2. Expand

(a) (x + y + x)4 .
(b) (2x + y ’ z)3 .
(c) (2 + 2 + 1)3 . (Evaluate two ways.)

3. (a) Find the coe¬cient of the term x2 y 3 z 2 in the expansion of
(x + y + z)7 .
[Ans. 210.]
(b) Find the coe¬cient of the term x6 y 3 z 2 in the expression (x’
2y + 5z)11
[Ans. -924,000.]

4. Using the binomial theorem prove that
(a)

n n n n
= 2n .
+ + +...+
0 1 2 n
65
3.6. BINOMIAL AND MULTINOMIAL THEOREMS

(b)

n n n n n
’ ’ +...±
+ =0
0 1 2 3 n

for n > 0.

5. Using an argument similar to the one in Section 3.6, prove that

n+1 n n n
= + + .
i ’ 1, j, k i, j ’ 1, k i, j, k ’ 1
i, j, k

6. Let f (n, r) be the number of terms in the multinomial expansion
of
(x1 + x2 + . . . + xr )n
and show that
n+r’1
f (n, r) = .
n
[Hint: Show that the conditions of Exercise 10 are satis¬ed by
showing that f (n, r ’ 1) is the number of terms which do not
have xr and f (n ’ 1, r) is the number which do.]

7. How many terms are there in each of the expansions:

(a) (x + y + z)6 ?
[Ans. 28.]
(b) (a + 2b + 5c + d)4 ?
[Ans. 35.]
(c) (r + s + t + u + v)6 ?
[Ans. 210.]
n
8. Prove that k n is the sum of the numbers for all choices
r1 ,r2 ,...,rk
of r1 , r2 , . . . , rk such that

r1 + r2 + . . . + rk = n.

Supplementary exercises.
66 CHAPTER 3. PARTITIONS AND COUNTING

9. Show that the problem given in Exercise 15b can also be solved
by a multinomial coe¬cient, and hence show that

n’k
n n r n
= = .
n ’ r, r ’ k, k r’k
r k k

10. Show that the problem given in Exercise 16 can also be solved by
a multinomial coe¬cient, and hence show that

n’s n’k
n n r k n
= = .
n ’ r, r ’ k, k ’ s, s k’s r’k
r k s s

11. If a + b + c = n, show that

n’a
n n
= .
a, b, c a b

12. If a + b + c + d = n, show that

n’a n’a’b
n n
= .
a, b, c, d a b c

13. If n1 + n2 + . . . + nr = n, guess a formula that relates the multino-
mial coe¬cient to a product of binomial coe¬cients. [Hint: Use
the formulas in Exercises 11 and 12 to guide you.]

14. Use Exercises 11, 12, and 13 to show that the multinomial co-
e¬cients can always be obtained by taking products of suitable
numbers in the ¬rst n rows of the Pascal triangle.


3.7 Voting power
We return to the problem raised in Section 2.6. Now we are interested
not only in coalitions, but also in the power of individual members. We
will develop a numerical measure of voting power that was suggested
by L. S. Shapley and M. Shubik. While the measure will be explained
in detail below, for the reasons for choosing this particular measure the
reader is referred to the original paper.
First of all we must realize that the number of votes a member
controls is not in itself a good measure of his or her power. If x has
three votes and y has one vote, it does not necessarily follow that x has
67
3.7. VOTING POWER

three times the power that y has. Thus if the committee has just three
members {x, y, z} and z also has only one vote, then x is a dictator and
y is powerless.
The basic idea of the power index is found in considering various
alignments of the committee members on a number of issues. The n
members are ordered x1 , x2 , . . . , xn according to how likely they are to
vote for the measure. If the measure is to carry, we must persuade x1
and x2 up to xi to vote for it until we have a winning coalition. If
{x1 , x2 , . . . , xi } is a winning coalition but {x1 , x2 , . . . , xi’1 } is not win-
ning, then xi is the crucial member of the coalition. We must persuade
him or her to vote for the measure, and he or she is the one hardest to
persuade of the i necessary members. We call xi the pivot.
For a purely mathematical measure of the power of a member we
do not consider the views of the members. Rather we consider all
possible ways that the members could be aligned on an issue, and see
how often a given member would be the pivot. That means considering
all permutations, and there will be n! of them. In each permutation
one member will be the pivot. The frequency with which a member is
the pivot of an alignment is a good measure of his or her voting power.
De¬nition. The voting power of a member of a committee is the
number of alignments in which he or she is pivotal divided by the total
number of alignments. (The total number of alignments, of course, is
n! for a committee of n members.)

Example 3.17 If all n members have one vote each, and it takes a
majority vote to carry a measure, it is easy to see (by symmetry) that
each member is pivot in 1/n of the alignments. Hence each member has
power equal to 1/n. Let us illustrate this for n = 3. There are 3! = 6
alignments. It takes two votes to carry a measure; hence the second
member is always the pivot. The alignments are: 123, 132, 213, 231,
312, 321. The pivots are emphasized. Each member is pivot twice,
hence has power 2 = 3 .
1
™¦
6


Example 3.18 Reconsider Example 2.9 of Section 2.6 from this point
of view. There are 24 permutations of the four members. We will list
them, with the pivot emphasized:
wxyz wxzy wyxz wyzx wzxy wzyx
xwyz xwzy xywz xyzw xzwy xzyw
yxwz yxzw ywxz ywzx yzxw yzwx
zxyw zxwy zyxw zywx zwxy zwyx
68 CHAPTER 3. PARTITIONS AND COUNTING

14 6 2
We see that z has power of 24 , w has 24 , x and y have 24 each. (Or,
7 3 1 1
simpli¬ed, they have 12 , 12 , 12 , 12 power, respectively.) We note that
these ratios are much further apart than the ratio of votes which is
3 : 2 : 1 : 1. Here three votes are worth seven times as much as the
™¦
single vote and more than twice as much as two votes.

Example 3.19 Reconsider Example 2.10 of Section 2.6. By an analy-
sis similar to the ones used so far it can be shown that in the Security
Council of the United Nations before 1966, each of the Big Five had
76
or approximately .197 power, while each of the small nations had
385
approximately .002 power. (See Exercise 12.) This reproduces our in-
tuitive feeling that, while the small nations in the Security Council are
not powerless, nearly all the power is in the hands of the Big Five.
The voting powers according to the 1966 revision will be worked
™¦
out in Exercise 13.

Example 3.20 In a committee of ¬ve each member has one vote, but
the chair has veto power. Hence the minimal winning coalitions are
three-member coalitions including the chair. There are 5! = 120 per-
mutations. The pivot cannot come before the chair, since without the
chair we do not have a winning coalition. Hence, when the chair is in
3
place number 3, 4, or 5, he or she is the pivot. This happens in 5 of the
permutations. When he or she is in position 1 or 2, then the number 3
member is pivot. The number of permutations in which the chair is in
one of the ¬rst two posltions and a given member is third is 2 · 3! = 12.
3 1
Hence the chair has power 5 , and each of the others has power 10 . ™¦

Exercises
1. A committee of three makes decisions by majority vote. Write
out all permutations, and calculate the voting powers if the three
members have

(a) One vote each.
111
[Ans. , , .]
333

(b) One vote for two of them, two votes for the third.
112
[Ans. , , .]
663

(c) One vote for two of them, three votes for the third.
69
3.7. VOTING POWER

[Ans. 0, 0, 1.]
(d) One, two, and three votes, respectively.
112
[Ans. , , .]
663

(e) Two votes each for two of them, and three votes for the
third.
111
[Ans. , , .]
333

2. Prove that in any decision-making body the sum of the powers of
the members is 1.

3. What is the power of a dictator? What is the power of a “pow-
erless” member? Prove that your answers are correct.

4. A large company issued 100,000 shares. These are held by three
stockholders, who have 50,000, 49,999, and one share, respec-
tively. Calculate the powers of the three members.

211
[Ans. , , .]
366


5. A committee consists of 100 members having one vote each, plus
a chairman who can break ties. Calculate the power distribution.
(Do not try to write out all permutations!)

6. In Exercise 5, give the chairman a veto instead of the power to
break ties. How does this change the power distribution?

50
[Ans. The chairman has power .]
101


7. How are the powers in Exercise 1 changed if the committee re-
3
quires a 4 vote to carry a measure?

8. If in a committee of ¬ve, requiring majority decisions, each mem-
1
ber has one vote, then each has power 5 . Now let us suppose that
two members team up, and always vote the same way. Does this
increase their power? (The best way to represent this situation is
by allowing only those permutations in which these two members
are next to each other.)

[Ans. Yes, the pair™s power increases from .4 to .5.]
70 CHAPTER 3. PARTITIONS AND COUNTING

9. If the minimal winning coalitions are known, show that the power
of each member can be determined without knowing anything
about the number of votes that each member controls.

10. Answer the following questions for a three-man committee.

(a) Find all possible sets of minimal winning coalitions.
(b) For each set of minimal winning coalitions ¬nd the distribu-
tion of voting power.
(c) Verify that the various distributions of power found in Ex-
ercises 1 and 7 are the only ones possible.

11. In Exercise 1 parts 1a and 1e have the same answer, and parts 1b
and 1d and Exercise 4 also have the same answer. Use the results
of Exercise 9 to ¬nd a reason for these coincidences.

12. Compute the voting power of one of the Big Five in the Security
Council of the United Nations as follows:

(a) Show that for the nation to be pivotal it must be in the
number 7 spot or later.
(b) Show that there are 6 6!4! permutations in which the nation
2
is pivotal in the number 7 spot.
(c) Find similar formulas for the number of permutations in
which it is pivotal in the number 8, 9, 10, or 11 spot.
(d) Use this information to ¬nd the total number of permuta-
tions in which it is pivotal, and from this compute the power
of the nation.

13. Apply the method of Exercise 12 to the revised voting scheme
in the Security Council (10 small-nation members, and 9 votes
required to carry a measure). What is the power of a large nation?
Has the power of one of the small nations increased or decreased?

421
[Ans. (nearly the same as before); decreased.]
2145



3.8 Techniques for counting
We know that there is no single method or formula for solving all count-
ing problems. There are, however, some useful techniques that can be
71
3.8. TECHNIQUES FOR COUNTING

learned. In this section we shall discuss two problems that illustrate
important techniques.
The ¬rst problem illustrates the importance of looking for a general
pattern in the examination of special cases. We have seen in Section
3.2 and Exercise 6 of that section, that the following formulas hold for
the number of elements in the union of two and three sets, respectively.

n(A1 ∪ A2 ) = n(A1 ) + n(A2 ) ’ n(A1 © A2 ),

n(A1 ∪ A2 ∪ A3 ) = n(A1 ) + n(A2 ) + n(A3 )
’n(A1 © A2 ) ’ n(A1 © A3 ) ’ n(A2 © A3 )
+n(A1 © A2 © A3 ).

On the basis of these formulas we might conjecture that the number of
elements in the union of any ¬nite number of sets could be obtained by
adding the numbers in each of the sets, then subtracting the numbers in
each possible intersection of two sets, then adding the numbers in each
possible intersection of three sets, etc. If this is correct, the formula for
the intersection of four sets should be

n(A1 ∪ A2 ∪ A3 ∪ A4 ) = n(A1 ) + n(A2 ) + n(A3 ) + n(A4 ) (3.1)
’ n(A1 © A2 ) ’ n(A1 © A3 ) ’ n(A1 © A4 )
’ n(A2 © A3 ) ’ n(A2 © A4 ) ’ n(A3 © A4 )
+ n(A1 © A2 © A3 ) + n(A1 © A2 © A4 )
+ n(A1 © A3 © A4 ) + n(A2 © A3 © A4 )
’ n(A1 © A2 © A3 © A4 )

Let us try to establish this formula. We must show that if u is an
element of at least one of the four sets, then it is counted exactly once
on the right-hand side of 3.1. We consider separately the cases where
u is in exactly 1 of the sets, exactly 2 of the sets, etc.
For instance, if u is in exactly two of the sets it will be counted twice
in the terms of the right-hand side of 3.1 that involve single sets, once
in the terms that involve the intersection of two sets, and not at all in
the terms that involve the intersections of three or four sets. Again, if
u is in exactly three of the sets it will be counted three times in the
terms involving single sets, twice in the terms involving intersections
of two sets, once in the terms involving the intersections of three sets,
and not at all in the last term involving the intersection of all four sets.
Considering each possibility we have the following table.
72 CHAPTER 3. PARTITIONS AND COUNTING

Number of sets that contain u Number of times it is counted
1 1
2’1
2
3’3+1
3
4’6+4’1
4
We see from this that, in every case, u is counted exactly once on the
right-hand side of 3.1. Furthermore, if we look closely, we detect a
pattern in the numbers in the righthand column of the above table. If
we put a ’1 in front of these numbers we have
’1 + 1
1
’1 + 2 ’ 1
2
’1 + 3 ’ 3 + 1
3
’1 + 4 ’ 6 + 4 ’ 1
4
We now recognize that these numbers are simply the numbers in the
¬rst four rows of the Pascal triangle, but with alternating + and ’
signs. Since we put a ’1 in each row of the table, we want to show
that the sum of each row is 0. If that is true, it should be a general
property of the Pascal triangle. That is, if we put alternating signs in
the jth row of the Pascal triangle, we should get a sum of 0. But this
is indeed the case, since, by the binomial theorem, for j > 0,

0 = ±(1 ’ 1)j
j j j
= 1’ ’ +...±1
+
1 2 3
j j j
= ’1 + ’ ’ . . . 1.
+
1 2 3
Thus we have not only seen why the formula works for the case of four
sets, but we have also found the method for proving the formula for the
general case. That is, suppose we wish to establish that the number of
elements in the union of n sets may be obtained as an alternating sum
by adding the numbers of elements in each of the sets, subtracting the
numbers of elements in each pairwise intersection of the sets, adding the
numbers of elements in each intersection of three sets, etc. Consider
an element u that is in exactly j of the sets. Let us see how many
times u will be counted in the alternating sum. If it is in j of the sets,
it will ¬rst be counted j times in the sum of the elements in the sets
by themselves. For u to be in the intersection of two sets, we must
j
choose two of the j sets to which it belongs. This can be done in 2
73
3.8. TECHNIQUES FOR COUNTING

j
di¬erent ways. Hence an amount 2 will be subtracted from the sum.
To be in the intersection of three sets, we must choose three of the j
j
sets containing u. This can be done in 3 di¬erent ways. Thus, an
j
amount 3 will be added to the sum, etc. Hence the total number of
times u will be counted by the alternating sum is

j j j
’ ’ ...± 1
+
1 2 3

since we have just seen that, if we add ’1 to the sum, we obtain 0.
Hence the sum itself must always be 1. That is, no matter how many
sets u is in, it will be counted exactly once by the alternating sum, and
this is true for every element u in the union. We have thus established
the general formula

n(A1 ∪ A2 ∪ . . . ∪ An ) = n(A1 ) + n(A2 ) + . . . + n(An ) (3.2)
’n(A1 © A2 ) ’ n(A1 © A3 ) ’ . . .
+n(A1 © A2 © A3 ) + n(A1 © A2 © A4 ) + . . .
’...
±n(A1 © A2 © . . . © An ).

This formula is called the inclusion-exclusion formula for the number
of elements in the union of n sets. It can be extended to formulas for
counting the number of elements that occur in two of the sets, three of
the sets, etc. See Exercises 21, 25, and 27.

Example 3.21 In a high school the following language enrollments are
recorded for the senior class.
English 150
French 75
German 35
Spanish 50

Also, the following overlaps are noted.

Taking English and French 70
Taking English and German 30
Taking English and Spanish 40
Taking French and German 5
Taking English, French and German 2
74 CHAPTER 3. PARTITIONS AND COUNTING

If every student takes at least one language, how many seniors are
there?
Let E, F , G, and S be the sets of students taking English, French,
German, and Spanish, respectively. Using formula 3.1 and ignoring
empty sets, we have

n(E ∪ F ∪ G ∪ S) = n(E) + n(F ) + n(G) + n(S)
’ n(E © F ) ’ n(E © G) ’ n(E © S) ’ n(F © G)
+ n(E © F © G)
= 150 + 75 + 35 + 50 ’ 70 ’ 30 ’ 40 ’ 5 + 2
= 167.

Since every student takes at least one language, the total number of
™¦
students is 167.

Example 3.22 The four words

TABLE, BASIN, CLASP, BLUSH

have the following interesting properties. Each word consists of ¬ve
di¬erent letters. Any two words have exactly two letters in common.
Any three words have one letter in common. No letter occurs in all
four words. How many di¬erent letters are there?
Letting the words be sets of letters, there are 4 ways of taking
1
4
these sets one at a time, ways of taking them two at a time, etc.
2
Hence formula 3.2 gives

4 4 4 4
·5’ ·2+ ·1’ · 0 = 12
1 2 3 4

<<

. 2
( 6)



>>