TITLE: Counting words with three letters
QUESTION [1 upvotes]: 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!

REPLY [3 votes]: Two ways of doing it. The first follows your idea, but corrects the error:

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

REPLY [2 votes]: 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} $$

REPLY [1 votes]: 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
{"set_name": "stack_exchange", "score": 1, "question_id": 47655}