edited by
11,323 views
43 votes
43 votes

In how many ways can we distribute $5$ distinct balls, $B_1, B_2, \ldots, B_5$ in $5$ distinct cells, $C_1, C_2, \ldots, C_5$ such that Ball $B_i$ is not in cell $C_i$, $\forall i= 1,2,\ldots 5$  and each cell contains exactly one ball?

  1. $44$
  2. $96$
  3. $120$
  4. $3125$
edited by

11 Answers

Best answer
52 votes
52 votes

Derangement : arrangement where no element is in its designated position

Number of derangement can be calculated easily using the principle of mutual exclusion and inclusion (http://math.mit.edu/~fox/MAT307-lecture04.pdf )

In this question, we take the designated position of ball $B_i$ as $C_i$.

We need to find all possible arrangements where no $B_i$ is in its designated cell $C_i$.

Lets take $5$ arrangements for positions $1,2,3,4$ and $5$ where, in each of them, one element is in its designated position and denote them as $S_i$.

$$\begin{array}{|c|c|c|c|} \hline \text {$1$} &  \text{ $x$}& \text{$x$} & \text{$x$} & \text{$x$}  \\\hline \end{array} \rightarrow{S_1}$$

$|{S_1}| = 4!$ as the other 4 balls can be arranged in $4!$ ways inside $S_1$

Similarly, we have $S_2$ which is the arrangement of all balls with $B_2$ in its designated position.

$$\begin{array}{|c|c|c|c|} \hline \text {$x$} &  \text{ $2$}& \text{$x$} & \text{$x$} & \text{$x$}  \\\hline \end{array} \rightarrow{S_2}$$

We have $|{S_2}| = 4!$ similar to $|S_1|$ and likewise $|{S_i}| = 4!$ . 

We have total number of non-derangement $=\ |{S_1}\cup{S_2}\cup{S_3}\cup{S_4}\cup{S_5}| $

According to the principle of Mutual Inclusion and Exclusion

$|{S_1}\cup{S_2}\cup{S_3}\cup{S_4}\cup{S_5}| = \Sigma|{S_i}|-\Sigma|{S_i\cap{S_j}}|+\Sigma|S_i\cap{S_j}\cap{S_k}|-\ldots \longrightarrow (A)$


$|S_1\cap{S_2}| = $number of arrangements where $B_1$ and $B_2$ are in their designated positions.

$$\begin{array}{|c|c|c|c|} \hline \text {$1$} &  \text{ $2$}& \text{$x$} & \text{$x$} & \text{$x$}  \\\hline \end{array}$$

This can be done in $3!$ ways.

Similarly all the other two intersections,$ |S_i\cap {S_j}| = 3!$ and three intersections,$|S_i\cap{S_j}\cap{S_k}| = 2! $ and similarly all. 

Substituting in equation $(A),$

$|{S_1}\cup{S_2}\cup{S_3}\cup{S_4}\cup{S_5}|= 5\times 4!-\binom{5}{2}\times 3!+\binom{5}{3}\times 2!-\binom{5}{4}\times 1!+\binom{5}{5}\times 0!=76$ (equals number of non derangements)

Derangements = all arrangements non derangements

$= 5! - 76 = 44$

Correct Answer: A

edited by
21 votes
21 votes

Number of Derangement is given by equation

$$!n=\left[\frac{n!}{e}\right]$$

Where $[x]$ is the nearest integer function.

Now lets put $n=5,$

$$!5=\left[\frac{5!}{e}\right]=44$$

https://en.wikipedia.org/wiki/Derangement

14 votes
14 votes
Answer: A

Number of ways = 5C0*5! - 5C1*4! + 5C2*3! - 5C3*2! + 5C4*1! - 5C5*0! = 44
Answer:

Related questions

41 votes
41 votes
1 answer
1
Ishrat Jahan asked Nov 2, 2014
5,505 views
Let $H_1, H_2, H_3,$ ... be harmonic numbers. Then, for $n \in Z^+$, $\sum_{j=1}^{n} H_j$ can be expressed as$nH_{n+1} - (n + 1)$$(n + 1)H_n - n$$nH_n - n$$(n + 1) H_{n+...
23 votes
23 votes
9 answers
2
19 votes
19 votes
4 answers
4
go_editor asked Dec 21, 2016
4,057 views
How many distinct ways are there to split $50$ identical coins among three people so that each person gets at least $5$ coins?$3^{35}$$3^{50}-2^{50}$$\binom{35}{2}$$\bino...