Enumerative Applications of Symmetric Functions

Ira Gessel

Séminaire lotharingien de combinatoire, Tome 17 (1987)

Résumé

This paper consists of two related parts. In the first part the theory of D-finite power series in several variables and the theory of symmetric functions are used to prove P-recursiveness for regular graphs and digraphs and related objects, that is, that their counting sequences satisfy linear homogeneous recurrences with polynomial coefficients. Previously this has been accomplished only for small degrees, for example, by Goulden, Jackson and Reilly, then by Goulden and Jackson, finally by Read. These authors found the recurrences satisfied by the sequences in question. Although the methods used here are in principle constructive, we are concerned here only with the question of existence of these recurrences and we do not find them.

In the second part we consider a generalization of symmetric functions in several sets of variables, first studied by MacMahon [Vol. 2, pp. 280-326]. MacMahon's generalized symmetric functions can be used to find explicit formulas and prove P-recursiveness for some objects to which the theory of ordinary symmetric functions does not apply, such as Latin rectangles and 0-1 matrices with zeros on the diagonal and given row and column sums.