If there are $k$ places and we have $m$ different numbers repeated $k_1, k_2, \dots, k_m$ times, then the number of ordered samples is ...

Question

I am currently studying the textbook Statistical Inference by Casella and Berger. In a section on combinatorics, the authors state the following:

In general, if there are $k$ places and we have $m$ different numbers repeated $k_1, k_2, \dots, k_m$ times, then the number of ordered samples is $\dfrac{k!}{k_1 ! k_2 ! \dots k_m !}$. This type of counting is related to the multinomial distribution, which we will see in Section 4.6.

I've been looking for a proof of this, but I've been unable to find any. I would greatly appreciate it if someone would please take the time to either provide a proof or direct me to one.

Answer 1

The simplest way to see this result is to first assume that all the numbers are different. There are therefore $k!$ arrangements.

Now suppose we make $k_1$ of the numbers the same. Then the arrangements will occur in blocks each containing $k_1!$ arrangements that we cannot tell apart. So we now have $\frac{k!}{k_1!}$ distinguishable arrangements.

Now repeat this for $k_2, k_3, ...$

We end up with the answer $$\dfrac{k!}{k_1 ! k_2 ! \dots k_m !}.$$

Answer 2

How many ways are there to arrange the letters AABBBCCCC?

1) Choose $2$ spots from $9$ for the A's ($9*8/(2*1)$)
2) Choose $3$ spots from $7$ for the B's ($7*6*5/(3*2*1)$)
3) Choose $4$ spots from $4$ for the C's ($4*3*2*1/(4*3*2*1)$)
Multiply these three fractions.