How many ways can $b$ balls be distributed in $c$ containers with no more than $n$ balls in any given container?

Question

I think there are $\binom{b+ c - 1}{c-1}$ ways to distribute $b$ balls in $c$ containers. (Please correct me if that's a mistake.) How does this change if I am not allowed to place more than $n$ balls in any given container?

If we call this number $N(b,c,n)$ then I can come up with

$$N(b,c,n) = \sum_{k=0}^n N(b-k, c-1, n)$$

with the base cases

$$N(b,c,n) = \binom{b+ c - 1}{c-1}$$

for $n\geq b$, and

$$N(b,c,n) = 0$$

for $n<b/c$.

Is there some better way of writing this than that recursion relation?

Answer 1

If you carry out the inclusion-exclusion argument mentioned by true blue anil in general, you get

$$N(b,c,n)=\sum_i(-1)^i\binom{c}i\binom{b+c-1-i(n+1)}{c-1}\;;$$

whether this is actually any more useful than the recurrence is another question.

Answer 2

You could use inclusion-exclusion.

I'll illustrate with a concrete case, you can then work out the formula.

Place 10 identical balls in 5 distinct containers with no more than 4 balls in any container.

We see that if left unconstrained, 1 or 2 containers may violate the restriction, so we allot 5 balls each to 1 or 2 containers, and correct for such configurations to get

C(14,4) - C(5,1)*C(9,4) + C(5,2)*C(4,4) = 381

Now generalise.

Answer 3

For $n\gt 2$ you can reduce the number of additions in the recursion if you replace

$$N(b,c,n) = \sum_{k=0}^n N(b-k, c-1, n)$$

by

$$N(b,c,n) = N(b-1, c, n)+N(b, c-1, n)-N(b-n-1, c-1, n).$$

It may not be a saving, but you can avoid multiplication and division if you replace the base cases by $N(0,c,n)=1$ and $N(b,c,n)=0$ for $b\lt 0$.

Answer 4

This is the number of solutions to $x_1+x_2+ \cdots + x_c = b$ where $0 \leq x_i \leq n$ for $i = 1, \dots, c$.

Answer 5

As Thomas pointed out, you can use generating functions to help with this problem. Also, Brian rightly notes you could use PIE and also he observes which method is more useful computationally is a different question altogether.

Below, I will produce a standard (and in my opinion still a beautiful and more expressive) argument to prove why is $N(b,c) = {{b+c-1}\choose{c-1}}$.

So, let us assume that you have got $b$ bananas you want to distribute among $c$ children. Some children can get $0$ bananas and you want to give away all $b$ bananas. Now let us imagine that you have $c-1$ "fake bananas" which are added to your initial stock giving a total of $b+c-1$ bananas. You can imagine that the bananas left to the first fake banana $c_1$ are reserved for child $C_1$. The bananas between fakes $c_i$ and $c_{i+1}$ are reserved for child $C_i$ for all $i < c-1$ and the last child gets all bananas to the right of fake banana $c_{c-1}$. Thus, the number of ways you can distribute these bananas is precisely equal to the places where you can have $c-1$ fake bananas among $b+c-1$ bananas. And the number of bananas, therefore is ${{b+c-1}\choose{c-1}}$.

I know this does not really answer your question but it is good to know about this argument in case you do not know it already.