## Integer Partition With Distinct Parts

## 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.