# Ways to put numbered balls in boxes no box being empty

I know the formula for putting $n$ identical balls in $r$ different boxes such that each box has at least 1 ball, but what is the formula for putting $n$ different balls in $r$ different boxes, no box being empty?

Thanks!

-
Is this homework? Look at the formula for multinomial coefficients (number of ways to divide $n$ objects into $r$ groups with specified sizes). – David Mitra Nov 13 '11 at 17:12
It's tangentially related to homework (trying to solve a question using this), but not a homework question specifically. I know about the multinomial formula, but the box sizes here are unspecified... – abcinmore Nov 13 '11 at 17:17
It says the number of ways to partition $n$ distinct objects into $r$ distinct groups with sizes $n_1,n_2,\ldots,n_r$ is $n!/(n_1!\cdot n_2!\cdot \cdots\cdot n_r!)$. Do you see where to go from here? – David Mitra Nov 13 '11 at 17:20
I suppose you could iterate between all possible box sizes and sum them up... but this is a bit of a scary summation! – abcinmore Nov 13 '11 at 18:15
Yes, joriki's approach is much better – David Mitra Nov 13 '11 at 18:24

You can do this by inclusion/exclusion. There are $\binom r0r^n$ ways of putting the $n$ balls into the $r$ boxes. From this we have to subtract the $\binom r1(r-1)^n$ ways of putting the $n$ balls into just $r-1$ of the boxes. To this we have to add the $\binom r2(r-2)^n$ ways of putting the $n$ balls into just $r-2$ of the boxes, and so on, so

$$a_n=\sum_{k=0}^r\binom rk(-1)^{r-k}k^n=\left.\left(q\frac{\partial}{\partial q}\right)^n(q-1)^r\right|_{q=1}\;.$$

-
This is a good answer. Thank you. – abcinmore Nov 13 '11 at 18:14

This is one of the problems (counting surjective functions from N to X) in the so-called Twelvefold way (the other 11 problems might interest you as well). The solution is $r!\left\{n\atop r\right\}$, where $\left\{n\atop r\right\}$ denotes the Stirling number of the second kind written $S(n,r)$ in the answer by leonbloy. If you need to compute these numbers explicitly, it is more efficient to use the recurrence $\left\{n+1\atop r\right\} = r \left\{n \atop r\right\} + \left\{n\atop r-1\right\}$ for $1<r<n$ with boundary conditions $\left\{n\atop1\right\} = \left\{n\atop n\right\} = 1$, than to use the summation formulas given in other answers (but don't forget to multiply by $r!$ afterwards).

-
Thank you for providing that first link! – sasha Dec 6 '11 at 15:05

This counting is related to Stirling Numbers of the second kind. Specifically,

$$S(n,r) = \frac{1}{r!}\sum_{j=0}^r (-1)^j {r \choose j} (r-j)^n$$

counts the number of ways of placing $n$ distinguishable balls in $r$ undistinguishable boxes, with no box empty (ref) - this result can be obtained by inclusion-exclusion or checked by recursion. If the boxes are distinguishable, you multiply it by $r!$ and (replacing $j=r-k$) you get joriki's answer .

-