# Find coefficient of $x^ny^m$

how can I find the coefficient of $x^ny^m$ of following series $$\frac{\log\big(\frac{1}{1-xy}\big)}{(1-x)(1-y)(1-xy)}$$ and $$\frac{\log(\frac{1}{1-x})}{(1-x)(1-y)(1-xy)}$$ where $1 \leq m \leq n$

-
You can write this functions as a Cauchy product of four series. Why do you want $m\leq n$? –  Davide Giraudo Jul 22 '12 at 16:37
I am trying to understand this paper on partial quick sort. lsi.upc.edu/~conrado/research/reports/ALCOMFT-TR-03-50.pdf . Page no 3 (F(z,u)*=) –  ami Jul 22 '12 at 16:41

Use $\log\left(\frac{1}{1-x y}\right) = -\log(1- xy) = - \sum_{n=1}^\infty \frac{1}{n} x^n y^n$, and $$-\frac{\log(1-x y)}{1-x y} = \sum_{n=1}^\infty x^n y^n \sum_{m=1}^n \frac{1}{n} = \sum_{n=1}^\infty x^n y^n H_n$$ Then use $$\frac{ \sum_{n \geqslant 1, m\geqslant 1} c_{n,m} x^n y^m}{(1-x)(1-y)} = \sum_{n=1}^\infty \sum_{m=1}^\infty x^n y^m \sum_{k=1}^n \sum_{\ell=1}^m c_{k,\ell}$$ In our case $c_{k,\ell} = H_k \delta_{k,\ell}$, and $\sum_{k=1}^n \sum_{\ell=1}^m H_k \delta_{k,\ell} = \sum_{k=1}^{\min(n,m)} H_k$ $$-\frac{\log(1-x y)}{1-x y} \cdot \frac{1}{(1-x)(1-y)} = \sum_{n=1}^\infty \sum_{m=1}^\infty x^n y^m \sum_{k=1}^{\min(n,m)} H_k = \sum_{n=1}^\infty \sum_{m=1}^\infty x^n y^m \left( \left(\min(n,m) +1\right)\left( H_{\min(n,m)+1}-1\right) \right)$$

For the second series, we start with $$[x]^n \frac{-\log(1-x)}{1-x} = H_n \quad [x]^m \frac{1}{1-x y} = y^m$$ Therefore $$[x]^n \frac{-\log(1-x)}{1-x} \cdot \frac{1}{1-x y} = \sum_{k=0}^{n-1} H_{n-k} y^k$$ Then $$[y]^m [x]^n \frac{-\log(1-x)}{1-x} \cdot \frac{1}{1-x y} \cdot \frac{1}{1-y} = \sum_{k=0}^{n-1}H_{n-k} \mathbf{1}\left( k \leqslant m \right) = \sum_{k=0}^{\min(m, n-1)}H_{n-k}$$

-
Thanks. please solve series no. 2. –  ami Jul 22 '12 at 16:54
Thanks @Sasha. your solution is more generic. –  ami Jul 22 '12 at 17:37
I think you're off by $1$ in the first series. You seem to be saying (in the last line) $\sum_{k=1}^K H_k = (K+1) (H_K-1)$ but it should be $\sum_{k=1}^K H_k = (K+1) (H_K-1) + 1$. So the answer should be $$\sum_{n=1}^\infty\sum_{m=1}^\infty x^n y^m \left((\min(n,m)+1)(H_{\min(n,m)}-1)+1\right)$$ –  Robert Israel Jul 22 '12 at 18:25
@RobertIsrael Thanks, I mean to say $\sum_{k=1}^n H_k = (n+1)(H_{n+1}-1)$. –  Sasha Jul 22 '12 at 19:29

Using geometric series and $\displaystyle\frac{1}{1-r}\log\frac{1}{1-r}=\sum_{k\ge1}H_kr^k$, with $H_k$ the $k$th harmonic number,

$$\sum_{a=0}^\infty x^a~\sum_{b=0}^\infty y^b~\sum_{k=1}^\infty H_k(xy)^k=\sum_{a,b\ge0}^{k\ge1}H_kx^{a+k}y^{b+k}.$$

The coefficient of $x^ny^m$ will be the sum of all $H_k$ with $k\le n,m$. With $m\le n$, this is

$$\sum_{k=1}^mH_k=(m+1)(H_{m+1}-1)$$

by induction. Similarly for the second,

$$\sum_{a=0}^\infty y^a\sum_{b=0}^\infty (xy)^b \sum_{k=1}^\infty H_kx^k=\sum_{a,b\ge0}^{k\ge1} H_k x^{b+k}y^{a+b}.$$

The coefficient of $x^ny^m$ will be the sum of all $k\le n$ such that $0\le n-k\le m$, i.e.

$$\sum_{k=n-m}^{n}H_k=\left(\sum_{k=1}^n H_k\right)-\left(\sum_{k=1}^{n-m-1}H_k\right)$$

$$=(n+1)\big(H_{n+1}-1\big)-(n-m)\big(H_{n-m}-1\big).$$

(Or $0$ if $m>n$.)

-
Thanks @anon. I learned something today. :) –  ami Jul 22 '12 at 17:35