# Number of ways to distribute n numbered balls into r boxes without summing over all distributions?

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?

• Can a box be empty? and are the boxes numbered too? – Tryss Aug 8 '15 at 11:09
• Its ok if no box is empty or some is empty. A formula in either situation is good. Yes, the boxes are numbered! – 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.
• 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. – user2908112 Aug 8 '15 at 14:40
• 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. – user2908112 Aug 8 '15 at 15:12
• 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$. – Jack's wasted life Aug 8 '15 at 15:18
• 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$$? – Jack's wasted life Aug 8 '15 at 15:36