Number of ways to distribute indistinguishable balls into distinguishable boxes of given size 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.
 A: 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}
$$
A: 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.
