Integer Partitions

Integer Partitioning is a standard problem that arises in many situations. If math is what you do, then perhaps you would classify this as a simple problem. For the rest of us, it's far from straightforward.

The basic problem can be stated as follows.

For any given positive integer N, in how many different ways can it be partitioned, that is, written as sum of smaller positive integers ?

Let's define the function P(N) as the number of integer partitions of N.

For example, 4 can be written in 5 different ways (partitions)
1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
2 + 2
4

So P(4) = 5.

Note that
1. Order of integers does not matter. So 1 + 4 is considered as the same partition as 4 + 1.
2. An integer can appear multiple times in a partition.

As is often the case, if you don't already know the trick, it's not easy to figure it out. For example, the first thing I tried was using induction, as in, can P(N+1) be expressed in terms of P(N)? I couldn't find any easy way to express it. Maybe there isn't a natural way.

The common trick in solving combinatorics problems is to use the principle of mutual exclusion. But how do I break the problem down to mutually exclusive smaller problems ? I couldn't find a way, so I gave up and surrendered myself to the all-knowing Wikipedia. Sure enough, the answer is there and this time the trick is to use an intermediate function.

Well that gave me the formula, but the explanation wasn't lucid enough on the Wikipedia page. So I decided to try to explain it in much simpler way.

It's a very nice trick and worth writing about.

Let's define another function - I am calling it partial partitions - PP(N,k) as the number of integer partitions, in which the smallest addend is at least k. It's important to note the language. The smallest addend doesn't have to be k, it can be more than k. In other words, no addend can be less than k.

For PP(4,2) we have 2 partitions in which every addend is equal or greater than 2
2 + 2
4
So PP(4,2) = 2.

For PP(4,3) and PP(4,4) we have just one same partition
4
So PP(4,4) = PP(4,3) = 1

Now, note that P(N) = PP(N,1). So if we can find a formula for PP(N,k), we will be able to determine P(N).

This neat trick of considering a more general problem, allows us to use the divide and conquer strategy. Now PP(N,k) can be divided into categories.

1. Where the smallest addend is exactly k. Let's call it PP(N,=k)
2. Where the smallest addend is strictly greater than k. Let's call it PP(N,>k).

It's easy to see that the second category is same as PP(N,k+1) because every addend must be strictly greater than k, so it's at least k+1.

What about the first category ? In this, every partition has to have k as an addend. There may be more than one addend equal to k. Since every partition has k, if we remove it, then we get partitions for N-k, and each of this partition satisfies the condition that no addend is less than k. This is PP(N-k,k). A diagram might help visualize this.

We must make sure that it is indeed the case that PP(N,=k) = PP(N-k,k) for all values of 1 <= k <= N for all integers N.

Consider a partition in PP(N,=k). As we have noticed already, removing the addend k, leaves us with a partition that adds up to N-k, with every addend >= k. Since we removed the same addend k, and every partition was different no two remaining partitions can be same. So we get proper set of distinct partitions. So PP(N,=k) must be a subset of PP(N-k,k).

Now let’s try from the other side. Consider PP(N-k,k). If we add the addend k to every partition, each partition will add up to N. Since we added the same term to each partition, they still remain distinct, so we have a proper set. Also, since we added the addend k to it, every partition of course has an element that's exactly k. So this PP(N-k, k) must be a subset of PP(N,=k).

Since PP(N-k,k) and PP(N,=k) are subsets of each other, they must be equal.

Combining all this together

PP(N,k) = PP(N,>k) + PP(N,=k) because of mutual exclusion
PP(N,k) = PP(N,k+1) + PP(N-k,k) as explained above

Now this is a recursive formula, so we need terminating conditions

PP(N,k) = 0 if k > N
PP(N,k) = 1 if k = N

To wrap up,

P(N) = PP(N,1) = PP(N-1, 1) + PP(N, 2)
That’s one pretty looking formula. In such recursive formulas, like partial derangement, both the terms reduce N and k to terminate the recursion. Here, one term reduces N, while other increases k. That’s got to put a smile on your face if you like recursion!