# Number of ways n can be written as sum of at least two positive integers

I found a solution in Python for this problem, but do not understand it. The problem is how many ways an integer n can be written as the sum of at least two positive integers. For example, take n = 5. The number 5 can be written as

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1


Here's a solution for given $$n$$.

# zero-based array (first index is 0)
ways = [1, 0, ..., 0] (n zeroes)

for i in 1, ..., n-1:
for j in i, ..., n:
ways[j] = ways[j] + ways[j-i]

print ways[n]


This solution is elegant and efficient, but unfortunately, I do not understand the logic. Can someone please explain the logic of this solution to the problem? Is there a way to make this algorithm easy to understand?

Let us denote the array ways after $$t$$ iterations of the outer loop by $$w_t$$. The recurrence implemented by the code is $$w_0(n) = \begin{cases} 1 & \text{if } n = 0, \\ 0 & \text{if } n > 0. \end{cases} \\ w_t(n) = \begin{cases} w_{t-1}(n) & \text{if } n < t, \\ w_{t-1}(n) + w_t(n-t) & \text{if } n \geq t. \end{cases}$$ You can prove by induction that $$w_t(n)$$ is the number of representations of $$n$$ as a sum of natural numbers between $$1$$ and $$t$$ (without regard to order). (This is also the number of representations of $$n$$ as a sum of at most $$t$$ natural numbers.)
The code returns $$w_{n-1}(n)$$, which is the number of representations of $$n$$ as an arbitrary sum of natural numbers, other than the representation $$n$$.
As an aside, if you allow the trivial representation then you get the partition function. Using Rademacher's asymptotic formula, the partition function can be computed in time $$\tilde O(\sqrt{n})$$, much faster than your $$\Theta(n^2)$$ algorithm.
• "This is also the number of representations of $n$ as a sum of at most $t$ natural numbers" Is this intuitively equivalent to the number of partitions of $n$ to numbers at most $t$ (the statement to prove with induction)? I don't quite see the relation between both statements. – narek Bojikian Dec 26 '19 at 2:51
• I was able to prove the statement by proving that the number representations of $n$ as a sum of exactly $t$ numbers is equal to the number of representations of $n-t$ as a sum of at most $t$ numbers. – narek Bojikian Dec 26 '19 at 15:53