# How can I think of Multinomial Theorem's "urn" model by permutation language.

Can you explain me a little how to think of the relation with (1) and the permutaion language

\begin{align*}\left(\begin{array}{c} n\\ k_1,k_2,\text{...},k_n \end{array}\right)=\frac{n!}{k_1!k_2!\text{...}k_m!}\tag{1}\end{align*}

statement1:

In permutaion language, (1) is the permutation number of $n$ elements that partitioned into $k$ tuples, in each tuples they are the same, but different with each other in different tuples. The number of elements in each tuples is $,n_1,n_2,\text{...},n_k$($n_1+n_2+\text{...}+n_k=n$).

In the special case, Binomial Theorem

$(a+b)^n=(a+b)(a+b)\text{...}(a+b)$, I know it's choosing k's $a$ from n tuples $(a+b)$(think it is a box, but according to the statement1, there are $a$ and $b$ in one box, so the box is not the same as that in statement1(the tuples))

$\left(\begin{array}{c} n\\ k \end{array}\right)a^kb^{n-k}$

• Do you mean the relationship between these and the multinomial theorem that gives the expansion of $(x_1+x_2+\cdots+x_m)^n$? Or do you mean why the thing on the right of (1) counts the permutations? Commented Aug 11, 2013 at 5:09
• @AndréNicolas yes, the relation between statement1 and the expansion of ... , your first judgement. Commented Aug 11, 2013 at 5:37
• Think of expanding. The coefficient of $x_1^{k_1}\cdots x_m^{k_m}$ is just the number of ways of choosing which ones of the $n$ terms will supply the $k_1$ $x_1$'s, which ones will supply the $k_2$ $x_2$'s, and so on. Commented Aug 11, 2013 at 5:46

My comment was badly worded. Here's the correct version.

In permutation language, $\binom{n}{k_1,k_2,\ldots,k_\ell}$ is the number of ways of arranging $n$ letters, with $k_1$ copies of letter $1,$ $k_2$ copies of letter $2$, $k_3$ copies of letter $3,$ and so on. For example, ABABC is one of the $\binom{5}{2,2,1}=\frac{5!}{2!\,2!\,1!}=30$ ways to arrange two As, two Bs, and one C.

1. Arrange $n$ letters in $n!$ ways. Then, since permutations of repeated letters amongst themselves do not change the arrangement, divide by the number of such permutations.
2. An arrangement can be formed by regarding the letters as being placed into $n$ slots. Choose which $k_1$ of the $n$ slots are to contain letter $1$; then choose which $k_2$ of the $n-k_1$ remaining slots are to contain letter $2$; then choose which $k_3$ of the $n-k_1-k_2$ remaining slots are to contain letter $3$; and so on. There are $\binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\ldots$ ways to do this.
A telescoping sum is one where there is cancelation between one term and the next, leading to a big simplification. They come up often in the study of sequences. An example would be \begin{aligned}\sum_{i=1}^5\frac{1}{i(i+1)}&=\sum_{i=1}^5\left[\frac{1}{i}-\frac{1}{i+1}\right]\\ &=(1/1-1/2)+(1/2-1/3)+(1/3-1/4)+(1/4-1/5)+(1/5-1/6)\\ &=1/1+(-1/2+1/2)+(-1/3+1/3)+(-1/4+1/4)+(-1/5+1/5)-1/6\\ &=1/1-1/6.\end{aligned} One can also have telescoping products. Let's actually try writing this one out: \begin{aligned}&\binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\ldots\binom{n-k_1-\ldots-k_{\ell-1}}{k_\ell}\\ &\quad=\frac{n!}{k_1!\,(n-k_1)!}\frac{(n-k_1)!}{k_2!\,(n-k_1-k_2)!}\frac{(n-k_1-k_2)!}{k_3!\,(n-k_1-k_2-k_3)!}\ldots\frac{(n-k_1-\ldots-k_{\ell-1})!}{k_\ell!\,(n-k_1-\ldots-k_\ell)!}\\ &\quad=\frac{1}{k_1!\,k_2!\,\ldots\,k_\ell!}\cdot\frac{n!}{(n-k_1)!}\frac{(n-k_1)!}{(n-k_1-k_2)!}\frac{(n-k_1-k_2)!}{(n-k_1-k_2-k_3)!}\ldots\frac{(n-k_1-\ldots-k_{\ell-1})!}{(n-k_1-\ldots-k_\ell)!}\\ &\quad=\frac{1}{k_1!\,k_2!\,\ldots\,k_\ell!}\cdot\frac{n!}{(n-k_1-\ldots-k_\ell)!}\\ &\quad=\frac{1}{k_1!\,k_2!\,\ldots\,k_\ell!}\cdot\frac{n!}{0!}.\end{aligned}