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.

  • $\begingroup$ Perhaps you can find the answer in a book that I studied some time ago: "Combinatorial Mathematics" by N. Vilenkin. $\endgroup$
    – ajotatxe
    Mar 11, 2014 at 12:10

2 Answers 2


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.



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

  • 1
    $\begingroup$ 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$. $\endgroup$ Mar 11, 2014 at 13:59
  • 1
    $\begingroup$ @user2983638, yes. And you are right, the sign is wrong. Fixing. $\endgroup$
    – vonbrand
    Mar 11, 2014 at 14:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – user
    Jan 30, 2018 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .