I need to find a formula for the total number of ways to distribute $N$ indistinguishable balls into $k$ distinguishable boxes of size $S\leq N$ (the cases with empty boxes are allowed). So I mean that the maximum number of balls that we can put in each box is $S$, while the minimum number is zero.
In the case $S=N$ the result should be:
\begin{equation} \binom{N+k-1}{N} \end{equation}
Do you know the formula for the general case? Thanks in advance!
P.S.: something similar can be found here.
$\endgroup$ 12 Answers
$\begingroup$Use generating functions. For each of the boxes the alternatives are represented by: $$ 1 + z + z^2 + \cdots + z^S = \frac{1 - z^{S + 1}}{1 - z} $$ To have $N$ balls in the the $k$ boxes is the coefficient of $z^N$: \begin{align} [z^N] \left( \frac{1 - z^{S + 1}}{1 - z} \right)^k &= [z^N] (1 - z^{S + 1})^k \cdot \sum_{r \ge 0} (-1)^r \binom{-k}{r} z^r \\ &= [z^N] (1 - z^{S + 1})^k \cdot \sum_{r \ge 0} \binom{r + k - 1}{k - 1} z^r \end{align} When $N \le S$ this gives the result cited; otherwise it gives a (finite) formula in terms of binomial coefficients. Nothing simple, I'm afraid.
EDIT:
Since:
$$ \left(1-z^{S+1}\right)^{k}=\sum_{j=0}^{k}\left(-1\right)^{j}\binom{k}{j}z^{\left(S+1\right)j} $$
then the coefficient of $z^N$ in the expression is:
$$ \sum_{\begin{array}{c} \left(S+1\right)j+r=N\\ r\geq0,\,0\leq j\leq k \end{array}}\left(-1\right)^{j}\binom{k}{j}\binom{r+k-1}{k-1} $$ Observing that given $r$, we can express $j = \lfloor (N - r) / (S + 1) \rfloor$ we get the rather horrible: $$ \sum_{r \ge 0} (-1)^{\left\lfloor \frac{N - r}{S + 1} \right\rfloor} \binom{r + k - 1}{k - 1} \binom{k}{\left\lfloor \frac{N - r}{S + 1} \right\rfloor} $$
$\endgroup$ 3 $\begingroup$Since the boxes are distinguishable, when $S=N$ I think we could just multiply $\binom{N+k-1}{N}$ by $k!$ to get the desired answer.
Not sure about the case $S<N$, yet.
$\endgroup$
