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

as the number of distinct letters. The reader should verify this answer

™¦

by direct count.

It often happens that a counting problem can be formulated in a

number of di¬erent ways that sound quite di¬erent but that are in fact

equivalent. And in one of these ways the answer may suggest itself

readily. To illustrate how a reformulation can make a hard sounding

problem easy, we give an alternate method for solving the problem

considered in Exercise 13.

The problem is to count the number of ways that n indistinguishable

objects can be put into r cells. For instance, if there are three objects

75

3.8. TECHNIQUES FOR COUNTING

and three cells, the number of di¬erent ways can be enumerated as

follows (Using —¦ for object and bars to indicate the sides of the cells:

| —¦—¦—¦ | | |

| —¦—¦ | —¦ | |

| —¦—¦ | | —¦ |

| —¦ | —¦—¦ | |

| —¦ | —¦ | —¦ |

| | —¦—¦—¦ | |

| | —¦—¦ | —¦ |

| | —¦ | —¦—¦ |

| | | —¦—¦—¦ |

We see that in this case there are ten ways the task can be accomplished.

But the answer for the general case is not clear.

If we look at the problem in a slightly di¬erent manner, the answer

suggests itself. Instead of putting the objects in the cells, we imagine

putting the cells around the objects. In the above case we see that

three cells are constructed from four bars. Two of these bars must

be placed at the ends. The two other bars together with the three

objects we regard as occupying ¬ve intermediate positions. Of these

¬ve intermediate positions we must choose two of them for bars and

three for the objects. Hence the total number of ways we can accomplish

the task is 5 = 5 = 10, which is the answer we got by counting all

2 3

the ways.

For the general case we can argue in the same manner. We have r

cells and n objects. We need r + 1 bars to form the r cells, but two

of these must be ¬xed on the ends. The remaining r ’ 1 bars together

with the n objects occupy r ’ 1 + n intermediate positions. And we

must choose r ’ 1 of these for the bars and the remaining n for the

objects. Hence our task can be accomplished in

n+r’1 n+r’1

=

r’1 n

di¬erent ways.

Example 3.23 Seven people enter an elevator that will stop at ¬ve

¬‚oors. In how many di¬erent ways can the people leave the elevator if

we are interested only in the number that depart at each ¬‚oor, and do

not distinguish among the people? According to our general formula,

76 CHAPTER 3. PARTITIONS AND COUNTING

the answer is

7+5’1 11

= = 330.

7 7

Suppose we are interested in ¬nding the number of such possibilities in

which at least one person gets o¬ at each ¬‚oor. We can then arbitrarily

assign one person to get o¬ at each ¬‚oor, and the remaining two can

get o¬ at any ¬‚oor. They can get o¬ the elevator in

2+5’1 6

= = 15

2 2

™¦

di¬erent ways.

Exercises

1. The survey discussed in Exercise 8 has been enlarged to include

a fourth magazine D. It was found that no one who reads either

magazine A or magazine B reads magazine D. However, 10 per

cent of the people read magazine D and 5 per cent read both C

and D. What per cent of the people do not read any magazine?

[Ans. 5 per cent.]

2. A certain college administers three qualifying tests. They an-

nounce the following results: “Of the students taking the tests, 2

per cent failed all three tests, 6 per cent failed tests A and B, 5

per cent failed A and C, 8 per cent failed B and C, 29 per cent

failed test A, 32 per cent failed B, and 16 per cent failed C.” How

many students passed all three qualifying tests?

3. Four partners in a game require a score of exactly 20 points to

win. In how many ways can they accomplish this?

23

[Ans. .]

3

4. In how many ways can eight apples be distributed among four

boys? In how many ways can this be done if each boy is to get

at least one apple?

5. Suppose we have n balls and r boxes with n ≥ r. Show that the

number of di¬erent ways that the balls can be put into the boxes

which insures that there is at least one ball in every box is n’1 .

r’1

77

3.8. TECHNIQUES FOR COUNTING

6. Identical prizes are to be distributed among ¬ve boys. It is ob-

served that there are 15 ways that this can be done if each boy is

to get at least one prize. How many prizes are there?

[Ans. 7.]

7. Let p1 , p2 , . . . , pn be n statements relative to a possibility space

U . Show that the inclusion-exclusion formula gives a formula

for the number of elements in the truth set of the disjunction

p1 ∨ p2 ∨ . . . ∨ pn in terms of the numbers of elements in the truth

sets of conjunctions formed from subsets of these statements.

8. A boss asks his or her secretary to put letters written to seven

di¬erent persons into addressed envelopes. Find the number of

ways that this can be done so that at least one person gets his or

her own letter. [Hint: Use the result of Exercise 7, letting pi be

the statement “The ith person gets his or her own letter”.]

[Ans. 3186.]

9. Consider the numbers from 2 to 10 inclusive. Let A2 be the set of

numbers divisible by 2 and A3 the set of numbers divisible by 3.

Find n(A2 ∪ A3 ) by using the inclusion-exclusion formula. From

this result ¬nd the number of prime numbers between 2 and 10

(where a prime number is a number divisible only by itself and

by 1). [Hint: Be sure to count the numbers 2 and 3 among the

primes.]

10. Use the method of Exercise 9 to ¬nd the number of prime numbers

between 2 and 100 inclusive. [Hint: Consider ¬rst the sets A2 ,

A3 , A5 , and A7 .]

[Ans. 25.]

11. Verify that the following formula gives the number of elements in

the intersection of three sets.

n(A1 © A2 © A3 ) = n(A1 ) + n(A2 ) + n(A3 )

’ n(A1 ∪ A2 ) ’ n(A1 ∪ A3 ) ’ n(A2 ∪ A3 )

+ n(A1 ∪ A2 ∪ A3 ).

78 CHAPTER 3. PARTITIONS AND COUNTING

12. Show that if we replace © by ∪ and ∪ by © in formula 3.2, we

get a valid formula for the number of elements in the intersection

of n sets. [Hint: Apply the inclusion-exclusion formula to the

left-hand side of

˜ ˜ ˜

n(A1 ∪ A2 ∪ . . . ∪ An ) = n(U ) ’ n(A1 © A2 © . . . © An .]

13. For n ¤ m prove that

m n m n m n m n m+n

+ + +...+ =

0 0 1 1 2 2 n n n

by carrying out the following two steps:

(a) Show that the left-hand side counts the number of ways of

choosing equal numbers of men and women from sets of m

men and n women.

(b) Show that the right-hand side also counts the same number

by showing that we can select equal numbers of men and

women by selecting any subset of n persons from the whole

set, and then combining the men selected with the women

not selected.

14. By an ordered partition of n with r elements we mean a sequence

of r nonnegative integers, possibly some 0, written in a de¬nite

order, and having n as their sum. For instance, [1, 0, 3] and [3, 0, 1]

are two di¬erent ordered partitions of 4 with three elements. Show

that the number of ordered partitions of n with r elements is

n+r’1

.

n

15. Show that the number of di¬erent possibilities for the outcomes

of rolling n dice is n+5 .

n

Note. The next few exercises illustrate an important counting

technique called the re¬‚ection principle. In Figure 3.6 we show

a path from the point (0, 2) to the point (7, 1). We shall be

interested in counting the number of paths of this type where at

each step the path moves one unit to the right, and either one

unit up or one unit down. We shall see that this model is useful

for analyzing voting outcomes.

16. Show that the number of di¬erent paths leading from the point

(0, 2) to (7, 1) is 7 . [Hint: Seven decisions must be made, of

3

which three moves are up and the rest down.]

79

3.8. TECHNIQUES FOR COUNTING

Figure 3.6: ™¦

17. Show that the number of di¬erent paths from (0, 2) to (7, 1) which

touch the x-axis at least once is the same as the total number of

paths from the point (0, ’2) to the point (7, 1). [Hint: Show

that for every path to be counted from (0, 2) that touches the x-

axis, there corresponds a path from (0, ’2) to (7, 1) obtained by

re¬‚ecting the part of the path to the ¬rst touching point through

the x-axis. A speci¬c example is shown in Figure 3.7.]

18. Use the results of Exercises 16 and 17 to ¬nd the number of paths

from (0, 2) to (7, 1) that never touch the x-axis.

[Ans. 14.]

19. Nine votes are cast in a race between two candidates A and B.

Candidate A wins by one vote. Find the number of ways the

ballots can be counted so that candidate A is leading throughout

the entire count. [Hint: The ¬rst vote counted must be for A.

Counting the remaining eight votes corresponds to a path from

(1, 1) to (9, 1). We want the number of paths that never touch

the x-axis.]

[Ans. 14.]

(k)

20. Let the symbol nr stand for “the number of elements that are

(1)

in k or more of the r sets A1 , A2 , . . . , Ar ”. Show that n3 =

n(A1 ∪ A2 ∪ A3 ).

80 CHAPTER 3. PARTITIONS AND COUNTING

Figure 3.7: ™¦

21. Show that

(2)

= n((A1 © A2 ) ∪ (A1 © A3 ) ∪ (A2 © A3 ))

n3

= n(A1 © A2 ) + n(A1 © A3 ) + n(A2 © A3 ) ’ 2n(A1 © A2 © A3 )

by using the inclusion-exclusion formula. Also develop an inde-

pendent argument for the last formula.

22. Use Exercise 21 to ¬nd the number of letters that appear two or

more times in the three words TABLE, BASIN, and CLASP.

(1) (2)

23. Give an interpretation for n3 ’ n3 .

24. Use Exercise 23 to ¬nd the number of letters that occur exactly

once in the three words of Exercise 22.

25. Develop a general argument like that in Exercise 21 to show that

(2)

= n(A1 © A2 ) + n(A1 © A3 ) + n(A1 © A4 )

n4

+ n(A2 © A3 ) + n(A2 © A4 ) + n(A3 © A4 )

’ 2[n(A1 © A2 © A3 ) + n(A1 © A2 © A4 )

+ n(A1 © A3 © A4 ) + n(A2 © A3 © A4 )]

+ 3n(A1 © A2 © A3 © A4 )

26. Use Exercise 25 to ¬nd the number of letters used two or more

times in the four words of Example 3.22.

81

3.8. TECHNIQUES FOR COUNTING

27. From the formulas in Exercises 21 and 25 guess the general for-

mula for n(2) and develop a general argument to establish its

r

correctness.

Suggested reading.

Shapley, L. S., and M. Shubik, “A Method for Evaluating the Distribu-

tion of Power in a Committee System”, The American Political Science

Review 48 (1954), pp. 787“792.

Whitworth, W. A., Choice and Chance, with 1000 Exercises, 1934.

Goldberg, S., Probability: An Introduction, 1960.

Parzen, E., Modern Probability Theory and Its Applications, 1960.

82 CHAPTER 3. PARTITIONS AND COUNTING

Chapter 4

Probability theory

4.1 Introduction