# Sixian Li

Algorithm

## Question

How many ways can you write an integer n as the sum of a decreasing sequence(excluding n+0)?

Let’s look at an example from Wikipedia:

Alternatively, we could count partitions in which no number occurs more than once. Such a partition is called a partition with distinct parts. If we count the partitions of 8 with distinct parts, we also obtain 6:

• 8
• 7 + 1
• 6 + 2
• 5 + 3
• 5 + 2 + 1
• 4 + 3 + 1

The problem boils down to find the number of partition with distinct parts and simply subtract 1 from it. So I’ll focus on the core part.

## Solution

Doing it by hand is easy. We choose the first element, e.g., 5, figure out 8-5=3, and try to split 3 into smaller parts. For human beings, checking “3 is less than 5” on paper happens in an instant. But we need a way to tell the computer what is the current max, so it knows possible choices for the next number.

### Recursion

#### Visualize the result

Before we directly count the total number of sequences, it helps to visualize the result. Based on the idea from StackOverflow:

Translate partition(n, maxi) into English: Parition the number n into a decreasing sequence where the first element(largest one) is no bigger than maxi.

min(n-i, i-1) is to ensure the sequence is decreasing, and the max is no more than the number itself. To see that, let $M = min(n-i, i-1) \Rightarrow M \leq i-1 \text{ and } M \leq n-i$.

This also avoids extra calculations because the size for each part can’t be more than what we have. For example, partition(5, 5) = partition(5, 14), so we don’t need to run the loop from 6 to 14.

#### Let’s count the total number

Base case is 0. When we have count_p(0, i-1), it means n=i or n=0, so the only possible partition is n = n no matter what the max is.

It works, but it’s super inefficient. To see where recalculations happen, I modified the function as below:

If these results are stored somewhere, we can avoid all recalculations and just use it.

### Dynamic Programming

Let’s decipher the highlighted line:

p[i][j]: Partition the integer i into a decreasing sequence with the first element(largest one) less than or equal to j. Here we are accumulating the result. Say we want to partition 8. After selecting 5 as the first element, we want to find all decreasing sequences starting with 4 or less that sum to 8-5=3. As long as the first element is less than 5, the sequence is valid.

p[i][j-1] +: Accumulate the result as explained above.

p[i-j][min(i-j, j-1)]: Find all valid subsequences from i-j(what’s left). This corresponds to our recursion partitoin(n-i, min(n-i, i-1)).

Finally, we can find our result at p[n][n]: partition the integer n with the starting element less than or equal to n. This is exactly what we’re looking for.

If you want to exclude n=n+0, just return p[n][n]-1.

Here’s the table from P(8). The result is at p[8, 8] = 6 as we expected.