Number of partitions of $50$ Does someone know the number of partitions of the integer $50$? I mean, in how many ways can I write $50$ as a sum of positive integers? 
I know that there's a table by Euler, which is useful to know in how many ways you can write $50$ as a sum of $m$ different numbers, but this table stops at $m=11$, so I can't end the calculation and calculate in how many ways in which I can write $50$ as a sum of (any) different numbers. Thank you
 A: According to the table at OEISWiki, the partition number of $50$ is $204226$.
A: 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$
A: 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 !)
