Número de particiones de $50$

Question

¿Alguien sabe el número de particiones del número entero $50$? ¿Quiero decir, de cuántas maneras puedo escribir $50$ como la suma de enteros positivos? Sé que hay una tabla por Euler, que es útil para saber de cuántas maneras se puede escribir $50$ como la suma de $m$ diferentes números, pero esta mesa se detiene en $m=11$, así que no puedo terminar el cálculo y calcular en cuántas maneras en que puedo escribir $50$ como la suma de (cualquier) números diferentes. Gracias

Answer 1

Es sabido --- y es difícil y famoso resultado demostrado por Hardy y Ramanujan --- que el número de particiones de $n$ es de aproximadamente (al $n$ es grande) dado por $p(n) \sim \frac{ e^{ \pi\sqrt{2n/3} } }{4n\sqrt{3} }$. Con $n = 50$, este yelds $p(50) \sim 217590$.

Malas noticias : no es útil la forma cerrada de $p(n)$. Pero también se puede calcular con la conocida fórmula de recurrencia

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

donde $1,2,5,7,12$ el (generalizada) números pentagonales.

Para $n=50$ esto se podría hacer con la ayuda de una computadora.

(edit : bueno, como Théophile se mencionó, existen tablas de hasta el $p(250)$ y más. También, la señal de error en la de Euler recurrencia ha sido corregido. ¡Gracias !)

Answer 2

Según la tabla en OEISWiki, el número de partición de $50$ es $204226$.

Answer 3

Usted puede resolver este problema a través de Euler de la recursividad.

Ella le dice que $p_n=\sum\limits_{i\neq 0}^{}(-1)^{i-1} p_{n-i(3i-1)/2}$.

Por supuesto, la función de $f(x)=x(3x-1)/2$ es positivo en todas partes, excepto $(0,1/3)$, por lo que este es un buen recursividad. También tenga en cuenta que $p_n$ se define a ser $0$ para los valores negativos.

Podemos utilizar esta recursividad para calcular el $p_n$ a partir de los valores anteriores en el tiempo $\mathcal O(\sqrt n)$ , por lo que sin duda podemos obtener $P_n$ a partir de cero en el tiempo $\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]);
}

El resultado es $204226$