Number of partitions of $50$

It is known --- and it is a difficult and famous result proven by Hardy and Ramanujan --- that the number of partitions of $n$ is approximately (when $n$ is large) given by $p(n) \sim \frac{ e^{ \pi\sqrt{2n/3} } }{4n\sqrt{3} }$. With $n = 50$, this yelds $p(50) \sim 217590$.

Bad news : there is no useful closed form of $p(n)$. But you can also compute it with the well-known recurrence formula

$$p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) - ... $$

where $1,2,5,7,12$ are the (generalized) pentagonal numbers.

For $n=50$ this could be done with the help of a computer.

(edit : well, as Theophile mentioned, there are tables up to $p(250)$ and more. Also, the sign mistake in the Euler recurrence has been corrected. Thanks !)

According to the table at OEISWiki, the partition number of $50$ is $204226$.

You can solve this problem using Euler's recursion.

It tells you that $p_n=\sum\limits_{i\neq 0}^{}(-1)^{i-1} p_{n-i(3i-1)/2}$.

Of course the function $f(x)=x(3x-1)/2$ is positive everywhere except $(0,1/3)$ so this is a good recursion. Also note that $p_n$ is defined to be $0$ for negative values.

We can use this recursion to calculate $p_n$ from the previous values in time $\mathcal O(\sqrt n)$ , so we can certainly obtain $P_n$ from scratch in time $\mathcal O(\sqrt n n)$

Here is some c++ code:


#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

const int MAX=100;
lli P[MAX];

int main(){
    P[0]=1;
    for(int a=1;a<MAX;a++){
        for(int b=-2*sqrt(a); b<= 2*sqrt(a); b++){// do recursion with all possible pentagonal numbers
            if( (b*(3*b-1) )/2 > a || b==0  ) continue;
            if(b%2) P[a]+= P[a- (b*(3*b-1) )/2];
            else P[a]-= P[a- (b*(3*b-1) )/2];
        }
    }
    printf("%lld\n",P[50]);
}

The output is $204226$