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!
$\begingroup$
$\endgroup$
6
-
$\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 MitraNov 13, 2011 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$– abcinmoreNov 13, 2011 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 MitraNov 13, 2011 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$– abcinmoreNov 13, 2011 at 18:15
-
$\begingroup$ Yes, joriki's approach is much better $\endgroup$– David MitraNov 13, 2011 at 18:24
|
Show 1 more comment
6 Answers
$\begingroup$
$\endgroup$
1
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
$\begingroup$
$\endgroup$
1
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).
answered Nov 14, 2011 at 14:23
$\begingroup$
$\endgroup$
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 .
answered Nov 13, 2011 at 18:06
$\begingroup$
$\endgroup$
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)!$.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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)