Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

3 Answers 3

up vote 3 down vote accepted

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}\;.$$

share|improve this answer
    
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).

share|improve this answer
    
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 .

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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