Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A seemingly simple combinatorial problem

  1. Sep 22, 2009 #1

    I'm looking to find the number of integral solutions to the equation:


    where p is a positive integer.

    This problem came about as an effort to solving another problem, which is posted here:

    Any help is greatly appreciated guys, thanks in advance!
  2. jcsd
  3. Sep 22, 2009 #2
    I think that from the earlier problem that you posted, you mean to limit x to a non-negative number; is that correct?
    If so you already have the partition theory that treats this problem.
    Last edited: Sep 22, 2009
  4. Sep 23, 2009 #3
    Partition theory would tell me ways of representing some integer as a sum of some other integers. But its when I place restrictions like all the even integers must appear even times that I run into troubled waters. These special cases aren't really handled as I suppose they dont submit a closed form solution.

    Yes, I mean to limit the x's to non negative integers. But I really havent been able to solve the above mentioned problem using partition theory or otherwise.

    As a starter, here is what I have:

    The number of solutions to




    But what do I do when the coefficients in this equation are not all unity?
  5. Sep 23, 2009 #4
    Since [tex]X_{i}*n = n+n+n+...[/tex] Your answer will be the same as if the coefficients were all unity.

    Sum r+p-1Cp-1 for 1<p<r

    But for particular [tex]x_i[/tex] if that is what you mean, then I dont see that there is any answer but 1!!
    Last edited: Sep 23, 2009
  6. Sep 23, 2009 #5


    User Avatar
    Science Advisor
    Homework Helper

    See Sloane's http://www.research.att.com/~njas/sequences/A000041 [Broken]. Specifically, the number of solutions in nonnegative integers to
    is A000041(p+1) - 1.
    Last edited by a moderator: May 4, 2017
  7. Sep 23, 2009 #6
    I don't get it , why should the answer be r+p-1Cp-1 , if the coefficients are different .

    Consider :
    a + b = 5

    There are 5 nonnegative integer solutions

    Now consider :
    a + 2b = 5

    the only solutions that a can take are 1,3,5 - only 3 solutions .
  8. Sep 23, 2009 #7
    Because the [tex]x_i[/tex] are specific to one of the numbers 1,2,3,or4 the sum of the x's goes from 2 to r and is every possible partition with those sums. Thus the total is the sum I gave plus 1 for r 1's which I neglected in my post.
    Last edited: Sep 23, 2009
  9. Sep 23, 2009 #8
    As an after thought I don't see how your formula works since if p = r then you have

    2r-1Cr-1 = 1 for all r. I dont see how that can be.

    Did you mean r+p-1C2p-1 ? That also cant be it, through, since Sloan's A000041 gives a different result.
    Last edited: Sep 23, 2009
  10. Sep 24, 2009 #9
    I'm afraid this wont work ramsey, since in finding the number of solutions to the equation

    the two behind x2 represents the fact that the number of times 2 occurs in the sum is multiplied by 2. So if I do x1+x2+x2, I am actually finding solutions that will be non-unique. So for example, in


    the actual solutions are (4,0,0),(2,1,0),(1,0,1),(0,2,0) which satisfy the equation as well.

    If I solve what you are saying instead,


    The number of solutions are 4+6-1C6-1=9C5=126 which is clearly wrong, and also, the solutions obtained will include cases where the repeated x2's (say) have different values. So one x2 might be one and the other might be two.

    2r-1Cr-1 for r = 3(say) is 2.3-1C3-1=5C2 which is not equal to one.

    Thanks for all the inputs though

    @ CRGreathouse could you please explain what it is that is mentioned on that link? Is it a library or a derivation or...?
  11. Sep 24, 2009 #10


    User Avatar
    Science Advisor
    Homework Helper

    The link is to an entry in Dr. Neil Sloane's encyclopedia (the OEIS). The sequence you're looking for is one less than the partition number. Methods of calculating it are mentioned in the encyclopedia entry. For example, in Pari/GP, the partition number is numbpart(n).

    So the number of nonnegative solutions to a + 2b + ... + 26z = 27 is numbpart(27) - 1 = 3009. The number of solutions to a_1 + 2a_2 + ... + 9999a_9999 = 10000 is numbpart(10000) - 1 = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435143.
  12. Sep 24, 2009 #11
    What I was trying to say was that the sum of the x's for every possible solution range from 2 to r and may be equated to p for that particular solution, For p = 4 the sum of the x's would be 4 and the only solution is (4,0,0) so using your formula, r+p-1Cp-1 for p=r=4 should be 1.

    For p = 3 the sum of the x's would be 3 for each possible solution, again there is only one solution, thus according to your formula, 4+3-1C3-1 should also be 1.

    For p = 2, the solutions are (1,0,1) and (0,2,0) or 2 solutions so in this case your formula for r = 4 and p = 2 should give 2.

    I merely summed these numbers to get an answer that should have been correct if your formula was correct, but my initial formulation omitted the term for r = p.

    Now it seems that I may be misinterpreting your formula.

    Glad to be of help
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook