Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

5 Answers 5

up vote 2 down vote accepted

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.

share|improve this answer
    
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

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.

share|improve this answer
    
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$.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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