\documentclass{article}
\input{preamble.tex}
\title{Day 23}
\date{June 25, 2012}
\def\Display{\@empty}
\newcommand{\Hide}[2]{\ifx \Display\undefined \strut \\ \vspace{#1} \\ \strut \else {\color{blue} #2} \fi }
\begin{document}
\maketitle
\section{Inclusion-Exclusion}
Today we will learn another counting method called Inclusion/Exclusion. The idea with this method is we want to count a set of elements, and avoid counting particular subsets. It may be hard to do this directly (we will see examples) but if it is easy to count the larger set and the smaller subsets we are avoiding, this method is appropriate.
\subsection{Early Exploration}
We have already seen an easy case of this technique, and that is when we could a set $A\sbs \Omega$ by counting $\Omega$ and $A^c$ and then taking the difference $|\Omega|-|A^c|$, which gives us a count for $A$. Therefore, inclusion/exclusion is quite easy when we are just trying to avoid counting one set.
\begin{eg}
Count the number of binary sequences of length 10 that do not begin with a $1$.
\begin{soln*}
\Hide{1in}{
Clearly, there are $2^{10}$ total binary strings. Now we exclude the strings that begin with a $1$. There are $2^9$ of these. Thus there are $2^{10} - 2^9$ total binary strings that do not begin with a $1$. (Aside: Another way to count would have been to just count the number of strings that begin with a $0$. So this could be a combinatory proof that $2^{10} - 2^9 = 2^9$.)
}
\end{soln*}
\end{eg}
The next question is, what if we want to count $\Omega$ but exclude two sets $A$ and $B$. Well, of course, this is the same as exluding $A\cup B$. But, how do we do this easily? It would be nice if we could just subtract $|A\cup B|$, but that quantity might be difficult to calculate directly. $A$ and $B$ might be easier to count, but $|A\cup B| \neq |A| + |B|$ in general. The left hand side is generally larger as there may be elements in $A\cap B$ that we are counting twice.
But, one can see that $|A\cup B| = |A| + |B| - |A \cap B|$, just by the simple rule of differences as above. This means that \[ |\Omega \minus (A\cup B)| = |\Omega| - |A| - |B| + |A\cap B| \]
\begin{eg}
Count the number of binary strings of length $3$ that do not contain consecutive $1$'s.
\end{eg}
\begin{soln*}
\Hide{1in}{
There are $2^3$ total binary strings. We are trying to exclude two sets: $A$, the set of binary strings that begin $11$ and $B$, the set of binary strings that end in $11$. If we exclude these two sets, we are left with the binary strings that do not contian two consecutive ones.
It is easy to count that the size of $A$ and $B$ is $2$. Then we need to count $|A\cap B|$. This is binary strings that both begin and end $11$. There is only one string like this: $111$. Thus the total is
\[
2^3 - 2 -2 + 1 = 5
\]
}
\end{soln*}
\subsection{Formal Statement}
\begin{thm}[Inclusion-Exclusion]
If $\Omega$ is a set, and $A_1, A_2, \ldots, A_n$ are sets, then
\[
|\Omega\minus(A_1\cup A_2\cup\cdots\cup A_n)| = \sum_{I\sbs[n]} (-1)^{|I|} \left|\bigcap_{i\in I} A_i\right|
\]
(Note: in the sum, when $I=\emptyset$, the intersection is defined to be $\Omega$.)
\end{thm}
\subsection{Examples}
\begin{eg}
Find the number of positive integer solutions to
\[
x_1 + x_2 + x_3 = 10
\]
Where $x_1\leq 4$, $x_2 \leq 4$ and $x_3\leq 4$.
\end{eg}
\begin{soln*}
\Hide{1.5in}{
Here $\Omega$ is the set of positive integer solutions to the above. We are trying to avoid three sets: $A_i$ is the set of all positive integer solutions to the above, with the restriction that $x_i \leq 4$.
Here, to count $\Omega$ we simply use simply stars and bars with $10$ stars and $2$ bars. So it has ${12 \choose 2}$ member. Note that $|A_1|=|A_2|=|A_3|$. So we will just count $A_1$. To do this, we do stars and bars, but before we imagine we have already given $5$ stars to $x_1$. Thus, we get the count is $7\choose 2$.
Now, we need to calculate the intersection set sizes. By symmetry, we have $|A_1\cap A_2| = |A_2 \cap A_3| = |A_1 \cap A_3|$. So we will calculate $|A_1 \cap A_2|$. This is also just stars and bars, where we give $5$ to $x_1$ and $x_2$. This means there are $0$ more stars to assign, so this makes only $1$ way.
Now we need to calculate the other intersection set sizes. Namely $|A_1\cap A_2 \cap A_3|$. But, this is $0$ since it is impossible to violate all $3$.
Thus, by inclusion-exclusion, our count is:
\[
{12\choose 2} - 3
\]
}
\end{soln*}
\begin{eg}
Count the number of ways to put $n$ people into $k$ distinguishable rooms such that none of the rooms is empty.
\end{eg}
\begin{soln*}
\Hide{2in}{
There are $n^k$ ways to put people into the rooms, as there are $k$ posssible decisions you need to make for each person. Now, you are trying to avoid $k$ sets, $A_1$, $A_2$, \ldots, $A_k$, where $A_i$ is the set of ways to do this while keeping the $i$th room empty.
Note that to count $A_i$, it's the same as putting the people in $k-1$ rooms, as I'm committing to the $i$th room being empty. So, $|A_i| = n^{k-1}$.
Similarly, to count $A_i\cap A_j$ ($i\neq j$), we just put the people in $k-2$ rooms; we are comitting to the $i$th and $j$th room being empty. So $|A_i \cap A_j| = n^{k-2}$.
This pattern continues. By the inclusion/exclusion formula, the total is $\sum_{I\sbs[k]} (-1)^{|I|} \left|\bigcap_{i\in I} A_i\right|$. Note that the sum only depends on the size of $I$. So, in reality we could write it as the some from $i=0$ to $i=k$. The number of times a given size $i$ of a subset of $[k]$ is counted in the sum is $k\choose i$ times.
This makes the total $\sum_{i=0}^k (-1)^i {k\choose i} (k-i)^n$.
Aside: What should the answer be if $n < k$? Therefore, what is the above sum when $n