3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes there are total 7 items. $\endgroup$ – Rockybilly Feb 13 '16 at 16:24
  • $\begingroup$ The items are not distict. So what decides how many ways are there, is actually how many items remain in each box. $\endgroup$ – Rockybilly Feb 13 '16 at 16:29
  • 2
    $\begingroup$ 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. $\endgroup$ – Michael Burr Feb 13 '16 at 16:29
  • $\begingroup$ 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. $\endgroup$ – Rockybilly Feb 13 '16 at 16:30
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Feb 13 '16 at 16:39
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rockybilly Feb 13 '16 at 16:36
  • $\begingroup$ The third solution should work quite quickly on a computer (you just need to run through a pair of arrays many times). $\endgroup$ – Michael Burr Feb 13 '16 at 17:08
  • 1
    $\begingroup$ 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. $\endgroup$ – Rockybilly Feb 13 '16 at 17:10
  • $\begingroup$ Cut and paste error! $\endgroup$ – Michael Burr Feb 13 '16 at 17:13
  • $\begingroup$ 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$. $\endgroup$ – Michael Burr Feb 13 '16 at 17:17
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rockybilly Feb 14 '16 at 18:00
  • $\begingroup$ 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). $\endgroup$ – Michael Burr Feb 14 '16 at 18:05
  • $\begingroup$ Yes, indeed. They are quite similar methods. $\endgroup$ – Rockybilly Feb 14 '16 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.