# Show that $(u_1+u_1+…u_k)^n=\sum\limits_{r_1+r_2+…r_k=n}\dfrac{n!}{r_1!r_2!…r_k!}u_1^{r_1}u_2^{r_2}…u_k^{r_k}$

Let $r_1,...r_k$ be integers sucht that, $r_1+r_2+r_3+...,r_k=n$

The number of ways in which a subpopulation of $n$ elements can be partitioned into $k$ subpopulations of which the first contains $r_1$ elements, the second $r_2$... is $\dfrac{n!}{r_1!r_2!...r_k!}$

Now the proof is clear

$\binom{n}{r_1}\binom{n-r_1}{r_2}...\binom{n-r_1-...r_{k-2}}{r_{k-1}}=\dfrac{n!}{r_1!r_2!...r_k!}$

this is clear. but the professor said, that this can be showed by an induction (alternate proof) on $n$. He wrote this formula below, but i don't understand it

$(u_1+u_1+...u_k)^n=\sum\limits_{r_1+r_2+...r_k=n}\dfrac{n!}{r_1!r_2!...r_k!}u_1^{r_1}u_2^{r_2}...u_k^{r_k}$

Do you know, that the $u_i's$ are, or is it maybe a famous formula or so ?

• It's called the multinomial formula. What do you mean what $u_i$'s are? It doesn't matter what as long as you are in a commutative ring. – user2345215 Feb 28 '14 at 16:36

Think of the simple case (binomial formula): $(\sum_{i=0}^{2}{u_i})^2 = (u_0+u_1)^2$. The "$u_i$'s" are the summands that will be raised to the power of $n$, in this case $n=2$.
$\dfrac{n!}{r_1!r_2!...r_k!}$ ist the "multinomial coefficient" $n \choose{r_1, ..., r_k}$ and it's used to expand $(u_1+u_1+...u_k)^n=\sum\limits_{r_1+r_2+...r_k=n}\dfrac{n!}{r_1!r_2!...r_k!}u_1^{r_1}u_2^{r_2}...u_k^{r_k}$, analogous to the binomial coefficients in the binomial theorem.
• But this is a general formula right? So $r_i`s$ are not fixed. – OBDA Feb 28 '14 at 17:33
• All $r_i$'s with $r_1+...+r_k=n$ are considered. Each gives you one summand. – Greg P. Feb 28 '14 at 17:35