How many words can be created by using the letters of "MATHEMATIK" when no same letters can be next to each other?

Question

The word MATHEMATIK (in german) has 10 letters.

I want to know how many different words can be created by using the letters of this word. However, the same letter can never be next to each other.

So for example, MAATHEMTIK is not allowed.

I did the following:

$n = 10$

$k_1 = 2$ (M)

$k_2 = 2$ (A)

$k_3 = 2$ (T)

$k_4 = 1$ (H)

$k_5 = 1$ (E)

$k_6 = 1$ (I)

$k_7 = 1$ (K)

I use the formula $\frac{n!}{k_1! \cdot k_2! ... \cdot k_n! }$ and get:

$$\frac{13!}{2! \cdot 2! \cdot 2! \cdot 1! \cdot 1! \cdot 1! \cdot 1!} = 778377600$$

This is the number of all possible words (permutations). Now we need to subtract the number of words which can be created by having the same letter next to each other, i.e.

• MAATHEMTIK
• AAMTHEMTIK
• MTAAHEMTIK
• etc.

But I don't know how to figure that out.

Answer 1

Please apply Principle of Inclusion Exclusion. It is a more standard approach.

Your answer would simply be

$\displaystyle \frac{10!}{2! \ 2! \ 2!} - \binom{3}{1} \ \frac{9!}{2! \ 2!} + \binom{3}{2} \ \frac{8!}{2!} - \binom{3}{3} \ 7! = 236880$

Some details -

The first term is unrestricted number of arrangements. Now we subtract from it all arrangements where either of $AA, MM, TT$ are together. If you take $AA$ together as one letter, you now have $9$ letters and the number of arrangements are $\frac{9!}{2! \ 2!}$. Now you have same number of arrangements for $MM$ and $TT$. But these overcount arrangements where two identical letters (say AA, MM) are together. As we subtracted them, we need to add them back. The same follows for the next.

Answer 2

Someone mentioned another solution involving the permutations of "Mississippi," but it makes things unnecessarily complicated.

Simple solution:

Assume initially that all the letters of 'mathematik' are distinct, subscripting them if necessary. So the first $m$ is labelled $m_1$ and the second is $m_2$. Then with 10 "distinct" letters (not really distinct, just different b/c of the subscripts) there are $10!$ permutations.

Now to deal with the overcounting due to the subscripts: for each subscripted letter divide by the factorial of its count. For example, since $m$ appears twice, divide by 2!. Likewise divide by 2! because of the 'a' appearing twice, and again by 2! because of the 't' appearing twice.

So the final answer is ${10! \over {2! 2!2!}}$.

In general, if a letter appears 3 times, divide by 3! to compensate for overcounting, etc.

---

[edit]: I forgot to incorporate the fact that a letter can't appear next to the same letter. Please see Aryan's answer below.

Answer 3

First of all the letters are :
2×A,2×M,2×T,H,E,I,K.
Now we will do as the following first of all it is clear that there is $7!$ different ways of making a word just by using the letters A,M,T,H,E,I,K.
note that there are $8$ different places for putting a letter in this word (one before the first letter one between the first and second letters one between the second and third and so on) so if we want to place a second letter A there are $8-2$ different possible places since there are two places adjacent to the first A and we should not place our second A in those places. So there is $7!×6$ different methods of putting 2×A,M,T,H,E,I,K such that no two same letters are adjacent.
Now in the same way there are 9 different places for putting the second M but two of them are out of access since the second M should not be adjacent to the first letter M. So there is $7!×6×7$ different methods of putting 2×A,2×M,T,H,E,I,K such that no two same letters are adjacent.
And finally for putting the second T there are 10 different places two of which or not allowed to have another T in them. So at last there are $7!×6×7×8$ different words having the same letters as MATEMATIKS such that no two same letters are adjacent.
Now note that in this counting, each valid word will be counted exactly 8 times and this is the reason:
If for a 10-letter word $W$ made of the letters of MATEMATIKS, we choose one A, one M and one T and the H,E,I,K as the initial letters, then by removing the other 3 letters there will be 7 initial letters, using which, by going through the foresaid procedure $W$ can be built. So technically each word is produced 8 times each time by a different initial 7-letter. (That's clearly because there are 2×2×2 choices for choosing one A, one M and one T to be the initial ones out of two A, two M and two T. Also note that because $W$ is a word in which no two same letters are adjacent, all of these initial 7-letters that produce $W$ are pairwisely different)
Hence any word is counted 8 times and the answer is $7!×6×7×8÷8=7!×6×7$