Distribution of $n$ balls to 10 cells; Inclusion-exclusion problem

So I got another ( :[ ) problem I got stuck with. So before I get going with that, I would like to know if you know any places where I can learn the principles of these subjects (compositions, inclusion-exclusion, etc') online?

So the question: How many ways are there to distribute $n$ balls to 10 cells, so the first and second cells will have at least 4 balls, the third, fourth and fifth have at most 3 balls.

So for the first step I said I put 4 balls in each of the first and second cells, so now we have $n-8$ balls, and we got $|U|={n-8+9 \choose 9}={n+1 \choose 9}$ ways to distribute the rest of the balls to the 10 cells. I got all messed up with the rest :\

Thanks in advance for any help!

You’re off to a good start; now you have to account for the upper bound on the numbers of balls in the third, fourth, and fifth cells. This requires an inclusion-exclusion argument.

First count the distributions that exceed the limit on cell $3$, i.e., that have at least $4$ balls in cell $3$. Put $4$ balls in cell $3$ (and of course $4$ in each of the first two cells as well), so that you’re distributing $n-12$ balls; you can do this in $\binom{n-3}9$ ways. There are also $\binom{n-3}9$ distributions that violate the upper limit on cell $4$ and another $\binom{n-3}9$ that violate the upper limit on cell $5$, so the next approximation to the desired number is

$$\binom{n+1}9-3\binom{n-3}9\;.\tag{1}$$

Unfortunately, every distribution that violates two of the upper limits is subtracted twice in $(1)$ and therefore counted $-1$ times. You want to count such distributions $0$ times, so you need to add those back in. How many are there that violate the upper limit on cells $3$ and $4$? Place $4$ balls in each of cells $1,2,3$, and $4$, and distribute the remaining $n-16$ arbitrarily; you can do this in $\binom{n-7}9$ ways. And there are $\binom32$ pairs of cells with upper bounds, so you need to add this quantity back in $\binom32$ times:

$$\binom{n+1}9-3\binom{n-3}9+\binom32\binom{n-7}9\;.$$

One more correction is needed, to fix up the count for the distributions that violate all three of the upper bounds; can you make that one yourself?

• Is it ${n-11 \choose 9}$? Subtracted ${3 \choose 3}$ times? – ohad May 12 '13 at 19:52
• @ohad: It is indeed. – Brian M. Scott May 12 '13 at 19:53
• Thanks Brian, once again! You are truly great. – ohad May 12 '13 at 19:54
• @ohad: You’re welcome. (And thank you.) – Brian M. Scott May 12 '13 at 19:55

Hint: Use generating functions. We can work directly with the problem as is, or put $4$ balls into each of the first two cells. Then we have the problem of distributing $m=n-8$ balls into $10$ cells, with at most $3$ in each of the last three. We will take that approach.

The generating function for this problem is $$(1+x+x^2+x^3+x^4+\cdots)^{7} (1+x+x^2+x^3)^3.$$ To make it easier to find the coefficient of $x^m$, use the formula for the sum of a finite geometric progression to simplify this to $$(1-x^4)^3 (1-x)^{-10}.$$ Then expand $(1-x^4)^3$ and write down the general binomial theorem expansion of $(1-x)^{-10}$. Out of this we can find an expression for the coefficient of $x^m$.

• Thank you for the unique solution. This problem is specifically instructing it should be solved with inclusion-exclusion. Although this solution is very interesting and elegant (and I now understand the possible usage of generating functions). So thank you very much – ohad May 12 '13 at 19:58
• @ohad: You are welcome. It wasn't clear what technique was desired. Thought I would mention the "general" generating function approach. Generating functions are not necessarily all that great, they can change a difficult counting problem into another difficult counting problem. One advantage is that software can be used to calculate coefficients. – André Nicolas May 12 '13 at 20:04