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!

$\endgroup$
  • $\begingroup$ Is this homework? Look at the formula for multinomial coefficients (number of ways to divide $n$ objects into $r$ groups with specified sizes). $\endgroup$ – David Mitra Nov 13 '11 at 17:12
  • $\begingroup$ 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... $\endgroup$ – abcinmore Nov 13 '11 at 17:17
  • $\begingroup$ 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? $\endgroup$ – David Mitra Nov 13 '11 at 17:20
  • $\begingroup$ I suppose you could iterate between all possible box sizes and sum them up... but this is a bit of a scary summation! $\endgroup$ – abcinmore Nov 13 '11 at 18:15
  • $\begingroup$ Yes, joriki's approach is much better $\endgroup$ – David Mitra Nov 13 '11 at 18:24
6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This is a good answer. Thank you. $\endgroup$ – abcinmore Nov 13 '11 at 18:14
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thank you for providing that first link! $\endgroup$ – sasha Dec 6 '11 at 15:05
1
$\begingroup$

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 .

$\endgroup$
0
$\begingroup$

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)!$.

$\endgroup$
0
$\begingroup$

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)

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

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.