ńņš. 2 |

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 |