Función de partición

En teoría de números, a función de partición Modelo:Math representa o número de posíbeis particións dun enteiro non negativo Modelo:Mvar. Por exemplo, Modelo:Math porque o número enteiro 4 ten as cinco particións Modelo:Math; Modelo:Math; Modelo:Math; Modelo:Math e Modelo:Math.

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 Modelo:Mvar remate no díxito 4 ou 9, o número de particións de Modelo:Mvar será divisíbel por 5.

Definición e exemplos

Para un número enteiro positivo Modelo:Math, Modelo:Math é o número de formas distintas de representar Modelo:Mvar 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 Modelo:Math, xa que hai unha forma (a suma baleira ) de representar cero como unha suma de enteiros positivos. A maiores Modelo:Math cando Modelo:Mvar é negativo.

Os primeiros valores da función de partición, comezando por Modelo:Math, son: Modelo:Bloque indentado

Función xeradora

Modelo:Main A función xeradora para p (n) vén dada por ^[1] $\begin{matrix} \sum_{n = 0}^{\infty} p (n) x^{n} & = \prod_{k = 1}^{\infty} (\frac{1}{1 - x^{k}}) \\ = (1 + x + x^{2} + x^{3} + \dots) (1 + x^{2} + x^{4} + x^{6} + \dots) (1 + x^{3} + x^{6} + x^{9} + \dots) \dots \\ = \frac{1}{1 - x - x^{2} + x^{5} + x^{7} - x^{12} - x^{15} + x^{22} + x^{26} - \dots} \\ = 1 / \sum_{k = - \infty}^{\infty} (- 1)^{k} x^{k (3 k - 1) / 2} . \end{matrix}$ 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^{2 k} + x^{3 k} + \dots) .$ 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^{2 a_{2}} x^{3 a_{3}} \dots$ para algunha secuencia de coeficientes $a_{i}$ , só un número finito deles poden ser distintos de cero. O expoñente do termo é $n = \sum i a_{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 (3 k - 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:^[2] $\begin{matrix} p (n) & = \sum_{k \in ℤ ∖ {0}} (- 1)^{k + 1} p (n - k (3 k - 1) / 2) \\ = p (n - 1) + p (n - 2) - p (n - 5) - p (n - 7) + p (n - 12) + p (n - 15) - p (n - 22) - \dots \end{matrix}$ 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{24 n + 1} - 1}{6} \leq k \leq \frac{\sqrt{24 n + 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} (p (n - k (3 k - 1) / 2) + p (n - k (3 k + 1) / 2)) .$

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^[3] $p (5 k + 4) \equiv 0 (\mod 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 (5 k + 4) x^{k} = 5 \frac{(x^{5})_{\infty}^{5}}{(x)_{\infty}^{6}},$ tamén debida a Ramanujan,^[4] 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:^[3] $\begin{matrix} p (7 k + 5) & \equiv 0 (\mod 7), \\ p (11 k + 6) & \equiv 0 (\mod 11) . \end{matrix}$ O primeiro procede da identidade de Ramanujan^[5] $\sum_{k = 0}^{\infty} p (7 k + 5) x^{k} = 7 \frac{(x^{7})_{\infty}^{3}}{(x)_{\infty}^{4}} + 49 x \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}{4 n \sqrt{3}} \exp (π \sqrt{\frac{2 n}{3}})

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 1 0^{31}$ , razoabelmente preto da resposta exacta (un 1,415 % maior que o valor verdadeiro).

Modelo:Harvard citations 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.^[6]

Función xeradora

A función xeradora dos números q(n) vén dada por un produto infinito simple:^[7] $\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 - a b^{k}) .$ A partir desta fórmula, pódense obter facilmente os primeiros termos Modelo:OEIS: $\sum_{n = 0}^{\infty} q (n) x^{n} = 1 + 1 x + 1 x^{2} + 2 x^{3} + 2 x^{4} + 3 x^{5} + 4 x^{6} + 5 x^{7} + 6 x^{8} + 8 x^{9} + 10 x^{10} + \dots .$

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: