in Combinatory edited by
11,385 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$
in Combinatory edited by
11.4k views

2 Comments

Option elimination for this problem only
Total arrangements possible = 5! = 120

1 combination when all balls are at their respective places
so remaining arrangements = 120 - 1 = 119 
this eliminates Options C & D

when B1 is placed at C1
no. of arrangements = 1 * 4 ! = 24
so remaining arrangements = 119 - 24 = 95 
this eliminates Options B 

Use this method when you dont know how to solve the ques
and their is large difference in the given options like above options

50
50

Before checking answer first read Derangement concept.

9
9

11 Answers

52 votes
52 votes
Best answer

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

4 Comments

@Utsav09 we can use the formula from here directly. 

http://oeis.org/wiki/Number_of_derangements

understanding the concept above will make formula seem trivial and might not need to keep in memory. 

10
10

Ok. Thanks @junk_mayavi

0
0

Hi , Can we think about in this way.

8
8
25 votes
25 votes

Use Derangement concept D5= 44 so answer is A

http://oeis.org/wiki/Number_of_derangements

2 Comments

Using formula I got 45. Why did we remove 1?
0
0

CJ147

U have calculated wrongly, answer will be only 44

1
1
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

3 Comments

genius! @lambda
1
1
i think this is applicablieonly for large values of N.
1
1
edited by

This is general formula applicable for all value of $n>0$.
See the comparison for some small values.

4
4
14 votes
14 votes
Answer: A

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

1 comment

Can you please explain how you got the equation ?

Thanks in advance...

0
0
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true