9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user12345 Apr 10 '17 at 14:41
  • 1
    $\begingroup$ 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. $\endgroup$ – coffeemath Apr 10 '17 at 14:47
  • $\begingroup$ @anonymaker00010001: What you describe may count compositions of an integer, but not the partitions. $\endgroup$ – hardmath Apr 10 '17 at 14:50
  • 3
    $\begingroup$ 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}$ $\endgroup$ – Mastrem Apr 10 '17 at 14:50
  • 2
    $\begingroup$ 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. $\endgroup$ – hardmath Apr 10 '17 at 15:02
6
$\begingroup$

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

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

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

$\endgroup$
  • 1
    $\begingroup$ I believe your approximation is off. The formula should give $p(50) \sim 217590$, not $198680$. $\endgroup$ – Théophile Apr 10 '17 at 14:56
  • 1
    $\begingroup$ @xyzt Hardy-Ramanujan is not approximating to the nearest integer. $\endgroup$ – Tlön Uqbar Orbis Tertius Apr 10 '17 at 15:01
  • 1
    $\begingroup$ @xyzt maybe you're referring to the series found by Rademacher? $\endgroup$ – Mastrem Apr 10 '17 at 15:07
  • 4
    $\begingroup$ 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. $\endgroup$ – Peter Green Apr 10 '17 at 17:41
  • 1
    $\begingroup$ @JorgeFernándezHidalgo More terms may be easily computable, but 10000 is a standard length for an OEIS b-file. $\endgroup$ – LegionMammal978 Apr 11 '17 at 10:44
5
$\begingroup$

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$

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

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.