arrangement of the word $“\bf{MATHEMATICS}”$ in which no two same letter occur together.

Total number of arrangement of the word $"\bf{MATHEMATICS}"$ in which

no two same letter occur together.

$\bf{My\; Try::}$ Here word contain $\bf{2M,2A,2T,H,E,I,C,S}$

So first we will arrange $\bf{H,E,I,C,S}$ as $\bf{5!}$ ways

$$\bf{-H-E-I-C-S-}$$

No we have $6$ gap and we can arrange $\bf{2M,2T,2A}$ as $\displaystyle \frac{6!}{2!\cdot 2!\cdot 2!}$

So total number of ways is $\displaystyle \bf{5!\times \frac{6!}{2!\cdot 2!\cdot 2!}}$

Is my solution is right, If not then how can we calculate it.

Help me

Thanks

• You meant $2A$ rather than $2S$. – N. F. Taussig Mar 17 '16 at 12:34
• Thanks N. F. Taussig I have edited it. – juantheron Mar 17 '16 at 12:38
• There are many valid arrangements that don't match your -H-E-I-C-S- pattern. For instance, the word MATHEMATICS itself. – TonyK Mar 17 '16 at 13:03

First, let's count the number of distinguishable arrangements of the word MATHEMATICS, which has eleven letters. We can fill two of the eleven positions with an M in $\binom{11}{2}$ ways. We can fill two of the remaining nine positions with an A in $\binom{9}{2}$ ways. We can fill two of the remaining seven positions with a T in $\binom{7}{2}$ ways. The five remaining letters can be permuted in $5!$ ways. Hence, the number of arrangements of the letters of the word MATHEMATICS is $$\binom{11}{2}\binom{9}{2}\binom{7}{2} \cdot 5! = \frac{11!}{9!2!} \cdot \frac{9!}{7!2!} \cdot \frac{7!}{5!2!} \cdot 5! = \frac{11!}{2!2!2!}$$ From these arrangements, we must exclude those in which two adjacent letters are the same.

We use the Inclusion-Exclusion Principle.

Consider those arrangements in which two adjacent letters are the same. Suppose, for example, that the two A's are consecutive. Place them in a box. We now have ten objects to arrange, the other nine letters in the word MATHEMATICS and the box containing the two A's. We can select two of the ten positions for the M's in $\binom{10}{2}$ ways, two of the remaining eight positions for the T's in $\binom{8}{2}$ ways, and arrange the other six objects in $6!$ ways. Thus, the number of arrangements in which the two A's are adjacent is $$\binom{10}{2}\binom{8}{2} \cdot 6! = \frac{10!}{2!2!}$$ An analogous argument applies to the two M's and two T's. Since there are three ways of choosing the pair of adjacent letters that are the same, the number of arrangements in which two consecutive letters are the same is $$\binom{3}{1} \cdot \frac{10!}{2!2!}$$

Next, we count those arrangements in which two adjacent letters are the same and two other adjacent letters are the same. Suppose, for example, that the two A's are adjacent and the two M's are adjacent. Place the A's in an amber box and the M's in a maroon box. We now have nine objects to arrange, the two boxes, two T's, and the other five letters. We can select two of the nine positions for the T's in $\binom{9}{2}$ ways, then arrange the remaining seven objects in $7!$ ways. Hence, the number of arrangements in which the two A's are adjacent and the two M's are adjacent is $$\binom{9}{2} \cdot 7! = \frac{9!}{2!}$$ Since there are $\binom{3}{2}$ ways to select two adjacent letters that are the same and two other adjacent letters that are the same, the number of arrangements of the word MATHEMATICS in which two adjacent letters are the same and two other adjacent letters are the same is $$\binom{3}{2} \cdot \frac{9!}{2!}$$ Finally, we count those arrangements in which the two A's are adjacent, the two M's are adjacent, and the two T's are adjacent. Place the A's in an amber box, the M's in a maroon box, and the T's in a turquoise box. We then have eight objects to arrange, the three different color boxes and the five other letters. They can be arranged in $8!$ ways.

Thus, by the Inclusion-Exclusion Principle, the number of distinguishable arrangements of the word MATHEMATICS in which no two adjacent letters are the same is $$\frac{11!}{2!2!2!} - \binom{3}{1} \cdot \frac{10!}{2!2!} + \binom{3}{2} \cdot \frac{9!}{2!} - 8!$$

My thanks to Barry Cipra for making me aware of the flaws in my first attempt to solve the problem.

• Where in this approach is the arrangement AMTAMTCEHIS created? – Barry Cipra Mar 17 '16 at 12:57
• It isn't. My approach does not work. – N. F. Taussig Mar 17 '16 at 13:01
• @BarryCipra Thank you for pointing out the flaws in my first attempt at the problem. After you forced me to rethink the problem, I decided to use the Inclusion-Exclusion Principle. – N. F. Taussig Mar 17 '16 at 13:58
• i thought it might be inclusion-exclusion. – miniparser Mar 17 '16 at 14:02
• @N.F.Taussig, I took a different route and believe I got the same final count. Please see the remark at the end of my answer. – Barry Cipra Mar 17 '16 at 15:19

Let's lay out the problematic letters A, M, and T first and then make sure they get separated.

Without restriction, there are ${6\choose2,2,2}={6!\over2!2!2!}=90$ ways to arrange $2$ A's, $2$ M's, and $2$ T's. Among these $6$ arrangements have all three letters doubled up (e.g., AAMMTT), $18$ have two letters doubled up (e.g., TAATMM), $36$ have one letter doubled up (e.g., TMAAMT), and $30$ have no letters doubled up (e.g., AMTMAT). Each of these counts requires a bit of thought, but I'll take them as given.

We now need to wedge in the remaining five letters, C, E, H, I, and S, in a way that busts up any doubled-up letters. Let's do one example carefully and then summarize the rest.

Suppose we have MMTTAA. Our first three wedge-in will bust up the pairs by attaching something immediately to the right of the first occurrence of each letter, i.e., (Mx)M(Ty)T(Az)A. This can be done in $5\times4\times3$ ways. The remaining two letters must then be wedged in among these $6$ groupings, and this can be done in $7\times8$ ways, for a total of $(5\times4\times3)\times(7\times8)$ arrangements.

If there are two doubled letters, the same approach gives of total of $(5\times4)\times(7\times8\times9)$ arrangements, and if there is only one doubled letter, it's $5\times(7\times8\times9\times10)$. Finally, if there are no doubled letters, the remaining $5$ letters can be wedged in in ($7\times8\times9\times10\times11)$ ways.

To wrap things up, we just have to multiply these counts by their occurrences and add everything up:

$$6\times(5\times4\times3)\times(7\times8)+18\times(5\times4)\times(7\times8\times9)+36\times5\times(7\times8\times9\times10)\\+30\times(7\times8\times9\times10\times11)$$

If I've done all the arithmetic correctly, the final answer is $2{,}772{,}000$.

Remark: N. F. Taussig's inclusion-exclusion approach leads to the same final answer, so I am somewhat more confident in my arithmetic. It's a bit curious that $2{,}772{,}000=11\times10\times5\times7!$. In particular, the answer is divisible by $11$, the total number of letters, even though neither approach makes it obvious that that should be the case. So I wonder if that's purely coincidental, or if there is some approach to the count that does make it obvious that the answer is divisible by the number of letters involved.

• I do not know an argument for why the answer should be divisible by $11$ either, but it is an interesting observation. I see you found a valid way to do what I initially tried to do. – N. F. Taussig Mar 17 '16 at 15:37
• @N.F.Taussig, I'm thinking now it's just coincidence. I did a quick calculation with two more (different) letters, and the answer there is not divisible by $13$. – Barry Cipra Mar 17 '16 at 16:56
• Isn't the first part, viz "...... $36$ have one letter doubled up .... $30$ have no letters doubled up ..." the tedious part unless you have some clever method of counting them ? – true blue anil Mar 23 '16 at 8:59
• @trueblueanil, I don't know about clever, but I was able to do those counts in my head. Given that each type of arrangement involves the $6$ permutations of the three letters, the "hard" numbers to count are $1$, $3$, $6$, and $5$. – Barry Cipra Mar 23 '16 at 13:18
• Nice unconventional approach ! (+1) – true blue anil Mar 24 '16 at 4:05

The word contains $\bf{2M,2A,2T,H,E,I,C,S}$

Use inclusion-exclusion to compute
[All ways] - [at least $1$ pair together] + [at least $2$ pairs together] - [all $3$ pairs together]

$= \dfrac{11!}{(2!)^3} - \dbinom31\dfrac{10!}{(2!^2} +\dbinom32\dfrac{9!}{2!} - {8!}$

• Oh, I see Taussig has given basically the same approach $5$ minutes ago ! (+1) – true blue anil Mar 17 '16 at 14:03

$5!{6\choose {2,2,2}}=5!{6\choose 2}{4\choose 2}{2\choose 2}$

fill the gaps between letters $h,e,i,c,s$ $2$ at a time combined with all orderings of $h,e,i,c,s$. simplifies to same answer of $5!{{6!}\over{2!2!2!}}$

• As Barry Cipra pointed out to me, this approach does not count the arrangement ATMTAMCEHIS. – N. F. Taussig Mar 17 '16 at 14:00

Here are two solutions generated using this tool of careerbless.com [see generated question no.24 with the word 'MATHEMATICS') Hint an alternative to check the correctness do parts it is safest . \begin{align*} \text{total arrangements} & - \text{ways where all letters M,A,T are together with the same letters}\\ & - \text{ways where M,T are together}\\ & - \text{ways where A,T are together}\\ & - \text{ways where A,M are together}\\ & - \text{ways where M are together}\\ & - \text{ways where A are together}\\ & - \text{ways where T are together} \end{align*} though its not healthy and competitive approach it ensures that all cases are taken.

• There are formatting problems with your answer. I suggest you write your formula on separate lines since it runs off the edge of the screen. – N. F. Taussig Mar 17 '16 at 12:43
• Should i write without latex looks ugly – Archis Welankar Mar 17 '16 at 12:48
• What I was thinking was separate lines in $\LaTeX$. – N. F. Taussig Mar 17 '16 at 12:50
• Please Can you tell me hows it done i dont know it :( sorry – Archis Welankar Mar 17 '16 at 12:52
• @TonyK Let me do the calculation, then: We have 10 letters (we are counting AA as a single letter), with 2 M's and 2 T's). Because we can swap the 2 T's or the 2 M's and not change our word, the total number is $10!/(2!2!)$. – Aaron Mar 17 '16 at 13:46