3
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – ohad May 12 '13 at 19:58
  • $\begingroup$ @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. $\endgroup$ – André Nicolas May 12 '13 at 20:04

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.