Register

GATE IT 2004 | Question: 35

• edited by
20,619 views
53 53 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$

14 Answers

Best answer
65 65 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
38 38 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 14 votes
Answer: A

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

Number of derangements of n-objects = $n! \sum_{i=0}^{n}\frac{(-1)^i}{i!}$

here $n =5.$

$\implies\ 5! \left [ \frac{(-1)^0}{0!} + \frac{(-1)^1}{1!} + \frac{(-1)^2}{2!} + \frac{(-1)^3}{3!}+ \frac{(-1)^4}{4!} + \frac{(-1)^5}{5!} \right ]$

$= 5! \left [ 1 - 1 +\frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} \right ]$

$= \left [ \frac{5!}{2!} - \frac{5!}{3!} + \frac{5!}{4!} - \frac{5!}{5!} \right ]$

$= 60-20+5-1$

$= 44$

• edited by
4 4 votes

Here's an intutive explanation:

Suppose you want to find the no.of derangements of n then:

T(n) = total possible permutations - ( let 1 element be at it's proper place and rest are deranged + let 2 elements be at their proper place and rest are deranged + ......+ except one all elements at their proper place which is same as saying that all elements at their proper place)

T(n) = n! - (nC1 * T(n-1) + nC2 * T(n-2) + ... + 1)

Applying the eqn here

T(2) = 1

T(3) = 3! - ( 3C1*T(2) + 1)

Similarly you can find T(4) and T(5). 

Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE IT 2004 | Quest...Next → · GATE IT 2004 | Quest...
← Previous in category · GATE IT 2004 | Quest...Next in category → · GATE IT 2005 | Quest...
Position:
Show:

Related questions

43 43 votes
6 answers 6 answers
16.9k
16.9k views
Kathleen asked Sep 23, 2014
16,948 views
GATE CSE 1999 | Question: 1.3
The number of binary strings of $n$ zeros and $k$ ones in which no two ones are adjacent is$^{n-1}C_k$$^nC_k$$^nC_{k+1}$None of the above
51 51 votes
8 answers 8 answers
17.4k
17.4k views
Kathleen asked Sep 14, 2014
17,386 views
GATE CSE 2000 | Question: 5
A multiset is an unordered collection of elements where elements may repeat any number of times. The size of a multiset is the number of elements in it, counting repetiti...
48 48 votes
1 answers 1 answer
10.0k
10.0k views
Ishrat Jahan asked Nov 2, 2014
10,021 views
GATE IT 2004 | Question: 34
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+...
51 51 votes
6 answers 6 answers
13.5k
13.5k views
Misbah Ghaya asked Nov 29, 2016
13,533 views
GATE CSE 1989 | Question: 4-i
How many substrings (of all lengths inclusive) can be formed from a character string of length $n$? Assume all characters to be distinct, prove your answer.