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

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?

-

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.

-
Could you help me understand...it seems that i*(n +1) makes the assumption that we are only looking at cases where the container/s with more than n balls contain exactly n+1 balls...but what if we have b=20, c=5, n=4 and we could have containers with 6,7,8 etc balls? –  גלעד ברקן Nov 2 '13 at 21:45
@groovy: No, we’re looking at containers with at least that many balls. –  Brian M. Scott Nov 3 '13 at 6:05

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.

-

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

-

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

-
Thank you. Yes, that was how I got that identity. –  Mark Eichenlaub Jan 12 '12 at 14:37

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-k-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$.

-