Permutation Enumeration Symmetric Functions, and Unimodality

Francesco Brenti^{1} Department of Mathematics University of Michigan Ann Arbor, Michigan 48109-1003 U.S.A.

Abstract We study the polynomials obtained by enumerating a set of permutations with respect to the number of excedances. We prove that these polynomials have only real zeros and are unimodal for many interesting classes of permutations. We then show how these polynomials also arise naturally from the theory of symmetric functions.

1 Introduction

Log-concave and unimodal sequences arise often in combinatorics, algebra, geometry and computer science, as well as in probability and statistics where these concepts were first defined and studied (see [1] for further information and references about the origin of the concept of a unimodal sequence). Even though log-concavity and unimodality have one-line definitions, it has now become apparent that to prove the unimodality or log-concavity of a sequence can sometimes be a very difficult task requiring the use of intricate combinatorial constructions ([15], [19], [32], [33]) or of refined mathematical tools. The number and variety of these tools has been constantly increasing and is quite bewildering and surprising. They include, for example, classical analysis ([5], [29], [30], [31]), linear algebra ([17]), the representation theory of Lie algebras and superalgebras ([16], [21], [22]), the theory of total positivity ([2], [4]), the theory of symmetric functions ([3], [6], [20]), and algebraic geometry ([24]). We refer the interested reader to [25] for an excellent survey of many of these techniques, problems, and results.

In this paper, motivated by a conjecture of R. Stanley, we study the unimodality of some polynomials obtained by enumerating a set of permutations with respect to the number of excedances. We prove that these polynomials are unimodal for many general classes of permutations including conjugacy classes, thus generalizing Stanley’s conjecture. We then show how these polynomials also arise, in a natural though unexpected way, from the theory of symmetric functions.

1Partially supported by NSF grant # DMS 8903246

The organization of the paper is as follows. In the next section we collect some notation, definitions and results that will be needed in the rest of the paper. In §3 we prove that the polynomials obtained by enumerating a conjugacy class of a symmetric group with respect to the number of excedances are symmetric and unimodal and have only real zeros. We then derive some consequences of this result, among which is Stanley’s original conjecture. In §4 we show how the polynomials studied in §3 also arise naturally from the theory of symmetric functions. This approach also leads to the consideration of some related (but more mysterious) polynomials whose study yields some interesting identities for inverse Kostka numbers and characters of the symmetric group (Corollaries ??, ??, and ??). Finally, in §5, we discuss some of the main open problems arising from our work, some conjectures and possible directions for further research.

2 Notation and Preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of this paper. We let P =^{def} {1, 2, 3, …} and N =^{def}P ∪{0}; for a ∈ N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). The cardinality of a set A will be denoted by |A|. A sequence {a_{0}, a_{1}, …, a_{d}} (of real numbers) is called log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for i = 1, …, d − 1. It is said to be unimodal if there exists an index 0 ≤ j ≤ d such that a_{i} ≤ a_{i+1} for i = 0, …, j −1 and a_{i} ≥ a_{i+1} for i = j, …, d−1. It is said to have no internal zeros if there are not three indices 0 ≤ i < j < k ≤ d such that a_{i}, a_{k} ≠ 0 and a_{j} = 0. It is said to be symmetric if a_{i} = a_{d−i} for i = 0, …, ⌊\frac{d}{2}⌋. We say that a polynomial ∑_{i=0}^{d} a_{i} x^{i} is log-concave (respectively, unimodal, with no internal zeros, symmetric) if the sequence {a_{0}, a_{1}, …, a_{d}} has the corresponding property. It is well known that if ∑_{i=0}^{d} a_{i} t^{i} is a polynomial with nonnegative coefficients and with only real zeros, then the sequence {a_{0}, a_{1}, …, a_{d}} is log-concave and unimodal, with no internal zeros (see, e.g., [2], or [7], Thm. B, p.270). If p(x) is a symmetric unimodal polynomial then there is a unique n ∈ N such that x^{n} p (\frac{1}{x}) = p (x). We call the number \frac{n}{2} the center of symmetry of p (x), and we write C(p) = \frac{n}{2}. So, for example, C(x^{2} + 3x^{3} + x^{4}) = 3 and C(1 + x) = \frac{1}{2}. An elementary, though crucial property of symmetric unimodal polynomials, which will be used repeatedly in this paper, is the following.

Proposition 2.1 Let p (x) and q(x) be two symmetric unimodal polynomials. Then p (x) q(x) is a symmetric unimodal polynomial and C(p q) = C(p) + C(q).

Proposition ?? is well known and a proof of it can be found, e. g., in [25], Prop.1.2.

We follow [14, Chap.1, §1] for the basic definitions, notation and terminology about (integer) partitions. In particular, given a partition λ, we let m_{i}(λ) be the multiplicity of i as a part of λ and z_{λ} =^{def} ∏_{i≥1} i^{m_{i}(λ)} m_{i} (λ)!. We also denote by d(λ) the length of the side of the Durfee square of λ, (i.e. d(λ) =^{def} max {i ∈ [n] : λ_{i} ≥ i} if λ = (λ_{1}, …, λ_{n})).

A partition of a (finite) set S is a collection of subsets S = {S_{1}, …, S_{p}} of S (which we may assume indexed so that |S_{1}| ≥ … ≥ |S_{p}|) such that ⋃_{i=1}^{p} S_{i} = S and S_{i} ∩ S_{j} = ∅ for i ≠ j. The type of the partition S is the integer partition T (S) =^{def} (|S_{1}|, |S_{2}|, …, |S_{p}|). Given an integer partition λ of n, we denote by P_{λ}([n]) the collection of all partitions of [n] such that T (S) = λ. For example, if λ = (2, 1, 1), then P_{(2,1,1)}([4]) consists of the 6 partitions 12/3/4, 13/2/4, 14/2/3, 23/1/4, 24/1/3, and 34/1/2. We also let P_{λ}(n) =^{def} |P_{λ}([n])|. The following result is well known (see, e.g., [14, p.22], or [7, Theorem B, p.205]) and is here recalled only for completeness.

Proposition 2.2 Let λ = (λ_{1}, …, λ_{p}) be a partition of n. Then

P_{λ}(n) = \frac{(\begin{matrix}n \\ λ_{1},...,λ_{p} \end{matrix} )}{∏_{i≥1}(m_{i}(λ)!)} .

Let π be a permutation on [n] (considered as a bijection π : [n] → [n]) and i ∈ [n]. We say that i is an excedance (respectively, a descent) of π if π(i) > i (respectively, i ≠ n and π(i) > π(i + 1)). We denote by e(π) (respectively, d(π), c(π)) the number of excedances (respectively, descents, cycles) of π. So, for example, if π = 291586347 then e(π) = 4, d(π) = 3, and c(π) = 3. For n ∈P the polynomial

A_{n}(t) =^{def} ∑_{π∈S_{n}} t^{d(π)+1}

(where S_{n} denotes the symmetric group on n elements) is called the n-th Eulerian polynomial and has been widely studied (see, e.g., [10]), for convenience we will let A_{0}(t) =^{def} 1. Given a partition λ of n we denote by S_{n}(λ) the set of all σ ∈ S_{n} of cycle type λ, we also let C_{n} =^{def} S_{n}((n)). The next result is known (see [10]) but is here recalled and proved for completeness.

Proposition 2.3 Let n ∈ N. Then

∑_{σ∈C_{n+1}} t^{e(σ)} = A_{n}(t) .

Proof. Each σ ∈ C_{n+1} can be written uniquely as an n + 1 cycle of the form σ = (n + 1a_{1} … a_{n}) (so that σ(n + 1) = a_{1}, σ(a_{i}) = a_{i+1} for i = 1, …, n − 1, and σ(a_{n}) = n + 1), we then let \overline{σ} =^{def} a_{n} … a_{1} (i.e. \overline{σ}(i) =^{def} a_{n+1−i}, for i = 1, …, n). The correspondence σ ↦ \overline{σ} is clearly a bijection between C_{n+1} and S_{n}. Furthermore, we have that

e(σ) = #\{i ∈ [n + 1] : σ(i) > i\} = #\{i ∈ [n − 1] : a_{i+1} > a_{i}\} + 1 = d(\overline{σ}) + 1 ,

which establishes the result. □

Let μ = (μ_{1}, …, μ_{l}) ∈ P, (where P denotes the set of all integer partitions). We denote the diagram of μ by D(μ). A special border strip of D(μ) is a border strip that is contained in D(μ) and which has at least 1 cell in the first column of D(μ), (see, e.g., [14, p.31], for the definition of a border srip). The sign of a border strip is (−1)^{r−1} where r is the number of rows that it occupies. A special border strip tabloid T of shape μ is a partition of D(μ) into special border strips. The type of T is its type as a (set) partition. The sign of T, denoted sgn(T), is the product of the signs of the special border strips of T. The following beautiful result appears in [9, Theorem 1], (we refer the reader to [14, Chapter 1, §6] for the definition of the Kostka matrix).

Theorem 2.4 Let λ, μ ∈ P, and K be the Kostka matrix. Then

(K^{−1})_{λ,μ} = ∑_{T} sgn(T)

where the sum is over all special border strips tabloids of shape μ and type λ.

Given λ, μ ∈ P with D(μ) ⊆ D(λ) we denote by f^{λ\μ} the number of standard tableaux of shape λ \ μ.

3 Permutation Enumeration and Unimodality

In this section we prove that the polynomials obtained by enumerating a conjugacy class of a symmetric group with respect to the number of excedances are symmetric and unimodal and have only real zeros. In order to prove this result in a clear and concise way it is convenient to establish a canonical way of writing partitions and permutations. We say that a partition {S_{1}, …, S_{p}} of [n] is indexed in canonical form if |S_{1}| ≥ … ≥ |S_{p}| and for |S_{i}| = |S_{j}| we have that i > j if and only if max(S_{i}) > max(S_{j}). So, for example, the canonical indexing of the partition 157/23/9/4/86 is S_{1} = {1, 5, 7}, S_{2} = {2, 3}, S_{3} = {8, 6}, S_{4} = {4}, S_{5} = {9}. Analogously, we say that the cycles C_{1}, …, C_{p} appearing in the disjoint cycle decomposition of a permutation π ∈ S_{n} are indexed in canonical form if |C_{1}| ≥ … ≥ |C_{p}| and for |C_{i}| = |C_{j}| we have that i > j if and only if max(C_{i}) > max(C_{j}). We can now prove one of the main results of this section.

Theorem 3.1 Let n ∈ P and λ = (λ_{1}, …, λ_{p}) be a partition of n. Then

∑_{π∈S_{n}(λ)} t^{e(π)} = \frac{n!}{z_{λ}} ∏_{i=1}^{p} \frac{A_{λ_{i}−1}(t)}{(λ_{i} − 1)!} .  (1)

Proof: Let (S_{i})_{i=1,...,p} be a partition of [n] of type λ, written in canonical form. We define a map

Φ : P_{λ}([n]) × ∏_{i=1}^{p}(C_{[λ_{i}]}) → S_{n}(λ)

by

Φ((S_{i})_{i=1,...,p} , (σ_{i})_{i=1,...,p}) =^{def} ∏_{i=1}^{p} T_{S_{i}}(σ_{i}) ,

where, for a subset S =^{def} {a_{1}, … a_{r}}_{<} ⊆ [n] (where S = {a_{1}, …, a_{r}}_{<} means that S = {a_{1}, …, a_{r}} and a_{1} < … < a_{r}), and σ ∈ S_{r}, T_{S}(σ) is the permutation of S defined by

T_{S}(σ)(a_{j}) =^{def} a_{σ(j)} ,

for j = 1, …, r. Clearly, the map σ ↦ T_{S}(σ) is a bijection. Furthermore, we have that

e (∏_{i=1}^{p} T_{S_{i}}(σ_{i})) = ∑_{i=1}^{p} e(σ_{i}) .  (2)

For π ∈ S_{n}(λ) let C_{1} … C_{p} be the disjoint cycle decomposition of π, written in canonical form. We then let S_{i}(π) be the subset of [n] consisting of the elements appearing in C_{i} and C_{i}(π) =^{def} (T_{S_{i}(π)})^{−1}(C_{i}) for i = 1, …, p. Then the map

θ : S_{n}(λ) → P_{λ}([n]) × ∏_{i=1}^{p}(C_{[λ_{i}]})

defined by

θ(π) =^{def} ( (S_{i}(π))_{i=1,...,p} , (C_{i}(π))_{i=1,...,p})

is such that (Φ ∘ Θ)(π) = π for all π ∈ S_{n}(λ). This proves that Φ is a bijection and hence, by (??), that

∑_{π∈S_{n}(λ)} t^{e(π)} = \frac{(\begin{matrix}n \\ λ_{1},...,λ_{p} \end{matrix} )}{∏_{i≥1}(m_{i}(λ)!)} ∏_{i=1}^{p} ( ∑_{σ∈C_{λ_{i}}} t^{e(σ)})

and (??) follows from Proposition ??. □

In what follows we will let, for simplicity,

E_{D}(t) =^{def} ∑_{π∈D} t^{e(π)} ,

for any D ⊆ S_{n}, and E_{λ}(t) =^{def} E_{S_{n}(λ)}(t) if λ is a partition of n. From the preceding theorem we immediately deduce the following result.

Theorem 3.2 Let n ∈ P and λ be a partition of n. Then the polynomial E_{λ}(t) is symmetric and unimodal with center of symmetry at \frac{|λ|−m_{1}(λ)}{2}, and has only real zeros. In particular, E_{λ}(t) is log-concave with no internal zeros.

Proof. It is well known (see, e.g., [7, p.241, eq.[5c], and p.292, Ex.3]) that, for n ≥ 1, A_{n}(t) is a symmetric and unimodal polynomial with C(A_{n}) = \frac{n+1}{2}. Therefore, from (??) and Proposition ?? we conclude that E_{μ}(t) is a symmetric and unimodal polynomial and that

C(E_{μ}) = C (∏_{i=1}^{p} A_{μ_{i}−1}) = C (∏_{i≥2}(A_{i−1})^{m_{i}(μ)}) =
= ∑_{i≥2} m_{i}(μ)\frac{i}{2} = \frac{|μ| − m_{1}(μ)}{2} .

Furthermore, it is well known (see, e.g., [7, p.292]) that, for n ≥ 1, the polynomials A_{n}(t) have only real zeros, hence, by (??), the same is true for E_{μ}(t). □

Theorem ?? has some interesting consequences, we begin with the following one.

Theorem 3.3 Let n, k, r ∈ P and let D_{r,k}(n) be the set of all π ∈ S_{n} having exactly k cycles each of length > r. Then E_{D_{r,k}(n)}(t) is a symmetric and unimodal polynomial with C(E_{D_{r,k}(n)}) = \frac{n}{2}.

Proof. Let μ =^{def} (μ_{1}, …, μ_{k}) be a partition of n of length k such that μ_{i} > r for i = 1, …, k. Then, by Theorem ??, E_{μ}(t) is a symmetric and unimodal polynomial with C(E_{μ}) = \frac{|μ|−m_{1}(μ)}{2} = \frac{|μ|}{2} = \frac{n}{2}. But, by our definitions

E_{D_{r,k}(n)} = ∑_{μ} E_{μ} ,

where the sum is over all partitions μ = (μ_{1}, …, μ_{k}) of length k such that μ_{i} > r for i = 1, …, k, and the thesis follows. □

One consequence of the preceding result is particularly interesting (see [7, p.257] for the definition of r-derangements). Theorem 3.4 Let n, r ∈ P and let D_{r}(n) be the set of all r-derangements of S_{n}. Then E_{D_{r}(n)}(t) is a symmetric and unimodal polynomial with C(E_{D_{r}(n)}) = \frac{n}{2}. Proof. Clearly

E_{D_{r}(n)} = ∑_{k≥1} E_{D_{r,k}(n)} ,

so the thesis follows from Theorem ??. □

In the case r = 1 the preceding result had been conjectured by Stanley (see the comments preceding and following Proposition 7.8 in [25]) and first proved in [3, Corollary 1]. We should remark, however, that the proof given in [3] makes use of the theory of symmetric functions while the one given here is elementary and completely combinatorial.

4 Symmetric functions and excedances

In this section we show how the combinatorially defined polynomials studied in the preceding section arise naturally from the theory of symmetric functions. We will use standard notation and terminology for this theory from [14]. In particular, we will denote by s_{λ} (respectively, h_{λ}, e_{λ}, m_{λ}, f_{λ}, and p_{λ}) the Schur (respectively, complete homogeneous, elementary, monomial, forgotten and power sum ) symmetric functions, associated to the partition λ. All the symmetric functions considered in this section are assumed to be in the variables (x_{1}, x_{2}, …). We start by defining a ring homomorphism

ξ : Λ Q[[t]] → Q[x][[t]]

by letting

ξ(e_{i}) =^{def} \frac{(1 − x)^{i−1}}{i!} ,  (3)

for i ∈ P, and ξ(e_{0}) =^{def} 1. Since the e_{i}’s are algebraically independent and generate ΛQ over Q (see, e.g., [14, p.13]) (??) uniquely defines a ring homomorphism ξ : ΛQ → Q[x]; we then extend ξ to all of Λ Q[[t]] by letting

ξ (∑_{n≥0} a_{n}t^{n}) =^{def} ∑_{n≥0} ξ(a_{n}) t^{n} ,  (4)

where a_{n} ∈ ΛQ for n ∈ N. It is then easy to check that the map ξ defined by (??) is still a ring homomorphism.

Theorem 4.1 Let ξ : ΛQ → Q[x] be the ring homomorphism defined by (??). Then, for n ∈ P, we have that

ξ(h_{n}) = \frac{A_{n}(x)}{x n!} .  (5)

Proof. It is a well known result in the theory of symmetric functions that

(∑_{n≥0} e_{n}(−t)^{n})^{−1} = ∑_{n≥0} h_{n} t^{n}

in ΛQ[[t]] (see, e.g., [14, p.14]). Therefore, by (??) and (??), we obtain that

∑_{n≥0} ξ(h_{n}) t^{n} = (∑_{n≥0} ξ(e_{n})(−t)^{n})^{−1}
= (\frac{e^{t (x−1)} − x}{1 − x})^{−1}
= 1 + ∑_{n≥1} \frac{A_{n}(x)}{x n!} t^{n} ,

where we have used a well known generating function for Eulerian polynomials (see, e.g., [7, eq.[5j], p.244]), and the thesis follows. □

We now come to one of the main results of this section.

Theorem 4.2 Let ξ : ΛQ → Q[x] be the ring homomorphism defined by (??) and λ be a partition of n. Then

ξ(p_{λ}) = \frac{z_{λ}}{n!} ∑_{π∈S_{n}(λ)} x^{e(π)} .

Proof. Define a second ring homomorphism \overline{ξ} : ΛQ → Q[x] by letting

\overline{ξ}(p_{i}) =^{def} \frac{A_{i−1}(x)}{(i − 1)!} ,

for i ∈ P, and \overline{ξ}(p_{0}) =^{def} 1 (note that \overline{ξ} is a well defined ring homomorphism since the p_{i}’s are algebraically independent and generate ΛQ over Q [14, p.16]). Then, for any partition λ =^{def} (λ_{1}, …, λ_{l}), we have, by Theorem ??, that

\overline{ξ}(p_{λ}) = ∏_{i=1}^{l} \overline{ξ}(p_{λ_{i}}) = ∏_{i=1}^{l} \frac{A_{λ_{i}−1}(x)}{(λ_{i} − 1)!} = \frac{z_{λ}}{|λ|!} ∑_{π∈S_{n}(λ)} x^{e(π)} .  (6)

Therefore, using a well known identity in the theory of symmetric functions (see, e.g., [14, (2.14’), p.17]), we obtain that, for n ∈ P

\overline{ξ}(h_{n}) = \overline{ξ} (∑_{λ⊢n} z_{λ}^{−1} p_{λ})
= ∑_{λ⊢n} z_{λ}^{−1} \overline{ξ}(p_{λ})
= ∑_{λ⊢n} \frac{1}{|λ|!} ∑_{π∈S_{n}(λ)} x^{e(π)}
= \frac{1}{n!} ∑_{π∈S_{n}} x^{e(π)}
= \frac{A_{n}(x)}{x n!} ,

(where we have used Proposition 1.3.12 of [23]). By Theorem ?? this shows that \overline{ξ}(h_{n}) = ξ(h_{n}) for all n ∈ N and since the h_{n}’s are algebraically independent and generate ΛQ over Q (see, e.g., [14, p.14]) this implies that \overline{ξ} ≡ ξ, which, by (??), gives the desired result. □

Note that even though our definition (??) of ξ had nothing to do with excedances, they have now come naturally into the picture.

The preceding results show that ξ(e_{λ}), ξ(h_{λ}) and ξ(p_{λ}) all have simple combinatorial interpretations and (by Theorem ??) only real zeros. It is therefore natural to ask whether ξ(s_{λ}), ξ(f_{λ}), and ξ(m_{λ}) have combinatorial interpretations and whether they also have only real zeros or are symmetric and unimodal. Before doing this we note two general results that follow easily from Theorems ?? and ?? and that will be used in the sequel, (we denote by ΛQ^{n} the set of all elements of ΛQ that are homogeneous of degree n).

Proposition 4.3 Let n ∈ P, k ∈ [n], and a ∈ ΛQ^{n} be such that

a = ∑_{λ} c_{λ} h_{λ} ,

where c_{λ} = 0 unless l(λ) = k. Then ξ(a) is a symmetric polynomial with C(ξ(a)) = \frac{n−k}{2}. Furthermore, if the c_{λ}’s are nonnegative, the ξ(a) is a unimodal polynomial.

Proof. As was observed in the proof of Theorem ??, the polynomials A_{n}(x) are symmetric and unimodal with C(A_{n}) = \frac{n+1}{2}, for n ≥ 1. This, by Proposition ?? and Theorem ??, implies that ξ(h_{λ}) is a symmetric and unimodal polynomial with C(ξ(h_{λ})) = \frac{|λ|−l(λ)}{2}, for all partitions λ, and the result follows. □

The proof of the following result is similar to that of the preceding one, and is therefore omitted.

Proposition 4.4 Let n ∈ P, k ∈ N, k ≤ n, and a ∈ ΛQ^{n} be such that

a = ∑_{λ} b_{λ} p_{λ} ,

where b_{λ} = 0 unless m_{1}(λ) = k. Then ξ(a) is a symmetric polynomial with C(ξ(a)) = \frac{n−k}{2}. Furthermore, if the b_{λ}’s are nonnegative, then ξ(a) is a unimodal polynomial. □

We will see later that the conditions of the preceding two propositions are not as restrictive as they may appear at first glance.

We now turn our attention to the investigation of the polynomials ξ(s_{λ}). We begin with the following result.

Proposition 4.5 Let n ∈ P and λ be a partition of n. Then

ξ(s_{λ}) = \frac{1}{n!} ∑_{\{w∈S_{n}: c(w)≥d(λ)\}} χ^{λ}(w) x^{e(w)} ,  (7)

where χ^{λ} is the irreducible character of S_{n} associated to λ.

Proof. It is a well known result (see, e.g., [14, p.62]) that

s_{λ} = ∑_{μ} z_{μ}^{−1} χ_{μ}^{λ} p_{μ} .

Applying ξ to both sides and using Theorem ?? we then obtain

ξ(s_{λ}) = \frac{1}{n!} ∑_{μ} χ_{μ}^{λ} ∑_{w∈S_{n}(μ)} x^{e(w)}
= \frac{1}{n!} ∑_{w∈S_{n}} χ^{λ}(w) x^{e(w)} .  (8)

Furthermore, it follows immediately from [14, Ex.5, p.64], that χ^{λ}(w) = 0 if c(w) ≤ d(λ) − 1, and (??) follows. □

We note the following curious consequence of (??).

Corollary 4.6 Let n ∈ P and λ be a partition of n. Then ξ(s_{λ})(x) equals the immanant corresponding to λ of the n × n matrix (a_{ij})_{1≤i , j≤n} where

a_{ij} =^{def} \{ \begin{matrix}1 , & if i ≤ j, \\ x , & if i > j. □ \end{matrix}

Even though immanants have received some attention in recent years (see, e.g., [12], [13], [26], [27]) the preceding result seems to be of little use in the understanding of the polynomials ξ(s_{λ}). An interesting consequence of Proposition ?? is the following.

Proposition 4.7 Let n ∈ P and λ be a partition of n. Then

ξ(s_{λ})(0) = \frac{f^{λ}}{n!} .

Proof. Since the only permutation of S_{n} having no excedances is the identity, letting x = 0 in (??) yields that

ξ(s_{λ})(0) = \frac{χ^{λ}(Id)}{n!} .

But it is well known (see, e.g., [14, p.62]) that χ^{λ}(Id) = f^{λ}, and the thesis follows. □

It is also possible to obtain an expression for ξ(s_{λ}) using the inverse Kostka matrix.

Proposition 4.8 Let n ∈ P and λ be a partition of n. Then

ξ(s_{λ}) = \frac{1}{n!} ∑_{μ} (\begin{matrix}n \\ μ_{1},μ_{2},... \end{matrix}) (K^{−1})_{μ,λ′}(1 − x)^{n−l(μ)} .  (9)

Proof. It is well known (see, e.g, [14, Chap.I, §6]) that

s_{λ} = ∑_{μ}(K^{−1})_{μ,λ} h_{μ} .  (10)

Applying the automorphism ω (see [14, Chap.I, §2]) to both sides of (??) we obtain that

s_{λ′} = ∑_{μ}(K^{−1})_{μ,λ}e_{μ}  (11)

Applying ξ to both sides of (??) and using (??) we get

ξ(s_{λ′}) = ∑_{μ}(K^{−1})_{μ,λ} \frac{(1 − x)^{|μ|−l(μ)}}{∏_{i≥1}(i!)^{m_{i}(μ)}} ,

and the thesis follows. □

An important consequence of the preceding proposition is the following result.

Proposition 4.9 Let λ = (λ_{1}, …, λ_{p}) ∈ P. Then ξ(s_{λ}) is divisible by (1 − x)^{|λ|−λ_{1}}.

Proof. From Proposition ?? we see that, for i = 1, 2, …, |λ|, the coefficient of (1 − x)^{|λ|−i} in ξ(s_{λ}) equals

\frac{1}{n!} ∑_{\{μ: l(μ)=i\}} (\begin{matrix}|λ| \\ μ_{1},μ_{2},... \end{matrix}) (K^{−1})_{μ,λ′}

But, from Theorem ??, we know that (K^{−1})_{μ,λ′} = 0 unless l(μ) ≤ l(λ′) (since if l(μ) > l(λ′) then there are no special border strip tabloids of shape λ′ and type μ) and the thesis follows. □

Note that the above result is not best possible since, for example, if λ = (3, 3) then ξ(s_{(3,3)}) = \frac{5}{6!}(1 − x)^{4} even though |λ| − λ_{1} = 3.

It seems to be difficult, in general, to give an explicit formula for ξ(s_{λ}). However, as we will now show, this is possible if λ is a hook. We begin with the following result which follows easily from Theorem ??.

Lemma 4.10 Let λ ∈ P, n =^{def} |λ|, r ∈ [n] and μ =^{def} (r, 1^{n−r}). Then

(K^{−1})_{λ μ} = (\begin{matrix}l(λ) \\ m_{1}(λ),...,m_{n}(λ) \end{matrix}) (−1)^{n−l(λ)+r−1} \frac{m_{≥r}(λ)}{l(λ)}  (12)

where m_{≥r}(λ) =^{def} ∑_{i=r}^{n} m_{i}(λ).

Proof. To choose a special border strip tabloid of shape (r, 1^{n−r}) and type λ we may first choose the special border strip H that contains the upper left square of D(r, 1^{n−r}) (note that this implies that |H| ≥ r) and then choose a special border strip tabloid of shape (1^{n−|H|}) and type λ\{H}. But all the border strips of D(1^{n−|H|}) are vertical, hence such a special border strip tabloid is equivalent to a permutation of the multiset {1^{m_{1}(λ)}, …, n^{m_{n}(λ)}} \ {H}. Therefore

(K^{−1})_{λ,(r,1^{n−r})} = ∑_{{r≤i≤n: m_{i}(λ)>0}}(−1)^{i−r}(K^{−1})_{λ\{i},(1^{n−i})}
= ∑_{i=r}^{n}(−1)^{i−r} (\begin{matrix}l(λ)−1 \\ m_{1}(λ),...,m_{i}(λ)−1,...,m_{n}(λ) \end{matrix}) (−1)^{n−l(λ)+1−i} ,

and (??) follows. □

Using the preceding lemma we obtain the following result. We denote by S(n, k), for n, k ∈ N, the Stirling numbers of the second kind, i.e. S(n, k) is the number of partitions of [n] into k blocks.

Theorem 4.11 Let n ∈ P and r ∈ [n]. Then

ξ(s_{(n−r+1,1^{r−1})}) = \frac{(−1)^{r−1}}{n!} ∑_{k=1}^{n−r+1}(k − 1)! (x − 1)^{n−k} ∑_{i=r}^{n} (\begin{matrix}n \\ i \end{matrix}) S(n − i, k − 1) . (13)

Proof. Let μ =^{def} (r, 1^{n−r}), then, using Lemma ??, (??) becomes

ξ(s_{(n−r+1,1^{r−1})}) = ∑_{λ} (\begin{matrix}l(λ) \\ m_{1}(λ),...,m_{n}(λ) \end{matrix}) (−1)^{|λ|−l(λ)+r−1} \frac{(1 − x)^{|λ|−l(λ)}}{∏_{i=1}^{n}(i!)^{m_{i}(λ)}} \frac{m_{≥r}(λ)}{l(λ)}

= (−1)^{r−1} ∑_{λ} \frac{(l(λ) − 1)!}{∏_{i=1}^{n}(m_{i}(λ)!)(i!)^{m_{i}(λ)}} m_{≥r}(λ) (x − 1)^{|λ|−l(λ)} . (14)

But if l(λ) > n − r + 1 then m_{i}(λ) = 0 for i = r, …, n (because if m_{i}(λ) ≥ 1 for some r ≤ i ≤ n, then i is a part of λ and hence l(λ) ≤ n − i + 1 ≤ n − r + 1), hence using Proposition ?? we deduce from (??) that

ξ(s_{(n−r+1,1^{r−1})}) = \frac{(−1)^{r−1}}{n!} ∑_{k=1}^{n−r+1}(k − 1)! (x − 1)^{n−k} ∑_{\{λ: l(λ)=k\}} ∑_{i=r}^{n} m_{i}(λ)P_{λ}(n) . (15)

To prove (??) it is therefore sufficient to show that

∑_{\{λ: l(λ)=k\}} m_{i}(λ)P_{λ}(n) = (\begin{matrix}n \\ i \end{matrix}) S(n − i, k − 1) .  (16)

But the LHS of (??) counts pairs (π, S) where π is a partition of [n] into k blocks, having at least one block of size i, and S is a block of π of size i, while the RHS of (??) counts pairs (π′, S) where S is a subset of [n] of size i and π′ is a partition of [n] \ S into k − 1 blocks. Since the map (π, S) ↦ (π \ S, S) is clearly a bijection between these sets of pairs, (??) follows and this concludes the proof. □

We should mention that the preceding theorem can also be derived from Ex. 9 on p.30 of [14]. However, we thought a combinatorial proof to be more illuminating.

As an immediate consequence of (??),Theorems ?? and ?? we obtain the following expansion for Eulerian polynomials, when expressed in terms of powers of (x − 1), originally due to Frobenius (see [7, Theorem E, p.244]).

Corollary 4.12 Let n ∈ P. Then

A_{n}(x) = x ∑_{k=0}^{n} k! S(n, k) (x − 1)^{n−k} .  (17)

Proof. Letting r = 1 in (??) we obtain that

ξ(s_{(n)}) = \frac{1}{n!} ∑_{λ} l(λ)! P_{λ}(n) (x − 1)^{n−l(λ)} .  (18)

But it is well known [14, p.26] that s_{(n)} = h_{n} in ΛQ, hence (??) follows from (??) and Theorem ??. □

Besides giving a nice combinatorial interpretation to ξ(s_{λ}) when λ is a hook, Theorem ?? can also be used to obtain a simple recurrence relation satisfied by these polynomials. In order to state the recurrence relation in a concise form it is convenient to normalize the ξ(s_{λ})’s as follows. For n ∈ P and r ∈ [n] we let

T_{n,r}(x) =^{def} (−1)^{r−1} x^{n−1} n! ξ(s_{(n−r+1,1^{r−1})}) (\frac{x + 1}{x}) .  (19)

We then have the following result.

Theorem 4.13 Let n ∈ P and r ∈ [n]. Then the polynomials T_{n,r}(x) defined by (??) satisfy the recurrence relation

T_{n,r}(x) = T_{n−1,r−1}(x) + x T_{n−1,r}(x) + (x^{2} + x) T′_{n−1,r}(x)  (20)

for r ≥ 2, with the initial conditions

T_{n,1}(x) = \frac{x^{n}}{x + 1} A_{n} (\frac{x + 1}{x}) , T_{n,n}(x) = 1

for n ∈ P.

Proof. Theorem ?? (and its proof) show that the coefficient of x^{k−1} in T_{n,r}(x) counts pairs (π, S) where S is a subset of [n] of size ≥ r and π is an ordered partition of [n] \ S into k − 1 blocks, (let T_{n,r}^{(k)} denote this number). If n ∈ S, then the map (π, S) ↦ (π, S \ {n}) is a bijection with the pairs enumerated by T_{n−1,r−1}^{(k)}. If n ∉ S, then there are two cases. If {n} is a block of π, then (π \ {n}, S) is a pair enumerated by T_{n−1,r}^{(k−1)} and each such pair is obtained k − 1 times (since π is ordered). If n is in a block of π of size ≥ 2, then removing it from this block yields a pair (π′, S) enumerated by T_{n−1,r}^{(k)}, and each such pair is obtained k − 1 times (since π has k − 1 blocks). Therefore

T_{n,r}^{(k)} = T_{n−1,r−1}^{(k)} + (k − 1) (T_{n−1,r}^{(k−1)} + T_{n−1,r}^{(k)})  (21)

for n ≥ 2 and k, r ∈ [n]. Multiplying both sides of (??) by x^{k−1} and summing for k = 1, …, n now yields (??); the initial conditions follow immediately from (??), (??), and (??), and the well known facts [14, p.26] that s_{(n)} = h_{n}, s_{(1^{n})} = e_{n}, for n ∈P. □

We now come to our main result about the polynomials ξ(s_{λ}). Given a partition λ = (λ_{1}, …, λ_{n}) let d =^{def} d(λ). We will find it convenient to associate to λ two partitions α(λ) =^{def} (α_{1}, …, α_{d}) and β(λ) =^{def} (β_{1}, …, β_{d}) defined by

α_{i} =^{def} λ_{i} − d(λ) ,

β_{i} =^{def} λ′_{i} − d(λ) ,

for i = 1, …, d(λ). Note that this implies that

λ = (α_{1} + d − 1, α_{2} + d − 2, …, α_{d}|β_{1} + d − 1, β_{2} + d − 2, …, β_{d})  (22)

if λ is written in Frobenius notation. For example, if λ = (7, 6, 3, 3, 1, 1) then d(λ) = 3, α(λ) = (4, 2), and β(λ) = (3, 1, 1). We also let α̃ =^{def} (α_{1} − α_{d}, α_{1} − α_{d−1}, …, α_{1} − α_{2}). Recall that the sum of two partitions λ =^{def} (λ_{1}, λ_{2}, …) and μ =^{def} (μ_{1}, μ_{2}, …) is the partition λ + μ =^{def} (λ_{1} + μ_{1}, λ_{2} + μ_{2}, …).

Theorem 4.14 Let n ∈ P and λ be a partition of n. Then the polynomial ξ(s_{λ}) has degree |λ| − d(λ) and leading coefficient

(−1)^{|β(λ)|} \frac{f^{γ(λ)\δ(λ)}}{|λ|!}

where γ(λ) =^{def} (α_{1} + d(λ))^{d(λ)} + β(λ), and δ(λ) = α̃(λ).

Proof. Note first that if λ = (n − r + 1, 1^{r−1}) for some r ∈ [n] then α̃(λ) = ∅ and (λ_{1})^{d(λ)} + β(λ) = (n) so that

(−1)^{|β(λ)|} \frac{f^{γ(λ)\δ(λ)}}{n!} = (−1)^{r−1} \frac{f^{(n)}}{n!} = \frac{(−1)^{r−1}}{n!}

and the result follows directly from Theorem ??. So assume that the result holds for hooks and let λ = (a_{1}, …, a_{r}|b_{1}, …, b_{r}), where a_{1} > a_{2} > … > a_{r} ≥ 0, b_{1} > b_{2} > … > b_{r} ≥ 0, and r =^{def} d(λ). It is a well known fact in the theory of symmetric functions (see, e.g., [14, Ex.9, p.30]) that

s_{λ} = det [s_{(a_{i}|b_{j})}]_{1≤i , j≤r} .  (23)

Applying now the homomorphism ξ to both sides of (??) we obtain that

ξ(s_{λ}) = det [ξ(s_{(a_{i}|b_{j})})]_{1≤i , j≤r}
= ∑_{σ∈S_{r}} sgn (σ) ξ(s_{(a_{1}|b_{σ(1)})}) … ξ(s_{(a_{r}|b_{σ(r)})}) .  (24)

Since the thesis holds for hooks, we know that ξ(s_{(a_{i}|b_{j})}) is a polynomial of degree a_{i} + b_{j} with leading coefficient (−1)^{b_{j}} \frac{1}{(a_{i}+b_{j}+1)!}. Therefore, from (??), we conclude that deg(ξ(s_{λ})) ≤ ∑_{i=1}^{d(λ)}(a_{i} + b_{j}) = |λ| − d(λ) and the coefficient of x^{|λ|−d(λ)} in ξ(s_{λ}) equals

(−1)^{∑_{i=1}^{r} b_{i}} det [\frac{1}{(a_{i} + b_{j} + 1)!}]_{1≤i , j≤r} = (−1)^{∑_{i=1}^{r} b_{i}+(\begin{matrix}r \\ 2 \end{matrix})} det [\frac{1}{(b_{i} + a_{r+1−j} + 1)!}]_{1≤i , j≤r}
= (−1)^{|β(λ)|+2(\begin{matrix}r \\ 2 \end{matrix})} det [\frac{1}{(γ_{i} − i − δ_{j} + j)!}]_{1≤i , j≤r} (25)

and since it is well known that this last determinant equals \frac{f^{γ\δ}}{|λ|!} (see, e.g., [11, §5.4.8]), the thesis follows. □

Theorem ?? has several interesting consequences.

Corollary 4.15 Let n ∈ P and λ be a partition of n. Then

∑_{\{μ: l(μ)=d(λ)\}} (\begin{matrix}n \\ μ_{1},μ_{2},... \end{matrix}) (K^{−1})_{μ,λ′} = (−1)^{n−d(λ)+|β(λ)|} f^{γ(λ)\δ(λ)} .  (26)

Proof. This follows immediately from Proposition ?? and Theorem ??. □

Corollary 4.16 Let n ∈ P and λ be a partition of n. Then

∑_{{w∈S_{n}: e(w)=n−d(λ)}} χ^{λ}(w) = (−1)^{|β(λ)|} f^{γ(λ)\δ(λ)} .  (27)

Proof. This follows immediately from Proposition ?? and Theorem ??. □

Corollary 4.17 Let λ ∈ P be such that α(λ) = ∅. Then

ξ(s_{λ}) = \frac{f^{λ}}{|λ|!} (1 − x)^{|λ|−d(λ)} .

Proof. If α(λ) = ∅ then λ_{1} = d(λ) and the thesis follows from Propositions ?? and ?? and Theorem ??.□

From Proposition ?? and the preceding corollary we also obtain the following result.

Corollary 4.18 Let λ ∈ P be such that α(λ) = ∅ and n =^{def} |λ|. Then

∑_{\{w∈S_{n}: e(w)=i\}} χ^{λ}(w) = (−1)^{i} (\begin{matrix}n−d(λ) \\ i \end{matrix}) f^{λ} ,

for i = 0, 1, 2, . . .. □

It would be interesting to obtain combinatorial proofs of (??) and (??) as they might shed some light on the combinatorial interpretation of the coefficient of x^{i} in ξ(s_{λ}) also for i < |λ| − d(λ). In particular, we feel that a Schensted-type correspondence should exist that proves (??).

So far we have concentrated on the combinatorial properties of ξ(s_{λ}). It seems to be difficult to say anything general about the unimodality properties of ξ(s_{λ}). In this direction we are only able to give the following result, which follows easily from Proposition ??.

Proposition 4.19 Let λ ∈ P be such that β(λ) = ∅. Then ξ(s_{λ}) is a symmetric polynomial with center of symmetry at \frac{|λ|−d(λ)}{2}.

Proof. Let λ = (λ_{1}, …, λ_{k}). Since β(λ) = ∅ this means that λ_{k} ≥ k and hence that k = d(λ). Since λ_{k} > k − 1, the Jacobi-Trudi identity implies that s_{λ} satisfies the conditions of Proposition ??, and the thesis follows. □

We now look at some properties of the polynomials ξ(m_{λ}). To do this we will first need the following result, which is also of independent interest.

Lemma 4.20 Let n ∈ P. Then

p_{n} = ∑_{μ⊢n}(−1)^{n−l(μ)} (\begin{matrix}l(μ) \\ m_{1}(μ),m_{2}(μ),... \end{matrix}) \frac{n}{l(μ)} e_{μ} .

Proof. Let, for convenience, P (t) =^{def} ∑_{r≥0} p_{r+1} t^{r} and E(t) =^{def} ∑_{r≥0} e_{r} t^{r}. Then it is well known (see, e.g., [14, p.16]) that

P (−t) = E′(t)/E(t)

(as formal power series in ΛQ[[t]]). Therefore

P (−t) = E′(t) ∑_{r≥0}(1 − E(t))^{r}
= E′(t) ∑_{r≥0} (− ∑_{i≥1} e_{i} t^{i})^{r}
= ∑_{r≥0}(r + 1) e_{r+1} t^{r} ∑_{λ}(−1)^{l(λ)} (\begin{matrix}l(λ) \\ m_{1}(λ),m_{2}(λ),... \end{matrix}) e_{λ} t^{|λ|} .

Equating the coefficients of t^{n} on both sides of the equality we obtain

(−1)^{n} p_{n+1} = ∑_{r=0}^{n}(r + 1) e_{r+1} ∑_{λ⊢n−r}(−1)^{l(λ)} (\begin{matrix}l(λ) \\ m_{1}(λ),m_{2}(λ),... \end{matrix}) e_{λ}
= ∑_{μ⊢n+1} e_{μ} ∑_{r≥1}(−1)^{l(μ)−1} (\begin{matrix}l(μ) \\ m_{1}(μ),m_{2}(μ),... \end{matrix}) \frac{r m_{r}(μ)}{l(μ)}

for n ∈ N, and the thesis follows. □

We can now prove our first main result on the polynomials ξ(m_{λ}).

Theorem 4.21 Let n ∈ P and λ = (λ_{1}, λ_{2}, …) be a partition of n. Then ξ(m_{λ}) is a polynomial of degree |λ| − 1 and leading coefficient

\frac{(−1)^{l(λ)−1}}{n!} \frac{|λ|}{l(λ)} (\begin{matrix}l(λ) \\ m_{1}(λ),m_{2}(λ),... \end{matrix}) .

Furthermore, ξ(m_{λ}) is divisible by (1 − x)^{|λ|−λ_{1}}.

Proof. Since the e_{λ}’s are a basis for Λ we have that

m_{λ} = ∑_{μ} A_{λ, μ} e_{μ}  (28)

for some integers A_{λ μ}, where the sum runs over all partitions of |λ|. Applying ξ to both sides of (??) yields

ξ(m_{λ}) = ∑_{μ} A_{λ, μ} \frac{(1 − x)^{|λ|−l(μ)}}{∏_{i≥1}(μ_{i}!)} .  (29)

But it is known (see, [14, Chap.I, §6]) that if A_{λ, μ} ≠ 0 then μ ≥ λ′ (in the reverse lexicographic ordering) and hence, in particular, l(μ) ≤ l(λ′) = λ_{1}. Hence we conclude from (??) that (1 − x)^{|λ|−λ_{1}} divides ξ(m_{λ}). Furthermore, there follows from (??) that deg(ξ(m_{λ})) ≤ |λ| − 1 and that the coefficient of x^{|λ|−1} in ξ(m_{λ}) equals

\frac{(−1)^{n−1}}{n!} A_{λ,(n)} .

But, using some well known properties of the operator ω : Λ → Λ and of the inner product <, > on Λ (see [14, Chap.I, §4] for details) we obtain from (??) and Lemma ?? that

A_{λ,(n)} = ⟨m_{λ}, f_{(n)}⟩
= ⟨ω(m_{λ}) , ω(f_{(n)})⟩
= ⟨f_{λ} , m_{(n)}⟩
= ⟨f_{λ} , p_{n}⟩
= (−1)^{n−l(λ)} (\begin{matrix}l(λ) \\ m_{1}(λ),m_{2}(λ),... \end{matrix}) \frac{n}{l(λ)} ,

and the thesis follows. □

Note that the second part of the above result is not best possible since, for example, if λ = (3, 3) then ξ(m_{(3,3)}) = \frac{−1}{240}x(x − 1)^{4} even though |λ| − λ_{1} = 3.

It is also possible to obtain an analogue of Proposition ?? for the polynomials ξ(m_{λ}). Given n ∈ P and a partition λ of n we let P_{λ} be the digraph consisiting of the disjoint union of m_{i}(λ) directed paths of size i, for i ≥ 1. We then define a function I_{λ} : S_{n} → N by letting, for w ∈ S_{n}, I_{λ}(w) be the number of (directed) subgraphs of the functional digraph of w (see, e.g., [7, p.29]) isomorphic to P_{λ}.

Proposition 4.22 Let n ∈ P and λ be a partition of n. Then

ξ(m_{λ}) = \frac{(−1)^{n−l(λ)}}{n!} ∑_{\{w∈S_{n}:c(w)≤l(λ)\}} sgn (w) I_{λ}(w) x^{e(w)} .  (30)

Proof. It follows from [27, Proposition 1.1] (see also [26, §3]) that

m_{λ} = \frac{(−1)^{n−l(λ)}}{n!} ∑_{w∈S_{n}} sgn (w) I_{λ}(w) p_{ρ(w)} ,  (31)

where ρ(w) is the cycle type of w. But it is clear that I_{λ} is a class function and that I_{λ}(w) = 0 unless c(w) ≤ l(λ), hence we may rewrite (??) as

m_{λ} = (−1)^{n−l(λ)} ∑_{\{μ:l(μ)≤l(λ)\}}(−1)^{n−l(μ)} I_{λ}^{μ} \frac{p_{μ}}{z_{μ}} ,  (32)

where I_{λ}^{μ} denotes the value of I_{λ} on permutations of cycle type μ. Applying now ξ to both sides of (??) and using Theorem ?? yields

ξ(m_{λ}) = \frac{(−1)^{n−l(λ)}}{n!} ∑_{\{μ:l(μ)≤l(λ)\}}(−1)^{n−l(μ)} I_{λ}^{μ} ∑_{w∈S_{n}(μ)} x^{e(w)} ,

and (??) follows. □

Note that it is possible to derive the first part of Theorem ?? from Proposition ??. However, we thought a self-contained proof to be preferable. As an immediate consequence of the preceding proposition we obtain the following result.

Corollary 4.23 Let n ∈ P and λ be a partition of n, λ ≠ (1^{n}). Then ξ(m_{λ}) is divisible by x. □

As is the case for the ξ(s_{λ})’s, it seems to be difficult, in general, to give an explicit formula for ξ(m_{λ}), except when λ is a hook. In order to do this we will first need the following result.

Lemma 4.24 Let n ∈ P and r ∈ [n]. Then

m_{(n−r+1,1^{r−1})} = ∑_{i=0}^{r−1}(−1)^{r−1−i} p_{n−i} e_{i} .  (33)

Proof. Note that, for r ∈ [n],

p_{n−r+1} e_{r−1} = ∑_{i≥1} x_{i}^{n−r+1} e_{r−1} (x_{1}, x_{2}, …)
= ∑_{i≥1} x_{i}^{n−r+1} [e_{r−1} (x_{1}, …, x_{i−1}, x_{i+1}, …) + x_{i} e_{r−2} (x_{1}, …, x_{i−1}, x_{i+1}, , …)]
= m_{(n−r+1,1^{r−1})} + m_{(n−r+2,1^{r−2})} ,

(where m_{(n−r+2,1^{r−2})} =^{def} 0 if r = 1). Inverting this system of linear equations yields (??). □

We can now prove the following surprising result.

Theorem 4.25 Let n ∈ P and r ∈ [n]. Then

ξ(m_{(n−r+2,1^{r−1})}) = x ξ(s_{(n−r+1,1^{r−1})}) .

Proof. Note that it follows from Theorems ?? and ?? that

ξ(p_{n+1}) = x ξ(h_{n})

for n ∈ P. Hence from Lemma ?? we conclude that

ξ(m_{(n−r+2,1^{r−1})}) = ∑_{i=0}^{r−1}(−1)^{r−1−i} ξ(p_{n+1−i}) ξ(e_{i})
= x ∑_{i=0}^{r−1}(−1)^{r−1−i} ξ(h_{n−i}) ξ(e_{i})
= x ξ(s_{(n−r+1,1^{r−1})}) ,

where in the last equality we have used a well known symmetric functions identity (see [14, Ex.9, p.30]). □

Since so many of the results that we have proved for the ξ(s_{λ})’s have an analogue for the ξ(m_{λ})’s it is natural to ask whether Corollary ?? and Proposition ?? also have an analogue for the latters. Unfortunately,

ξ(m_{(3,3,3)}) = \frac{3}{9!} x(x + 1)(x − 1)^{6} ,

which shows that the condition α(λ) = ∅ is not sufficient to imply that ξ(m_{λ})/x is a power of (1 − x). However, a much stronger version of Proposition ?? holds for the ξ(m_{λ})’s, in fact we have the following result.

Proposition 4.26 Let λ ∈ P be such that m_{1}(λ) = 0. Then ξ(m_{λ}) is a symmetric polynomial with center of symmetry at \frac{|λ|}{2}.

Proof. Let λ ∈ P be such that m_{1}(λ) = 0. Then it follows immediately from their definition that (if |μ| = |λ|) then I_{λ}^{μ} = 0 unless m_{1}(μ) = 0. Therefore from (??) we conclude that m_{λ} satisfies the conditions of Proposition ?? , and the thesis follows. □

We conclude this section by investigating the polynomials ξ(f_{λ}), where f_{λ} denotes the “forgotten ” symmetric function associated to λ. These functions are defined by f_{λ} =^{def} ω(m_{λ}) and we refer the reader to [14, Chap. I, §2] and [8] for further information about them. The theory of the ξ(f_{λ})’s is parallel to that of the ξ(m_{λ})’s, but simpler.

Theorem 4.27 Let n ∈ P and λ = (λ_{1}, λ_{2}, …) be a partition of n. Then ξ(f_{λ}) is a polynomial of degree |λ| − 1 and leading coefficient

\frac{(−1)^{|λ|−l(λ)}}{n!} \frac{|λ|}{l(λ)} (\begin{matrix}l(λ) \\ m_{1}(λ),m_{2}(λ),... \end{matrix}) .

Proof. Since the e_{λ}’s are a basis for Λ we have that

f_{λ} = ∑_{μ} C_{λ, μ} e_{μ}

for some integers C_{λ, μ}, where the sum runs over all partitions of |λ|. Reasoning as in the proof of Theorem ?? we conclude that deg(ξ(f_{λ})) ≤ |λ| − 1 and that the coefficient of x^{|λ|−1} in ξ(f_{λ}) equals

\frac{(−1)^{n−1}}{n!} C_{λ,(n)} .

But

f_{(n)} = ω (m_{(n)}) = ω (p_{n}) = (−1)^{n−1} p_{n} .

Hence

C_{λ,(n)} = ⟨f_{λ}, f_{(n)}⟩
= (−1)^{n−1} ⟨f_{λ}, p_{n}⟩
= (−1)^{l(λ)−1} (\begin{matrix}l(λ) \\ m_{1}(λ),m_{2}(λ),... \end{matrix}) \frac{n}{l(λ)} ,

by Lemma ??, and the thesis follows. □

Proposition 4.28 Let n ∈ P and λ be a partition of n. Then

ξ(f_{λ}) = \frac{(−1)^{n−l(λ)}}{n!} ∑_{\{w∈S_{n}: c(w)≤l(λ)\}} I_{λ}(w) x^{e(w)} .

Proof. Applying the automorphism ω to both sides of (??) yields

f_{λ} = (−1)^{n−l(λ)} ∑_{\{μ: l(μ)≤l(λ)\}} I_{λ}^{μ} \frac{p_{μ}}{z_{μ}} ,

reasoning now as in the proof of Proposition ?? gives the desired result. □

Corollary 4.29 Let n ∈ P and λ be a partition of n, λ ≠ (1^{n}). Then ξ (f_{λ}) is divisible by x. □

Proposition 4.30 Let n ∈ P and r ∈ [n]. Then (−1)^{n−r} ξ(f_{(n−r+1,1^{r−1})}) is a unimodal polynomial.

Proof. If r = n then f_{(1^{n})} = ω(m_{(1^{n})}) = ω(e_{n}) = h_{n} and the thesis follows from Proposition ??. If r ≤ n − 1 then applying the automorphism ω to both sides of (??) we obtain that

f_{(n−r+1,1^{r−1})} = (−1)^{n−r} ∑_{i=0}^{r−1} p_{n−i} h_{i} .

Applying now ξ to both sides of this equality we get

ξ (f_{(n−r+1,1^{r−1})}) = (−1)^{n−r} ∑_{i=0}^{r−1} ξ (p_{n−i}) ξ (h_{i}) .  (34)

But, from Propositions ??, ?? , and ?? we deduce that ξ(p_{n−i}) ξ(h_{i}) is a symmetric unimodal polynomial with center of symmetry at \frac{n−i}{2} + \frac{i−1}{2} = \frac{n−1}{2} if 1 ≤ i ≤ r − 1 and \frac{n}{2} if i = 0. Therefore ∑_{i=0}^{r−1} ξ (p_{n−i}) ξ (h_{i}) is a unimodal (but not necessarily symmetric) polynomial, and the thesis follows from (??). □

It is not hard to give a simple combinatorial interpretation of the polynomials considered in the previous result using Proposition ??. Given n ∈ P and w ∈ S_{n} we let c_{i}(w) be the number of cycles of w of lenght i, for i = 1, …, n.

Proposition 4.31 Let n ∈ P and r ∈ [n]. Then

(−1)^{n−r} ξ (f_{(n−r+1,1^{r−1})}) = \frac{1}{n!} ∑_{\{w∈S_{n}:c(w)≤r\}} ∑_{i=n−r+1}^{n} i c_{i} (w) x^{e(w)} .  (35)

Proof. It follows immediately from its definition that if λ = (n − r + 1, 1^{r−1}) and w ∈ S_{n} then I_{λ}(w) equals the sum of the lenghts of the cycles of w having size ≥ n − r + 1, and (??) follows from Proposition ?? . □

The proof of the following result is similar to that of Proposition ?? and is therefore omitted.

Proposition 4.32 Let λ ∈ P be such that m_{1}(λ) = 0. Then (−1)^{|λ|−l(λ)} ξ (f_{λ}) is a symmetric unimodal polynomial with center of symmetry at \frac{|λ|}{2}. □

5 Conjectures and Open Problems

There are several problems that are suggested by the research presented in this paper. Most of them concern the ring homomorphism ξ defined by (??). In view of Theorem ?? and Proposition ?? it is natural to define, for λ ∈ P, S_{λ}(x) and M_{λ}(x) to be the unique polynomials such that

ξ(s_{λ}) = \frac{(−1)^{|β(λ)|}}{|λ|!} (x − 1)^{p(λ)} S_{λ}(x) ,

ξ(m_{λ}) = \frac{(−1)^{l(λ)−1}}{|λ|!} (x − 1)^{q(λ)} M_{λ}(x) ,

and S_{λ}(1), M_{λ}(1) ≠ 0, for some (necessarily unique) p(λ), q(λ) ∈ N. Regarding these polynomials we feel that the following statements are true.

Conjecture 5.1 Let λ ∈ P. Then M_{λ}(x) has only real zeros.

Conjecture 5.2 Let λ ∈ P. Then S_{λ}(x) has only real zeros.

These conjectures have been verified for |λ| ≤ 8. Unfortunately, the interest in the above conjectures is somewhat diminished by the fact that the polynomials M_{λ}(x) and S_{λ}(x) do not always have nonnegative coefficients. For example, one can compute that S_{(4,4)}(x) = 14 (x^{2} − 6x + 1) and M_{(4,4)}(x) = 4x (x^{2} − 16x + 1). In particular, this shows that S_{λ}(x) need not be unimodal even if β(λ) = ∅. However, it would be interesting to know for which partitions λ we have that S_{λ}(x), M_{λ}(x) ∈ N[x]. In this respect, we feel that the following statement holds.

Conjecture 5.3 Let λ be a hook. Then the polynomial S_{λ}(x) (equivalently, M_{λ}(x)) has nonnegative coefficients and only real zeros. In particular, it is log-concave and unimodal.

This conjecture has been verified for |λ| ≤ 8. It is not hard to show that it holds if l(λ) ≤ 2 or if l(λ′) ≤ 3, we have also verified that it holds if 3 ≤ l(λ) ≤ 5 and |λ| ≤ 12. As further evidence that S_{λ}(x) ∈ N[x] if λ is a hook let us mention that it follows easily from our definitions and Theorem ?? that

S_{(n−r+1,1^{r−1})}(1) = (n)_{n−r} ,

for n ∈ P and r ∈ [n]. Thus it is possible that a simple combinatorial interpretation exists for the coefficients of S_{λ}(x) when λ is a hook.

From the algebraic point of view the most intersting problem about ξ is that of characterizing its kernel. Theorems ?? and ?? imply that

ξ(p_{n+1} − p_{2} h_{n}) = 0 ,

for n ∈ P. This naturally suggests the following question.

Problem 5.4 Does {p_{n+1} − p_{2} h_{n} : n ∈ P} generate ker(ξ)?

From the point of view of permutation enumeration we feel that the results presented in §3 naturally suggest the investigation of the following general question.

Problem 5.5 For which subsets T ⊆ S_{n} does the polynomial E_{T} (x) =^{def} ∑_{π∈T} x^{e(π)} have only real zeros?

Theorem ?? shows that the answer to the above problem is affirmative if T is a conjugacy class of S_{n}. That the answer is affirmative for T = S_{n} is a well known, but nontrivial, classical result (see, e.g., [7, p.292, Ex.3]) while for T = D_{n} (where D_{n} denotes the set of all derangements of S_{n}) it was conjectured in [3, p.1140] and recently proved by R. Canfield (private communication). That there should be many more subsets T for which Problem ?? has an affirmative solution is also suggested, in view of the close relationship existing between excedances and descents (see, e.g., [23, Proposition 1.3.12]), by the following conjecture, which was made by R. Stanley in 1986.

Conjecture 5.6 Let (P, ω) be a finite labeled poset and L(P, ω) ⊆ S_{|P |} be its Jordan Hölder set (see, e.g., [23, p.131], for the definition of this terminology). Then the polynomial ∑_{π∈L(P,ω)} x^{d(π)} has only real zeros.

Conjecture ?? can be stated in many equivalent ways (see, e.g., [2, §§1.2, 1.4, and 6.3]) and is known as the “Poset Conjecture” or as the “Neggers-Stanley Conjecture” (since J. Neggers conjectured it in the case that ω is a natural labeling). It is known to be true for many infinite classes of posets but is still open in general, even for natural labelings. We refer the reader to [2], [18], [25], and [29] for further information about it. Acknowledgements. The author would like to thank Phil Hanlon, Ian Macdonald, John Stembridge, and Richard Stanley for some valuable discussions. The computations in this paper have been carried out using a Maple package for handling symmetric functions developed by John Stembridge.

References

[1] E. Bertin and R. Theodorescu, On the unimodality of Discrete Probability Measures, Math. Zeitschrift, 201 (1989), 131-137.

[2] F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., no.413, 1989.

[3] F. Brenti, Unimodal polynomials arising from symmetric functions, Proc. Amer. Math. Soc., 108(1990),1133-1141.

[4] F. Brenti, Log-concavity and combinatorial properties of Fibonacci Lattices, Europ. J. Combin., to appear.

[5] F. Brenti, Expansions of chromatic polynomials and log-concavity, Trans. Amer. Math. Soc., to appear.

[6] L. Butler, A unimodality result in the enumeration of subgroups of a finite abelian group, Proc. Amer. Math. Soc., 101(1987),771-775.

[7] L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974.

[8] P. Doubilet, On the foundations of combinatorial theory VII: Symmetric functions through the theory of distribution and occupancy, Studies Appl. Math., 51(1972), 377-396.

[9] O. Egecioglu and J. Remmel, A combinatorial interpretation of the inverse Kostka matrix, Linear Multilinear Algebra, 26(1990), 59-84.

[10] D. Foata and M. Schutzenberger Theorie geometrique des polynomes euleriens, Lecture Notes in Mathematics, no.138, Springer-Verlag, Berlin-New York, 1970.

[11] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley, New York, 1983.

[12] I. Goulden and D. Jackson, Immanants of combinatorial matrices, research report CORR 89-30, Univ. of Waterloo, 1989.

[13] C. Greene, Proof of a conjecture on immanants of the Jacobi-Trudi matrix, preprint.

[14] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, New York/London, 1979.

[15] K. O’Hara, Unimodality of Gaussian coefficients: a constructive proof, J. Combin. Theory Ser. A. 53 (1990) 29-52.

[16] R. Proctor, Representations of sl(2,C) on posets and the Sperner property, SIAM J. Algebraic Discrete Methods 3 (1982), 275-280.

[17] R. Proctor, Solution of two difficult combinatorial problems with linear algebra, Amer. Math. Monthly, 89 (1982), 721-734.

[18] V. Reiner, Quotients of Coxeter complexes and P-Partitions, Ph.D. Thesis, 1990, Massachusetts Institute of Technology.

[19] B. Sagan, Inductive and injective proofs of log concavity results, Discrete Math., 68 (1988), 281-292.

[20] B. Sagan, Log-concave sequences of symmetric functions and analogs of the Jacobi-Trudi determinant, Trans. Amer. Math. Soc., to appear.

[21] R. Stanley, Unimodal sequences arising from Lie algebras, in Young Day Proceedings T. V. Narayana, R. M. Mathsen, and J. G. Williams, eds., Dekker, New York/Basel, 1980, pp. 127-136.

[22] R. Stanley, Unimodality and Lie superalgebras, Studies in Applied Math. 72 (1985), 263-281.

[23] R. Stanley, Enumerative Combinatorics, vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[24] R. Stanley, Generalized h-vectors, intersection cohomology of toric varieties, and related results, Advanced Studies in Pure Math. 11 (1987), 187-213.

[25] R. Stanley, Log-concave and unimodal sequences in Algebra, Combinatorics and Geometry, Annals of the New York Academy of Sciences, 576 (1989), 500-534.

[26] R. Stanley and J. Stembridge, On immanants of Jacobi-Trudi matrices and permutations with restricted position, preprint.

[27] J. Stembridge, Some conjectures for immanants, preprint.

[28] J. Stembridge, Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Discrete Math., to appear.

[29] D. Wagner, Enumerative Combinatorics of partially ordered sets, and total positivity of Hadamard products, Ph.D. Thesis, 1989, Massachusetts Institute of Technology.

[30] D. Wagner, The partition polynomial of a finite set system, J. Combin. Theory Ser. A, to appear.

[31] D. Wagner, Total positivity of Hadamard products, J Math. Analysis and Applications, to appear.

[32] D. E. White, Monotonicity and unimodality of the pattern inventory, Advances in Math., 38 (1980), 101-108.

[33] D. Zeilberger, Kathy O’ Hara’ s Constructive Proof of the Unimodality of the Gaussian Polynomials, Amer. Math. Monthly, 96 (1989), 590-602.