# How many ways we can choose items from different boxes

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.

• Yes there are total 7 items. – Rockybilly Feb 13 '16 at 16:24
• The items are not distict. So what decides how many ways are there, is actually how many items remain in each box. – Rockybilly Feb 13 '16 at 16:29
• Are the items in each box identical? If so, you're talking about the number of sums $a_1+a_2+a_3=3$ where $0\leq a_1\leq 1$, $0\leq a_2\leq 4$, and $0\leq a_3\leq 2$. Sums of this form are standard in combinatorics. – Michael Burr Feb 13 '16 at 16:29
• Yes, Michael. I guess that was the thing I was trying to convert my problem into. But if a1, a2, a3 are the items remain in each box, the sum must be 4. If not, it is correct. – Rockybilly Feb 13 '16 at 16:30
• I think the general problem you are after is this. We have $k$ boxes, labelled $1$ to $k$. The number of items in Box $i$ is $a_i$, given. We are also given a number $n$ of items we must choose. We want to find the number of solutions of $x_1+\cdots+x_k=n$ in non-negative integers, with the restriction that $x_i\le a_i$. How many ways $w_n$ are there to do this? Not a simple problem! One can easily write down a generating function for the $w_n$, but computing the coefficients is messy. – André Nicolas Feb 13 '16 at 16:39

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

• You are right, however I am currently constructing a computer program where I will deal with much bigger inputs. So I need a formula. These was just the values I came up to explain the situation. – Rockybilly Feb 13 '16 at 16:36
• The third solution should work quite quickly on a computer (you just need to run through a pair of arrays many times). – Michael Burr Feb 13 '16 at 17:08
• Forgive my dullness, but I didn't understand your last solution. How $$N(b, s)$$ is defined and how $$N(3,2) = 2$$ and $$N(3,2) = 5$$ in your explanation. – Rockybilly Feb 13 '16 at 17:10
• Cut and paste error! – Michael Burr Feb 13 '16 at 17:13
• For the calculation of $N(b+1,s)$: How many objects can be taken from the $b+1$st box? At most $s$ or the number of objects in the box. If you take $0$ objects from the $b+1$st box, then the objects must come from the remaining $b$ boxes, so you have $N(b,s)$ ways. If you take $1$ object from the $b+1$st box, then the remaining $s-1$ objects must come from the remaining $b$ boxes, so you have $N(b,s-1)$ ways. Continue adding these up until you run out of objects in the box or take $s$ objects from box $b+1$. – Michael Burr Feb 13 '16 at 17:17

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.

• Much better indeed. However, it is still not enough for the method I need. If I had found a solution in here, I would have answered this question much better. – Rockybilly Feb 14 '16 at 18:00
• Using a generating function is a nice method. I should have thought of that! (Although the code above is (more or less) computing the coefficients of the generating function). – Michael Burr Feb 14 '16 at 18:05
• Yes, indeed. They are quite similar methods. – Rockybilly Feb 14 '16 at 18:11