# Combination problem with constraints

You have four containers and one pitcher of water that holds 100L. Each container has different capacities with maximums of, say...70L, 45L, 33L and 11L levels respectively.

What is the formula that can be used to solve the number of all possible combinations that a total (in this case, 100L of water) can be poured among a number of containers (70L, 45L, 33L 11L), each having a different maximum level?

I have looked into the binomial coefficient, $\displaystyle \frac {n!}{r!(n-r)!}$, but this would solve for the number of combinations if the containers have the same maximums, not varying maximums.

Generating functions can solve for combinations with constraints, but what about a formula that could be plugged in straight away so that you can find just the answer to the single coefficient and total that you are looking for; not all the possible coefficients and all the possible totals for those sets. I am having trouble understanding how this can be achieved using generating functions or any other method.

Can you draw a formula to solve the number of combinations by knowing the following: the number of sets and their maximums, and the total number that can be divided among them?

Here is another example: ${[0-5] + [0-15] + [0-24] + [0-35] + [0-51]}$. The total must be 60.

-
Big pitcher! Do the containers have to be full? Presumably, it not, they still must have an integer number of litres. – André Nicolas May 27 '11 at 22:18
The partition function from number theory seems relevant to your problem: en.wikipedia.org/wiki/… – Austin Mohr May 27 '11 at 22:26
No, not all the containers need to be full. Some can even be 0. But their sum must equal the total amount. In this example, they all must be in increments of 1L. In other words, the containers can't contain a fraction of a liter such as 2.5L, but either 2L or 3L. – user11452 May 27 '11 at 22:35
The partition function looks to give all possible partitions. What would be the way to provide an equation (like the binomial formula) to solve the number of possible combinations of partitions with a set number of sections (containers) that have constraints? – user11452 May 27 '11 at 22:56

Another approach is inclusion-exclusion. If you didn't have the constraints you would just be asking for the number of solutions in non-negative integers to $$a+b+c+d=100$$ which is ${103\choose3}$. But you have to throw away the solutions with $a\ge71$, which is $a-71\ge0$. Let $a'=a-71$; then you're throwing away solutions to $$a'+b+c+d=29$$ of which there are ${32\choose3}$. Similarly, you have to throw away the solutions with $b\ge46$, the ones with $c\ge34$, and the ones with $d\ge12$. This gets you down to $${103\choose3}-{32\choose3}-{57\choose3}-{69\choose3}-{91\choose3}$$ But you've thrown away some solutions twice; for example, those with both $b\ge46$ and $c\ge34$. You have to put them back. These correspond to solutions of $$a+b'+c'+d=20$$ of which there are ${23\choose3}$. Similarly for those solutions with $b\ge46$ and $d\ge12$, and those with $c\ge34$ and $d\ge12$, and those with $a\ge71$ and $d\ge12$. All told, that's 4 binomial coefficients you have to add back in. Finally, there are the solutions with $b\ge46$ and $c\ge34$ and $d\ge12$; these were counted originally, then thrown out three times, then put back in three times; they must be thrown out once more, so there's one more binomial coefficient to subtract, the one corresponding to $$a+b'+c'+d'=8$$ which is ${11\choose3}$.

-
Excellent! I want to be sure I understand this. Why are some solutions thrown away twice and how do you know the right ones to add back, like the four pairs; as b and c? Why not a and c? Then, 3 are known to be counted, thrown out 3 times, and added back. How do you know the solutions to add or subtract from the total solutions? I have been using different variables and numbers, visualizing the problem, but am having a little difficulty understanding why. This is very close to a general formula or method and of the best I've seen thus far that I understand. Thank you! – user11452 May 28 '11 at 23:13
What's going on here is called The Principle Of Inclusion-Exclusion and can be found under that name in many textbooks and undoubtedly on many websites, where it will be explained in greater detail and with more clarity than I can achieve here. It's worth learning about, as it has many applications beyond the kind discussed here. – Gerry Myerson May 29 '11 at 0:26
Thank you for your help. I'll research and hopefully understand more of the small details! – user11452 May 29 '11 at 2:14
I've looked into P.I.E. I understand the basics. Most examples have all the sets intersecting each other. In your example, not all intersections are included. "a" does not intersect b and c, while it does with d. Why does "a" intersect d, and not b or c? I still do not understand why all sets should not intersect each other in order to solve this problem. Thank you! – user11452 May 29 '11 at 21:46
You do have to consider all possible intersections, but in some applications (including this one), some of those intersections are empty. There are no solutions to $a+b+c+d=100$ with $a\ge71$ and $b\ge46$, right? – Gerry Myerson May 30 '11 at 2:03

So you're asking for an easy way to find the number of solutions in non-negative integers to $a+b+c+d=100$, $a\le70$, $b\le45$, $c\le33$, $d\le11$. Let's do it the hard way and then see what the answer tells us. What we want is the coefficient of $x^{100}$ in $$(1+x+\cdots+x^{70})(1+x+\cdots+x^{45})(1+x+\cdots+x^{33})(1+x+\cdots+x^{11})$$ which is $$(x^{71}-1)(x^{46}-1)(x^{34}-1)(x^{12}-1)(1-x)^{-4}$$ which is $$(1-x^{12}-x^{34}+x^{58}-x^{71}+x^{80}+x^{83}-x^{92}+\dots)(1+4x+10x^2+20x^3+\dots)$$ where the coefficients in the second bracket are the binomial coefficients $n$-choose-3. So the answer is going to be a sum/difference of 8 of these binomial coefficients. I can't think of any reason to expect there to be a simpler form for the answer, nor a simpler way to get to the answer. Can you?

-
Could you explain, please, what you mean by "n-choose-3" and "sum/difference of 8 of these binomial coefficients?" Would you show this, possibly in an example to get the final number? Thank you. – user11452 May 28 '11 at 3:37
$n$-choose-3 is the binomial coefficient $n\choose3$ for which the formula is $n(n-1)(n-2)/6$. For each of the 8 terms in the left bracket there's exactly one term in the right bracket which will make the product have $x^{100}$, e.g., $-x^{92}$ in the left goes with the term in $x^8$ on the right, which is ${11\choose3}x^8$, so one of the 8 terms in the answer will be $-{11\choose3}$. – Gerry Myerson May 28 '11 at 6:07

Dynamic programming can be used. Given nonnegative integers $M_j$, $j = 1 \ldots n$, let $F(y,m)$ be the number of solutions of $x_1 + \ldots + x_m = y$ with $x_j \in \{0,\ldots,M_j\}$ for each $j$. Then $F(y, 1) = 1$ for $y=0, 1, \ldots M_1$, $0$ for $y > M_1$, and $F(y, m+1) = \sum_{x=0}^{\min(y,M_{m+1})} F(y - x, m)$.

-
I see your formula, but I do not understand it. May you help me by, perhaps, using the variables in the example of the water pitcher and the constraints of the containers so I may understand? That would be helpful. – user11452 May 28 '11 at 4:00
OK, you have $M_j = 70, 45, 33, 11$ for $j=1,2,3,4$. $F(y,1) = 1$ for $y = 0,1,\ldots, 70$, $0$ otherwise. $F(y,2) = \sum_{x=0}^{min(y,45)} F(y-x, 1)$. Compute this for all $y$ from $0$ to $100$. It turns out to be $y$ for $y$ from $0$ to $45$, then $46$ for $y$ from $46$ to $70$, then $116 - y$ for $y$ from $71$ to $100$. Then compute $F(y,3) = \sum_{x=0}^{\min(y,33)} F(y,2)$ for $y$ from $0$ to $100$. Then $F(100,4) = \sum_{x=0}^{11} F(100-x,3)$, which turns out to be 14948. – Robert Israel May 29 '11 at 6:36
Thank you for explaining that. I will be looking into dynamic programming more so I may fully appreciate this solution! – user11452 May 29 '11 at 21:48
@RobertIsrael Dear Robert, I need to refer to your solution in a working paper about OR. Please, may you address myself to a paper/book that contains your solution so that I can cite it? Thank you in advance. R. – Roberto Trunfio Jul 29 '13 at 19:10