Number of ways to distribute indistinguishable balls into distinguishable boxes of given size

Solution 1:

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} $$