1
$\begingroup$

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 ?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – user2345215 Feb 28 '14 at 16:36
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But this is a general formula right? So $r_i`s$ are not fixed. $\endgroup$ – OBDA Feb 28 '14 at 17:33
  • $\begingroup$ All $r_i$'s with $r_1+...+r_k=n$ are considered. Each gives you one summand. $\endgroup$ – Greg P. Feb 28 '14 at 17:35
  • 1
    $\begingroup$ You can formulate it all more elegant using multiindices: en.wikipedia.org/wiki/Multiindices $\endgroup$ – Greg P. Feb 28 '14 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.