I don't see how the binomial theorem relates to the principle of inclusion and exclusion?

Question

I'm learning discrete maths as a hobby at the moment and I got stuck when the tutor starting relating the binomial theorem to the principles of inclusion and exclusion. The video I was watching is https://www.youtube.com/watch?v=GS7dIWA6Hpo&list=PLDDGPdw7e6Aj0amDsYInT_8p6xTSTGEi2&index=6 and the question starts at (14.25).

I understand the binomial theorem, and I see how combinatorics is used to calculate the coefficients. I've seen multiple online tutorials where the binomial theorem has been used to describe the nature of inclusion and exclusion and I just don't understand.

Exclusion/Inclusion formula:

|A1 ∪ A2 ∪ A3| = |A1| + |A2| + |A3| − |A1 ∩ A2| − |A1 ∩ A3| − |A2 ∩ A3| + |A1 ∩ A2 ∩ A3|

This makes sense because we have to exclude the cases where elements are counted twice (drawing venn diagrams helped me understand this).

Binomial Theorem:

$(A+B)^n = \sum_{k=0}^n {n\choose{k}} A^{n-k} B^{k}$

This formula makes sense to me again, but can someone please explain it to me in simple terms how the binomial theorem is even related to inclusion/exclusion?

I've also seen proofs where examples substitute the x = 1 and y = -1 and we end up getting the binomial expansion to equal 0. I just don't see how we can relate that to PIE.

Please help.

EDIT:

This part of the video is what confuses me (17.27). I don't get the ((1) + (-1)) part, what is he trying to show from that?

Answer 1

Referring to the example of finding the number of numbers not divisible by $2,3,5$, the inclusion-exclusion principle is: $$\bar{N}=N-N(2)-N(3)-N(5)+N(2,3)+N(2,5)+N(3,5)+N(2,3,5)=\\ 100-50-33-20+16+10+6-3=26.$$ In this problem let's see how many times the central region (which contains the numbers divisible by $2,3,5$ simultaneously) is counted. The teacher calls this region by $x$. By $r$ the teacher considers the number of numbers (i.e. $2,3,5$), that is $r=3$. So: $${r\choose 0}={3\choose 0}=1 \ \ \ \text{in} \ N \ \\ \text{(i.e. in the whole universal set)};\\ {r\choose 1}={3\choose 1}=3 \ \ \text{in} \ N(2)+N(3)+N(4) \ \\ \text{(i.e. in each of the three regions)};\\ {r\choose 2}={3\choose 2}=3 \ \ \text{in} \ N(2,3)+N(2,5)+N(3,5) \ \\ \text{(i.e. in each of the pairwise intersections of the three regions)};\\ {r\choose 3}={3\choose 3}=1 \ \ \text{in} \ N(2,3,5) \ \\ \text{(i.e. in the common intersection of the three regions)}.$$ Now the inclusion-exclusion formula for the number of times the region $x$ is counted looks like: $$\begin{align}x&={r\choose 0}-{r\choose 1}+{r\choose 2}-{r\choose 3}=\\ &={3\choose 0}-{3\choose 1}+{3\choose 2}-{3\choose 3}=\color{red}{1-3+3-1=0}=\\ &={3\choose 0}\cdot 1^3\cdot (-1)^0+{3\choose 1}\cdot 1^2\cdot (-1)^1+{3\choose 2}\cdot 1^1\cdot (-1)^2+{3\choose 3}\cdot 1^0\cdot (-1)^3=\\ &=(1-1)^3=0.\end{align}$$ The aim of the teacher for using the binomial expansion of $(1-1)^3$ is to explain in an easy way that the sum is zero, $\color{red}{\text{rather than calculating each term and adding}}$.

Answer 2

We start out by adding up $|A_1|+|A_2|+\dots+|A_n|$. Then we say, "Wait any element in to subsets have been counted twice; we have to subtract those." So we subtract $|A_1\cap A_2|+|A_1\cap A_3|+\dots+A_{n-1}\cap A_n|$ But wait. Any element in $3$ subsets has been added $3$ times and subtracted ${3\choose2}$ times, so it hasn't been counted at all, so we have to add them back in. But then an element of $4$ subsets has been counted ${4\choose1}-{4\choose2}+{4\choose3}=2$ times so we have to subtract those. Do you see where this is going?

Answer 3

The explanation goes back to the origins of Boolean algebra. Define a "Boolean" variable $\, x \,$ as one where $\, x^2 = x. \,$ For these variables $\, 1-x \,$ denotes logical negation and $\, xy \,$ denotes logical and. Finally, by De Morgan's laws, $\ 1-(1-x)(1-y) \,$ denotes logical or.

In the context of subsets of a univeral set $\, U, \,$ any subset $\, A \,$ of $\, U \,$ is identified by its indicator function $\, A(x) \,$ which is Boolean valued. Now the number of elements of $\, A \,$ is $\, |A| = \sum A(x) .\,$ Next, the indicator function of $\, A \cap B \,$ is $\, A(x)B(x), \,$ of complement of $\, A \,$ is $\, 1-A(x), \,$ and of $\, A \cup B \,$ is $\, 1-(1-A(x))(1-B(x)). \,$

Given any subsets $\, A_1, A_2, \dots, A_n \,$ and their indicator functions $\, A_1(x), A_2(x), \dots, A_n(x), \,$ we can write $\, 1-(1-A_1(x))(1-A_2(x)) = A_1(x) + A_2(x) - A_1(x)A_2(x) \,$ which implies $\, |A_1 \cap A_2| = |A_1| + |A_2| - |A_1 \cup A_2|. \,$ This obviously generalizes to any finite number of subsets and is one form of the PIE.

Now suppose that $\,A = A_1=A_2=\dots=A_n.\,$ Use the binomial theorem to get $$ (1-A(x))^n = \sum_{k=0}^n {n\choose{k}} (-1)^k A(x)^{k}$$ but since $\,A(x)\,$ and $\,1-A(x)\,$ are Boolean valued and if also $\,n>0\,$ this simplifies to $$ 1-A(x) = (1-A(x))^n = 1 + A(x)\sum_{k=1}^n {n\choose{k}} (-1)^k.$$ If now $\,A(x)\ne 0\,$ then this implies that $$ -1 = \sum_{k=1}^n {n\choose{k}} (-1)^k \qquad \text{ and } \qquad 0 = \sum_{k=0}^n {n\choose{k}} (-1)^k . $$

Answer 4

In Goulden-Jackson approach, the PIE looks like :

$N(x)=E(x+1)$

For the considered example we have the "exact generating function"

$E(x) = 26 + 48x + 32x^2 + 3x^3$

since we have 26 numbers that are not divisible with 2 or 3 or 5, 48 numbers that are divisible with exactly one of {2,3, 5}, 32 numbers divisible with exactly two of them and three numbers divisible with 2 and 3 and 5.

$N(x) = 100 + 103x + 32x^2 + 3x^3$

is the "at least" generating function for numbers that are divisible with at least zero, one, two or three of {2,3,5}

We have to obtain the 26 knowing 100, 103 = 50 + 33 + 20, 32 = 16 + 6 + 10 and 3

Well, by Goulden-Jackson, $26 = E(0) = N(-1) = 100-103+32-3$

One may see that the binomial coefficients occur in $E(x+1)$.