Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $X_n$ be the set of all word of the length $3 n$ over the alphabet $\{A,B,C\}$ which contain each of the three letters n times.

The amount of elements of $X_n$ is $\frac{(3n)!}{(n!)^3}$, but why?

I tried to split the problem into three smaller ones by only looking at the distribution of the single letters. For each one there should be $\binom{3n}{n} = \frac{(3n)!}{n!(2n)!}$ possibilities, but if this is correct, how do I get it combined? According to Wolfram Alpha $\binom{3n}{n}^3 \neq \frac{(3n)!}{(n!)^3}$.

Thanks in advance!

share|improve this question
    
You're starting from a good place: you have $3n$ slots and can start making a word by placing $n$ copies of, say, A. As you said, there are $\binom{3n}{n}$ possibilities. Now how many slots are available for B? The answer is not $3n$. –  Dylan Moreland Jun 25 '11 at 21:38

3 Answers 3

up vote 3 down vote accepted

Two ways of doing it. The first follows your idea, but corrects the error:

  1. You are right that there are $\binom{3n}{n}$ possible ways to place one of the letters. However, once you place one of the letters (say, you place all the $A$s), and you try to place the $B$s, you'll find that you do not have $3n$ positions into which the $B$s can go, because you've already used up $n$ of them. So in fact, there are only $2n$ locations remaining for the $B$'s. That means that after placing the $A$s, the number of ways in which you can place the $B$s is only $\binom{2n}{n}$. And once you place the $A$s and the $B$s, the location of the $C$s is forced. So in total you have $$\binom{3n}{n}\times\binom{2n}{n} = \frac{(3n)!}{n!(2n)!}\times\frac{(2n)!}{n!n!} = \frac{(3n)!}{(n!)^3}.$$

  2. Instead of thinking of it as three letters, think of it as $3n$ letters: $$\{A_1, A_2,\ldots,A_{n}, B_1, B_2,\ldots,B_n, C_1,\ldots, C_n\}.$$ How many ways can you arrange them? Well, $(3n)!$. Now, erase the subindices on the $A$s; that means that any way you shuffle the $A$s will correspond to the same word. So, how many different orderings of the $A$s are there? $n!$; so you've overcounted by a factor of $n!$. The same is true when you erase the indices of the $B$s, and again for the indices of the $C$s. So the total is $$\frac{(3n)!}{n!n!n!} = \frac{(3n)!}{(n!)^3}.$$

share|improve this answer
    
Magidin So understandable even I got it - thank you! –  muffel Jun 25 '11 at 21:55

If we number each occurence of a letter, e.g. $A_1, A_2,...$ there are $3n$ numbered letters rearrange, so $(3n)!$ permutations.

But permutations of the same letters ($A_1A_2$ vs $A_2A_1$) are indistinguishable, so we have $n!$ permutations of the numbering of each kind of letter. Hence you divide by $n!$ three times getting:

$$ \frac{(3n)!}{(n!)^3} $$

share|improve this answer

The number of words out of length $n$ out of which $n_1$ are of one letter and $n_2$ are of another letter etc and $n_k$ are of another letter is same as the number of arrangements of $n$ objects of which $n_1$ are of one type, $n_2$ are of another type, etc is $$\frac{n!}{n_1!n_2!\cdots n_k!}$$ Can you prove this?

Or equivalently, as others have pointed out, there are $\binom{3n}{n}$ ways to choose position of one letter, $\binom{2n}{n}$ ways of choosing positions for one of the other remaining letters, and $1$ way to put the last letter in the remaining positions. By the product rule $$\binom{3n}{n}\binom{2n}{n}\binom{n}{n} = \frac{3n!}{(2n!)n!}\cdot\frac{2n!}{n!n!}\cdot 1=\frac{3n!}{(n!)^3}$$

Also see wikipedia

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.