All possible ways to sum to a number

[Aero51]

I am curious if there is a universal formula to find all possible sums of a given number. For instance, to add to 10:
1+9
2+8
1+1+8
2+2+2+3+1, etc

I came up with a simple algorithm, but I'm sure there is something similar to Gauss's formula which can be utilized. I have heard Partitions used in number theory, but I don't know much about them beyond the fact that they are related to a similar problem.

 

[micromass]

https://en.wikipedia.org/wiki/Partition_of_a_number

 

[pwsnafu]

Yes, Rademacher's formula. See micromass's link.

 

[mathsman1963]

There's a lovely theorem by Euler about the sums of a given number:

Count the number of ways a number may be represented as a sum of distinct integers. Then count the number of ways that number may be represented as a sum of odd but not necessarily distinct integers. The number of ways is the same in both cases.

For example take the number 7. Using distinct integers 7 may be represented as

7=7
=6+1
=5+2
=4+3
=4+2+1

5 ways.

Now we try with only the odd integers removing the restriction that they be distinct

7=7
=5+1+1
=3+3+1
=3+1+1+1+1
=1+1+1+1+1+1+1

5 ways. Unfortunately I can't remember the proof and I'm too lazy to have a bash at it myself.

 

[Gackhammer]

Well here's something that might help (or not)

I did something with interative sums (liek 4 + 5 + 6, or 12+13, or 23+24+25+26+27) that always differ by one (and only integers)

So for 23, the only iterative sum is 11 + 12

For 26, its 5+6+7+8

Its basically related to the factors of the number...

Take 23 for instance... Its only factor is 1

Add 1 to the factor to get 2, then 23/2 = 11.5, then +- (1/2) from 11.5, to get 11 and 12

11 + 12 = 23

Take 35... the factors are 1,5,7,35...

So you can have a linear sum of 5 terms that revolve around 7 (5 + 6 + 7 + 8 + 9) or a linear sum of 7 terms that revolve around 5 (2+3+4+5+6+7+8)...


I can't remember the whole thing... but I remember that it was inpossible for a linear iterative sum for anything of 2^n, like 2,4,8,16...

I can't remember, I worked on it, but I can't remember what the exact thing I did...


Idk, just thought I'd mention it, since your question reminded me of it...



... or take

 

[Bacle2]

This is also called the problem of balls-in-boxes , i.e., you have n balls that you want to

put in k boxes. Line up the balls , together with the boxes. Every line-up corresponds

to an assignment of balls in boxes , e.g., if n=k , the line up : ball, box, ball, box,...

ball, box corresponds to the assignment of exactly one ball for each box. In total,

you have n+k-1 objects to assign ( n balls, k boxes, but subtract one, since

after k-1 boxes have been used, there is only one way of filling the k-th box)

any choice of k-1 spaces ( for the balls, or, by symmetry, of n spaces

where the boxes boxen? * will go ) is an assignment of balls to boxes.

There are (n+k-1) C (k-1) or (n+k-1) C n ways of doing this assignment.

If you want to guarantee that no boxes are empty, throw-in one ball on each

box and do the same process: you are left with : n+k-1-k = n-1 balls to put in

the same k-1 boxes in (n-1) C (k-1) ways.