LEC DMAT 12

Principle of inclusion and exclusion

Theorem 210.1(Principle of inclusion and exclusion).

Let $X$ be a finite universe. $A_1,A_2,\dots ,A_n\subseteq X$. For $I\subseteq [n]$, define $A_I:={\bigcap }_{i\in I}{A}_i$, $A_{\varnothing }:=X$.

$$\left|X\setminus \bigcup _{i=1}^n{A}_i\right|=\sum _{I\subseteq [n]}(-1{)}^{|I|}|A_I|.$$

Proof.

Let $x\in X$.
Contribution of $x$ to the LHS:

• $x\in \bigcup A_i$ $⟹$ $x$ contributes 0
• $x\notin \bigcup A_i$ $⟹$ $x$ contributes 1.

Let $J$ be the largest index set such that that $x\in A_J$ (observe that such a set is unique). Let $j=|J|$. Then, contribution of $x$ to the RHS is equal to

$$\sum _{I\subseteq J}(-1{)}^{|I|}=\sum _{i=0}^j(-1{)}^i\left(\genfrac{}{}{0ex}{}{j}{i}\right)=\{\begin{array}{ll}(1-1{)}^j=0& j>0\left(⟺x\in \bigcup A_i\right)\\ 1& j=0\left(⟺x\notin \bigcup A_i\right).\end{array}$$ □

Number of surjections

Let $X=[k{]}^{[n]}$ be the set of all functions from $[n]\to [k]$.
Let $A_i$ be the set of all functions from $[n]$ to $[k]$ such that $i\in [k]$ is not covered.
Then, the number of surjections is equal to

$$\begin{array}{rl}\left|X\setminus \bigcup _{i=1}^k{A}_i\right|& =\sum _{I\subseteq [k]}(-1{)}^{|I|}|A_I|\\ & =\sum _{i=0}^k(-1{)}^i(\genfrac{}{}{0ex}{}{k}{i})(k-i{)}^n\\ & =n!S(m,n).\end{array}$$

Derangements

Let $X$ be the set of all permutations on $[n]$. Let $A_i\subset X$ be the set of all permutations which map $i$ to $i$. Then, the number of derangements is equal to

$$\begin{array}{rl}& \\ \left|X\setminus \bigcup _{i=1}^n{A}_i\right|& =\sum _{I\subseteq [n]}(-1{)}^{|I|}|A_I|\\ & =\sum _{i=0}^n(-1{)}^n(\genfrac{}{}{0ex}{}{n}{i})(n-i)!\\ & =n!\sum _{i=0}^n\frac{(-1{)}^n}{i!}.\end{array}$$

The Euler $\varphi$ function

Let $X=[n]$. Let $p_1,p_2,\dots ,p_k$ be distinct prime factors of $n$. The “bad elements” are the multiples of the $p_i$s. Let $A_i=\{x\in X:p_i\text{ divides }x\}$.

$$\begin{array}{rl}|A_i|& =\frac{n}{p_i}.\\ |A_I|& =\frac{n}{{\prod }_{i\in I}{p}_i}\text{ when }I\ne \varnothing .\\ |A_{\varnothing }|& \equiv n.\end{array}$$ $$\begin{array}{rl}\varphi (n)& =\left|X\setminus \bigcup _{i=1}^k{A}_i\right|\\ & =n\sum _{I\subseteq [k]}(-1{)}^{|I|}\frac{1}{{\prod }_{i\in I}{p}_i}\\ & =n\prod _{i=1}^n\left(1-\frac{1}{p_i}\right).\end{array}$$

Linear algebraic formulation

Let $X=[n]$. Consider the collection $V=\{f:\mathcal{P}(X)\to \mathbb{R}\}$. This forms a $2^n$ dimensional vector space over $\mathbb{R}$. Then, for $f,g\in V$, the following two statements are equivalent.

$$\begin{array}{rlr}& 1.g(I)=\sum _{J\supseteq I}f(J)& \forall I\in \mathcal{P}(X),\\ & 2.f(I)=\sum _{J\supseteq I}(-1{)}^{|J\setminus I|}g(J)& \forall I\in \mathcal{P}(X).\end{array}$$

Think of it this way: Let the elements of $X$ be different “properties” of elements of another set $S$. An element of $S$ can have any number of properties $x\in X$. For $I\subset X$, Let $A_I$ be the set of all $s\in S$ which have each property $i\in I$ (Note that all the properties of $s\in A_I$ may be a super set of $I$). Think of $g$ as counting the number of elements in $S$ which have properties $I$ ($g(I)\equiv |A_I|$), and $f$ as counting the number of elements in $G$ which have exactly the properties $I$ ($f(I)\equiv |A_I\setminus {\bigcup }_{i\in \overline{I}}{A}_i|$).

Proof.

$(1⟹2)$

$$\begin{array}{rlr}\sum _{J\supseteq I}(-1{)}^{|J\setminus I|}g(J)& =\sum _{J\supseteq I}(-1{)}^{|J\setminus I|}\left(\sum _{K\supseteq J}f(K)\right)& \\ & =\sum _{K\supseteq I}f(K)\sum _{K\supseteq J\supseteq I}(-1{)}^{|J\setminus I|}& \\ & =f(I)+\sum _{K\supset I}f(K)\underset{=0}{\underbrace{\sum _{K\supseteq J\supseteq I}(-1{)}^{|J\setminus I|}}}& (\ast )\\ & =f(I).& \end{array}$$

$(\ast )$ is true since for any finite set, the number of subsets of odd cardinality is equal to the number of subsets of even cardinality.

$(2⟹1)$

$$\begin{array}{rl}\sum _{J\supseteq I}f(J)& =\sum _{J\supseteq I}\sum _{K\supseteq J}(-1{)}^{|K\setminus J|}g(K)\\ & =\sum _{K\supseteq I}g(K)\sum _{K\supseteq J\supseteq I}(-1{)}^{|K\setminus J|}\\ & =g(I)+\sum _{K\supset I}g(K)\underset{=0}{\underbrace{\sum _{K\supseteq J\supseteq I}(-1{)}^{|K\setminus J|}}}\\ & =g(I).\end{array}$$ □