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