4
$\begingroup$

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.

  • 0
    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?2011-05-27

3 Answers 3

2

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

  • 0
    @user11452,$ $it$ $doesn't$ $make sense to ask whether a single problem is NP-complete, only a family of problems. If the number of containers is fixed, I think this method solves the problem in time polynomial in the input, so it's in P. The subset sum problem would arise if each container had to be full to the brim or else empty, the number of containers being allowed to increase without bound. And that problems just asks whether there is a way to fill the containers, not how many ways.2011-06-03
5

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?

  • 0
    $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}$.2011-05-28
3

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

  • 0
    @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.2013-07-29