Problem 7.1.
How many integers between 1 and 881 inclusively are divisible by 3 or 5?
Chapter 7 Principle of Inclusion and Exclusion
We now introduce a concept known as the Principal of Inclusion and Exclusion. Recall Theorem 1.14, which states that if \(A\) and \(B\) are sets, then
\begin{equation*}
{|A\cup B| = |A| + |B| - |A\cap B|.}
\end{equation*}
But what do we do if we have more than two sets? Let’s first examine the situation with three sets.
Problem 7.2.
If \(A, B\text{,}\) and \(C\) are sets, then find a formula in the same vein as Theorem 1.14 for \(|A\cup B\cup C|\text{.}\)
The upshot is that we add “singles” subtract “doubles” and add “triples”.
Problem 7.3.
In the Natteranian township, 750 of the residents have a smart phone, 620 have a laptop computer, 480 have a desktop computer, 420 have both a laptop and a smart phone, 390 have both a smart phone and a desktop, 212 have both a laptop and a desktop computer and 164 have all three items.
-
How many residents have at least one of the three items?
-
How many residents do not have desktop computer?
-
How many residents have a smart phone or a laptop?
-
How many have a smart phone or a laptop but not a desktop?
We can generalize to any finite number of sets.
Theorem 7.4. Principal of Inclusion and Exclusion.
The number of elements in the union of finite sets \(A_1, A_2, \dots, A_n\) is
\begin{equation*}
{{|A_1\cup\cdots \cup A_n|=\sum_i |A_i| - \sum_{i\lt j} |A_i\cap A_j| + \sum_{i\lt j\lt k}|A_i\cap A_j\cap A_k| -\cdots +(-1)^{n+1}|A_1\cap A_2 \cdots \cap A_n|.}}
\end{equation*}
Problem 7.5.
How many nonnegative integer solutions does the equation \(x_1+x_2+x_3+x_4 = 25\) have such that \(x_1 \lt 7\text{,}\) \(x_2 \lt 5\text{,}\) and \(x_4\lt 8\text{?}\)
We now discuss one important application of the Principle of Inclusion and Exclusion. Formally, a derangement is a permutation \(w:[n]\to [n]\) such that \(w(i)\neq i\) for all \(1\leq i\leq n\) (i.e., \(w\) has no fixed points). That is, a derangement is a special rearrangement of objects such that none is in its original spot.
Problem 7.6.
How many derangements of CAT are there?
Let \(d_n\) denote the number of derangements of \([n]\text{.}\) We set \(d_0:=1\text{.}\)
Problem 7.7.
For \(1\leq i\leq n\text{,}\) let \(F_i\) be the set of permutations that fix \(i\text{.}\)
-
Explain why\begin{equation*} d_n=|F^c_1\cap \cdots \cap F^c_n|\text{.} \end{equation*}
-
Explain why\begin{equation*} d_n=n!-\sum_i |F_i|+\sum_{i\lt j} |F_i\cap F_j|-\sum_{i\lt j\lt k}|F_i\cap F_j\cap F_k|+\cdots +(-1)^n|F_1\cap\cdots \cap F_n|\text{.} \end{equation*}
-
Explain why the number of derangements of \([n]\) is\begin{equation*} {d_n=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +(-1)^n\frac{1}{n!} \right)=n!\sum_{k=0}^n\frac{(-1)^k}{k!}.} \end{equation*}
Problem 7.8.
Using the previous problem, verify that we got the right answer to Problem 7.6.
Problem 7.9.
If 7 hats are left at the hat-check window, in how many ways can they be returned so that no one gets the correct hat?
Now, just for funsies… from second semester calculus, we know
\begin{equation*}
e^x=\sum_{k=0}^{\infty}\frac{x^k}{k!}\text{,}
\end{equation*}
which implies that
\begin{equation*}
e^{-1}=\sum_{k=0}^{\infty}\frac{(-1)^k}{k!}\text{.}
\end{equation*}
Using Part (c) of Problem 7.7, we see that
\begin{equation*}
\lim_{n\to \infty}\frac{d_n}{n!}=\lim_{n\to\infty}\sum_{k=0}^n\frac{(-1)^k}{k!}=\frac{1}{e}\approx 0.367879\text{.}
\end{equation*}
In other words, when \(n\) is large, the probability of selecting a derangement at random from the collection of permutations of \(n\) is approximately \(1/e\text{.}\) As \(n\) increases, the approximation improves. Boom.
