Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
    
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
2  
@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
    
@user7475: please use the "add comment" feature of this website to request follow-up information, instead of posting a new answer. –  Willie Wong Apr 8 '11 at 16:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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