# 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

• Look up the stars and bars method. You could use it on every integer from $1$ to $50$ and sum them up to get total number of partitions. – user12345 Apr 10 '17 at 14:41
• Depends on whether you count differently ordered sums as different, like 20+20+10 versus 10+20+20. stars and bars assumes order matters, and also needs to know how many summands. – coffeemath Apr 10 '17 at 14:47
• @anonymaker00010001: What you describe may count compositions of an integer, but not the partitions. – hardmath Apr 10 '17 at 14:50
• Also, you can could use Eulers recurrence formula. It says that $p(n)=p(n-1)+p(n-2)+p(n-5)+p(n-7)\ldots$ where the numbers $1,2,5,7$ are the generalized pentagonal numbers $g_k=\frac{k(3k-1)}{2}$ – Mastrem Apr 10 '17 at 14:50
• More extensive tables are found online. See for example the OEIS entry for the partition function, and the table to $1000$ there linked by David Wilson. – hardmath Apr 10 '17 at 15:02

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

• I was really looking for this kind of table. Thank you. – xyzt Apr 10 '17 at 14:58

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 !)

• I believe your approximation is off. The formula should give $p(50) \sim 217590$, not $198680$. – Théophile Apr 10 '17 at 14:56
• @xyzt Hardy-Ramanujan is not approximating to the nearest integer. – Tlön Uqbar Orbis Tertius Apr 10 '17 at 15:01
• @xyzt maybe you're referring to the series found by Rademacher? – Mastrem Apr 10 '17 at 15:07
• Your reccurance formula doesn't seem like it can possiblly be right. It seems to imply that p(n) is less than p(n-1) which is clearly absurd. – Peter Green Apr 10 '17 at 17:41
• @JorgeFernándezHidalgo More terms may be easily computable, but 10000 is a standard length for an OEIS b-file. – LegionMammal978 Apr 11 '17 at 10:44

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$

• Interesting way!! :) – xyzt Apr 10 '17 at 15:12
• Any reason for calculating up to P(100) when the goal is to find p(50)? – Peter Green Apr 10 '17 at 17:47
• @PeterGreen nope no reason, just wanted to show off – Jorge Fernández Hidalgo Apr 11 '17 at 5:42