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 thisthisthisthis and this. Hope to see you soon.
Emon.

Comments

Popular posts from this blog

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig