\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<k$? 
}
\end{soln*}

\begin{eg}
There are 10 people who give their cars to a valet. How many ways can the valet return the cars so that no one gets back the car they put in? What about at least one people gets their car back? What about at least two?
\end{eg}
\begin{soln*}
\Hide{2in}{
For the frst part, note there are $n!$ total ways the valet an return the cars. There are $10$ sets we are trying to avoid, one for each person. The set $A_i$ is the set of ways to give back their cars so that person $i$ gets the correct car back. Note that $|A_i| = (n-1)!$, since we committed to person $i$ getting their car back. Similar, $|A_i \cap A_j| = (n-2)!$. 

Note that the size of the intersection of some number of these sets depends only on the number of sets being intersected. So, in the inclusion exclusion formula, $\sum_{I\sbs[10]} (-1)^{|I|} \left|\bigcap_{i\in I} A_i\right|$, each part of the sum only depends on $|I|$. Moreover, for a given size of $I$, $i$, there are $10\choose i$ times where a set of that size is in the sum. 

Therefore, the inclusion-exclusion formula tells us the sum is:
\[
\sum_{i=0}^{10} (-1)^i {10 \choose i} (n-i)!
\] 

Try to do the others as an exercise.
}
\end{soln*}

\begin{exc}
Do the above for $n$ people, and then count how many ways there are to return the car so that exactly $1$ person gets their own car back. 
\end{exc}

\begin{eg}
If there are 12 balls, 3 black, 4 red, and 5 white, all indisinguishable apart from color, count the number of ways to line them up so that all the balls of a single color form a single block. 
\end{eg}
\begin{soln*}
\Hide{2in}{
First note that there are clearly ${12 \choose {3,4,5}}$ ways, all together to put line up these balls. Now, we want to avoid $3$ sets: $A_1$ is where all the black balls form a single block, $A_2$ where all reds, and $A_3$ where all white. 

To count $A_1$, ignore the black balls, and just think of white and red balls. There are $9$ total balls, so there are $9\choose 4$ total ways to arrange them. Then there are 11 total positions to put the black block. Thus there are $11\cdot{9\choose 4}$. 

Similarly, $A_2$ is $10\cdot {8\choose 3}$, and $A_3$ is $9\cdot {7\choose 3}$. 

Now, to calculate the intersections, $A_1\cap A_2$ we have both a black block and a red block. So, for this, first decide which block comes first (there are two ways). Then we need to split up white balls and decide how many go before, in the middle of, and after this blocks. There are $7\choose 5$ ways to do this (stars and bars; the white balls are the stars and diving them into 3 categories: before, middle, after). Thus, $|A_1 \cap A_2| = 2{7\choose 5}$. Similar, $|A_1 \cap A_3| = 2{6\choose 4}$, and $|A_2\cap A_3| = 2{5\choose 3}$. 

Now, the the final one, we try to count $A_1\cap A_2\cap A_3$. Here, we know everything comes in blocks, need only arrange those. There are $3!$ ways. 

Thus the total is \[
{12 \choose {3,4,5}} - 11\cdot{9\choose 4} - 10\cdot{8\choose 3} - 9\cdot {7\choose 3} + 2{7\choose 5} + 2{6\choose 4} + 2{5\choose 3} - 3!
\]
}
\end{soln*}


\begin{eg}
There are $n$ work groups, each with a project supervisor, an engineer, and a programmer. The boss decides it's time for a change, so she orders that the groups be mixed aorund so that none of the groups are the same as they were. Their roles however, will be unchanged. How many ways is there to do this?
\end{eg}
\begin{soln*}
\Hide{2in}{
The total number of ways to arrange people as in the above is $\frac{ n!^3 }{n!}$ or $n!^2$. To see the first, we just line up everyone by their roles, and then mod out by rearrangements when they get assigned the same group. 

Now, we are trying to avoid $n$ set. Each set is associated with a group, and that is the set of arrangements where that group remains.There is symmetry; each of these ways is $(n-1)!^2$ by the same aregument as the above, but there re is a particular group that remains. 

Now, we want to calculate the intersection of two of these sets. Well, clearly this is just $(n-2)!^2$ as before. And this is similar for each. 

Well, inclusion/exclusion tells us the formula $\sum_{I\sbs[n]} (-1)^{|I|} \left|\bigcap_{i\in I} A_i\right|$. But, clearly this depends only on the size of $I$. Moreover, for a given size of $I$, say $i$, there are exactly $n\choose i$ number of $I$'s that will appear in the sum with that size. 

This makes the sum tramsformable to 
\[
 \sum_{i=0}^n (-1)^i {n\choose i} (n-i)!^2
\] 
}
\end{soln*}




\end{document}
