9
$\begingroup$

I'm reading Analytic Combinatorics [PDF] book by Flajolet and Sedgewick, and I can't figure out one of the steps in the derivation of the $P_n$ — number of partitions of size $n$ (or coefficients in Taylor expansion of $P(z)$, see below).

On page 42, I.13. says:

$\rhd$ I.13. A recurrence for the partition numbers. Logarithmic differentiation gives 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}\,, where $\sigma(n)$ is the sum of divisors of $n$ (e.g., $\sigma(6)=1+2+3+6=12$).

$P(z)$ is earlier defined ($(39)$ on page 41) as $P(z) = \prod_{n=1}^\infty \frac{1}{1-z^n}.$

I understand how they get the part to the left of the word “implying”, however I fail to see how they get the part to the right of it. How do they get it?

1 Answers 1

9

By definition, $P(z)=\sum_{n=0}^\infty P_nz^n.$ Note also $\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.$ Above we observed that all coefficients of $z^m$ (where we relabel $n\ell$ as $m$) in the series will be sums of all the $n$ such that $n|m$, i.e. the sum of divisors, hence the presence of the divisor function. This is an example of Dirichlet convolution and in particular a Lambert series. [-J.M.]

Multiplying both sides of the equation given before "$\text{implying}$" by $P(z)$ we obtain $\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.$ Above we observed that the coefficients of $z^m$ (where we relabel $n+j$ as $m$) in the series will be sums of terms of the form $\sigma_1(j)P_n$ with $j+n=m,j\ge1$, hence the presence of the inner sum. This stems from a general pattern: the product of two generating functions is a generating function for the convolution of the underlying sequences.

Equating both sides gives the desired equality.

  • 2
    About the second bit: $y$ou could've also said that multipl$y$ing two generating $f$unctions gives a series whose coefficients are convolutions.2011-09-23