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)$ .
$\endgroup$ 22 Answers
$\begingroup$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 partitionsThe 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)$.
$\endgroup$ 1
