CMSC-27100

Discrete Math

Winter Quarter, 2019

Home Lectures Policies

---

Piazza

Lecture 23: Inclusion-Exclusion

\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\left\vert#1\right\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \newcommand{\ceiling}[1]{\lceil#1\rceil} \newcommand{\floor}[1]{\lfloor#1\rfloor} \DeclareMathOperator{\Pr}{Pr} \DeclareMathOperator{\rng}{rng} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\E}{E} \DeclareMathOperator{\V}{V} \DeclareMathOperator{\T}{T} \DeclareMathOperator{\O}{O} \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \)

Warmup

Recall, from all the way back in Lecture 2, the inclusion-exclusion theorem:

Theorem 23.1 (Simple Inclusion-Exclusion). For all finite sets $A$ and $B$, $\size{A \union B} = \size{A} + \size{B} - \size{A \intersect B}$.

Recall the proof: if an element $c \in A \union B$ occurred in $A$ but not $B$, then it was counted once, in the $\size{A}$ term. Likewise, if it occurred in $B$, but not $A$. And if it occurred in both, then we counted $1+1-1$ times, $1$ for $\size{A}$, 1 for $\size{B}$ and $-1$ for $\size{A \intersect B}$. And $1+1-1=1$, so each element $c\in A \union B$ was counted once (in aggregate) by the expression $\size{A} + \size{B} - \size{A\intersect B}$.

Let's warm up with a couple of simple examples, from Rosen:

Example 23.2 In a discrete math class, all of the students are either Math majors, CS majors, or double majoring in Math and CS. There are $25$ students who are majoring in Computer Science (this includes double majors), $13$ who are majoring in Math (again, counting double majors), and $8$ who major in both. How many students are taking the class? Let's let $A$ be the set of CS majors in the class, $B$ be the set of math majors in the class, and $C$ be the set of students in the class. We have:

\begin{align*} \size{C} &= \size{A \union B}\\ &= \size{A} + \size{B} - \size{A \intersect B}\\ &= 25 + 13 - 8\\ &= 30 \end{align*}

I guess this isn't our class.

Example 23.3 How many positive integers less than or equal to $1000$ are divisible by $6$ or $8$?

A first observation is that the number of positive integers less than or equal to $n$, i.e., integers in the set $\set{1,2,\ldots,n}$ which are divisible by $d$ is $\floor{n/d}$.

Let $A$ be the set of positive integers less than or equal to $1000$ which are divisible by $6$, and $B$ be the set of positive integers less than or equal to $1000$ which are divisible by $8$. A number is divisible by $a$ and $b$ iff it is divisible by their least common multiple, $\lcm(a,b)$. A simple formula for the $\lcm$ is

\begin{align*} \lcm(a,b) = {a \mult b \over \gcd(a,b)}, \end{align*}

which if we think about it at the level of multiplicities of prime factors, is itself an application of the inclusion-exclusion principle!

Anyway, in our case, $\lcm(6,8) = {6 \mult 8 \over \gcd(6,8)} = {48 \over 2} = 24$. So,

\begin{align*} \size{A \union B} &= \size{A} + \size{B} - \size{A \intersect B}\\ &= \floor{1000/6} + \floor{1000/8} - \floor{1000/24}\\ &= 166 + 125 - 41\\ &= 250 \end{align*}

Inclusion-Exclusion, it's not just for $2$ sets

Let's assume we have three sets, $A$, $B$, and $C$. If we want to count $A \union B \union C$, we can first apply the inclusion-exclusion principle to $A$ and $B \union C$, obtaining:

\begin{align*} \size{A \union B \union C} &= \size{A} + \size{B \union C} - \size{A \intersect (B \union C)}\\ &= \size{A} + \size{B \union C} - \size{(A \intersect B) \union (A \intersect C)} \end{align*}

We next compute

\begin{align*} \size{(A \intersect B) \union (A \intersect C)} &= \size{A \intersect B} + \size{A \intersect C} - \size{(A \intersect B) \intersect (A \intersect C)}\\ &= \size{A \intersect B} + \size{A \intersect C} - \size{A \intersect B \intersect C} \end{align*}

Substituting into the the above, we now have

\begin{align*} \size{A \union B \union C} &= \size{A} + \size{B \union C} + \size{(A \intersect B) \union (A \intersect C)}\\ &= \size{A} + (\size{B} + \size{C} - \size{B \intersect C}) - (\size{A \intersect B} + \size{A \intersect C} - \size{A \intersect B \intersect C})\\ &= \size{A} + \size{B} + \size{C} - \size{A \intersect B} - \size{A \intersect C} - \size{B \intersect C} + \size{A \intersect B \intersect C} \end{align*}

Thus

Theorem 23.4 (Inclusion-Exclusion for $3$ Sets) For finite sets $A$, $B$, and $C$,

\begin{align*} \size{A \union B \union C} =\;&\size{A} + \size{B} + \size{C}\\ &- \size{A \intersect B} - \size{A \intersect C} - \size{B \intersect C}\\ &+ \size{A \intersect B \intersect C} \end{align*}

A simple mnemonic for Theorem 23.4 is that we add all of the ways an element can occur in each of the sets taken singly, subtract off all the ways it can occur in sets taken two at a time, and add all of the ways it can occur in sets taken three at a time.

Example 23.5 (Again, from Rosen) A total of $1232$ students have taken Spanish, $879$ have taken French, and $114$ have taken Russian. Further $103$ have taken both Spanish and French, $23$ have taken both Spanish and Russian, and $14$ have taken both French and Russian. If $2092$ students have taken at least one of Spanish, French, and Russian, how many have taken all three?

We use the inclusion-exclusion theorem for 3 sets, with $A$ being the set of student who have taken Spanish, $B$ the set of students who have taken French, and $C$ the set of students who have taken Russian. We have

\begin{align*} \size{A \union B \union C} &= \size{A} + \size{B} + \size{C} - \size{A \intersect B} - \size{A \intersect C} - \size{B \intersect C} + \size{A \intersect B \intersect C}\\ 2092 &= 1232 + 879 + 114 - 103 - 23 - 14 + \size{A \intersect B \intersect C}\\ 2092 &= 2085 + \size{A \intersect B \intersect C}\\ \end{align*}

Thus,

\begin{align*} \size{A \intersect B \intersect C} &= 7 \end{align*}

Of course, we might expect that inclusion-exclusion isn't just for three sets, either, but we don't want to pursue quite the same proof as before.

Theorem 23.8 (Inclusion-Exclusion) Let $A = \set{A_1,A_2,\ldots,A_n}$ be a set of finite sets finite sets. Then

\begin{equation*} \size{\ixUnion_{i=1}^n A_i} = \sum_{P \in \mathcal{P}(A)} (-1)^{\size{P}+1} \size{\ixIntersect_{A_i \in P} A_i} \end{equation*}

Note that the $P=\emptyset$ term contributes $0$ to the sum, as $\size{\emptyset} = 0$, and so it is usually elided.

Proof We have to show that each element $x \in \ixUnion_{i=1}^n A_i$ is counted once. To that end, assume that $x$ occurs in $r$ of the $A_i$'s. We'll count $x$ $r \choose 1$ times as a result of $1$ element terms $P$, we'll count $-{r \choose 2}$ as the result of $2$ element terms, and in general $(-1)^{k+1} {r \choose k}$ times as a result of $k$ element terms $P$. Thus, $x$ is counted $\sum_{i=1}^k (-1)^{k+1} {r \choose k}$ times.

But here's the punchline. Recall our earlier application of the binomial theorem

\begin{align*} 0 &= (1-1)^r\\ &= \sum_{i=0}^r (-1)^k {r \choose k}\\ &= (-1)^0 {r \choose 0} + \sum_{i=1}^r (-1)^k {r \choose k} \\ &= 1 + \sum_{i=1}^r (-1)^k {r \choose k}\\ \end{align*} Rearranging the equation, we have \begin{align*} 1 &= -\sum_{i=1}^r (-1)^k {r \choose k}\\ &= \sum_{i=1}^r (-1)^{k+1} {r \choose k}\\ \end{align*}

So, in aggregate, $x$ was counted just once, as required.

$\Box$ Theorem 23.8

In practice, the inclusion-exclusion theorem takes a simple, beautiful, recurrent form. For example, consider the $n=4$ case

\begin{align*} \size{A \union B \union C \union D} =\;&\size{A} + \size{B} + \size{C} + \size{D} \\ &- \size{A \intersect B} - \size{A \intersect C} - \size {A \intersect D} - \size{B \intersect C} - \size{B \intersect D} - \size{C \intersect D}\\ &+ \size{A \intersect B \intersect C} + \size{A \intersect B \intersect D} + \size{A \intersect C \intersect D} + \size{B \intersect C \intersect D}\\ &- \size{A \intersect B \intersect C \intersect D} \end{align*}

We have a total of fifteen terms (we'd have sixteen, but for $\emptyset$), and the number of terms that involve the intersection of $k$ sets is $n \choose k$, with the signs alternating with each group.

---

© 2016–2019 Stuart A. Kurtz
Last modified: March 13, 2019