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.
Diagonals of power series in combinatorics
3
$\begingroup$
combinatorics
generating-functions
1 Answers
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@user7475: please use the "add comment" feature of this website to request follow-up information, instead of posting a new answer. – 2011-04-08