Problem 19
Use the Binomial Theorem to prove the following identities…
(a)
�n � n � j=0 j
= 2n (b)
�n k=1
(−1)k
� n � k
= −1
The General Inclusion-Exclusion Principle
Inclusion-Exclusion on 3 sets
|A∪B| = |A|+|B|−|A∩B|
|A∪B ∪C| = |A|+|B|+|C|−|A∩B|−|A∩C|−|B ∩C|+|A∩B ∩C|
Problem 20
How many permutations of the 26 letters of the alphabet do not contain any of the strings “fish”, “rat” or “bird”?
Inclusion-Exclusion on n sets
|A1 ∪A2 ∪…∪An|
= |A1|+|A2|+…|An|
−|A1 ∩A2|−|A1 ∩A3|−…−|An−1 ∩An|
+|A1 ∩A2 ∩A3|+|A1 ∩A2 ∩A4|+…+|An−2 ∩An−1 ∩An|
−…+(−1)n+1|A1 ∩A2 ∩…∩An|
�n �
= (−1)k+1 |Ai1 ∩…∩Aik|
k =1 1≤i1 <···