Inclusion and Exclusion principle
The principle of inclusion and exclusion is a counting technique in which the elements satisfy at least one of the different properties while counting elements satisfying more than one property are counted exactly once.
For example if we want to count number of numbers in first $100$ natural numbers which are either divisible by 5 or by 7 . Let Set $A$ is collection of numbers divisible by $5$ , and Set $B$ is collection of numbers divisible by 7 , $A\cap B$ is numbers divisible by both 5 and 7 .
Number of such numbers are $n(A\cup B)=n(A)+n(B)-n(A\cap B)$ that is first number of numbers divisible by 5 and 7 are included and the number divisible by both 5 and 7 i.e 35 are counted in both hence excluded once to count them exactly once .
The distribution of distinct object into group such that each group get at least one object is an application of principle of Inclusion and Exclusion.
(1) Distribution of n distinct objects into m distinct group such that non of the group remain empty.
Let $a_1,a_2,a_3,……,a_n$ be n distinct objects need to be distributed into m distinct groups.
Number of distribution of n distinct object into m group such that any number of object can be given into any group $=m^n$
Let $A_i$ denote distribution of n distinct object into m groups such that particular $i^{th}$ group do not get any object.
i.e $n(A_i)$ is number of distributions in which group $i$ do not get any object , $n(A_i\cap A_j)\;where\,i \neq j$ is number of distribution such that $i^{th}\,and\,j^{th}$ group dose not get any object.
Therefore \begin{matrix} n(A_i)&=&(m-1)^n&&&& \\ n(A_i\cap A_j)&=&(m-2)^n&,&i\neq j&&\\ n(A_i\cap A_j\cap A_k)&=&(m-3)^n&,&i\neq j&,&j\neq k\\ …..\\ \end{matrix}
$$n(A_1\cap A_2\cap A_3\cap….\cap A_{m-1})=(m-(m-1))^n$$
Hence number of distribution of n distinct object into m distinct groups such that at least one of the group remain an empty group =$n(A_1\cup A_2\cup A_3\cup…..\cup A_m)$ $$=\,\sum n(A_i)-\sum_{i\neq j} n(A_i\cap A_j)+\sum_{i\neq j\neq k} n(A_i\cup A_j\cup A_k)….+(-1)^m\sum n(A_1\cap A_2\cap …..\cap A_{m-1})$$
$$={m \choose 1}(m-1)^n-{m \choose 2}(m-2)^n+{m \choose 3}(m-3)^n-….+(-1)^m {m \choose {m-1}} (m-(m-1))^n$$
$$n(A_1\cup A_2\cup A_3\cup…\cup A_m)=\sum_{r=1}^{m-1} (-1)^{r+1}{m \choose r}(m-r)^n$$
If from all possible distribution of objects without any condition that include case when none of the group is empty to the case when at least one of the group is an empty group . If we exclude when at least one of the group does not get any object ,we get when each group gets at least one of the object is principle of inclusion and exclusion .
Hence number of distributions are $=m^n-n(A_1\cap A_2\cap A_3\cap….\cap A_n)$
$$=m^n-{m \choose 1}(m-1)^n + {m \choose 2} (m-2)^n-{m \choose 3} (m-3)^n……+(-1)^{m-1}{m \choose {m-1}} (m-(m-1))^n$$
Therefore Number of distributions are $$=\sum_{r=0}^{m} (-1)^r {m \choose r}. (m-r)^n$$
Illustration 1 :- Find number of ways in which 10 different toy can be distributed among 4 children such that each get at-least one of the toy.
Solution :- Now 10 different object (toys ) to be distributed into 4 distinct groups ( Children ) such the each get at-least one. is
$$=4^{10}-{4 \choose 1}3^{10}+{4 \choose 2} 2^{10}-{4 \choose 3} 1^{10}=4^{10}-4.3^{10}+6.2^{10}-4.1^{10}$$
Illustration 2 :-If $A=\{x_1,x_2,x_3,…,x_n\}$ and $B=\{y_1,y_2,y_3\}$ are two non empty sets then find number of onto functions $f:A\rightarrow B$.
Solution :- Number of onto functions is number of ways n distinct objects ( elements of set A ) can be distributed into 3 distinct groups ( Elements of set B ) such that each group get at-least one object.
$$=3^n-{3 \choose 1}2^n +{3 \choose 2}1^n=3^n-3.2^n+3$$
Illustration 3 :- If a dice is rolled n times and the number shown up is noted then , Find number of ways it is possible that of n noted numbers exactly three distinct number appear.
Solution :- first from all possible outcomes from 3 only appears the three from 6 can be selected in ${6 \choose 3}$ number of ways.
Now with these three numbers it will be case of onto functions from set A to set B where $n(A)=n$ and $n(B)=3$ Hence number of functions are $$=3^n-{3 \choose 1}.2^n+{3 \choose 2}.1^n$$
Hence total number of ways are $$={6 \choose 3}(3^n-3.2^n+3)$$
(2) Derangement : Number of arrangements in which none of the object occupy its correct place.
What is Derangement ?
Let n distinct objects have there respective correct places. Total number of arrangements of n distinct object at n places are $n!$ . Of which some of the arrangements are where none of the object is at its correct place is called Derangement of n distinct object at n places , and is denoted as $D_n$
How to find Derangement of n distinct object at n places.
Let distinct objects $a_1,a_2,a_3,…..,a_n$ is to be arranged at n places. Let correct place of object $a_i$ is i.
All arrangements of n distinct objects at n places is $=n!$
Let $A_i$ denote the arrangement of object in which object $a_i$ is at its correct place i.
Therefore \begin{matrix} n(A_i)&=&(n-1)!&&&& \\ n(A_i\cap A_j)&=&(n-2)!&,&i\neq j&&\\ n(A_i\cap A_j\cap A_k)&=&(n-3)!&,&i\neq j&,&j\neq k\\ …..\\ \end{matrix}
$$n(A_1\cap A_2\cap A_3\cap….\cap A_n)=(n-n)!$$
Therefore number of arrangements of n distinct objects at n places such that at-least one of the object occupy its correct place $n(A_1\cup A_2\cup A_3\cup…..\cup A_n)$ $$=\,\sum n(A_i)-\sum_{i\neq j} n(A_i\cap A_j)+\sum_{i\neq j\neq k} n(A_i\cup A_j\cup A_k)….+(-1)^{n+1}\sum n(A_1\cap A_2\cap …..\cap A_n)$$
$$={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+{n \choose 3}(n-3)!-…..+(-1)^{n+1} {n \choose n} (n-n)!$$
$$n(A_1\cup A_2\cup A_3\cup…\cup A_n)=\sum_{r=1}^{n} (-1)^{r+1}{n \choose r}(n-r)!$$ $$=\sum_{r=1}^{n} (-1)^{r+1}(\frac{n!}{r!.(n-r)!}).(n-r)!$$
$$=\sum_{r=1}^{n} (-1)^{r+1}\frac{n!}{r!}=n!(\frac{1}{1!}-\frac{1}{2!}+\frac{1}{3!}…..+(-1)^{n+1}\frac{1}{n!})$$
From all possible arrangement of n object at n places excluding the number of arrangements when at least one of the object occupy its correct place is principle of inclusion and exclusion and is called as derangement of n distinct object at n places .
Given by $\;\;D_n=n!-n(A_1\cap A_2\cap A_3\cap….\cap A_n)$
$$\therefore D_n=n!-n!(\frac{1}{1!}-\frac{1}{2!}-\frac{1}{3!}+….+(-1)^{n+1}\frac{n!}{n!})$$
$$\therefore D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+…..+(-1)^n\frac{1}{n!})$$
Illustration 4 :- Find number of one-one function $f:A\rightarrow A$ , where set $A=\{1,2,3,4\}$ . Such that $f(i)\neq i\;,\,\forall\,\,i=1,2,3,4$.
Solution :- Number of one – one function $f:A\rightarrow A$ such that $f(i)\neq i$ is derangement of 4 objects at 4 places.
$$D_4=4!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!})=9$$
Illustration 5 :- Find number of one-one function $f:A\rightarrow A$ , where set $A=\{1,2,3,4,5\}$ . Such that $f(i)\neq i\;,\,\forall\,\,i=1,2,3,4,5\;and\;f(1)=2$.
Solution :- Number of one – one function $f:A\rightarrow A$ such that $f(i)\neq i\;and\;f(1)=2$
It is case of derangement of 5 objects at 5 places , with condition that $f(1)=2$
Let number of derangement when $f(1)=2\;be\;n$
Hence number derangement for $f(1)=3\,or\,4\,or\,5$ will also be $n$ for each $f(1)$ .
Hence number of such functions $f$ are $=\frac{D_5}{4}$
Where $D_5=5!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!})=44$
Hence number of functions are $=\frac{44}{4}=11$
For permutation and combination formula of distribution of identical and distinct objects.