# 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:

$$\binom{N+k-1}{N}$$

Do you know the formula for the general case? Thanks in advance!

P.S.: something similar can be found here.

• Perhaps you can find the answer in a book that I studied some time ago: "Combinatorial Mathematics" by N. Vilenkin. – ajotatxe Mar 11 '14 at 12:10

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

• Many thanks vonbrand. I tried to find the final formula of the coefficient. Is this what you mean? Moreover, when you say $N\geq S$ at the end of your post, probably you mean $N=S$. – user2983638 Mar 11 '14 at 13:59
• @user2983638, yes. And you are right, the sign is wrong. Fixing. – vonbrand Mar 11 '14 at 14:30
• In the second to the last expression I would suggest to express $r$ via $j$ and not the reverse. In this case the final expression would be 1) correct and 2) nice looking and rather self-explanatory. – user Jan 30 '18 at 15:56

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.