Integer sum combinatorics problem

In summary, the proposed solution to finding the number of sets of non-negative integers (a,b,c,d) that satisfy 2a+b+c+d=N appears to be incorrect. The correct answer is given as 2^{N+1}-1, and this can be verified by counting the number of solutions for various values of N. It is also suggested that the number of solutions for x1+x2+...+xk=n can be found using the formula (n+k-1)C(k-1) or (n-1)C(k-1) if all xi must be greater than 0.
  • #1
henpen
50
0
Question:
Given a non-negative integer N, show many sets of non-negative integers [itex] (a,b,c,d) [/itex] satisfy [itex] 2a+b+c+d=N [/itex]

Proposed (and roadblocked) solution:

Case 1: [itex]2a=0[/itex]
Then there are [tex]\binom{N+2}{2}[/tex] solutions (easy to prove).

Case 2: [itex]2a=2[/itex]
Then there are [tex]\binom{N+2-2}{2}[/tex] solutions.

Case 3: [itex]2a=4[/itex]
Then there are [tex]\binom{N+2-4}{2}[/tex] solutions.
...

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

The answer I'm looking for is actually [itex]2^{N+1}-1[/itex], and numerically my method doesn't check. Where have I gone wrong? I'm fairly confident my analysis for each case 1 was correct.
 
Mathematics news on Phys.org
  • #2
[itex]2^{N+1}-1[/itex]?

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
  • #4
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
awkward said:
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.

My formula agrees for those cases. Thanks for the help.
 
  • #6
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)
 

1. What is an integer sum combinatorics problem?

An integer sum combinatorics problem is a mathematical problem that involves finding the number of ways to add two or more integers to reach a given sum. This type of problem often involves finding all possible combinations of integers that add up to a specific value.

2. How do I solve an integer sum combinatorics problem?

The most common approach to solving an integer sum combinatorics problem is by using a systematic counting method, such as the stars and bars method or the generating functions method. These methods involve breaking down the problem into smaller, more manageable sub-problems and then using mathematical formulas to calculate the final solution.

3. Can you provide an example of an integer sum combinatorics problem?

Sure, an example of an integer sum combinatorics problem would be: How many different ways can you roll two dice to get a sum of 7? In this case, the possible combinations are (1,6), (2,5), (3,4), (4,3), (5,2), and (6,1), for a total of 6 different ways.

4. What is the significance of integer sum combinatorics in real life?

Integer sum combinatorics has many practical applications in real life, such as in computer science, cryptography, and finance. For example, in computer science, this concept is used in programming algorithms and data compression techniques. In cryptography, it is used to develop secure encryption methods. In finance, it is used in risk management and portfolio optimization.

5. Are there any tips for solving integer sum combinatorics problems?

Some tips for solving integer sum combinatorics problems include breaking down the problem into smaller parts, using mathematical formulas and techniques, and practicing with different types of problems. It is also helpful to understand the underlying principles and patterns involved in these types of problems.

Similar threads

  • General Math
Replies
2
Views
1K
  • General Math
Replies
1
Views
710
Replies
1
Views
239
Replies
25
Views
5K
  • General Math
Replies
3
Views
698
Replies
7
Views
1K
  • General Math
Replies
16
Views
2K
Replies
6
Views
909
Replies
2
Views
1K
Back
Top