A seemingly simple combinatorial problem

[tanujkush]

Hi,

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

x1+2x2+3x3+..+pxp=p+1

where p is a positive integer.

This problem came about as an effort to solving another problem, which is posted here:
http://www.physicsforums.com/showthread.php?t=339103

Any help is greatly appreciated guys, thanks in advance!

[ramsey2879]

Hi,

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

x1+2x2+3x3+..+pxp=p+1

where p is a positive integer.

This problem came about as an effort to solving another problem, which is posted here:
http://www.physicsforums.com/showthread.php?t=339103

Any help is greatly appreciated guys, thanks in advance!

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.

[tanujkush]

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.

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

x1+x2+...+xp=r

are

r+p-1Cp-1

But what do I do when the coefficients in this equation are not all unity?

[ramsey2879]

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

x1+x2+...+xp=r





are

r+p-1Cp-1

But what do I do when the coefficients in this equation are not all unity?
Since X_{i}*n = n+n+n+... 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 x_i if that is what you mean, then I dont see that there is any answer but 1!!

[CRGreathouse]

See Sloane's A000041 (http://www.research.att.com/~njas/sequences/A000041). Specifically, the number of solutions in nonnegative integers to
x1+2x2+3x3+..+pxp=p+1
is A000041(p+1) - 1.

[srijithju]

Since X_{i}*n = n+n+n+... 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 x_i if that is what you mean, then I dont see that there is any answer but 1!!

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 .

[ramsey2879]

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 .

Because the x_i 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.

[ramsey2879]

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

x1+x2+...+xp=r

are

r+p-1Cp-1

But what do I do when the coefficients in this equation are not all unity?

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.

[tanujkush]

Because the x_i 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.

I'm afraid this wont work ramsey, since in finding the number of solutions to the equation
x1+2x2+3x3+...+pxp=p+1,

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

x1+2x2+3x3=4,

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,

x1+x2+x2+x3+x3+x3=4,

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.



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.

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

[CRGreathouse]

@ CRGreathouse could you please explain what it is that is mentioned on that link? Is it a library or a derivation or...?

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 = 36167251325636293988820471890953695495016030339315 65042208186860588795256875406642059231055605290691 6435143.

[ramsey2879]

I'm afraid this wont work ramsey, since in finding the number of solutions to the equation
x1+2x2+3x3+...+pxp=p+1,

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

x1+2x2+3x3=4,

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

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.



Thanks for all the inputs though


Glad to be of help