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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1, but could you elaborate on why $ \sum n \sum z^{nl} = \sum \sigma(n)z^n$ ? $\endgroup$ – Ragib Zaman Sep 23 '11 at 9:35
  • 1
    $\begingroup$ @Ragib: One way to see that is to use the property of the Lambert series: the Lambert series becomes a power series in $z$ whose coefficients are a Dirichlet convolution. $\endgroup$ – J. M. is a poor mathematician Sep 23 '11 at 9:47
  • 2
    $\begingroup$ About the second bit: you could've also said that multiplying two generating functions gives a series whose coefficients are convolutions. $\endgroup$ – J. M. is a poor mathematician Sep 23 '11 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.