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$
Find coefficient of $x^ny^m$
-
1I $a$m trying to understand this paper on partial quick sort. http://www.lsi.upc.edu/~conrado/research/reports/ALCOMFT-TR-03-50.pdf . Page no 3 (F(z,u)*=) – 2012-07-22
2 Answers
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} $
-
0@RobertIsrael Thanks, I mean to say $\sum_{k=1}^n H_k = (n+1)(H_{n+1}-1)$. – 2012-07-22
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$.)
-
0Thanks @anon. I learned something today. :) – 2012-07-22