1

Im stuck on a problem which I have answered and need help to verifiy if I have done/understood it correctly.

Problem If we have the following string: A,A,B,C,D,D,D,E,F,G How many ways are there to rearrange the letters if the Letters, E,F,G have to appear in the same order.

My approach
I first decided to find the permutation of the letters except E,F,G and deal with these 3 last. So i ended up with $\frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4}{2!\cdot3!}$
And now that there are 3 more letters left. (The last three) and that they have to appear in order, we have no choice other than placing the letters on order. i.e E,F,G

So the final answer is $\frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot1\cdot1\cdot1}{2!\cdot3!}$

Question
I would like to know if I have attempted this problem correctly. If not could you point out where i have gone wrong and/or give me some hints?

Edit
E,F,G doesn't have to appear in next to eachother

Krimson
  • 591
  • 1
    When you say "appear in order, do you mean that they have to appear like $EFG$ or do they not have to be next to each other as long as E comes (not necessarily directly) before F, which comes before G? – MT_ Feb 10 '14 at 03:31
  • @user92774 E,F,G doesn't have to appear in next to eachother – Krimson Feb 10 '14 at 04:31

4 Answers4

3

The number of ways to arrange all $10$ letters is found from the multinomial coefficient as:

$$\binom{10}{3,2,1,1,1,1,1} = \frac{10!}{3!2!1!1!1!1!1!}=302,400$$

Then for each ordering of all $10$ letters if we think of keeping all but those in the set $S=\{E,F,G\}$ fixed then there are $3!$ ways to arrange the elements in $S$. If we divide the above number by $3!=6$ we get the answer you're looking for which is $50,400$.

Patrick
  • 2,106
  • thanks for your answer, you explained it really well! just one more thing, what if the last three letters were {E,E,F}? How would I go about doing that then, would it just be the same: divide by 3! – Krimson Feb 10 '14 at 06:07
  • 1
    Not quite, first your count of the number of orderings of all $10$ letters would be slightly different since the multiplcity of $E$s went from one to two. Can you use the definition of the multinomial coefficient to figure this out? Finally you need to divide by the number of distinct orderings of ${E,E,F}$ which is also counted using the multinomial coefficients. – Patrick Feb 10 '14 at 12:40
1

You said the E, F, and G have to appear in order. Do they have to appear consecutively?

If so, then your approach started out correct; finding all the possible 7-letter words of the remaining letters and inserting the string "EFG" in various places would yield the answer. However, you would want 7-letter words:

$\cfrac{7\cdot6\cdot5\cdot4\cdot3\cdot2}{3!\cdot2!} = 420$

(so you would not start the multiplication with $10$)

After this, there are eight places to insert the string "EFG" (before the first letter, between the first and second letters, between the second and third, etc.)

So $8\cdot420 = 3360$

If E, F, and G do NOT have to appear consecutively, the problem becomes a bit more difficult.

Ivarpoiss
  • 103
  • 1
  • 2
Andrew
  • 1,008
  • 1
    A bit more difficult? Not really. First find the number of ways to place the letters EFG in between each already existing letter and then divide by 6 since only the order $EFG$ is allowed. – MT_ Feb 10 '14 at 03:36
  • @user92774, nice insight. You should write that up as an alternative answer. – vonbrand Feb 10 '14 at 03:43
  • There are already too many answers for this question. And if I were to solve it in an even better way, I would just find $\frac{10!}{2!3!}$ (permutations of all of the letters regardless of order) and divide that by $6$, as Patrick did. – MT_ Feb 10 '14 at 03:51
1

I assume that order of E,F,G would be same and E,F,G can appear anywhere in the 10 letter string, not necessarily consecutively.

So, First select 3 out of 10 positions, where to put E,F,G that would be

$$\binom{10}{3} = \frac{10.9.8}{3.2} = 120$$

Further, permuting 7 alphabets gives you 420.

So the answer would be $120*420 = 50400$

abstractnature
  • 649
0

First permute the non-ordered letters in the multiset $\{A^2, B^1, C^1, D^3\}$, which gives you $$\binom{7}{2, 1, 1, 3} = \frac{7!}{2! 1! 1! 3!} = 420$$ Next there are 8 positions for the other 3 letters, you need to pick 3 of them, for $$\binom{8}{3} = \frac{8!}{3! 5!} = 56$$ I.e., in all: $$\binom{7}{2, 1, 1, 3} \binom{8}{3} = 420 \cdot 56 = 23520$$

vonbrand
  • 27,812
  • can i please ask you, how do you write in mathematical form, I am new here, so I need help to write like this on stackexchange, I would be grateful, ty – abstractnature Feb 10 '14 at 03:32
  • I don't think this is completely right. First there would be $8$ positions assuming you mean the $6$ spots between the first $7$ letters plus the two endpoints but also you could certainly have $AAEFGBCDDD$ as a possible string which your formula wouldn't account for. – Patrick Feb 10 '14 at 03:36
  • @Patrick, thanks. Had found out my error before your comment. – vonbrand Feb 10 '14 at 03:37
  • I think this is still incorrect, there are 10 positions overall due to 10 alphabets, so for picking E, F, G you would select 3 out of 10 first, that is C(10,3) * 420. – abstractnature Feb 10 '14 at 03:39
  • @abstractnature, that is just a subset of LaTeX. Take a peek here. – vonbrand Feb 10 '14 at 03:40
  • @abstractnature, for a systematic way of handling such cases (letters that repeat) you need the enlightenment of the Tao of BOOKKEEPER. – vonbrand Feb 10 '14 at 03:42
  • @vonbrand to fix your solution, instead of multiplying by 56 multiply by $8910$ and then divide by 6. There's 8 positions for the first letter, 9 for the next, and 10 for the last. Then divide by 6 because $EFG$ is one of 6 permutations of those letters. – MT_ Feb 10 '14 at 03:53