Question
A wonderful, but very tough question from
Permutation and Combinations.
In
how many ways, can we rearrange the word MONSOON such that no two adjacent
positions are taken by the same letter? (Tough one. Tougher than what we will
see in CAT)
Explanation
First
up, lets get the facts out of the way – The three O’s need to be kept apart,
then the 2 N’s.
Let us focus on the three O’s.
We
can place the three O’s in some blanks around the other letters. Or, three O’s
can be placed in 3 slots out of the 5 in __M__N__S__N__ . This can be done in 5C3,
or 10 ways.
Or,
the O’s can be in slots {1, 3, 5} or {1, 3, 6} or {1, 3, 7} or {1, 4, 6} or {1,
4, 7} or {1, 5, 7} or {2, 4, 6} or {2, 4, 7} or {2, 5, 7} or {3, 5, 7} - Whew.
Now,
for each of these arrangements, there are 4!/2! = 12 arrangements for the other
4 letters. But the one thing we need to keep in mind now is the fact that 2 N’s
could be adjacent in these arrangements. We will need to eliminate these.
O’s
in slots {1, 3, 5} or O__O__O__ __ - Ns could be in the last two slots. There are
2! = 2 words like this. So, number of words that we need to count = 12 – 2 = 10
O’s
in slots {1, 3, 6} or O__O__ __O__ - Ns could be two slots 4 and 5. There are
2! = 2
words like this. So, number of words that we need to count = 12 – 2 = 10
O’s
in slots {1, 3, 7} or O__O__ __ __O - Ns could be in the slots {4, 5} or {5, 6}.
There are totally 4 words that we need to subtract. So, number of words that we
need to count = 12 – 4 = 8
O’s
in slots {1, 4, 6} or O__ __O__O__ - Ns
could be in the slots {2, 3}. There are 2! = 2 words like this. So, number of
words that we need to count = 12 – 2 = 10
O’s
in slots {1, 4, 7} or O__ __O__ __O - Ns could be in slots {2, 3} or {5, 6}. There
are totally 4 words that we need to subtract. So, number of words that we need
to count = 12 – 4 = 8
O’s
in slots {1, 5, 7} or O__ __ __O__ O - Ns could be in the slots {2, 3} or {3, 4}.
There are totally 4 words that we need to subtract. So, number of words that we
need to count = 12 – 4 = 8
O’s
in slots {2, 4, 6} or __O__O__O__ - Tehre
are no possible slots for N. So, we count all 12 words on this list.
O’s
in slots {2, 4, 7} or __O__O__ __ O - Ns could be in slots {5, 6}. There are 2!
= 2 words like this. So, number of words that we need to count = 12 – 2 = 10
O’s
in slots {2, 5, 7} or __O__ __O__ O - Ns could be in slots {3, 4}. There are 2!
= 2 words like this. So, number of words that we need to count = 12 – 2 = 10.
O’s
in slots {3, 5, 7} or __ __ O__O__O - Ns could be in the first two slots. There
are 2! = 2 words like this. So, number of words that we need to count = 12 – 2 =
10
Total
number of words = 10 + 10 + 8 + 10 + 8 + 8 + 12 + 10 + 10 + 10 = 96.
Phew!.
There
is a far more elegant method for accounting for the words where the 2 N’s
appear together. This one came from Mukund Sukumar.
We
need to account for the number of possibilities of N,N being together. So to
subtract that part, consider 'NN' being together as one letter and place O's. In
3 out of the 4 slots in _M_NN_S_
The
O’s can be selected in 4C3 ways. The MNNS can be
rearranged in 3! Ways if the N’s have to appear together.
Or,
we get 4C3 * 3! = 24 ways. So, we have 120-24 = 96 ways
totally.