Recurrencia para el número de partición

Question

Yo soy de la lectura Analítica de la Combinatoria [PDF] libro de Flajolet y Sedgewick, y no puedo entender uno de los pasos en la obtención de la $P_n$ - número de particiones de tamaño $n$ (o coeficientes en la expansión de Taylor de $P(z)$, ver más abajo).

En la página 42, I. 13. dice:

$\rhd$ I. 13. Una recurrencia de los números de partición. La diferenciación logarítmica da $$z \frac{P\,'(z)}{P(z)} = \sum_{n=1}^\infty \frac{n z^n}{1-z^n} \qquad \text{implying} \qquad n P_n = \sum_{j=1}^n \, \sigma(j) P_{n-j}\,,$$ donde $\sigma(n)$ es la suma de los divisores de a $n$ (por ejemplo, $\sigma(6)=1+2+3+6=12$).

$P(z)$ es anterior define ( $(39)$ , en la página 41) como $$P(z) = \prod_{n=1}^\infty \frac{1}{1-z^n}.$$

Entiendo cómo consiguen que la parte a la izquierda de la palabra "implica", sin embargo, no veo cómo consiguen que la parte a la derecha de ella. ¿Cómo se consiguen?

Answer 1

Por definición, $$P(z)=\sum_{n=0}^\infty P_nz^n.$$ Nota también $$\sum_{n=1}^\infty \frac{nz^n}{1-z^n}=\sum_{n=1}^\infty n\sum_{\ell=1}^\infty z^{n\ell}=\sum_{m=1}^\infty \sigma_1(m)z^m.$$ Anteriormente hemos observado que todos los coeficientes de $z^m$ (donde nos re-etiquetar $n\ell$$m$) en la serie será la suma de todas las $n$ tal que $n|m$, es decir, la suma de los divisores, de ahí la presencia de la función de divisor. Este es un ejemplo de Dirichlet de convolución y, en particular, una Lambert de la serie. [-J. M.]

Multiplicando ambos lados de la ecuación dada antes de "$\text{implying}$ " $P(z)$ obtenemos $$\sum_{m=1}^\infty mP_m z^m= \left(\sum_{n=0}^\infty P_nz^n\right)\left(\sum_{j=1}^\infty \sigma_1(j)z^j\right)$$ $$=\sum_{m=1}^\infty\left(\sum_{j=1}^m \sigma_1(j)P_{m-j}\right)z^m.$$ Anteriormente se observó que los coeficientes de $z^m$ (donde nos re-etiquetar $n+j$$m$) en la serie será sumas de términos de la forma$\sigma_1(j)P_n$$j+n=m,j\ge1$, de ahí la presencia de el interior de la suma. Esto se deriva de un patrón general: el producto de dos funciones de generación es una generación de la función de la convolución de la base de secuencias.

La equiparación de ambos lados da la deseada igualdad.