6.3 THE PRINCIPLE OF INCLUSION-EXCLUSION 207
6.2.32 In Example 6.2.4 on page 200, the incorrect
argument overcounted by 48. Account exactly for this
discrepancy.
6.2.33 As defined in Problem 4.3.17 on page 142, let
p(n) denote the number of unrestricted partitions of n.
Show that p(n) 2 2lv'nJ for all n 2 2.
6.2.34 (Putnam 1993) Let f!lJn be the set of subsets
of {l, 2, ... ,n }. Let c( n, m) be the number of func
tions f: f!lJn ..... {1,2, ... ,m} such that f(A nB) =
min{f(A),j(B)}. Prove that
m
c(n,m) = � jn.
}= 1
6.3 The Principle of Inclusion-Exclusion
The partitioning tactic makes a pretty utopian assumption, namely that the thing we
wish to count can be nicely broken down into pairwise disjoint subsets. Reality is often
messier, and new tactics are needed. We shall explore a number of ways of dealing
with situations where sets overlap and overcounting is not uniform.
Count the Complement
By now you are used to the strategy of changing your point of view. A particular
application of this in counting problems is
If the thing you wish to count is confusing, try looking at its complement
instead.
Example 6.3. 1 How many n-bit strings contain at least one zero?
Solution: Counting this directly is hard, because there are n cases, namely, exactly
one zero, exactly two zeros, .... This is certainly not impossible to do, but an easier
approach is to first note that there are 2 n possible n-bit strings, and then count how
many of them contain no zeros. There is only one such string (the string containing n
Is). So our answer is 2 n -1. •
Example 6.3.2 Ten children order ice-cream cones at a store featuring 31 flavors.
How many orders are possible in which at least two children get the same flavor?
Solution: We shall make the humanistic assumption that the children are distin
guishable. Then we are counting a pretty complex thing. For example, one order
might be that all the children order flavor #6. Another order might specify that child
#7 and child #9 each order flavor #12 and children #1-4 order flavor #29, etc. Let us
first count all possible orders with no restrictions; that is just 3 110, since each of the
10 kids has 3 1 choices. Now we count orders where there is no duplication of flavor;
that is just 31 x 30 x 29 x ... x 22 = P( 3 1, 10). The answer is then the difference
3 11O-P( 3 1,1O). •
PIE with Sets
Sometimes the complement counting tactic fails us, because the complement is just
as complicated as the original set. The principle of inclusion-exclusion (PIE) is a
