A seemingly simple combinatorial problem

[tanujkush]

Hi,

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

x₁+2x₂+3x₃+..+px_p=p+1

where p is a positive integer.

This problem came about as an effort to solving another problem, which is posted here:
https://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:

x₁+2x₂+3x₃+..+px_p=p+1

where p is a positive integer.

This problem came about as an effort to solving another problem, which is posted here:
https://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 don't submit a closed form solution.

Yes, I mean to limit the x's to non negative integers. But I really haven't 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

x₁+x₂+...+x_p=r

are

^r+p-1C_p-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 don't submit a closed form solution.

Yes, I mean to limit the x's to non negative integers. But I really haven't 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

x₁+x₂+...+x_p=r





are

^r+p-1C_p-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-1C_p-1 for 1<p<r

But for particular $$x_i$$ if that is what you mean, then I don't see that there is any answer but 1!

 

[CRGreathouse]

See Sloane's http://www.research.att.com/~njas/sequences/A000041 . Specifically, the number of solutions in nonnegative integers to
x₁+2x₂+3x₃+..+px_p=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-1C_p-1 for 1<p<r

But for particular $$x_i$$ if that is what you mean, then I don't see that there is any answer but 1!

I don't get it , why should the answer be ^r+p-1C_p-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-1C_p-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 don't submit a closed form solution.

Yes, I mean to limit the x's to non negative integers. But I really haven't 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

x₁+x₂+...+x_p=r

are

^r+p-1C_p-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-1C_r-1 = 1 for all r. I don't see how that can be.

Did you mean ^r+p-1C_2p-1 ? That also can't 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 won't work ramsey, since in finding the number of solutions to the equation
x₁+2x₂+3x₃+...+px_p=p+1,

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

x₁+2x₂+3x₃=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,

x₁+x₂+x₂+x₃+x₃+x₃=4,

The number of solutions are ^4+6-1C_6-1=⁹C₅=126 which is clearly wrong, and also, the solutions obtained will include cases where the repeated x₂'s (say) have different values. So one x₂ 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-1C_r-1 = 1 for all r. I don't see how that can be.

Did you mean ^r+p-1C_2p-1 ? That also can't be it, through, since Sloan's A000041 gives a different result.

^2r-1C_r-1 for r = 3(say) is ^2.3-1C_3-1=⁵C₂ 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 = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435143.

 

[ramsey2879]

I'm afraid this won't work ramsey, since in finding the number of solutions to the equation
x₁+2x₂+3x₃+...+px_p=p+1,

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

x₁+2x₂+3x₃=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-1C_p-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-1C_3-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