In how many ways can the letters of the word ELEMENTARY be permutated such that no two E's are next to each other?

Question

What I did was to separate out the 3 E's (EEE) from the word ELEMENTARY, which leaves L M N T A R Y. For no two E's to be next to each other, we can place the E's in 8 positions (between the alphabets L M N T A R Y and also before L and after Y). Firstly, since all the letters L M N T A R Y are distinct the number of ways to permute them is 7! = 5040. Then to place the 3E's in the 8 locations; firstly the first E have 8 choices to choose from, then second E has 7 choices to choose from and 3rd E has 6 choices to choose from. Then using product rule, 5040 x 8 x 7 x 6 = 1693440.

However, my answer is wrong, the method above is correct till the "7! = 5040". In the solution that was given to me, there are indeed 8 positions to place the 3 E's. However, instead of using 8 x 7 x 6, the solution used C(8,3) = 56. Then, using product rule, 5040 x 56 = 282240 ways of permutating ELEMENTARY such that no two E's are next to each other.

Why is my answer wrong? Thank you! :")

Answer 1

As you state, the difference between your answer is that you multiply by $8*6*5$ whereas the correct answer multiplies by $C(8,3)$. By definition, $C(8, 3) = \frac{8!}{3! 5!} = \frac{8*6*5}{3!}$, so your approach missed thus division by $3!$.

Essentially, your approach counted the same configuration multiple times. Let's label these 3 E's as $E_1, E_2, E_3$. Then your argument correctly shows that there are $7! * 8 * 7 * 6$ ways to arrange the letters of $E_1LE_2ME_3NTARY$ so that no $E_i$'s are adjacent. But of course, we aren't working with $E_i$, we're just working with $E$! Your counting would consider $E_1LE_2ME_3NTARY$ and $E_2LE_1ME_3NTARY$ to be different but all we did was shuffle the same letter around. That is, permuting the 3 E's doesn't lead to a new configuration. And how many permutations of 3 elements are there? $3!$ (And I'm not just excited!)

To summarize, for every correct configuration of $ELEMENTARY$, your method counts each $E_{\sigma(1)}LE_{\sigma(2)}ME_{\sigma(3)}NTARY$ as distinct while they should be the same, for $\sigma$ a permutation of $\{1,2,3\}$. There are $3!$ such permutations so you have to divide your result by $3!$ to get the correct one.

Answer 2

you have 7 letters {L,M,N,T,A,R,Y}, u have 7!=5040 ways to permute and create new string.

• Now you have 8 places total( before, after and between them) to put 3 letters. C(8,3)=56
• hence you have total ${5040 \cdot 56=282240}$ ways to create new string.
• The number of subsets of k elements from a set with n elements, denoted by ${{N}\choose{k}}$
• observe that we ask here for the number of subsets, and then the order is irrelevant. Each collection of k elements can be obtained in k! different orderings, so to obtain the number of subsets of size k, we need to take the number of ordered subsets, and divide by k!, that is $${(n \times (n-1) \times... \times(n-k+1)) \mid k! }$$
• what you have taken is number of ordered subset.
• The number of ordered subsets of k elements from a set with n elements is equal to ${n \times (n-1) \times... \times(n-k+1)}$