# Diagonals of power series in combinatorics

Where in combinatorics does the procedure of taking diagonals of power series (generating functions) arise? With diagonal is meant the following: if $f = \sum a_{i_1 ... i_n} x_1^{i_1}...x_n^{i_n}$ is a formal power series in $n$ variables then one can form for example the diagonal $I_{12}(f) = \sum a_{i_1 i_1 i_3 ... i_n} x_1^{i_1} x_3^{i_3}...x_n^{i_n}$ and similar $I_{ij}$ and also compose diagonals.

-

Exactly the obvious thing: if you are interested in some sequence $a_n$ and it is best expressed as $b_{n,n}$ for some two-parameter sequence $b_{n,m}$ whose generating function you know. For example, the sequence $a_n = {2n \choose n}$ is $b_{n,n}$ where $b_{m,n} = {m+n \choose m}$. This has bivariate generating function

$$B(x, y) = \sum_{m, n \ge 0} {m+n \choose m} x^m y^n = \frac{1}{1 - x - y}$$

and taking its diagonal gives

$$A(x) = \sum_{n \ge 0} {2n \choose n} x^n = \frac{1}{\sqrt{1 - 4x}}.$$

-
Can (and, if so, how does) one go straight from, say, $\frac{1}{1-x-y}$ to $\frac{1}{\sqrt{1-4x}}$? I mean generally or for some class of gfs. –  Mitch Apr 2 '11 at 17:09
@Mitch: this requires some analysis, either complex analysis or Fourier analysis. See qchu.wordpress.com/2009/10/07/extracting-the-diagonal or Stanley's Enumerative Combinatorics Vol. II, 6.3. The method always works for rational functions of two variables and past that things get murky. –  Qiaochu Yuan Apr 2 '11 at 17:23
Thanks for this nice example. I've somewhere read that the lagrange inversion formula can be expressed in terms of a diagonal. Does anybody know where i can find this? –  user7475 Apr 7 '11 at 22:36