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

  • $\begingroup$ 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. $\endgroup$ – Mitch Apr 2 '11 at 17:09
  • 2
    $\begingroup$ @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. $\endgroup$ – Qiaochu Yuan Apr 2 '11 at 17:23
  • $\begingroup$ 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? $\endgroup$ – user7475 Apr 7 '11 at 22:36
  • $\begingroup$ @user7475: please use the "add comment" feature of this website to request follow-up information, instead of posting a new answer. $\endgroup$ – Willie Wong Apr 8 '11 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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