5
$\begingroup$

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!

  • 0
    Is this homework? Look at the formula for multinomial coefficients (number of ways to divide $n$ objects into $r$ groups with specified sizes).2011-11-13
  • 0
    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...2011-11-13
  • 0
    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?2011-11-13
  • 0
    I suppose you could iterate between all possible box sizes and sum them up... but this is a bit of a scary summation!2011-11-13
  • 0
    Yes, joriki's approach is much better2011-11-13
  • 0
    Related: [About the Stirling number of the second kind](http://math.stackexchange.com/questions/79540)2011-11-13

6 Answers 6

6

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

  • 1
    This is a good answer. Thank you.2011-11-13
4

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

  • 0
    Thank you for providing that first link!2011-12-06
1

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 .

0

Let $K= NA+B$. $NA$ balls can be put in $n$ boxes in $n!^A$ ways. Balls can be put in either of two ways: $N^B and (N-B)!$ ways. Total+ $(N!)^AN^B$ or $N!^A(N-A)!$.

0

K distinct balls are K! distinct vectors of identical balls. K identical balls can be distributed in N distinct boxes such that no box is empty in (K-1)C (N-1) ways. The arrangement to distribute K! distinct balls in N boxes is K!*(K-1)C(N-1)

-1

Distribute n out of k balls in the n numbered boxes in n! ways (no box could have more than one ball). Distribute the remaining k-n balls in n^(k-n) ways (no restriction). Total arrangement =n!* n^(k-n) ways.