Inclusion-Exclusion

We have talked about the principle of inclusion-exclusion already: \[|A\cup B| = |A|+|B|-|A\cap B|\,.\]
- e.g. This answers: How many number from one to a hundred are divisible by both 6 and 8?
- There's a little more to it than that.
What we have basically done is (1) counted all of \(A\), (2) counted all of \(B\), and (3) realized that we counted \(A\cap B\) twice so removed one.

This and all of the Venn diagrams derived from Wikimedia Commons Venn numbered.svg.
What if we are counting three things? How do we include-exclude then?
- Maybe the Venn diagram will help:
- We could start trying to figure out exactly how many times each piece was counted, but that sounds hard.
- Let's redraw the picture to make it easier:
- Now, what we know already can save us: \[\begin{align*} &\quad |A\cup B\cup C| \\ &= |(A\cup B)\cup C| \\ &= |(A\cup B)| + |C| - |(A\cup B)\cap C|\\ &= |(A\cup B)| + |C| - |(A\cap C)\cup (B\cap C)|\\ &= |(A\cup B)| + |C| - (|A\cap C|+| B\cap C| - |(A\cap C)\cap (B\cap C)|) \\ &= |(A\cup B)| + |C| - (|A\cap C|+| B\cap C| - |A\cap B\cap C|) \\ &= |A|+|B|-|A\cap B| + |C| - (|A\cap C|+| B\cap C| - |A\cap B\cap C|) \\ &= |A|+|B|+ |C|-|A\cap B| - |A\cap C|-|B\cap C| + |A\cap B\cap C| \,. \end{align*}\]
- What we ended up with:
  - Add all of the one-way intersections.
  - Subtract all of the two-way intersections (because they were added too many times).
  - Add all of the three-way intersections (because it was subtracted too many times).
That looks like a pattern that might continue. In fact, it does…
Lemma: For a positive integer \(n\), we have \(\sum_{k=0}^n (-1)^k C(n,k) = 0\).

Proof: Evaluate the binomial theorem with \(x=-1\) and \(y=1\).∎
Theorem: [Principle of Inclusion-Exclusion] Let \(S_1,S_2,\ldots,S_n\) be finite sets. Then, \[\begin{align*} |S_1\cup S_2\cup \cdots\cup S_n| &= \sum_{1\le i \le n} |A_i| \\ &\quad - \sum_{1\le i< j \le n} |A_i\cap A_j|\\ &\quad + \sum_{1\le i< j< k \le n} |A_i\cap A_j\cap A_k| \\ &\quad \vdots \\ &\quad + (-1)^{n+1}|A_1\cap A_1\cap\cdots\cap A_n|\,. \end{align*}\]

Proof: We will show that each element in the union of all of the sets is counted exactly once. First note that an element not in any of the sets will be counted zero times.

Consider any element \(x\in S_1\cup S_2\cup \cdots\cup S_n\). Let \(r\) be the number \(i\) for which \(r\in A_i\).

The element \(x\) will be counted \(C(r,1)\) times in the one-way intersections sum. It will be counted \(C(r,2)\) times in the two-way intersections, \(C(r,3)\) in the three-way intersections, and so on. So, in the expression above, the total number of times the element \(x\) will be counted a total is \[C(r,1)-C(r,2)+C(r,3)-\cdots +(-1)^rC(r,r) = \sum_{k=1}^{r} (-1)^{k+1}C(r,k)\,.\]

We can now use our lemma: \[\begin{align*} \sum_{k=1}^{r} (-1)^{k+1}C(r,k) &= \sum_{k=0}^{r} (-1)^{k+1}C(r,k) - (-1)^{0+1}C(r,0)\\ &= \sum_{k=0}^{r} (-1)^{k+1}C(r,k) - (-1)\cdot 1\\ &= -\sum_{k=0}^{r} (-1)^{k}C(r,k) +1\\ &= 1\,. \end{align*}\] Thus, the inclusion-exclusion formula counts each element of the union exactly once.∎

Positive Integer Equations

As an example, the principle of inclusion-exclusion can be used to answer some questions about solutions in the integers.
How many solutions are there to \(x+y+z=15\) where each variable is a non-negative integer?
- With no further restrictions, this is a combination with repetition problem. How many ways can be distribute the 15 values to the three variables?
- \(C(17,15)=136\).
If we start applying restrictions, we need inclusion-exclusion.
Solutions to \(x+y+z=15\) with \(x\le 3\)?
- We have to exclude the solutions where \(x\ge 4\). That is, solutions to something like \((4+x_0)+y+z=15\) in non-negative integers.
- \(C(17,15)-C(13,11)=58\).
Solutions to \(x+y+z=15\) with \(x\le 3\) and \(y\le 4\)?
- Unrestricted: \(C(17,15)=136\).
- With \(x\ge 4\): \(C(13,11)=78\).
- With \(y\ge 5\): \(C(12,10)=66\).
- With \(x\ge 4\) and \(y\ge 5\): \(C(8,6)=28\).
- We combine and get solutions with \(x\le 3\) and \(y\le 4\): \(136-78-66+28=20\).
Solutions to \(x+y+z=15\) with \(x\le 3\) and \(y\le 4\) and \(z\le 8\)?
- Unrestricted: \(C(17,15)=136\).
- With \(x\ge 4\): \(C(13,11)=78\).
- With \(y\ge 5\): \(C(12,10)=66\).
- With \(z\ge 9\): \(C(8,6)=28\).
- With \(x\ge 4\) and \(y\ge 5\): \(C(8,6)=28\).
- With \(x\ge 4\) and \(z\ge 9\): \(C(4,2)=6\).
- With \(y\ge 5\) and \(z\ge 9\): \(C(3,1)=3\).
- With \(x\ge 4\) and \(y\ge 5\) and \(z\ge 9\): \(0\).
- We combine and get solutions with \(x\le 3\) and \(y\le 4\) and \(z\le 8\): \(78-78-66-28+6+3-0=1\).
The lesson: inclusion-exclusion can be complicated, but at least it's correct.

Derangements

How many ways can \(n\) items be permuted so that none of the items are in their original position? Such permutations are called derangements.
- For example, if we start with 12345, then 23451 is a derangement, but 23415 is not since 5 is in its original position.
- Counting the derangements needs inclusion-exclusion.
Some preliminaries:
- There are \(n!\) permutations of \(n\) elements.
- There are \((n-1)!\) permutations where 1 stays in its original position (and some other elements might, but don't have to).
- … and \((n-1)!\) where 2 stays, and so on.
- There are \((n-2)!\) where any two elements stay in their original position (again with maybe some others staying).
- And so on: \((n-k)!\) ways to permute where a specific \(k\) elements stay in their original positions.
Let's use \(F_S\) to denote the number of permutations where the elements of \(S\) are fixed.
- For example, \(F_{\{1\}} = (n-1)!\) as we said above.
When counting, we can start by counting all of the permutations.
- … and subtract the ones where the sets of size one are fixed.
- … and add the ones where the sets of size two are fixed.
- … and subtract the ones where the sets of size three are fixed.
- … and so on.
- That will be every derangement counted exactly once.
So, the number of derangements is, \[\begin{align*} D_n &= F_\emptyset \\ &\quad\text{} - F_{\{1\}} - F_{\{2\}} -\cdots - F_{\{n\}}\\ &\quad\text{} + F_{\{1,2\}} + F_{\{1,3\}} +\cdots + F_{\{n-1,n\}}\\ &\quad\text{} - F_{\{1,2,3\}} - F_{\{1,2,4\}} -\cdots - F_{\{n-2,n-1,n\}}\\ &\qquad\vdots \\ &\quad\text{} +(-1)^n F_{\{1,2,\ldots,n\}} \\ &= n! \\ &\quad\text{} - (n-1)! - (n-1)! -\cdots - (n-1)!\\ &\quad\text{} + (n-2)! + (n-2)! +\cdots + (n-2)!\\ &\quad\text{} - (n-3)! - (n-3)! -\cdots - (n-3)!\\ &\qquad\vdots \\ &\quad\text{} +(-1)^n 1! \\ &= n! \\ &\quad\text{} - C(n,1)(n-1)! \\ &\quad\text{} + C(n,2)(n-2)!\\ &\quad\text{} - C(n,3)(n-3)!\\ &\qquad\vdots \\ &\quad\text{} +C(n,n)(-1)^n 1! \\ &= n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} +\cdots +(-1)^n \frac{n!}{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}(-1)^k \frac{1}{k!}\,. \end{align*}\]
The lesson: inclusion-exclusion can be complicated, but some times it works out nicer.

Number of Onto Functions

Suppose we have a function \(f:A\rightarrow B\), with \(A\) and \(B\) both finite and \(|A|=m\) and \(|B|=n\).
It is easy enough to count the number of possible functions.
- For each element of \(A\) we select a \(B\) to map it to: \(n^m\) ways.
How many one-to-one functions? (assuming \(n\ge m\))
- Such a function is basically an \(m\)-permutation of the elements of \(B\).
- If we decide on an order for the elements of \(A\), then we need to select \(m\) elements of \(B\) in a particular order to correspond to them (and define the one-to-one function).
- Or looking at it another way: select the \(m\) elements in \(C(n,m)\) ways, then permute them in \(m!\) ways to define the function.
- Either way, we get \(n!/m!\) possibilities.
How many bijections? (assuming \(m=n\))
- As above, we basically just have to order the elements of \(B\) to match them up with elements from \(A\).
- Each ordering is a different bijection.
- There are \(n!\) of them.
How many onto functions? (assuming \(n\le m\))
- This is a lot trickier.
- We need a bunch of inclusion/exclusion.
Let \(F\) be the set of functions \(A\rightarrow B\), and \(F_{S}\) for \(S\subseteq B\) be the set of functions that do not map onto the elements of \(S\).
- In other words, functions \(A\rightarrow B-S\).
- For example with \(A=\{1,2,3,4\}\) and \(B=\{4,5,6\}\), the function \(f(a)=4\) (for all \(a\)) is in \(F_{\emptyset}\), \(F_{\{5\}}\), \(F_{\{6\}}\), and \(F_{\{5,6\}}\).
- Note that every function is in \(F_\emptyset\).
- As with the number of derangements, we can use this notation and inclusion/exclusion to count the number of onto functions (each exactly once).
What is \(|F_{S}|\)?
- Remembering that \(A\rightarrow B-S\) makes it easy.
- If \(|S|=k\), then there are \((n-k)^m\) functions in \(F_{S}\).
- Except that \(|F_{B}|=0\): there are no functions mapping onto the empty set.
For our small example with \(m=4\) and \(n=3\), the number of onto functions is \[\begin{align*} &\quad |F_\emptyset| - |F_{\{4\}}| - |F_{\{5\}}| - |F_{\{6\}}| + |F_{\{4,5\}}| + |F_{\{4,6\}}| + |F_{\{5,6\}}|- |F_{\{4,5,6\}}| \\ &= 3^4 - 3(2^4) + 3(1^4) - 0\\ &= 36\,. \end{align*}\]
We can generalize this for any \(m\) and \(n\). The number of onto functions is: \[\begin{align*} &\quad |F_\emptyset| - C(n,1)|F_{\{a\}}| + C(n,2)|F_{\{a,b\}}| -\cdots+(-1)^{n-1}C(n,n-1)\cdot |F_{B-\{a\}}| \\ &= n^m - C(n,1)(n-1)^m + C(n,2)(n-2)^m- \cdots + (-1)^{n-1}C(n,n-1)\cdot 1^m\\ &= \sum_{k=0}^{n-1} C(n,k)(n-k)^m\,. \end{align*}\]
A much uglier answer than the other types of functions, but we wouldn't have been able to find it without inclusion/exclusion.