How many ways we can choose items from different boxes

Question

I searched through the internet but couldn't find my answer, which can either be a very simple or a hard one.

Assume there are $3$ boxes, which carry, respectively, $1$, $4$, $2$ items. My question is how many ways we can select $3$ items from these boxes. I am looking for a formula rather than a solution for these specific values.

If I choose (take away) $3$ items by trying one by one. \begin{array}{c c c} 0 & 3 & 1\\ 0 & 2 & 2\\ 0 & 4 & 0\\ 1 & 1 & 2\\ 1 & 3 & 0\\ 1 & 2 & 1 \end{array}

Items remain each time, so the answer seems to be $6$ different ways. But I am not sure.

Answer 1

Observe that since the items are identical, it does not matter that there are $4$ items in the second box. Your are then asking for the number of sums $a_1+a_2+a_3=3$ where $0\leq a_1\leq 1$, $0\leq a_2\leq 3$, and $0\leq a_3\leq 2$. I will give three answers.

First, an elementary argument: We know that $a_1=0$ or $a_1=1$. If $a_1=0$, then $a_2+a_3=3$. In this case, there are three possibilities: $3+0=3$, $2+1=3$, and $1+2=3$. If $a_1=1$, then $a_2+a_3=2$ and there are still three possibilities: $2+0=2$, $1+1=2$, and $0+2=2$. This results in $6$ different options.

A more combinatorial argument: The number of ways to write $n$ as a sum of $k$ nonnegative integers is $$ \binom{n+k-1}{k-1} $$ and a discussion can be found here. So, in this case, the number of ways that $a_1+a_2+a_3=3$ (without restrictions) is $$ \binom{3+3-1}{3-1}=\binom{5}{2}=10. $$ This, however, counts too many possible sums. Suppose that we take too many from box $1$, this means that we take at least $2$ from box $1$. In this case, we can write $a_1=2+b_1$ where $b_1$ is nonnegative. Then, the initial sum becomes $b_1+a_2+a_3=1$. Using the same formula, this results in $$ \binom{1+3-1}{3-1}=\binom{3}{2}=3 $$ impossible ways. Continuing, there is no way to take too many objects from the second box, but it is possible to take too many objects from box $3$. In this case, one must take $3$ objects from box $3$, so we write $a_3=3+b_3$ where $b_3$ is nonnegative. This results in the equation $a_1+a_2+(3+b_3)=3$. There are $$ \binom{0+3-1}{3-1}=1 $$ ways for this sum to occur. We should now use the inclusion/exclusion principle to see if we've over-counted. This could happen if we take more than $1$ item from box $1$ and more than $2$ items from box $3$. Then, we have $(2+b_1)+b_2+(3+b_3)=3$, but this has no solutions as a sum of nonnegative integers cannot be negative.

Therefore, out of the original $10$ possibilities, $3+1=4$ are impossible, leaving the $6$ that we've found.

A dynamic programming-type solution: Let $N(b,s)$ be the number of ways to use the first $b$ boxes to sum to $s$. Also, write $m_i$ for the number of objects in box $i$. In your case: \begin{align*} N(1,0)&=1\\ N(1,1)&=1\\ N(1,2)&=0\\ N(1,3)&=0. \end{align*}

Then, the values in the second box can be computed as follows: $$ N(b+1,s)=\sum_{i=0}^{\min\{s,m_{b+1}\}}N(b,s-i). $$ Using this formula: \begin{align*} N(2,0)&=N(1,0)=1\\ N(2,1)&=N(1,0)+N(1,1)=2\\ N(2,2)&=N(1,0)+N(1,1)+N(1,2)=2\\ N(2,3)&=N(1,0)+N(1,1)+N(1,2)+N(1,3)=2. \end{align*}

Continuing for the third column, \begin{align*} N(3,0)&=N(2,0)=1\\ N(3,1)&=N(2,0)+N(2,1)=3\\ N(3,2)&=N(2,0)+N(2,1)+N(2,2)=5\\ N(3,3)&=N(2,1)+N(2,2)+N(2,3)=6. \end{align*}

We are interested in the value $N(3,3)=6$.

Answer 2

Here is the code that I came up with in Sage. It takes about 19 minutes that is MUCH larger than the one initially posed (1000 boxes with random values between 1 and 1000). But 100 boxes with values between 1 and 100 finished under a second. Also, if you need a particular maximum value, just change $s$ to that value.

Boxes = [randint(1,100) for i in range(1000)]
n = len(Boxes)
s = sum(Boxes)
l1 = [0] * (s+1)
l2 = [0] * (s+1)
parity = 0
for i in range(Boxes[0]+1):
    l1[i]=1
for i in range(1,n):
    if(parity == 0):
        l2[0]=l1[0]
        for j in range(1,Boxes[i]+1):
            l2[j]=l2[j-1]+l1[j]
        for j in range(Boxes[i]+1,s+1):
            l2[j]=l2[j-1]+l1[j]-l1[j-Boxes[i]-1]
        parity = 1
    else:
        l1[0]=l2[0]
        for j in range(1,Boxes[i]+1):
            l1[j]=l1[j-1]+l2[j]
        for j in range(Boxes[i]+1,s+1):
            l1[j]=l1[j-1]+l2[j]-l2[j-Boxes[i]-1]
        parity = 0
if(parity == 1):
    l = l2
else:
    l = l1

print l

Edit: I cut out one of the loops, reducing the complexity.