It is possible to write five as a sum in exactly six different ways:
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
How many different ways can one hundred be written as a sum of at least two positive integers?
Take 6 as an example:
It can be split into lists whose add number $ \le i, 1 \le i \le n-1 $. We can make a record of (s, i), which stands for number of summations of 's' that all add numbers less or equal to 'i' for further usage.
def solve(n):
record = {(1, 0): 0}
for s in range(1, n+1):
record[(s, 1)] = 1
for a in range(2, s):
record[(s, a)] = sum([record[(s-a, p)] for p in range(1, a+1)]) if s-a > a else 1+sum([record[(s-a, m)] for m in range(1, s-a)])
return sum([record[(n, m)] for m in range(1, n)])
[solve(i) for i in range(1, 8)]
solve(100)