1
$\begingroup$

$n_{1},...,n_{m}$ are nonnegative integers

$n = n_{1}+...+n_{m}$

$W[n_{1},...,n_{m}]$ denotes the # of ways to place $n$ balls (of labels $1, 2, . . . , n$) into $m$ boxes $B_{1},...,B_{m}$ such that there are $n_{1}$ balls falling into $B_{1}$,..., $n_{m}$ balls falling into $B_{m}$

I am trying to show that for m = 2, $W[n_{1},n_{2}]$ = $n \choose n_{1}$<--- what does this mean? Does it mean the # of ways to place 2 balls in 2 boxes is equal to the sum of $n_{1}+...+n_{m}$ choosing 1 ball? Btw, multinomial coefficient was never taught in class and now I have to show/prove a bunch of stuff. Would be glad to get some understanding/clarification. Thanks!


This is my attempt:

So, from the statement above, there is one way to put $n_{m}$ balls into $B_{m}$ boxes? $W[n_{1},n_{2}]$ will be the # of ways to place 2 balls into 2 boxes [with 1 ball in each box]?

Since m = 2, there are 2 balls and 2 boxes and $n_{1}+n_{2} \choose n_{1},n_2{}$ $\equiv$ $n \choose n_{1}$ $\equiv$ $n \choose n_{2}$.

Hence, $W[n_{1},n_{2}]$ = $n \choose n_{1}$ <--- what does this mean?

$\endgroup$
2
$\begingroup$

$$\binom{n}{n_1} = \frac{n!}{n_1!(n-n_1)!}$$ in terms of a formula. One conceptual interpretation that is relevant to this problem is that this is the number of ways to throw $n_1$ labeled balls into one box. Notice that if you have two boxes, then you are left with $n-n_1$ balls and there are $$\binom{n-n_1}{n-n_1} = 1$$ ways to place the other balls in the other box. In other words, you are forced to throw the rest of the balls into the other box.

As for the multinomial coefficient notation, it is $$\binom{n}{n_1,n_2,\dotsc,n_k} = \frac{n!}{n_1!\cdot n_2!\dotsm n_k!}$$ where $n = n_1+\dotsb+n_k$.

Another point regarding notation is $$\binom{n}{n_1} = \frac{n!}{n_1!(n-n_1)!} = \frac{n!}{n_1!n_2!} = \binom{n}{n_1,n_2}.$$ So, instead of using the multinomial coefficient notation, you usually just use the binomial coefficient notation. Also, $$\binom{n}{n_1} = \frac{n!}{n_1!n_2!}= \frac{n!}{n_2!(n-n_2)!} = \binom{n}{n_2}$$ which I think you showed.

Finally, suppose $n = n_1+n_2$. Then regarding your question there are $m = 2$ boxes, but there are $n = n_1+n_2$ labeled balls. Then the number of ways to throw $n_1$ labeled balls into boxes (and the rest in the other) is $$\binom{n}{n_1}\binom{n-n_1}{n_2} = \frac{n!}{n_1!(n-n_1)!}\cdot\frac{(n-n_1)!}{n_2!(n-n_1-n_2)!} = \frac{n!}{n_1!n_2!0!} =\frac{n!}{n_1!n_2!} = \binom{n}{n_1}.$$

$\endgroup$
  • $\begingroup$ thanks! that was very helpful! $\endgroup$ – misheekoh Feb 1 '16 at 3:05
  • $\begingroup$ Shouldn't the equation in the last row be: $$\binom{n}{n_1}\binom{n-n_1}{n_2} = \frac{n!}{n_1!(n-n_1)!}\cdot\frac{(n-n_1)!}{n_2!(n-n_2)!} = \frac{n!}{n_1!n_2!} = \binom{n}{n_1}.$$ $\endgroup$ – misheekoh Feb 1 '16 at 3:25
  • $\begingroup$ @misheekoh No. What you have is $$\frac{n!}{n_1!(n-n_1)!}\cdot\frac{(n-n_1)!}{n_2!(n-n_2)!} = \frac{n!}{n_1!n_2!n_1!}\neq \binom{n}{n_1}. $$ $\endgroup$ – Em. Feb 1 '16 at 3:32
  • $\begingroup$ Your equation would be right if m = 3 $$\binom{n}{n_1}\binom{n-n_1}{n_2} = \frac{n!}{n_1!(n-n_1)!}\cdot\frac{(n-n_1)!}{n_2!(n-n_1-n_2)!} = \frac{n!}{n_1!n_2!(n-n_1-n_2!)} = \binom{n}{n_1,n_2,n_3}.$$ $\endgroup$ – misheekoh Feb 1 '16 at 3:36
  • 2
    $\begingroup$ @misheekoh Also, I was just making some clarifications about the binomial and multinomial notation. Meaning, they might want you to do $$\binom{n}{n_1,n_2} = \frac{n!}{n_1!n_2!} = \frac{n!}{n_1!(n-n_1)!} = \binom{n}{n_1}$$ $\endgroup$ – Em. Feb 1 '16 at 3:38
0
$\begingroup$

It means number of ways to select $n_1$ things from total $n$ things its same as $nCn_1=\frac{n!}{n_1!(n-n_1)!}$

$\endgroup$

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.