12
$\begingroup$

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$
2
  • 2
    $\begingroup$ Wiki: p(100) = 190569292 (none of your options). $\endgroup$
    – Jasper
    Commented Mar 3, 2018 at 21:07
  • $\begingroup$ Where do the four options come from? $\endgroup$
    – saulspatz
    Commented Mar 3, 2018 at 21:08

3 Answers 3

13
$\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 partitions
$\endgroup$
1
  • 1
    $\begingroup$ How to modify this beautiful formula to get the number of partitions when the number of parts in every partition is restricted to be exactly k and all parts are <=m and >0? $\endgroup$ Commented Jun 21, 2019 at 10:59
6
$\begingroup$

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)$.

$\endgroup$
1
  • 1
    $\begingroup$ Using this formula is the correct way to get an estimate, as opposed to the exact solution I proposed; since it seems that's what the question is looking for, this answer is better than mine. $\endgroup$
    – Gadi A
    Commented Mar 3, 2018 at 21:59
2
$\begingroup$

Hardy and Ramanujan provided an exact answer for $p(100)$ in their 1918 paper (see image) using a simple and explicit asymptotic expansion for $p(n)$.

While the simpl$est$ asymptotic approximation formula

$$ \tag{1} p(n) \sim \frac{e^{\sqrt{\frac{2}{3}}\pi \sqrt{n}}}{4\sqrt{3} n}, \ \ \ \ \ n\to\infty $$

can be used, and is often the preferred approximation formula, it gives 199,280,893.35 as the approximate answer.

Hardy and Ramanujan's unsimplified first term is actually

\begin{equation} \tag{2} p(n) \sim \frac{e^{\pi \sqrt{\frac{2}{3}} \sqrt{n - \frac{1}{24}}}}{4\sqrt{3}\left(n-\frac{1}{24}\right)}\left(1 - \frac{1}{\pi \sqrt{\frac{2}{3}} \sqrt{n - \frac{1}{24}}}\right), \ \ \ \ \ \ \ \ n\to\infty. \end{equation}

It gives $190,568,944.783$, compared to the exact $p(100) = 190,569,292$.

I prefer formula $(2)$ for quick numerical calculations, and Euler's pentagonal number theorem for a quick exact answer.

See also Will the Real Hardy-Ramanujan Formula Please Stand Up?.

Hardy and Ramanujan's formula for calculating p(100)

$\endgroup$
1
  • 1
    $\begingroup$ What a nice paper at the end of your answer!! +1 $\endgroup$
    – Paramanand Singh
    Commented Dec 1, 2023 at 15:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .