Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
+1, but could you elaborate on why $ \sum n \sum z^{nl} = \sum \sigma(n)z^n$ ? –  Ragib Zaman Sep 23 '11 at 9:35
1  
@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. –  J. M. Sep 23 '11 at 9:47
2  
About the second bit: you could've also said that multiplying two generating functions gives a series whose coefficients are convolutions. –  J. M. Sep 23 '11 at 9:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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