A class of q-symmetric functions arising from plethysm

Francesco Brenti^{1} Dipartimento di Matematica Universitá di Roma “Tor Vergata” Via della Ricerca Scientifica, 1 00133 Roma, Italy

Abstract We introduce and study a class of symmetric functions, which depend on a parameter q, and which includes symmetric functions that have already appeared in the literature in connection with Jack symmetric functions, parking functions, and lattices of non-crossing partitions. Our results generalize previous ones by Haiman, Stanley, and the author.

1 Introduction

The purpose of this paper is to study certain symmetric functions, which depend on a parameter q, and which are obtained through a simple plethysm from the classical bases of the ring of symmetric functions. The motivation for this comes from the fact that several symmetric functions that have already appeared in the literature in connection with Jack symmetric functions, parking functions, and lattices of non-crossing partitions, are special cases of this construction. Among our results we obtain generalizations of results of Haiman [11] and Stanley [24], q-analogues of classical results on symmetric functions, as well as of more recent ones by the author [3], and some new combinatorial reciprocity theorems (in the sense of [19]).

The organization of the paper is as follows. In the next section we recall some definitions, and fix some notation, that will be used throughout the rest of this work. In section 3 we define, for each symmetric function f ∈ Λ, a symmetric function f[x]_{q}, which depends on a parameter q, and study the basic properties of this operation which is based on plethysm. We then show that the symmetric functions h_{λ}[x]_{q}, e_{n}[x]_{n+1}, and e_{n}[x]_{n} have already appeared in the literature in connection with Jack symmetric functions (Proposition 3.5), parking functions (Proposition 3.6), and lattices of non-crossing partitions (Proposition 3.7). In sections 4, 5, and 6 we obtain our main results, namely combinatorial rules for the expansions of the symmetric functions m_{λ}[x]_{q}, s_{λ}[x]_{q}, e_{λ}[x]_{q}, and h_{λ}[x]_{q} in terms of monomial, Schur, elementary, and complete symmetric functions. Even though the symmetric functions h_{λ}[x]_{q} have appeared before in the literature in [22] and [14], our results are new even in this case, while they reduce to results of Haiman and Stanley for e_{n}[x]_{n+1}. Also, since f[x]_{1} = f, our results give q-analogues of the usual transition matrices between the classical bases of the ring of symmetric functions. They also yield two combinatorial reciprocity results (Corollaries 4.8 and 6.2) which can be stated without any reference to symmetric functions. In section 7 we obtain, applying the homomorphism ξ defined in [3] to the symmetric functions studied in §§4, 5, and 6, q-analogues of some of the results obtained in [3], and results on a q-analogue of the Eulerian polynomials which does not seem to have been studied before. Finally, in section 8, we present several conjectures and open problems arising from this work.

1Part of this work was carried out while the author was a member of the Mathematical Sciences Research Institute in Berkeley, California, U.S.A., and was partially supported by NSF grant DMS 9022140.

2 Definitions, Notation, and Preliminaries

In this section we collect some definitions and notation that will be used in the rest of this paper. We let P =^{def} {1, 2, 3, …}, N =^{def} P ∪ {0}, and Q be the field of rational numbers; for a ∈ N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). For S ⊆ P we write S = {a_{1}, …, a_{t}}_{<} to mean that S = {a_{1}, …, a_{t}} and a_{1} < … < a_{t}. If q is an indeterminate and i ∈ N then we let (q)_{i} =^{def} q(q − 1) … (q − i + 1), ( i^{q}) =^{def} \frac{(q)_{i}}{i!} , and (( i^{q})) =^{def} (−1)^{i} ( i^{−q}), with the convention that (q)_{0} = ( 0^{q}) = (( 0^{q})) = 1. We denote by R[q] (respectively, R(q), R[[q]]) the ring of polynomials (respectively, rational functions, formal power series) in the variable q with coefficients in the ring R. If P (q) ∈ R[[q]] and i ∈ N then we denote by [q^{i}](P (q)) the coefficient of q^{i} in P (q). We denote by N[q^{i}] (respectively, N [( i^{q})]) the set of all the polynomials that when expanded in terms of the basis {q^{i}}_{i∈N} (respectively, \{(\begin{matrix}q \\ i \end{matrix})\}_{i∈N}), have all coefficients in N. Note that N[q^{i}] ⊆ N [( i^{q})].

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. We say that a polynomial ∑_{i=0}^{d} a_{i} x^{i} is log-concave (respectively, unimodal) if the sequence {a_{0}, a_{1}, …, a_{d}} has the corresponding property. It is well known that if ∑_{i=0}^{d} a_{i} x^{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 (see, e.g., [8, Thm. B, p.270]). Given two polynomials f and g having only real zeros we say that g alternates left of f if deg (g) = deg (f) and we have that

η_{1} ≤ ξ_{1} ≤ η_{2} ≤ … ≤ η_{d} ≤ ξ_{d}

where η_{1}, η_{2}, …, η_{d} are the zeros of g and ξ_{1}, ξ_{2}, …, ξ_{d} are those of f.

We follow [14, Chap. I] for notation and terminology related to partitions. In particular, given a partition λ = (λ_{1}, λ_{2}, …), we denote by λ′ its conjugate, by m_{i}(λ) the number of parts of λ that are equal to i, for i ∈ P, and we then write λ = (1^{m_{1}(λ)}, 2^{m_{2}(λ)}, …).

We also let λ! =^{def} ∏_{i≥1} λ_{i}!, |λ| =^{def} ∑_{i≥1} λ_{i}, l(λ) =^{def} ∑_{i≥1} m_{i}(λ), ε_{λ} =^{def} (−1)^{|λ|−l(λ)}, and

z_{λ} =^{def} ∏_{i≥1}(i^{m_{i}(λ)}m_{i}(λ)!). If n = |λ| then we also write λ ⊢ n. We denote by P the set of all partitions, and we let P_{n} =^{def} {λ ∈ P : |λ| = n} for n ∈ P. We usually identify a partition λ = (λ_{1}, …, λ_{r}) with its diagram {(i, j) ∈ P × P : 1 ≤ i ≤ r, 1 ≤ j ≤ λ_{i}}. In particular, if (i, j) is in (the diagram of) λ then we denote by c(i, j) (respectively, h(i, j)) the content (respectively, hook-length) of (i, j) in λ. We denote by ≤ (respectively, ≤_{R}) the dominance ordering (respectively, refinement order) on P_{n}. If λ, μ ∈ P then we let

λ ∪ μ =^{def} (1^{m_{1}(λ)+m_{1}(μ)}, 2^{m_{2}(λ)+m_{2}(μ)}, …).

Let λ, μ, ν ∈ P, with λ ⊇ μ. We then call λ \ μ (by which we mean the set theoretic difference of the diagrams of λ and μ) a skew diagram. A skew diagram is a horizontal strip (respectively, a vertical strip) if it contains at most one element in each column (respectively, row). By a tableau of shape λ \ μ we mean an array T = (a_{i,j})_{(i,j)∈λ\μ} of positive integers, indexed by the elements in the diagram of λ\μ, such that a_{i,j} ≥ a_{i,j+1} and a_{i,j} > a_{i+1,j} whenever both sides of these inequalities are defined.The weight of the tableau T is the vector w(T) =^{def} (m_{1}(T), m_{2}(T), …), where m_{i}(T) equals the number of entries of T that are equal to i, for i ∈ P. The tableau T is standard if w(T) = (\underbrace{1, …, 1}_{|λ|−|μ|}, 0, 0, …).

As customary, we denote by K_{λ\μ,ν} the number of tableaux of shape λ \ μ and weight ν, and call this a Kostka number. We also let f^{λ\μ} =^{def} K_{λ\μ,(1^{|λ|−|μ|})}.

By a brick we mean a skew diagram that consists of a single row. Given λ ∈ P, a brick tabloid (see, e.g., [14, Chap. I, §6, Ex. 5] where these objects are called, somewhat improperly, domino tabloids) of shape λ is a partition of (the diagram of) λ into bricks. The type of the brick tabloid is its type as a set partition. For example, Figure 1 shows a brick tabloid of shape (5, 3, 2) and type (3, 2, 2, 1, 1, 1). Note that if μ ≰_{R} λ then there are no brick tabloids of shape λ and type μ.

Figure 1.

We follow Chap.I of [14] for symmetric function notation and terminology. In particular, we denote by Λ the ring of symmetric functions, and we let Λ_{Q} =^{def} Λ ⊗_{Z} Q, and ΛQ^{n} be the subspace of all elements of Λ_{Q} that are homogeneous of degree n. Given a partition λ we denote by s_{λ} (respectively, h_{λ}, e_{λ}, m_{λ}, f_{λ}, and p_{λ}) the Schur (respectively, complete, elementary, monomial, forgotten, and power sum) symmetric function, associated to λ. Recall (see, e.g., [14, Chap. I, §2 and §4]) that there is a standard involution ω in Λ_{Q} defined by ω(e_{λ}) = h_{λ} for all λ ∈ P, and a standard scalar product ⟨, ⟩ defined by ⟨h_{λ}, m_{μ}⟩ = δ_{λ,μ} for all λ, μ ∈ P. We will often apply ω and ⟨, ⟩ to elements of Λ ⊗ Q(q). In this case it is to be understood that ω and ⟨, ⟩ act on Q(q) as they do on scalars. For f, g ∈ Λ_{Q} we denote by f ∗ g (respectively, f ∘ g) the internal product (respectively, plethysm) of f and g (see, e.g., [14, Chap. I, §§7-8] for the definition of, and further information about, these operations). We call a basis {a_{λ}}_{λ∈P} of Λ_{Q} standard if, for all n ∈ N, {a_{λ} : λ ⊢ n} is a basis of ΛQ^{n}. Two standard bases {a_{λ}}_{λ∈P} and {b_{λ}}_{λ∈P} are dual if ⟨a_{λ}, b_{μ}⟩ = 0 if λ ≠ μ; a standard basis is orthogonal if it is dual to itself. It is known (see, e.g., [2, Proposition 6.2.1]), and also easy to see, that if f ∈ Λ_{Q} then there exists a polynomial in Q[q], which we denote by f(1^{q}), such that

f(\underbrace{1, 1, …, 1}_{n}, 0, 0, …) = f(1^{n})

for all n ∈ P.

We follow [20] for notation and terminology concerning posets and permutations. In particular, we denote by S_{n} the set of all the permutations on [n]. For π ∈ S_{n} we let e(π) (respectively, c(π)) be the number of excedances (respectively, cycles) of π. Given λ, μ ∈ P_{n} we denote by χ_{μ}^{λ} the value of the irreducible character of S_{n} indexed by λ on permutations of cycle-type μ.

3 Basic Properties

In this section we define, for each symmetric function f ∈ Λ_{Q}, a symmetric function f[x]_{q} ∈ Λ_{Q} ⊗ Q[q], and we derive some basic properties of this operation. We then show that the symmetric functions h_{λ}[x]_{q}, e_{n}[x]_{n+1}, and e_{n}[x]_{n} have already appeared in the literature in connection with Jack symmetric functions, parking functions, and lattices of non-crossing partitions.

Let a(x) ∈ Λ_{Q} (x = (x_{1}, x_{2}, …)) and q be an indeterminate. We define a[x]_{q} to be the only element of Λ ⊗ Q[q] such that

a[x]_{r} = a ∘ (rp_{1}),

for all r ∈ Q (it is easy to see that a[x]_{q} always exists). So, for example, it follows easily from the definition of plethysm that

p_{λ}[x]_{q} = q^{l(λ)}p_{λ},  (1)

for all λ ∈ P, and that if n ∈ P then

a[x]_{n} = a(\underbrace{x_{1}, …, x_{1}}_{n}, \underbrace{x_{2}, …, x_{2}}_{n}, …).  (2)

In particular, a[x]_{1} = a(x).

We begin with some simple results that will be used repeatedly later on.

Proposition 3.1 Let f ∈ Λ_{Q}. Then

ω(f[x]_{q}) = ω(f)[x]_{q} = f[−x]_{−q}.

In particular, f[−x]_{−1} = ω(f).

Proof. Using (1) and a well known property of the involution ω (see, e.g., [14, Chap. I, §2, p. 24, eq. (2.13)]) we have that

ω(p_{λ}[x]_{q}) = ω(q^{l(λ)}p_{λ}) = q^{l(λ)}ω(p_{λ}) = q^{l(λ)}ε_{λ}p_{λ} = ω(p_{λ})[x]_{q}

and

p_{λ}[−x]_{−q} = (−q)^{l(λ)}p_{λ}(−x) = ε_{λ}q^{l(λ)}p_{λ},

for all λ ∈ P. Since {p_{λ}}_{λ∈P} is a basis of Λ_{Q} the result follows by linearity. □

Following [22, §1, p. 77] (see also [14, Chap. VI, §1, p. 305, eq. (1.4)]) we define a (bilinear) scalar product ⟨, ⟩_{q} on Λ ⊗ Q(q) by letting

⟨p_{λ}, p_{μ}⟩_{q} =^{def} q^{l(λ)}z_{λ}δ_{λ,μ}  (3)

for all λ, μ ∈ P, where δ_{λ,μ} = 0 if λ ≠ μ and δ_{λ,λ} = 1. The scalar product defined by (3) is fundamental in the theory of Jack symmetric functions (see, e.g., [22], or [14, Chap. VI, §§1 and 10]). The next result shows that the problem of computing ⟨f, g⟩_{q} is closely related to that of computing f[x]_{q}.

Proposition 3.2 Let f, g ∈ Λ_{Q}, and α, β ∈ Q. Then

⟨f[x]_{α}, g[x]_{β}⟩ = ⟨f, g⟩_{αβ} = (f ∗ g)(1^{αβ}).  (4)

Proof. It is clear from (1) and (3) that

⟨p_{λ}[x]_{α}, p_{μ}[x]_{β}⟩ = ⟨α^{l(λ)}p_{λ}, β^{l(μ)}p_{μ}⟩ = α^{l(λ)}β^{l(μ)}z_{λ} δ_{λ,μ} = ⟨p_{λ}, p_{μ}⟩_{αβ}  (5)

and

⟨p_{λ}, p_{μ}⟩_{αβ} = δ_{λ,μ} z_{λ}(αβ)^{l(λ)} = δ_{λ,μ} z_{λ} p_{λ}(1^{αβ}) = (p_{λ} ∗ p_{μ})(1^{αβ})  (6)

for all λ, μ ∈ P, where we have used two well known orthogonality relations (see, e.g., [14, Chap.I, §4, p.64, eq. (4.7)], and [14, Chap.I, §7, p.116, eq. (7.12)]). Since {p_{λ}}_{λ∈P} is a basis of Λ_{Q} the result follows from (5) and (6) by linearity. □

Proposition 3.3 Let {b_{λ}}_{λ∈P} be a standard basis of Λ_{Q}. Then {b_{λ}[x]_{q}}_{λ∈P} is a standard basis of Λ ⊗ Q(q).

Proof. Let μ ∈ P. Then since {b_{λ}}_{λ∈P} is a standard basis of Λ_{Q} we have that

p_{μ} = ∑_{λ⊢|μ|} a_{μλ}b_{λ}

for some a_{μλ} ∈ Q. Therefore, using (1) yields that

p_{μ} = \frac{p_{μ}[x]_{q}}{q^{l(μ)}} = ∑_{λ⊢|μ|} \frac{a_{μλ}}{q^{l(μ)}} b_{λ}[x]_{q}.

Hence {b_{λ}[x]_{q}}_{λ∈P_{n}} spans Λ^{n} ⊗ Q(q), for all n ∈ P, and the result follows. □

Note that it is not true, in general, that if {b_{λ}}_{λ∈P} is an orthogonal standard basis of Λ_{Q} then {b_{λ}[x]_{q}}_{λ∈P} is orthogonal. For example,

⟨s_{2}[x]_{q}, s_{(1,1)}[x]_{q}⟩ = \frac{1}{2}q^{2}(q^{2} − 1).

However, the following orthogonality result does hold.

Proposition 3.4 Let {u_{λ}}_{λ∈P} and {v_{λ}}_{λ∈P} be dual standard bases of Λ_{Q}. Then {u_{λ}[x]_{q}}_{λ∈P} and \{v_{λ}[x]_{\frac{1}{q}} \}_{λ∈P} are dual standard bases of Λ ⊗ Q(q).

Proof. It is clear from Proposition 3.3 that \{u_{λ}[x]_{q}\}_{λ∈P} and \{v_{λ}[x]_{\frac{1}{q}} \}_{λ∈P} are standard bases of Λ ⊗ Q(q). But it follows immediately from (4) that ⟨f[x]_{q}, g[x]_{\frac{1}{q}} ⟩ = ⟨f, g⟩ for all f, g ∈ Λ_{Q}, so the result follows. □

We conclude this section by showing that the symmetric functions h_{λ}[x]_{q}, e_{n}[x]_{n+1}, and e_{n}[x]_{n} have appeared before in the literature in connection with Jack symmetric functions, parking functions, and lattices of noncrossing partitions.

For λ ∈ P let J_{λ}(x; q) ∈ Λ ⊗ Q(q) be the Jack symmetric function associated to λ (see, e.g., [14, Chap. VI, §10], or [22], for the definition of, and further information about, these symmetric functions). Following [22, §2, p. 82] we then define

J_{λ}(x; q) =^{def} ∏_{i≥1} J_{(λ_{i})}(x; q)  (7)

for any λ = (λ_{1}, λ_{2}, …) ∈ P.

Proposition 3.5 Let λ ∈ P. Then

h_{λ}[x]_{q} = \frac{q^{|λ|}}{λ!} J_{λ} (x; \frac{1}{q}) ,

in Λ ⊗ Q(q). In particular, h_{n}[x]_{q} = \frac{q^{n}}{n!} J_{(n)} (x; \frac{1}{q}).

Proof. It is well known (see, e.g., [14, Chap.I, §2, p.25, eq. (2.14’)]) that h_{n} = ∑_{λ⊢n} z_{λ}^{−1}p_{λ}. Hence using (1) yields that

h_{n}[x]_{q} = ∑_{λ⊢n} \frac{q^{l(λ)}}{z_{λ}} p_{λ}.  (8)

But it is proved in [22, Proposition 2.2(b)] (see also [14, Chap. VI, §10, eq. (10.5) and Ex. 1]) that

J_{(n)}(x; α) = ∑_{λ⊢n} α^{n−l(λ)}n! \frac{p_{λ}}{z_{λ}} ,

so setting α = \frac{1}{q} and comparing with (8) yields that n! h_{n}[x]_{q} = q^{n} J_{(n)}(x; q^{−1}) and the result follows from (7). □ Note that the symmetric functions h_{λ}[x]_{q} also appear in Macdonald’s book [14, Chap. VI, §10, p.378] where they are denoted g_{λ}^{(\frac{1}{q})}(x).

Let n, k ∈ P. A k-parking function of length n is a sequence (a_{1}, …, a_{n}) ∈ P^{n} such that if b_{1} ≤ b_{2} ≤ … ≤ b_{n} is the increasing rearrangement of (a_{1}, …, a_{n}) then b_{i} ≤ ki for i = 1, …, n. Let Π(n, k) denote the set of all k-parking functions of length n. It is clear that if σ ∈ S_{n} and (a_{1}, …, a_{n}) ∈ Π(n, k) then (a_{σ(1)}, …, a_{σ(n)}) ∈ Π(n, k). Hence S_{n} acts on Π(n, k). Following [24, §5, p. 10] we let P F_{n}^{(k)} ∈ Λ be the Frobenius characteristic (see, e.g., [14, Chap. I, §7, p. 113]) of this representation of S_{n}. The symmetric function P F_{n}^{(k)} has been first considered by Haiman for k = 1 (see [11, §§2.6 and 4.1]) and by Stanley in the general case (see [24, §5]).

Proposition 3.6 Let n, k ∈ P. Then

P F_{n}^{(k)} = \frac{1}{n + 1} h_{n}[x]_{k(n+1)}.

Proof. It is proved by Stanley (see [24, §5, p. 10]) that

P F_{n}^{(k)} = \frac{1}{n + 1}[t^{n}] (∏_{i≥1}(1 − x_{i}t)^{−k(n+1)}) .

On the other hand, it follows immediately from (2) and a well known identity in the theory of symmetric functions (see, e.g., [14, Chap. I, §2, p. 21, eq. (2.5)]) that

∑_{n≥0} h_{n}[x]_{m}t^{n} = ∏_{i≥1}(1 − x_{i}t)^{−m},  (9)

for all m ∈ P, so the result follows. □

Let P be a finite graded poset with ˆ0 and ˆ1 and rank function ρ. We denote by F_{P} the formal power series

F_{P} (x_{1}, x_{2}, …) =^{def} ∑_{0=t_{0}≤t_{1}≤...≤t_{k−1}<t_{k}=ˆ1} ∏_{i=1}^{k} x_{i}^{ρ(t_{i})−ρ(t_{i−1})}.  (10)

This formal power series was introduced in [9], and has been further studied in, e.g., [23], [24], and [17]. It is known (see [23, Thm. 1.4]) that if every interval of P is rank-symmetric then F_{P} is a symmetric function. For n ∈ P and S ⊆ [n] we let NC_{n} (respectively, NC_{n}^{BD}(S)) be the poset of all non-crossing set partitions of [n] (respectively, non-crossing B_{n}-partitions that avoid S), ordered by refinement (we refer the reader to [16] for the definition of these posets).

Proposition 3.7 Let n ∈ P. Then

F_{NC_{n+1}} = \frac{1}{n + 1}e_{n}[x]_{n+1},  (11)

and

F_{NC_{n+1}^{BD}(S)} = e_{n+1}[x]_{n+1} − \frac{s}{n}e_{n+1}[x]_{n}  (12)

where s is the cardinality of S.

Proof. We have from Theorem 2.3 of [24] that F_{NC_{n+1}} = ω(P F_{n}^{(1)}), so (11) follows from Propositions 3.1 and 3.6. Furthermore, it follows from the definition (10) and Theorem 11 of [16] that

F_{NC_{n+1}^{BD}(S)} = ∑_{λ⊢n+1} (∏_{i≥1} (\begin{matrix}n+1 \\ λ_{i} \end{matrix}) − \frac{s}{n} ∏_{i≥1} (\begin{matrix}n \\ λ_{i} \end{matrix} )) m_{λ}.

On the other hand, it follows immediately from (2) and a well known identity in the theory of symmetric functions (see, e.g., [14, Chap. I, §2, p. 19, eq. (2.2)]) that

∑_{n≥0} e_{n}[x]_{m}t^{n} = ∏_{i≥1}(1 + x_{i}t)^{m}

and therefore (see also Corollary 4.2 of this work) that

e_{n}[x]_{m} = ∑_{λ⊢n} ∏_{i≥1} (\begin{matrix}m \\ λ_{i} \end{matrix}) m_{λ}

for all m ∈ P, and (12) follows. □

4 m-expansions

In this section we study the expansions of the symmetric functions m_{λ}[x]_{q}, s_{λ}[x]_{q}, h_{λ}[x]_{q}, and e_{λ}[x]_{q}, in terms of monomial symmetric functions.

Let n ∈ P. An n-brick tabloid (respectively, strict n-brick tabloid) is a brick tabloid where each brick has associated an integer in [n] so that the integers associated to the bricks in each row weakly (respectively, strictly) increase from left to right. For example,

4 2  5 1  2 1  3  4

is a (strict) 6-brick tabloid of shape (8, 6, 2, 2) and type (4, 4, 3, 2, 2, 1, 1, 1). In particular, for each λ ∈ P there is a unique strict 1-brick tabloid of shape λ, necessarily of type λ. Note that a 1-brick tabloid is the same as a brick tabloid. We denote by D_{λ,μ}(n) (respectively, \overline{D}_{λ,μ}(n)) the number of n-brick tabloids (respectively, strict n-brick tabloids) of shape λ and type μ.

Theorem 4.1 Let μ ∈ P. Then

m_{μ}[x]_{q} = ∑_{λ} (∑_{i=1}^{l(μ)} \overline{d}_{λ,μ}(i) (\begin{matrix}q \\ i \end{matrix})) m_{λ},  (13)

where \overline{d}_{λ,μ}(i) equals the number of strict i-brick tabloids T of shape λ and type μ such that all the integers in [i] appear in T. In particular, ⟨m_{μ}[x]_{q}, h_{λ}⟩ = \overline{D}_{λ,μ}(q), ⟨m_{μ}[x]_{q}, h_{λ}⟩ = 0 if μ ≰_{R} λ, and deg(⟨m_{μ}[x]_{q}, h_{λ}⟩) = l(μ) if μ ≤_{R} λ.

Proof. Note first that it follows from Propositions 3.1 and 3.2 and well known properties of the scalar product ⟨, ⟩ (see, e.g., [14, Chap. I, §4, p. 64, eq. (4.10)]) that

⟨m_{μ}[x]_{q}, h_{λ}⟩ = ⟨f_{μ}[x]_{q}, e_{λ}⟩ = ⟨f_{μ}, e_{λ}[x]_{q}⟩.  (14)

Fix n ∈ P. We will show, by induction on l(λ), that

\overline{D}_{λ,μ}(n) = ⟨e_{λ}[x]_{n}, f_{μ}⟩.  (15)

If λ = (m) then it is clear that

\overline{D}_{(m),μ}(n) = \frac{l(μ)!}{∏_{i≥1}m_{i}(μ)!} (\begin{matrix}n \\ l(μ) \end{matrix}) .

On the other hand by (2) and a well known identity in the theory of symmetric functions (see, e.g., [14, Chap. I, §2, p. 19, eq. (2.2)]) we have that

∑_{m≥0} e_{m}[x]_{n}t^{m} = ( ∑_{m≥0} e_{m}t^{m})^{n} = ∑_{j≥0} (\begin{matrix}n \\ j \end{matrix}) ( ∑_{m≥1} e_{m}t^{m})^{j} .

Hence

e_{m}[x]_{n} = ∑_{μ⊢m} \frac{(n)_{l(μ)}}{∏_{i≥1}m_{i}(μ)!} e_{μ}  (16)

and (15) follows in this case.

Suppose now that λ = (λ_{1}, …, λ_{r}) with r ≥ 2. Then from our induction hypothesis we have that

e_{λ}[x]_{n} = e\overline{λ}[x]_{n} e_{λ_{r}}[x]_{n}
= ∑_{μ⊢|\overline{λ}|} \overline{D}_{\overline{λ},μ}(n) e_{μ} ∑_{ν⊢λ_{r}} \overline{D}_{(λ_{r}),ν}(n) e_{ν}

= ∑_{ρ} (  ∑_{\{(μ,ν): μ⊢|\overline{λ}|, ν⊢λ_{r}, μ∪ν=ρ\}} \overline{D}_{\overline{λ},μ}(n) \overline{D}_{(λ_{r}),ν}(n)) e_{ρ},

where \overline{λ} =^{def} (λ_{1}, …, λ_{r−1}), and this proves (15). But it is easy to see that

\overline{D}_{λ,μ}(n) = ∑_{i=1}^{l(μ)} \overline{d}_{λ,μ}(i) (\begin{matrix}n \\ i \end{matrix})  (17)

for all n ∈ P, so (13) follows from (14) and (15) since ⟨m_{μ}[x]_{q}, h_{λ}⟩ ∈ Q[q]. The last statements follow easily from (13) by noting that \overline{d}_{λ,μ}(l(μ)) > 0. □

We illustrate the preceding theorem with an example. Let μ = (3, 2, 2) and λ = (5, 2). Then there are only two brick tabloids of shape (5, 2) and type (3, 2, 2) and one easily counts that \overline{d}_{λ,μ}(1) = 0, \overline{d}_{λ,μ}(2) = 4, and \overline{d}_{λ,μ}(3) = 6. Hence the coefficient of m_{(5,2)} in m_{(3,2,2)}[x]_{q} equals q^{2}(q − 1).

A special case of the preceding result takes a particularly simple form which is worth noting explicitly. Given an integer partition λ = (λ_{1}, λ_{2}, …) ∈ P and r ∈ P we let

rλ =^{def} (rλ_{1}, rλ_{2}, …) ∈ P.

Corollary 4.2 Let r, s ∈ P. Then

m_{(r^{s})}[x]_{q} = ∑_{ν⊢s} (∏_{i≥1} (\begin{matrix}q \\ ν_{i} \end{matrix} )) m_{rν}.

In particular, e_{n}[x]_{q} = ∑_{ν⊢n} ∏_{i≥1} (\begin{matrix}q \\ ν_{i} \end{matrix} ) m_{ν}.

Proof. It is clear that (r^{s}) ≤_{R} λ if and only if λ = rν for some ν ⊢ s. In this case we easily see that

\overline{D}_{rν,(r^{s})}(n) = ∏_{i≥1} (\begin{matrix}n \\ ν_{i} \end{matrix})

for all n ∈ P, so the result follows from Theorem 4.1. □

We now examine the expansion of s_{λ\μ}[x]_{q} in terms of monomial symmetric functions. Given a tableau T and a positive integer i ∈ P we let

w_{i}(T) =^{def} (∑_{j=1}^{i} m_{j}(T), ∑_{j=i+1}^{2i} m_{j}(T), …)

and call w_{i}(T) the i-weight of T. For example, if

T = 2 3 4 4 5

then w_{2}(T) = (1, 3, 1, 0, …) and w_{3}(T) = (2, 3, 0, 0, …).

Theorem 4.3 Let λ, μ ∈ P. Then

s_{λ\μ}[x]_{q} = ∑_{ν} ( ∑_{i=1}^{|λ\μ|} k_{λ\μ,ν}(i) (\begin{matrix}q \\ i \end{matrix})) m_{ν},  (18)

where k_{λ\μ,ν}(i) is the number of tableaux T of shape λ \ μ and i-weight ν such that all the congruence classes modulo i are represented in T. In particular, if n ∈ P then ⟨s_{λ\μ}[x]_{n}, h_{ν}⟩ equals the number of tableaux T of shape λ \ μ and n-weight ν.

Proof. Let, for brevity, θ =^{def} λ \ μ. It is well known (see, e.g., [14, Chap. I, §5, p. 73, eq. (5.12)]) that

s_{θ}(x) = ∑_{T} x_{1}^{m_{1}(T)}x_{2}^{m_{2}(T)} …

where T runs over all the tableaux of shape θ. Therefore, if n ∈ P then we conclude from (2) that

s_{θ}[x]_{n} = s_{θ}(\underbrace{x_{1}, …, x_{1}}_{n}, \underbrace{x_{2}, …, x_{2}}_{n}, …)
= ∑_{T} x_{1}^{∑_{i=1}^{n} m_{i}(T)}x_{2}^{∑_{i=n+1}^{2n} m_{i}(T)} ….  (19)

Now fix ν = (ν_{1}, …, ν_{s}) ∈ P. Then, by (19), the coefficient of x_{1}^{ν_{1}} … x_{s}^{ν_{s}} in s_{θ}[x]_{n} equals the number of tableaux T of shape θ and n-weight ν. Since s_{θ}[x]_{n} is a symmetric function this is also the coefficient of m_{ν} in s_{θ}[x]_{n}, and this proves the second statement.

Now let T be a tableau of shape θ and n-weight ν. We define ψ(T) =^{def} (T_{S}, S) where

S =^{def} {j ∈ [n] : ∑_{r≥0} m_{rn+j}(T) > 0}

(i.e., S is the set of all the j ∈ [n] such that T has at least one entry congruent to j modulo n) and T_{S} is the tableau obtained from T by replacing all entries of T equal to rn+j_{k} with ri + k (for k ∈ [i] and r ∈ N), where {j_{1}, …, j_{i}}_{<} =^{def} S. Note that T_{S} is again a tableau since an + j_{k} < bn + j_{l} if and only if ai + k < bi + l (k, l ∈ [i], a, b ∈ N). Furthermore,

∑_{k=1}^{i} m_{ri+k}(T_{S}) = ∑_{k=1}^{i} m_{rn+j_{k}}(T) = ∑_{j=1}^{n} m_{rn+j}(T) = ν_{r+1}

for r ∈ N (since m_{rn+j}(T) = 0 if j ∈ [n] \ S), and

∑_{r=0}^{s−1} m_{ri+k}(T_{S}) = ∑_{r=0}^{s−1} m_{rn+j_{k}}(T) > 0

for k ∈ [i], by our definition of S. Hence the i-weight of T_{S} is ν and all the congruence classes modulo i are represented in T_{S}. It is clear from our definitions that if T and U are two tableaux of shape θ and n-weight ν such that ψ(T) = ψ(U) then T = U. Hence ψ is injective.

Conversely, let R ⊆ [n] and U be a tableau of shape θ and i-weight ν such that

∑_{r≥0} m_{ri+k}(U) > 0

for k ∈ [i], where i =^{def} |R|. Let {j_{1}, …, j_{i}}_{<} =^{def} R. We define a tableau T by replacing all entries of U equal to ri+k with rn+j_{k} (for r ∈ N, and k ∈ [i]). Then T is again a tableau, and reasoning as above we conclude that its n-weight is ν and that ψ(T) = (U, R).

This shows that ψ is a bijection between the set of all tableaux of shape θ and n-weight ν, and the set of all pairs (U, R) where R ⊆ [n] and U is a tableau of shape θ and |R|-weight ν such that every congruence class modulo |R| is represented in U. Since it is clear that k_{θ,ν}(i) = 0 if i > |θ| we conclude, by what has already been proved, that

⟨s_{θ}[x]_{n}, h_{ν}⟩ = ∑_{i=1}^{|θ|} k_{θ,ν}(i) (\begin{matrix}n \\ i \end{matrix})

for all n ∈ P, and the result follows since ⟨s_{θ}[x]_{n}, h_{ν}⟩ is a polynomial function of n. □ We illustrate the preceding theorem with an example. Let λ = (2, 2, 1), μ = ∅, ν = (3, 2), and n = 2, then there are 8 tableaux of shape (2, 2, 1) and 2-weight (3, 2) (namely those shown in Figure 2) and hence ⟨s_{(2,2,1)}[x]_{2}, h_{(3,2)}⟩ = 8.

1 1 2 4 3  1 1 2 3 4  1 1 2 3 3  1 1 2 4 4  1 2 2 4 3  1 2 2 3 4  1 2 2 3 3  1 2 2 4 4

Figure 2: the 8 tableaux of shape (2, 2, 1) and 2-weight (3, 2).

Given an N-matrix A and λ ∈ P we denote by K_{λ,A} the number of tableaux of shape λ and weight given by the entries of A (note that this is well defined by a well known property of Kostka numbers, see, e.g., [14, Chap. I, §5]). Given a partition λ = (λ_{1}, λ_{2}, …) ∈ P

and i ∈ P we let λ^{(i)} =^{def} (λ_{1} + … + λ_{i}, λ_{i+1} + … + λ_{2i}, …).

Proposition 4.4 Let λ, μ, ν ∈ P, and i ∈ P. Then

k_{λ\μ,ν}(i) = ∑_{A∈C(ν,i)} K_{λ\μ,A}  (20)

where C(ν, i) is the set of all the i × l(ν) N-matrices with column sum ν and positive row sum. Furthermore, k_{λ,ν}(i) ≠ 0 only if ν ≤ λ^{(i)}.

Proof. The first statement follows immediately from the definition of k_{λ\μ,ν}(i). Suppose now that k_{λ,ν}(i) ≠ 0 and let T be a tableau of shape λ and i-weight ν. Then, for each r ∈ P, there are exactly ν_{1} + … + ν_{r} entries in T that are ≤ ri. On the other hand, these entries must all lie in the first ri rows of T (by the column strictness of T). Hence ν_{1} + … + ν_{r} ≤ λ_{1} + … + λ_{ri}. □ It would be interesting to know if the converse of the last statement in Proposition 4.4 also holds.

For convenience, let

K_{λ\μ,ν}(q) =^{def} ⟨s_{λ\μ}[x]_{q}, h_{ν}⟩  (21)

for all λ, μ, ν ∈ P. Clearly, K_{λ\μ,ν}(q) ∈ Q[q], and K_{λ\μ,ν}(q) = 0 if |λ \ μ| ≠ |ν|. Furthermore, by Theorem 4.3, K_{λ\μ,ν}(n) equals the number of tableaux of shape λ \ μ and n-weight ν, for all n ∈ P.

Corollary 4.5 Let λ, μ, ν ∈ P be such that |λ \ μ| = |ν|. Then K_{λ\μ,ν}(q) is a polynomial of degree |ν| and leading coefficient

\frac{f^{λ\μ}}{ν_{1}! … ν_{s}!}

where s =^{def} l(ν). Furthermore, K_{λ\μ,(1^{|ν|})}(q) = f^{λ\μ} q^{|ν|}.

Proof. Let A ∈ C(ν, |ν|). Then A is necessarily a (0, 1)-matrix having exactly one nonzero entry in each row, and column sum ν. Hence there are (\begin{matrix}|ν| \\ ν_{1},...,ν_{s} \end{matrix} ) such matrices A and we conclude from (20) that

k_{λ\μ,ν}(|ν|) = ∑_{A∈C(ν,|ν|)} K_{λ\μ,(1^{|ν|})} = (\begin{matrix}|ν| \\ ν_{1},...,ν_{s} \end{matrix} ) f^{λ\μ}

and the result follows from (21) and (18).

Furthermore, given a standard tableau T of shape λ \ μ and an n-tuple (i_{1}, …, i_{n}) ∈ [m]^{n} (where n =^{def} |ν|), the tableau obtained by substituting j with (j − 1)m + i_{j} for j = 1, …, n has shape λ \ μ and m-weight (1^{n}), and this is clearly a bijection, so by (21) and Theorem 4.3 K_{λ\μ,(1^{|ν|})}(m) = f^{λ\μ}m^{|ν|} for all m ∈ P, and the second statement also follows. □

It is well known (see, e.g., [14, Chap. I, §5, Ex.1]) that elementary and complete symmetric functions are skew Schur functions corresponding to vertical and horizontal strips, respectively. Therefore Theorem 4.3 also gives the expansions of e_{λ}[x]_{q} and h_{λ}[x]_{q} in terms of monomial symmetric functions. However, just as in the ordinary case, more explicit combinatorial interpretations can be given in these special cases.

Let m, n, p ∈ P. Given a 3-dimensional m×n×p matrix M = (M_{i,j,k})_{1≤i≤m, 1≤j≤n, 1≤k≤p} we let

S_{1,2}(M) =^{def} (∑_{i=1}^{m} ∑_{j=1}^{n} M_{i,j,1}, …, ∑_{i=1}^{m} ∑_{j=1}^{n} M_{i,j,p})

and define S_{1,3}(M) and S_{2,3}(M) analogously.

Theorem 4.6 Let λ ∈ P. Then

e_{λ}[x]_{q} = ∑_{μ} (∑_{i=1}^{|λ|} M_{λ,μ}(i) (\begin{matrix}q \\ i \end{matrix})) m_{μ}

where M_{λ,μ}(i) is the number of l(λ) × l(μ) × i (0, 1)-matrices M such that S_{2,3}(M) = λ, S_{1,3}(M) = μ, and S_{1,2}(M) > 0. In particular, if n ∈ P then ⟨e_{λ}[x]_{n}, h_{μ}⟩ equals the number of l(λ) × l(μ) × n (0, 1)-matrices M such that S_{2,3}(M) = λ and S_{1,3}(M) = μ.

Proof. Let n ∈ P, θ be a vertical strip consisting of r connected pieces θ_{1}, …, θ_{r} of size λ_{1}, …, λ_{r} respectively, where r =^{def} l(λ), and T be a tableau of (skew) shape θ and n-weight μ. Define a l(λ) × l(μ) × n (0, 1)-matrix M by letting

M_{i,j,k} =^{def} m_{(j−1)n+k}(T_{i})

for i ∈ [l(λ)], j ∈ [l(μ)], and k ∈ [n], where T_{i} is the i-th connected piece of T. It is then clear that S_{2,3}(M) = λ (since |T_{i}| = λ_{i}) and S_{1,3}(M) = μ. Conversely, given an l(λ) × l(μ) × n (0, 1)-matrix N such that S_{2,3}(N) = λ and S_{1,3}(N) = μ we can construct a tableau U of (skew) shape θ by putting (j − 1)n + k in θ_{i} if N_{i,j,k} = 1 (for i ∈ [l(λ)], j ∈ [l(μ)] , k ∈ [n]). Then U has n-weight μ since S_{1,3}(N) = μ.

It is clear that this is a bijection between the set of tableaux T of skew shape θ and n-weight μ and the set of l(λ) × l(μ) × n (0, 1)-matrices M such that S_{2,3}(M) = λ and S_{1,3}(M) = μ, and that all congruence classes modulo n are represented in T if and only if S_{1,2}(M) > 0. Therefore k_{θ,μ}(n) = M_{λ,μ}(n). But it is well known (see, e.g., [14, Chap.I, §5, Ex. 1, p. 74]) that e_{λ} = s_{θ}, so from Theorem 4.3 we have that

⟨e_{λ}[x]_{q}, h_{μ}⟩ = ⟨s_{θ}[x]_{q}, h_{μ}⟩ = ∑_{i=1}^{|θ|} k_{θ,μ}(i) (\begin{matrix}q \\ i \end{matrix})

and the thesis follows. □

Note that it is also possible to prove Theorem 4.6 from Theorem 4.3 and Proposition 4.4 using the well known fact (see, e.g., [14, Chap. I, (5.12), (6.7), and Ex. 1, p. 74]) that if θ is a vertical strip consisting of l(λ) connected pieces of sizes λ_{1}, λ_{2}, … then K_{θ,A} equals the number of (0, 1)-matrices with row sum λ and column sum equal to the entries of A (in some order). However, we thought a self-contained combinatorial proof to be preferable.

The proof of the following result is analogous to that of the previous one, and is therefore omitted.

Theorem 4.7 Let λ ∈ P. Then

h_{λ}[x]_{q} = ∑_{μ} (∑_{i=1}^{|λ|} H_{λ,μ}(i) (\begin{matrix}q \\ i \end{matrix})) m_{μ}

where H_{λ,μ}(i) equals the number of l(λ) × l(μ) × i N-matrices M such that S_{2,3}(M) = λ, S_{1,3}(M) = μ, and S_{1,2}(M) > 0. In particular, if n ∈ P then ⟨h_{λ}[x]_{n}, h_{μ}⟩ equals the number of l(λ) × l(μ) × n N-matrices M such that S_{2,3}(M) = λ and S_{1,3}(M) = μ.

We close this section by noting the following “reciprocity theorem” for the polynomials K_{λ\μ,ν}(q).

Corollary 4.8 Let λ, μ, ν ∈ P. Then

(−1)^{|λ\μ|}K_{λ\μ,ν}(−q) = K_{λ′\μ′,ν}(q)

in Z[q].

Proof. It follows from Proposition 3.1 and a well known property of the involution ω (see, e.g., [14, Chap.I, §5, p. 71, eq. (5.6)]) that s_{λ\μ}[−x]_{−q} = s_{λ′\μ′}[x]_{q}, so the result follows from (21). □

It would be interesting to have a direct combinatorial proof of Corollary 4.8 using the combinatorial interpretation of the polynomials K_{λ\μ,ν}(q) given by Theorem 4.3.

5 s-expansions

In this section we study the expansions of the symmetric functions s_{λ}[x]_{q}, h_{λ}[x]_{q}, e_{λ}[x]_{q}, and m_{λ}[x]_{q} in terms of Schur symmetric functions.

Theorem 5.1 Let λ, μ ∈ P. Then

s_{λ\μ}[x]_{q} = ∑_{ν} (∑_{η} γ_{λ\μ,ν}^{η} ∏_{(i,j)∈η} (\frac{q + c(i, j)}{h(i, j)})) s_{ν},  (22)

where γ_{λ\μ,ν}^{η} =^{def} ⟨s_{λ\μ} ∗ s_{ν}, s_{η}⟩. Furthermore, ⟨s_{λ\μ}[x]_{q}, s_{ν}⟩ is a polynomial in N [(\begin{matrix}q \\ i \end{matrix})] of degree |λ \ μ| and leading coefficient f^{λ\μ}f^{ν}/|λ \ μ|!.

Proof. Let, for brevity, θ =^{def} λ \ μ. Then we have from Proposition 3.2 that ⟨s_{θ}[x]_{q}, s_{ν}⟩ = (s_{θ} ∗ s_{ν})(1^{q}). Hence

s_{θ}[x]_{q} = ∑_{ν}(s_{θ} ∗ s_{ν})(1^{q})s_{ν}.  (23)

By the definition of the γ_{θ,ν}^{η} we have that

s_{θ} ∗ s_{ν} = ∑_{η} γ_{θ,ν}^{η} s_{η}.  (24)

But it is well known (see, e.g., [14, Chap.I, §3, Ex. 4, p.45]) that

s_{η}(1^{q}) = ∏_{(i,j)∈η} (\frac{q + c(i, j)}{h(i, j)})

so (22) follows from (23) and (24).

Furthermore, it is known (see, e.g., [2, Theorem 5.2.3, p. 59]) and also follows easily from [14, Chap.I, §5, (5.12), p. 73] that s_{η}(1^{q}) is the order polynomial of a certain labeled poset associated to η, and hence is in N [(\begin{matrix}q \\ i \end{matrix})] (see, e.g., [18, Proposition 13.1, p. 45], or [2, §1.2, p. 1]). Since s_{θ} is a nonnegative linear combination of Schur functions, and the numbers ⟨s_{θ} ∗ s_{ν}, s_{η}⟩ are nonnegative integers (see, e.g., [14, Chap. I, §7]), we conclude that ⟨s_{θ}[x]_{q}, s_{ν}⟩ ∈ N [(\begin{matrix}q \\ i \end{matrix})]. Finally, it is known (see, e.g., [14, Chap.I, §7, (7.2) and Ex. 3]) that

s_{θ} = ∑_{η} \frac{χ_{η}^{θ}}{z_{η}} p_{η}.  (25)

Hence using (1) and another well known identity in the theory of symmetric functions ([14, Chap.I, §7, (7.8)]) yields that

s_{θ}[x]_{q} = ∑_{η} \frac{χ_{η}^{θ}}{z_{η}} q^{l(η)}p_{η} = ∑_{η} \frac{χ_{η}^{θ}}{z_{η}} q^{l(η)} ∑_{ν} χ_{η}^{ν}s_{ν}.

Therefore the leading coefficient of ⟨s_{θ}[x]_{q}, s_{ν}⟩ is \frac{χ_{(1^{n})}^{θ} χ_{(1^{n})}^{ν}}{n!} (where n =^{def} |θ|) and the last statement follows. □

We should mention that a (different) formula for ⟨s_{λ}[x]_{q}, s_{ν}⟩ can be deduced from Theorem 6.1 of [12].

As observed in the previous section, elementary and complete symmetric functions are also covered by Theorem 5.1. However, once again, there is a more explicit expansion in these special cases.

Proposition 5.2 Let λ ∈ P. Then

e_{λ}[x]_{q} = ∑_{μ} K_{μ′,λ}(q) s_{μ},

and

h_{λ}[x]_{q} = ∑_{μ} K_{μ,λ}(q) s_{μ},

where K_{μ,λ}(q) has the same meaning as in (21).

Proof. Using a well known property of the involution ω and of the scalar product ⟨, ⟩ on Λ_{Q} (see, e.g., [14, Chap.I, §4, (4.10)]) we have that

⟨e_{λ}[x]_{q}, s_{μ}⟩ = ⟨ω(e_{λ}[x]_{q}), ω(s_{μ})⟩ = ⟨h_{λ}[x]_{q}, s_{μ′}⟩,

by Proposition 3.1. But it follows immediately from Proposition 3.2 and (21) that

⟨h_{λ}[x]_{q}, s_{μ}⟩ = ⟨h_{λ}, s_{μ}[x]_{q}⟩ = K_{μ,λ}(q),

and the result follows. □

We now turn to the expansion of m_{λ}[x]_{q} in terms of Schur symmetric functions. Recall (see, e.g., [14, Chap. I, §1, p. 5]) that a border strip is a connected skew diagram that contains no 2 × 2 squares, and that its height is one less than the number of rows that it occupies. Given μ ∈ P a special border strip tabloid of shape μ is a partition S of the diagram of μ into border strips, so that each border strip intersects the first column. The weight of S is the type of S (as a set partition), and the height of S is the sum of the heights of its border strips.

Theorem 5.3 Let λ ∈ P. Then

m_{λ}[x]_{q} = ∑_{μ} (∑_{i=1}^{l(λ)} (∑_{S}(−1)^{ht(S)}\overline{d}_{w(S),λ}(i)) (\begin{matrix}q \\ i \end{matrix})) s_{μ}  (26)

where S runs over all the special border strip tabloids of shape μ, w(S) denotes the weight of S, and ht(S) denotes the height of S.

Proof. Note first that, by Proposition 3.2

⟨m_{λ}[x]_{q}, s_{μ}⟩ = ⟨m_{λ}, s_{μ}[x]_{q}⟩.  (27)

On the other hand, by a well known result (see, e.g., [14, Chap. I, §6, Ex. 4(d)]), we have that

s_{μ} = ∑_{S}(−1)^{ht(S)}h_{w(S)}

where S runs over all the special border strip tabloids of shape μ. Therefore, we obtain from Proposition 3.2 and Theorem 4.1 that

s_{μ}[x]_{q} = ∑_{S}(−1)^{ht(S)} h_{w(S)}[x]_{q}

= ∑_{S}(−1)^{ht(S)} ∑_{ν}⟨h_{w(S)}[x]_{q}, m_{ν}⟩h_{ν}
= ∑_{S}(−1)^{ht(S)} ∑_{ν}⟨h_{w(S)}, m_{ν}[x]_{q}⟩h_{ν}
= ∑_{S}(−1)^{ht(S)} (∑_{ν} \overline{D}_{w(S),ν}(q) h_{ν})

where S runs over all the special border strip tabloids of shape μ, and (26) follows from (27) and (17). □

The above formula for m_{λ}[x]_{q} is not very satisfactory since it contains alternating sums. However, these may be unavoidable since the coefficients in the expansion of m_{λ}[x]_{q} in terms of Schur functions don’t possess, in general, the nice nonnegativity properties of Theorem 5.1 and Proposition 5.2. For example,

⟨m_{(3,1,1)}[x]_{q}, s_{(2,1,1,1)}⟩ = 3 (\begin{matrix}q \\ 3 \end{matrix}) + 2 (\begin{matrix}q \\ 2 \end{matrix}) − (\begin{matrix}q \\ 1 \end{matrix}) .

6 e-expansions and h-expansions

In this section we study the expansions of m_{λ}[x]_{q}, s_{λ}[x]_{q}, e_{λ}[x]_{q}, and h_{λ}[x]_{q} in terms of elementary and complete symmetric functions.

First note that we have already computed the expansions of s_{λ}[x]_{q} and h_{λ}[x]_{q} in terms of complete symmetric functions in Theorems 4.1 and 5.3 since it follows immediately from Proposition 3.2 that

⟨h_{λ}[x]_{q}, m_{μ}⟩ = ⟨h_{λ}, m_{μ}[x]_{q}⟩  (28)

and

⟨s_{λ}[x]_{q}, m_{μ}⟩ = ⟨s_{λ}, m_{μ}[x]_{q}⟩.

We now consider the expansion of e_{λ}[x]_{q} in terms of complete symmetric functions. Recall (see §4) that given λ, μ ∈ P and n ∈ P we denote by D_{λ,μ}(n) the number of n-brick tabloids of shape λ and type μ.

Theorem 6.1 Let λ ∈ P. Then

e_{λ}[x]_{q} = ∑_{μ} ε_{μ} (∑_{i=1}^{l(μ)} d_{λ,μ}(i) (\begin{matrix}q \\ i \end{matrix})) h_{μ},

where d_{λ,μ}(i) equals the number of i-brick tabloids T of shape λ and type μ such that every integer in [i] appears in T. In particular, ⟨e_{λ}[x]_{q}, m_{μ}⟩ = ε_{μ}D_{λ,μ}(q), ⟨e_{λ}[x]_{q}, m_{μ}⟩ = 0 if μ ≰_{R} λ, and deg(⟨e_{λ}[x]_{q}, m_{μ}⟩) = l(μ) if μ ≤_{R} λ.

Proof. Let n ∈ P. We will show, by induction on l(λ), that

D_{λ,μ}(n) = ε_{μ}⟨e_{λ}[x]_{n}, m_{μ}⟩.  (29)

If λ = (m) then we clearly have that

D_{(m),μ}(n) = (\begin{matrix}l(μ) \\ m_{1}(μ),m_{2}(μ),... \end{matrix}) ((\begin{matrix}n \\ l(μ) \end{matrix})) .

On the other hand, applying ω to both sides of (16) and using Proposition 3.1 yields that

e_{m}[x]_{n} = (−1)^{m} ∑_{μ⊢m} \frac{(−n)_{l(μ)}}{∏_{i≥1}m_{i}(μ)!}h_{μ}

so (29) holds in this case.

Assume now that λ = (λ_{1}, …, λ_{r}) with r ≥ 2. Then we have from our induction hypothesis that

e_{λ}[x]_{n} = e\overline{λ}[x]_{n}e_{λ_{r}}[x]_{n}
= ∑_{μ} ε_{μ}D_{\overline{λ},μ}(n) h_{μ} ∑_{ν} ε_{ν}D_{(λ_{r}),ν}(n)h_{ν}
= ∑_{ρ} ε_{ρ} (  ∑_{\{(μ,ν): μ⊢|\overline{λ}|, ν⊢λ_{r}, μ∪ν=ρ\}} D_{\overline{λ},μ}(n) D_{(λ_{r}),ν}(n)) h_{ρ},

where \overline{λ} =^{def} (λ_{1}, …, λ_{r−1}), and (29) follows. The other statements now follow as in the proof of Theorem 4.1. □

We note the following reciprocity result which follows from Theorems 4.1 and 6.1.

Corollary 6.2 Let λ, μ ∈ P. Then

D_{λ,μ}(−q) = (−1)^{l(μ)}\overline{D}_{λ,μ}(q),

in Z[q].

Proof. From Proposition 3.1 we have that h_{λ}[x]_{q} = e_{λ}[−x]_{−q} and the result follows from (28) and Theorems 4.1 and 6.1. □

We now examine the problem of expanding m_{λ}[x]_{q} in terms of complete symmetric functions. Given n ∈ P and λ = (λ_{1}, λ_{2}, …) ∈ P_{n} let D_{λ} be the digraph consisting of the disjoint union of directed paths of size λ_{1}, λ_{2}, . . .. Following [3] and [25] we 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., [8, p. 69]) isomorphic to D_{λ}. So, for example, I_{(3,2)}((3, 1, 4), (5, 2)) = 6.

Theorem 6.3 Let n ∈ P and λ ∈ P_{n}. Then

m_{λ}[x]_{q} = ε_{λ} ∑_{μ} ε_{μ} (\frac{1}{n!} ∑_{w∈S_{n}} I_{λ}(w)I_{μ}(w)q^{c(w)}) h_{μ}.  (30)

In particular, ε_{λ}ε_{μ}⟨m_{λ}[x]_{q}, m_{μ}⟩n! ∈ N[q^{i}], and deg(⟨m_{λ}[x]_{q}, m_{μ}⟩) ≤ min(l(λ), l(μ)).

Proof. It follows from [26, Prop. 1.1] (see also [25, §3], or [14, Chap. I, §6, Ex. 8]) that

⟨p_{μ}, m_{λ}⟩ = ε_{μ}ε_{λ}I_{λ}^{μ}  (31)

where I_{λ}^{μ} is the common value of I_{λ} on permutations of cycle-type μ. Therefore we deduce from (31) and (1) that

m_{λ}[x]_{q} = ε_{λ} ∑_{ν} \frac{ε_{ν}}{z_{ν}} I_{λ}^{ν}p_{ν}[x]_{q} = ε_{λ} ∑_{ν} \frac{ε_{ν}}{z_{ν}} I_{λ}^{ν}q^{l(ν)} ∑_{μ} ε_{ν}ε_{μ}I_{μ}^{ν}h_{μ}

and (30) follows. Now notice that I_{λ}(w) = 0 if c(w) > l(λ), and this proves the last statement. □

Note that, although ε_{λ}ε_{μ}⟨m_{λ}, m_{μ}⟩ ∈ N (see, e.g., [13]) it is not true, in general, that ε_{λ}ε_{μ}⟨m_{λ}[x]_{q}, m_{μ}⟩ ∈ N[q^{i}]. For example, −⟨m_{(3,3,2)}[x]_{q}, e_{8}⟩ = \frac{1}{2}q^{3} + \frac{3}{2}q^{2} + q. Also, notice that the degree of ⟨m_{λ}[x]_{q}, m_{μ}⟩ does not equal, in general, min(l(λ), l(μ)). For example, ⟨m_{(3,1)}[x]_{q}, m_{(2,2)}⟩ = 2q.

We conclude by examining the expansions of m_{λ}[x]_{q}, s_{λ}[x]_{q}, h_{λ}[x]_{q}, and e_{λ}[x]_{q} in terms of elementary symmetric functions. Note that we have already computed these expansions for s_{λ}[x]_{q}, e_{λ}[x]_{q}, and h_{λ}[x]_{q} since, by Proposition 3.1, we have that

⟨a[x]_{q}, f_{μ}⟩ = ⟨ω(a[x]_{q}), ω(f_{μ})⟩ = ⟨ω(a)[x]_{q}, m_{μ}⟩

for all a ∈ Λ_{Q} and μ ∈ P. The following result is an immediate consequence of Proposition 3.1 and Theorem 6.3.

Corollary 6.4 Let n ∈ P and λ ∈ P_{n}. Then

m_{λ}[x]_{q} = ε_{λ} ∑_{μ} ε_{μ} (\frac{(−1)^{n}}{n!} ∑_{w∈S_{n}} I_{λ}(w)I_{μ}(w)(−q)^{c(w)}) e_{μ}.□

As for Theorem 5.3, this result is not very satisfactory since it contains an alternating sum. However, once again, this may be unavoidable since the coefficients in the expansion of m_{λ}[x]_{q} in terms of e_{μ}’s don’t possess, in general, the nonnegativity properties of Theorems 6.1 and 6.3. For example,

⟨m_{(3,2,2,1)}[x]_{q}, f_{(3,2,2,1)}⟩ = −12 (\begin{matrix}q \\ 2 \end{matrix}) − 126 (\begin{matrix}q \\ 3 \end{matrix}) + 144 (\begin{matrix}q \\ 4 \end{matrix}) .

7 The ξ-homomorphism

In [3] a ring homomorphism ξ : Λ_{Q}[[t]] → Q[x][[t]] is defined, and it is shown that the images under ξ of the classical bases of Λ_{Q} possess interesting enumerative properties. In this section we show that many of the results in [3] have natural q-analogues which are obtained by considering e_{n}[x]_{q}, h_{n}[x]_{q}, m_{λ}[x]_{q}, s_{λ}[x]_{q}, and p_{λ}[x]_{q}. We should mention that other (different) q-analogues of some of the results of [3] have been obtained by Beck and Remmel in [1].

We first recall the definition of the homomorphism ξ (see [3, §4]). One starts by defining a ring homomorphism ξ : Λ_{Q} → Q[x] by letting

ξ(e_{n}) =^{def} \frac{(1 − x)^{n−1}}{n!}  (32)

for n ∈ P, and ξ(e_{0}) =^{def} 1. Since the e_{i}’s are algebraically independent and generate Λ_{Q} over Q this defines ξ uniquely. One then extends ξ to Λ_{Q}[[t]] by letting

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

where a_{n} ∈ Λ_{Q} for n ∈ N. It is easy to check that this is a ring homomorphism from Λ_{Q}[[t]] to Q[x][[t]].

We need to extend this definition to Λ ⊗ Q(q). We do this by letting ξ act on Q(q) as it does on scalars, so that ξ(f(q)a) =^{def} f(q)ξ(a) for all f(q) ∈ Q(q) and a ∈ Λ_{Q}. We then extend ξ to (Λ ⊗ Q(q))[[t]] in the same way as before.

We begin by obtaining a q-analogue of Theorems 4.1 and 4.2 as well as of Propositions 4.5 and 4.22 of [3]. Given n ∈ P and a partition λ of n we denote by S_{n}(λ) the conjugacy class of all the elements of S_{n} of cycle-type λ.

Theorem 7.1 Let n ∈ P and λ ∈ P_{n}. Then:

i) ξ(e_{n}[x]_{q}) = \frac{(−1)^{n}}{n!} ∑_{π∈S_{n}} x^{e(π)} (−q)^{c(π)};

ii) ξ(h_{n}[x]_{q}) = \frac{1}{n!} ∑_{π∈S_{n}} x^{e(π)} q^{c(π)};

iii) ξ(p_{λ}[x]_{q}) = \frac{z_{λ}}{n!} ∑_{π∈S_{n}(λ)} x^{e(π)} q^{c(π)};

iv) ξ(s_{λ}[x]_{q}) = \frac{1}{n!} ∑_{π∈S_{n}} χ^{λ}(π)x^{e(π)}q^{c(π)};

v) ξ(m_{λ}[x]_{q}) = \frac{ε_{λ}}{n!} ∑_{π∈S_{n}} sgn(π)I_{λ}(π)x^{e(π)}q^{c(π)}.

Proof. From (1) we have that

ξ(p_{λ}[x]_{q}) = ξ(q^{l(λ)}p_{λ}) = q^{l(λ)} ξ(p_{λ}) = q^{l(λ)} \frac{z_{λ}}{n!} ∑_{π∈S_{n}(λ)} x^{e(π)} = \frac{z_{λ}}{n!} ∑_{π∈S_{n}(λ)} x^{e(π)} q^{c(π)},

where we have used Theorem 4.2 of [3], and this proves iii). Now we obtain from iii) and (25) that

ξ(s_{μ}[x]_{q}) = ξ (∑_{λ} \frac{χ_{λ}^{μ}}{z_{λ}} p_{λ}[x]_{q})

= ∑_{λ} \frac{χ_{λ}^{μ}}{z_{λ}} ξ(p_{λ}[x]_{q})
= ∑_{λ} \frac{χ_{λ}^{μ}}{n!} ∑_{π∈S_{n}(λ)} x^{e(π)} q^{c(π)}
= \frac{1}{n!} ∑_{λ} ∑_{π∈S_{n}(λ)} χ^{μ}(π)x^{e(π)}q^{c(π)},

and iv) follows. Now i) and ii) are special cases of iv) since χ^{(n)}(π) = 1 and χ^{(1^{n})}(π) = (−1)^{n−c(π)} for all π ∈ S_{n}. Finally, we have from (31) and (1) that

ξ(m_{λ}[x]_{q}) = ξ (ε_{λ} ∑_{ν} \frac{ε_{ν}}{z_{ν}} I_{λ}^{ν}p_{ν}[x]_{q}) = ε_{λ} ∑_{ν} \frac{ε_{ν}}{n!} I_{λ}^{ν} ∑_{π∈S_{n}(ν)} x^{e(π)}q^{c(π)}

and v) also follows. □

Note that while ξ(s_{λ}) can be expressed as the immanant corresponding to λ of a simple matrix (see [3, Corollary 4.6]) there does not seem to be a similar expression for ξ(s_{λ}[x]_{q}).

Theorem 7.1 suggests the following definition. For n ∈ P let

A_{n}(x, q) =^{def} ∑_{π∈S_{n}} x^{e(π)+1} q^{c(π)}.  (33)

So, for example, A_{3}(x, q) = xq^{3} + x^{2}(3q^{2} + q) + x^{3}q. It is clear that A_{n}(x, 1) = A_{n}(x) (the n-th Eulerian polynomial). Although a large number of q-analogues of the Eulerian polynomials have been studied in the literature (see, e.g., [10], [15], [4], [6], [7]) no one seems to have considered this particular one.

One of the main results of [3] is that the polynomials ξ(e_{n}), ξ(h_{n}), and ξ(p_{λ}) have only real zeros (see [3, Theorem 3.2]). We now show that this result also has a q-analogue in the present context. We begin by showing that some of the crucial properties of the Eulerian polynomials have nice q-analogues for the polynomials A_{n}(x, q).

Proposition 7.2 The polynomials A_{n}(x, q) defined by (33) satisfy the recursion relation

A_{n}(x, q) = (nx + q − 1)A_{n−1}(x, q) + x(1 − x)\frac{∂}{∂x}(A_{n−1}(x, q)),

for all n ∈ P, with the initial condition A_{0}(x, q) =^{def} x.

Proof. Fix n ∈ P, n ≥ 2. For σ ∈ S_{n−1} and i ∈ [n] let σ_{(i)} ∈ S_{n} be the permutation obtained by inserting n, in the disjoint cycle form of σ, just before σ(i) if i ∈ [n − 1] (respectively, as a new cycle, if i = n). More precisely,

σ_{(i)}(j) = \{ \begin{matrix}n, & if j = i, \\ σ(i), & if j = n, \\ σ(j), & otherwise, \end{matrix}

(where σ(n) =^{def} n) for j ∈ [n]. It is then clear that

e(σ_{(i)}) = \{ \begin{matrix}e(σ), & if σ(i) > i, \\ e(σ) + 1, & if σ(i) ≤ i, \end{matrix}

for i ∈ [n − 1], e(σ_{(n)}) = e(σ), and

c(σ_{(i)}) = \{ \begin{matrix}c(σ), & if i < n, \\ c(σ) + 1, & if i = n. \end{matrix}

Therefore we conclude from (33) that

A_{n}(x; q) = ∑_{π∈S_{n}} x^{e(π)+1} q^{c(π)}
= ∑_{i=1}^{n} ∑_{σ∈S_{n−1}} x^{e(σ_{(i)})+1} q^{c(σ_{(i)})}
= ∑_{σ∈S_{n−1}} x^{e(σ)+1} q^{c(σ)+1} + ∑_{i=1}^{n−1} ∑_{σ∈S_{n−1}} x^{e(σ_{(i)})+1} q^{c(σ)}
= qA_{n−1}(x, q) + ∑_{σ∈S_{n−1}}(e(σ)x^{e(σ)+1} + (n − 1 − e(σ))x^{e(σ)+2})q^{c(σ)}
= qA_{n−1}(x, q) + (nx − 1)A_{n−1}(x, q) + ∑_{σ∈S_{n−1}}(1 − x)(e(σ) + 1)x^{e(σ)+1}q^{c(σ)},

and the result follows. □ Proposition 7.3 We have that

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

in Q(x,q)[[t]] . Proof. It follows from (9) that

∑_{n≥0} h_{n}[x]_{q}t^{n} = (∑_{n≥0} h_{n}t^{n})^{q}  (34)

in (Λ ⊗ Q(q))[[t]]. Applying now ξ to both sides of (34) we therefore obtain that

∑_{n≥0} ξ(h_{n}[x]_{q})t^{n} = [ξ (∑_{n≥0} h_{n}t^{n})]^{q}
= (∑_{n≥0} ξ(h_{n})t^{n})^{q}
= (1 + ∑_{n≥1} \frac{A_{n}(x)}{x n!} t^{n})^{q}
= (\frac{e^{t(x−1)} − x}{1 − x})^{−q}  (35)

where we have used Theorem 4.1 of [3] and a well-known generating function for Eulerian polynomials (see, e.g., [8, eq. [5j], p.244]). The result now follows from (35), (33), and part ii) of Theorem 7.1. □

The preceding proposition has the following curious enumerative consequence, the first part of which also follows from (32) and part i) of Theorem 7.1.

Corollary 7.4 Let n ∈ P, n ≥ 2. Then

∑_{π∈S_{n}} x^{e(π)} (−1)^{c(π)} = −(x − 1)^{n−1},

and

∑_{π∈S_{n}} x^{e(π)}(−2)^{c(π)} = 2(2^{n−1} − x)(x − 1)^{n−2}.□

It would be interesting to find a direct combinatorial proof of the preceding corollary. We now come to the main result of this section.

Theorem 7.5 Let q ∈ Q, q > 0. Then the polynomials A_{n}(x, q) have only real nonpositive simple zeros. In particular, A_{n}(x, q) is log-concave and unimodal.

Proof. We proceed by induction on n ∈ P, the result being clearly true for n = 1. By our induction hypothesis A_{n−1}(x, q) has only simple real nonpositive zeros, and it is clear from the definition (33) that A_{n−1}(0, q) = 0. So let

ξ_{n−1} < ξ_{n−2} < … < ξ_{2} < ξ_{1} = 0

be the zeros of A_{n−1}(x, q). It then follows from Rolle’s theorem that \frac{d}{dx}(A_{n−1}(x, q)) has only simple real zeros and that

ξ_{n−1} < η_{n−2} < ξ_{n−2} < … < ξ_{2} < η_{1} < ξ_{1} = 0

where η_{n−2}, …, η_{1} denote the zeros of \frac{d}{dx}(A_{n−1}(x, q)). Furthermore, since A_{n−1}(x, q) has positive leading term, it is clear that

(−1)^{j}A_{n−1}(η_{j}, q) > 0  (36)

for j ∈ [n − 2], and

(−1)^{j+1} \frac{d}{dx}(A_{n−1}(x, q))_{|x=ξ_{j}} > 0  (37)

for j ∈ [n − 1].

Now let α =^{def} \frac{1−q}{n}. If α ≥ η_{1} then (since α < 1 by our hypothesis) (nx+q−1)A_{n−1}(x, q) alternates left of x(1 − x)\frac{d}{dx}(A_{n−1}(x, q)) and the result follows from standard techniques (see, e.g., [27, §3]). We may therefore assume that α < η_{1}. Then let 2 ≤ i ≤ n − 1 be such that

η_{i} < α ≤ η_{i−1},

(where η_{n−1} =^{def} −∞). It then follows from Proposition 7.2, (36) and (37) that

(−1)^{i}A_{n}(α, q) ≥ 0,  (38)

(−1)^{j}A_{n}(η_{j}, q) \{ \begin{matrix}> 0 & if & j ∈ [i − 2] \\ ≥ 0 & if & j = i − 1 \\ < 0 & if & i ≤ j ≤ n − 1, \end{matrix}  (39)

and

(−1)^{j}A_{n}(ξ_{j}, q) > 0  (40)

for j = 2, …, n − 1 (where A_{n}(−∞, q) =^{def} lim_{x→−∞} A_{n}(x, q)). Therefore

A_{n}(η_{j}, q)A_{n}(ξ_{j+1}; q) < 0

for j ∈ [i − 2], and

A_{n}(ξ_{j}, q)A_{n}(η_{j}, q) < 0

for j = i + 1, …, n − 1. This implies that A_{n}(x, q) has a zero in (ξ_{j+1}, η_{j}) for j ∈ [i − 2], and a zero in (η_{j}, ξ_{j}) for j = i + 1, …, n − 1.

Furthermore, if a =^{def} min{ξ_{i}, α} and b =^{def} max{ξ_{i}, α}, then we have from (38), (39), and (40) that

A_{n}(η_{i}, q)A_{n}(a, q) ≤ 0,

and

A_{n}(b, q) A_{n}(η_{i−1}, q) ≤ 0.

Therefore A_{n}(x, q) has a zero in [η_{i}, a] and a zero in [b, η_{i−1}], and these zeros must be distinct since A_{n}(ξ_{i}, q) ≠ 0 by (40). Since A_{n}(0, q) = 0 this shows that A_{n}(x, q) has n real nonpositive simple zeros, as claimed. □

Note that the above result fails if q < 0. For example,

A_{3} (x, −\frac{1}{2}) = \frac{1}{8}(−4x^{2} + 2x − 1)x

which does not have only real zeros.

We can now obtain the following q-analogue of one of the main results of [3].

Corollary 7.6 Let q ∈ Q, q > 0. Then ξ(h_{n}[x]_{q}), and ξ(p_{λ}[x]_{q}) have only real zeros.

Proof. This follows immediately from Theorems 7.1 and 7.5, and from Theorem 3.2 of [3] since ∑_{π∈S_{n}(λ)} x^{e(π)}q^{c(π)} = q^{l(λ)} ∑_{π∈S_{n}(λ)} x^{e(π)}. □

8 Conjectures and Open Problems

In this section we collect some conjectures and open problems arising from the present work, together with the evidence that we have about them.

As we have seen in sections 4, 5, and 6, most of the expansions of the symmetric functions e_{λ}[x]_{q}, m_{λ}[x]_{q}, s_{λ}[x]_{q}, and h_{λ}[x]_{q} in terms of the usual bases of Λ ⊗ Q(q) can be computed from two basic polynomials which have a nice combinatorial interpretation, namely K_{λ\μ,ν}(q) and D_{λ,μ}(q). It is therefore natural to investigate these polynomials further.

We begin with the polynomials K_{λ\μ,ν}(q). Recall that we may write

K_{λ\μ,ν}(q) = ∑_{i=1}^{|ν|} k_{λ\μ,ν}(i) \binom{q}{i}

where the integers k_{λ\μ,ν}(i) have the combinatorial interpretation described in the statement of Theorem 4.3. In particular, k_{λ,μ}(1) is the usual Kostka number K_{λ,μ}. Conjecture 8.1 Let λ, μ, ν ∈ P. Then the sequence (k_{λ\μ,ν}(1), …, k_{λ\μ,ν}(|ν|)) is logconcave and unimodal. The above conjecture has been verified for |λ| ≤ 11. Note that it is not true, in general, that the polynomials ∑_{i=1}^{|ν|} k_{λ\μ,ν}(i)q^{i} have only real zeros. For example,

∑_{i=1}^{8} k_{(4,4),(4,4)}(i)q^{i} = q + 33q^{2} + 384q^{3} + 1912q^{4} + 4690q^{5} + 6000q^{6} + 3850q^{7} + 980q^{8},

which has only 6 real zeros. Conjecture 8.1 is true (but non-trivial) if any one of λ \ μ, λ′ \ μ′ or ν′ has only one row, or if μ = ∅ and ν has only one row. In fact, in these cases it follows easily from Theorem 4.3 and Corollary 4.5 that

K_{(n),ν}(q) = ∏_{i=1}^{l(ν)} ((\begin{matrix}q \\ ν_{i} \end{matrix} ))  (41)
K_{(1^{n}),ν}(q) = ∏_{i=1}^{l(ν)} (\begin{matrix}q \\ ν_{i} \end{matrix} )  (42)
K_{λ,(n)}(q) = ∏_{(i,j)∈λ} (\frac{q + c(i, j)}{h(i, j)})  (43)
K_{λ\μ,(1^{n})}(q) = f^{λ\μ}q^{n}  (44)

where n =^{def} |ν|, and the conjecture then follows from Theorems 4.4.1 and 2.6.1 of [2].

Note that in all four cases (41), (42), (43), and (44), the polynomial K_{λ,μ}(q) is (apart possibly from a constant factor) the order polynomial of some labeled poset. This, however, is false in general. For example,

K_{(2,2),(2,2)}(q) = (\begin{matrix}q \\ 1 \end{matrix}) + 8 (\begin{matrix}q \\ 2 \end{matrix}) + 18 (\begin{matrix}q \\ 3 \end{matrix}) + 12 (\begin{matrix}q \\ 4 \end{matrix})  (45)

is not a multiple of the order polynomial of any labeled poset. In fact, it is known (see, e.g., [18, Proposition 13.1]) that if ∑_{i=1}^{|P |} e_{i}(P, ω) (\begin{matrix}q \\ i \end{matrix}) is the order polynomial of some labeled poset (P, ω) then e_{0}(P, ω) ∈ {0, 1} and e_{|P |}(P, ω) equals the number of linear extensions of P. Hence if (45) were a multiple of the order polynomial of some labeled poset (P, ω) then P would have to have size 4 and 12 linear extensions. There is only one such P, namely the one shown in Figure 3, and one can check that no labeling ω of this poset gives an order polynomial equal to K_{(2,2),(2,2)}(q). Thus Conjecture 8.1 is not a consequence of the so-called “Poset Conjecture” (see, e.g., [21, Conjecture 1], [2, Chapters 1 and 5], and [5, Conjecture 3.9] for further information on this conjecture).

[figure]

Figure 3: The only poset of size 4 with 12 linear extensions.

In the case that λ \ μ is either a vertical or a horizontal strip we feel that the following strengthening of Conjecture 8.1 holds.

Conjecture 8.2 Let λ, μ, ν ∈ P, and assume that λ\μ is either a vertical or a horizontal strip.Then the polynomial ∑_{i=1}^{|ν|} k_{λ\μ,ν}(i)q^{i} has only real (nonpositive) zeros.

The above conjecture has been verified for |λ \ μ| ≤ 12.

We now turn our attention to the polynomials D_{λ,μ}(q). Recall that by (17), Theorem 6.1, and Corollary 6.2, they can be expressed as

D_{λ,μ}(q) = ∑_{i=1}^{l(μ)} d_{λ,μ}(i) \binom{q}{i} = ∑_{i=1}^{l(μ)}(−1)^{l(μ)−i} \overline{d}_{λ,μ}(i) (\binom{q}{i})

where the integers d_{λ,μ}(i) (respectively, \overline{d}_{λ,μ}(i)) have the combinatorial interpretation described in the statement of Theorem 6.1 (respectively, Theorem 4.1).

Conjecture 8.3 Let λ, μ ∈ P. Then the sequences (d_{λ,μ}(1), …, d_{λ,μ}(l(μ))) and (\overline{d}_{λ,μ}(1), …, \overline{d}_{λ,μ}(l(μ))) are log-concave and unimodal.

Conjecture 8.3 has been verified for |λ| ≤ 12, and is true if d_{λ,μ}(1) = 1 (i.e., if there is exactly one brick tabloid of shape λ and type μ). In fact, in this case it is clear that

D_{λ,μ}(q) = ∏_{i=1}^{l(λ)} ((\begin{matrix}q \\ r_{i} \end{matrix} ))

and

\overline{D}_{λ,μ}(q) = ∏_{i=1}^{l(λ)} (\begin{matrix}q \\ r_{i} \end{matrix} )

where r_{i} is the number of bricks that tile the i-th row of λ, and the conjecture then follows as in the comments following Conjecture 8.1. In particular, Conjecture 8.3 holds if μ is a rectangle, or if λ = μ. Similarly, one can see that Conjecture 8.3 holds if λ has only one row. Note that it is not true, in general, that the polynomials ∑_{i=1}^{l(μ)} d_{λ,μ}(i)q^{i} and ∑_{i=1}^{l(μ)} \overline{d}_{λ,μ}(i)q^{i} have only real zeros. For example,

∑_{i=1}^{6} \overline{d}_{(9,3),(3^{3},1^{3})}(i)q^{i} = q^{3} + 12q^{4} + 80q^{5} + 80q^{6}

and hence

∑_{i=1}^{6} d_{(9,3),(3^{3},1^{3})}(i)q^{i} = 11q + 114q^{2} + 355q^{3} + 492q^{4} + 320q^{5} + 80q^{6}

which both have only 4 real zeros.

There is a consequence of Conjecture 8.3 that we can prove.

Proposition 8.4 Let λ, μ ∈ P. Then the sequences (d_{λ,μ}(1), …, d_{λ,μ}(l(μ))) and (\overline{d}_{λ,μ}(1), …, \overline{d}_{λ,μ}(l(μ))) have no internal zeros.

Proof. Let i ∈ [l(μ) − 1] be such that \overline{d}_{λ,μ}(i) > 0 and let T be a strict i-brick tabloid of shape λ and type μ such that every integer in [i] appears in T. Since i < l(μ) there exist j ∈ [i] and two bricks B_{1}, B_{2} that have both label j. Therefore, adding 1 to the label of B_{2} and all the bricks that have label ≥ j + 1 yields a strict (i + 1)-brick tabloid T′ of the same shape and type as T such that every integer in [i + 1] appears in T′. Hence \overline{d}_{λ,μ}(i + 1) > 0, and this proves the second statement. The first statement follows easily from the fact that, for any i ∈ [l(μ)], d_{λ,μ}(1) > 0 if and only if d_{λ,μ}(i) > 0. □

Regarding the transition matrices that cannot be directly computed from the polynomials K_{λ\μ,ν}(q) and D_{λ,μ}(q), computer evidence suggests that the following holds.

Conjecture 8.5 For λ, μ ∈ P let ⟨s_{λ}[x]_{q}, s_{μ}⟩ = ∑_{i=1}^{|λ|} S_{λ,μ}(i) (\begin{matrix}q \\ i \end{matrix}). Then the sequence {S_{λ,μ}(i)}_{i=1,...,|λ|} is log-concave and unimodal.

Conjecture 8.6 Let λ, μ ∈ P. Then ε_{μ}ε_{λ}⟨m_{λ}[x]_{q}, m_{μ}⟩ is log-concave.

The above conjectures have been verified for |λ| ≤ 12. Note that the polynomials ∑_{i=1}^{|λ|} S_{λ,μ}(i)q^{i} and ⟨m_{λ}[x]_{q}, m_{μ}⟩ do not always have only real zeros. For example,

⟨s_{(2,2)}[x]_{q}, s_{(2,2)}⟩ = (\begin{matrix}q \\ 1 \end{matrix}) + 4 (\begin{matrix}q \\ 2 \end{matrix}) + 6 (\begin{matrix}q \\ 3 \end{matrix}) + 4 (\begin{matrix}q \\ 4 \end{matrix}) ,

and

⟨m_{(3,1^{3})}[x]_{q}, m_{(3,1^{3})}⟩ = \frac{q^{4}}{2} + \frac{7}{2}q^{3} + 9q^{2} + 6q.

As noted after Theorem 5.1, a formula for ⟨s_{λ}[x]_{q}, s_{μ}⟩ (different from the one given in Theorem 5.1) can be obtained from Theorem 6.1 of [12]. However, this formula seems to be of little use in deciding Conjecture 8.5.

There is another conjecture that follows from Conjectures 8.1, 8.3, and 8.5.

Conjecture 8.7 Let λ, μ, ν ∈ P. Then the sequences {K_{λ\μ,ν}(n)}_{n=1,2,...}, {D_{λ,μ}(n)}_{n=1,2,...}, \{\overline{D}_{λ,μ}(n)\}_{n=1,2,...}, and \{⟨s_{λ}[x]_{n}, s_{μ}⟩\}_{n=1,2,...} are all log-concave.

That Conjecture 8.7 is a consequence of Conjectures 8.1, 8.3 and 8.5 follows from Theorem 2.5.7 of [2].

Regarding the polynomials A_{n}(x; q) studied in §7, we feel that the following holds.

Conjecture 8.8 Let n, m ∈ P. Then A_{n}(x; −m) has only real zeros.

The above conjecture has been verified for n, m ≤ 15, and is true for m ≤ 3.

Finally, we believe that other results in [3] should have q-analogues obtained by considering s_{λ}[x]_{q} instead of s_{λ}. In particular, we feel that this is true for Corollaries 4.16 and 4.18 of [3].

Acknowledgements. I would like to thank Jeff Remmel and Richard Stanley for useful comments and references. Many of the computations in this paper have been carried out using a Maple package for handling symmetric functions developed by John Stembridge.

References

[1] D. Beck and J. Remmel, The combinatorics of symmetric functions and permutation enumeration of S_{n}, J. Combin. Theory Ser.A, 72 (1995), 1-49.

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

[3] F. Brenti, Permutation enumeration, symmetric functions, and unimodality, Pacific J. Math., 157 (1993), 1-28.

[4] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, Europ. J. Combinatorics, 15 (1994), 417-441.

[5] F. Brenti, Log-concave and unimodal sequences in Algebra, Combinatorics and Geometry: an update, Contemporary Math., 178 (1994), 71-89.

[6] R. J. Clarke and D. Foata, Eulerian Calculus, II: an extension of Han’s fundamental transformation, Europ. J. Combinatorics, 16 (1995), 221-252.

[7] R. J. Clarke and D. Foata, Eulerian Calculus, III: the ubiquitous Cauchy formula, Europ. J. Combinatorics, 16 (1995), 329-355.

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

[9] R. Ehrenborg, On posets and Hopf algebras, Advances in Math., 119 (1996), 1-25.

[10] A. Garsia, On the “maj” and “inv” q-analogues of Eulerian polynomials, Linear and Multilinear Algebra, 8 (1979), 21-34.

[11] M. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Alg. Combinatorics, 3 (1994), 17-76.

[12] A. N. Kirillov, Decomposition of symmetric and exterior powers of the adjoint representation of gl_{N}, Int. J. Modern Physics A, 7 (1992), Suppl. 1B, 545-579.

[13] A. Kulikauskas and J. B. Remmel, Primitive bi-brick permutations and symmetric functions, preprint, 1994.

[14] I. G. Macdonald, Symmetric Functions and Hall Polynomials, ( 2nd edition), Oxford University Press, Oxford, 1995.

[15] V. Reiner, Signed permutation statistics and cycle type, Europ. J. Combinatorics, 14 (1993), 569-579.

[16] V. Reiner, Non-crossing partitions for classical reflection groups, preprint dated March, 1996.

[17] R. Simion and R. P. Stanley, Flag-symmetry of the poset of shuffles and a local action of the symmetric group, preprint dated September, 1997.

[18] R. P. Stanley, Ordered Structures and Partitions, Memoirs Amer. Math. Soc., no. 119 (1972).

[19] R. P. Stanley, Combinatorial reciprocity theorems, Adv. in Math., 14 (1974), 194-253.

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

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

[22] R. P. Stanley, Some combinatorial properties of Jack symmetric functions, Adv. in Math., 77 (1989), 76-115.

[23] R. P. Stanley, Flag-symmetric and locally rank-symmetric partially ordered sets, Electronic J. Combinatorics, 3, R6 (1996), 22 pp.

[24] R. P. Stanley, Parking functions and noncrossing partitions, Electronic J. Combinatorics, 4, R20 (1997), 14 pp.

[25] R. P. Stanley and J. Stembridge, On immanants of Jacobi-Trudi matrices and permutations with restricted positions, J. Combin. Theory Ser.A, 62 (1993), 261-279.

[26] J. Stembridge, Some conjectures for immanants, Canadian J. Math., 44 (1992), 1079-1099.

[27] D. Wagner, Total positivity of Hadamard products, J. Math. Analysis and Applications, 163 (1992), 459-483.