3
$\begingroup$

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$
1
  • $\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 '14 at 12:10
5
$\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
  • 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$ – user2983638 Mar 11 '14 at 13:59
  • 1
    $\begingroup$ @user2983638, yes. And you are right, the sign is wrong. Fixing. $\endgroup$ – vonbrand Mar 11 '14 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 '18 at 15:56
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.