<< . .

. 8
( : 20)



. . >>

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

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

<< . .

. 8
( : 20)



. . >>