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.

  • 0
    +1, but could you elaborate on why $ \sum n \sum z^{nl} = \sum \sigma(n)z^n$ ?2011-09-23
  • 1
    @Ragib: One way to see that is to use the property of the [Lambert series](http://en.wikipedia.org/wiki/Lambert_series): the Lambert series becomes a power series in $z$ whose coefficients are a [Dirichlet convolution](http://en.wikipedia.org/wiki/Dirichlet_convolution).2011-09-23
  • 2
    About the second bit: you could've also said that multiplying two generating functions gives a series whose coefficients are convolutions.2011-09-23