Hi, I am Emon and I am back this time to provide you with some ideas regarding the **''Inclusion and Exclusion Principle"**, which is a really important topic that we should learn for olympiads.

The **I****nclusion-Exclusion Principle** is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets, which is given by the formula

$$\left|A\cup B\right| = \left|A\right|+\left|B\right| - \left|A\cap B\right|.$$

where $A$ and $B$ are two finite sets and $|X|:=$ cardinality of set $X$, $i.e.$ the number of elements present in the set $X$.

The proof of this formula can be understood directly from the above venn diagram.

*Additional Note (though a bit out of context).* Let $\mathcal{S}$ be a discrete sample space. Then, if $A, B\subset \mathcal{S}$ are two events, then we may write

$$\mathbb{P}(A\cup B)=\mathbb{P}(A)+\mathbb{P}(B)-\mathbb{P}(A\cap B),$$ which is equivalent to the previous formula $$|A\cup B|=|A|+|B|-|A\cap B|.$$

Similarly, for $3$ finite sets, we will have,

$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|.$$

**Inclusion-Exclusion Principle**.

**Formula.**If $A_1, A_2, \ldots, A_n$ be $n$ finite sets. Then, we can write

**Derangements**

**Example 1.**A postman has to deliver $n$ letters in $n$ houses. Suppose the letter $\ell_i$ should be delivered at house $h_i$. But, the postman, being a naughty one, decides to deliver the letters in such a way that $\ell_i$ is not delivered to $h_i$ for all $i$. In how many ways can he do so?

**Example 2.**Suppose that a professor gave a test to $n$ students $\mathcal{S}_1, \mathcal{S}_2, \ldots, \mathcal{S}_n$ and wants to let them grade each other's tests. Of course, no student should grade their own test. How many ways could the professor hand the tests back to the students for grading, such that no student received their own test back?

**Formula (Derangement).**The number of derangements of an $n$ element set, $D_n$ or $!n$, is given by the formula

**PIE**. So, at first, we consider the all possible arrangements of the whole sequence, which is given by $n!$. Next, we must remove all the arrangements in which each element appears in its original position, $i.e.$ we have to subtract $\binom{n}{1}(n-1)!$. Again, we have to add back the permutations in which each set of two elements stay in their original positions, as we subtracted them twice, so we must add $\binom{n}{2}(n-2)!$ and so on. Thus, we have,

*Note.*The probability of a derangement is $\displaystyle\frac{1}{e}.$

**Problem $1$ (IMO $1987/1$).**Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $$\sum_{k=0}^nk p_n(k)=n!.$$

**Solution.**Firstly, observe that $\displaystyle p_n(k)=\binom{n}{k}(n-k)!\sum_{i=0}^{n-k} \frac{(-1)^i}{i!}$, $i.e.$ $p_n(k)=D_{n-k}$ where $D_i:=$ the number of derangements of $\{1, 2, \ldots, i\}$. Now, observe that, $$\begin{aligned} \frac{p_n(k)}{p_{n-1}(k-1)} &= \frac{n}{k}\\ \iff p_n(k) &= \frac{n}{k}p_{n-1}(k-1)\\ \implies \sum_{k=0}^nkp_n(k) &= n\sum_{k=1}^np_{n-1}(k-1)\\ &= n(n-1)! = n!,\text{ as desired.} \end{aligned}$$

**PIE**, then maybe go through this, this, this, this and this. Hope to see you soon.

**Emon.**

## Comments

## Post a Comment