Séminaire Lotharingien de Combinatoire, B17a (1987), 17
pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1988, 348/S-17, p.
5-21.]
Ira Gessel
Enumerative Applications of Symmetric Functions
Abstract.
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.
The following versions are available: