How can I explain this integer partitions function recursion?

Question

How to explain how this algorithm works? I need to write an article about this but I can't explain why this recursion works fine.

It defines the number of partitions of a given integer

function p(sum,largest):
    if largest==0: return 0
    if sum==0: return 1
    if sum<0: return 0
    return p(sum, largest-1) + p(sum-largest, largest)

(call: p(n,n))

Thank you very much.

Answer 1

This function is the same as $F(n, k)$ which is the number of partitions of $n$ such that no element in the partition is greater than $k$ (assuming $k <= n$).

Using this function $F(n, n)$ denotes the number of partitions of $n$ as no element in the partition of $n$ can be greater than $n$.

The base conditions $F(0, k) = 1$ and $F(-m, k) = 0$ are by the definition of the partition function $P(n)$ which represents the total number of partitions of $n$ ($m > 0$). $F(n, 0) = 0$ as $n$ cannot be partitioned such that no element in the partition is greater than $0$.

Now as for the last statement in the function, think of $F(n, k)$ - the number of partitions of $n$ such that no element in a partition is greater than $k$ - as the union of two mutually exclusive sets, first set containing all the partitions such that all elements in a partition are less than $k$ and the second set containing all the partitions such that at least one element in each partition is equal to $k$.

Clearly the cardinality of first set is $F(n, k-1)$ and the cardinality of the second set is $F(n-k, k)$ because we have already chosen $k$ as an element in a partition so now we have to partition $n-k$.

Clearly the the above two sets are mutually exclusive therefore,

$F(n, k) = F(n, k-1) + F(n-k, k) $

Answer 2

Hints:

Can you actually use relatively small numbers and work through the algorithm to allow you to see what is happening?

Then, look at the area labeled 'Intermediate Function' on this web site and see if you can work through this.

You can also look at the recurrence relation here.

HTH ~A

Answer 3

The terminology largest is misleading: the idea is actually that $p(n,m)$ is the number of partitions of $n$ whose largest part is at most $m$, not the number whose largest part is $m$. This function is usually denoted by $q$, as in this reference.

Now look at the stopping conditions of the algorithm. The first one is that $p(n,0)$ is always $0$; that makes sense, since a partition has to have a positive part. Skip the next line for a moment; if $n<0\ne m$, $p(n,m)=0$; that also makes sense, since partitions of negative integers aren’t defined. The middle stopping condition says that if $m\ne 0$, then $p(0,m)=1$, which probably looks a bit odd. It turns out, however, to make life simpler if we say by convention that the integer $0$ has $1$ partition.

What’s left to explain is the actual recurrence:

$$p(n,m)=p(n,m-1)+p(n-m,m)\text{ if }m,n\ne 0\;.$$

Consider the partitions of $n$ with no part bigger than $m$.

1. Some of them actual have no part equal to $m$, either; how many of those are there?

2. The rest all have at least one part equal to $m$. Take away that part, and what’s left is a partition of what integer? And what’s the largest possible size of the remaining parts?