How many permutations are there of
$$ M, M, A, A, A, T, T, E, I, K $$
so that there are no two consecutive letters are the same?
I would use the Inclusion-exclusion principle where
$$ A_{i} = \{ \text{on} \ i-\text{th} \text{ and }(i+1)-\text{th} \text{ position, there are two same consecutive letters} \}. $$
So my answer would be
$$ \frac{10!}{2!3!2!} – 9 \cdot \left(\frac{9!}{3!2!} + \frac{9!}{3!2!} +\frac{9!}{2!2!}\right)+ 8 \cdot \left(\frac{8!}{2!2!}\right) +8 \cdot 7 \cdot \left(\frac{8!}{3!} + \frac{8!}{2!} +\frac{8!}{2!}\right) – 7 \cdot 6 \cdot 5 \cdot 7!$$
How many permutations are there of M, M, A, A, A, T, T, E, I, K, so that no two consecutive letters are the same
combinatoricsinclusion-exclusion
Related Solutions
(i)
For the first question, your idea of using the Inclusion-Exclusion Principle is the correct approach.
The number of distinguishable arrangements of the letters $a, a, a, b, b, b, c, c, c$ is $$\frac{9!}{3!3!3!}$$ where the factors of $3!$ in the denominator are attributable to the fact that interchanging identical letters in a given arrangement does not produce an arrangement that is distinguishable from the original arrangement. Alternatively, we can choose to fill three of the nine positions with $a$'s, three of the remaining six positions with $b$'s, and the remaining three positions with $c$'s, which can be done in $$\binom{9}{3}\binom{6}{3}\binom{3}{3} = \frac{9!}{3!6!} \cdot \frac{6!}{3!3!} \cdot \frac{3!}{3!0!} = \frac{9!}{3!3!3!}$$ ways.
From these, we must exclude those arrangements in which there are three consecutive identical letters.
Next, we count the number of arrangements in which a block of three consecutive identical letters appears. There are three ways to choose which letter appears in the block of three consecutive letters. Treating the block of three identical letters as one object, we have seven objects to arrange, the block and the other six letters. Since those six letters contain two sets of three identical letters, the number of arrangements containing a block of three consecutive letters is $$\binom{3}{1}\frac{7!}{3!3!}$$
However, we have counted arrangements in which two blocks of consecutive identical letters appear twice.
Next, we count arrangements in which two blocks of three consecutive identical letters appear. There are three ways to choose which two letters appear in blocks of three consecutive letters. If we treat each block as an object, we have five objects to arrange, the two blocks and the other three letters. Since the other three letters are identical, the number of arrangements containing two blocks of three consecutive letters is $$\binom{3}{2}\frac{5!}{3!}$$
If we subtract the number of arrangements in which two blocks of three identical letters appear from our initial count of the number of arrangements in which a block of three identical letters appears, we will not have counted arrangements in which three blocks of three identical letters appear since we first counted them three times, then subtracted them three times.
The number of arrangements with three blocks of three consecutive identical objects is $3!$.
By the Inclusion-Exclusion Principle, the number of arrangements in which at least one block of three consecutive letters appears is
$$\binom{3}{1}\frac{7!}{3!3!} - \binom{3}{2}\frac{5!}{3!} + \binom{3}{3}3!$$
so the number of arrangements in which no three consecutive letters are identical is $$\frac{9!}{3!3!3!} - \binom{3}{1}\frac{7!}{3!3!} + \binom{3}{2}\frac{5!}{3!} - \binom{3}{3}3!$$
(ii)
The second problem can also be handled by Inclusion-Exclusion Principle.
We wish to exclude pairs of identical letters.
One pair of consecutive identical letters:
There are three ways to choose the repeated letter. Treating that pair of identical letters as a block leaves us with eight objects, including two sets of three identical letters. The number of ways these objects can be arranged is $$\binom{3}{1}\frac{8!}{3!3!}$$
Two pairs of consecutive identical letters:
There are two cases. We can have three consecutive identical letters (two overlapping pairs) or two distinct pairs of consecutive identical letters (such as $aa$ and $bb$). We found above that there are $$\binom{3}{1}\frac{7!}{3!3!}$$ arrangements with three consecutive identical letters.
For the other case, there are three ways of choosing the letters of the alphabet from which the pairs of consecutive identical letters are chosen. This leaves us with seven objects, the two blocks of consecutive identical letters, the third letter from each chosen type, and the three letters of the third type. Since the three letters of the third type are indistinguishable, the number of such arrangements is $$\binom{3}{2}\frac{7!}{3!}$$ In total, the number of arrangements with two pairs of consecutive identical letters is $$\binom{3}{1}\frac{7!}{3!3!} + \binom{3}{2}\frac{7!}{3!}$$
Three pairs of consecutive identical letters:
Again, there are two cases. We could choose three pairs of consecutive identical letters from different letters of the alphabet or three consecutive identical letters (two overlapping pairs) and a pair of consecutive identical letters from a different letter of the alphabet.
If each pair of consecutive identical letters is from a distinct letter of the alphabet, we have six objects to arrange, $aa$, $bb$, $cc$, $a$, $b$, and $c$. This can be done in $$6!$$ ways.
For the other case, there are three ways of selecting the letter of the alphabet from which three consecutive identical letters are selected, and two ways of selecting the letter of the alphabet from which two consecutive identical letters are selected. Again, we have six objects, the block of three consecutive identical letters, the block of two consecutive identical letters, and the other four letters. Three of those other four letters are indistinguishable, so the number of such arrangements is $$\binom{3}{1}\binom{2}{1}\frac{6!}{3!}$$ Therefore, the total number of arrangement with three consecutive identical letters is $$6! + \binom{3}{1}\binom{2}{1}\frac{6!}{3!}$$
Four pairs of consecutive identical letters:
Again, we have two cases. We have two blocks of three consecutive identical letters (two sets of two overlapping pairs), or we have one block of three consecutive identical letters (two overlapping pairs) with a pair of consecutive identical letters from each of the other letters of the alphabet.
We found above that the number of arrangements with two blocks of three consecutive identical letters is $$\binom{3}{2}\frac{5!}{3!}$$ For the remaining case, there are three ways of choosing the letter of the alphabet with three consecutive identical letters. We have five objects, the block of three consecutive identical letters, the two blocks of two consecutive identical letters, and the two remaining single letters. They can be arranged in $$\binom{3}{1}5!$$ ways. The total number of arrangements with four pairs of consecutive identical letters is then $$\binom{3}{2}\frac{5!}{3!} + \binom{3}{1}5!$$
Five pairs of consecutive identical letters:
For this to occur, there must be two blocks of three consecutive identical letters (two sets of two overlapping pairs) and a block of two consecutive identical letters drawn from the other available letter. There are three ways of selecting the two letters from which the blocks of three identical consecutive letters are drawn. We now have four objects to arrange, the two blocks of three consecutive identical letters, the block of two consecutive identical letters, and the remaining letter. The number of such arrangements is $$\binom{3}{2}4!$$
Six pairs of consecutive identical letters:
The only ways for this to occur is if we have three blocks of three consecutive identical letters (three sets of two overlapping pairs). We saw above that there are $$3!$$ such arrangements.
By the Inclusion-Exclusion Principle, the number of arrangements of the letters $a, a, a, b, b, b, c, c, c$ in which no two identical letters are consecutive is $$\frac{9!}{3!3!3!} - \binom{3}{1}\frac{8!}{3!3!} + \left[\binom{3}{1}\frac{7!}{3!3!} + \binom{3}{2}\frac{7!}{3!}\right] - \left[6! + \binom{3}{1}\binom{2}{1}\frac{6!}{3!}\right] + \left[\binom{3}{2}\frac{5!}{3!} + \binom{3}{1}5!\right] - \binom{3}{2}4! + \binom{3}{3}3! = 174$$
We shall solve by successively applying the well known "gap" and "subtraction" methods.
Firstly, we shall keep the $E's$ separate by placing them in the gaps of $-A-B-C-D-D-$ and permute the other letters, thus $\binom63\cdot\frac{5!}{2!} = 1200$ ways.
We shall now subtract arrangements with the $D's$ together treating them as a super $D$, $-A-B-C-\mathscr D-$, i.e. $\binom53\cdot4!= 240$
Thus we get $1200-240 = \boxed{960}$
Best Answer
As you observed, there are $10$ letters, of which $3$ are $A$s, $2$ are $M$s, $2$ are $T$s, $1$ is an $E$, $1$ is an $I$, and $1$ is a $K$.
If there were no restrictions, we would choose three of the ten positions for the $A$s, two of the remaining seven positions for the $M$s, two of the remaining five positions for the $T$s, and arrange the $E$, $I$, $K$ in the remaining three positions in $$\binom{10}{3}\binom{7}{2}\binom{5}{2}3! = \frac{10!}{3!7!} \cdot \frac{7!}{2!5!} \cdot \frac{5!}{2!3!} \cdot 3! = \frac{10!}{3!2!2!}$$ in agreement with your answer.
From these, we must subtract those arrangements in which or more pairs of identical letters are adjacent.
Arrangements with a pair of adjacent identical letters: We have to consider cases, depending on whether the identical letters are $A$s, $M$s, or $T$s.
A pair of $A$s are adjacent: We have nine objects to arrange: $AA, A, M, M, T, T, E, I, K$. Choose two of the nine positions for the $M$s, two of the remaining seven positions for the $T$s, and then arrange the five distinct objects $AA$, $A$, $E$, $I$, $K$ in the remaining five positions, which can be done in $$\binom{9}{2}\binom{7}{2}5!$$ ways.
A pair of $M$s are adjacent: We have nine objects to arrange: $A, A, A, MM, T, T, E, I, K$. Choose three of the nine positions for the $A$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $MM, E, I, K$ in the remaining four positions, which can be done in $$\binom{9}{3}\binom{6}{2}4!$$ ways.
A pair of $T$s are adjacent: By symmetry, there are $$\binom{9}{3}\binom{6}{2}4!$$ such arrangements.
Arrangements with two pairs of adjacent identical letters: This can occur in two ways. Either the pairs are disjoint or they overlap.
Two pairs of $A$s are adjacent: This can only occur if the three $A$s are consecutive. Thus, we have eight objects to arrange: $AAA, M, M, T, T, E, I, K$. Choose two of the eight positions for the $M$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $AAA, E, I, K$ in the remaining four positions, which can be done in $$\binom{8}{2}\binom{6}{2}4!$$ ways.
A pair of $A$s are adjacent and a pair of $M$s are adjacent: We have eight objects to arrange: $AA, A, MM, T, T, E, I, K$. Choose two of the eight positions for the $T$s and arrange the six distinct objects $AA, A, MM, E, I, K$ in the remaining six positions in $$\binom{8}{2}6!$$ ways.
A pair of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are $$\binom{8}{2}6!$$ such arrangements.
A pair of $M$s are adjacent and a pair of $T$s are adjacent: We have eight objects to arrange: $A, A, A, MM, TT, E, I, K$. Choose three of the eight positions for the $A$s and then arrange the remaining five distinct objects $MM, TT, E, I, K$ in the remaining five positions in $$\binom{8}{3}5!$$ ways.
Arrangements with three pairs of adjacent identical letters: We again consider cases.
Two pairs of $A$s are adjacent and a pair of $M$s are adjacent: We have seven objects to arrange, $AAA, MM, T, T, E, I, K$. Choose two of the seven positions for the $T$s and arrange the five distinct objects $AAA, MM, E, I, K$ in the remaining five positions in $$\binom{7}{2}5!$$ ways.
Two pairs of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are $$\binom{7}{2}5!$$ such arrangements.
A pair of $A$s are adjacent, a pair of $M$s are adjacent, and a pair of $T$s are adjacent: We have seven objects to arrange: $AA, A, MM, TT, E, I, K$. Since all the objects are distinct, there are $$7!$$ such arrangements.
Arrangements containing four pairs of adjacent identical letters: We have six objects to arrange: $AAA, MM, TT, E, I, K$. Since all the objects are distinct, there are $$6!$$ such arrangements.
By the Inclusion-Exclusion Principle, there are $$\binom{10}{3}\binom{7}{2}\binom{5}{2}3! - \binom{9}{2}\binom{7}{2}5! - \binom{9}{3}\binom{6}{2}4! - \binom{9}{3}\binom{6}{2}4! + \binom{8}{2}\binom{6}{2}4! + \binom{8}{2}6! + \binom{8}{2}6! + \binom{8}{3}5! - \binom{7}{2}5! - \binom{7}{2}5! - 7! + 6!=47760$$ arrangements in which no two adjacent letters are identical.