Skip to main content

Including and Excluding

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 Inclusion-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|.$$

The proof of this is also direct from the venn diagram. 

Now, let's state the original, generalised version of the Inclusion-Exclusion Principle.

Formula. If $A_1, A_2, \ldots, A_n$ be $n$ finite sets. Then, we can write
$$|A_1\cup A_2\cup \cdots \cup A_n|=\sum_{i=1}^n|A_i| - \sum_{i<j}|A_i\cap A_j|+\cdots+(-1)^{n+1}|A_1\cap A_2\cap \cdots \cap A_n|.$$

$Proof.$ You may look into the proofs here or here. 

Derangements
Consider the following 2 examples.

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?

The above problems are the typical examples of derangements. A derangement can be defined as the permuatation(s) of the elements of a set such that no element appear in it's original position, or in other words, have no fixed points.

Formula (Derangement). The number of derangements of an $n$ element set, $D_n$ or $!n$, is given by the formula
$$D_n = n!\sum_{k=0}^n\frac{(-1)^k}{k!}.$$
$Proof.$ We can prove this using the 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, 
$$D_n=n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!-\cdots + (-1)^n\binom{n}{n}(n-n)!.$$
But, since $\displaystyle \binom{n}{k}(n-k)!=\frac{n!}{(n-k)!k!}(n-k)!=\frac{n!}{k!}$, we have, 
$$\begin{aligned} D_n &=n!-\frac{n!}{1!}+\frac{n!}{2!}-\cdots+(-1)^n\left(\frac{n!}{n!}\right) \\ &= n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\cdots+(-1)^n\left(\frac{1}{n!}\right)\right) \\  &= n!\sum_{k=0}^n\frac{(-1)^k}{k!},\end{aligned}$$ as desired. 
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}$$

That's all for today. If you want to try some problems, consider looking at this problem set made by me. Also, if you are interested to learn something more about PIE, then maybe go through this, this, this, this and this. Hope to see you soon.
Emon.

Labels:

Comments

Post a Comment

Popular posts from this blog

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess wha...
2 comments
Read more

Functional Equations 101

Let's get to the math:  Let there be two sets $X$ and $Y$. A function  from $X$ to $Y$ denoted as $f \colon X \to Y$ is assigning a value in $Y$ for every element in $X$. We say that $X$ is the domain of the function $f$ and $Y$ is the range.  A function $f \colon X \to y$ is said to be injective if $f(x) = f(x^{\prime}) \implies x = x^{\prime}$ To put it in a more abstract way, if there is some $a \in Y$ then there is at most one $b \in X$ such that $f(b) = a$ holds true.  A function is said to be surjective when for any $a \in Y$ there is at least one $b \in X$ such that $f(b) = a$ holds true.  A function is bijective if for every $a \in Y$ there is exactly one $b \in X$ such that $f(b) = x$. Bijective functions are basically functions which are both injective and surjective.  Bonus: A function $f \colon X \to X$ is known as an involution if $f(f(x)) = x \; \forall  x \in X$  As an exercise, the readers should try to prove that every function th...
Post a Comment
Read more

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe ...
1 comment
Read more