Calculating integer partitions

Question

A partition of a positive integer $n$, also called an integer partition, is a way of writing $n$ as a sum of positive integers. The number of partitions of $n$ is given by the partition function $p(n)$ Partition (number theory). For example, $p(4) = 5$.

Now, what is $p(100)$?

a) $10^2$

b) $2^{10}$

c) $10^{10}$

d) ${(10 !)}^{2}$

I can't compute $p(100)$ .

Answer 1

There is a beautiful recursive formula which enables an extremely simple calculation of $p(n)$ given you have already calculated all the previous values. It gives $p(n)=190569292$ in our case.

The idea is to take the generating function of $p(n)$ and use a clever trick to display it as a rational function; the denominator of rational generating functions always gives a recursive formula for the sequence the generating function encodes. You can see it in Wikipedia's page about Euler's Pentagonal number theorem.

Here is the basic idea, equation wise:

• The generating fucntion: $\sum_{n=0}^{\infty}p\left(n\right)x^{n}=\prod_{n=1}^{\infty}\frac{1}{\left(1-x^{n}\right)}$

• Euler's Pentagonal theorem: $\prod_{n=1}^{\infty}\left(1-x^{n}\right)=\sum_{k=-\infty}^{\infty}\left(-1\right)^{k}x^{k\left(3k-1\right)/2}$

Combine to get the recurrence relation

$p\left(n\right)=p\left(n-1\right)+p\left(n-2\right)-p\left(n-5\right)-p\left(n-7\right)+p\left(n-12\right)+p\left(n-15\right)+\dots$

Where the $1,2,5,7,12,15\dots$ sequence is generated by the formula $\frac{k\left(3k-1\right)}{2}$ when you plugin nonzero integers (also negative numbers) for $k$ and you subtract instead of adding elements for $k$ even (e.g. 5 is generated from $k=2$ and the sum has $-p(n-5)$ instead of $+p(n-5)$).

Here's a simple Python code for computing all $p(n)$ up to a certain goal, based on the recurrence relation:

def pentagonal_number(k):
    return int(k*(3*k-1) / 2)

def compute_partitions(goal):
    partitions = [1]
    for n in range(1,goal+1):
        partitions.append(0)
        for k in range(1,n+1):
            coeff = (-1)**(k+1)
            for t in [pentagonal_number(k), pentagonal_number(-k)]:
                if (n-t) >= 0:
                    partitions[n] = partitions[n] + coeff*partitions[n-t]
    return partitions

Answer 2

The reference to the Wikipedia page in your question gives you both the value for $p(100)$, which is $190{,}569{,}292$, and a formula to approximate this number as follows $$p(n) \sim \displaystyle\frac{1}{4n\sqrt{3}}\exp\left(\pi\sqrt{\frac{2n}{3}}\right), n\to\infty$$ Plugging in $n = 100$ in this formula (using MATLAB) gives me $199{,}280{,}893$ which is close to the actual value (it probably varies so much because $100$ is no where near $\infty$).

I would imagine that calculating this by hand would be a very tedious job. If it were me, I would write a computer program to calculate $p(n)$.