With a direct approach I get $\sum_{A(k_1,..,k_r)} {n \choose k_1} \cdot {n-k_1 \choose k_2} \cdot ... \cdot {k_r \choose k_r} $ where
$ A(k_1,..,k_r) = $ { $k_1,..,k_r$ | $k_1+...+k_r=n$ }.

Is there any formula/theorem which I can use to write the same without any summation?

  • $\begingroup$ Can a box be empty? and are the boxes numbered too? $\endgroup$ – Tryss Aug 8 '15 at 11:09
  • $\begingroup$ Its ok if no box is empty or some is empty. A formula in either situation is good. Yes, the boxes are numbered! $\endgroup$ – user2908112 Aug 8 '15 at 14:47

Check out multinomial theorem. If $k_j$'s sum to $n$ we have $$\prod_{j=1}^r\binom{n-\sum_{i=1}^{j-1}k_i}{k_j}={n!\over\prod_{j=1}^r{k_j}!}=\binom{n}{k_1,k_2,...,k_r}$$ So your sum becomes $$ \sum_{\sum_{j=1}^rk_j=n}{n!\over\prod_{j=1}^r{k_j}!}=(1+1+\cdots+\underbrace{1}_{\text{r-th 1}})^n=r^n $$ Which makes sense since for each of the $n$ balls you have $r$ choices regarding where you can put it.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the multinimial theorem.. But the last 2 equalities doesn't hold. For example, the order of the $k_i$ balls in box i should not be counted. $\endgroup$ – user2908112 Aug 8 '15 at 14:40
  • $\begingroup$ In a box, the order in which the balls are arranged shouldn't matter. $r^n$ counts every arrangement in a box. For example, if 2 balls with number 1 and 2 are placed in box 1, then that is only one arrangement in box one. But with $r^n$ both balls 1,2 and balls 2,1 in box 1 are counted. $\endgroup$ – user2908112 Aug 8 '15 at 15:12
  • $\begingroup$ Say you have $1$ box and $2$ balls, $r^n=1^2=1$ so we don't differentiate between $(1,2),(2,1)$ which would've given us $2$. $\endgroup$ – Jack's wasted life Aug 8 '15 at 15:18
  • $\begingroup$ My God! Maybe you are right.. I must be confused like hell.. Can you prove the last 2 equalities? $\endgroup$ – user2908112 Aug 8 '15 at 15:25
  • $\begingroup$ By last two do you mean $$\prod_{j=1}^r\binom{n-\sum_{i=1}^{j-1}k_i}{k_j}={n!\over\prod_{j=1}^r{k_j}!}$$ and $$\sum_{\sum_{j=1}^rk_j=n}{n!\over\prod_{j=1}^r{k_j}!}=(1+1+\cdots+\underbrace{1}_{\text{r-th 1}})^n$$? $\endgroup$ – Jack's wasted life Aug 8 '15 at 15:36

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.