5
$\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
    $\begingroup$ Wiki: p(100) = 190569292 (none of your options). $\endgroup$ – Jasper Mar 3 '18 at 21:07
  • $\begingroup$ Where do the four options come from? $\endgroup$ – saulspatz Mar 3 '18 at 21:08
7
$\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
| cite | improve this answer | |
$\endgroup$
  • $\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$ – George Robinson Jun 21 '19 at 10:59
3
$\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)$.

| cite | improve this answer | |
$\endgroup$
  • $\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 Mar 3 '18 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.