Séminaire Lotharingien de Combinatoire 54A (2007), Article B54As

THE COMBINATORICS OF MACDONALD’S D_{n}^{1} OPERATOR

Jeffrey Remmel^{1}

Department of Mathematics University of California, San Diego La Jolla, CA 92093-0112. USA

                                jremmel@ucsd.edu

Dedicated to Adriano Garsia who taught me the beauty of combinatorics and symmetric functions.

Abstract. To prove the existence of the Macdonald polynomials {P_{λ}(x; q, t)}_{λ⊢n}, Macdonald [Séminaire Lotharingien Combin. 20 (1988), Article B20a; “Symmetric functions and Hall polynomials”, 2nd ed., Clarendon Press, New York, 1995] introduced an operator D_{n}^{1} and proved that for any Schur function s_{λ}(x_{1}, …, x_{n}), D_{n}^{1}(s_{λ}(x_{1}, …, x_{n})) = ∑_{μ} d_{λ,μ}(q, t)s_{μ}(x_{1}, …, x_{n}) where the sum runs over all partitions μ of n which are less than or equal to λ in the dominance order and the d_{λ,μ}(q, t) are polynomials in q and t with integer coefficients. We give an explicit combinatorial formula for the d_{λ,μ}(q, t)’s.

1. Introduction

In 1988, I.G. Macdonald [4] introduced a remarkable new basis for the space of symmetric functions. The elements of this basis are denoted P_{λ}(\overline{x}; q, t) where λ is a partition, \overline{x} = (x_{1}, …, x_{N}), and p, q are two free parameters. The P_{λ}(\overline{x}; q, t)’s, which are now called “Macdonald polynomials”, specialize to many of the well-known bases for the symmetric functions by suitable choices of the parameters q and t. In fact, we can obtain in this manner the Schur functions, the Hall-Littlewood symmetric functions, the Jack symmetric functions, the zonal symmetric functions, the zonal spherical functions, and the elementary and monomial symmetric functions.

We will use standard notation from the theory of symmetric functions. We let Λ_{n}(\overline{x}) = Λ_{n}(x_{1}, x_{2}, …, x_{N}) denote the space of homogeneous symmetric functions of degree n where N ≥ n. Then the dimension of Λ_{n}(\overline{x}) is the number of partitions of n and Λ_{n}(\overline{x}) has many well known bases including the monomial symmetric functions \{m_{λ}(\overline{x})\}_{λ}, the power symmetric functions \{p_{λ}(\overline{x})\}_{λ}, the elementary symmetric functions \{e_{λ}(\overline{x})\}_{λ}, and the homogeneous symmetric functions, \{h_{λ}(\overline{x})\}_{λ}, where in each case λ ranges over the set P tn(n) of partitions of n. Here h_{n}(\overline{x}) = ∑_{1≤i_{1}≤···≤i_{n}≤N} x_{i_{1}} ⋯ x_{i_{n}}, e_{n}(\overline{x}) = ∑_{1≤i_{1}<···<i_{n}≤N} x_{i_{1}} ⋯ x_{i_{n}}, and p_{n}(\overline{x}) = ∑_{1=1}^{N} x_{i}^{n}. Then for a partition λ = (λ_{1}, …, λ_{k}), m_{λ}(\overline{x}) is the sum over all monomials x_{1}^{a_{1}} ⋯ x_{N}^{a_{N}} so that the non-zero terms in a_{1}, …, a_{N} can be rearranged to λ, h_{λ}(\overline{x}) = ∏_{i=1}^{k} h_{λ_{i}}(\overline{x}), e_{λ}(\overline{x}) = ∏_{i=1}^{k} e_{λ_{i}}(\overline{x}), and p_{λ}(\overline{x}) = ∏_{i=1}^{k} p_{λ_{i}}(\overline{x}).

2000 Mathematics Subject Classification. 05E05 05E10.

1 Partially supported by NSF Grants DMS 0400507 and DMS 0502858.

Figure 1. A column strict tableau

Given two partitions λ, μ, we write λ ⊆ μ provided the Ferrers diagram of λ fits inside the Ferrers diagram of μ. If λ ⊆ μ, we let |μ/λ| = |μ| − |λ| and we associate μ/λ with the cells in the Ferrers diagram of μ that are not in the Ferrers diagram of λ. The resultant cells are known as the skew shape μ/λ.

A column strict tableau T of shape μ/λ is a filling of the skew shape μ/λ with positive integers such that the integers weakly increase when read from left to right and strictly increase when read from bottom to top. Let CS(μ/λ) be the set of all column strict tableaux of shape μ/λ. Given T ∈ CS(μ/λ), let w_{i}(T) be the number of occurrences of i in T and let w(T) = ∏_{i} x_{i}^{w_{i}(T)}. Figure 1 gives an example of a column strict tableau T of shape (1, 2, 3, 4, 4)/(1, 3) with w(T) = x_{1}^{3}x_{2}^{2}x_{3}^{3}x_{4}^{2}.

Then the skew Schur function s_{μ/λ} can be defined by

s_{μ/λ}(x_{1}, x_{2}, …) = ∑_{T ∈CS(μ/λ)} w(T).

When λ = ∅, this coincides with the definition of s_{μ}(x_{1}, x_{2}, …).

Macdonald [4, 5] introduced a new scalar product ⟨, ⟩_{q,t} on Λ_{n}(\overline{x}) by declaring that

⟨p_{λ}(\overline{x}), p_{μ}(\overline{x})⟩ = z_{λ}δ_{λ,μ} ∏_{i=1}^{ℓ(λ)} \frac{1 − q^{λ_{i}}}{1 − t^{λ_{i}}} .  (1)

Here we let ℓ(λ) denote the number of parts of λ so that λ = (λ_{1}, …, λ_{ℓ(λ)}). Macdonald then proved the existence of a unique family of polynomials \{P_{λ}(\overline{x}; q, t)\}_{λ⊢n} which is a basis of Λ(x_{1}, …, x_{n}) such that for all partitions λ and μ of n, there exists rational functions ξ_{λ,μ}(q, t) so that

P_{λ}(\overline{x}; q, t) = s_{λ} + ∑_{μ⊢n,μ<_{D}λ} s_{μ}(\overline{x})ξ_{λ,μ}(q, t)  (2)

and

⟨P_{λ}(\overline{x}; q, t), P_{μ}(\overline{x}; q, t)⟩_{q,t} = 0 if λ ≠ μ.  (3)

Here <_{D} is the dominance order. That is, given two partitions of n, λ = (λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n}) and μ = (μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{n}), we define λ ≥_{D} μ if and only if for i = 1, …, n, ∑_{j=1}^{i} λ_{j} ≥ ∑_{j=1}^{i} μ_{i}.

THE COMBINATORICS OF MACDONALD’S D_{n}^{1} OPERATOR 3

In general, conditions (2) and (3) overdetermine the family \{P_{λ}(\overline{x}; q, t)\}_{λ⊢n} so the proof of existence is non-trivial. To prove the existence of the family of polynomials \{P_{λ}(\overline{x}; q, t)\}_{λ⊢n}, Macdonald introduced a very useful operator D_{n}^{1} which is defined as follows. Let [n] = {1, …, n}. Then given a polynomial P (x_{1}, …, x_{n}), let

T_{q}^{(s)}P (x_{1}, …, x_{n}) = P (x_{1}, …, x_{s−1}, qx_{s}, x_{s+1}, …, x_{n})  (4)

and

D_{n}^{1}P (x_{1}, …, x_{n}) = ∑_{s=1}^{n} ∏_{i∈[n]−\{s\}} \frac{tx_{s} − x_{i}}{x_{s} − x_{i}} T_{q}^{(s)}P (x_{1}, …, x_{n})

= ∑_{s=1}^{n} \frac{T_{t}^{(s)}Δ(x_{1}, …, x_{n})}{Δ(x_{1}, …, x_{n})}T_{q}^{(s)}P (x_{1}, …, x_{n})  (5)

where Δ(x_{1}, …, x_{n}) = ∏_{1≤i<j≤n}(x_{i} − x_{j}) is the Vandermonde determinant. Macdonald proved the following facts about the operator D_{n}^{1}. Given any sequence of integers p = (p_{1}, …, p_{n}), let ω_{p}(q, t) = ∑_{i=1}^{n} t^{n−i}q^{p_{i}}. For any partition λ = (λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n}) we shall write λ(p) = λ if the decreasing rearrangement of p equals λ. Then Macdonald proved that for all partitions λ of n,

D_{n}^{1}(m_{λ}(x_{1}, …, x_{n})) = ω_{λ}(q, t)m_{λ}(x_{1}, …, x_{n}) + ∑_{μ<_{D}λ} m_{μ} ∑_{p=(p_{1},...,p_{n}),λ(p)=λ} ϵ_{μ}(p)ω_{p}(q, t) (6)

where ϵ_{μ}(p) = sgn(σ) if there is a permutation σ such that p_{σ_{i}} + n − i = μ_{i} + n − i for i = 1, …, n and ϵ_{μ}(p) = 0 if there is no such σ. It immediately follows that for all partitions λ of n

D_{n}^{1}(s_{λ}(x_{1}, …, x_{n})) = ω_{λ}(q, t)s_{λ}(x_{1}, …, x_{n}) + ∑_{μ<_{D}λ} d_{λ,μ}(q, t)s_{μ}(x_{1}, …, x_{n})  (7)

for some polynomials d_{λ,μ}(q, t). In fact, Macdonald proved that if

z_{λ}(x) = ∏_{μ∈P tn(n)−\{λ\}} \frac{x − ω_{μ}(q, t)}{ω_{λ}(q, t) − ω_{μ}(q, t)},  (8)

then

P_{λ}(x_{1}, …, x_{n}; q, t) = z_{λ}(D_{n}^{1})s_{λ}(x_{1}, …, x_{n}).  (9)

The main goal of this paper is to find a combinatorial interpretation for the polynomials d_{λ,μ}(q, t). Our combinatorial interpretation of d_{λ,μ}(q, t) will be defined as a product of weights of certain rim hooks associated to μ which depend on λ, see Theorem 15. Given a Ferrers diagram λ, a rim hook h of λ is a consecutive sequence of cells along the northeast boundary of λ such that any two consecutive cells of h share an edge and the removal of cells of h from λ results in a Ferrers diagram corresponding to another partition. A broken rim hook (BRH) of λ is a union of rim hooks of λ. See Figure 2.

Figure 2. A broken rim hook

This given, the first step in finding our combinatorial interpretation for the d_{λ,μ}(q, t) is to use a Λ-ring expression for D_{n}^{1} due to Garsia and Haiman [2] to prove that

D_{n}^{1}(s_{λ}(x_{1}, …, x_{n})) = \frac{s_{λ}(x_{1}, …, x_{n})}{1 − t}

+ \frac{t^{|λ|}}{t − 1}_{∑_{λ/μ is a BRH of λ} γ/μ is a BRH of γ}w_{r}(λ/μ)w_{b}(γ/μ)s_{γ}(x_{1}, …, x_{n}) (10)

where the sum runs over all μ and γ such that |λ/μ| = |γ/μ| and, for u ∈ {r, b},

w_{u}(λ/μ) = ∏_{s∈λ/μ} w_{u,λ/μ}(s)  (11)

where

w_{r,λ/μ}(s) = \begin{cases}\frac{q}{t} & if s has a square in λ/μ to its right, \\ \frac{−1}{t} & if s has a square in λ/μ below it, \\ \frac{(q−1)}{t} & otherwise \end{cases}  (12)

and

w_{b,λ/μ}(s) = \begin{cases}t & if s has a square in λ/μ to its right, \\ −1 & if s has a square in λ/μ below it, \\ (t − 1) & otherwise. \end{cases}  (13)

The next step in the evaluation of the right-hand side of (10) is to give combinatorial proofs of the following two facts:

(1) d_{λ,λ}(q, t) = ∑_{i=1}^{n} t^{n−i}q^{λ_{i}} and

(2) if λ ≠ γ and d_{λ,γ}(q, t) ≠ 0, then γ satisfies the following condition:

(*) γ arises from λ by first removing a broken rim hook R of λ from λ to get a partition μ and then adding a broken rim hook B of γ on the outside of μ to obtain obtain γ so that rows occupied by B lie strictly above the rows occupied by R and |B| = |R|.

Note that any γ that satisfies condition (*) is automatically dominated by λ. If γ satisfies condition (*), then our combinatorial interpretation for d_{λ,γ}(q, t) is best described by example. Suppose

λ = (1, 3, 4, 5^{2}, 6, 7, 8^{2}, 11^{2}, 13^{4}, 16^{3}, 17, 18)

and

γ = (1, 5^{4}, 8^{4}, 11^{3}, 12^{2}, 13, 15^{2}, 16, 17, 18),

see Figure 3. We shall think of the cells of the broken rim hook R as being colored red so we will put an r in the cells corresponding to R. We shall think of the cells of the broken rim hook B as being colored blue so that we will put a b in the cells corresponding to B. Thus in Figure 3, λ corresponds to all the cells except the blue cells and γ corresponds to all the cells except the red cells. As required by condition (*), |R| = |B| and all the blue cells lie strictly above any red cells. If we consider the right-hand side of (10), it is clear that the red and blue cells completely determine λ and γ, but there are many μ’s in the sum that could give rise to the same λ and γ. That is, if we consider the rim hooks which form the connecting pieces between colored cells, it could be that some of these cells were originally removed from λ to form μ and then added back to form γ. Thus in Figure 3, we know what weight to assign any blue square which has a blue square to its right or below it and, similarly, we know what weight to assign any red square which has a red square to its right or below it. However, we do not know how to assign a weight to a blue or red square that is at the top of one of the rim hooks which connect colored cells because the next square could have been part of a μ that appears on the right-hand side of (10) or not. Thus for each such connecting rim hook, we have to consider the sum of the weights over all possible choices of which cells in that rim hook are part of the corresponding μ on the right-hand side of (10). In Figure 3, we have pictured the possible connecting rim hooks to the right of the diagram and labeled these connecting rim hooks from top to bottom with the numbers 1 through 5. We shall make the convention that the top colored square, if any, is part of the connecting rim hook while the bottom colored square, if it exists, is not part of the connecting rim hook. Nevertheless, we shall always draw a connecting rim hook with its colored square at the bottom, if it exists, because the ultimate contribution of that connecting rim hook to the coefficient of s_{γ}(x_{1}, …, x_{n}) on the right-hand side of (10) depends on the color of the bottom square. Thus in Figure 3, we shall think of the connecting rim hook 1 as blank-blue connecting rim hook, the connecting rim hook 2 as blue-blue connecting rim hook, the connecting rim hook 3 as blue-red connecting rim hook, the connecting rim hook 4 as red-red connecting rim hook, and the connecting rim hook 5 as red-blank connecting rim hook. These are all the possible connecting rim hooks that can arise from a γ that satisfies condition (*).

This given, we shall show that for γ ≠ λ, d_{λ,γ}(q, t) is equal to \frac{t^{|λ|}}{t−1} times the product of the weights assigned to the connecting rim hooks times the product of the weights of all the blue squares which are not part of any connecting rim hook according their

Figure 3. Connecting rim hooks for γ

weights relative to the weight function w_{b} times the product of the weights of all the red squares which are not part of any connecting rim hook according their weights relative to the weight function w_{r}. The weight W (H) of a connecting rim hook H is obtained by summing the weights of its squares over all possible μ that give rise to λ and γ in equation (10). We shall show that we can find a closed expression for such a sum for each type of connecting rim hook. These closed expressions are listed below. Given any connecting rim hook h, we let r(h) and c(h) denote the number of rows and columns of h respectively. Again we emphasize that the bottom colored square, if any, is not considered part of the connecting rim hook. Thus for example, the first rim hook h_{1} in Figure 3 has r(h_{1}) = 2 and c(h_{1}) = 3. Similarly, if h_{2} is the second connecting rim hook in Figure 3, then r(h_{2}) = 4 and c(h_{2}) = 2. For each non-negative integer n, we let [n]_{t} = \frac{1−t^{n}}{1−t} = 1 + t + ⋯ + t^{n−1}.

Weights of connecting rim hooks

(1) If H is a blank-blue connecting rim hook, then W (H) = q^{c(H)}.

(2) If H is a blue-blue connecting rim hook, then W (H) = (t − q)q^{c(H)−1}.

(3) If H is a blue-red connecting rim hook, then

W (H) = \frac{(t − 1)(q − t)}{t(q − 1)} (\frac{[r(H) − 1]_{t} − q[r(H) − 2]_{t}}{t^{r(H)−2}} − q^{c(H)} − (q − t) ∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}} − 1}{t^{i}} ) ,

where β is the partition whose diagram is obtained by removing the first row and column of the smallest shape α which contains the connecting rim hook H, see Figure 3. Moreover, we assume that the sum ∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}}−1}{t^{i}} is equal to 0 if β is empty.

(4) If H is a red-red connecting rim hook, then W (H) = \frac{(q−t)}{t^{r(H)}}.

(5) If H is a red-blank connecting rim hook, then W (H) = \frac{(q−1)}{t^{r(H)}}.

For example, if we let H_{i} denote the connecting rim hook numbered by i in Figure 3, then

W (H_{1}) = q^{3},
W (H_{2}) = (t − q)q,
W (H_{3}) = \frac{(t − 1)(q − t)}{t(q − 1)} (\frac{[5]_{t} − q[4]_{t}}{t^{4}} − q^{4} − (q − t)(\frac{q^{3} − 1}{t} + \frac{q^{3} − 1}{t^{2}})) ,
W (H_{4}) = \frac{q − t}{t^{3}}, and
W (H_{5}) = \frac{q − 1}{t^{4}}.

Now the weights of the blue squares not in any connecting rim hook reading from top to bottom in Figure 3 are t, −1, t, and −1 respectively, and the weights of the red squares not in any connecting rim hook reading from top to bottom in Figure 3 are q/t, 1/t, 1/t, and 1/t, respectively. Thus for our example, d_{λ,γ}(q, t) = \frac{t^{|λ|}}{t−1} \frac{q}{t^{2}} W (H_{1}) ⋯ W (H_{5}). We should note that if γ ≠ λ, then there must always be a blue-red connecting rim hook H for γ. Thus the factor of (t − 1) which occurs in W (H) will always cancel the factor of t − 1 which appears in \frac{t^{|λ|}}{t−1}. In addition, there will either be a red-blank connecting rim hook or a bottom red square which will contribute a factor of q − 1 to cancel the q − 1 that appears in the denominator of W (H). Then it is not difficult to see that the factor t^{|λ|} is enough to cancel all the powers of t that occur in the denominators of any of the weights of the connecting rim hooks or isolated blue and red squares. Thus our result will show that d_{λ,γ}(q, t) is always just a polynomial in t and q.

2. λ-Ring Notation

Let A be a set of formal commuting variables and A^{∗} denote the set of all words over A. The empty word will be identified with “1”. Let c ∈ ℂ, γ = (γ_{1}, …, γ_{ℓ}) ⊢ n, x = a_{1}a_{2} … a_{i} be any word in A^{∗}, and X, X_{1}, X_{2}, … be any sequence of formal sums of the words in A^{∗} with complex coefficients. We define the λ-ring notation for the power symmetric functions by

p_{r}[0] = 0,  p_{r}[1] = 1,
p_{r}[x] = x^{r} = a_{1}^{r}a_{2}^{r} … a_{i}^{r},  p_{r}[c X] = c p_{r}[X],
p_{r} [∑_{i} X_{i}] = ∑_{i} p_{r}[X_{i}],  p_{γ}[X] = p_{γ_{1}}[X] ⋯ p_{γ_{ℓ}}[X],

where r is a nonnegative integer. These definitions imply that p_{r}[XX_{1}] = p_{r}[X]p_{r}[X_{1}] and therefore p_{γ}[XX_{1}] = p_{γ}[X]p_{γ}[X_{1}]. These definitions also imply that for any complex number c and γ ⊢ n, p_{γ}[cX] = c^{ℓ(γ)}p_{γ}[X].

When X = x_{1} + ⋯ + x_{N}, then our definitions ensure that

p_{k}[X] = ∑_{i=1}^{N} x_{i}^{k},

which is the usual power symmetric function p_{k}(x_{1}, …, x_{N}). Furthermore, for any partition λ = (λ_{1}, …, λ_{ℓ}),

p_{λ}[X] = p_{λ}(x_{1}, …, x_{N}).

The power symmetric functions are a basis for the ring of symmetric functions, so if Q is a symmetric function, then there are unique coefficients a_{λ} such that Q = ∑_{λ} a_{λ}p_{λ}. We then define Q[X] = ∑_{λ} a_{λ}p_{λ}[X]. It follows that in the special case where X = x_{1}+⋯+x_{N} is a sum of letters in A, Q[X] is simply the symmetric function Q(x_{1}, …, x_{N}). We note that if X = x_{1} + x_{2} + ⋯ as an infinite sum of letters, the same reasoning will show that for any symmetric function Q, Q[X] = Q(x_{1}, x_{2}, …).

Define

Ω[A] = e^{∑^{k≥1} \frac{p_{k}[A]}{k}} .  (14)

Next we state two well known theorems from the theory of λ-rings, see [3] or [6].

Theorem 1. For X, Y formal sums of words in A^{∗} with complex coefficients,

s_{μ/λ}[X + Y] = ∑_{λ⊆δ⊆μ} s_{μ/δ}[X]s_{δ/λ}[Y],  (15)
s_{μ/λ}[−X] = (−1)^{|μ′/λ′|}s_{μ′/λ′}[X],  (16)
s_{μ/λ}[X − Y] = ∑_{λ⊆δ⊆μ} s_{μ/δ}[X](−1)^{|δ/λ|}s_{δ′/λ′}[Y].  (17)

where λ′ denotes the conjugate partition of λ.

Theorem 2. If X = x_{1} + x_{2} + ⋯ and Y = y_{1} + y_{2} + ⋯, then

Ω[X + Y] = Ω[X]Ω[Y],  (18)
Ω[X] = ∏_{i} \frac{1}{1 − x_{i}} = ∑_{n≥0} h_{n}[X],  (19)
Ω[−X] = ∏_{i}(1 − x_{i}) = ∑_{n≥0}(−1)^{n}e_{n}[X].  (20)

Garsia and Haiman [2] proved the following λ-ring formulation of the operator D_{1}^{n}.

Theorem 3. If X = x_{1} + x_{2} + ⋯ + x_{n}, then for any symmetric polynomial Q[X],

D_{n}^{1}(Q[X]) = \frac{Q[X]}{1 − t} + \frac{t^{n}}{t − 1}Q [X − \frac{1 − q}{tz} ] Ω[(t − 1)Xz]|_{z^{0}}.  (21)

For the rest of this paper, we shall let X = x_{1} + x_{2} + ⋯ + x_{n}. Then for any Schur function s_{λ}(x_{1}, …, x_{n}) = s_{λ}[X] and we have by Theorems (1) and (2) that

D_{n}^{1}(s_{λ}[X]) = \frac{s_{λ}[X]}{1 − t} + \frac{t^{n}}{t − 1}s_{λ} [X − \frac{1 − q}{tz} ] Ω[(t − 1)Xz]|_{z^{0}}

= \frac{s_{λ}[X]}{1 − t} + \frac{t^{n}}{t − 1} (∑_{μ⊆λ} s_{μ}[X]s_{λ/μ} [\frac{q − 1}{tz}]) Ω[tXz]Ω[−Xz]|_{z^{0}}

= \frac{s_{λ}[X]}{1 − t} + \frac{t^{n}}{t − 1} (∑_{μ⊆λ} s_{μ}[X] (\frac{1}{tz} )^{|λ/μ|} s_{λ/μ}[q − 1])

× (∑_{n≥0} h_{n}[X](tz)^{n}) (∑_{n≥0} e_{n}[X](−z)^{n}) |_{z^{0}}

= \frac{s_{λ}[X]}{1 − t} + \frac{t^{n}}{t − 1}( ∑_{μ⊆λ} s_{μ}[X] (\frac{1}{t})^{|λ/μ|} s_{λ/μ}[q − 1]

× ∑_{k=0}^{|λ/μ|} t^{k}h_{k}[X](−1)^{|λ/μ|−k}e_{|λ/μ|−k}[X]).  (22)

By (17),

s_{λ/μ}[q − 1] = ∑_{μ⊆β⊆λ} s_{β/μ}[q](−1)^{|λ/β|}s_{λ′/β′}[1].  (23)

A skew diagram is a horizontal strip (respectively vertical strip) if it contains no two cells in the same column (row). It is easy to see that s_{β/μ}[q] = 0 unless β/μ is a horizontal strip. If β/μ is a horizontal strip, then s_{β/μ}[q] = q^{|β/μ|}. Similarly, s_{λ′/β′}[1] = 0 unless λ/β is a vertical strip. If λ/β is a vertical strip, then s_{λ/β}[1] = 1. This means that if μ arises from λ by first removing a vertical strip to obtain β and then removing a horizontal strip to obtain μ, then in the last summand of (22), s_{μ} would come with a weight \frac{1}{t^{|λ/μ|}} (−1)^{|λ/β|}q^{|β/μ|}. We can picture this situation as in Figure 4 by placing a −1 in each cell of λ/β and q in each cell of β/μ. It easy to see that in such situation, λ/μ is just a broken rim hook (BRH) of λ and that

(i): if s is a cell which has a cell in λ/μ to its right, then s must have a q in it, (ii): if s is a cell which has a cell in λ/μ to below it, then s must have a −1 in it,

and (iii): if s is a cell which has neither a cell in λ/μ to its right or below it, i.e. if s is the lowest cell in one of the rim hooks of λ/μ, then s could have either a q or a −1 in it.

Figure 4. A term from s_{λ/μ}[q − 1]

It follows that

D_{n}^{1}(s_{λ}[X]) = \frac{s_{λ}[X]}{1 − t}

+ \frac{t^{n}}{t − 1} ( ∑_{μ⊆λ,λ/μ is a BRH of λ} w_{r}(λ/μ)s_{μ}[X] ∑_{k=0}^{|λ/μ|} t^{k}h_{k}[X](−1)^{|λ/μ|−k}e_{|λ/μ|−k}[X]) . (24)

Here

w_{r}(λ/μ) = ∏_{s∈λ/μ} w_{r,λ/μ}(s)  (25)

where for each cell s ∈ λ/μ,

w_{r,λ/μ}(s) = \begin{cases}\frac{q}{t} & if s has a cell of λ/μ to its right, \\ \frac{−1}{t} & if s has a cell of λ/μ below it, and \\ \frac{q−1}{t} & if s is lowest cell of a rim hook in λ/μ. \end{cases}  (26)

Next we consider a term of the form

s_{μ}[X] (∑_{k=0}^{|λ/μ|} t^{k}h_{k}[X](−1)^{|λ/μ|−k}e_{|λ/μ|−k}[X]) .  (27)

The Pieri rules state that

s_{μ}[X]h_{k}[X] = ∑_{μ⊆β,β/μ is a horizontal strip of size k} s_{β} (28)

and

s_{μ}[X]e_{k}[X] = ∑_{μ⊆β,β/μ is a vertical strip of size k} s_{β}. (29)

It follows that if γ arises from μ by first adding a horizontal strip of size k to the outside of μ to get a shape α and then adding of vertical strip of size |λ/μ| − k on the outside of

Figure 5. A term from s_{μ}[X]t^{k}h_{k}[X](−1)^{|λ/μ|−k}e_{|λ/μ|−k}[X])

α to get γ, then s_{γ} will appear in the product s_{μ}[X]t^{k}h_{k}[X](−1)^{|λ/μ|−k}e_{|λ/μ|−k}[X]) with weight t^{k}(−1)^{|λ/μ|−k}. We can picture this situation in Figure 5 where we place a t in each square of the horizontal strip and −1 is each cell of the vertical strip. It easy to see that in such situation that γ/μ is just a broken rim hook (BRH) of γ and that

(a): if s is a cell which has a cell in γ/μ to its right, then s must have a t in it, (b): if s is a cell which has a cell in γ/μ below it, then s must have a −1 in it, and (c): if s is a cell which has neither a cell in γ/μ to its right or below it, i.e. if s is the lowest cell in one of the rim hooks of γ/μ, then s could have either a t or a −1 in it.

It follows that

s_{μ}[X] (∑_{k=0}^{|λ/μ|} t^{k}h_{k}[X](−1)^{|λ/μ|−k}e_{|λ/μ|−k}[X]) = ∑_{μ⊆γ,γ/μ is a BRH of γ of size |λ/μ|} w_{b}(γ/μ)s_{γ}[X]

(30)

where

w_{b}(γ/μ) = ∏_{s∈λ/μ} w_{b,λ/μ}(s)  (31)

and for each cell s ∈ γ/μ,

w_{b,λ/μ}(s) = \begin{cases}t & if s has a cell of γ/μ to its right, \\ −1 & if s has a cell of γ/μ below it, and \\ t − 1 & if s is lowest cell of a rim hook in γ/μ. \end{cases}  (32)

Thus combining (24) and (30), we see that

D_{n}^{1}(s_{λ}[X]) = \frac{s_{λ}[X]}{1 − t} + \frac{t^{n}}{t − 1} (_{∑_{μ⊆λ,λ/μ is a BRH of λ} μ⊆γ,γ/μ is a BRH of γ of size |λ/μ|}w_{r}(λ/μ)w_{b}(γ/μ)s_{γ}[X]) . (33)

Figure 6. A term from the sum in (33)

Each γ that appears on the right-hand side of (33) can be constructed by first removing a broken rim hook λ/μ from λ and then adding back a broken rim hook γ/μ of size |λ/μ| on the outside of μ. We shall think of the cells of λ/μ as being colored red and the cells of γ/μ as being colored blue. This is pictured in Figure 6 by putting an r in the cells of λ/μ and putting a b in the cells of γ/μ. In this case we see that λ = (2^{2}, 6^{3}, 9^{2}, 10^{2}, 14^{3}, 16, 17), μ = (1, 4, 5^{3}, 9, 10^{2}, 11, 14^{2}, 15, 17), and γ = (1, 6^{3}, 10^{4}, 14^{3}, 17^{2}).

We should note however that we cannot determine μ from λ and γ. That is, in Figure 6, we can determine the cells that are colored with just red and the cells that are colored with just blue from λ and γ. However λ and γ do not give us enough information to distinguish a cell which is colored both red and blue from a cell that is blank. That is, a cell that is colored both red and blue represents a cell that we first removed in the process of forming μ but then added back in the process of forming γ. Such a cell must lie on the outer boundary of γ. However, there may be other cells that are on the outer boundary of γ that have no color and hence are not a part of μ. For example, suppose λ = (2^{3}, 4) and γ = (1, 2^{2}, 5), then we know that cell (2, 4) must be red and cell (5, 1) must be blue. However there are various possibilities of for μ which are pictured in Figure 7. For the rim hook H of (2^{3}, 5) which includes the cell (2,4) plus all cells on the boundary between cell (2,4) and cell (5,1), there are 10 possible ways to color the remaining squares of H with either red-blue or blank so that the shape μ that results by removing all the squares which are colored red, blue, or red-blue from λ corresponds to a partition.

Thus the final weight associated with s_{γ} in (33) in the example of Figure 7 is the sum w_{r}(λ/μ)w_{b}(γ/μ) over all such μ. In our case, if we number the ten diagrams with the numbers 1 through 10 reading from left to right and then from top to bottom, then table 1 gives the corresponding weights of w_{r}(λ/μ), w_{b}(γ/μ) and w_{r}(λ/μ)w_{b}(γ/μ) for each of the 10 diagrams.

Figure 7. Possible μ for λ = (2^{3}, 4) and γ = (1, 2^{2}, 5)

\begin{matrix}diagram & w_{r}(λ/μ) & w_{b}(γ/μ) & w_{r}(λ/μ)w_{b}(γ/μ) \\ (1) & \frac{(q−1)}{t} & (t − 1) & \frac{(q−1)(t−1)}{t} \\ (2) & \frac{−(q−1)}{t^{2}} & (t − 1)^{2} & \frac{−(q−1)(t−1)^{2}}{t^{2}} \\ (3) & \frac{(q−1)}{t^{3}} & −(t − 1)^{2} & \frac{(q−1)(t−1)^{2}}{t^{3}} \\ (4) & \frac{(q−1)^{2}}{t^{2}} & t(t − 1) & \frac{(q−1)^{2}t(t−1)}{t^{2}} \\ (5) & \frac{−(q−1)^{2}}{t^{3}} & t(t − 1)^{2} & \frac{−(q−1)^{2}t(t−1)^{2}}{t^{3}} \\ (6) & \frac{(q−1)^{2}}{t^{4}} & −t(t − 1)^{2} & \frac{−(q−1)^{2}t(t−1)^{2}}{t^{4}} \\ (7) & \frac{q(q−1)^{2}}{t^{3}} & t^{2}(t − 1) & \frac{q(q−1)^{2}t^{2}(t−1)}{t^{3}} \\ (8) & \frac{−q(q−1)^{2}}{t^{4}} & t^{2}(t − 1)^{2} & \frac{−q(q−1)^{2}t^{2}(t−1)^{2}}{t^{4}} \\ (9) & \frac{q(q−1)^{2}}{t^{5}} & −t^{(}t − 1)^{2} & \frac{−q(q−1)^{2}t^{2}(t−1)^{2}}{t^{5}} \\ (10) & −\frac{q^{2}(q−1)}{t^{6}} & t^{3}(t − 1) & \frac{−q^{2}(q−1)t^{3}(t−1)}{t^{6}} \end{matrix}

Table 1

Now the weight associated to s_{γ}[X] in (33) would be the sum of all the polynomials in the last column. It is also easy to see that the bottom blue cell contributes a factor of (t − 1) to w_{b}(γ/μ), regardless of what μ is, since it will never have cell to its right or below it in γ/μ. In this case, there is only one connecting rim hook, namely H. Since H does not include cell (5,1), it follows that we can associate a weight W (H) by summing over all the terms in column four of the table and dividing by (t − 1). In this way, we can associate a final weight W (H) with each connecting rim hook H of γ. In fact, in general there will 9 types of connecting rim hooks associated an s_{γ}[X] that appears on the right-hand side of (33) depending on the color of the top and bottom squares of the connecting rim hooks. These are pictured in Figure 8.

Figure 8. Possible connecting rim hooks

Figure 9. The connecting rim hook B_{λ}

Now suppose that relative to λ, the connecting rim hooks of γ are H_{1}, …, H_{a}, the red cells which are not part of any connecting rim hooks are r_{1}, …, r_{b} and blue cells which are not part of any connecting rim hooks are b_{1}, …, b_{c}. Then it is easy to see that since the color of the cells which lie either immediately to the right of directly below each r_{i} and b_{j} is completely determined by λ and γ, the weights of w_{r,λ/μ}(r_{i}) and w_{b,γ/μ}(b_{j}) will be always be the same for all μ. Thus the total weight associated with s_{γ}[X] in (33) can be factored as

(∏_{s=1}^{a} W (H_{i})) (∏_{i=1}^{b} w_{r,λ/μ}(r_{i})) (∏_{j=1}^{c} w_{b,γ/μ}(b_{j})) .

3. The leading coefficient

In this section, we shall directly compute the coefficient of s_{λ} in D_{n}^{1}(s_{λ}). To do this, we shall need to compute W (H) when H is a blank-blank connecting rim hook. Indeed the only s_{γ} that appears in (33) that involves a blank-blank connecting rim hook is when γ = λ. We then have the following result.

Theorem 4. Let λ = (λ_{1} ≥ ⋯ ≥ λ_{ℓ(α)}) be a partition of n and let B_{λ} be the outside border of λ as pictured in Figure 9. Then

W (B_{λ}) = 1 + (t − 1) ∑_{i=1}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}}.  (34)

Proof. We proceed by induction on the number of non-zero parts of λ. Let BRH(B_{λ}) denote the set of broken rim hooks in B_{λ}. Note that

W (B_{λ}) = ∑_{μ⊆λ,λ/μ is a BRH} w_{r}(λ/μ)w_{b}(λ/μ)
= 1 + ∑_{h∈BRH(B_{λ}),h≠∅} w_{r}(h)w_{b}(h)  (35)

That is, the μ = λ term above corresponds to the empty broken rim hook which contributes 1 to the sum since all the cells would be blank in this case. Thus to prove (34), we must show that

∑_{h∈BRH(B_{λ}),h≠∅} w_{r}(h)w_{b}(h) = (t − 1) ∑_{i=1}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t_{i}}.  (36)

Now if λ = (n), then B_{λ} = λ and the only non-empty h ∈ BRH(B_{λ}) are of form h = (n)/(n − k) some k > 0. For each cell c that has a cell to its right in h,

w_{r,(n)/(n−k)}(c)w_{b,(n)/(n−k)}(c) = \frac{q}{t} t = q.

For the last red-blue cell in (n)/(n − k), w_{r,(n)/(n−k)}(c)w_{b,(n)/(n−k)}(c) = \frac{q−1}{t}(t − 1). Thus in this case,

w_{r}((n)/(n − k))w_{b}((n)/(n − k)) = (q − 1)(t − 1)q^{k−1}/t.

Hence

∑_{h∈BRH(B_{λ}),h≠∅} w_{r}(h)w_{b}(h) = ∑_{k=1}^{n}(q − 1)(t − 1)q^{k−1}/t

= \frac{(t − 1)}{t}(q − 1)(1 + q + ⋯ + q^{n−1})

= \frac{(t − 1)}{t}(q^{n} − 1) = (t − 1)\frac{q^{n} − 1}{t}.

Now assume ℓ(λ) ≥ 2 and that for all k and all partitions γ = (γ_{1} ≥ ⋯ ≥ γ_{ℓ(γ)}) of k such that ℓ(γ) < ℓ(λ), we have

∑_{h∈BRH(B_{γ}),h≠∅} w_{r}(h)w_{b}(h) = (t − 1) ∑_{i=1}^{ℓ(γ)} \frac{q^{γ_{i}} − 1}{t^{i}}.  (37)

It follows that if ℓ(γ) < ℓ(λ), then

∑_{h∈BRH(B_{γ}), h starts in row 1} w_{r}(h)w_{b}(h) = (t − 1) ∑_{i=1}^{ℓ(γ)} \frac{q^{γ_{i}} − 1}{t^{i}} − (t − 1) ∑_{i=1}^{ℓ(γ)−1} \frac{q^{γ_{i+1}} − 1}{t^{i}}. (38)

Figure 10. Two types of configuration for B_{λ}

We shall classify the non-empty h ∈ BRH(B_{λ}) into two types depending on whether h contains the left most cell s in the first row or not. We let γ be the partition that results by removing λ_{1} from λ. Thus γ = (λ_{2} ≥ ⋯ ≥ λ_{ℓ(λ)}). First suppose λ_{1} ≠ λ_{2}. Then we have two types of configurations as pictured in Figure 10 where we indicate the red-blue squares by shading the square.

If h does not contain s then

∑_{h∈BRH(B_{λ}),h≠∅,s∉h}w_{r}(h)w_{b}(h)

= ( ∑_{h_{1}∈BRH(B_{γ})} w_{r}(h_{1})w_{b}(h_{1})) ( ∑_{h_{2}∈BRH(B_{(λ_{1}−λ_{2})})} w_{r}(h_{2})w_{b}(h_{2})) − 1

= (1 + (t − 1) ∑_{i=1}^{ℓ(λ)−1} \frac{q^{λ_{i+1}} − 1}{t^{i}} ) (1 + (t − 1)\frac{q^{λ_{1}−λ_{2}} − 1}{t}) − 1

= (1 + t(t − 1) ∑_{i=2}^{n} \frac{q^{λ_{i}} − 1}{t^{i}}) (1 + (t − 1)\frac{q^{λ_{1}−λ_{2}} − 1}{t}) − 1

= (t − 1)\frac{q^{λ_{1}−λ_{2}} − 1}{t} + t(t − 1) ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}}

+ (q^{λ_{1}−λ_{2}} − 1)(t − 1)^{2} ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}}

= (t − 1)\frac{q^{λ_{1}−λ_{2}} − 1}{t} + (t − 1) ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}}

+ q^{λ_{1}−λ_{2}}(t − 1)^{2} ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}}.  (39)

Here the −1 in the first equality comes from subtracting away the configuration corresponding to the empty BRH which has weight 1. Now if λ_{1} = λ_{2}, then it is easy to see that

∑_{h∈BRH(B_{λ}),h≠∅,s∉h} w_{r}(h)w_{b}(h) = ∑_{h∈BRH(B_{γ}),h≠∅} w_{r}(h)w_{b}(h)

= (t − 1) ∑_{i=1}^{n−λ_{1}} \frac{q^{γ_{i}} − 1}{t_{i}}

= t(t − 1) ∑_{i=2}^{n} \frac{q^{λ_{i}} − 1}{t^{i}}.

which is equal to the expression in line 4 of our string of equalities in (39). Thus (39) is also true when λ_{1} = λ_{2}.

Now if the broken rim hook h does contain s, then all the squares directly above and to the right of s must be colored red-blue. For the cell s_{a} directly above s, w_{r,h}(s_{a})w_{b,h}(s_{a}) = \frac{−1}{t}(−1) = \frac{1}{t}. Then we can argue as above that the cells in the first row contribute a factor of q^{λ_{1}−λ_{2}} \frac{(q−1)(t−1)}{t}. Now let h′ be the BRH which consists of all the cells of h except those in the first row. In that case it follows that w_{r,h′}(s_{a})w_{b,h′}(s_{a}) = \frac{(q−1)(t−1)}{t}. Thus w_{r}(h)w_{b}(h) = \frac{q^{λ_{1}−λ_{2}}}{t} w_{r}(h′)w_{b}(h′). Again this holds for λ_{1} = λ_{2}. Hence

∑_{h∈BRH(B_{λ}),h≠∅,s∈h} w_{r}(h)w_{b}(h) = \frac{q^{λ_{1}−λ_{2}}}{t} ∑_{h′∈BRH(B_{γ}), h starts in row 1} w_{r}(h′)w_{b}(h′)

= \frac{q^{λ_{1}−λ_{2}}}{t} (t − 1) ( ∑_{i=1}^{ℓ(λ)−1} \frac{q^{λ_{i+1}} − 1}{t^{i}} − ∑_{i=1}^{ℓ(λ)−2} \frac{q^{λ_{i+2}} − 1}{t^{i}} )

= q^{λ_{1}−λ_{2}}(t − 1) (∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}} − t ∑_{i=3}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}} ) .  (40)

18 JEFFREY REMMEL

Thus combining (39) and (40), we see that

∑_{h∈BRH(B_{λ}),h≠∅}w_{r}(h)w_{b}(h)

= \frac{t − 1}{t}(q^{λ_{1}−λ_{2}} − 1) + (t − 1) ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}} + q^{λ_{1}−λ_{2}}(t − 1)^{2} ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}}

+ q^{λ_{1}−λ_{2}}(t − 1) ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}} − q^{λ_{1}−λ_{2}}(t^{2} − t) ∑_{i=3}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}}

= \frac{t − 1}{t}(q^{λ_{1}−λ_{2}} − 1) + t(t − 1) ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}}

+ q^{λ_{1}−λ_{2}}(t^{2} − t) ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}} − q^{λ_{1}−λ_{2}}(t^{2} − t) ∑_{i=3}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}}

= \frac{t − 1}{t}(q^{λ_{1}−λ_{2}} − 1) + (t − 1) ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}} + (t^{2} − t)\frac{q^{λ_{2}} − 1}{t^{2}}

= \frac{t − 1}{t}(q^{λ_{1}−λ_{2}} − 1) + (t − 1) ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}} + q^{λ_{1}−λ_{2}} \frac{(t − 1)}{t}(q^{λ_{2}} − 1)

= \frac{t − 1}{t}(q^{λ_{1}−λ_{2}} − 1) + (t − 1) ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}} + \frac{(t − 1)}{t}(q^{λ_{1}} − \frac{(t − 1)}{t}q^{λ_{1}−λ_{2}})

= (t − 1)\frac{q^{λ_{1}} − 1}{t} + (t − 1) ∑_{i=2}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}}

= (t − 1) ∑_{i=1}^{ℓ(λ)} \frac{q^{λ_{i}} − 1}{t^{i}}.

□

It follows that the coefficient of s_{λ} in D_{n}^{1}(s_{λ}) is

\frac{1}{1 − t} + \frac{t^{n}}{(t − 1)} (1 + (t − 1) ∑_{i=1}^{n} \frac{q^{λ_{i}} − 1}{t^{i}}) = \frac{t^{n} − 1}{t − 1} + ∑_{i=1}^{n} q^{λ_{i}}t^{n−i} − t^{n−i}

= ∑_{i=1}^{n} q^{λ_{i}}t^{n−i}.

Thus we have proved the following. Theorem 5. The coefficient of s_{λ} in D_{n}^{1}(s_{λ}) equals ∑_{i=1}^{n} q^{λ_{i}}t^{n−i}.

Figure 11. Weights of vertical connecting rim hooks

4. Computing weights of simple connecting rim hooks

The goal of the next 4 sections is compute explicit formulas for the weights over all such connecting rim hooks as described in section 2. We shall start by computing the weights of certain simple connecting rim hooks.

We start by considering the connecting rim hooks which are just a column. That is, in Figure 11, we consider connecting rim hooks which consists of a column of L squares that can be colored either red-blue or blank and then we add either a square colored red, a square colored blue, a square colored red-blue, or nothing on top. We shall let rV (L), bV (L), rbV (L), and V (L) denote the connecting rim hooks pictured in Figure 11 reading from left to right. We then have the following lemma.

Lemma 6.

W (rV (L)) = \frac{(q − 1)}{t^{L+1}},  (41)
W (bV (L)) = (t − q) + \frac{(q − 1)}{t^{L}},  (42)
W (rbV (L)) = (q − 1) (1 − \frac{1}{t^{L+1}} ) ,  (43)
W (V (L)) = 1 + (q − 1) (1 − \frac{1}{t^{L}} ) .  (44)

Proof. We will do the calculation for W (rV (L)) and leave the rest of the calculations to the reader as they are all done in the same way. Let the cells of rV (L) be labeled as c_{0}, c_{1}, …, c_{L} reading from top to bottom. Relative to rV (L), the possible μ are determined by how many (r, b) cells there are immediately below the cell c_{0} which contains the red cell at the top of rV (L). If there are k such cells, then the factor of w_{r}(λ/μ) contributed by these cells is ∏_{i=0}^{k} w_{r,λ/μ}(c_{i}) = \frac{(−1)^{k}(q−1)}{t^{k+1}}. The factor of w_{b}(γ/μ) contributed by these cells is 1 if k = 0 and ∏_{i=1}^{k} w_{b,γ/μ}(c_{i}) = (−1)^{k−1}(t − 1). Thus if k = 0, w_{r,λ/μ}(c_{0}) = \frac{q−1}{t}

Figure 12. Possible connecting horizontal rim hooks

and if 0 < k ≤ L,

(∏_{i=0}^{k} w_{r,λ/μ}(c_{i})) (∏_{i=1}^{k} w_{b,γ/μ}(c_{i})) = \frac{(−1)(q − 1)(t − 1)}{t^{k+1}}.

Thus

W (rV (L)) = \frac{(q − 1)}{t} + ∑_{k=1}^{L} \frac{(−1)(q − 1)(t − 1)}{t^{k+1}}

= (q − 1) (\frac{1}{t} − ∑_{k=1}^{L}(\frac{1}{t^{k}} − \frac{1}{t^{k+1}} ))

= \frac{(q − 1)}{t^{L+1}}.

□

In Figure 12, we consider the connecting rim hooks which consist of a row of L squares which can be colored with either red-blue or blank and then we add either a square colored red, a square colored blue, a square colored red-blue, or nothing to the right. We shall let Hr(L), Hb(L), Hrb(L) and H(L) denote the connecting rim hooks pictured in Figure 11 reading from top to bottom. Recall that by our conventions, these rim hooks do not include the colored square on the right if it exists. We then have the following lemma.

Lemma 7.

W (Hr(L)) = \frac{(q − t) + (t − 1)q^{L+1}}{t(q − 1)} ,  (45)
W (Hb(L)) = q^{L},  (46)
W (Hrb(L)) = \frac{q^{L+1} − 1}{q − 1},  (47)
W (H(L)) = 1 + \frac{(t − 1)(q^{L} − 1)}{t}.  (48)

Proof. We will do the calculation for W (Hr(L)) and leave the rest of the calculations to the reader. Let the cells of Hr(L) be labeled as c_{0}, c_{1}, …, c_{L} reading from right to left. Relative to Hr(L), the possible μ are determined by how many (r, b) cells there are immediately to the left of the cell c_{0} which contains the red cell at the right of Hr(L). If there are k such cells, then the factor of w_{r}(λ/μ) contributed by these cells is ∏_{i=1}^{k} w_{r,λ/μ}(c_{i}) = (q/t)^{k}. The factor of w_{b}(γ/μ) contributed by these cells is 1 if k = 0 and ∏_{i=1}^{k} w_{b,γ/μ}(c_{i}) = t^{k−1}(t − 1) if k > 0. Thus if k = 0, the contribution is 1 and if 0 < k ≤ L, the contribution is

(∏_{i=1}^{k} w_{b,γ/μ}(c_{i})w_{r,λ/μ}(c_{i})) = \frac{q^{k}(t − 1)}{t}.

Thus

W (Hr(L)) = 1 + \frac{q(t − 1)}{t} ∑_{k=0}^{L−1} q^{k}

= 1 + \frac{q(t − 1)(q^{L} − 1)}{t(q − 1)}

= \frac{tq − t + tq^{L+1} − qt − q^{L+1} + q}{t(q − 1)}

= \frac{q − t + (t − 1)q^{L}}{t(q − 1)} .

□

There is one more simple rim hook whose weight we want to compute for future computations. This rim hook pictured in Figure 13 which we call an inverted-L of type (a, b) and denote by INV L(a, b).

Lemma 8.

W (INV L(a, b)) = q^{a+1} + \frac{1}{t^{b+1}} − \frac{q^{a+1}}{t^{b+1}} .  (49)

Proof. There are two cases. Namely if the top corner square is blank, then it must be case that all the squares are blank. That is, the red squares represent those squares which we first removed from λ to form λ/μ so that a square which is colored red or red-blue cannot lie to the left or below a blank square. Thus if the top corner square is blank, then the corresponding configuration would have weight 1.

Figure 13. An inverted L of type (a, b)

Next if the top corner square is colored red-blue, then the configuration breaks up into two connecting rim hooks, namely, Hrb(a) and rbV (b). Thus by our previous lemma, the sum of w_{r}(λ/μ)w_{r}(γ/μ) over all possible μ’s in this case is just

\frac{q^{a+1} − 1}{q − 1} · (q − 1) (1 − \frac{1}{t^{b+1}} ) = (q^{a+1} − 1) (1 − \frac{1}{t^{b+1}} ) .

Thus

W (H) = 1 + (q^{a+1} − 1)(1 − \frac{1}{t^{b+1}} )

= 1 + (q^{a+1} − 1) − \frac{q^{a+1}}{t^{b+1}} + \frac{1}{t^{b+1}}

= q^{a+1} + \frac{1}{t^{b+1}} − \frac{q^{a+1}}{t^{b+1}} .

□

5. W (H) for red-blue, blue-blue, and blank-blue connecting rim hooks.

In this section, we shall compute W (H) for red-blue, blue-blue, and blank-blue connecting rim hooks. Recall that by our conventions, the blue square at the end is not part of the connecting rim hook. We also note that in such a case, we cannot have the last square of the connecting rim hook be immediately above the blue square for this would mean that there is blank square immediately above the blue square. But then this blank square would be part of both λ and μ which would violate the condition that the blue squares are added on the outside of μ.

Our first step is to compute a reduction lemma which will allows to reduce the number of lower corner squares that are part of the connecting rim hook. To this end, we consider the connecting rim hooks H_{1} and H_{2} pictured in Figures 14 and 15 respectively.

In Figure 14, we shall label the corner squares on the lower side of H_{1} by s, t, and w reading from top to bottom. In Figure 15, we shall label the corner squares on the lower side of H_{2} by u and v reading from top to bottom. We shall refer to the portion of the connecting rim hook that lies above above the corner labeled s in Figure 14 as Up(H_{1}, s) and the portion of the connecting rim hook that lies above the corner labeled Figure 14. The connecting rim hook H_{1}

Figure 15. The connecting rim hook H_{2}

u in Figure 15 as Up(H_{2}, u). Then we shall assume that Up(H_{1}, s) = Up(H_{2}, u) where we allow the possibility that both Up(H_{1}, s) and Up(H_{2}, u) are empty. While we have drawn our pictures so that E ≠ 0, we also allow the possibility that E = 0.

Lemma 9. If H_{1} and H_{2} are the connecting rim hooks pictured in Figures 14 and 15, respectively, and Up(H_{1}, s) = Up(H_{2}, u), then W (H_{1}) = W (H_{2}).

We note that import of Lemma 9 is that it says that to compute W (H) for any blueblue, red-blue, or blank-blue connecting rim hook, we need only consider the cases where H has at most 2 lower corner squares. For example, to compute a formula for W (H) for red-blue connecting rim hooks, we need only consider the two types of connecting rim hooks pictured in Figure 16.

Proof. Let A = q^{A+1}, B = t^{B+1}, C = q^{C+1}, D = t^{D+1} and E = q^{E}. To compute W (H_{i}), we need to compute the sum of ∏_{c∈H_{1}} w_{r,λ/μ}(c)w_{b,γ/μ}(c) over all possible choices of μ in (10). This is equivalent to considering all possible colorings of H_{i}, using either the colors blank or red-blue for all the cells of H_{i}, except possibly the top cell of H_{i}, that could correspond to such μ. Thus we shall think of the weights of colorings of the cells of H_{i} where the weight of any blank cell is 1 and the weight of any red-blue cell c is w_{r,λ/μ}(c)w_{b,γ/μ}(c).

Figure 16. Limiting cases of red-blue connecting rim hooks

Figure 17. Case 1 for H_{1}, s is blank

We shall organize our computation of W (H_{1}) and W (H_{2}) by first considering those colorings for which the square s and the square u are blank. In such a situation, we let U denote the sum of the weights over all possible colorings of Up(H_{1}, s) = UP (H_{2}, u) given that the cells s and u are blank. This given, we can then classify such colorings for H_{1} according to whether cells t and w are blank or red-blue. In the pictures below, we shall picture a red-blue cell as a filled cell. There are clearly four such cases.

In Case 1, we are assuming that t and w are blank, see Figure 17. Thus the sum S_{1} of the weights of the colorings in this case is

S_{1} = W (INV L(A, B))W (INV L(C, D))W (Hb(E))U.  (50)

Thus using Lemmas 6, 7, and 8, we see that

S_{1} = W (INV L(A, B))W (INV L(C, D))W (Hb(E))U

= (q^{A+1} + \frac{1}{t^{B+1}} − \frac{q^{A+1}}{t^{B+1}} ) (q^{C+1} + \frac{1}{t^{D+1}} − \frac{q^{C+1}}{t^{D+1}} ) q^{E}U

= (A + \frac{1}{B} − \frac{A}{B}) (C + \frac{1}{D} − \frac{C}{D}) EU.  (51)

In Case 2, we are assuming that cell t is colored red-blue and that cell w is blank, see Figure 18. It follows that the cells directly above cell t and the cells directly to the right of cell t must be colored red-blue. Among those cells it is easy to see from our definitions of w_{r,λ/μ}(c) and w_{b,λ/μ}(c) that the cells directly above cell t contribute a factor of \frac{1}{B} = \frac{1}{t^{B+1}} and cell t plus all the cells to the right of cell t except the last cell in its row contribute a factor of C = q^{C+1}. Note we consider the last cell in the row of cell t to be part of the rbV (D) connecting rim hook. Thus the sum S_{2} of the weights of the colorings in this case

Figure 18. Case 2 for H_{1}, s is blank

is

S_{2} = W (Hrb(A))W (rbV (D))W (Hb(E))U \frac{C}{B}.  (52)

Again using Lemmas 6, 7, and 8, we see that

S_{2} = W (Hrb(A))W (rbV (D))W (Hb(E))U \frac{C}{B}

= \frac{(q^{A+1} − 1)}{(q − 1)}(q − 1) (1 − \frac{1}{t^{D+1}} ) q^{e}U \frac{C}{B}

= (A − 1) (1 − \frac{1}{D}) EU \frac{C}{B}.  (53)

In Case 3, we are assuming that cell w is colored red-blue and that cell t is blank, see Figure 19. It follows that the cells directly above cell w and the cells directly to the right of w must be colored red-blue. Among those cells it is easy to see from our definitions of w_{r,λ/μ}(c) and w_{b,λ/μ}(c) that the cells directly above cell w contribute a factor of \frac{1}{D} = \frac{1}{t^{D+1}} and cell w plus all the cells to the right of cell w except the last cell in its row contribute a factor of E(q − 1) = q^{E}(q − 1). Here the (q − 1) corresponds to the weight of the cell directly to left of the blue cell at the bottom of the diagram. Thus the sum S_{3} of the weights of the colorings in this case is

S_{3} = W (INV L(A, B))W (Hrb(C))U \frac{E}{D}(q − 1).  (54)

Again using Lemmas 6, 7, and 8, we see that

S_{3} = W (INV L(A, B))W (Hrb(C))U \frac{E}{D}(q − 1)

= (q^{A+1} + \frac{1}{t^{B+1}} − \frac{q^{A+1}}{t^{B+1}} ) \frac{(q^{C+1} − 1)}{(q − 1)}U \frac{E}{D}(q − 1)

= (A + \frac{1}{B} − \frac{A}{B}) (C − 1)U \frac{E}{D}.  (55)

In Case 4, we are assuming that both cell t and cell w are colored red-blue, see Figure 20. Thus all the cells of H_{1} that lie either directly above or to the right of cells t and w must be colored red-blue. The product of the weights of such cells is \frac{CE}{BD}(q − 1) = \frac{q^{A+1}q^{D}}{t^{B+1}t^{D+1}} (q − 1).

Figure 19. Case 3 for H_{1}, s is blank

Figure 20. Case 4 for H_{1}, s is blank

Thus the sum S_{4} of the weights of the colorings in this case is

S_{4} = W (Hrb(A))U \frac{CE}{BD}(q − 1).  (56)

Using Lemma 7, we see that

S_{4} = W (Hrb(A))U \frac{CE}{BD}(q − 1)

= \frac{(q^{A+1} − 1)}{(q − 1)}U \frac{CE}{BD}(q − 1)

= (A − 1)U \frac{CE}{BD}.  (57)

A little algebra will show that

S_{1} + S_{2} + S_{3} + S_{4} = ACEU.  (58)

Next we consider the cases for H_{1} where cell s is colored red-blue. This means that all the cells directly above or directly to the right of s must be colored red-blue. In particular, all the cells in same row as s except for the last cell contributes a factor of A = q^{A+1} to the weight. We let V denote the sum of weights over all possible colorings of Up(H_{1}, s) = UP (H_{2}, u) given that the cells s and u are colored red-blue. Then we have four more cases to consider, depending on the colors of cells t and w.

In Case 5, we are assuming that t and w are blank, see Figure 21. Thus the sum S_{5} of the weights of the colorings in this case is

S_{5} = W (rbV (B))W (INV L(C, D))W (Hb(E))AV.  (59)

Figure 21. Case 5 for H_{1}, s is colored red-blue

Thus using Lemmas 6, 7, and 8, we see that

S_{5} = W (rbV (B))W (INV L(C, D))W (Hb(E))AV

= (q − 1)(1 − \frac{1}{t^{B+1}} ) (q^{C+1} + \frac{1}{t^{D+1}} − \frac{q^{D+1}}{t^{D+1}} ) q^{E}AV

= (q − 1) (1 − \frac{1}{B}) (C + \frac{1}{D} − \frac{C}{D}) EAV.  (60)

In Case 6, we are assuming that cell t is colored red-blue and that cell w is blank. It follows that the cells directly above cell t and the cells directly to the right of cell t must be colored red-blue. It is easy to see from our definitions of w_{r,λ/μ}(c) and w_{b,λ/μ}(c) that the cells directly above cell t contribute a factor of \frac{1}{B} = \frac{1}{t^{B+1}} and cell t plus all the cells to the right of cell t except the last cell in its row contribute a factor of C = q^{C+1}. Again, we shall consider the last cell in the row of cell t to be part of the rbV (D) connecting rim hook. Thus the sum S_{6} of the weights of the colorings in this case is

S_{6} = W (rbV (D))W (Hb(E))AV \frac{C}{B}.  (61)

Using Lemmas 6 and 7, we see that

S_{6} = W (rbV (D))W (Hb(E))AV \frac{C}{B}

= (q − 1) (1 − \frac{1}{t^{D+1}} ) q^{E}AV \frac{C}{B}

= (q − 1) (1 − \frac{1}{D}) EAV \frac{C}{B}.  (62)

In Case 7, we are assuming that cell w is colored red-blue and that cell t is blank, see Figure 23. It follows that the cells directly above cell w and the cells directly to the right of w must be colored red-blue. Among those cells it is easy to see from our definitions of w_{r,λ/μ}(c) and w_{b,λ/μ}(c) that the cells directly above cell w contribute a factor of \frac{1}{D} = \frac{1}{t^{D+1}} and cell w plus all the cells to the right of cell w except the last cell in its row contribute a factor of E(q − 1) = q^{E}(q − 1). Here the (q − 1) corresponds to the weight of the cell directly to left of the blue cell at the bottom of the diagram. Thus the sum S_{7} of the Figure 22. Case 6 for H_{1}, s is colored red-blue

Figure 23. Case 7 for H_{1}, s is colored red-blue

weights of the colorings in this case is

S_{7} = W (rbV (B))W (Hrb(C))AV \frac{E}{D}(q − 1).  (63)

Again using Lemmas 6, 7, and 8, we see that

S_{7} = W (rbV (B))W (Hrb(C))AV \frac{E}{D}(q − 1)

= (q − 1) (1 − \frac{1}{t^{B+1}} ) \frac{(q^{c+1} − 1)}{(q − 1)}AV \frac{E}{D}(q − 1)

= (q − 1) (1 − \frac{1}{B}) (C − 1)AV \frac{E}{D}.  (64)

In Case 8, we are assuming that both cell t and cell w are colored red-blue, see Figure 24. Thus all the cells of H_{1} that lie either directly above or to the right of cells t and w must be colored red-blue. The product of the weights of such cells is \frac{CE}{BD}(q − 1) = \frac{q^{A+1}q^{E}}{t^{B+1}t^{D+1}} (q − 1). Thus the sum S_{8} of the weights of the colorings in this case is

S_{8} = (q − 1)AV \frac{CE}{BD}.  (65)

Then it is easy to check that

S_{5} + S_{6} + S_{7} + S_{8} = (q − 1)ACEV  (66)

and, hence,

W (H_{1}) = ACEU + (q − 1)ACEV.  (67)

Figure 24. Case 8 for H_{1}, s is red-blue

Figure 25. Case I for H_{2}, u is blank

We organize the computation of W (H_{2}) in the same way. That is, we first consider those colorings where cell u is blank. In this situation, there are two cases.

In Case I, we assume that cell v is blank, see Figure 25. Thus the sum T_{1} of weights of the colorings in this case is

T_{1} = W (INV L(A + C + 1, B + D + 1))W (Hb(E))U

= (q^{A+C+2} + \frac{1}{t^{B+D+2}} − \frac{q^{A+C+2}}{t^{B+D+2}} ) q^{E}U

= (AC + \frac{1}{BD} − \frac{AC}{BD}) EU.  (68)

In Case II, we assume that v is colored red-blue, see Figure 26. Thus all the cells in the same row and column as v must be colored red-blue. These cells always contribute a factor of \frac{1}{t^{B+D+2}} q^{E}(q − 1) = \frac{E}{BD} to the weight of any coloring. Thus the sum T_{2} of the weights of the possible colorings in this case is

T_{2} = W (Hrb(A + C + 1))U(q − 1)\frac{E}{BD}

= \frac{(q^{A+C+2} − 1)}{(q − 1)}U(q − 1)\frac{E}{BD}

= (AC − 1)U \frac{E}{BD}  (69)

Then it is easy to check that T_{1} + T_{2} = ACEU.

Next we consider the case where u is colored red-blue. Then all the cells in the same row or column as u must be colored red-blue. In this case, the cells in the same row as u Figure 26. Case II for H_{2}, u is blank

Figure 27. Case III for H_{1}, u is red-blue

except for the last cell contribute a factor of q^{A+C+2} = AC to the weight of any coloring. Again there are two cases depending on the color of v.

In Case III, we assume that cell v is blank, see Figure 27. Thus the sum T_{3} of weights of the colorings in this case is

T_{3} = W (rbV (B + D + 1)W (Hb(E))V AC

= (q − 1) (1 − \frac{1}{t^{B+D+2}} ) q^{E}V AC

= (q − 1) (1 − \frac{1}{BD}) EV AC.  (70)

In Case IV, we assume that v is colored red-blue, see Figure 28. In this case, the sum T_{4} of the weights of the coloring is

T_{4} = q^{A+C+2} \frac{1}{t^{B+D+2}} q^{E}(q − 1)V = (q − 1)\frac{ACE}{BD}V.  (71)

Then it is easy to check that

T_{3} + T_{4} = (q − 1)ACEV

so that

W (H_{2}) = ACEU + (q − 1)ACEV.  (72)

Thus comparing (67) and (72), we see that W (H_{1}) = W (H_{2}) as claimed. □

We now are in position to prove the main result of this section.

Theorem 10. (1) If H is red-blue connecting rim hook, then W (H) = 0. (2) If H is a blank-blue connecting rim hook, then W (H) = q^{c(H)}.

Figure 28. Case 4 for H_{1}, u is red-blue

Figure 29. Red-blue 1 lower corner shapes

(3) If H is a blue-blue connecting rim hook, then W (H) = (t − q)q^{c(H)−1}.

Proof. We shall prove only (1) since the exact same ideas can be used to prove (2) and (3) and, hence, we will leave those details to the reader. As noted above, we need only consider connecting rim hooks H where there are either one or two lower corner squares as pictured Figure 16.

Let us first consider the case where the red-blue connecting rim hook H has one lower corner square. There are two basic cases, namely, the case where the corner square is blank and the corner square is colored red-blue, see Figure 29.

If the corner square is blank, then it is easy to see that sum of the weights of the possible colorings is

W (rV (A))W (Hb(B)) = \frac{(q − 1)}{t^{A+1}}q^{B}.

If the corner cell is colored red-blue, then the top red cell has weight \frac{−1}{t} and the remaining A cells is the vertical part each contribute a weight \frac{−1}{t}(−1) = \frac{1}{t}. Each cell in the bottom row except for the cell that immediately precedes the blue cell, contributes a weight of \frac{q}{t}t = q. The cell that immediately precedes the blue cell contributes a weight of \frac{(q−1)}{t}t = (q − 1). The weight corresponding to this configuration is −\frac{(q−1)q^{B}}{t^{A+1}} . Thus W (H) = 0 in this case.

Next we consider the case where the red-blue connecting rim hook has two corner squares. Thus there are four cases depending on whether the two lower corner squares are colored red-blue or blank as pictured in Figure 30.

Figure 30. Red-blue 2 lower corner shapes

In Case 1 of Figure 30, we have the sum of the weights of the colorings in this case is

W (rV (A))W (INV T L(B, C))W (Hb(D)) = \frac{(q − 1)}{t^{A+1}} (q^{B+1} + \frac{1}{t^{C+1}} − \frac{q^{B+1}}{t^{C+1}} ) q^{D}
= \frac{(q − 1)q^{D}}{t^{A+1}} (q^{B+1} + \frac{1}{t^{C+1}} − \frac{q^{B+1}}{t^{C+1}} ) . (73)

In Case 2 of Figure 30, we have the sum of the weights of the colorings in this case is

\frac{−1}{t^{A+1}} q^{B+1}W (rbV (C))W (Hb(D)) = \frac{−q^{B+1}}{t^{A+1}} (q − 1) (1 − \frac{1}{t^{C+1}} ) q^{D}
= \frac{−(q − 1)q^{D}}{t^{A+1}} (q^{B+1} − \frac{q^{B+1}}{t^{C+1}} ) .  (74)

It is then easy to see that the sum of the weights of the colorings in Cases 1 and 2 is simply

\frac{(q − 1)q^{D}}{t^{A+1}} \frac{1}{t^{C+1}} = \frac{(q − 1)q^{D}}{t^{A+C+2}} .  (75)

In Case 3 of Figure 30, we have the sum of the weights of the colorings in this case is

W (rbV (A))W (Hrb(B))\frac{1}{t^{C+1}} q^{D}(q − 1) = \frac{(q − 1)}{t^{A+1}} \frac{(q^{B+1} − 1)}{(q − 1)}(q − 1)\frac{q^{D}}{t^{C+1}}
= \frac{(q − 1)q^{D}}{t^{A+C+2}} (q^{B+1} − 1).  (76)

Finally in case 4 of Figure 30, we have the sum of the weights of the colorings in this case is

\frac{−1}{t} \frac{1}{t^{A}} q^{B+1} \frac{1}{t^{C+1}} q^{D}(q − 1) = \frac{−(q − 1)q^{D}}{t^{A+C+2}} q^{B+1}.  (77)

It is then easy to see that the sum of the weights of the colorings in Cases 3 and 4 is simply

\frac{−(q − 1)q^{D}}{t^{A+C+2}} .  (78)

Figure 31. The connecting rim hook G_{1}

Thus comparing equations (75) and (78), we see that W (H) = 0 in this case as well. □

We note that Theorem 10 is important because it says that the coefficient of any s_{γ} in (10) such that γ has a red-blue connecting rim hook is 0. First, if γ is such that there is a red square which lies above a blue square, then the γ must have a red-blue connecting rim hook. Thus the the coefficient of s_{γ} in (10) is automatically 0. Hence there is no loss in restricting ourselves to γ that satisfies condition (∗). Moreover, it follows that there is no use in computing W (H) when H is either a blank-red or blue-blank connecting rim hook since any s_{γ} in (10) for which γ has either a blank-red or blue-blank connecting rim hook must also have red-blue connecting rim hook and, hence, the coefficient of s_{γ} in (10) is automatically 0. Thus, of the nine types of connecting rim hooks, we are left with computing W (H) when H is red-red, red-blank, or blue-red connecting rim hooks. In the next section, we shall compute W (H) for red-red and red-blank connecting rim hooks.

6. W (H) for red-red and red-blank connecting rim hooks.

The main goal of this section is to compute W (H) for red-red and red-blank connecting rim hooks. Our first step to prove a reduction lemma which is similar to Lemma 9 for those connecting rim hooks which start with a red square. We note that in such a case, we cannot have the next square of the connecting rim hook be immediately to the right of the red square for this would mean that there is blank square immediately to the right of the red square which is impossible. We want to consider the connecting rim hooks G_{1} and G_{2} pictured in Figures 31 and 32 respectively.

In Figure 31, we shall label the corner squares on the lower side of G_{1} by s, t, and w reading from bottom to top. In Figure 32, we shall label the corner squares on the lower side of G_{2} by u and v reading from bottom to top.

We shall refer to the portion of the connecting rim hook that lies to the right of the corner labeled s in Figure 31 as Rt(G_{1}, s) and the portion of the connecting rim hook that lies to the right of the corner labeled u in Figure 32 as Rt(G_{2}, u). Then shall assume that Rt(G_{1}, s) = Rt(G_{2}, u) and we allow the possibility that both Rt(G_{1}, s) and Rt(G_{2}, u) are empty. While we have drawn our pictures so that A ≠ 0, we also allow the possibility that A = 0.

Figure 32. The connecting rim hook G_{2}

Figure 33. Case 1 for G_{1}, s is blank

Lemma 11. If G_{1} and G_{2} are the connecting rim hooks pictured in Figures 31 and 32, respectively, and Rt(G_{1}, s) = Rt(G_{2}, u), then W (G_{1}) = W (G_{2}).

Proof. The proof of Lemma 11 is very similar to the proof of Lemma 9 so we shall suppress some of the details. We let A = q^{A+1}, B = t^{B+1}, C = q^{C+1}, D = t^{D+1} and E = q^{E+1}.

We shall organize our computation of W (G_{1}) and W (G_{2}) by first considering those colorings for which the square s and the square u are blank. In such a situation, we let U denote the sum of the weights over all possible colorings of Rt(G_{1}, s) = Rt(G_{2}, u) given that the cells s and u are blank. This given, we can then classify such colorings for H_{1} according to whether cells t and w are blank or red-blue. In the pictures, below we shall picture a red-blue cell as a filled cell. There are clearly four such cases.

In Case 1, we are assuming that t and w are blank, see Figure 33. Thus the sum P_{1} of the weights of the colorings in this case is

P_{1} = W (rV (A))W (INV L(B, C))W (INV L(D, E))U

= \frac{(q − 1)}{t^{A+1}} (q^{B+1} + \frac{1}{t^{C+1}} − \frac{q^{B+1}}{t^{C+1}} ) (q^{D+1} + \frac{1}{t^{E+1}} − \frac{q^{D+1}}{t^{E+1}} ) U

= \frac{(q − 1)}{A} (B + \frac{1}{C} − \frac{B}{C}) (D + \frac{1}{E} − \frac{D}{E}) U.  (79)

In Case 2, we are assuming that cell t is colored red-blue and that cell w is blank, see Figure 34. It follows that the cells directly above cell t and the cells directly to the right of cell t must be colored red-blue. It is easy to see from our definitions of w_{r,λ/μ}(c) and Figure 34. Case 2 for G_{1}, s is blank

Figure 35. Case 3 for G_{1}, s is blank

w_{b,λ/μ}(c) that the cells directly above cell t contribute a factor of \frac{1}{C} = \frac{1}{t^{C+1}} and cell t plus all the cells to the right of cell t except the last cell in its row contribute a factor of D = q^{D+1}. Note we consider the last cell in the row of cell t to be part of the rbV (E) connecting rim hook. Thus the sum P_{2} of the weights of the colorings in this case is

P_{2} = W (rV (A))W (Hrb(B))W (rbV (E))U \frac{D}{C}

= \frac{(q − 1)}{t^{A+1}}(q − 1)\frac{(q^{B+1} − 1)}{(q − 1)} (1 − \frac{1}{t^{E+1}} ) U \frac{D}{C}

= (q − 1)(B − 1) (1 − \frac{1}{E}) U \frac{D}{AC}.  (80)

In Case 3, we are assuming that cell w is colored red-blue and that cell t is blank, see Figure 35. It follows that the cells directly above cell w and the cells directly to the right of w must be colored red-blue. It is easy to see from our definitions of w_{r,λ/μ}(c) and w_{b,λ/μ}(c) that the cells directly above cell w contribute a factor of −\frac{1}{t^{A+1}} = −\frac{1}{A} and cell t plus all the cells to the right of cell t except the last cell in its row contribute a factor of q^{B+1} = B. Thus the sum P_{3} of the weights of the colorings in this case is

P_{3} = W (rbV (C))W (INV L(D, E))U(−1)\frac{B}{A}

= (q − 1) (1 − \frac{1}{t^{C+1}} ) (q^{D+1} + \frac{1}{t^{E+1}} − \frac{q^{D+1}}{t^{E+1}} ) U(−1)\frac{B}{A}

= −(q − 1) (1 − \frac{1}{C}) (D + \frac{1}{E} − \frac{D}{E}) U \frac{B}{A}.  (81)

Figure 36. Case 4 for G_{1}, s is blank

In Case 4, we are assuming that both cell t and cell w are colored red-blue, see Figure 36. Thus all the cells of G_{1} that lie either directly above or to the right of cells t and w must be colored red-blue. The product of the weights of such cells is −\frac{q^{B+1}q^{D+1}}{t^{A+1}t^{C+1}} = −\frac{BD}{AC}(q − 1). Thus the sum P_{4} of the weights of the colorings in this case

P_{4} = W (rbV (E))U(−1)\frac{BD}{AC}

= (q − 1) (1 − \frac{1}{t^{E+1}} ) U(−1)\frac{BD}{AC}

= −(q − 1) (1 − \frac{1}{E}) U \frac{BD}{AC}.  (82)

A little algebra will show that

P_{1} + P_{2} + P_{3} + P_{4} = (q − 1)\frac{1}{ACE}U.  (83)

Next we consider the cases for G_{1} where cell s is colored red-blue. This means that all the cells directly above or directly to the right of s must be colored red-blue. In particular, all the cells in the same column as s except for s itself contribute a factor of \frac{1}{E} = \frac{1}{t^{E+1}} to the weight. We let V denote the sum of the weights over all possible colorings of Rt(G_{1}, s) = Rt(G_{2}, u) given that the cells s and u are colored red-blue. Then we have four more cases to consider for G_{1}, depending on the colors of cells t and w.

In Case 5, we are assuming that t and w are blank, see Figure 37. Thus the sum P_{5} of the weights of the colorings in this case is

P_{5} = W (rV (A))W (INV L(B, C))W (Hrb(D))V \frac{1}{E}

= \frac{(q − 1)}{t^{A+1}} (q^{B+1} + \frac{1}{t^{C+1}} − \frac{q^{B+1}}{t^{C+1}} ) \frac{q^{D+1} − 1}{(q − 1)}V \frac{1}{E}

= (B + \frac{1}{C} − \frac{B}{C}) (D − 1)V \frac{1}{AE}.  (84)

In Case 6, we are assuming that cell t is colored red-blue and that cell w is blank, see Figure 38. It follows that the cells directly above cell t and the cells directly to the right of cell t must be colored red-blue. It is easy to see from our definitions of w_{r,λ/μ}(c) and w_{b,λ/μ}(c) that the cells directly above cell t contribute a factor of \frac{1}{t^{C+1}} = \frac{1}{C} and cell t Figure 37. Case 5 for G_{1}, s is colored red-blue

Figure 38. Case 6 for G_{1}, s is colored red-blue

plus all the cells to the right of cell t except the last cell in its row contribute a factor of q^{D+1} = D. Thus the sum P_{6} of the weights of the colorings in this case is

P_{6} = W (rV (A))W (Hrb(B))V \frac{D}{CE}

= \frac{(q − 1)}{t^{A+1}} \frac{(q^{B+1} − 1)}{(q − 1)}V \frac{D}{CE}

= (B − 1)\frac{D}{ACE}V.  (85)

In Case 7, we are assuming that cell w is colored red-blue and that cell t is blank, see Figure 39. It follows that the cells directly above cell w and the cells directly to the right of w must be colored red-blue. It is easy to see from our definitions of w_{r,λ/μ}(c) and w_{b,λ/μ}(c) that the cells directly above cell w contribute a factor of = −\frac{1}{t^{A+1}} = −\frac{1}{A} and cell w plus all the cells to the right of cell w except the last cell in its row contribute a factor of q^{B+1} = B. Thus the sum P_{7} of the weights of the colorings in this case is

P_{7} = W (rbV (C))W (Hrb(D))V (−1)\frac{B}{AE}

= −(q − 1) (1 − \frac{1}{t^{C+1}} ) \frac{(q^{D+1} − 1)}{(q − 1)}AV \frac{B}{AE}

= − (1 − \frac{1}{C}) (D − 1)V \frac{B}{AE}.  (86)

In Case 8, we are assuming that both cell t and cell w are colored red-blue, see Figure 40. Thus all the cells of G_{1} that lie either directly above or to the right of cells t and w Figure 39. Case 7 for G_{1}, s is colored red-blue

Figure 40. Case 8 for H_{1}, s is red-blue

must be colored red-blue. The product of the weights of such cells is −\frac{q^{B+1}q^{D+1}}{t^{A+1}t^{C+1}} = −\frac{BD}{AC}. Thus the sum P_{8} of the weights of the colorings in this case is

P_{8} = −V \frac{BD}{ACE}.  (87)

Then it is easy to check that

P_{5} + P_{6} + P_{7} + P_{8} = \frac{−1}{ACE}V  (88)

and, hence,

W (G_{1}) = \frac{(q − 1)}{ACE}U − \frac{1}{ACE}V.  (89)

We organize the computation of W (G_{2}) in the same way. That is, we first consider those colorings where cell u is blank. In this situation, there are two cases.

In Case I, we assume that cell v is blank, see Figure 41. Thus the sum Q_{1} of weights of the colorings in this case is

Q_{1} = W (rV (A + C + 1))W (INV L(B + D + 1, E))U

= \frac{(q − 1)}{t^{A+C+2}} (q^{B+D+2} + \frac{1}{t^{E+1}} − \frac{q^{B+D+2}}{t^{E+1}} ) U

= (q − 1)\frac{1}{AC} (BD + \frac{1}{E} − \frac{BD}{E}) U.  (90)

In Case II, we assume that v is colored red-blue, see Figure 42. Thus all the cells in the same row and column as u must be colored red-blue. These cells always contribute a Figure 41. Case I for G_{2}, u is blank

Figure 42. Case II for G_{2}, u is blank

factor of −\frac{q^{B+D+2}}{t^{A+C+2}} = −\frac{BD}{AC} to the weight of any coloring. Thus the sum Q_{2} of the weights of the possible colorings in this case is

Q_{2} = W (rbV (E))U(−1)\frac{BD}{AC}

= −(q − 1) (1 − \frac{1}{t^{E+1}} ) U \frac{BD}{AC}

= −(q − 1) (1 − \frac{1}{E}) U \frac{BD}{AC}.  (91)

Then it is easy to check that Q_{1} + Q_{2} = (q − 1)\frac{1}{ACE}U.

Next we consider the case where u is colored red-blue. Then all the cells in the same row or column as u must be colored red-blue. The factor that all the cells in the same column as u contributes to the weights of the colorings in this situation is \frac{1}{t^{E+1}} = \frac{1}{E}. Again there are two cases depending on the color of v.

In Case III, we assume that cell v is blank, see Figure 43. Thus the sum Q_{3} of the weights of the colorings in this case is

Q_{3} = W (rV (A + C + 1))W (Hrb(B + D + 1))V \frac{1}{E}

= \frac{(q − 1)}{t^{A+C+2}} \frac{(q^{B+D+2} − 1)}{(q − 1)}V \frac{1}{E}

= (BD − 1)V \frac{1}{ACE}.  (92)

Figure 43. Case III for G_{2}, u is red-blue

Figure 44. Case IV for G_{2}, u is red-blue

In Case IV, we assume that v is colored red-blue, see Figure 44. In this case, the sum Q_{4} of the weights of the coloring is

Q_{4} = q^{B+D+2} \frac{1}{t^{A+C+2}} V \frac{1}{E} = −\frac{BD}{ACE}V.  (93)

Then it is easy to check that

Q_{3} + Q_{4} = \frac{−1}{ACE}V.

so that

W (H_{2}) = \frac{(q − 1)}{ACE}U − \frac{1}{ACE}V.  (94)

Thus comparing (89) and (94), we see that W (G_{1}) = W (G_{2}) as claimed. □

We now are in position to prove the main result of this section.

Theorem 12. (1) If H is a red-red connecting rim hook, then W (H) = \frac{(q−t)}{t^{r(h)}}. (2) If H is a red-blank connecting rim hook, then W (H) = \frac{(q−1)}{t^{r(h)}}.

Proof. We shall prove only (1) since the proof of (2) is similar. It follows from Lemma 11 that we need only consider the connecting rim hooks H where there are either one or two lower corner squares.

Let us first consider the case where the red-red connecting rim hook H has one lower corner square. There are two basic cases, namely, the case where the corner square is blank and the corner square is colored red-blue, see Figure 45.

Figure 45. Red-red 1 lower corner shapes

Figure 46. Red-red 2 lower corner shapes

If the corner square is blank, then it is easy to see that sum of the weights of the possible colorings is

W (rV (A))W (Hr(B)) = \frac{(q − 1)}{t^{A+1}} \frac{(q − t) + (t − 1)q^{B+1}}{t(q − 1)} = \frac{(q − t) + (t − 1)q^{B+1}}{t^{A+2}} .

If the corner cell is colored red-blue, then top red cell has weight \frac{−1}{t} and the remaining A cells in the vertical part each contribute a weight \frac{−1}{t}(−1) = \frac{1}{t}. Each cell in the bottom row except for the cell that immediately precedes the red cell, contributes a weight of \frac{q}{t}t = q. The cell that immediately precedes the red cell contributes a weight of \frac{q}{t}(t − 1) = \frac{(t−1)q}{t}. Thus the weight corresponding to this configuration is −\frac{(t−1)q^{B+1}}{t^{A+2}} . Hence W (H) = \frac{q−t}{t^{A+2}} = \frac{(q−t)}{t^{r(H)}} in this case.

Next we consider the case where the red-red connecting rim hook has two corner squares. Thus there are four cases depending on whether the two lower corner squares are colored red-blue or blank as pictured in Figure 46.

In Case 1 of Figure 46, we have the sum of the weights of the colorings in this case is

W (rV (A))W (INV T L(B, C))W (Hr(D))  (95)

= \frac{(q − 1)}{t^{A+1}} (q^{B+1} + \frac{1}{t^{C+1}} − \frac{q^{B+1}}{t^{C+1}} ) \frac{(q − t) + (t − 1)q^{D+1}}{t(q − 1)}

= \frac{(q^{B+1}t^{C+1} + 1 − q^{B+1})((q − t) + (t − 1)q^{D+1})}{t^{A+C+3}}.  (96)

In Case 2 of Figure 46, we have the sum of the weights of the colorings in this case is

\frac{−1}{t^{A+1}} q^{B+1}W (rbV (C))W (Hr(D)) = \frac{−q^{B+1}}{t^{A+1}} (q − 1) (1 − \frac{1}{t^{C+1}} ) \frac{(q − t) + (t − 1)q^{D+1}}{t(q − 1)}
= \frac{−q^{B+1}(t^{C+1} − 1)((q − t) + (t − 1)q^{D+1})}{t^{A+C+3}}.  (97)

It is then easy to see that the sum of the weights of the colorings in Cases 1 and 2 is simply

\frac{(q − t) + (t − 1)q^{D+1}}{t^{A+C+3}} .  (98)

In Case 3 of Figure 46, we have the sum of the weights of the colorings in this case is

W (rV (A))W (Hrb(B))\frac{1}{t^{C+1}} q^{D} \frac{q(t − 1)}{t} = \frac{(q − 1)}{t^{A+1}} \frac{(q^{B+1} − 1)}{(q − 1)} \frac{1}{t^{C+1}} q^{D} \frac{q(t − 1)}{t}
= \frac{(t − 1)(q^{B+1} − 1)q^{D+1}}{t^{A+C+3}} .  (99)

Finally in case 4 of Figure 46, we have the sum of the weights of the colorings in this case is

\frac{−1}{t} \frac{1}{t^{A}} q^{B+1} \frac{1}{t^{C+1}} q^{D} \frac{q(t − 1)}{t} = \frac{−(t − 1)q^{D+1}q^{B+1}}{t^{A+C+3}} .  (100)

It is then easy to see that the sum of the weights of the colorings in Cases 3 and 4 is simply

\frac{−(t − 1)q^{D+1}}{t^{A+C+2}} .  (101)

Thus comparing equations (98) and (101), we see that W (H) = \frac{(q−t)}{t^{A+C+3}} = \frac{(q−t)}{t^{r(H)}} in this case as well. □

At this point, to complete our calculation, we need only compute the weights of blue-red connecting rim hooks.

7. W (H) for blue-red connecting rim hooks.

In this section, we shall compute W (H) when H is a blue-red connecting rim hook. As one might expect from the formula given in section 1, this is the most involved computation for the weights of connecting rim hooks.

We start with the case when H has one lower corner, see Figure 47.

Figure 47. Blue-red 1 lower corner shape

Theorem 13. If H is a blue-red connecting rim hook with one lower corner, then

W (H) = \frac{(q − t)(t − 1)}{(q − 1)t} (\frac{[r(H) − 1]_{t} − q[r(H) − 2]}{t^{r(H)−2}} − q^{c(H)}) .  (102)

Proof. We shall consider two cases. First suppose that the corner cell is blank. Then the sum of the weights of the colorings in this case is

W (bV (A))W (Hr(B))

= ((t − q) + \frac{(q − 1)}{t^{A}}) \frac{((q − t) + (t − 1)q^{B+1})}{t(q − 1)}

= \frac{((q − 1) − (q − t)t^{A})((q − t) + (t − 1)q^{B+1})}{(q − 1)t^{A+1}}

= \frac{((q − 1)(q − t) + (q − 1)(t − 1)q^{B+1}t^{A} − (q − t)^{2}t^{A} − (q − t)(t − 1)q^{B+1}t^{A})}{(q − 1)t^{A+1}}. (103)

If the corner square is colored red-blue, then all the squares except the top blue square and the bottom red square must be colored red-blue so that the weight of this configuration is

(−1)\frac{1}{t^{A}} q^{B} \frac{q(t − 1)}{t} = \frac{−((q − 1)(t − 1)q^{B+1}t^{A})}{(q − 1)t^{A+1}}.  (104)

Combining (103) and (104), we see that

W (H) = \frac{1}{(q − 1)t^{A+1}} ((q − 1)(q − t) − (q − t)^{2}t^{A} − (q − t)(t − 1)q^{B+1}t^{A})

= \frac{(q − t)}{(q − 1)t^{A+1}} ((q − 1) − (q − t)t^{A} − (t − 1)q^{B+1}t^{A})

= \frac{(q − t)(t − 1)}{(q − 1)t} (\frac{(q − 1) − (q − t)t^{A}}{t^{A}(t − 1)} − q^{B+1})

= \frac{(q − t)(t − 1)}{(q − 1)t} (\frac{(t^{A+1} − 1) − q(t^{A} − 1)}{(t − 1)t^{A}} − q^{B+1})

= \frac{(q − t)(t − 1)}{(q − 1)t} (\frac{[r(H) − 1]_{t} − q[r(H) − 2]_{t}}{t^{r(H)−2}} − q^{c(H)}) .

□

Figure 48. Blue-red 2 lower corners shape

Now we consider the general case.

Theorem 14. Let H be a blue-red rim hook with at least two lower corners and suppose that α is the smallest partition which contains H and β is the partition that results by removing the first row and column from α. Then

W (H) = \frac{(q − t)(t − 1)}{(q − 1)t} (\frac{[r(H) − 1]_{t} − q[r(H) − 2]}{t^{r(H)−2}} − q^{c(H)} − (q − t) ∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}} − 1}{t^{i}} ) .

(105)

Proof. We first consider the case where the blue-red connecting rim hook has exactly two corner squares. Thus there are four cases depending on whether the two lower corner squares are colored red-blue or blank as pictured in Figure 48. We let A = t^{A}, B = q^{B+1}, C = t^{C+1}, and D = q^{D+1}.

In Case 1 of Figure 48, we have the sum of the weights of the colorings in this case is

W (bV (A))W (INV T L(B, C))W (Hr(D))

= ((t − q) + \frac{q − 1}{t^{A}}) (q^{B+1} + \frac{1}{t^{C+1}} − \frac{q^{B+1}}{t^{C+1}} ) \frac{(q − t) + (t − 1)q^{D+1}}{t(q − 1)}

= \frac{((q − 1) − (q − t)t^{A})}{t^{A}} \frac{(q^{B+1}t^{C+1} + 1 − q^{B+1})}{t^{C+1}} \frac{((q − t) + (t − 1)q^{D+1})}{t(q − 1)}

= \frac{(q − t) + (t − 1)D}{t(q − 1)AC}((q − 1) − (q − t)A)(BC + 1 − B).  (106)

THE COMBINATORICS OF MACDONALD’S D_{n}^{1} OPERATOR 45

In Case 2 of Figure 48, we have the sum of the weights of the colorings in this case is

(−1)\frac{1}{t^{A}} q^{B+1}W (rbV (C))W (Hr(D))

= \frac{−q^{B+1}}{t^{A}} (q − 1) (1 − \frac{1}{t^{C+1}} ) \frac{(q − t) + (t − 1)q^{D+1}}{t(q − 1)}

= \frac{−q^{B+1}}{t^{A}} \frac{((q − 1)t^{C+1} − (q − 1))}{t^{C+1}} \frac{((q − t) + (t − 1)q^{D+1})}{t(q − 1)}

= −\frac{(q − t) + (t − 1)D}{t(q − 1)AC}((q − 1)BC − (q − 1)B).  (107)

Since ((q − 1) − (q − t)A)(BC + 1 − B))

= (q − 1)BC + (q − 1) − (q − 1)B − (q − t)ABC − (q − t)A + (q − t)AB,

it is easy to see that sum of the weights of the coloring in Cases 1 and 2 is

\frac{(q − t) + (t − 1)D}{(t(q − 1)AC}((q − 1) − (q − t)ABC − (q − t)A + (q − t)AB).  (108)

In Case 3 of Figure 48, we have the sum of the weights of the colorings in this case is

W (bV (A))W (Hrb(B))\frac{1}{t^{C+1}} q^{D} \frac{q(t − 1)}{t}

= ((t − q) + \frac{q − 1}{t^{A}}) \frac{(q^{B+1} − 1)}{(q − 1)} \frac{q^{D+1}(t − 1)}{t^{C+2}}

= \frac{((q − 1) − (q − t)t^{A})}{t^{A}} \frac{(q^{B+1} − 1)}{(q − 1)} \frac{q^{D+1}(t − 1)}{t^{C+2}}

= \frac{(t − 1)D}{t(q − 1)AC}((q − 1) − (q − t)A)(B − 1)

= \frac{((q − 1)(t − 1)BD − (q − 1)(t − 1)D − (q − t)(t − 1)ABD + (q − t)(t − 1)AD)}{t(q − 1)AC}.

(109)

Finally in Case 4 of Figure 48, we have the sum of the weights of the colorings in this case is

(−1)\frac{1}{t^{A}} q^{B+1} \frac{1}{t^{C+1}} q^{D} \frac{q(t − 1)}{t} = \frac{−1}{t(q − 1)AC}((q − 1)(t − 1)BD).  (110)

It is then easy to see that the sum of the weights of the colorings in Cases 3 and 4 is simply

\frac{1}{t(q − 1)AC}((q − t)(t − 1)AD − (q − 1)(t − 1)D − (q − t)(t − 1)ABD).  (111)

46 JEFFREY REMMEL

If we factor out the common factor of \frac{1}{t(q−1)AC} in (108) and (111), we are left with

(q − t)(q − 1) − (q − t)^{2}ABC − (q − t)^{2}A + (q − t)^{2}AB)

+ ((q − 1)(t − 1)D − (q − t)(t − 1)ABCD − (q − t)(t − 1)AD + (q − t)(t − 1)ABD)

+ (q − t)(t − 1)AD − (q − 1)(t − 1)D − (q − t)(t − 1)ABD

= (q − t)(q − 1) − (q − t)^{2}ABC − (q − t)^{2}A + (q − t)^{2}AB) − (q − t)(t − 1)ABCD. It follows that

W (H) = \frac{(q − t)}{t(q − 1)} (\frac{(q − 1)}{AC} − (q − t)\frac{(ABC + A − AB)}{AC} − (t − 1)BD)

= \frac{(q − t)}{t(q − 1)} (\frac{(q − 1)}{AC} − (q − t) (B + \frac{1}{C} − \frac{B}{C}) − (t − 1)BD) .

In this case β = (B + 1)^{C+1} and the border of β, B_{β} is equal to INV L(B, C). Note that by Theorem 4 and Lemma 8, we have that

W (B_{β}) = 1 + (t − 1) ∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}} − 1}{t^{i}}

= 1 + (t − 1) ∑_{i=1}^{C+1} \frac{q^{B+1} − 1}{t^{i}}

= q^{B+1} + \frac{1}{t^{C+1}} − \frac{q^{B+1} − 1}{t^{C+1}}

= 1 + (q^{B+1} − 1)(t − 1) ∑_{i=1}^{C+1} \frac{1}{t^{i}}

= 1 + (q^{B+1} − 1)(1 − \frac{1}{t^{C+1}} )

= (B + \frac{1}{C} − \frac{B}{C}) .  (112)

It follows that

W (H) = \frac{(q − t)}{t(q − 1)} (\frac{(q − 1)}{AC} − (q − t) (B + \frac{1}{C} − \frac{B}{C}) − (t − 1)BD)

= \frac{(q − t)}{t(q − 1)} (\frac{(q − 1)}{AC} − (q − t)\frac{AC}{AC} − (q − t)(t − 1) (∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}} − 1}{t^{i}} ) − (t − 1)BD)

= \frac{(q − t)(t − 1)}{t(q − 1)} (\frac{(tAC − 1) − q(AC − 1)}{(t − 1)AC} − (q − t) (∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}} − 1}{t^{i}} ) − BD) .

Figure 49. Blue-red ≥ 3 lower corners shape

Note that tAC = t^{A+C+2} = t^{r(H)−1}, AC = t^{r(H)−2}, and BC = q^{B+C+2} = q^{c(H)}. Thus it follows that

W (H) = \frac{(q − t)(t − 1)}{t(q − 1)} (\frac{t^{r(H)−1} − 1}{(t − 1)t^{r(H)−1}} − \frac{q(t^{r(H)−2} − 1)}{(t − 1)t^{r(H)−1}} − q^{c(H)} − (q − t) ∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}} − 1}{t^{i}} )

= \frac{(q − t)(t − 1)}{t(q − 1)} (\frac{[r(H) − 1]_{t} − q[r(H) − 2]_{t}}{t^{r(H)−1}} − q^{c(H)} − (q − t) ∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}} − 1}{t^{i}} )

which is what we wanted to prove.

Finally we consider the case where H has 3 or more lower corner squares. Again we shall let α be the smallest partition that contains H and β be the partition whose diagram is the result of removing the first row and column of α. We let u denote the top lower corner of H and v denote the bottom lower corner of H. We let B_{β} denote the border of β, a denote the first cell of B_{β}, and b denote the last cell of B_{β}. See Figure 49. We let B_{β}^{a} denote the connecting rim hook which results from B_{β} by coloring cell a red-blue. We let B_{β}^{b} denote the connecting rim hook which results from B_{β} by first removing the vertical portion corresponding to C at the bottom of diagram and then coloring the cell at the top of column that contains b red-blue. Note, in this case, we do not consider the top cell in the column above b to be part of B_{β}^{b}. Finally we let B_{β}^{ab} denote the connecting rim hook which results from B_{β}^{b} by coloring the cell a red-blue. Again, in this case, we do consider the cell that is at the top of the column that contains b to be part of B_{β}^{ab}.

We consider 4 cases depending on whether cells u and v are colored red-blue. In fact, we shall also need to consider similar cases for two other connecting rim hooks derived from H, namely, bbH which is the same as H except that the bottom cell is colored blue instead of red and rH/row1 which is same as H except that the top cell is red instead of blue and the first row is removed. See Figure 50.

Case 1. Both u and v are blank. See Figure 51.

Figure 50. The shapes bbH and rH/row1

Figure 51. Blue-red ≥ 3 lower corners shape: Case 1

We shall refer to the sum of the weights of all the colorings in this case as W (H(1)). Similarly, we shall refer to the similar sum of the weights of coloring for bbH and rH/row1 as W (bbH(1)) and W (rH/row1(1)) respectively. Then it is easy to see that

W (H(1)) = W (bV (A))W (B_{β})W (Hr(D))
= ((t − q) + \frac{(q − 1)}{t^{A}}) (\frac{(q − t) + (t − 1)q^{D+1}}{t(q − 1)} ) W (B_{β}).  (113)

and

W (bbH(1)) = W (bV (A))W (B_{β})W (Hb(D))
= ((t − q) + \frac{(q − 1)}{t^{A}}) q^{D}W (B_{β}).  (114)

Similarly,

W (rH/row(1)) = W (rV (A))W (B_{β})
= \frac{(q − 1)}{t^{A+1}}W (B_{β}).  (115)

Figure 52. Blue-red ≥ 3 lower corners shape: Case 2

Note that

((t − q) + \frac{(q − 1)}{t^{A}}) (\frac{(q − t) + (t − 1)q^{D+1}}{t(q − 1)} )

= ((t − q) + \frac{(q − 1)}{t^{A}}) (\frac{t(q − 1) − q(t − 1) + (t − 1)q^{D+1}}{t(q − 1)} )

= ((t − q) + \frac{(q − 1)}{t^{A}}) (1 + \frac{q(t − 1)(q^{D} − 1)}{t(q − 1)})

= ((t − q) + \frac{(q − 1)}{t^{A}}) (\frac{q(t − 1)}{t(q − 1)}q^{D} + 1 − \frac{q(t − 1)}{t(q − 1)})

= \frac{q(t − 1)}{t(q − 1)} ((t − q) + \frac{(q − 1)}{t^{A}}) q^{D} + (1 − \frac{q(t − 1)}{t(q − 1)}) ((t − q) + \frac{(q − 1)}{t^{A}})

= \frac{q(t − 1)}{t(q − 1)} ((t − q) + \frac{(q − 1)}{t^{A}}) q^{D}

+ t (1 − \frac{q(t − 1)}{t(q − 1)}) \frac{(q − 1)}{t^{A+1}} + (t − q) (1 − \frac{q(t − 1)}{t(q − 1)}) .

It then follows that

W (H(1)) = \frac{q(t − 1)}{t(q − 1)}W (bbH(1))

+ t (1 − \frac{q(t − 1)}{t(q − 1)}) W (rH/row1(1)) + (t − q) (1 − \frac{q(t − 1)}{t(q − 1)}) W (B_{β}). (116)

Case 2. Cell u is colored red-blue and v are blank. See Figure 52.

We shall refer the sum of the weights of all the colorings in this case as W (H(2)). Similarly, we shall refer to the similar sum of the weights of coloring for bbH and rH/row1 as W (bbH(2)) and W (rH/row1(2)) respectively. Then it is easy to see that

W (H(2)) = (−1)\frac{1}{t^{A}} q^{B+1}W (B_{β}^{a})W (Hr(D))
= \frac{−q^{B+1}}{t^{A}} (\frac{(q − t) + (t − 1)q^{D+1}}{t(q − 1)} ) W (B_{β}^{a})  (117)

and

W (bbH(1)) = (−1)\frac{1}{t^{A}} q^{B+1}W (B_{β}^{a})W (Hb(D))
= \frac{−q^{B+1}}{t^{A}} ((t − q) + \frac{(q − 1)}{t^{A}}) q^{D}W (B_{β}^{a}).  (118)

Similarly,

W (rH/row(1)) = \frac{−1}{t} \frac{1}{t^{A}} q^{B+1}W (B_{β}^{a})
= \frac{−q^{B+1}}{t^{A+1}} W (B_{β}^{a}).  (119)

Next observe that

(\frac{(q − t) + (t − 1)q^{D+1}}{t(q − 1)} ) = (\frac{t(q − 1) − q(t − 1) + (t − 1)q^{D+1}}{t(q − 1)} )

= (1 + \frac{q(t − 1)(q^{D} − 1)}{t(q − 1)})

= \frac{q(t − 1)}{t(q − 1)}q^{D} + (1 − \frac{q(t − 1)}{t(q − 1)}).

It then follows that

W (H(2)) = \frac{q(t − 1)}{t(q − 1)}W (bbH(2)) + t (1 − \frac{q(t − 1)}{t(q − 1)}) W (rH/row1(2)).  (120)

By part 2 of Theorem 12,

\frac{(q − 1)}{t^{r(rH/row1)}} = W (rH/row1) = W (rH/row1(1)) + W (rH/row1(2)).

Since r(rH/row1) = r(H) − 1, we get that

W (H(1)) + W (H(2)) = \frac{q(t − 1)}{t(q − 1)}(W (bbH(1)) + W (bb(H(2))))

+ t (1 − \frac{q(t − 1)}{t(q − 1)}) \frac{(q − 1)}{t^{r(H)−1}} + (t − q) (1 − \frac{q(t − 1)}{t(q − 1)}) W (B_{β}). (121)

Case 3. Cell u is blank and cell v is red-blue. See Figure 53.

We shall refer to the sum of the weights of all the colorings in this case as W (H(3)). Similarly, we shall refer to the similar sum of the weights of coloring for bbH as W (bbH(3)). Then it is easy to see that

W (H(3)) = W (bV (A))W (B_{β}^{b})\frac{1}{t^{C+1}} q^{D} \frac{q(t − 1)}{t}
= ((t − q) + \frac{(q − 1)}{t^{A}}) (\frac{q^{D+1}(t − 1)}{t^{C+2}}) W (B_{β}^{b}).  (122)

Figure 53. Blue-red ≥ 3 lower corners shape: Case 3

Figure 54. Blue-red ≥ 3 lower corners shape: Case 4

and

W (bbH(3)) = W (bV (A))W (B_{β}^{b})\frac{1}{t^{C+1}} q^{D}(q − 1)
= ((t − q) + \frac{(q − 1)}{t^{A}}) \frac{t(q − 1)q^{D}}{t^{C+2}} W (B_{β}^{b}).  (123)

Thus

W (H(3)) = \frac{q(t − 1)}{t(q − 1)}W (bbH(3)).  (124)

Case 4. Both u and v are red-blue. See Figure 54.

We shall refer to the sum of the weights of all the colorings in this case as W (H(4)). Similarly, we shall refer to the similar sum of the weights of coloring for bbH as W (bbH(4)). Then it is easy to see that

W (H(4)) = (−1)\frac{1}{t^{A}} q^{B+1}W (B_{β}^{ab})\frac{1}{t^{C+1}} q^{D} \frac{q((t − 1)}{t}.  (125)

and

W (bbH(4)) = (−1)\frac{1}{t^{A}} q^{B+1}W (B_{β}^{ab})\frac{1}{t^{C+1}} q^{D}(q − 1).  (126)

Thus again we have

W (H(4)) = \frac{q(t − 1)}{t(q − 1)}W (bbH(4)).  (127)

By part 3 of Theorem 10,

W (bbH(1)) + W (bbH(2)) + W (bbH(3)) + W (bbH(4)) = W (bbH) = (t − q)q^{c(H)−1}.

52 JEFFREY REMMEL

Thus

W (H) = W (H(1)) + W (H(2)) + W (H(3)) + W (H(4))

= \frac{q(t − 1)}{t(q − 1)}W (bbH) + t (1 − \frac{q(t − 1)}{t(q − 1)}) \frac{(q − 1)}{t^{r(H)−1}} + (t − q) (1 − \frac{q(t − 1)}{t(q − 1)}) W (B_{β})

= \frac{q(t − 1)}{t(q − 1)}((t − q)q^{c(H)−1}) + t (1 − \frac{q(t − 1)}{t(q − 1)}) \frac{(q − 1)}{t^{r(H)−1}}

+ (t − q) (1 − \frac{q(t − 1)}{t(q − 1)}) W (B_{β}).  (128)

Using the fact that

1 − \frac{q(t − 1)}{t(q − 1)} = \frac{t(q − 1) − q(t − 1)}{t(q − 1)} = \frac{(q − t)}{t(q − 1)},

we see that

W (H) = −\frac{(q − t)(t − 1)}{t(q − 1)}q^{c(H)} + \frac{(q − t)}{t^{r(H)−1}} − \frac{(q − t)^{2}}{t(q − 1)}W (B_{β}).

Since W (B_{β}) = 1 + (t − 1) ∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}}−1}{t^{i}}, it follows that

W (H) = \frac{(q − t)(t − 1)}{t(q − 1)} (\frac{(q − 1)}{(t − 1)t^{r(H)−2}} − q^{c(H)} − \frac{(q − t)}{(t − 1)} − (q − t) ∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}} − 1}{t^{i}} ) .

Finally using the fact that

\frac{(q − 1)}{(t − 1)t^{r(H)−2}} − \frac{(q − t)}{(t − 1)} = \frac{(q − 1) − (q − t)t^{r(H)−2}}{(t − 1)t^{r(H)−2}}

= \frac{(t^{r(H)−1} − 1) − q(t^{r(H)−2} − 1)}{(t − 1)t^{r(H)−2}}

= \frac{[r(H) − 1]_{t} − q[r(H) − 2]_{t}}{t^{r(H)−2}} ,

we see that

W (H) = \frac{(q − t)(t − 1)}{t((q − 1)} (\frac{[r(H) − 1]_{t} − q[r(H) − 2]_{t}}{t^{r(H)−2}} − q^{c(H)} − (q − t) ∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}} − 1}{t^{i}}.)

(129)

as claimed.

□

8. Conclusion

In this paper, we have proved the following theorem. Theorem 15. Suppose that λ = (λ_{1} ≥ ⋯ ≥ λ_{n}) is a partition of n. Then

D_{n}^{1}(s_{λ}(x_{1}, …, x_{n})) = ∑_{γ⊢n} d_{λ,γ}(q, t)s_{γ}(x_{1}, …, x_{n})  (130)

where

(a): d_{λ,λ} = ∑_{i=1}^{n} t^{n−i}q^{λ_{i}}, (b): d_{λ,γ} = 0 unless γ satisfies (*) where

(*) γ arises from λ by first removing a broken rim hook R of λ from λ to get a partition μ and then adding a broken rim hook B of γ on the outside of μ to obtain obtain γ so that rows occupied by B lie strictly above the rows occupied by R and |B| = |R|.

(c): If γ satisfies (*), we let D be the diagram consisting of the squares of λ ∪ γ and we color the squares of R with red and the squares of B with blue. We then let H_{1}, …, H_{m} be the connecting rim hooks determined by λ and γ, B = {b_{1}, …, b_{p}} be the blue squares which are not part of any connecting rim hook, and R = {r_{1}, …, r_{q}} be the red squares which are not part of any connecting rim hook. Then

d_{λ,γ}(q, t) = \frac{t^{n}}{(t − 1)} (∏_{i=1}^{m} W (H_{i})) (∏_{j=1}^{p} w_{b}(b_{j})) (∏_{k=1}^{q} w_{r}(r_{k}))  (131)

where for any square s ∈ B ∪ R,

w_{b}(s) = \begin{cases}t & if s has a blue square in D to its right, \\ −1 & if s has a blue square in D below it, \\ (t − 1) & otherwise, \end{cases}  (132)

w_{r}(s) = \begin{cases}\frac{q}{t} & if s has a red square in D to its right, \\ \frac{−1}{t} & if s has a red square in D below it, \\ \frac{(q−1)}{t} & otherwise, \end{cases}  (133)

and for connecting rim hook H_{i},

(1) W (H_{i}) = q^{c(H_{i})} if H_{i} is a blank-blue connecting rim hook,

(2) W (H_{i}) = (t − q)q^{c(H_{i})−1}, if H_{i} is a blue-blue connecting rim hook,

(3) W (H_{i}) = \frac{(q−t)}{t^{r(H_{i})}} if H_{i} is a red-red connecting rim hook,

(4) W (H_{i}) = \frac{(q−1)}{t^{r(H_{i})}} if H_{i} is a red-blank connecting rim hook, and

(5) W (H_{i}) = \frac{(t−1)(q−t)}{t(q−1)} (\frac{[r(H)−1]_{t}−q[r(H)−2]_{t}}{t^{r(H)−2}} − q^{c(H)} − (q − t) ∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}}−1}{t^{i}}) if H_{i} is a blue-red connecting rim hook and β is the partition whose diagram results by removing the first row and column of the smallest shape α which contains H_{i} and by definition, the sum ∑_{i=1}^{ℓ(β)} \frac{q^{β_{i}}−1}{t^{i}} is equal to 0 if β is empty.

For example, suppose that λ = (2^{2}, 1). Then the two γ that satisfy condition (*) for λ are pictured in Figure 55 along with the corresponding connecting rim hooks H_{i}, blue squares b_{j} and red squares r_{k}. Note that as usual, we do not consider the red square at the bottom of H_{1} to be part of H_{1}.

Figure 55. The γ for λ = (2^{2}, 1)

Note by Theorem 15, d_{(2^{2},1),(2^{2},1)}(q, t) = t^{4}q^{2} + t^{3}q^{2} + t^{2}q + t + 1. For γ = (2, 1^{3}), we have

W (H_{1}) = \frac{(t − 1)(q − t)}{t(q − 1)} (\frac{[3 − 1]_{t} − q[3 − 2]_{t}}{t^{3−2}} − q)

= \frac{(t − 1)(q − t)}{t(q − 1)} (\frac{1 + t − q}{t} − q)

= \frac{(t − 1)(q − t)}{t(q − 1)} \frac{1 + t − q − qt}{t}

= \frac{(t − 1)(q − t)}{t(q − 1)} \frac{(q − 1)(t + 1)}{t}

= \frac{(t − 1)(q − t)(t + 1)}{t^{2}}

and W (H_{2}) = \frac{(q−1)}{t^{2}} so that

d_{(2^{2},1),(2,1^{3})}(q, t) = \frac{t^{5}}{(t − 1)} \frac{(t − 1)(q − t)(t + 1)}{t^{2}} \frac{(q − 1)}{t^{2}}
= t(q − t)(t + 1)(q − 1).

For γ = (1^{5}), we have w_{b}(b_{1}) = −1, w_{r}(r_{1}) = \frac{−1}{t}, w_{r}(r_{2}) = \frac{(q−1)}{t}, and W (H_{1}) = \frac{(t−1)(q−t)(t+1)}{t^{2}} as above. Thus

d_{(2^{2},1),(1^{5})}(q, t) = \frac{t^{5}}{(t − 1)}(−1)\frac{−1}{t} \frac{(q − 1)}{t} \frac{(t − 1)(q − t)(t + 1)}{t^{2}}
= t(q − t)(t + 1)(q − 1).

Finally, we should note that Macdonald [5] defined a whole sequence of operators D_{n}^{i} via the equation

D_{n}(X; q, t) = ∑_{i=1}^{n} D_{n}^{i}X^{i} = \frac{1}{Δ(x_{1}, …, x_{n})} ∑_{w∈S_{n}} ϵ(w)x^{wδ} ∏_{i=1}^{n}(1 + Xt^{(wδ)_{i}}T_{q}^{(i)})  (134)

where X is another indeterminate, δ = (n − 1, n − 2, …, 1, 0), Δ(x_{1}, …, x_{n}) is the Vandermonde determinant, x^{(p_{1},...,p_{n})} = x_{1}^{p_{1}} ⋯ x_{n}^{p_{n}}, ϵ(w) is the sign of w, and (wδ)_{i} is the i-th component of wδ. A λ-ring expression for D_{n}^{i} can be found in [1], but we have not tried of find a combinatorial description of the coefficients that arise in Schur function expansion of D_{n}^{i}(s_{λ}(x_{1}, …, x_{n})) for i ≥ 2.

References

[1] Bergeron, F., Garsia, A.M., Haiman, M. and Tesler, G., Identities and positivity conjectures for some remarkable operators in the theory of symmetric functions, Methods Appl. Analysis 6, (1999), 363–420.

[2] Garsia, A. and Haiman, M., A remarkable q, t-Catalan sequence and q-Lagrange inversion, J. Algebraic Combin. 5, no.3, (1996), 191–244.

[3] Knutson, D., λ-rings and the representation theory of the symmetric group, Lecture Notes in Mathematics, Vol. 308, Springer–Verlag, Berlin, (1973).

[4] Macdonald, I.G., A new class of symmetric functions, Actes du 20^{e} Séminaire Lotharingien de Combinatoire, Publ.I.R.M.A. Strasbourg 372/S-20 (1988), 131–171; Séminaire Lotharingien Combin. 20, (1988), Article B20a, 41 pp.

[5] Macdonald, I. G., Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, Clarendon Press, New York, (1995).

[6] Mendes, A., Remmel, J.B. and Wagner, J., A λ-ring Frobenius characteristic for wreath products G ≀ S_{n}, Electron. J. Combin. 11, no. 1, (2004), Article #R56, 33 pp.