1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Integer sum combinatorics problem

  1. Apr 8, 2013 #1
    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.
     
  2. jcsd
  3. Apr 8, 2013 #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
     
  4. Apr 9, 2013 #3
  5. Apr 9, 2013 #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.
     
  6. Apr 9, 2013 #5
    My formula agrees for those cases. Thanks for the help.
     
  7. Apr 10, 2013 #6

    Bacle2

    User Avatar
    Science Advisor

    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)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Integer sum combinatorics problem
  1. Combinatorical Problem (Replies: 1)

  2. Combinatorics problem (Replies: 14)

  3. Combinatorics problem (Replies: 2)

Loading...