1
$\begingroup$

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!

  • 0
    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$.2011-06-25

3 Answers 3

3

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}.$

  • 0
    Magidin So understandable even I got it - thank you!2011-06-25
2

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} $

1

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