Permutation-Combination
Aptitude

 Back to Questions
Q.

Bob is about to hang his 8 shirts in the wardrobe. He has four different styles of shirt, two identical ones of each particular style.

How many different arrangements are possible if no two identical shirts are next to one another?

 A.

764

 B.

864

 C.

964

 D.

1064

 Hide Ans

Solution:
Option(B) is correct

Total number of 8-perms of 8 shirts, recognising identical pairs, is:

$= \dfrac{8!}{{2!}^4}$

$= 2520$

In order to find the number of perms with no adjacency we subtract from this the number of perms with 4 pairs adjacent, 3 pairs adjacent, 2 pairs adjacent and 1 pair adjacent.

The following four intermediate results aid explanation of the final calculation :

Let, the shirts be called $A, A, B, B, C, C, D, D$ and let $\{A,.....\}$ be the set of 8-perms that have only the styles named in the argument list adjacent to each other.

So, for instance, $\{B,D\}$ is the set of perms that contain $BB$ and $DD$ but not $AA$ and $CC$. Let $s\{A,....\}$ be the number of perms in $\{A,...\}$

(i) $s\{A,B,C,D\} = 24$. This is because we can imagine each pair as one object and simply permute the four twin objects amongst themselves in $4!$ ways to give $\{A,B,C,D\}$.

(ii) $s\{A,B,C\} = 36$. To see this we first permute the 5 objects $AA, BB, CC, D, D$. This can be done in $\dfrac{5!}{2!}=60$ ways but includes $\{A,B,C,D\}$. Hence $s\{A,B,C\} = \dfrac{5!}{2!}-24$

(iii) $s\{A,B\}=84$. As before, we first permute the 6 objects $AA, BB, C, C, D, D$. This can be done in $\dfrac{6!}{{2!}^2}$ ways but includes $\{A,B,C\}, \{A,B,D\}$ and $\{A,B,C,D\}$.

Hence $s\{A,B\} =\dfrac{6!}{{2!}^2} - 2×36 -24$

(iv) $s\{A\}=246$. This time we start by permuting the 7 objects $AA, B, B, C, C, D, D$ in 
$\dfrac{7!}{{2!}^3}$ ways and then removing from it the subsets $\{A,B\}, \{A,C\}, \{A,D\}, \{A,B,C\}, \{A,B,D\}, \{A,C,D\}$ and $\{A,B,C,D\}$. Hence $s\{A\}=\dfrac{7!}{{2!}^3}- (3 × 36) -(3 × 84) - 24$

Assembling the total number of perms with some adjacency:

There are $^4C_4$ subsets of type (i) ie $\{A,B,C,D\}$

Total number of 8-perms of this type is 24.

There are $^4C_3$ subsets of type (ii) ie $\{A,B,C\} \{A,B,D\} \{A,C,D\} \{B,C,D\}$

Total number of 8-perms of this type is $4×36=144$

There are $^4C_2$ subsets of type (iii) ie $\{A,B\} \{A,C\} \{A,D\} \{B,C\} \{B,D\} \{C,D\}$

Total number of 8-perms of this type is,

$=6×84$

$= 504$

Finally there are $^4C_1$ subsets of type (iv) ie $\{A\} \{B\} \{C\} \{D\}$

Total number of 8-perms of this type,

$= 4×246$

$= 984$

Therefore, number of perms with some adjacency is,

$=24+144+504+984$

$= 1656$

Number of perms with no adjacency is,

$=2520-1656$

$=\textbf{864}$


(0) Comment(s)