Publ. I.R.M.A. Strasbourg, 1987, 229/S–08 Actes 17^{e} Séminaire Lotharingien, p. 5-21

ENUMERATIVE APPLICATIONS

OF SYMMETRIC FUNCTIONS

BY

Ira M. GESSEL^{1}

1. Introduction. — 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. See,

for example, GOULDEN, JACKSON, and REILLY [7], GOULDEN and JACKSON

[6], and READ [16, 18]. 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 [13 ; 14, 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.

I. Symmetric functions and P-recursiveness

I.M. GESSEL

2. D-finite power series and P-recursive functions. — A formal power series f(x) is said to be D-finite (or differentiably finite) if f satisfies a linear homogeneous differential equation with polynomial coefficients. An equivalent condition is that the set of derivatives of f spans a finitedimensional vector space over the field of rational functions in x. A function a(n) defined on the nonnegative integers is said to be P-recursive (or polynomially recursive) if there exist polynomials p_{0}(n), p_{1}(n), …, p_{k}(n) such that

1partially supported by NSF grant DMS-8504134

∑_{i=0}^{k} p_{i}(n)a(n + i) = 0

for all nonnegative integers n.

The fundamental fact relating these two concepts is that a(n) is Precursive if and only if its generating function ∑_{n=0}^{∞} a(n)x^{n} is D-finite. We refer the reader to STANLEY [20] for the proof of this and other basic facts.

In this paper we show that counting sequences for certain combinatorial problems which can be expressed as coefficients of symmetric functions are P-recursive. To do this we need a multivariable generalization of the theory of D-finiteness and P-recursiveness. Such a generalization was first given by ZEILBERGER [22]. However, Zeilberger’s definition of multivariable Precursiveness is not suitable for our purposes. A more useful definition of multivariable P-recursiveness has been given by LIPSHITZ [10], but we shall work only with multivariable D-finiteness.

The theory of D-finiteness generalizes easily to the multivariable case. In the next section we define multivariable D-finiteness and describe some of its properties.

3. D-finite power series in several variables. — First we discuss the theory of D-finite power series. Let I be an integral domain and let F be the quotient field of I[x_{1}, x_{2}, …, x_{n}]. Let f(x_{1}, x_{2}, …, x_{n}) be a formal power series in I[[x_{1}, x_{2}, …, x_{n}]]. We say that f(x) is D-finite in

the variables x_{1}, x_{2}, …, x_{n} if the set of all partial derivatives \frac{∂^{i_{1}+···+i_{n}}f}{∂x_{1}^{i_{1}} ⋯ ∂x_{n}^{i_{n}}}

spans a finite-dimensional vector space over F (as a subspace of the tensor product F ⊗_{I[x_{1},...,x_{n}]} I[[x_{1}, x_{2}, …, x_{n}]]).

The following lemma contains some of the basic facts about D-finite power series in several variables that we will need :

Lemma 1.

(i) The set of D-finite power series forms an I-subalgebra of I[[x_{1}, …, x_{n}]]. (ii) If f is D-finite in x_{1}, x_{2}, …, x_{n} then f is D-finite in any subset of

x_{1}, x_{2}, …, x_{n}. (iii) If f(x_{1}, x_{2}, …, x_{n}) is D-finite in x_{1}, x_{2}, …, x_{n} and for each i, r_{i} is a

polynomial in the variables y_{1}, y_{2}, …, y_{m}, (which may include some or all of the x_{i}) then f(r_{1}, r_{2}, …, r_{n}) is D-finite in y_{1}, y_{2}, …, y_{m}, as long as it is well-defined as a formal power series.

SYMMETRIC FUNCTIONS

(iv) If P (x) is a polynomial in x_{1}, x_{2}, …, x_{n} then e^{P (x)} is D-finite. The proofs of these statements are straightforward, and are similar to proofs for the one-variable case given by STANLEY [20]. (See also LIPSHITZ [10].) We need one further fact about D-finite power series in several variables, due to LIPSHITZ [9], which is somewhat harder to prove. If A(x) = ∑ a(i_{1}, …, i_{n})x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}} and B(x) = ∑ b(i_{1}, …, i_{n})x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}}, then the Hadamard product A(x) ⊙ B(x) with respect to the variables x_{1}, x_{2}, …, x_{n} is defined to be

∑ a(i_{1}, …, i_{n})b(i_{1}, …, i_{n})x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}}.

Note that the a’s and b’s may involve other variables.

Lemma 2 (LIPSHITZ [9]). — Suppose that A and B are D-finite in the variables x_{1},x_{2}, …, x_{m+n}. Then the Hadamard product A ⊙ B with respect to the variables x_{1}, x_{2}, …, x_{n} is D-finite in x_{1}, x_{2}, …, x_{m+n}.

Now suppose that f is a formal power series in an infinite set X of variables. For any subset S of X let f_{S} be the formal power series in the variables in S obtained by setting to zero all the variables in X − S. We shall say that f is D-finite in X if f_{S} is D-finite in S for every finite subset S of X. With this definition, all the properties of D-finite series in finitely many variables are easily seen to remain valid, except that in Lemma 1(iii) we may only substitute for finitely many variables.

4. Symmetric functions. — We recall some facts about symmetric functions. We refer the reader to MACDONALD [12] for proofs and details.

We work with symmetric functions in the infinitely many variables x_{1}, x_{2}, … with coefficients in a field of characteristic zero. We will be concerned with the following particular symmetric functions :

The power sum symmetric function p_{n} is defined by

p_{n} = ∑_{i} x_{i}^{n}.

More generally, if λ = λ_{1}λ_{2} ⋯ λ_{k} is a partition, we define p_{λ} = p_{λ_{1}}p_{λ_{2}} ⋯ p_{λ_{k}}.

The elementary symmetric function e_{n} is defined by

e_{n} = ∑_{i_{1}<i_{2}<···<i_{n}} x_{i_{1}}x_{i_{2}} ⋯ x_{i_{n}}.

If λ = λ_{1}λ_{2} ⋯ λ_{k} is a partition, we define e_{λ} = e_{λ_{1}}e_{λ_{2}} ⋯ e_{λ_{k}}.

The complete symmetric function h_{n} is defined by

h_{n} = ∑_{i_{1}≤i_{2}≤···≤i_{n}} x_{i_{1}}x_{i_{2}} ⋯ x_{i_{n}}.

It is convenient to define h_{λ} to be h_{λ_{1}}h_{λ_{2}} ⋯ h_{λ_{k}} for any sequence λ = λ_{1}λ_{2} ⋯ λ_{k} of nonnegative integers, not necessarily a partition. We set h = ∑_{n=0}^{∞} h_{n} and e = ∑_{n=0}^{∞} e_{n}, where h_{0} = e_{0} = 1.

The monomial symmetric function m_{λ} is the sum of all distinct monomials of the form x_{i_{1}}^{λ_{1}} ⋯ x_{i_{k}}^{λ_{k}}, where i_{1}, …, i_{k} are distinct.

It is known that each of the sets {e_{λ}}, {h_{λ}}, {p_{λ}}, and {m_{λ}}, where λ ranges over all partitions of n, is a basis for the vector space of symmetric functions homogeneous of degree n.

If λ has r_{i} parts equal to i for each i, then we define z_{λ} to be 1^{r_{1}}2^{r_{2}} ⋯ k^{r_{k}} r_{1}! r_{2}! ⋯ r_{k}! .

There is a symmetric scalar product ⟨ , ⟩ defined on symmetric functions that has the following properties :

(4.1)  ⟨m_{λ}, h_{μ}⟩ = δ_{λμ}

and

(4.2)  ⟨p_{λ}, p_{μ}⟩ = z_{λ}δ_{λμ}

where δ_{λμ} is 1 if λ = μ and 0 otherwise.

This scalar product was introduced by REDFIELD [19] in 1927 in his then-ignored but now-famous paper on what later became known as Pólya theory. Redfield called it the “cap product.” The scalar product was rediscovered by HALL [8] in 1957 and is often attributed to him. It is equivalent to the usual scalar product on characters of symmetric groups.

Note that (4.1) implies that if f is a symmetric function, then the coefficient of x_{i_{1}}^{λ_{1}}x_{i_{2}}^{λ_{2}}⋯x_{i_{k}}^{λ_{k}} in f is ⟨f, h_{λ}⟩. To evaluate scalar products of symmetric functions, we shall express them in terms of power sum symmetric functions and use (4.2). Thus, we need to express the complete homogeneous symmetric functions in terms of power sum symmetric functions, and this is accomplished by the formula

(4.3)  ∑_{n=0}^{∞} h_{n} = exp(∑_{k=1}^{∞} \frac{p_{k}}{k} ),

which implies that

h_{n} = ∑_{λ} \frac{p_{λ}}{z_{λ}}

where the sum is over all partitions λ of n.

Next we recall the operation of internal (also called inner) product on symmetric functions which is defined by

(4.4)  p_{λ} ∗ p_{μ} = δ_{λμ}z_{λ}p_{λ}

and extended by linearity to all symmetric functions. The internal product was discovered by REDFIELD [19] in 1927, who called it the “cup product,” and it was rediscovered by LITTLEWOOD [11] in 1956. It is equivalent to pointwise multiplication of characters of symmetric groups, which corresponds to the tensor (or Kronecker) product of representations.

5. D-finite symmetric functions. — We shall say that a symmetric function is D-finite if it is D-finite when considered as a power series in the p_{n}. We shall show that functions obtained from coefficients of D-finite symmetric functions are P-recursive.

Theorem 3. — Suppose that f and g are symmetric functions which are D-finite in the p_{i} and possibly in some other variables. Then f ∗ g is D-finite in these variables.

Proof. — Note that f ∗g = f ⊙g⊙u, where ⊙ is the Hadamard product in the p_{i} and u is the symmetric function given by

u = ∑_{λ} z_{λ}p_{λ},

where the sum is over all partitions λ. Now

u = ∑_{r_{1},r_{2},...} 1^{r_{1}}2^{r_{2}} ⋯ r_{1}! r_{2}! ⋯ p_{1}^{r_{1}}p_{2}^{r_{2}} ⋯

= (∑_{r_{1}} r_{1}! (1p_{1})^{r_{1}}) (∑_{r_{2}} r_{2}! (2p_{2})^{r_{2}}) ⋯

= A(1p_{1})A(2p_{2}) ⋯,

where A(y) = ∑_{n=0}^{∞} n! y^{n}. Since u is easily seen to be D-finite, f ∗ g is a Hadamard product of three D-finite power series, and is thus D-finite by Lipshitz’s theorem.

Corollary 4. — Let f and g be symmetric functions which are Dfinite in the p_{i} and in another variable t, and suppose that g involves only finitely many of the p_{i}. Then ⟨f, g⟩ is D-finite in t as long as it is well-defined as a formal power series.

Proof. — By the previous theorem, f ∗ g is D-finite in the p_{i} and in t, and involves only finitely many of the p_{i}. Then ⟨f, g⟩ is obtained from f ∗ g by setting each p_{i} equal to 1, and thus the conclusion follows from Lemma 1(iii).

Note that without the restriction on g the theorem would not be true : according to our definitions, ∑_{n=0}^{∞} c_{n}p_{n} is D-finite for any coefficients c_{n} and thus any power series in t can be obtained as a scalar product of two D-finite symmetric functions.

Corollary 5. — Let f be a D-finite symmetric function and let S be a finite set of integers. Define integers b_{n} as follows : b_{n} is the sum over all n-tuples (λ_{1}, λ_{2}, …, λ_{n}) ∈ S^{n} of the coefficient of x_{1}^{λ_{1}} ⋯ x_{n}^{λ_{n}} in f. Then b(t) = ∑_{n=0}^{∞} b_{n}t^{n} is D-finite.

Proof. — The coefficient of x_{1}^{λ_{1}} ⋯ x_{n}^{λ_{n}} in f is ⟨f, h_{λ}⟩, and so b(t) = ⟨f, g⟩, where

g = ∑_{n=0}^{∞} (t ∑_{i∈S} h_{i})^{n} = (1 − t ∑_{i∈S} h_{i})^{−1}

and the assertion follows from the previous corollary.

In particular, it will follow that the generating functions for various types of graphs and hypergraphs on n vertices whose degrees are constrained to a finite set are D-finite. This proves a conjecture of GOULDEN and JACKSON [6].

Next we need to consider the operation of composition (also called plethysm) for symmetric functions. First, suppose that g is a symmetric function which can can be expressed in the form t_{1} +t_{2} +⋯, where each t_{i} is of the form x_{1}^{i_{1}}x_{2}^{i_{2}} ⋯ x_{k}^{i_{k}}. (The terms t_{i} need not be distinct.) Then for any symmetric function f = f(x_{1}, x_{2}, …) the composition f(g) is defined to be f(t_{1}, t_{2}, …).

In the general case, composition may be defined as follows : If f_{1} and f_{2} are symmetric functions then (f_{1} + f_{2})(g) = f_{1}(g) + f_{2}(g) and (f_{1}f_{2})(g) = f_{1}(g)f_{2}(g) so it is sufficient to define p_{n}(g). This is accomplished by the formula p_{n}(g) = g(p_{n}), where g(p_{n}) is determined by the special case given in the previous paragraph, or by the formula p_{m}(p_{n}) = p_{mn}.

Theorem 6. — Suppose that g is a polynomial in the p_{n}. Then h(g) is D-finite.

Proof. — To show that h(g) is D-finite we need only show that h(g) is D-finite in the variables p_{1}, p_{2}, …, p_{n} for each n.

By (4.3) we have

h(g) = exp(∑_{k=1}^{∞} \frac{p_{k}(g)}{k}) = exp(∑_{k=1}^{∞} \frac{g(p_{k})}{k})

= exp(∑_{k=1}^{n} \frac{g(p_{k})}{k}) exp( ∑_{k=n+1}^{∞} \frac{g(p_{k})}{k}),

where the second factor on the right does not involve p_{1}, p_{2}, …, p_{n}. Then by Lemma 1(iv), h(g) is D-finite in p_{1}, p_{2}, …, p_{n}.

The same reasoning shows that e(g) is also D-finite, where e = ∑_{n=0}^{∞} e_{n}. Let us now give some examples of Theorem 6. Consider the products

(5.1)  h(h_{2}) = ∏_{i≤j} \frac{1}{1 − x_{i}x_{j}}

(5.2)  h(e_{2}) = ∏_{i<j} \frac{1}{1 − x_{i}x_{j}}
(5.3)  e(h_{2}) = ∏_{i≤j}(1 + x_{i}x_{j})
(5.4)  e(e_{2}) = ∏_{i<j}(1 + x_{i}x_{j}).

By Theorem 6, they are all D-finite. Each counts a class of graphs. Thus the coefficient of x_{1}^{λ_{1}}x_{2}^{λ_{2}} ⋯ in (5.1) is the number of graphs on the vertex set {1, 2, …}, with multiple edges and loops allowed, such that the degree of vertex i is λ_{i}, where a loop contributes 2 to the degree of its vertex. Similarly, (5.2) counts graphs with multiple edges but no loops, (5.3) counts graphs with loops allowed, but not multiple edges, and (5.4) counts graphs without loops or multiple edges. Graphs with loops in which a loop contributes only 1 to the degree of its vertex are counted by h(e_{1} + e_{2}) (multiple edges allowed) and e(e_{1} + e_{2}) (multiple edges not allowed). Similarly, k-uniform hypergraphs are counted by e(e_{k}), and so on.

6. Symmetric functions in several sets of variables. — In some applications it is necessary to work with symmetric functions in two or more sets of variables. For simplicity, we consider here only the case of two sets of variables, which we use to count nonnegative integer matrices with prescribed row and column sums (or equivalently, digraphs with prescribed indegrees and outdegrees or two-colored graphs with prescribed degrees).

Let x_{1}, x_{2}, … and y_{1}, y_{2}, … be two disjoint sets of variables. We shall consider power series in these variables which are symmetric in the x’s and symmetric in the y’s. It is easy to see that such a symmetric function can be expressed in the form

∑_{λ, μ} a_{λμ}p_{λ}(x)p_{μ}(y)

where p_{λ}(x) means p_{λ}(x_{1}, x_{2}, …) and similarly for p_{μ}(y). We call these series D-finite if they are D-finite in the p_{i}(x) and p_{j}(y).

We may extend the scalar product ⟨ , ⟩ to symmetric functions in two sets of variables by setting

⟨f_{1}(x)f_{2}(y), g_{1}(x)g_{2}(y)⟩ = ⟨f_{1}(x), g_{1}(x)⟩⟨f_{2}(y), g_{2}(y)⟩.

If f is a symmetric function, by f(xy) we mean f(x_{1}y_{1}, x_{1}y_{2}, …, x_{i}y_{j}, …). Thus, for example, we have

h(xy) = ∏_{i,j} \frac{1}{1 − x_{i}y_{j}} .

This product is easily seen to be D-finite using the fact that p_{n}(xy) = p_{n}(x)p_{n}(y). It is clear that the coefficient of x_{1}^{λ_{1}} ⋯ x_{n}^{λ_{n}}y_{1}^{μ_{1}} ⋯ y_{n}^{μ_{n}} in h(xy) is the number of digraphs on {1, 2, ⋯, n}, with multiple edges allowed, in which vertex i has outdegree λ_{i} and indegree μ_{i}, or equivalently, the number of n × n matrices of nonnegative integers in which the sum of the ith row is λ_{i} and the sum of the jth column is μ_{j}. This coefficient is easily seen to be equal to ⟨h(xy), h_{λ}(x)h_{μ}(y)⟩, which is also equal to ⟨h_{λ}(x), h_{μ}(x)⟩.

Now let b_{n} be the number of n × n nonnegative integer matrices with every row and column sum equal to k. It follows that

(6.1)  b(t) = ∑_{n=0}^{∞} b_{n}t^{n} = ⟨h(xy), g(x, y)⟩,

where g(x, y) is given by g(x, y) = (1−th_{k}(x)h_{k}(y))^{−1}, and by reasoning as before, b(t) is D-finite. Similarly, e(xy) counts 0-1 matrices with prescribed row and column sums, or equivalently, digraphs without multiple edges with prescribed indegrees and outdegrees.

7. Explicit formulas and asymptotics. — In all of our examples, we have actually shown something stronger than P-recursiveness—we have shown that there exists an explicit formula for the numbers in question as a sum of fixed multiplicity. (In the terminology of Zeilberger, these sums are “multi-hypergeometric.”) Although these formulas are complicated, they can be used to derive asymptotic approximations.

For example, the number of n × n nonnegative integer matrices with every row and column sum two is

⟨h(xy), h_{2}^{n}(x)h_{2}^{n}(y)⟩ = ⟨h_{2}^{n}, h_{2}^{n}⟩ = ⟨(\frac{p_{1}^{2} + p_{2}}{2} )^{n}, (\frac{p_{1}^{2} + p_{2}}{2} )^{n}⟩

= 2^{−2n} ∑_{i,j} \binom{n}{i}\binom{n}{j}⟨p_{1}^{2n−2i}p_{2}^{i}, p_{1}^{2n−2j}p_{2}^{j}⟩

= 2^{−2n} ∑_{i} \binom{n}{i}^{2}⟨p_{1}^{2n−2i}p_{2}^{i}, p_{1}^{2n−2i}p_{2}^{i}⟩

= ∑_{i} 2^{−(2n−i)}\binom{n}{i}^{2}(2n − 2i)! i! .

It can be shown that asymptotically we may replace each summand by its limit as n → ∞, and thus the sum is asymptotic to

2^{−2n}(2n)! ∑_{i=0}^{∞} \frac{2^{i}}{i!} (\frac{1}{2})^{2i} = 2^{−2n}(2n)! e^{1/2}.

A more detailed analysis yields a complete asymptotic expansion.

More generally, the number of n × n nonnegative integer matrices with every row and column sum k is ⟨h_{k}^{n}, h_{k}^{n}⟩, and it can be shown that the major contribution to this scalar product comes from the terms in

⟨(\frac{p_{1}^{k}}{k!} + \frac{p_{1}^{k−2}}{(k − 2)!} \frac{p_{2}}{2} )^{n} , (\frac{p_{1}^{k}}{k!} + \frac{p_{1}^{k−2}}{(k − 2)!} \frac{p_{2}}{2} )^{n}⟩

= \frac{(kn)!}{k!^{2n}} ∑_{i=0}^{n} \frac{(k(k − 1))^{2i}}{i! 2^{i}} \frac{(n(n − 1) ⋯ (n − i + 1))^{2}}{kn(kn − 1) ⋯ (kn − 2i + 1)}.

The sum is asymptotic to

\frac{(kn)!}{k!^{2n}} ∑_{i=0}^{∞} \frac{(k^{2}(k − 1)^{2}/2)^{i}}{i!} (\frac{1}{k} )^{2i} = \frac{(kn)!}{k!^{2n}}e^{(k−1)^{2}/2},

as found by EVERETT and STEIN [2], who also used symmetric functions. A similar analysis can be used to obtain asymptotic expansions for related problems, since although in general the formulas have many terms, nearly all are asymptotically insignificant.

II. MacMahon’s symmetric functions of several systems of quantities

8. MacMahon’s symmetric functions. — Some enumeration problems involve generating functions which are almost, but not quite, symmetric. Here are three examples :

Example 1. — The number of n × n 0-1 matrices with zeros on the diagonal with row sums r_{1}, r_{2}, …, r_{m} and column sums c_{1}, c_{2}, …, c_{n} is the coefficient of x_{1}^{r_{1}} ⋯ x_{m}^{r_{m}}y_{1}^{c_{1}} ⋯ y_{n}^{c_{n}} in

∏_{i≠j}(1 + x_{i}y_{j}).

Example 2. — The number of 3 × n Latin rectangles is the coefficient of x_{1}x_{2} ⋯ x_{n}y_{1}y_{2} ⋯ y_{n}z_{1}z_{2} ⋯ z_{n} in

(∑_{i,j,k} x_{i}y_{j}z_{k})^{n},

where the sum is over all triples of distinct integers i, j, k.

Example 3. — Consider the monoid freely generating by the letters a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{n}, subject only to the commutation relations a_{i}b_{i} = b_{i}a_{i}. By the CARTIER-FOATA theory of free partially commutative monoids [1], the number of equivalence classes of words in this monoid with u_{i} occurrences of a_{i} and v_{i} occurrences of b_{i} is the coefficient of x_{1}^{u_{1}} … x_{n}^{u_{n}}y_{1}^{v_{1}} … y_{n}^{v_{n}} in

(1 − x_{1} − ⋯ x_{n} − y_{1} − ⋯ − y_{n} + x_{1}y_{1} + ⋯ + x_{n}y_{n})^{−1}.

One can show that this coefficient is also the number of words in the letters a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{n}, with u_{i} occurrences of a_{i} and v_{i} occurrences of b_{i}, containing no consecutive a_{i}b_{i}.

These generating functions all have the property that they are symmetric under any permutation of the subscripts which acts the same on x’s and y’s, i.e., the coefficient of x_{1}^{u}y_{2}^{v} is equal to the coefficient of x_{a}^{u}y_{b}^{v} as long as a ≠ b, but need not be equal to the coefficient of x_{1}^{u}y_{1}^{v}. (The usual theory of symmetric functions in two sets of variables applies to symmetric functions which are symmetric independently in the x’s and the y’s.) These more general symmetric functions were studied by MACMAHON [13 ; 14, Vol. 2, pp. 280–326] who called them “symmetric functions of several systems of quantities.” MacMahon applied to them his favorite tool for manipulating symmetric functions, Hammond operators, and claimed to have solved the problem of counting Latin rectangles with these operators. His work on these symmetric functions seems to have been ignored, and his claimed solution to the problem of counting Latin rectangles dismissed as impractical and useless.

In previous sections we showed how the theory of symmetric functions can be applied to get “useful” formulas from symmetric function generating functions, and in particular, to show that certain sequences are P -recursive. We now do the same for MacMahon’s symmetric functions of several systems of quantities, which we henceforth call MacMahon symmetric functions. First we discuss the fundamental bases for MacMahon symmetric functions and the formulas relating them, which are straightforward generalizations of those for ordinary symmetric functions. For simplicity, we discuss here only MacMahon symmetric functions in two sets of variables. The generalization to more than two presents no difficulties.

9. Bases. — We take two sets of variables, x_{1}, x_{2}, … and y_{1}, y_{2}, . . .. A formal power series f in these variables is a MacMahon symmetric function if whenever i_{1}, i_{2}, …, i_{n} are distinct positive integers, and a_{1}, a_{2}, …, a_{n} and b_{1}, b_{2}, …, b_{n} are nonnegative integers, the coefficient of x_{i_{1}}^{a_{1}}y_{i_{1}}^{b_{1}}x_{i_{2}}^{a_{2}}y_{i_{2}}^{b_{2}} ⋯ in f is equal to the coefficient of x_{1}^{a_{1}}y_{1}^{b_{1}}x_{2}^{a_{2}}y_{2}^{b_{2}} ⋯ in f.

Just as bases for ordinary partitions are indexed by partitions of integers, bases for the MacMahon symmetric functions are indexed by bipartite partitions. A bipartite number is an element of N × N − {(0, 0)}, where N is the set of nonnegative integers. A bipartite partition of the bipartite number (a, b) is a multiset of bipartite numbers with (componentwise) sum (a, b). Thus {(0, 1), (0, 1), (1, 0)} is a bipartite partition of (1, 2). For simplicity we write {(0, 1), (0, 1), (1, 0)} as (0, 1)(0, 1)(1, 0) or as (0, 1)^{2}(1, 0).

Now if λ = (a_{1}, b_{1})(a_{2}, b_{2}) ⋯ is a bipartite partition, we define the monomial symmetric function m_{λ} to be the sum of all monomials of the form

x_{i_{1}}^{a_{1}}y_{i_{1}}^{b_{1}}x_{i_{2}}^{a_{2}}y_{i_{2}}^{b_{2}} ⋯

where i_{1}, i_{2}, … are distinct. For example,

\begin{aligned}m_{(1,0)(0,1)} & = ∑_{i≠j} x_{i}y_{j} \\ m_{(1,1)} & = ∑_{i} x_{i}y_{i} \\ m_{(1,1)(1,1)} & = ∑_{i<j} x_{i}y_{i}x_{j}y_{j}. \end{aligned}

Note that m_{(1,1)(1,1)} is not equal to ∑_{i≠j} x_{i}y_{i}x_{j}y_{j} since the latter sum contains every monomial twice. It is clear that the m_{λ} over all bipartite partitions λ of (a, b) constitute a basis for the vector space of all MacMahon symmetric functions of degree (a, b).

Next we define the three “multiplicative bases” : the elementary symmetric functions e_{λ}, the complete symmetric functions h_{λ}, and the power sum symmetric functions p_{λ}. These bases are multiplicative in the sense that if λ = (a_{1}, b_{1})(a_{2}, b_{2}) ⋯ then e_{λ} = e_{(a_{1},b_{1})}e_{(a_{2},b_{2})} ⋯ and similarly for the other bases. We define e_{(a,b)} by

1 + ∑_{a, b} e_{(a,b)}s^{a}t^{b} = ∏_{i}(1 + x_{i}s + y_{i}t),

so that e_{(a,b)} = m_{(1,0)^{a}(0,1)^{b}}, and we define h_{(a,b)} by

1 + ∑_{a, b} h_{(a,b)}s^{a}t^{b} = ∏_{i} \frac{1}{1 − x_{i}s − y_{i}t}.

Note that in general h_{(a,b)} is not a sum of m_{λ}’s with unit coefficients. For example,

h_{(1,1)} = x_{1}y_{1} + y_{1}x_{1} + x_{1}y_{2} + y_{1}x_{2} + ⋯ = 2m_{(1,1)} + m_{(1,0)(0,1)}.

We define p_{(a,b)} by

p_{(a,b)} = ∑_{i} x_{i}^{a}y_{i}^{b} = m_{(a,b)}.

By taking logarithms and exponentiating we obtain

(9.1) 1 + ∑_{a,b} e_{(a,b)}s^{a}t^{b} = exp( ∑_{k+l>0}(−1)^{k+l−1} \frac{1}{k + l} \binom{k + l}{l}p_{(k,l)}s^{k}t^{l})

and

(9.2)  1 + ∑_{a,b} h_{(a,b)}s^{a}t^{b} = exp( ∑_{k+l>0} \frac{1}{k + l} \binom{k + l}{l}p_{(k,l)}s^{k}t^{l}).

We now show that {e_{λ}}, {h_{λ}}, and {p_{λ}} are in fact bases. Since they have the right cardinality, it is sufficient to show that they span, and in view of (9.1) and (9.2) it is sufficient to show that the p_{λ} span.

We may define a partial order on the bipartite partitions of (a, b) by saying that μ covers λ if λ can be obtained from μ by replacing two parts of μ by their sum. Thus (2, 0)(1, 3) < (1, 0)(1, 0)(1, 0)(0, 3) since (2, 0) = (1, 0) + (1, 0) and (1, 3) = (1, 0) + (0, 3).

It is easy to see that

p_{μ} = ∑_{λ≤μ} c_{λ}m_{λ}

for some integers c_{λ}, with c_{μ} ≠ 0. Thus, for example,

p_{(1,1)(1,1)} = (∑_{i} x_{i}y_{i})(∑_{j} x_{j}y_{j})

= ∑_{i≠j} x_{i}y_{i}x_{j}y_{j} + ∑_{i} x_{i}^{2}y_{i}^{2}

= 2m_{(1,1)(1,1)} + m_{(2,2)}

It follows that these equations can be solved to express the m_{λ} as linear combinations of the p_{λ}, and thus the p_{λ} form a basis.

If every part of λ is of the form (a_{i}, 0), then all of these MacMahon symmetric functions reduce to the corresponding ordinary symmetric functions.

Now let x̄_{1}, x̄_{2}, …, ȳ_{1}, ȳ_{2}, … be new variables. If f is a MacMahon symmetric function let us write f(x, y) for f and f(x̄, ȳ) for f with x̄_{i} replacing x_{i} and ȳ_{i} replacing y_{i}.

Suppose that λ has r_{ij} parts equal to (i, j) for each i and j. Then set

z_{λ} = ∏_{i,j} r_{ij}! (\frac{i! j!}{(i + j − 1)!})^{r_{ij}} .

Note that unlike the case of ordinary symmetric functions, the z_{λ} are not in general integers ; for example, z_{(2,2)} = 2/3. The following formulas are proved similarly to their analogs for ordinary symmetric functions :

(9.3)  ∏_{i,j} \frac{1}{1 − x_{i}x̄_{j} − y_{i}ȳ_{j}} = ∑_{λ} h_{λ}(x, y)m_{λ}(x̄, ȳ)

= ∑_{λ} z_{λ}^{−1}p_{λ}(x, y)p_{λ}(x̄, ȳ) (9.4)

MACMAHON [14, Vol. 2, pp. 286–291] proved the following “law of symmetry” : The coefficient of x_{1}^{a_{1}}y_{1}^{b_{1}}x_{2}^{a_{2}}y_{2}^{b_{2}} ⋯ in h_{(c_{1},d_{1})(c_{2},d_{2})···} is equal to the coefficient of x_{1}^{c_{1}}y_{1}^{d_{1}}x_{2}^{c_{2}}y_{2}^{d_{2}} ⋯ in h_{(a_{1},b_{1})(a_{2},b_{2})···} . MacMahon’s law of symmetry follows easily from (9.3).

Just as in the case of ordinary symmetric functions, we may define a scalar product on MacMahon symmetric functions by ⟨h_{λ}, m_{μ}⟩ = δ_{λμ}. Equivalently, for any symmetric function f, ⟨h_{λ}, f⟩ is the coefficient of x_{1}^{a_{1}}y_{1}^{b_{1}}x_{2}^{a_{2}}y_{2}^{b_{2}} ⋯ in f. MacMahon’s law of symmetry is then equivalent to the formula ⟨h_{λ}, h_{μ}⟩ = ⟨h_{μ}, h_{λ}⟩, which implies that ⟨ , ⟩ is symmetric. It follows from (9.4) by a standard linear algebra argument that ⟨p_{λ}, p_{μ}⟩ = z_{λ}δ_{λμ}.

In the author’s opinion MacMahon’s work on symmetric functions failed to achieve what it might have because of his ignorance of the scalar product, which is understandable, since linear algebra was not well-known in MacMahon’s day. Instead of the scalar product, MacMahon used what he called “Hammond operators,” which can be used for the same purposes. Hammond operators, as explained elegantly and concisely by MACDONALD [12, p. 45], are adjoints of multiplication operators : if f is a symmetric function then the Hammond operator θ_{f} is defined by

⟨θ_{f}(g), h⟩ = ⟨g, fh⟩

for all symmetric functions g and h. Thus in particular, ⟨f, g⟩ = ⟨f · 1, g⟩ = ⟨1, θ_{f}(g)⟩, so if f and g are homogeneous of the same degree, ⟨f, g⟩ = θ_{f}(g). But Hammond operators are undesirable for two reasons. First they disguise the symmetry of the scalar product. Second, they can be represented as differential operators. Although this might seem like an advantage, it seems to be of little use, but misleads by directing attention in the wrong direction.

10. D-finiteness and P-recursiveness. — The theory of D-finiteness for symmetric functions generalizes easily to MacMahon symmetric functions. We call a MacMahon symmetric function D-finite if it is D-finite in the p_{(a,b)}. For example,

∏_{i≠j}(1 + x_{i}y_{j})

is D-finite because it is equal to

exp(∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (p_{(j,0)}p_{(0,j)} − p_{(j,j)})).

It follows that for fixed k, the number of n × n 0-1 matrices with zeros on the diagonal and every row and column sum k is P-recursive as as a function of n.

By using MacMahon symmetric functions in k sets of variables, one can show that for fixed k, the number of k × n Latin rectangles is P-recursive as a function of n. In GESSEL [4] a combinatorial derivation is given of a formula for k × n Latin rectangles which implies P-recursiveness. This formula can also be obtained from MacMahon symmetric functions.

11. Explicit formulas. — We now give two simple examples of the use of MacMahon symmetric functions to derive explicit formulas. First we find the number of 2 × n Latin rectangles. This number is easily seen to be the coefficient of x_{1} ⋯ x_{n}y_{1} ⋯ y_{n} in (∑_{i≠j} x_{i}y_{j})^{n} = e_{(1,1)}^{n}. Thus

the desired number is ⟨h_{(1,1)}^{n}, e_{(1,1)}^{n}⟩. We have

h_{(1,1)} = p_{(1,0)(0,1)} + p_{(1,1)}  and  e_{(1,1)} = p_{(1,0)(0,1)} − p_{(1,1)}.

Therefore, the number of 2 × n Latin rectangles is

⟨h_{(1,1)}^{n}, e_{(1,1)}^{n}⟩ = ⟨(p_{(1,0)(0,1)} + p_{(1,1)})^{n}, (p_{(1,0)(0,1)} − p_{(1,1)})^{n}⟩

= ⟨∑_{i=0}^{n} \binom{n}{i}p_{(1,0)}^{i}p_{(0,1)}^{i}p_{(1,1)}^{n−i},

∑_{j=0}^{n} \binom{n}{j}p_{(1,0)}^{j}p_{(0,1)}^{j}(−1)^{n−j}p_{(1,1)}^{n−j}⟩

= ∑_{i=0}^{n} \binom{n}{i}^{2}(−1)^{n−i}⟨p_{(1,0)}^{i}p_{(0,1)}^{i}p_{(1,1)}^{n−i}, p_{(1,0)}^{i}p_{(0,1)}^{i}p_{(1,1)}^{n−i}⟩

= ∑_{i=0}^{n} \binom{n}{i}^{2}(−1)^{n−i}i! i! (n − i)!

= n! ∑_{i=0}^{n}(−1)^{n−i} \frac{n!}{(n − i)!} = n! D_{n},

where D_{n} is the nth derangement number.

Next we consider Example 3 of Section 7, which involves the coefficient of x_{1}^{u_{1}} … x_{n}^{u_{n}}y_{1}^{v_{1}} … y_{n}^{v_{n}} in

(1 − x_{1} − ⋯ x_{n} − y_{1} − ⋯ − y_{n} + x_{1}y_{1} + ⋯ + x_{n}y_{n})^{−1}.

This coefficient is then ⟨h_{(u_{1},v_{1})(u_{2},v_{2})···}, f⟩, where

\begin{aligned}f & = (1 − p_{(1,0)} − p_{(0,1)} + p_{(1,1)})^{−1} \\ & = ∑_{i,j,k}(−1)^{i}p_{(1,1)^{i}(1,0)^{j}(0,1)^{k}} \frac{(i + j + k)!}{i! j! k!} \end{aligned}

It follows that if λ = (1, 1)^{i}(1, 0)^{j}(0, 1)^{k} then

(11.1)  ⟨p_{λ}, f⟩ = (−1)^{i}(i + j + k)!

and ⟨p_{λ}, f⟩ = 0 for λ not of this form. Now let θ be the homomorphism from the MacMahon symmetric functions to polynomials in z defined by

θ(p_{(1,1)}) = −z, θ(p_{(1,0)}) = θ(p_{(0,1)}) = z,

and θ(p_{(a,b)}) = 0 for other (a, b). Let L be the linear functional on polyomials in z defined by L(z^{n}) = n!, so that L has the integral representation

L(r(z)) = ∫_{0}^{∞}e^{−z}r(z) dz.

It follows from (11.1) that for any symmetric function g,

⟨g, f⟩ = L(θ(g)).

Now let

r_{u,v}(z) = θ(h_{(u,v)}) = ∑_{i=0}^{min \{u,v\}}(−1)^{i} \frac{z^{u+v−i}}{i! (u − i)! (v − i)!}.

Then the coefficient we want is

(11.2)  L(∏_{j=1}^{n} r_{u_{j},v_{j}}(z)).

We note that this result can also be obtained by an argument like that used in the theory of rook polynomials.

For the special case u_{i} = v_{i} = 1 we obtain

⟨h_{(1,1)}^{n}, f⟩ = L((z^{2} − z)^{n}) = ∑_{i=0}^{n}(−1)^{i}\binom{n}{i}(2n − i)!,

as is well-known. (See, for example, STANLEY [21, Exercise 10, p. 89 ; Solution, p. 93].)

REFERENCES

[1] CARTIER (P.) and FOATA (D.). — Problèmes combinatoire de commutation et réarrangements. — Springer-Verlag, 1969 (Lecture Notes in Math., 85).

[2] EVERETT (C.J.) and STEIN (P.R.). — The asymptotic number of integer stochastic matrices, Discrete Math., t. 1, 1971, p. 55–72.

[3] GESSEL (I.M.). — Two theorems on rational power series, Utilitas Math., t. 19, 1981, p. 247–254.

[4] GESSEL (I.M.). — Counting Latin rectangles, Bull. Amer. Math. Soc., t. 16, 1987, p. 79–82.

[5] GOULDEN (I.P.) and JACKSON (D.M.). — Combinatorial Enumeration. — Wiley, 1983.

[6] GOULDEN (I.P.) and JACKSON (D.M.). — Labelled graphs with small vertex degrees and P-recursiveness, SIAM J. Alg. Disc. Meth., t. 7, 1986, p. 60–66.

[7] GOULDEN (I.P.), JACKSON (D.M.), and REILLY (J. W.). — The Hammond series of a symmetric function and its application to P-recursiveness, SIAM J. Alg. Disc. Meth., t. 4, 1983, p. 179–193.

[8] HALL (P.). — The algebra of partitions, Proc. 4th Canadian Math. Cong. [Banff. 1957], p. 147–159. — 1959.

[9] LIPSHITZ (L.). — The diagonal of a D-finite power series is D-finite, J. Algebra, to be published.

[10] LIPSHITZ (L.). — D-finite power series, preprint.

[11] LITTLEWOOD (D.E.). — The Kronecker product of symmetric group representations, J. London Math. Soc., t. 31, 1956, p. 89–93.

[12] MACDONALD (I.G.). — Symmetric Functions and Hall Polynomials. — Oxford University Press, 1979.

[13] MACMAHON (P.A.). — Combinatory Analysis. The foundations of a new theory, Phil. Trans., t. 194, 1900, p. 361–386.

[14] MACMAHON (P.A.). — Combinatory Analysis. — Chelsea, 1960. (Originally published by Cambridge University Press, 1915, 1916).

[15] READ (R.C.). — The enumeration of locally restricted graphs (I), J. London Math. Soc., t. 34, 1959, p. 417–436.

[16] READ (R.C.). — The enumeration of locally restricted graphs (II), J. London Math. Soc., t. 35, 1960, p. 334–351.

[17] READ (R.C.). — The use of S-functions in combinatorial analysis, Canad. J. Math., t. 20, 1968, p. 808–841.

[18] READ (R.C.) and WORMALD (N.C.). — Number of labelled 4-regular graphs, J. Graph Theory, t. 4, 1980, p. 203–212.

[19] REDFIELD (J.H.). — The theory of group reduced distributions, American J. Math., t. 49, 1927, p. 433–455.

[20] STANLEY (R.P.). — Differentiably finite power series, European J. Combin., t. 1, 1980, p. 175–188.

[21] STANLEY (R.P.). — Enumerative Combinatorics, Volume I. — Wadsworth, 1986.

[22] ZEILBERGER (D.). — Sister Celine’s technique and its generalizations, J. Math. Anal. Appl., t. 85, 1982, p. 114–145.

Ira M. Gessel

Department of Mathematics Brandeis University Waltham, MA 02254 USA