# Integer sum combinatorics problem

1. Apr 8, 2013

### henpen

Question:
Given a non-negative integer N, show many sets of non-negative integers $(a,b,c,d)$ satisfy $2a+b+c+d=N$

Case 1: $2a=0$
Then there are $$\binom{N+2}{2}$$ solutions (easy to prove).

Case 2: $2a=2$
Then there are $$\binom{N+2-2}{2}$$ solutions.

Case 3: $2a=4$
Then there are $$\binom{N+2-4}{2}$$ solutions.
...

Thus the answer should be $$\large \sum_{i=0}^{i=1+ \left \lfloor \frac{N}{2} \right \rfloor}\binom{N+2-2i}{2}$$

The answer I'm looking for is actually $2^{N+1}-1$, and numerically my method doesn't check. Where have I gone wrong? I'm fairly confident my analysis for each case 1 was correct.

2. Apr 8, 2013

### awkward

$2^{N+1}-1$?

I count 13 solutions when N=3.

0 0 0 3
0 0 1 2
0 0 2 1
0 0 3 0
0 1 0 2
0 1 1 1
0 1 2 0
0 2 0 1
0 2 1 0
0 3 0 0
1 0 0 1
1 0 1 0
1 1 0 0

3. Apr 9, 2013

4. Apr 9, 2013

### awkward

Starting with N=1, the values I get are 3, 7, 13, 22, 34, 50. I haven't checked your answer against these values-- I'll leave that up to you-- but it appears the answer given on the page you linked to is incorrect.

5. Apr 9, 2013

### henpen

My formula agrees for those cases. Thanks for the help.

6. Apr 10, 2013

### Bacle2

Maybe you're looking for the number of solutions to :

x1+x2+...+xk=n

for xi, n ≥ 0 , it is :

(n+k-1)C(k-1) , where aCb is "a choose b"

If you want all xi>0 , the number of solutions is (n-1)C(k-1)

( throw one ball in each box and then apply the first method)