Función de partición

Os valores $p(1),\dots ,p(8)$ da función de partición (1, 2, 3, 5, 7, 11, 15 e 22) pódese determinar contando os diagramas de Young para as particións dos números do 1 ao 8.

En teoría de números, a función de partición p(n) representa o número de posíbeis particións dun enteiro non negativo n. Por exemplo, p(4) = 5 porque o número enteiro 4 ten as cinco particións 1 + 1 + 1 + 1; 1 + 1 + 2; 1 + 3; 2 + 2 e 4.

Non se coñece ningunha expresión de forma pechada para a función de partición, mais ten tanto expansións asintóticas que a aproximan con precisión como relacións de recorrencia polas que se pode calcular exactamente. Medra como función exponencial da raíz cadrada do seu argumento. O inverso multiplicativo da súa función xeradora é a función de Euler; polo teorema dos números pentagonais de Euler esta función é unha suma alterna de potencias numéricas pentagonais do seu argumento.

Srinivasa Ramanujan descubriu por primeira vez que a función de partición ten patróns non triviais en aritmética modular, agora coñecidos como congruencias de Ramanujan. Por exemplo, sempre que a representación decimal de n remate no díxito 4 ou 9, o número de particións de n será divisíbel por 5.

Definición e exemplos

Para un número enteiro positivo n, p(n) é o número de formas distintas de representar n como unha suma de números enteiros positivos. Para os efectos desta definición, a orde dos termos na suma é irrelevante: dúas sumas cos mesmos termos nunha orde diferente non se consideran distintas.

Por convención p(0) = 1, xa que hai unha forma (a suma baleira ) de representar cero como unha suma de enteiros positivos. A maiores p(n) = 0 cando n é negativo.

Os primeiros valores da función de partición, comezando por p(0) = 1, son:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... (secuencia A000041 na OEIS).

Función xeradora

Artigo principal: Teorema do número pentagonal.

A función xeradora para p (n) vén dada por $${\begin{aligned}\sum _{n=0}^{\infty }p(n)x^{n}&=\prod _{k=1}^{\infty }\left({\frac {1}{1-x^{k}}}\right)\\&=\left(1+x+x^{2}+x^{3}+\cdots \right)\left(1+x^{2}+x^{4}+x^{6}+\cdots \right)\left(1+x^{3}+x^{6}+x^{9}+\cdots \right)\cdots \\&={\frac {1}{1-x-x^{2}+x^{5}+x^{7}-x^{12}-x^{15}+x^{22}+x^{26}-\cdots }}\\&=1{\Big /}\sum _{k=-\infty }^{\infty }(-1)^{k}x^{k(3k-1)/2}.\end{aligned}}$$A igualdade entre os produtos da primeira e segunda liñas desta fórmula obtense coa expansión de cada factor $1/(1-x^{k})$ na serie xeométrica $(1+x^{k}+x^{2k}+x^{3k}+\cdots ).$ Para ver que o produto expandido é igual á suma da primeira liña, aplicamos a lei distributiva. Isto expande o produto nunha suma de monomios da forma $x^{a_{1}}x^{2a_{2}}x^{3a_{3}}\cdots$ para algunha secuencia de coeficientes $a_{i}$, só un número finito deles poden ser distintos de cero. O expoñente do termo é ${\textstyle n=\sum ia_{i}}$, e esta suma pódese interpretar como unha representación de $n$ como partición en $a_{i}$ copias de cada número $i$. Polo tanto, o número de termos do produto que teñen expoñente $n$ é exactamente $p(n)$, o mesmo que o coeficiente de $x^{n}$ na suma da esquerda. Polo tanto, a suma é igual ao produto.

A función que aparece no denominador na terceira e cuarta liñas da fórmula é a función de Euler. A igualdade entre o produto da primeira liña e as fórmulas da terceira e cuarta liñas é o teorema dos números pentagonais de Euler. Os expoñentes de $x$ nestas liñas son os números pentagonais $P_{k}=k(3k-1)/2$ para $k\in \{0,1,-1,2,-2,\dots \}$.

Relacións de recorrencia

A mesma secuencia de números pentagonais aparece nunha relación de recorrencia para a función de partición: $${\begin{aligned}p(n)&=\sum _{k\in \mathbb {Z} \setminus \{0\}}(-1)^{k+1}p(n-k(3k-1)/2)\\&=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-p(n-22)-\cdots \end{aligned}}$$Como casos básicos considramos $p(0)$ igual $1$, e $p(k)$igual a cero para $k$ negativo. Aínda que a suma do lado dereito parece infinita, só ten un número finito de termos distintos de cero, procedentes dos valores de $k$ distintos de cero na franxa $$-{\frac {{\sqrt {24n+1}}-1}{6}}\leq k\leq {\frac {{\sqrt {24n+1}}+1}{6}}.$$ A relación de recorrencia tamén se pode escribir na forma equivalente $$p(n)=\sum _{k=1}^{\infty }(-1)^{k+1}{\big (}p(n-k(3k-1)/2)+p(n-k(3k+1)/2){\big )}.$$

Congruencias

Srinivasa Ramanujan descubriu que a función de partición ten modelos non triviais na aritmética modular. Por exemplo, o número de particións é divisíbel por cinco sempre que a representación decimal de $n$ remata no díxito 4 ou 9, como se expresa pola congruencia$$p(5k+4)\equiv 0{\pmod {5}}$$Por exemplo, o número de particións para o número enteiro 4 é 5. Para o número enteiro 9 é 30; para 14 hai 135 particións. Esta congruencia vén implicada pola identidade máis xeral $$\sum _{k=0}^{\infty }p(5k+4)x^{k}=5~{\frac {(x^{5})_{\infty }^{5}}{(x)_{\infty }^{6}}},$$tamén debida a Ramanujan, onde a notación $(x)_{\infty }$ denota o produto definido por $$(x)_{\infty }=\prod _{m=1}^{\infty }(1-x^{m}).$$Unha pequena proba deste resultado pódese obter a partir da función xeradora da función de partición.

Ramanujan tamén descubriu congruencias módulo 7 e 11: $${\begin{aligned}p(7k+5)&\equiv 0{\pmod {7}},\\p(11k+6)&\equiv 0{\pmod {11}}.\end{aligned}}$$ O primeiro procede da identidade de Ramanujan $$\sum _{k=0}^{\infty }p(7k+5)x^{k}=7~{\frac {(x^{7})_{\infty }^{3}}{(x)_{\infty }^{4}}}+49x~{\frac {(x^{7})_{\infty }^{7}}{(x)_{\infty }^{8}}}.$$

Fórmulas de aproximación

Existen fórmulas de aproximación que son máis rápidas de calcular que a fórmula exacta indicada anteriormente.

Unha expresión asintótica para p(n) vén dada por

$p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)$ cando $n\to \infty$ .

Esta fórmula asintótica foi obtida por primeira vez por GH Hardy e Ramanujan en 1918 e de forma independente por JV Uspensky en 1920. Considerando $p(1000)$, a fórmula asintótica dá aproximadamente $2.4402\times 10^{31}$, razoabelmente preto da resposta exacta (un 1,415 % maior que o valor verdadeiro).

Paul Erdős (1942) publicou unha proba elemental da fórmula asintótica de $p(n)$.

Función de partición estrita

Definición e propiedades

Unha partición na que ningunha parte aparece máis dunha vez chámase estrita. A función q(n) dá o número destas particións estritas con suma n. Por exemplo, q(3) = 2 porque as particións 3 e 1 + 2 son estritas, mentres que a terceira partición 1 + 1 + 1 de 3 ten partes repetidas.

Pore outro parte resulta que o número q(n) coincide co número de particións de n nas que só se permiten sumandos impares.

Función xeradora

A función xeradora dos números q(n) vén dada por un produto infinito simple: $$\sum _{n=0}^{\infty }q(n)x^{n}=\prod _{k=1}^{\infty }(1+x^{k})=(x;x^{2})_{\infty }^{-1},$$onde a notación $(a;b)_{\infty }$ representa o símbolo de Pochhammer $(a;b)_{\infty }=\prod _{k=0}^{\infty }(1-ab^{k}).$ A partir desta fórmula, pódense obter facilmente os primeiros termos (secuencia A000009 na OEIS): $$\sum _{n=0}^{\infty }q(n)x^{n}=1+1x+1x^{2}+2x^{3}+2x^{4}+3x^{5}+4x^{6}+5x^{7}+6x^{8}+8x^{9}+10x^{10}+\ldots .$$

Función de partición restrinxida

De forma máis xeral, é posíbel considerar particións restrinxidas só a elementos dun subconxunto A dos números naturais (por exemplo, unha restrición no valor máximo das partes), ou cunha restrición no número de partes ou á diferenza máxima entre as partes. Cada restrición particular dá lugar a unha función de partición asociada con propiedades específicas. A continuación móstranse algúns exemplos comúns.

Teorema de Euler e Glaisher

Dous exemplos importantes son as particións restrinxidas só a partes enteiras impares ou só a partes enteiras pares, coas funcións de partición correspondentes a miúdo denotadas $p_{o}(n)$ e $p_{e}(n)$ (do inglés odd e even).

Un teorema de Euler mostra que o número de particións estritas é igual ao número de particións con só partes impares: para todo n, $q(n)=p_{o}(n)$. Isto xeneralízase no teorema de Glaisher, que afirma que o número de particións con non máis de d-1 repeticións de calquera parte é igual ao número de particións sen parte divisíbel por d.

Coeficiente binomial de Gauss

Se denotamos $p(N,M,n)$ o número de particións de n como máximo en M partes, sendo cada parte menor ou igual a N, entón a función xeradora de $p(N,M,n)$ é o seguinte coeficiente binomial de Gauss:

$\sum _{n=0}^{\infty }p(N,M,n)q^{n}={N+M \choose M}_{q}={\frac {(1-q^{N+M})(1-q^{N+M-1})\cdots (1-q^{N+1})}{(1-q)(1-q^{2})\cdots (1-q^{M})}}$

Véxase tamén

Bibliografía

• Al, Busra; Alkan, Mustafa (2018). "A note on relations among partitions". Proc. Mediterranean Int. Conf. Pure & Applied Math. and Related Areas (MICOPAM 2018). pp. 35–39. 

• Ahlgren, Scott; Boylan, Matthew (2003). Arithmetic properties of the partition function (PDF). Inventiones Mathematicae 153. pp. 487–502. Bibcode:2003InMat.153..487A. MR 2000466. doi:10.1007/s00222-003-0295-6. 

• Andrews, George E. (1976). The Theory of Partitions. Cambridge University Press. p. 69. ISBN 0-521-63766-X. MR 0557013. </ref>

• Ahlgren, Scott; Ono, Ken (2001). Congruence properties for the partition function (PDF). Proceedings of the National Academy of Sciences 98. pp. 12882–12884. Bibcode:2001PNAS...9812882A. MR 1862931. PMC 60793. PMID 11606715. doi:10.1073/pnas.191488598. </ref>

• Abramowitz, Milton; Stegun, Irene (1964). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. United States Department of Commerce, National Bureau of Standards. p. 825. ISBN 0-486-61272-4. 

• Berndt, Bruce C.; Ono, Ken (1999). "Ramanujan's unpublished manuscript on the partition and tau functions with proofs and commentary" (PDF). The Andrews Festschrift (Maratea, 1998). Séminaire Lotharingien de Combinatoire 42. Art. B42c, 63. MR 1701582. </ref>

• Euler, Leonhard (1753). De partitione numerorum. Novi Commentarii Academiae Scientiarum Petropolitanae (en latín) 3. pp. 125–169. 

• Erdős, P. (1942). On an elementary proof of some asymptotic formulas in the theory of partitions (PDF). Annals of Mathematics. Second Series 43. pp. 437–450. JSTOR 1968802. MR 0006749. Zbl 0061.07905. doi:10.2307/1968802. 

• Ewell, John A. (2004). Recurrences for the partition function and its relatives. The Rocky Mountain Journal of Mathematics 34. pp. 619–627. JSTOR 44238988. MR 2072798. doi:10.1216/rmjm/1181069871. 

• Johansson, Fredrik (March 2, 2014). New partition function record: p(10²⁰) computed. 

• Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. p. 380. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001. </ref>

• Hardy, G. H.; Ramanujan, S. (1918). Asymptotic formulae in combinatory analysis. Proceedings of the London Mathematical Society. Second Series 17. . Reprinted in Collected papers of Srinivasa Ramanujan, Amer. Math. Soc. (2000), pp. 276–309.</ref>

• Johansson, Fredrik (2012). Efficient implementation of the Hardy–Ramanujan–Rademacher formula. LMS Journal of Computation and Mathematics 15. pp. 341–59. MR 2988821. arXiv:1205.5991. doi:10.1112/S1461157012001088. </ref>

• Nathanson, M. B. (2000). Elementary Methods in Number Theory. Graduate Texts in Mathematics 195. Springer-Verlag. p. 456. ISBN 0-387-98912-9. Zbl 0953.11002. </ref>

• (secuencia A070177 na OEIS)

• Ono, Ken (2000). Distribution of the partition function modulo m. Annals of Mathematics 151. pp. 293–307. Bibcode:2000math......8140O. JSTOR 121118. MR 1745012. Zbl 0984.11050. arXiv:math/0008140. doi:10.2307/121118. 

• Ono, Ken (2004). The web of modularity: arithmetic of the coefficients of modular forms and q-series. CBMS Regional Conference Series in Mathematics 102. Providence, Rhode Island: American Mathematical Society. p. 87. ISBN 0-8218-3368-5. Zbl 1119.11026. 

• Rademacher, Hans (1937). On the partition function p(n). Proceedings of the London Mathematical Society. Second Series 43. pp. 241–254. MR 1575213. doi:10.1112/plms/s2-43.4.241. 

• Wilf, Herbert S. (1982). What is an answer?. American Mathematical Monthly 89. pp. 289–292. JSTOR 2321713. MR 653502. doi:10.2307/2321713. 

Outros artigos

• Función xeradora.

Ligazóns externas

• First 4096 values of the partition function