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