Page 580 - Discrete Mathematics and Its Applications

8.6 Applications of Inclusion–Exclusion 559
EXAMPLE 1
Writing these quantities in terms of sets, we have
).
|A i 1 ∩ A i 2 ∩ ··· ∩ A i k |= N(P i 1 i 2
P ...P i k
If the number of elements with none of the properties P 1 ,P 2 ,...,P n is denoted by
N(P P ...P ) and the number of elements in the set is denoted by N, it follows that
1 2 n
N(P P ...P ) = N −|A 1 ∪ A 2 ∪ ··· ∪ A n |.
1 2 n
From the inclusion–exclusion principle, we see that
N(P P ...P ) = N − N(P i ) + N(P i P j )
1 2 n
1≤i≤n 1≤i<j≤n
n
− N(P i P j P k ) + ··· + (−1) N(P 1 P 2 ...P n ).
1≤i<j<k≤n
Example 1 shows how the principle of inclusion–exclusion can be used to determine the
number of solutions in integers of an equation with constraints.
How many solutions does
x 1 + x 2 + x 3 = 11
have, where x 1 , x 2 , and x 3 are nonnegative integers with x 1 ≤ 3, x 2 ≤ 4, and x 3 ≤ 6?
Solution: To apply the principle of inclusion–exclusion, let a solution have property P 1
if x 1 > 3, property P 2 if x 2 > 4, and property P 3 if x 3 > 6. The number of solutions satis-
fying the inequalities x 1 ≤ 3, x 2 ≤ 4, and x 3 ≤ 6is
N(P P P ) = N − N(P 1 ) − N(P 2 ) − N(P 3 ) + N(P 1 P 2 )
1 2 3
+ N(P 1 P 3 ) + N(P 2 P 3 ) − N(P 1 P 2 P 3 ).
Using the same techniques as in Example 5 of Section 6.5, it follows that
N = total number of solutions = C(3 + 11 − 1, 11) = 78,
N(P 1 ) = (number of solutions with x 1 ≥ 4) = C(3 + 7 − 1, 7) = C(9, 7) = 36,
N(P 2 ) = (number of solutions with x 2 ≥ 5) = C(3 + 6 − 1, 6) = C(8, 6) = 28,
N(P 3 ) = (number of solutions with x 3 ≥ 7) = C(3 + 4 − 1, 4) = C(6, 4) = 15,
N(P 1 P 2 ) = (number of solutions with x 1 ≥ 4 and x 2 ≥ 5) = C(3 + 2 − 1, 2) =
C(4, 2) = 6,
N(P 1 P 3 ) = (number of solutions with x 1 ≥ 4 and x 3 ≥ 7) = C(3 + 0 − 1, 0) = 1,
N(P 2 P 3 ) = (number of solutions with x 2 ≥ 5 and x 3 ≥ 7) = 0,
N(P 1 P 2 P 3 ) = (number of solutions with x 1 ≥ 4, x 2 ≥ 5, and x 3 ≥ 7) = 0.
Inserting these quantities into the formula for N(P P P ) shows that the number of solutions
1 2 3
with x 1 ≤ 3, x 2 ≤ 4, and x 3 ≤ 6 equals
N(P P P ) = 78 − 36 − 28 − 15 + 6 + 1 + 0 − 0 = 6. ▲
1 2 3