De-Arrangement
Selection of objects from two or more groups: if there are n₁ objects of one kind, n₂ objects of second kind, … nk objects of kth kind, then the number of ways of selecting r objects out of these objects is equal to coefficient of x² in [(1 + x + x² + … + xn₁) (1 + x + x² + … + xn₂) … (1 + x + x² + … + xⁿk)].
If there are n₁ objects of one kind, n₂ objects of second kind, … nk objects of Kth kind, then the number of ways of selecting r objects out of these object such that each selection contains at least one object of each kind, is Coefficient of x² in [(1 + x + x² + … + xn₁) (1 + x + x² + … + xn₂) … (1 + x + x² + …. + xⁿk)].
Of there are n₁ objects of one kind, n₂ objects of second kind, …, nk objects of Kth kind, then the number of arrangement of these objects taken r at a time is Coefficient of x² in \(\left[ r!\left( 1+\frac{x}{1!}+\frac{{{x}^{2}}}{2!}+\,…\,+\frac{{{x}^{{{n}_{1}}}}}{n!} \right)\times \left( 1+\frac{x}{1!}+\frac{{{x}^{2}}}{2!}+\,…\,+\frac{{{x}^{{{n}_{2}}}}}{{{n}_{2}}!} \right)…\left( 1+\frac{x}{1!}+\frac{{{x}^{2}}}{2!}+\,…\,+\frac{{{x}^{{{n}_{k}}}}}{{{n}_{k}}!} \right) \right]\).
De-Arrangement: Let a₁, a₂, …, an be n distinct objects such that their position is fixed a row.
If we now re-arrange a₁, a₂, …, an in such a way that no one occupies its original place than such as arrangement Is called a derangement.
In other words, a derangement of a₁, a₂, … an is a bijection f: [a₁, a₂, … an] → [a₁, a₂, … an].
Such that f(ai) ≠ ai ; I = 1, 2, … n.
If n distinct objects are arranged in a row then the number of ways in which they can be deranged so that none of them occupies its original place is \(n!\left[ 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\,…\,+{{\left( -1 \right)}^{n}}\frac{1}{n!} \right]\) and it is denoted by D(n).
If r(O ≤ r ≤ n) objects occupy the places assigned to them i.e., their original places and none of the remaining (n – r) objects occupies its original places, then the number of such ways is
D (n – r) = \({{n}_{{{c}_{r}}}}\) D (n – r)
= \({{n}_{{{c}_{r}}}}\,\left( n-r \right)!\left[ 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\,…\,+\left( -1 \right)\frac{n!}{\left( n-r \right)!} \right]\).
Example: In how many ways can 10 letters be placed in 10 marked envelops, so that no letter is in the right envelope?
Solution: The required number of ways is equal to the number of derangement of 10 objects hence, required number of ways.
= 10! \(\left[ 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\,…\,+\frac{1}{10!} \right]\).
Example: Ravish writes letters to his five friends and addresses the corresponding envelops.
In how many ways can the letters be placed in the envelops so that at least two of them are in the wrong envelopes?
Solution: Required number of ways
= \(\sum\limits_{r=2}^{5}{{{5}_{{{C}_{5-r}}}}D\left( r \right)}\),
= \(\sum\limits_{r=2}^{5}{\frac{5!}{r!\left( 5-r \right)!}r!\left[ 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\,…\,+\frac{{{\left( -1 \right)}^{r}}}{r!} \right]}\),
= \(\sum\limits_{r=2}^{5}{\frac{5!}{\left( 5-r \right)!}}\left[ \frac{1}{2!}-\frac{1}{3!}+\,…\,+\frac{{{\left( -1 \right)}^{r}}}{r!} \right]\),
= \(\frac{5!}{3!}\left( \frac{1}{2!} \right)+\frac{5!}{2!}\left( \frac{1}{2!}-\frac{1}{3!} \right)+\frac{5!}{1!}\left( \frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!} \right)+\frac{5!}{0!}\left( \frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!} \right)\),
= 10 + 20 + (60 – 20 + 5) + (60 – 20 + 5 – 1)
= 10 + 20 + 45 + 44
= 119