3
$\begingroup$

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.

1 Answers 1

6

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}}.$$

  • 0
    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.2011-04-02
  • 2
    @Mitch: this requires some analysis, either complex analysis or Fourier analysis. See http://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.2011-04-02
  • 0
    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?2011-04-07
  • 0
    @user7475: please use the "add comment" feature of this website to request follow-up information, instead of posting a new answer.2011-04-08