Identities for classical group characters of nearly rectangular shape

C. Krattenthaler^{†}

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: KRATT@Pap.Univie.Ac.At

           WWW: http://radon.mat.univie.ac.at/People/kratt

Abstract. We derive several identities that feature irreducible characters of the general linear, the symplectic, the orthogonal, and the special orthogonal groups. All the identities feature characters that are indexed by shapes that are “nearly” rectangular, by which we mean that the shapes are rectangles except for one row or column that might be shorter than the others. As applications we prove new results in plane partitions and tableaux enumeration, including new refinements of the Bender-Knuth and MacMahon (ex-)conjectures.

1. Introduction. We prove identities that set into relation irreducible characters of classical Lie groups. All of them feature a classical group character indexed by a “nearly” rectangular shape. What is remarkable about these identities is that they have simple explicit forms (as opposed to many, however more general, identities in the literature), and that many of them exhibit multiplicity-free expansions, typically featuring sums of characters indexed by shapes that have a fixed number of rows or columns of odd length.

There are three types of identities that we consider.

First, in Theorem 1, we express (irreducible) characters of the general linear group GL(N) (these characters are also known as Schur functions) of “nearly” rectangular shape in terms of (irreducible) characters of the symplectic group Sp(N), and in terms of (irreducible) characters of the orthogonal group O(N). As may be expected, for the proofs of these identities we utilize Littlewood’s [25] branching rules for restricting representations of the general linear groups to representations of the symplectic or orthogonal groups.

1991 Mathematics Subject Classification. Primary 20G05; Secondary 05E05, 05E10, 05E15, 20C15, 22E45.

Key words and phrases. Schur functions, general linear characters, symplectic characters, orthogonal characters, characters of Lie groups, tableaux, plane partitions, Littlewood–Richardson rule, restriction rules.

†Supported in part by EC’s Human Capital and Mobility Program, grant CHRX-CT93-0400 and the Austrian Science Foundation FWF, grant P10191-MAT

Secondly, in Theorem 2, we express (irreducible) characters of the symplectic group Sp(N) (where N = 2n) and (irreducible) characters of the special orthogonal group SO(N) (and its spin covering group) of “nearly” rectangular shape in terms of (irreducible) characters of the general linear group GL(N). For the proofs of these identities we use the tableaux descriptions for symplectic characters developed by DeConcini and Procesi [3, 4], and for special orthogonal characters as developed by Lakshmibai, Musili and Seshadri [22, 23, 21].

Finally, in Theorem 3, we express the product of two (irreducible) characters of the symplectic group Sp(2n), respectively of the special orthogonal group SO(N) (and its spin covering group), of “nearly” rectangular shape in terms of (irreducible) characters of the same type. For the proofs of these identitites, we rely on Littelmann’s extension [24] of the Littlewood–Richardson rule for all classical group characters, which also uses the tableaux by DeConcini, Procesi, Lakshmibai, Musili and Seshadri. In fact, as a first “approximation”, we convert Littelmann’s rule in the special case of the product of an (irreducible) symplectic or special orthogonal character of rectangular shape by an arbitrary (irreducible) character of the same type to a simpler and more explicit form, the coefficients in the expansion being expressed in terms of modified Littlewood–Richardson coefficients. The resulting formulas are given in Proposition 1 in Section 6.

We want to emphasize that it is particularly the tableaux descriptions by DeConcini, Procesi, Lakshmibai, Musili and Seshadri that turn out to be very useful and effective here. The more classical rules (cf. [12, 13, 16]) involving Littlewood–Richardson coefficients, which would also apply to the second and third problem type that we consider, are nice in theory but useless in practice, since it seems to be impossible to keep track of the cancellations that are caused by application of modification rules.

As will become apparent, the reason that classical group characters indexed by “nearly” rectangular shapes allow particularly nice identities is because Littlewood– Richardson fillings and the above mentioned tableaux behave special for “nearly” rectangular shapes. This fact was previously observed by Proctor and Stanley [28, 29, 31] for rectangular shapes. Aside from these three papers, the inspiration for the current paper comes from [20]. There it was discovered that symplectic characters of “nearly” rectangular shape have a nice explicit expansion in terms of general linear characters. This gave the idea to explore what other identities for classical group characters of “nearly” rectangular shapes exist.

Finally, we remark that Okada’s paper [27] may be considered as a precursor to this paper as it contains the specializations to rectangular shapes of all our identities. Okada, however, uses a completely different approach (namely, he uses the minor summation formula of Ishikawa and Wakayama [9]). It must be pointed out on the other hand, that there is one type of identities that Okada adresses, but I am not able to address. This is restrictions of representations of G(N) (G can be GL, Sp, or SO) to a representation of G(l) × G(N − l). Though computational evidence exists that the respective identities of Okada can be extended from rectangular shapes to “nearly” rectangular shapes as well, so far I was not able to prove anything because of the lack of an efficient combinatorial rule. (Again, the rules in [12, 16] are apparently useless.)

Our paper is organized as follows. In Section 2 we recall the definitions of irreducible general linear, symplectic, orthogonal, and special orthogonal characters. Then, in Section 3, we state our results. These are subsequently proved in Sections 4, 5, and 6. Section 7 contains applications of our identities to plane partition theory, including new refinements of the Bender–Knuth and MacMahon (ex-)conjectures. Finally, in the Appendix we provide the necessary background information, in particular there we describe all the different types of tableaux that we use, Littlewood– Richardson fillings, the Littlewood–Richardson rule, Littelmann’s extension of it to other classical groups, and Littlewood’s branching rules for restricting representations of the general linear groups to representations of the symplectic or orthogonal groups.

2. General linear characters (Schur functions), symplectic, orthogonal, and special orthogonal characters. Here we recall the classical character formulas. We refer the reader to [5; 6, ch. 24; 13; 15; 33, Appendix; 39] for surveys and more detailed background information concerning classical group characters.

In what follows x = (x_{1}, x_{2}, …) will always be an infinite sequence of indeterminates. We call a sequence λ = (λ_{1}, λ_{2}, …, λ_{r}) with λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{r} ≥ 0 a partition if all the λ_{i}’s are integers, and a half-partition if all the λ_{i}’s are half-integers, by which we mean numbers of the form k + 1/2, where k is an integer. For (ordinary) partitions we adopt the convention, that partitions that only differ by trailing zeros are considered to be the same. The components λ_{1}, λ_{2}, … of λ are also called the parts of λ. We call a sequence λ = (λ_{1}, λ_{2}, …, λ_{r}) with λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{r−1} ≥ |λ_{r}| an r-orthogonal partition if all the λ_{i}’s are integers, and an r-orthogonal half-partition if all the λ_{i}’s are half-integers.

Given a partition λ = (λ_{1}, λ_{2}, …, λ_{r}), we define the (formal) general linear character, also called Schur function, s(λ; x) by (see [26, I, (3.4)])

s(λ; x) = det_{1≤i,j≤r} (h_{λ_{i}−i+j}(x)),  (2.1)

where h_{m}(x) = ∑_{1≤i_{1}≤···≤i_{m}} x_{i_{1}} ⋯ x_{i_{m}} denotes the complete homogeneous symmetric function of degree m. If r ≤ n,

s(λ; x_{1}, x_{2}, …, x_{n}, 0, 0, …)

is the irreducible character for GL(n, ℂ) indexed by λ (see e.g. [6, (24.10)]). Following King [13] we write

s_{n}(λ; x) := s(λ; x_{1}, x_{2}, …, x_{n}, 0, 0, …).  (2.2)

Two further similar notations for Schur functions that we use are

s_{2n}(λ; x^{±1}) := s(λ; x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}, 0, 0, …)  (2.3)

and

s_{2n+1}(λ; x^{±1}) := s(λ; x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}, 1, 0, 0, …).  (2.4)

Again, let λ = (λ_{1}, λ_{2}, …, λ_{r}) be a partition. Following Koike and Terada [15, Def. 2.1.1], we define the (formal) symplectic character sp(λ; x) by

sp(λ; x) = det_{1≤i,j≤r} (h_{λ_{i}−i+1}(x) ⋮ h_{λ_{i}−i+j}(x) + h_{λ_{i}−i−j+2}(x)).  (2.5)

Here, the notation of the determinant means that the first expression gives the entries of the first column and the second the entries for the remaining columns, j ≥ 2. If r ≤ n,

sp(λ; x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}, 0, 0, …)

is the irreducible character for Sp(2n, ℂ) indexed by λ (see [6, Prop. 24.22]). We write

sp_{2n}(λ; x^{±1}) := sp(λ; x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}, 0, 0, …).  (2.6)

If r ≤ n + 1,

sp(λ; x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}, 1, 0, …)

is a character for Proctor’s odd symplectic group SSp(2n + 1, ℂ) (see [30, Prop. 3.1 with x_{N} = 1]). We write

sp_{2n+1}(λ; x^{±1}) := sp(λ; x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}, 1, 0, 0, …).  (2.7)

Following Koike and Terada [15, Def. 2.1.1], we define the (formal) orthogonal character o(λ; x) by

o(λ; x) = det_{1≤i,j≤r} (h_{λ_{i}−i+j}(x) − h_{λ_{i}−i−j}(x)).  (2.8)

If r ≤ n,

o(λ; x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}, 0, 0, …)

is the irreducible character for O(2n, ℂ) indexed by λ (see [6, Ex. 24.46]), for which we write

o_{2n}(λ; x^{±1}) := o(λ; x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}, 0, 0, …).  (2.9)

Similarly, if r ≤ n,

o(λ; x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}, 1, 0, 0, …)

is the irreducible character for O(2n + 1, ℂ) indexed by λ (see [6, Ex. 24.46]), for which we write

o_{2n+1}(λ; x^{±1}) := o(λ; x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}, 1, 0, 0, …).  (2.10)

The character o_{2n+1}(λ; x^{±1}) is also the irreducible character for SO(2n + 1, ℂ) indexed by λ. Therefore we shall sometimes write so_{2n+1}(λ; x^{±1}) for o_{2n+1}(λ; x^{±1}).

However, for the spin covering group of SO(2n + 1, ℂ) there are also irreducible characters indexed by half-partitions. Let λ = (λ_{1}, …, λ_{n}) be a half-partition, then the irreducible character so_{2n+1}(λ; x^{±1}) is given by the Weyl formula (see [6, (24.28)])

so_{2n+1}(λ; x^{±1}) = \frac{det_{1≤i,j≤n}(x_{j}^{λ_{i}+n−i+1/2} − x_{j}^{−(λ_{i}+n−i+1/2)})}{det_{1≤i,j≤n}(x_{j}^{n−i+1/2} − x_{j}^{−(n−i+1/2)})}.  (2.11)

In fact (see again [6, (24.28)]), if λ is an ordinary partition, then so_{2n+1}(λ; x^{±1}) is given by the same formula.

The situation is even more delicate for SO(2n, ℂ). The irreducible characters for SO(2n, ℂ) and its spin covering group are indexed by n-orthogonal partitions or halfpartitions. Let λ = (λ_{1}, λ_{2}, …, λ_{n}) be an n-orthogonal partition or half-partition, i.e., λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n−1} ≥ |λ_{n}|, with the λ_{i}’s integers, respectively half-integers. Then the irreducible special orthogonal character so_{2n}(λ; x^{±1}) is given by the Weyl formula (see [6, (24.40)])

so_{2n}(λ; x^{±1}) = \frac{det_{1≤i,j≤n}(x_{j}^{λ_{i}+n−i} + x_{j}^{−(λ_{i}+n−i)}) + det_{1≤i,j≤n}(x_{j}^{λ_{i}+n−i} − x_{j}^{−(λ_{i}+n−i)})}{det_{1≤i,j≤n}(x_{j}^{n−i} + x_{j}^{−(n−i)})}.

(2.12)

The irreducible character for O(2n, ℂ) indexed by the partition λ, o_{2n}(λ; x^{±1}), equals the irreducible character for SO(2n, ℂ) indexed by λ, so_{2n}(λ; x^{±1}), if λ_{n} = 0, but splits into two irreducible characters for SO(2n, ℂ) if λ_{n} ≠ 0, one indexed by λ = (λ_{1}, λ_{2}, …, λ_{n}), the other indexed by λ^{−}, which by definition is (λ_{1}, λ_{2}, …, λ_{n−1}, −λ_{n}) (see [6, first paragraph on p. 411]).

The characters s(λ; x), sp(λ; x), o(λ; x) are also called universal characters, meaning that by specializing one obtains the actual (general linear, symplectic, orthogonal, respectively) characters for any dimension of the corresponding group. There is no such thing in the even special orthogonal case and for odd special orthogonal characters indexed by half-partitions. Of course, it has to be mentioned that there is not only a Weyl formula for so_{N}(λ; x^{±1}), but also for s_{n}(λ; x) (see [6, p. 403, (A.4); 26, I, (3.1)]) and sp_{2n}(λ; x) (see [6, (24.18)]), the latter reading

sp_{2n}(λ; x^{±1}) = \frac{det_{1≤i,j≤n}(x_{j}^{λ_{i}+n−i+1} − x_{j}^{−(λ_{i}+n−i+1)})}{det_{1≤i,j≤n}(x_{j}^{n−i+1} − x_{j}^{−(n−i+1)})}.  (2.13)

Actually, the Weyl formulas for all these characters allow a uniform statement (see [6, Theorem 24.2; 39, Theorem 4.1]).

3. Character identities. In this section we collect our identities for classical group characters of “nearly” rectangular shapes. By “nearly” rectangular shape we mean partitions of the form (c, c, …, c, c−p) or (c, …, c, c−1, …, c−1), i.e., partitions whose Ferrers diagram (see Section A1 of the Appendix) is a rectangle, except that one row or column might be shorter. We write (c^{r−1}, c − p) for the first partition (given that the partition has r components) and (c^{r−p}, (c − 1)^{p}) for the second (given that the partition has r components, p of which are equal to c − 1).

The first five identities express general linear characters (Schur functions) in terms of symplectic, respectively orthogonal characters. Most of the “partition terminology” that we use here and henceforth is explained in Section A1 of the Appendix. Other terminology concerns the parity of rows or columns: When we say ‘an odd (even) row’ we mean ‘a row of odd (even) length.’ We use the same convention with columns. For convenience, we denote the number of odd rows of some (ordinary or skew) shape σ by oddrows(σ) and the number of odd columns of σ by oddcols(σ), and the same with ‘even’ instead of ‘odd.’

Theorem 1. Let r, c, p by nonnegative integers. For c ≥ p there holds

s((c^{r−1}, c − p); x) = _{∑_{ν⊆(c^{r})} ; oddcols((c^{r})/ν)=p} sp(ν; x),  (3.1)

and for r ≥ p there holds

s((c^{r−p}, (c − 1)^{p}); x) = _{∑_{ν⊆(c^{r})} ; oddrows((c^{r})/ν)=p} o(ν; x).  (3.2)

In particular, for r ≤ N and c ≥ p there hold

s_{N}((c^{r−1}, c − p); x^{±1}) = \{ \begin{matrix}_{∑_{ν⊆(c^{r})} ; oddcols((c^{r})/ν)=p} sp_{N}(ν; x^{±1}) & r ≤ ⌈N/2⌉ \\ _{∑_{ν⊆(c^{N−r+1})} ; oddcols((c^{N−r+1})/ν)=c−p} sp_{N}(ν; x^{±1}) & r > ⌈N/2⌉, \end{matrix} (3.3)

and

s_{2n+1}((c^{r}); x^{±1}) = \{ \begin{matrix}∑_{ν⊆(c^{r})} sp_{2n}(ν; x^{±1}) & r ≤ n \\ ∑_{ν⊆(c^{2n+1−r})} sp_{2n}(ν; x^{±1}) & r > n. \end{matrix}  (3.4)

For p ≤ r ≤ ⌊N/2⌋ there holds

s_{N}((c^{r−p}, (c − 1)^{p}); x^{±1}) = _{∑_{ν⊆(c^{r})} ; oddrows((c^{r})/ν)=p} o_{N}(ν; x^{±1}).  (3.5)

Remark. The identities (3.3)–(3.5) have obvious interpretations as branching rules for the restriction of representation modules of GL(N, ℂ) to Sp(N, ℂ), Sp(N − 1, ℂ), respectively O(N, ℂ).

The case N = 2n, r ≤ n of (3.3) is implicit in Proctor’s paper [28, Proof of Lemma 4, Claim on p. 558]. In the same paper, there appear, explicitly, the case N = 2n, r ≤ n, p = 0 of (3.3) [28, Lemma 4, equation for A_{2n−1}(mω_{r})] and the case r ≤ n of (3.4) [28, Lemma 4, equation for A_{2n}(mω_{r})]. The cases N = 2n, r ≤ n, p = 0 of (3.3)–(3.5) appear in [27, Theorem 2.6].

The next four identities express symplectic and special orthogonal characters in terms of general linear characters (Schur functions).

Theorem 2. Let n, c, p by nonnegative integers. For n ≥ p there holds

sp_{2n} ((c^{n−p}, (c − 1)^{p}); x^{±1}) = (x_{1}x_{2} ⋯ x_{n})^{−c} ·_{∑_{ν⊆((2c)^{n})} ; oddrows(ν)=p}s_{n}(ν; x).  (3.6)

If c is a nonnegative integer or half-integer and p a nonnegative integer, 2c ≥ p, then there holds

so_{2n} ((c^{n−1}, c − p); x^{±1}) = (x_{1}x_{2} ⋯ x_{n})^{−c} ·_{∑_{ν⊆((2c)^{n})} ; oddcols(((2c)^{n})/ν)=p}s_{n}(ν; x).  (3.7)

Next, if c is a nonnegative integer or half-integer and p a nonnegative integer, n ≥ p, then there holds

so_{2n+1} ((c^{n−p}, (c − 1)^{p}); x^{±1}) = (x_{1}x_{2} ⋯ x_{n})^{−c} · ∑_{ν⊆((2c)^{n})}a_{n,p}(ν) · s_{n}(ν; x), (3.8)

where

a_{n,p}(ν) = number of vertical strips of length p on the
rim of ν avoiding the (2c)-th column.  (3.9)

Finally, if c is a nonnegative integer or half-integer and p a nonnegative integer, c ≥ p, then there holds

so_{2n+1} ((c^{n−1}, c − p); x^{±1}) = (x_{1}x_{2} ⋯ x_{n})^{−c} · ∑_{ν⊆((2c)^{n})}b_{n,p}(ν) · s_{n}(ν; x), (3.10)

where

b_{n,p}(ν) = number of horizontal strips of length p on the rim of ν

such that the i-th cell of the strip (counted from left to

right) comes before the (2c − 2p + 2i)-th column.  (3.11)

Remark. The identities (3.6)–(3.8), and (3.10) have obvious interpretations as decomposition formulas for representation modules of Sp(2n, ℂ), SO(2n, ℂ), or SO(2n+ 1, ℂ) as representations of the subgroup GL(n, ℂ). For the interested reader we add that, without much additional effort, it is also possible to derive decomposition formulas for sp_{2n} ((c^{n−1}, c − p); x^{±1}) and so_{2n} ((c^{n−p}, (c − 1)^{p}); x^{±1}) which are in the spirit of (3.10), respectively (3.8), by slightly modifying the arguments in the proofs of (3.10) and (3.8).

Formula (3.6) for the first time appeared in [20], although it is implicit already in [7, Theorem 2.6; 18, (2.2)]. The case p = 0 of (3.6) appeared already in a number of papers [31, Theorem 3; 37, Theorem 4.1; 38, Cor. 7.4.(b); 27, Theorem 2.3.(2)].

The case p = 0 of (3.8) and (3.10), which is

so_{2n+1} ((c^{n}); x^{±1}) = (x_{1}x_{2} ⋯ x_{n})^{−c} · ∑_{ν⊆((2c)^{n})}s_{n}(ν; x),  (3.12)

appeared also in a number of papers [31, Theorem 3; 38, Cor. 7.4.(a); 27, Theorem 2.3.(1)].

Finally, the cases p = 0 and p = c of (3.7) previously appeared in [1; 27, Theorem 2.3.(3)].

Our final identities of this section display the decomposition of the product of a rectangularly shaped and a “nearly” rectangularly shaped (general linear, symplectic, respectively special orthogonal) character. As will become apparent from the proofs, these identities follow rather easily from decomposition formulas for the product of a rectangularly shaped symplectic, respectively special orthogonal, character and an arbitrarily shaped symplectic, respectively special orthogonal, character, which we obtain in Proposition 1 in Section 6 from Littelmann’s decomposition formula [24].

Theorem 3. Let n, c, d, p be nonnegative integers.

First let n ≥ p. If c ≤ d then there holds

sp_{2n} ((c^{n}); x^{±1}) · sp_{2n} (((d + 1)^{p}, d^{n−p}); x^{±1}) = _{∑_{((d−c)^{n})⊆ν⊆((c+d+1)^{n})} ; oddrows(ν/((d−c)^{n}))=p} sp_{2n}(ν; x^{±1}),

(3.13)

and if c ≥ d,

sp_{2n} ((c^{n}); x^{±1}) · sp_{2n} ((d^{n−p}, (d − 1)^{p}); x^{±1}) = _{∑_{((c−d)^{n})⊆ν⊆((c+d)^{n})} ; oddrows(ν/((c−d)^{n}))=p} sp_{2n}(ν; x^{±1}),

(3.14)

Next, if c, d are nonnegative integers or half-integers and p an integer with p ≤ 2d, then there hold

so_{2n} ((c^{n}); x^{±1}) · so_{2n} ((d^{n−1}, d − p); x^{±1}) = _{∑_{(|c−d|^{n−1},c−d)⊆ν⊆((c+d)^{n})} ; oddcols(((c+d)^{n})/ν)=p} so_{2n}(ν; x^{±1}),

(3.15) with the understanding that ν ranges over n-orthogonal partitions if c+d is an integer and over n-orthogonal half-partitions if c + d is a half-integer, and

so_{2n} ((c^{n−1}, −c); x^{±1}) · so_{2n} ((d^{n−1}, d − p); x^{±1})

= _{∑_{(|c−d|^{n−1},c−d)⊆ν⊆((c+d)^{n})} evencols(((c+d)^{n})/ν)=p} so_{2n}((ν_{1}, …, ν_{n−1}, −ν_{n}); x^{±1}), (3.16)

with the same understanding.

For c, d nonnegative integers or half-integers and for n > p there holds

so_{2n+1} ((c^{n}); x^{±1}) · so_{2n+1} ((d^{n−p}, (d − 1)^{p}); x^{±1})

= ∑ ; (|c−d|^{n−p},(max{c−d,d−c−1})^{p})⊆ν⊆((c+d)^{n})c_{n,p}(ν) · so_{2n+1}(ν; x^{±1}), (3.17)

where, with m_{l}(ν) denoting the multiplicity of l in ν,

c_{n,p}(ν) = number of vertical strips of length p − m_{d−c−1}(ν)

that can be added to ν to obtain another (half-)partition, avoiding the

(d − c)-th, the (c − d + 1)-st, and the (c + d + 1)-st column of ν. (3.18)

Again, the sum in (3.17) is understood to range over partitions if c + d is an integer and over half-partitions if c + d is a half-integer.

Finally, for c, d nonnegative integers or half-integers and for d ≥ p there holds

so_{2n+1} ((c^{n}); x^{±1}) · so_{2n+1} ((d^{n−1}, d − p); x^{±1})

= ∑ ; (|c−d|^{n−1},max{c−d,d−c−p})⊆ν⊆((c+d)^{n})d_{n,p}(ν) · so_{2n+1}(ν; x^{±1}), (3.19)

where d_{n,p}(ν) is the number of all horizontal strips σ, that can be added to ν to obtain another (half-)partition, avoiding the (c + d + 1)-st column and the n-th row of ν, and which satisfy the following inequalities: If σ_{i} denotes the number of cells of the strip σ in the i-th row, i = 1, 2, …, n − 1, and if |σ| denotes the total number of cells in σ, then

\begin{matrix}||σ| − c + d − p| ≤ ν_{n}, ν_{n} + p − ν_{n−1} ≤ |σ| ≤ p \\ and 2σ_{1} + ⋯ + 2σ_{i−1} + σ_{i} + ν_{i} ≥ c − d + 2p for i = 1, 2, …, n − 1. \end{matrix} (3.20)

Also here, the sum in (3.19) is understood to range over partitions if c+d is an integer and over half-partitions if c + d is a half-integer.

Remark. All these formulas, that is (3.13)–(3.20) and (6.1)–(6.5), have obvious interpretations as decomposition formulas for the tensor product of two representation modules of Sp(2n, ℂ), SO(2n, ℂ), or SO(2n + 1, ℂ). For the interested reader we add that, without much additional effort, it is also possible to derive decomposition formulas for sp_{2n} ((c^{n}); x^{±1}) · sp_{2n} ((d^{n−1}, d − p); x^{±1}) and so_{2n} ((c^{n}); x^{±1}) · so_{2n} ((d^{n−p}, (d − 1)^{p}); x^{±1}) which are in the spirit of (3.19), respectively (3.17), by slightly modifying the arguments in the proofs of (3.19) and (3.17).

Formulas (3.13)–(3.20) generalize the symplectic and special orthogonal decompositions of Okada [27, Theorem 2.5], who proved the p = 0 special cases. Okada also proves a decomposition formula for the product of two rectangularly shaped general linear characters (Schur functions), thus generalizing Stanley’s results [36, Lemma 3.3]. More generally, Carini [2, sec. 3.3, p. 105ff] derived decomposition formulas for the product of two “nearly” rectangularly shaped general linear characters.

4. Proof of Theorem 1. Here we use decomposition rules of Littlewood [25] (see Section A7 of the Appendix). All the notions that appear in this section, like Littlewood–Richardson filling (LR-filling), Littlewood–Richardson condition (LRcondition), content, etc., are also explained in the Appendix, mainly in Section A6.

Proof of (3.1). Implicitly, this was already proved in [28, Proof of Lemma 4, Claim on p. 558]. However, since there is no explicit statement in [28] and since one would have to translate things appropriately, we include a detailed proof of (3.1) here.

According to (A.13) we have

s((c^{r−1}, c − p); x) = ∑_{ν} sp(ν; x) ∑_{μ, μ′ even} LR_{μ,ν}^{(c^{r−1},c−p)} .

Hence we have to show that

∑_{μ, μ′ even} LR_{μ,ν}^{(c^{r−1},c−p)} = \{ \begin{matrix}1 & oddcols ((c^{r})/ν) = p \\ 0 & otherwise. \end{matrix}  (4.1)

To see this, suppose that μ is a fixed partition whose Ferrers diagram has only even columns. Consider a LR-filling of shape (c^{r−1}, c − p)/μ. By the LR-condition, there is no choice for the entries in the first r − 1 rows. I.e., all the rows except for the r-th row are uniquely determined in the way that is exemplified in Figure 1. There is only freedom in the r-th row.

μ  ^{1} ^{1} ^{1} ^{1} ^{1} ^{1} ^{1} ^{1}^{2} ^{2} ^{2} ^{2} ^{2} ^{2} ^{2} ^{2}^{1} ^{1} ^{1} ^{3} ^{3} ^{3} ^{3} ^{3} ^{3} ^{3} ^{3}^{2} ^{2} ^{2} ^{4} ^{4} ^{4} ^{4} ^{4} ^{4} ^{4} ^{4}^{3} ^{3} ^{3} ^{5} ^{5} ^{5} ^{5} ^{5} ^{5} ^{5} ^{5}^{4} ^{4} ^{4} ^{6} ^{6} ^{6} ^{6} ^{6} ^{6} ^{6} ^{6}^{1} ^{5} ^{5} ^{5} ^{7} ^{7} ^{7} ^{7} ^{7} ^{7} ^{7} ^{7}^{2} ^{6} ^{6} ^{6} ^{8} ^{8} ^{8} ^{8} ^{8} ^{8} ^{8} ^{8}^{∗} ^{∗} ^{∗} ^{∗} ^{∗} ^{∗} ^{∗} ^{∗} ^{∗} ^{∗} \underbrace{c} r\{  \overbrace{p} Figure 1

It should be observed that the content of the uniquely determined part of the LRfilling equals μ̃ := (c−μ_{r−1}, c−μ_{r−2}, …, c−μ_{1}). In particular, this implies that all the columns in (c^{r})/μ̃ have odd length, except for columns c−μ_{r−1} +1, c−μ_{r−1} +2, …, c (which would have length r) in case that r is even.

Suppose that ν is the content of the complete LR-filling. Then the LR-condition is equivalent to saying that ν/μ̃ is a horizontal strip (see Appendix A1 for the definition of a horizontal strip). Besides, this horizontal strip is of length c − p − μ_{r}, the length of the r-th row of the LR-filling. Hence, there are c − (c − p − μ_{r}) = p + μ_{r} odd columns in (c^{r})/ν if c is odd, and there are c−μ_{r−1} −(c−p−μ_{r}) = p+μ_{r} −μ_{r−1} odd columns in (c^{r})/ν if r is even. The latter is due to the fact that 1 cannot be an entry in the r-th row of the LR-filling if r is even, hence the horizontal strip has to avoid the first row. Actually, the number of odd columns is p in both cases, since in case r odd we must have μ_{r} = 0 because the Ferrers diagram of μ has only even columns, and in case r even we have μ_{r−1} = μ_{r} for the same reason. Thus we have shown that, given a fixed μ whose Ferrers diagram has only even columns, then LR_{μ,ν}^{(c^{r−1},c−p)} ≠ 0 only if ν is a partition such that the number of odd columns in (c^{r})/ν equals p. In particular, this establishes the “otherwise” part of (4.1).

Conversely, given a partition ν ⊆ (c^{r}) such that the number of odd columns in (c^{r})/ν equals p, we claim that there is exactly one partition μ whose Ferrers diagram has only even columns and such that LR_{μ,ν}^{(c^{r−1},c−p)} ≠ 0. And, more precisely, we have LR_{μ,ν}^{(c^{r−1},c−p)} = 1, which means that there is exactly one LR-filling of shape (c^{r−1}, c − p)/μ and content ν. Altogether, this would establish (4.1).

The claim is established by going through the preceding paragraphs, backwards. Suppose that ν ⊆ (c^{r}) is a partition with LR_{μ,ν}^{(c^{r−1},c−p)} ≠ 0, for some μ whose Ferrers diagram has only even columns. Then μ̃, defined as above as (c−μ_{r−1}, c−μ_{r−2}, …, c− μ_{1}), is a partition in which (1) all the columns have length ≡ r mod 2, and (2) which is contained in ν and differs from ν by a horizontal strip of length c − p − μ_{r}. It is straight-forward to see that (1) and (2) determine μ̃ uniquely. Hence, μ_{1}, μ_{2}, …, μ_{r−1} are uniquely determined, thus also μ_{r}, since the Ferrers diagram of μ has to contain only even columns. To be precise, the latter condition implies that μ_{r} equals μ_{r−1} if r is even, and 0 if r is odd.

Let μ be this uniquely determined partition. To show that LR_{μ,ν}^{(c^{r−1},c−p)} = 1 it remains to see that there is exactly one LR-filling of shape (c^{r−1}, c−p)/μ with content ν. In fact, as we already observed, the entries of the first r − 1 rows of a LR-filling of shape (c^{r−1}, c − p)/μ are uniquely determined. The content of this partial filling of these first r − 1 rows is μ̃. Since ν, which should be the content of the complete LRfilling, differs from μ̃ by a horizontal strip, also the entries of the r-th row are uniquely determined. To be precise, the length of the i-th row of ν/μ̃ gives the multiplicity of i in the r-th row of the LR-filling.

Altogether, this establishes (4.1), and hence (3.1), as desired. □

Proof of (3.2). According to (A.14) we have

s((c^{r−p}, (c − 1)^{p}); x) = ∑_{ν} o(ν; x) ∑_{μ, μ even} LR_{μ,ν}^{(c^{r−p},(c−1)^{p})} .

Hence we have to show that

∑_{μ, μ even} LR_{μ,ν}^{(c^{r−p},(c−1)^{p})} = \{ \begin{matrix}1 & oddrows((c^{r})/ν) = p \\ 0 & otherwise. \end{matrix}  (4.2)

We could prove this again directly, in a similar style as in the proof of (4.1). However, once (4.1) is already known, the companion (4.2) follows straight-forwardly from the well-known identity (see [8]) LR_{μ,ν}^{λ} = LR_{μ′,ν′}^{λ′}. □

For the proofs of (3.3) and (3.4) we utilize the following auxiliary result.

Lemma. Let N be a positive integer. Then, for any partition λ = (λ_{1}, λ_{2}, …, λ_{N}) we have

s_{N}((λ_{1}, λ_{2}, …, λ_{N}); x^{±1}) = s_{N}((λ_{1} − λ_{N}, λ_{1} − λ_{N−1}, …, λ_{1} − λ_{2}, 0); x^{±1}). (4.3)

Proof. This identity follows upon little manipulation from the dual Jacobi–Trudi identity (the Nägelsbach–Kostka identity, see [26, I, (3.5)]) for Schur functions,

s(λ; x) = det_{1≤i,j≤λ_{1}} (e_{λ′_{i}−i+j}(x)),  (4.4)

where e_{m}(x) = ∑_{1≤i_{1}<···<i_{m}} x_{i_{1}} ⋯ x_{i_{m}} denotes the elementary symmetric function of degree m. For, by (4.4), and because of

e_{m}(x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}) = e_{2n−m}(x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1})

and a similar identity for e_{m}(x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}, 1), we have (in the following calculation e_{m}(x^{±1}) is short for e_{m}(x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}), respectively for e_{m}(x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}, 1), depending on whether N is even or odd)

s_{N}((λ_{1}, λ_{2}, …, λ_{N}); x^{±1}) = det_{1≤i,j≤λ_{1}} (e_{λ′_{i}−i+j}(x^{±1}))

= det_{1≤i,j≤λ_{1}} (e_{N−λ′_{i}+i−j}(x^{±1}))

= det_{1≤i,j≤λ_{1}} (e_{N−λ′_{λ_{1}+1−i}+(λ_{1}+1−i)−(λ_{1}+1−j)}(x^{±1}))

= s_{N}((λ_{1} − λ_{N}, λ_{1} − λ_{N−1}, …, λ_{1} − λ_{2}, 0); x^{±1}).

Proof of (3.3). In (3.1) we specialize x to (x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}, 0, 0, …) if N = 2n, and to (x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}, 1, 0, 0, …) if N = 2n + 1, which leads to

s_{N}((c^{r−1}, c − p); x^{±1}) = _{∑_{ν⊆(c^{r})} ; oddcols((c^{r})/ν)=p} sp_{N}(ν; x^{±1}).  (4.5)

This gives (3.3) for r ≤ ⌈N/2⌉ immediately. In case r > ⌈N/2⌉, on the right-hand side of (4.5) the partition ν could have more than ⌈N/2⌉ parts, in which case one would have to apply modification rules for the corresponding symplectic characters sp_{N}(ν; x) (see e.g. [10; 39, Theorem 5.4]). However, we circumvent this difficulty by appealing to the Lemma above. In fact, by (4.3) and (4.5) we have for r > ⌈N/2⌉,

s_{N}((c^{r−1}, c − p); x^{±1}) = s_{N}((c^{N−r}, p); x^{±1})

= _{∑_{ν⊆(c^{N−r+1})} ; oddcols((c^{N−r+1})/ν)=c−p} sp_{N}(ν; x^{±1}),

which is (3.3) for r > ⌈N/2⌉. □

Proof of (3.4). In (3.1) we set N = 2n+1, p = 0, and substitute (x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}, 1, 0, 0, …) for x to obtain

s_{2n+1}((c^{r}); x^{±1}) = _{∑_{ρ⊆(c^{r})} ; oddcols((c^{r})/ρ)=0} sp_{2n+1}(ρ; x^{±1}).  (4.6)

Now let first be r ≤ n. The odd symplectic characters on the right-hand side of (4.6) are known to decompose in terms of even symplectic characters as (see [30, Cor. 8.1; 32, Lemma 9.1 with z = 1 and b = 0])

sp_{2n+1}(ρ; x^{±1}) = _{∑_{ν⊆ρ} ρ/ν a horizontal strip} sp_{2n}(ν; x^{±1}).  (4.7)

Combining this with (4.6) yields (3.4) for r ≤ n, as for any subpartition ν of the rectangle (c^{r}) there is exactly one way of adding a horizontal strip to ν such that a partition ρ with oddcols((c^{r})/ρ) = 0 is obtained.

The case r > n of (3.4) then follows from the r ≤ n case by use of (4.3) with N = 2n + 1. □

Proof of (3.5). Here, in (3.2) we specialize x to (x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}, 0, 0, …) if N = 2n, and to (x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}, 1, 0, 0, …) if N = 2n + 1. □

5. Proof of Theorem 2. In this section we combine the tableaux description of symplectic characters due to DeConcini and Procesi [3, 4] (see Section A3 of the Appendix) and tableaux descriptions of special orthogonal characters due to Lakshmibai, Musili and Seshadri [22, 23, 21] (see Sections A4 and A5 of the Appendix) with Robinson–Schensted–Knuth type algorithms. We remark that while there are restriction rules that would apply here (they involve ordinary Littlewood–Richardson coefficients, see [12, (4.20)–(4.22); 16, Theorem 2.1 with k = n, Theorem A1]), these do not appear to be very helpful for our purposes. This is because they involve modification rules for characters, these cause alternating signs, and these in turn cause a lot of cancellations, and all this is simply not tractable for the applications that we have in mind.

Proof of (3.6). By (A.4) we know that the left-hand side of (3.6) equals

∑_{S a (2n)-symplectic tableau} of shape (c^{n−p},(c−1)^{p})(x^{±1})^{S}.  (5.1)

On the other hand, by (A.2) we have that the right-hand side of (3.6) equals

(x_{1}x_{2} ⋯ x_{n})^{−c} ·_{∑_{T an n-tableau} of shape ν⊆((2c)^{n}) with oddrows(ν)=p}x^{T} .  (5.2)

Comparing (5.1) and (5.2), we see that (3.6) will be proved if we can find a bijection, Φ say, between (2n)-symplectic tableaux S of shape (c^{n−p}, (c − 1)^{p}) and n-tableaux T with at most 2c columns and exactly p odd rows such that

(x^{±1})^{S} = (x_{1}x_{2} ⋯ x_{n})^{−c} · x^{T} , if T = Φ(S).  (5.3)

The bijection that we are going to construct proceeds in two steps. In the first step we map (2n)-symplectic tableaux of shape (c^{n−p}, (c − 1)^{p}) to certain pairs (see the paragraph including (5.4)) by analyzing how these symplectic tableaux look like. In the second step we map these pairs to the above described n-tableaux by a Robinson– Schensted–Knuth type correspondence.

First step. Let S be a (2n)-symplectic tableaux of shape (c^{n−p}, (c − 1)^{p}). By the definition of (2n)-symplectic tableaux in Section A3 of the Appendix, S is a (2n)- tableau of shape ((2c)^{n−p}, (2c − 2)^{p}) such that columns 2c−1, 2c, columns 2c−3, 2c−2, etc., form (2n)-symplectic admissible pairs. An example with n = 6, c = 4, p = 2 is displayed in Figure 2.

1 1 1 1 3 3 3 4 2 2 2 3 4 4 5 5 3 4 4 5 7 7 9 10 4 5 7 7 8 8 12 12 5 6 8 9 11 11 7 10 10 11 12 12 \underbrace{2c} n\{ \}p Figure 2

We claim that (2n)-symplectic tableaux S of shape (c^{n−p}, (c − 1)^{p}) are in bijection with pairs (T̄, {e_{1}, e_{2}, …, e_{p}}), by a bijection Φ_{1} say, where T̄ is an n-tableau whose shape has only even rows and is contained in ((2c)^{n−p}, (2c − 2)^{p}), and where {e_{1}, e_{2}, …, e_{p}} is a set of numbers satisfying

\begin{matrix}1 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ n, \\ and e_{l} ∉ [i(m), j(m)] for 1 ≤ l ≤ p, 1 ≤ m ≤ s, \end{matrix}  (5.4)

given that

\begin{matrix}i(1) & j(1) \\ ⋮ & ⋮ \\ i(s) & j(s) \end{matrix}

are the (2c − 1)-st and (2c)-th column of T̄, such that

(x^{±1})^{S} = (x_{1}x_{2} ⋯ x_{n})^{−c} · x_{e_{1}} ⋯ x_{e_{p}} · xT̄, if (T̄, {e_{1}, e_{2}, …, e_{p}}) = Φ_{1}(S). (5.5)

The construction of the bijection Φ_{1} is based on an analysis of the symplectic tableaux under consideration. By Observation 2 in Section A3 of the Appendix, both columns in a (2n)-symplectic admissible pair have the same number of entries ≤ n. Hence, the entries ≤ n in S form an n-tableau, T̄ say, with only even rows. Of course, the shape of T̄ is contained in ((2c)^{n−p}, (2c − 2)^{p}). In Figure 2 we have marked the area that is covered by entries ≤ n by a bold line. The resulting tableau is displayed in the left half of Figure 3.

The next observation is that, given T̄, we can recover S almost completely, only the (2c−1)-st and the (2c)-th column cannot be necessarily recovered. For, all the columns of S except columns 2c−1 and 2c have length n. Thus, by Observation 3 in Section A3 of the Appendix, if the entries ≤ n in a column of length n are {i(1), i(2), …, i(s)} then the entries > n are {n+1, n+2, …, 2n}\{2n+1−i(1), 2n+1−i(2), …, 2n+1−i(s)}. Only for recovering columns 2c − 1 and 2c of S from T̄ we need more information than just the (2c − 1)-st and (2c)-th column of T̄.

Let the (2c − 1)-st and (2c)-th column of S be

\begin{matrix}i(1) & j(1) \\ ⋮ & ⋮ \\ i(s) & j(s) \end{matrix} \} entries ≤ n

\begin{matrix}i(s + 1) & j(s + 1) \\ ⋮ & ⋮ \\ i(n − p) & j(n − p) \end{matrix} \} entries > n

(5.6)

Observe that by definition of a (2n)-symplectic admissible pair (see Definition 1 in the Appendix) we have

{i(1), …, i(s), 2n + 1 − i(s + 1), …, 2n + 1 − i(n − p)} = {j(1), …, j(s), 2n + 1 − j(s + 1), …, 2n + 1 − j(n − p)}. (5.7)

Let {e_{1}, e_{2}, …, e_{p}} be the complement of this set in {1, 2, …, n}. With other words, e_{1}, e_{2}, …, e_{p} are the numbers e between 1 and n with the property that neither e nor its “conjugate” 2n + 1 − e occur in the (2c − 1)-st or (2c)-th column of S. Without loss of generality we may assume e_{1} < e_{2} < ⋯ < e_{p}. In our running example (recall p = 2) we have {e_{1}, e_{2}} = {2, 6}.

Obviously, because of (5.7) and the definition of T̄ and {e_{1}, e_{2}, …, e_{p}}, all the information about the (2c − 1)-st and the (2c)-th column (displayed in (5.6)) is contained in the (2c − 1)-st and (2c)-th column of T̄ (the entries ≤ n in (5.6)) and {e_{1}, e_{2}, …, e_{p}}. Moreover, because of the definition of a (2n)-symplectic admissible pair, we have e_{l} ∉ [i(m), j(m)], for all l and m. And conversely, if we have

\begin{matrix}i(1) & j(1) \\ ⋮ & ⋮ \\ i(s) & j(s) \end{matrix} , \{e_{1}, e_{2}, …, e_{p}\}

such that (5.4) is satisfied, then (5.6) with

{i(s + 1), …, i(n − p)} := {n + 1 …, 2n}\{2n + 1 − i(1), …, 2n + 1 − i(s),
2n + 1 − e_{1}, …, 2n + 1 − e_{p}}
{j(s + 1), …, j(n − p)} := {n + 1 …, 2n}\{2n + 1 − j(1), …, 2n + 1 − j(s),
2n + 1 − e_{1}, …, 2n + 1 − e_{p}}

will be a (2n)-symplectic admissible pair.

Hence, we have defined the desired bijection Φ_{1}. It is easy to check that the weight property (5.5) holds under this correspondence.

Our running example in Figure 2 is mapped under Φ_{1} to the pair in Figure 3.

( 1 1 1 1 3 3 3 4 2 2 2 3 4 4 5 5 3 4 4 5 4 5 5 6 , {2, 6}) Figure 3

Second step. In the second step we construct a bijection Φ_{2} between pairs (T̄, {e_{1}, e_{2}, …, e_{p}}) satisfying the above conditions including (5.4), and n-tableaux T with at most 2c columns and exactly p odd rows, such that

x^{T} = x_{e_{1}} ⋯ x_{e_{p}} · xT̄.  (5.8)

Let (T̄, {e_{1}, e_{2}, …, e_{p}}) be such a pair. We insert e_{p}, e_{p−1}, …, e_{1}, in this order, into T̄, according to the following procedure. Let T̄_{0} := T̄. Suppose that, by inserting e_{p}, e_{p−1}, …, e_{p−l+1} we already formed T̄_{l}. Next we insert e_{p−l} into T̄_{l} in the following way. Choose the first row (from top to bottom) of T̄_{l} such that e_{p−l} is less than the entry in the (2c − 1)-st column in that row of T̄_{l}. If there is no such row choose the first row that does not have an entry in the (2c − 1)-st column of that row. Then, starting with that row of T̄_{l}, ROW-INSERT e_{p−l} into T̄_{l}, i.e., (cf. [14, p. 712; 19, pp. 87–88]) find the leftmost entry in that row that is larger than e_{p−l}, bump it and replace it by e_{p−l}, if there is none then place e_{p−l} at the end of that row. If an entry was bumped then repeat this same procedure with the bumped entry and the next row, etc. Thus one obtains T̄_{l+1}. Finally, set T = Φ_{2}((T̄, {e_{1}, e_{2}, …, e_{p}})) := T̄_{p}. Our running example from Figure 3 is mapped under Φ_{2} to the tableau in Figure 4.

1 1 1 1 2 3 3 4 2 2 2 3 3 4 5 5 3 4 4 4 6 4 5 5 5 6 Figure 4

Since T̄ was an n-tableau with only even rows, and since later “insertion paths” are (weakly) to the left of previous ones, T is an n-tableau with exactly p odd rows. Trivially, (5.8) is satisfied.

To show that Φ_{2} is a bijection, we have to construct the inverse mapping. Take an n-tableau T with at most 2c columns and exactly p odd rows. Choose the last row (from top to bottom) of T that has odd length. Now, starting with that row, perform a, slightly modified, ROW-DELETE (cf. [14, p. 713; 19, pp. 88]). Namely, remove the last entry, x say, from that row and find the rightmost entry, y say, in the previous row that is less than x, replace y by x and repeat this same procedure with y and the row before the row that contained y, etc., until no row is left to be considered or until an entry in the (2c)-th column would be replaced. In the latter case (this is the modification), do not replace the entry in the (2c)-th column, but stop the procedure. Thus we obtain an n-tableau T_{1} with p − 1 odd rows and an entry, e_{1} say, that was replaced in the last step of the procedure. This procedure is repeated with T_{1}, thus obtaining T_{2} and e_{2}, etc. In the end we obtain T_{p}, which is an n-tableau with only even rows, and in the course of our algorithm we obtained the elements e_{1}, e_{2}, …, e_{p}. By standard properties of ROW-INSERT and ROW-DELETE (cf. [34]), it is not difficult to see that this algorithm exactly reverses Φ_{2}, step by step. In particular, the start of ROW-INSERT in a row that is possibly different from the first and the modified ending of ROW-DELETE complement each other exactly.

The composition Φ_{2} ∘ Φ_{1} is by definition the desired bijection between (2n)-sym-plectic tableaux S of shape (c^{n−p}, (c−1)^{p}) and n-tableaux T with at most 2c columns and exactly p odd rows. From (5.5) and (5.8) the weight property (5.3) follows immediately. This completes the proof of (3.6). □

Proof of (3.7). Using (A.6) and (A.2) in (3.7), we see that (3.7) will be proved if we can find a bijection, Ψ say, between (2n)-orthogonal tableaux S of shape (c^{n−1}, c− p) and n-tableaux T with at most 2c columns and exactly p columns with parity different from n (by which we mean that the lengths of the columns have parity different from n) such that

(x^{±1})^{S} = (x_{1}x_{2} ⋯ x_{n})^{−c} · x^{T} , if T = Ψ(S).  (5.9)

Again, the bijection that we are going to construct proceeds in two steps. In the first step we map (2n)-orthogonal tableaux of shape (c^{n−1}, c − p) to certain pairs (see the paragraph including (5.10)) by analyzing how these orthogonal tableaux look like. In the second step we map these pairs to the above described n-tableaux by Robinson–Schensted–Knuth insertion.

First step. Let S be a (2n)-orthogonal tableaux of shape (c^{n−1}, c − p). By Observation 1 in Section A5 of the Appendix, S consists of a pair (S_{3}, S_{2}) of (2n)-tableaux, S_{3} being of shape ((2c − p)^{n}) and each column of which containing an even number of entries > n, S_{2} being of shape (p^{n}), each column of which containing an odd number of entries > n, and all the entries in the first row of S_{2} being at most n, such that the concatenation S_{3} ∪ S′_{2} is a (2n)-tableau, where S′_{2} is the tableau arising from S_{2} by replacing the topmost element, e_{i} say, in column i of S_{2} by its “conjugate” 2n+1−e_{i}, for all i = 1, 2, …, p, and by rearranging the columns in increasing order. An example with n = 6, c = 7/2, p = 2 is displayed in the left half of Figure 5. The right half shows the concatenation S_{3} ∪ S′_{2} (note that e_{1} = 1, e_{2} = 2).

1 1 1 2 3 1 2 2 2 3 3 4 3 3 4 4 4 7 7 4 5 5 5 6 8 8 7 7 7 7 8 9 11 8 9 10 10 11 12 12 11 12 \underbrace{2c} n\{ \overbrace{S_{3}}\overbrace{p} \overbrace{S_{2}} 1 1 1 2 3 3 3 2 2 3 3 4 4 5 4 4 4 7 7 7 7 5 5 6 8 8 8 9 7 7 8 9 11 11 11 10 10 11 12 12 12 12 \overbrace{S_{3}}\overbrace{S′_{2}} Figure 5

We claim that (2n)-orthogonal tableaux S of shape (c^{n−1}, c−p) are in bijection with pairs (T̄, {e_{1}, e_{2}, …, e_{p}}), by a bijection Ψ_{1} say, where T̄ is an n-tableau whose shape has only columns with the same parity as n and is contained in ((2c)^{n−1}, 2c − p), and where {e_{1}, e_{2}, …, e_{p}} is a set of numbers satisfying

1 ≤ e_{1} ≤ e_{2} ≤ ⋯ ≤ e_{p} ≤ n,

e_{i} is less than the topmost element of the (2c − p + i)-th column of T̄,

(5.10)

such that

(x^{±1})^{S} = (x_{1}x_{2} ⋯ x_{n})^{−c} · x_{e_{1}} ⋯ x_{e_{p}} · xT̄, if (T̄, {e_{1}, e_{2}, …, e_{p}}) = Ψ_{1}(S). (5.11)

The construction of the bijection Ψ_{1} is based on an analysis of the orthogonal tableaux under consideration. By definition, all the columns in S_{3} ∪ S′_{2} contain an even number of entries > n. Hence, the entries ≤ n in S_{3} ∪ S′_{2} form an n-tableau, T̄ say, with all columns having the same parity as n. Of course, the shape of T̄ is contained in ((2c)^{n−1}, 2c − p). In the right half of Figure 5 we have marked the area that is covered by entries ≤ n by a bold line. The resulting tableau is displayed in the left half of Figure 6.

Now, let Ψ_{1}(S) be defined by (T̄, {e_{1}, e_{2}, …, e_{p}}), where, as before, e_{i} is the topmost element of the i-th column of S_{2}. Our running example in Figure 5 is mapped under Ψ_{1} to the pair in Figure 6. It is obvious that (5.10) and (5.11) hold under this mapping. Besides, it is trivial to recover S from (T̄, {e_{1}, e_{2}, …, e_{p}}). Hence, Ψ_{1} is a bijection, as desired.

( 1 1 1 2 3 3 3 2 2 3 3 4 4 5 4 4 4 5 5 6 , {1, 2}) Figure 6

Second step. In the second step we construct a bijection Ψ_{2} between pairs (T̄, {e_{1}, e_{2}, …, e_{p}}) satisfying the above conditions including (5.10), and n-tableaux T with at most 2c columns and exactly p columns of parity different from n, such that

x^{T} = x_{e_{1}} ⋯ x_{e_{p}} · xT̄.  (5.12)

Let (T̄, {e_{1}, e_{2}, …, e_{p}}) be such a pair. We ROW-INSERT e_{1}, e_{2}, …, e_{p}, in this order, into T̄. (The reader should observe the differences to the algorithm in the second step of the proof of (3.6): Here we use genuine ROW-INSERT, without any modification, as opposed to the proof of (3.6). Furthermore, the order in which the elements e_{1}, e_{2}, …, e_{p} are inserted is exactly the reversed order in the proof of (3.6).) I.e., (cf. [14, p. 712; 19, pp. 87–88]) let T̄_{0} := T̄. Suppose that, by inserting e_{1}, e_{2}, …, e_{l} we already formed T̄_{l}. Next we insert e_{l+1} into T̄_{l}. Namely, we find the leftmost entry in the first row of T̄_{l} that is larger than e_{l+1}, bump it and replace it by e_{l+1}, if there is none we place e_{l+1} at the end of that row. If an entry was bumped then we repeat this same procedure with the bumped entry and the next row, etc. Thus one obtains the tableau T̄_{l+1}. Finally, we set T = Ψ_{2}((T̄, {e_{1}, e_{2}, …, e_{p}})) := T̄_{p}. Our running example from Figure 6 is mapped under Ψ_{2} to the tableau in Figure 7.

1 1 1 1 2 3 3 2 2 2 3 3 4 5 3 4 4 4 4 5 6 5 Figure 7

Since T̄ was an n-tableau with all columns having the same parity as n, and since later “insertion paths” are strictly to the right of previous ones, T is an n-tableau with exactly p columns of parity different from n. Moreover, since e_{i} is less than the topmost element of the (2c − p + i)-th column of T̄, the insertion process will at no stage produce more than 2c columns. Hence, T has at most 2c columns. Trivially, (5.12) is satisfied.

To show that Ψ_{2} is a bijection, we have to construct the inverse mapping. Take an n-tableau T with at most 2c columns and exactly p columns of parity different from n. Choose the rightmost column of T that has parity different from n. Suppose that the bottommost entry in this column is in row I. Now, starting with that row, perform ROW-DELETE, i.e., (cf. [14, p. 713; 19, pp. 88]) remove the last entry, x_{I} say, from the I-th row and find the rightmost entry, x_{I−1} say, in the (I − 1)-st row that is less than x_{I}, replace x_{I−1} by x_{I} and repeat this same procedure with x_{I−1} and the (I − 2)-nd row, etc., until no row is left to be considered. Thus we obtain an ntableau T_{1} with p−1 columns of parity different from n and an entry, e_{p} say, that was replaced in the last step of the procedure. This procedure is repeated with T_{1}, thus obtaining T_{2} and e_{p−1}, etc. In the end we obtain T_{p}, which is an n-tableau with all columns having the same parity as n, and in the course of our algorithm we obtained the elements e_{p}, e_{p−1}, …, e_{1}. Again, by standard properties of ROW-INSERT and ROW-DELETE (cf. [34]), it is not difficult to see that this algorithm exactly reverses Ψ_{2}, step by step.

The composition Ψ_{2} ∘ Ψ_{1} is by definition the desired bijection between (2n)-orth-ogonal tableaux S of shape (c^{n−1}, c − p) and n-tableaux T with at most 2c columns and exactly p columns of parity different from n. From (5.11) and (5.12) the weight property (5.9) follows immediately. This completes the proof of (3.7). □

Proof of (3.8). Here we have to deal with (2n + 1)-orthogonal tableaux. Since these are not too far from (2n)-symplectic tableaux, the arguments here are very similar to those in the proof of (3.6). In fact, the basic steps are the same, only the details differ. So we shall be sometimes sketchy and provide details only if necessary.

Using (A.5) and (A.2) in (3.8), we see that (3.8) will be proved if we can find a bijection, Θ say, between (2n+1)-orthogonal tableaux S of shape (c^{n−p}, (c−1)^{p}) and pairs (T, σ), where T is an n-tableau whose shape is contained in ((2c)^{n}), and where σ is a vertical strip of length p on the rim of ν that avoids the (2c)-th column, such that

(x^{±1})^{S} = (x_{1}x_{2} ⋯ x_{n})^{−c} · x^{T} , if (T, σ) = Θ(S), for some σ.  (5.13)

Again, we proceed in two steps.

First step. Let S be a (2n + 1)-orthogonal tableaux of shape (c^{n−p}, (c − 1)^{p}). By the definition of (2n + 1)-orthogonal tableaux in Section A4 of the Appendix, S is a (2n)-tableau of shape ((2c)^{n−p}, (2c − 2)^{p}) such that columns 2c − 1, 2c, columns 2c − 3, 2c − 2, etc., form (2n + 1)-orthogonal admissible pairs. An example with n = 6, c = 4, p = 3 is displayed in Figure 8.

1 1 1 1 3 3 4 4 2 2 2 3 4 5 5 5 3 3 4 6 7 7 12 12 4 5 5 8 8 9 5 6 6 9 11 11 6 9 10 11 12 12 \underbrace{2c} n\{  \}p Figure 8

We claim that (2n + 1)-orthogonal tableaux S of shape (c^{n−p}, (c − 1)^{p}) are in bijection with pairs (T̄, {e_{1}, e_{2}, …, e_{p}}), by a bijection Θ_{1} say, where T̄ is an ntableau contained in ((2c)^{n−p}, (2c − 2)^{p}), and where {e_{1}, e_{2}, …, e_{p}} is a set of numbers satisfying

1 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ n,
e_{l} ∉ [i(m), j(m)] for 1 ≤ l ≤ p, 1 ≤ m ≤ s,
and e_{l} ∉ [i(s + 1), n] for 1 ≤ l ≤ p,

(5.14)

given that

i(1) j(1)
⋮  ⋮
i(s) j(s)
i(s + 1)
⋮
i(t)

are the (2c − 1)-st and (2c)-th column of T̄, such that

(x^{±1})^{S} = (x_{1}x_{2} ⋯ x_{n})^{−c} · x_{e_{1}} ⋯ x_{e_{p}} · xT̄, if (T̄, {e_{1}, e_{2}, …, e_{p}}) = Θ_{1}(S). (5.15)

The construction of the bijection Θ_{1} is based on an analysis of the orthogonal tableaux under consideration. Clearly, the entries ≤ n in S form an n-tableau, T̄ say, whose shape is contained in ((2c)^{n−p}, (2c − 2)^{p}). Note that in difference to the symplectic case, here T̄ is not necessarily a tableau with only even rows. In Figure 8 we have marked the area that is covered by entries ≤ n by a bold line. The resulting tableau is displayed in the left half of Figure 9.

Now, let the (2c − 1)-st and (2c)-th column of S be

\begin{matrix}n ≥ \{ i(1) ; ⋮ ; ⋮ ; i(t) \\ n < \{ i(t + 1) ; ⋮ ; i(n − p) \end{matrix} \begin{matrix}j(1) ; ⋮ ; j(s) \} ≤ n \\ j(s + 1) ; ⋮ ; ⋮ ; j(n − p) \} > n \end{matrix}  (5.16)

As in the symplectic case, we define {e_{1}, e_{2}, …, e_{p}} to be the set of numbers e between 1 and n with the property that neither e nor its “conjugate” 2n + 1 − e occur in the (2c − 1)-st or (2c)-th column of S. Again, without loss of generality we may assume e_{1} < e_{2} < ⋯ < e_{p}. In our running example (recall p = 3) we have {e_{1}, e_{2}, e_{3}} = {2, 3, 6}. From the definition of a (2n+1)-orthogonal admissible pair (see Definition 2 in the Appendix) it follows that the numbers e_{1}, e_{2}, …, e_{p} satisfy (5.14). Note that (5.14) differs from the “symplectic analogue” (5.4) by the additional condition in the third line.

We define Θ_{1}(S) to be (T̄, {e_{1}, e_{2}, …, e_{p}}). Our running example in Figure 8 is mapped under Θ_{1} to the pair in Figure 9.

( 1 1 1 1 3 3 4 4 2 2 2 3 4 5 5 5 3 3 4 6 4 5 5 5 6 6 6 , {2, 3, 6}) Figure 9

As in the symplectic case, it can be shown that S can be uniquely recovered from (T̄, {e_{1}, e_{2}, …, e_{p}}). Also, it is easy to check that the weight property (5.15) holds under this correspondence.

Second step. In the second step we construct a bijection Θ_{2} between pairs (T̄, {e_{1}, e_{2}, …, e_{p}}) satisfying (5.14) as before, and pairs (T, σ), where T is an n-tableau whose shape is contained in ((2c)^{n}), and where σ is a vertical strip of length p on the rim of ν that avoids the (2c)-th column, such that

x^{T} = x_{e_{1}} ⋯ x_{e_{p}} · xT̄.  (5.17)

To obtain T from such a pair (T̄, {e_{1}, e_{2}, …, e_{p}}) we use the mapping Φ_{2} from the second step of the proof of (3.6). On the other hand, σ is defined to be the vertical strip by which the shapes of T and T̄ differ. Thus, our running example from Figure 9 is mapped under Θ_{2} to the pair in Figure 10. There, the vertical strip σ is visualized by bold lines embedded in the shape of T.

( 1 1 1 1 2 3 3 4 2 2 2 3 3 4 5 5 3 3 4 4 6 4 5 5 5 5 6 6 6 6  ,  ) Figure 10

By definition of Θ_{2} (recall that an element is never inserted into the (2c)-th column of some T̄_{i}), σ is a vertical strip on the rim of the shape of T that avoids the (2c)-th column. It is obvious that (5.17) holds.

The composition Θ_{2}∘Θ_{1} is by definition the desired bijection between (2n+1)-orth-ogonal tableaux S of shape (c^{n−p}, (c − 1)^{p}) and pairs (T, σ), where T is an n-tableau whose shape is contained in ((2c)^{n}), and where σ is a vertical strip of length p on the rim of ν that avoids the (2c)-th column. From (5.15) and (5.17) the weight property (5.13) follows immediately. This completes the proof of (3.8). □

Proof of (3.10). Here we proceed very similarly to the preceding proof of (3.8).

Using (A.5) and (A.2) in (3.10), we see that (3.10) will be proved if we can find a bijection, Ω say, between (2n + 1)-orthogonal tableaux S of shape (c^{n−1}, c − p) and pairs (T, σ), where T is an n-tableau whose shape is contained in ((2c)^{n}), and where σ is a horizontal strip of length p on the rim of ν such that the i-th cell of the strip comes before the (2c − 2p + 2i)-th column, such that

(x^{±1})^{S} = (x_{1}x_{2} ⋯ x_{n})^{−c} · x^{T} , if (T, σ) = Ω(S), for some σ.  (5.18)

Again, we proceed in two steps.

First step. Let S be a (2n + 1)-orthogonal tableau of shape (c^{n−1}, c − p). By the definition of (2n + 1)-orthogonal tableaux in Section A4 of the Appendix, S is a (2n)- tableau of shape ((2c)^{n−1}, 2c − 2p) such that columns 2c−1, 2c, columns 2c−3, 2c−2, etc., form (2n + 1)-orthogonal admissible pairs. An example with n = 6, c = 7/2, p = 3 is displayed in Figure 11.

1 1 1 1 2 3 4 2 2 2 5 5 5 5 3 5 5 6 7 9 10 4 7 7 9 9 11 11 5 10 10 11 12 12 12 7 \underbrace{2c} n\{ \overbrace{2p} Figure 11

We claim that (2n+1)-orthogonal tableaux S of shape (c^{n−1}, c−p) are in bijection with pairs (T̄, (e_{1}, e_{2}, …, e_{p})), by a bijection Ω_{1} say, where T̄ is an n-tableau contained in ((2c)^{n−1}, 2c − 2p), and where (e_{1}, e_{2}, …, e_{p}) is a vector of numbers (we definitely mean vector here, i.e., the order of the numbers is important) satisfying

\begin{matrix}1 ≤ e_{1}, e_{2}, …, e_{p} ≤ n, \\ e_{l} ∉ [i_{l}(m), j_{l}(m)] for 1 ≤ l ≤ p, 1 ≤ m ≤ s_{l}, \\ e_{l} ∉ [i_{l}(s_{l} + 1), n] for 1 ≤ l ≤ p, \end{matrix}  (5.19)

and for all m,

|{1, 2, …, m}\{e_{l}, j_{l}(1), …, j_{l}(s_{l})}| ≤ |{1, 2, …, m}\{e_{l+1}, i_{l+1}(1), …, i_{l+1}(t_{l+1})}|,

(5.20)

given that

i_{l}(1)  j_{l}(1)
⋮  ⋮
i_{l}(s_{l}) j_{l}(s_{l})
i_{l}(s_{l} + 1)
⋮
i_{l}(t_{l})

are the (2c − 2p + 2l − 1)-st and (2c − 2p + 2l)-th column of T̄, such that

(x^{±1})^{S} = (x_{1}x_{2} ⋯ x_{n})^{−c} · x_{e_{1}} ⋯ x_{e_{p}} · xT̄, if (T̄, {e_{1}, e_{2}, …, e_{p}}) = Ω_{1}(S). (5.21)

Again, the construction of the bijection Ω_{1} is based on an analysis of the orthogonal tableaux under consideration. Clearly, the entries ≤ n in S form an n-tableau, T̄ say, whose shape is contained in ((2c)^{n−1}, 2c − 2p). In Figure 11 we have marked the area that is covered by entries ≤ n by a bold line. The resulting tableau is displayed in the left half of Figure 12.

If we apply the paragraph containing (5.16) with p = 1, then we see that, with e_{l} being the number that together with its conjugate 2n + 1 − e_{l} does not appear in the (2c − 2p + 2l − 1)-st or (2c − 2p + 2l)-th column of S, l = 1, 2, …, p, the map Ω_{1} defined by

S → (T̄, (e_{1}, e_{2}, …, e_{p}))

defines the desired bijection. In particular, the fact that also the entries > n in S form a (skew) tableau is reflected by condition (5.20). For, the entries > n from the (2c − 2p + 2l)-th column of S are

{n + 1, n + 2, …, 2n}\{2n + 1 − e_{l}, 2n + 1 − j_{l}(1), …, 2n + 1 − j_{l}(s_{l})},

and the entries > n from the (2c − 2p + 2l + 1)-st column of S are

{n + 1, n + 2, …, 2n}\{2n + 1 − e_{l+1}, 2n + 1 − i_{l+1}(1), …, 2n + 1 − i_{l+1}(t_{l+1})}.

That all entries > n from the (2c − 2p + 2l)-th column of S are less or equal than their right neighbours from the (2c − 2p + 2l + 1)-st column of S, is exactly equivalent to requiring

|{2n, 2n − 1, …, 2n − m}\{2n + 1 − e_{l}, 2n + 1 − j_{l}(1), …, 2n + 1 − j_{l}(s_{l})}|

≤ |{2n, 2n − 1, …, 2n − m}

\{2n + 1 − e_{l+1}, 2n + 1 − i_{l+1}(1), …, 2n + 1 − i_{l+1}(t_{l+1})}|

for all m, which is clearly equivalent to (5.20).

Again, it is easy to check that the weight property (5.21) holds under this correspondence. Our running example in Figure 11 is mapped under Ω_{1} to the pair in Figure 12.

( 1 1 1 1 2 3 4 2 2 2 5 5 5 5 3 5 5 6 4 5 , (4, 3, 6)) Figure 12

Second step. In the second step we construct a bijection Ω_{2} between pairs (T̄, (e_{1}, e_{2}, …, e_{p})) satisfying (5.19) as before, and pairs (T, σ), where T is an n-tableau whose shape is contained in ((2c)^{n}), and where σ is a is a horizontal strip of length p on the rim of ν such that the i-th cell of the strip comes before the (2c − 2p + 2i)-th column, such that

x^{T} = x_{e_{1}} ⋯ x_{e_{p}} · xT̄.  (5.22)

Let (T̄, (e_{1}, e_{2}, …, e_{p})) be such a pair. We insert e_{1}, e_{2}, …, e_{p}, in this order, into T̄, according to a procedure that is very similar to Φ_{2}, or Θ_{2}, which were used in the proofs of (3.6), respectively (3.8). That we have to modify these procedures is due to the fact that e_{l} satisfies a condition, namely (5.19), that depends on the (2c − 2p + 2l − 1)-st and (2c − 2p + 2l)-th column of T̄, and not just on the (2c − 1)-st and (2c)-th column as was the case in (5.4) or (5.14). Let T̄_{0} := T̄. Suppose that, by inserting e_{1}, e_{2}, …, e_{l} we already formed T̄_{l}. Next we insert e_{l+1} into T̄_{l} in the following way. Choose the first row (from top to bottom) of T̄ such that e_{l+1} is less than the entry in the (2c − 2p + 2l − 1)-st column in that row of T̄_{l}. If there is no such row choose the first row that does not have an entry in the (2c − 2p + 2l − 1)-st column of that row. Then, starting with that row of T̄, ROW-INSERT e_{l+1} into T̄, see the definition of Φ_{2} in the second step of the proof of (3.6). Thus one obtains the tableau T̄_{l+1}. Finally, set T = Ω_{2}((T̄, (e_{1}, e_{2}, …, e_{p}))) := T̄_{p}. On the other hand, σ is defined to be the vertical strip (it is indeed a vertical strip, as will be shown in a moment) by which the shapes of T and T̄ differ. Thus, our running example from Figure 12 is mapped under Ω_{2} to the pair in Figure 13. There, the vertical strip σ is visualized by bold lines embedded in the shape of T.

( 1 1 1 1 2 3 4 2 2 2 3 5 5 5 3 4 5 5 6 4 5 6 5  ,  ) Figure 13

It is obvious that (5.22) holds under this correspondence. Moreover, it is immediate from the definition of σ as a result of the above insertion procedure, that the i-th cell of σ comes before the (2c − 2p + 2i)-th column. However, it is not so immediate that σ is indeed a vertical strip. This will be established next. We will be done if we are able to show that later “insertion paths” are strictly to the right of previous ones. It suffices to consider two successive insertion paths.

Let the columns 2c − 2p + 2l − 1, 2c − 2p + 2l, 2c − 2p + 2l + 1, 2c − 2p + 2l + 2 be given by the four columns in Figure 14 (ignore for the moment ‘e_{l} →’ and ‘e_{l+1} →’)

i_{l}(1)  j_{l}(1) ; ⋮  ⋮ ; ⋮  ⋮ ; ⋮  ⋮ ; e_{l} → i_{l}(u)  j_{l}(u) ; ⋮  ⋮ ; ⋮  ⋮ ; i_{l}(s_{l}) j_{l}(s_{l}) ; i_{l}(s_{l} + 1) ; ⋮ ; i_{l}(t_{l}) i_{l+1}(1)  j_{l+1}(1) ; ⋮  ⋮ ; e_{l+1} → i_{l+1}(v)  j_{l+1}(v) ; ⋮  ⋮ ; i_{l+1}(s_{l+1}) j_{l+1}(s_{l+1}) ; ⋮ ; i_{l+1}(t_{l+1}) Figure 14

Suppose that the insertion of e_{l} would start in row u, as is symbolized by e_{l} → i_{l}(u) in Figure 14, and that the subsequent insertion of e_{l+1} would start in row v, as is symbolized by e_{l} → i_{l+1}(v) in Figure 14. This would mean that we have

j_{l}(u − 1) < e_{l} < i_{l}(u)  (5.23)

and

j_{l+1}(v − 1) < e_{l+1} < i_{l+1}(v).  (5.24)

During insertion of e_{l+1}, first the element e_{l+1} bumps i_{l+1}(v) (which is an element of the (2c − 2p + 2l + 1)-st column of T̄) or an element to the left of i_{l+1}(v) in the same row. Let us further suppose that until row w − 1, w ≥ v, elements of the (2c − 2p + 2l + 1)-st column are bumped, i.e., i_{l+1}(v) bumps i_{l+1}(v + 1), …, finally i_{l+1}(w − 2) bumps i_{l+1}(w − 1). This would mean

j_{l}(v + 1) ≤ i_{l+1}(v), …, j_{l}(w − 1) ≤ i_{l+1}(w − 2).  (5.25)

We suppose that then in row w the insertion path jumps to the left of the (2c − 2p + 2l + 1)-st column (note that the case w = v covers the case that e_{l+1} bumps an element to the left of i_{l+1}(v)), which means that

i_{l+1}(w − 1) < j_{l}(w), or e_{l+1} < j_{l}(v) in case w = v.  (5.26)

We do not care what happens afterwards.

We claim that u ≤ w and that e_{l} ≤ i_{l+1}(w − 1), respectively e_{l} ≤ e_{l+1} in case w = v. This would imply that in the u-th row the insertion path caused by e_{l+1} is strictly to the right of the insertion path caused by e_{l} and therefore has to stay strictly to the right from thereon, by an elementary property of ROW-INSERT. And this is what we want to show.

For proving the claim we consider (5.20) with m = i_{l+1}(w − 1), respectively m = e_{l+1} in case w = v. For this choice of m, the right-hand side of (5.20) equals i_{l+1}(w − 1) − w since we have

i_{l+1}(1) < i_{l+1}(2) < ⋯ < i_{l+1}(w − 1),

and by (5.24),

e_{l+1} < i_{l+1}(v) < ⋯ < i_{l+1}(w − 1),

respectively equals e_{l+1} − v in case w = v since by (5.24) we have

i_{l+1}(1) < ⋯ < i_{l+1}(v − 1) ≤ j_{l+1}(v − 1) < e_{l+1} < i_{l+1}(v).

Hence, the left-hand side of (5.20) is bounded above by i_{l+1}(w − 1) − w, respectively e_{l+1} − v in case w = v.

On the other hand, the left-hand side of (5.20) is at least i_{l+1}(w−1)−w, respectively e_{l+1} − v in case w = v, and equal to the lower bound only if e_{l} ≤ i_{l+1}(w − 1), respectively e_{l} ≤ e_{l+1} in case w = v. For, by (5.25) and (5.26) we have

j_{l}(1) < ⋯ < j_{l}(w − 1) ≤ i_{l+1}(w − 2) < i_{l+1}(w − 1) < j_{l}(w),

and in case w = v we have by (5.24) and (5.26)

j_{l}(1) < ⋯ < j_{l}(v − 1) ≤ j_{l+1}(v − 1) < e_{l+1} < j_{l}(v).

So the lower bound can only be reached if e_{l} ≤ i_{l+1}(w − 1), respectively e_{l} ≤ e_{l+1} in case w = v, which is what we wanted to show.

Summarizing, we have shown that indeed e_{l} ≤ i_{l+1}(w − 1), respectively e_{l} ≤ e_{l+1} in case w = v. Combining this with (5.23) and (5.26), we obtain the inequality chain

j_{l}(u − 1) < e_{l} ≤ i_{l+1}(w − 1) (respectively e_{l+1}) < j_{l}(w),

hence j_{l}(u−1) < j_{l}(w). Since columns are strictly increasing, this immediately implies u ≤ w, as desired.

To show that Ψ_{2} is a bijection, we have to construct the inverse mapping. Experienced with three other similar proofs, this is rather straight-forward. Let (T, σ) be a pair, where T is an n-tableau whose shape is contained in ((2c)^{n}), and where σ is a horizontal strip of length p on the rim of ν such that the i-th cell of the strip comes before the (2c − 2p + 2i)-th column. For l = 1, 2, …, p start a ROW-DELETE with the entry of T that is located in the cell corresponding to the l-th cell of σ (counted from the right), but stop before an entry in the (2c − 2l + 2)-th column would be bumped. This procedure reverses the algorithm Ω_{2}, step by step.

The composition Ω_{2} ∘ Ω_{1} is by definition the desired bijection between (2n + 1)- orthogonal tableaux S of shape (c^{n−1}, c − p) and pairs (T, σ), where T is an n-tableau whose shape is contained in ((2c)^{n}), and where σ is a horizontal strip of length p on the rim of ν such that the i-th cell of the strip comes before the (2c − 2i + 2)-nd column. From (5.21) and (5.22) the weight property (5.18) follows immediately. This completes the proof of (3.10). □

6. Proof of Theorem 3. In this section we use Littelmann’s extension [24] of the Littlewood–Richardson rule to symplectic and special orthogonal characters. This extension is described in Section A6 of the Appendix. We remark that while there are other rules for the decomposition of the product of two symplectic or orthogonal characters involving ordinary Littlewood–Richardson coefficients (the Newell–Littlewood rules, see [13, Theorem 4.1; 15, Cor. 2.5.3/Prop. 2.5.2; 39, Theorem 5.3]), these do not appear to be very helpful for our purposes. Again, this is because they involve modification rules for characters, these cause alternating signs, and these in turn cause a lot of cancellations, and all this is simply not tractable for the applications that we have in mind.

Before we move on to the proofs of (3.13)–(3.20) itself, in Proposition 1 we supply decomposition formulas for the product of a rectangularly shaped symplectic, respectively special orthogonal, character and an arbitrarily shaped character of the same type. All these expansions involve slightly modified Littlewood–Richardson coefficients, which even reduce to ordinary Littlewood–Richardson coefficients in a number of cases, see the Remark after Proposition 1. But there are no alternating signs here, and hence there is no cancellation. The formulas (3.13)–(3.20) then follow rather easily from (6.1)–(6.5).

Proposition 1. For any nonnegative integer c and any partition λ with at most n parts there holds

sp_{2n} ((c^{n}); x^{±1}) · sp_{2n} (λ; x^{±1}) = ∑_{ν⊆λ+(c^{n})} sp_{2n}(ν; x^{±1})_{∑_{μ⊆((2c)^{n})} ; μ even} \overline{LR}_{λ,μ}^{ν+(c^{n})}(c) (6.1)

(‘μ even’ means that all the rows of μ are even), where \overline{LR}_{λ,μ}^{ν+(c^{n})}(c) is the number of LR-fillings F of shape (ν + (c^{n}))/λ with content μ and with the additional property that

if there is an entry e in the n-th row of F, in column j say (see Section A1 in the Appendix how columns are counted), then F must contain at least 2c − 2j + 1 other entries e to the right of column j.

(6.2)

Next, for any nonnegative integer or half-integer c and any partition or half-parti-tion λ with at most n parts there holds

so_{2n+1} ((c^{n}); x^{±1}) · so_{2n+1} (λ; x^{±1}) = ∑_{ν⊆λ+(c^{n})} so_{2n+1}(ν; x^{±1}) ∑_{μ⊆((2c)^{n})} \overline{LR}_{λ,μ}^{ν+(c^{n})}(c),

(6.3)

with the understanding that ν ranges over partitions if λ + (c^{n}) is a partition and over half-partitions if λ + (c^{n}) is a half-partition, and where \overline{LR}_{λ,μ}^{ν+(c^{n})}(c) is defined as before. (Again, see Section A1 in the Appendix how columns are counted; in particular, in condition (6.2) the column index j ranges over the integers if λ is a partition and over half-integers if λ is a half-partition.)

Finally, for any nonnegative integer or half-integer c and any (2n)-orthogonal partition or half-partition λ with at most n parts there holds

so_{2n} ((c^{n}); x^{±1}) · so_{2n} (λ; x^{±1})

= ∑_{ν⊆λ+(c^{n})} so_{2n}(ν; x^{±1})(_{∑_{μ⊆((2c)^{n})} ; oddcols(((2c)^{n})/μ)=0} L̃R_{λ,μ}^{ν+(c^{n})}(c)), (6.4)

where L̃R_{λ,μ}^{ν+(c^{n})}(c) is the number of LR-fillings F of shape (ν + (c^{n}))/λ with content μ and with the additional property that for ℓ = 1, 2, …, 2c holds:

If the subfilling that arises from F by deleting the rightmost 2c−ℓ entries 1, the rightmost 2c − ℓ entries 2, …, the rightmost 2c − ℓ entries n (if there are less than 2c − ℓ entries of some size then delete all of these) has shape ν(ℓ)/λ then ν(ℓ)_{n−1} + ν(ℓ)_{n} ≥ ℓ.

(6.5)

Again, the sum in (6.4) is understood to range over n-orthogonal partitions if λ+(c^{n}) is an n-orthogonal partition and over n-orthogonal half-partitions if λ + (c^{n}) is an n-orthogonal half-partition.

Remark. It should be noted that in case λ_{n} ≥ c the condition (6.2) is void, so that the coefficients \overline{LR}_{λ,μ}^{ν+(c^{n})}(c) which appear in (6.1) and (6.3) reduce to the ordinary Littlewood–Richardson coefficients LR_{λ,μ}^{ν+(c^{n})}. Likewise, if λ_{n−1} + λ_{n} ≥ 2c

the condition (6.5) is void, so that the coefficients L̃R_{λ,μ}^{ν+(c^{n})}(c) which appear in (6.4) reduce to the ordinary Littlewood–Richardson coefficients LR_{λ,μ}^{ν+(c^{n})}.

Proof of Proposition 1. For convenience, we start with the proof of (6.3).

Proof of (6.3). By (A.10) with χ_{n}( .) = so_{2n+1}( .; x^{±1}) we know that

so_{2n+1} ((c^{n}); x^{±1}) · so_{2n+1} (λ; x^{±1}) = ∑_{T} so_{2n+1}(λ + con(T); x^{±1}),  (6.6)

where the sum is over all (2n + 1)-orthogonal tableaux T of shape (c^{n}) such that for all ℓ = 1, 2, …, 2c the vector ν(ℓ) := λ + con(T (ℓ)) is in the Weyl chamber (A.8) of type B, i.e., satisfies

ν(ℓ)_{1} ≥ ν(ℓ)_{2} ≥ ⋯ ≥ ν(ℓ)_{n} ≥ 0.  (6.7)

The content con(T) of T is defined after (A.3).

By comparing (6.6) with (6.3) we see that (6.3) will be proved once we construct a bijection, Υ say, between (2n + 1)-orthogonal tableaux T of shape (c^{n}) and content ρ which satisfy (6.7) for ℓ = 1, 2, …, 2c and LR-fillings F of shape (λ + ρ + (c^{n}))/λ which satisfy property (6.2).

The bijection Υ is defined as follows. Let λ be fixed and let T be a (2n + 1)- orthogonal tableau of shape (c^{n}) with content ρ. By Observation 2 in Section A4 of the Appendix, (2n + 1)-orthogonal tableaux of shape (c^{n}) are nothing else but (2n)- tableaux of shape ((2c)^{n}) where each column contains one of e or 2n + 1 − e for all e = 1, 2, …, n. An example with n = 5 and c = 5/2 is displayed in the left half of Figure 15. It satisfies the required property that λ+con(T (ℓ)) is in the Weyl chamber of type B, ℓ = 1, 2, …, 2c for λ = (4, 4, 3, 1, 1), as is easily checked.

1 1 1 4 6 2 3 4 6 7 3 4 5 8 8 5 5 8 9 9 7 9 9 10 10  ⟷  1 1 1 2 2 3 1 2 3 3 4 4 Figure 15

To obtain the image of T under Υ, we construct a sequence F_{0}, F_{1}, …, F_{2c} of fillings by reading T column-wise, from right to left. The desired filling F will then be defined to be the last filling, F_{2c}. Define F_{0} to be the only filling of the shape λ/λ (which is of course the empty filling). Suppose that we already constructed F_{ℓ}. To obtain F_{ℓ+1}, we add for i = 1, 2, …, n an entry e to row i of F_{ℓ} if i is an entry in the (2c − ℓ)-th column and the e-th row of T. As already announced, we define F to be F_{2c}. Thus, with λ = (4, 4, 3, 1, 1), our tableau in the left half of Figure 15 is mapped by Υ to the filling in the right half of Figure 15.

It is straight-forward from this construction that the mapping Υ can be reversed, step by step. So we shall be done if we show that, given that T is mapped to F by Υ, T is a (2n+1)-orthogonal tableau of shape (c^{n}) with content ρ if and only if F is a LR-filling of shape (λ + ρ + (c^{n}))/λ satisfying (6.2). We provide the details only for the forward implication. Since the arguments for the backward implication are similar, the reader will have no difficulties to fill in the respective details.

Let T be a (2n+1)-orthogonal tableau of shape (c^{n}) with content ρ that is mapped by Υ to the filling F. What we have to show is that F is an n-tableau, i.e., that entries are weakly increasing along rows and strictly increasing along columns, that the LR-condition holds, that the shape of F is (λ + con(T) + (c^{n}))/λ, and that F satisfies (6.2). The reader is advised to keep the example of Figure 15 in mind. It will help to follow the subsequent arguments.

For the first statement, let e and f be entries in the i-th row of F, e being the left neighbour of f. Then, by construction of Υ, e was caused by some entry i in the e-th row and c_{e}-th column, say, of T, while f was caused by some entry i in the f-th row and c_{f}-th column, say, of T. Since f is to the right of e, f was added “later”, hence c_{f} < c_{e}. Now, since T is a tableau, the entry i in column c_{f} cannot be higher than the entry i in column c_{e}. Therefore we have e ≤ f. This holds for any left-right neighbours in F, so rows are weakly increasing, as desired. To see that columns of F are strictly increasing, we consider entries e and f in the same column of F, e being the top neighbour of f. Let e be located in the i-th row of F (and so f be located in the (i + 1)-st row of F). Then, by construction of Υ, e was caused by some entry i in the e-th row and c_{e}-th column, say, of T, while f was caused by some entry (i + 1) in the f-th row and c_{f}-th column, say, of T. It is easily seen by induction that for all ℓ the shape of the partial filling F_{ℓ} is given by (λ + con(T (ℓ)) + ((ℓ/2)^{n}))/λ. In particular, because of (6.7), this implies that the “outer shape” of F_{ℓ} is always “well-behaved” in the sense that lower rows always terminate earlier than higher rows. Therefore the entry f of F was added “later” then the entry e, which means that the column c_{f} of T must be weakly to the left of column c_{e}. We already know that there is an entry i in column c_{e} and an entry (i + 1) in column c_{f}. Since column c_{f} is located weakly to the left of column c_{e}, the entry (i + 1) must be in a lower row than the entry i. As the entry (i + 1) is located in the f-th row and the entry i is located in the e-th row, this means nothing else than e < f. This holds for any top-bottom neighbours in F, so columns are strictly increasing, as desired.

Now we turn to the LR-condition. We have to show that, while reading the entries of F row-wise from top to bottom, and in each row from right to left, at any stage we have

number of 1’s ≥ number of 2’s ≥ number of 3’s ≥ · · · .

Now, by construction of Υ, each entry in F corresponds to some entry in T. Thus, to the above described reading of the entries of F there corresponds the following reading of the entries of T: First read the entries 1 in T, from left to right, then the entries 2, from left to right, then the entries 3, etc. The LR-condition is equivalent to saying that at any stage during this reading of T the number of entries read from the first row is greater or equal the number of entries read from the second row, which in turn is greater or equal the number of entries read from the third row, etc. But this is obviously true because T is a tableau.

What regards the shape, we already noticed that for all ℓ the shape of F_{ℓ} is given by (λ + con(T (ℓ)) + ((ℓ/2)^{n}))/λ. Hence F = F_{2c} has shape (λ + con(T) + (c^{n}))/λ.

Finally, we want to show that F satisfies (6.2). Let e be a fixed entry in the n-th row and j-th column of F. Write again ν(ℓ) = λ + con(T (ℓ)). By assumption, ν(ℓ) lies in the Weyl chamber of type B, see (6.7). In particular, we have ν(ℓ)_{n} ≥ 0. Now, we already observed that

(λ + con(T (ℓ)) + ((ℓ/2)^{n}))/λ = (ν(ℓ) + ((ℓ/2)^{n}))/λ

is the shape of F_{ℓ}. Hence, the condition ν(ℓ)_{n} ≥ 0 is equivalent to saying that F_{ℓ} contains an entry in the n-th row that is located in the (ℓ/2)-th, respectively (ℓ+1)/2th, column (depending on whether λ is a partition or half-partition). (In passing, we note that the ℓ = 2c case of this fact implies that F = F_{2c} contains an entry in the c-th, respectively (c+1/2)-th, column. Hence the shape of F can indeed be written in the form (ν + (c^{n}))/λ with ν a partition or half-partition.) On the other hand, F_{ℓ} is the subfilling of F that arises by deleting the rightmost 2c − ℓ entries 1, the rightmost 2c − ℓ entries 2, …, 2c − ℓ entries e, etc., from F. Now, suppose that the fixed entry e in the n-th row and j-th column is also contained in F_{ℓ}, i.e., j ≤ (ℓ + 1)/2. Then there must be at least 2c − ℓ entries e in F to the right of the j-th column. This last property holds for all ℓ with j ≤ (ℓ + 1)/2. Hence there must be at least 2c − (2j − 1) entries e in F to the right of the j-th column. This is exactly what we wanted to show.

Thus, the proof of (6.3) is complete.

Proof of (6.1). By (A.10) with χ_{n}( .) = sp_{2n}( .; x^{±1}) we know that

sp_{2n} ((c^{n}); x^{±1}) · sp_{2n} (λ; x^{±1}) = ∑_{T} sp_{2n}(λ + con(T); x^{±1}),  (6.8)

where the sum is over all (2n)-symplectic tableaux T of shape (c^{n}) such that for all ℓ = 1, 2, …, 2c the vector ν(ℓ) := λ + con(T (ℓ)) is in the Weyl chamber (A.8) of type C, i.e., satisfies (6.7). (Recall that the Weyl chambers of types B and C are the same.) By comparing (6.8) with (6.1) we see that (6.1) will be proved once we construct a bijection between (2n)-symplectic tableaux T of shape (c^{n}) with content ρ and LR-fillings F of shape (λ+ρ+(c^{n}))/λ with even content which satisfy property (6.2).

As bijection we can take the mapping Υ from the preceding proof of (6.3). We only have to observe (see Observation 3 in Section A3 of the Appendix) that (2n)- symplectic tableaux T of shape (c^{n}) are the same as (2n + 1)-orthogonal tableaux of shape (c^{n}) with the additional property that the entries ≤ n form a subtableau with only even rows. Suppose that T is mapped by Υ to F. Then the length of the i-th row of this subtableau of T is the same as the number of occurences of i in the filling F. In other words, the shape of the subtableau equals the content of the corresponding filling F. Since the shape of the subtableau is even, the filling must have even content, as desired. The final observation is that since (6.7) holds here, too, the filling must again satisfy (6.2).

Proof of (6.4). By (A.10) with χ_{n}( .) = so_{2n}( .; x^{±1}) we know that

so_{2n} ((c^{n}); x^{±1}) · so_{2n} (λ; x^{±1}) = ∑_{T} so_{2n}(λ + con(T); x^{±1}),  (6.9)

where the sum is over all (2n)-orthogonal tableaux T of shape (c^{n}) such that for all ℓ = 1, 2, …, 2c the vector ν(ℓ) := λ + con(T (ℓ)) is in the Weyl chamber (A.9) of type D. By comparing (6.9) with (6.4) we see that (6.4) will be proved once we construct a bijection between (2n)-orthogonal tableaux T of shape (c^{n}) with content ρ and LRfillings F of shape (λ + ρ + (c^{n}))/λ and content μ where all the columns of μ have the same parity as n and where property (6.5) is satisfied.

Again, we can take the mapping Υ from the proof of (6.3) as the bijection. Here, this is because of the observation (see Observation 1 in Section A5 of the Appendix, with λ_{n−1} = λ_{n} = c) that (2n)-orthogonal tableaux T of shape (c^{n}) are the same as (2n+1)-orthogonal tableaux of shape (c^{n}) with the additional property that the entries ≤ n form a subtableau whose shape has only columns of the same parity as n. Again, since the shape of the subtableau equals the content of the corresponding filling, the content μ of the filling must have columns of the same parity as n throughout, as desired. This time we have to impose (6.5) (instead of (6.2)) since ν(ℓ) = λ+con(T (ℓ)) has to be in the Weyl chamber of type D (and not of type B or C).

This completes the proof of the Proposition. □

Now we are in the position to prove (3.13)–(3.20).

Proof of (3.13). We apply (6.1) with λ = ((d + 1)^{p}, d^{n−p}). Because of the assumption c ≤ d, the Remark after Proposition 1 applies, which says that the coefficients \overline{LR}_{λ,μ}^{ν+(c^{n})}(c) reduce to ordinary Littlewood-Richardson coefficients LR_{λ,μ}^{ν+(c^{n})}. Then, obviously, (3.13) is equivalent to the claim

∑_{μ⊆((2c)^{n})} ; μ even LR_{((d+1)^{p},d^{n−p}),μ}^{ν+(c^{n})} = \{ \begin{matrix}1 & ((d − c)^{n}) ⊆ ν ⊆ ((c + d + 1)^{n}) \\ & and oddrows(ν/((d − c)^{n})) = p \\ 0 & otherwise. \end{matrix}  (6.10)

Let F be a LR-filling of shape (ν+(c^{n}))/((d+1)^{p}, d^{n−p}) with even content. Because of the LR-condition, almost all the entries of F are uniquely determined. To be precise, except for the entries in column d + 1, all the entries in the i-th row have to equal i throughout, i = 1, 2, …, n, as is exemplified in Figure 16.

1 1 1 1 1 2 2 2 3 3 4 4 5 ∗ ∗ ∗ \underbrace{d + 1} n\{ p\{ q\{ \overbrace{d} Figure 16

However, also the entries in the (d + 1)-st column of F are uniquely determined because the content of F should be even. Namely, i occurs in the (d + 1)-st column if and only if the number of the other entries i, which is ν_{i} + c − (d + 1), is odd. In our example in Figure 16, the entries in the (d + 1)-st column would have to be 1, 2, 5. Now, suppose that F contains exactly q entries in the (d + 1)-st column, q ≤ n − p of course. Equivalently, ν = (ν_{1}, …, ν_{p+q}, d − c, …, d − c). Then there are exactly q quantities ν_{i} + c − (d + 1), i ≤ p + q, that are odd, plus n − p − q quantities ν_{i} + c − (d + 1) = −1 for i = p + q + 1, p + q + 2, …, n. Therefore, the number of odd rows in ν/((d + 1 − c)^{n}) is exactly q + (n − p − q) = n − p, or equivalently, the number of odd rows in ν/((d − c)^{n}) is exactly p.

Summarizing, we have shown that the left-hand side in (6.10) is different from zero only if ((d − c)^{n}) ⊆ ν ⊆ ((d + c + 1)^{n}) and oddrows(ν/((d − c)^{n})) = p, the inclusions being trivial constraints. In addition, we have also seen that there is exactly one LR-filling under those conditions. Thus, (6.10), and thus also (3.13), is established. □

Proof of (3.14). Here we apply (6.1) with λ = (d^{n−p}, (d − 1)^{p}). Now the assumption is c ≥ d, so the Remark after Proposition 1 does not apply. We have to show

∑_{μ⊆((2c)^{n})} ; μ even \overline{LR}_{(d^{n−p},(d−1)^{p}),μ}^{ν+(c^{n})}(c) = \{ \begin{matrix}1 & ((c − d)^{n}) ⊆ ν ⊆ ((c + d)^{n}) \\ & and oddrows(ν/((c − d)^{n})) = p \\ 0 & otherwise. \end{matrix}  (6.11)

From (6.10) it follows directly that the left-hand side in (6.11) can only be non-zero if ((d − c − 1)^{n}) ⊆ ν ⊆ ((c + d)^{n}) and if oddrows(ν/((d − 1 − c)^{n})) = n − p. Note that the latter condition is equivalent to oddrows(ν/((c − d)^{n})) = p (if this makes sense, i.e., if ((c − d)^{n}) ⊆ ν). It also follows from (6.10) that if the left-hand hand side of (6.11) is non-zero then it can only be 1. So, what remains to see is that it is non-zero if and only if in addition ((c − d)^{n}) ⊆ ν, or equivalently, c − d ≤ ν_{n}.

We begin with the forward implication. Suppose that there is a LR-filling F of shape (ν + (c^{n}))/(d^{n−p}, (d − 1)^{p}) with even content satisfying (6.2). If c = d there is nothing to show. So let c > d. Then, by considering the shape of F, we see that there must be an entry in the n-th row and (d + 1)-st column of F. (If there is no entry in the (d + 1)-st column of F, then ν_{n} + c ≤ d. So, ν_{n} ≤ d − c < 0, which is impossible since ν has to be a partition.) Clearly, this entry equals n since it is located in the last row of a column of length n. Now, condition (6.2) applied to this entry says that there must be 2c − 2(d + 1) + 1 = 2c − 2d − 1 more entries n to the right of this column. All of them necessarily have to be in the n-th row of F, hence ν_{n} + c ≥ (d + 1) + (2c − 2d − 1), or equivalently, ν_{n} ≥ c − d, as desired.

For the backward implication, assume ν_{n} ≥ c−d. We have to establish the existence of a LR-filling of shape (ν + (c^{n}))/(d^{n−p}, (d − 1)^{p}) with even content satisfying (6.2). This LR-filling can only be the uniquely determined filling that was described in the proof of (3.13). In fact, the arguments of the first paragraph of this proof and those in the proof of (3.13) actually show that this uniquely determined LR-filling satisfies all the required properties, except for possibly (6.2) for the entry in the d-th column.

We now verify (6.2) for this entry, e say, by distinguishing between too cases. First let e ≠ n. Condition (6.2) would require that there are 2c − 2d + 1 more entries e to the right. All these entries necessarily have to be located in the e-th row. Hence, condition (6.2) would require ν_{e} + c − d ≥ 2c − 2d + 1. Now, because of ν_{n} ≥ c − d, we have ν_{e} +c−d ≥ ν_{n} +c−d ≥ 2c−2d. So the total number of e’s, which is ν_{e} +c−d+1, is at least 2c − 2d + 1. Since the content of the filling is even, this number must be even. So it is actually at least 2c − 2d + 2. Hence, ν_{e} + c − d + 1 ≥ 2c − 2d + 2, or equivalently, ν_{e} + c − d ≥ 2c − 2d + 1, as required.

Now let e = n. Condition (6.2) would require that there are 2c−2d+1 more entries n to the right. Now, the total number of n’s (all of them are located in the n-th row) equals ν_{n} + c − d + 1. Because of ν_{n} ≥ c − d this number is at least 2c − 2d + 1. Again, since the content of the filling is even, this number must be even. So it is actually at least 2c − 2d + 2. Hence, there are at least 2c − 2d + 1 more n’s to the right of the n in the d-th column, as required.

This completes the proof of (3.14). □

Proof of (3.15). We apply (6.4) with λ = (d^{n−1}, d − p). Thus, we have to show that

∑_{μ⊆((2c)^{n})} ; oddcols(((2c)^{n})/μ)=0 L̃R_{(d^{n−1},d−p),μ}^{ν+(c^{n})}(c) = \{ \begin{matrix}1 & (|c − d|^{n−1}, c − d) ⊆ ν ⊆ ((c + d)^{n}) \\ & and oddcols(((c + d)^{n})/ν) = p \\ 0 & otherwise. \end{matrix}

(6.12)

Let F be a LR-filling of shape (ν + (c^{n}))/(d^{n−1}, d − p) with content μ, where oddcols(((2c)^{n})/μ) = 0. For later use we note right here that the left-hand side of (6.12) can only be non-zero if

ν ⊆ ((c + d)^{n}).  (6.13)

Similarly here, because of the LR-condition, the entries in the first n − 1 rows are uniquely determined. To be precise, all the entries in the i-th row have to equal i, i = 1, 2, …, n − 1, as is exemplified in Figure 17.

1 1 1 1 1 1 2 2 2 2 3 3 4 5 ∗ ∗ ∗ ∗ \underbrace{d} n\{  \underbrace{p} \overbrace{q}  1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 4 4 4 5 5 5 ∗ ∗ ∗ ∗ ∗ ∗ \underbrace{d} n\{  \underbrace{p} \overbrace{q} Figure 17

However, also the entries in the n-th row of F are uniquely determined because the content μ of F should satisfy oddcols(((2c)^{n})/μ) = 0. For convenience, let F̃ denote the subfilling of F consisting of the first n − 1 rows of F. Namely, there have to be as many entries i in the n-th row of F as there are columns in F̃ of length i − 1 with parity different from n, i = 1, 2, …, n. (On the side we note that therefore all the entries in the n-th row have the same parity as n.) In our examples in Figure 17, the entries in the n-th row would have to be 2, 2, 4, 6 and 2, 2, 4, 6, 6, 6, respectively. Now, suppose that F contains exactly q entries in the n-th row. Then there are exactly q columns in F̃ with parity different from n. If q ≤ p then the number of columns of F whose parity is different from n equals the aforementioned q columns plus the p − q empty columns d − p + q + 1, d − p + q + 2, …, d, see the left filling in Figure 17. If q ≥ p then the number of columns of F whose parity is different from n equals the aforementioned q columns minus the q − p columns d + 1, d + 2, …, d + q − p of length n, see the right filling in Figure 17. Hence, in both cases the number of columns of F whose parity is different from n equals p, or equivalently, oddcols(((c + d)^{n})/ν) = p. (Recall that by (6.13) the shape ν is indeed contained in ((c + d)^{n}).)

Summarizing, we have shown that the left-hand side of (6.12) is different from zero only if ν ⊆ ((c + d)^{n}) and oddcols(((c + d)^{n})/ν) = p. We have also shown that if the left-hand side is non-zero, it can only be 1 since there is at most one LR-filling. So, what remains is to show that it is non-zero if and only if in addition (|c − d|^{n−1}, c − d) ⊆ ν.

Again, we begin with the forward implication. Suppose that there is a LR-filling F of shape (ν+(c^{n}))/(d^{n−1}, d−p) with oddcols(((2c)^{n})/μ) = 0, where μ is the content of F, satisfying (6.5). Because of (d^{n−1}, d−p) ⊆ ν+(c^{n}), we have ((d−c)^{n−1}, d−c−p) ⊆ ν. Hence, we will be done if we can show c − d ≤ ν_{n}.

We already noted that the first n − 1 rows of F are uniquely determined, in particular, the (n−1)-st row of F contains only entries n−1. Now we apply condition (6.5) with ℓ = c + d − ν_{n−1}. (Note that in (6.5) this choice of ℓ has the effect of removing 2c − ℓ = ν_{n−1} + c − d entries of each size. In particular, all the entries from (n − 1)-st row are removed.) Since the content μ of F satisfies oddcols(((2c)^{n})/μ) = 0, the number of n’s must equal the number of (n − 1)’s in F. Therefore the number of n’s, all of which have to be in the n-th row, is at least as large as the number of (n − 1)’s in the (n − 1)-st row of F, the latter being ν_{n−1} + c − d. Therefore condition (6.5) with ℓ = c + d − ν_{n−1} reads

(c + ν_{n−1} − (ν_{n−1} + c − d)) + (c + ν_{n} − (ν_{n−1} + c − d)) ≥ c + d − ν_{n−1}.

Simplifying, we obtain ν_{n} ≥ c − d, which is what we wanted.

For the backward implication, assume ν_{n} ≥ c−d. Recall that there is a uniquely determined LR-filling of shape (ν + (c^{n}))/(d^{n−1}, d − p) with content μ, where oddcols(((2c)^{n})/μ) = 0. What has to be shown is that it also satisfies (6.5). A careful reading of the previous paragraph reveals that ν_{n} ≥ c − d is actually equivalent to condition (6.5) with ℓ = c + d − ν_{n−1}. Now, a moment’s thought will convince the reader that in our particular situation (the (n − 1)-st row consists of (n − 1)’s throughout, ℓ = c + d − ν_{n−1} in (6.5) therefore empties the complete (n − 1)-st row), condition (6.5) holds for all ℓ if and only if it holds for the particular choice ℓ = c + d − ν_{n−1}. Thus, (6.5) is established.

This completes the proof of (3.15). □

Proof of (3.16). Equation (3.16) is an easy corollary of equation (3.15) with p replaced by 2d − p. This is due to the observation that the substitution x_{n} → 1/x_{n} in a character so_{2n}(λ; x^{±1}) has the effect

so_{2n}((λ_{1}, …, λ_{n−1}, λ_{n}); x^{±1})|_{x_{n}→1/x_{n}} = so_{2n}((λ_{1}, …, λ_{n−1}, −λ_{n}); x^{±1}),

which follows easily from the definition (2.12). □

Proof of (3.17). We apply (6.3) with λ = (d^{n−p}, (d − 1)^{p}). Note that the only difference between (6.3) and (6.1) is that in (6.1) the partition μ is required to be even. Hence, we can use those arguments from the proofs of (3.13) (here one has to replace d by d − 1 and p by n − p) and (3.14) that do not rely on this requirement.

Again, we have to consider LR-fillings F of shape (ν + (c^{n}))/(d^{n−p}, (d − 1)^{p}) that satisfy (6.2), but with arbitrary content. So, again all entries to the right of the d-th column are uniquely determined, and in the same way, see Figure 16. But the entries in the d-th column are not unique now. In fact, there is almost complete freedom, the constraints being that the entries along the columns have to be strictly increasing, i.e., each entry of a particular size can only occur once, that the total content μ of F has to be a partition of course, and that (6.2) must be satisfied. It is easy to see that the first and second constraint are equivalent to (μ + (d^{n}))/(ν + (c^{n})) being a vertical strip of length p − m_{d−c−1}(ν) avoiding the d-th column and, because of μ ⊆ ((2c)^{n}), the (d + 2c + 1)-st column. Note that the latter “avoidance” conditions give the first and third “avoidance” condition in (3.18) when columns are counted with respect to ν, i.e., when everything is shifted back by c.

The inclusion (|c − d|^{n−p}, (max{d − c − 1, c − d})^{p}) ⊆ ν follows from the trivial inclusion ((d − c)^{n−p}, (d − c − 1)^{p}) ⊆ ν, and from the fact that c − d ≤ ν_{n} if c ≥ d, which is shown in the same way as in the proof of (3.14).

Finally, we claim that if c ≥ d the vertical strip (μ + (d^{n}))/(ν + (c^{n})) has to avoid the (2c − d + 1)-st column. Note that this “avoidance” condition gives the second “avoidance” condition in (3.18) when columns are counted with respect to ν, i.e., when everything is shifted back by c. The former “avoidance” condition comes from considering condition (6.2) for the entry in the n-th row and d-th column of the filling F. See the analogous considerations at the end of the proof of (3.14). The difference here is that the content μ can be arbitrary. Hence the argument in the proof of (3.14) that the number of e’s or n’s is even does not apply here. We leave the details to the reader.

This finishes the proof of (3.17). □

Sketch of proof of (3.19). As in the preceding proof of (3.17) we apply (6.3), this time with λ = (d^{n−1}, d − p). The arguments are very similar here. We have to consider LR-fillings F of shape (ν + (c^{n}))/(d^{n−1}, d − p) with arbitrary content. As in the proof of (3.15), all the entries in the first n − 1 rows of such a filling are uniquely determined, and in the same way, see Figure 17. But the entries in the n-th row are not. They can be chosen arbitrarily as long as the LR-condition and (6.2) are satisfied. The LR-condition implies that, with μ denoting the content of the filling, (μ_{1} + d, …, μ_{n−1} + d)/(ν_{1} + c, …, ν_{n−1} + c) is a horizontal strip, σ say. Of course, the length of σ, which equals the number of entries ≤ n − 1 in the n-th row of the LR-filling, is at most ν_{n} + c − d + p, the length of the n-th row of the filling. Note that this is one part of the first inequality in (3.20). At the same time, the length of σ is at most p. For, there cannot be more than p entries ≤ n − 1 in the n-th row since the entry in the (d + 1)-st column (which is a column of length n) and the n-th row has to be n. Note that this proves the second part of the second inequality in (3.20). Moreover, the LR-condition applied to entries n − 1 and n implies the first part of the second inequality in (3.20). Finally, condition (6.2) implies the third inequality in (3.20), and, when applied to the first entry n in the n-th row, that the length of σ is at least c − d + p − ν_{n}, the latter being the missing part of the first inequality in (3.20). We leave it to the reader to check this in detail.

The inclusion (|c − d|^{n−1}, max{c − d, d − c − p}) ⊆ ν follows on the one hand from the trivial inclusion ((d − c)^{n−1}, d − c − p) ⊆ ν, and on the other hand from c − d ≤ ν_{n}, which is derived from the first and second inequality in (3.20) as follows: ν_{n} ≥ −|σ| + c − d + p ≥ c − d. □

7. Applications to plane partitions and tableaux enumeration. We now apply results from Section 3 to derive some enumeration results for plane partitions of trapezoidal shape and for tableaux. Recall [28] that the trapezoidal shape (N, N − 2, …, N − 2r + 2) is an array of cells with r rows, each row indented by one cell to the right with respect to the previous row, and N − 2i + 2 cells in row i. A plane partition of shape (N, N − 2, …, N − 2r + 2) is a filling of the trapezoidal shape (N, N − 2, …, N − 2r + 2) with nonnegative integers (note that we allow 0 as an entry) such that entries along rows and columns are weakly decreasing.

We begin with an application of (3.3). The second statement in the theorem below, (7.2), is a result of Proctor [28, Corollary on p. 554].

Theorem 4. The number of plane partitions of trapezoidal shape (N, N − 2, …, N − 2r + 2) with entries between 0 and c and where the entries on the main diagonal form a partition with exactly p columns of parity different from r (equivalently, ∑_{i=1}^{r}(−1)^{r−i+1}a_{ii} = p if r is even, respectively ∑_{i=2}^{r}(−1)^{r−i+1}a_{ii} = p if r is odd, with a_{ii} denoting the first entry in row i), equals

\binom{c}{p}\begin{matrix}( & {p + r − 1 \atop p} & ) \\ ( & {N − r + c \atop p} & ) \end{matrix}_{∏_{1≤i≤r} ; 1≤j≤c} \frac{N − i + j}{i + j − 1} .  (7.1)

In particular, the number of plane partitions of trapezoidal shape (N, N − 2, …, N − 2r + 2) with entries between 0 and c equals

∏_{1≤i≤r} ; 1≤j≤c \frac{N + 1 − i + j}{i + j − 1} .  (7.2)

Proof. We use (3.3) with x_{i} = 1, i = 1, 2, …, ⌊N/2⌋. For this choice of x_{i}’s, the Schur functions reduce to a number (which is the dimension of the corresponding irreducible representation of GL(N, ℂ)) which has a nice closed form (see [6, Ex. A.30.(ii); 26, I, Ex. 4 on p. 45; 39, Theorem 4.4]), and is therefore easily computed. Thus, the left-hand side of (3.3) turns into (7.1). On the right-hand side of (3.3), we have a certain sum of symplectic characters evaluated at x_{i} = 1, i = 1, 2, …, ⌊N/2⌋. Now, beside the (2n)-symplectic tableaux of DeConcini and Procesi in Section A3 of the Appendix there are other symplectic tableaux. Namely, the (even) symplectic characters sp_{2n}(λ; x^{±1}) can also be described by King’s [11] symplectic tableaux of shape λ (see also [33, Theorem 4.2; 39, Theorem 2.3]), and the (odd) symplectic characters sp_{2n+1}(λ; x^{±1}) can also be described by Proctor’s [30] odd symplectic tableaux of shape λ (see also [33, Theorem 4.2 with z = 1]). There is a uniform definition. Let N = 2n or N = 2n + 1. Then a King/Proctor symplectic tableau of shape λ is an N-tableau of shape λ such that the entries in the i-th row are at least 2i − 1 for all i. Thus, the right-hand side of (3.3) can be interpreted as the number of King/Proctor symplectic tableaux with entries ≤ N and of some shape ν, where ν is contained in (c^{r}) and oddcols((c^{r})/ν) = p. These tableaux are now translated into plane partitions of trapezoidal shape as described in [31, bottom of p. 295]. Namely, given such a King/Proctor symplectic tableau, replace each entry e by 2n + 1 − e, then interpret each row of the resulting array as a partition and replace it by its conjugate partition. Next, shift the i-th row by (i − 1) cells to the right, i = 1, 2, …, to obtain a plane partition of “shifted” shape that is contained in the trapezoidal shape (N, N − 2, …, N − 2r + 2). Finally, place a zero in each cell of the trapezoidal shape that is not yet filled. It is easy to see that during this transformation the lengths of the rows of a King/Proctor symplectic tableau become the entries on the main diagonal of the resulting plane partition of trapezoidal shape. This establishes the first assertion of Theorem 4.

The number in (7.2) is obtained by summing the numbers in (7.1) over all p, by means of the Vandermonde sum (cf. [35, (1.7.7)]). This completes the proof of Theorem 4. □

The next two theorems give applications of Theorem 2. For the proof of these theorems we need a few determinant evaluations that are listed in the Lemma below. We remark that the evaluations (7.3), (7.4), (7.5) are basically the Weyl denominator factorizations of types C, B, D, respectively (cf. [6, Lemma 24.3, Ex. A.52, Ex. A.62, Ex. A.66]).

Lemma. The following identities hold true:

det_{1≤i,j≤n}(x_{i}^{j} − x_{i}^{−j}) = (x_{1} ⋯ x_{n})^{−n} ∏_{1≤i<j≤n} ((x_{i} − x_{j})(1 − x_{i}x_{j})) ∏_{i=1}^{n}(x_{i}^{2} − 1), (7.3)

det_{1≤i,j≤n}(x_{i}^{j−1/2} − x_{i}^{−(j−1/2)})

= (x_{1} ⋯ x_{n})^{−n+1/2} ∏_{1≤i<j≤n} ((x_{i} − x_{j})(1 − x_{i}x_{j})) ∏_{i=1}^{n}(x_{i} − 1), (7.4)

det_{1≤i,j≤n}(x_{i}^{j−1} + x_{i}^{−(j−1)}) = 2 · (x_{1} ⋯ x_{n})^{−n+1} ∏_{1≤i<j≤n} ((x_{i} − x_{j})(1 − x_{i}x_{j})), (7.5)

det_{1≤i,j≤n}(x_{i}^{j} + x_{i}^{−j}) = (x_{1} ⋯ x_{n})^{−n} ∏_{1≤i<j≤n} ((x_{i} − x_{j})(1 − x_{i}x_{j})) ∑_{k=0}^{n} e_{k}(x_{1}, …, x_{n})^{2},

(7.6)

det_{1≤i,j≤n}(x_{i}^{j−1/2} + x_{i}^{−(j−1/2)})

= (x_{1} ⋯ x_{n})^{−n+1/2} ∏_{1≤i<j≤n} ((x_{i} − x_{j})(1 − x_{i}x_{j})) ∏_{i=1}^{n}(x_{i} + 1). (7.7)

Proof. Identities (7.3)–(7.5), and (7.7) are readily proved by the standard argument that proves Vandermonde-type determinant evaluations.

For (7.6) there is a little bit of work to do. First, by reversing the order of columns, and adding some factors, we rewrite the determinant in (7.6) as

(−1)^{\binom{n}{2}} \frac{det_{1≤i,j≤n}(x_{i}^{n+1−j} + x_{i}^{−(n+1−j)})}{det_{1≤i,j≤n}(x_{i}^{n−j} + x_{i}^{−(n−j)})} det_{1≤i,j≤n}(x_{i}^{n−j} + x_{i}^{−(n−j)}).  (7.8)

Next we observe that because of (2.12) the quotient of determinants is one half of the orthogonal character o_{2n} ((1, 1, …, 1); x^{±1}) (recall that o_{2n}(λ; x^{±1}) is the sum of so_{2n}(λ; x^{±1}) and so_{2n}(λ^{−}; x^{±1}) if λ_{n} ≠ 0). In addition, we reverse the order of columns in the single determinant in (7.8) to obtain for (7.8)

\frac{1}{2} o_{2n} ((1, 1, …, 1); x^{±1}) det_{1≤i,j≤n}(x_{i}^{j−1} + x_{i}^{−(j−1)}).  (7.9)

By the “orthogonal Jacobi–Trudi identity” [6, Cor. 24.45; 15, Theorem 2.3.3, (6)], the orthogonal character in (7.9) is nothing else but the elementary symmetric function e_{n}(x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}). Moreover, the determinant in (7.9) can be evaluated by (7.5). Thus, the expression (7.9) becomes

e_{n}(x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}) · (x_{1} ⋯ x_{n})^{−n+1} ∏_{1≤i<j≤n} ((x_{i} − x_{j})(1 − x_{i}x_{j})). (7.10)

The elementary symmetric function in (7.10) can be transformed as follows:

e_{n}(x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}) = ∑_{k=0}^{n} e_{k}(x_{1}, …, x_{n}) · e_{n−k}(x_{1}^{−1}, …, x_{n}^{−1})

= (x_{1} ⋯ x_{n})^{−1} ∑_{k=0}^{n} e_{k}(x_{1}, …, x_{n})^{2}.

Plugging this into (7.10) completes the proof of (7.6). □

As a first application of Theorem 2 we give new proofs of two theorems of the author [19, Theorems 21 and 11] by means of (3.6). These are refinements of the Bender–Knuth and MacMahon (ex-)conjectures, see [19, Sections 3.3, 4.3] for more information and references. In order to be able to formulate the Theorem, we have to introduce a few q-notations. We write [α]_{q} := 1 − q^{α}, [n]_{q}! := [1]_{q}[2]_{q} ⋯ [n]_{q}, [0]_{q}! := 1, and

[ \begin{matrix}n \\ k \end{matrix} ]_{q} = \{ \begin{matrix}\frac{[n]_{q} · [n − 1]_{q} ⋯ [n − k + 1]_{q}}{[k]_{q}!} & k ≥ 0 \\ 0 & k < 0 \end{matrix} .

The base q in [α]_{q}, [n]_{q}!, and [ \begin{matrix}n \\ k \end{matrix} ]_{q} will in most cases be omitted. Only if the base is different from q it will be explicitly stated.

Theorem 5. Let n(T) denote the sum of all the entries of a tableau T. The generating function ∑ q^{n(T)} for tableaux T with p odd rows, with at most c columns, and with entries between 1 and n is given by

q^{\binom{p+1}{2}} \frac{[2r]}{[2r + p]} [ \begin{matrix}n \\ p \end{matrix} ] \begin{matrix}[ & \begin{matrix}n + 2r \\ n \end{matrix} & ] \\ [ & \begin{matrix}n + 2r + p \\ n \end{matrix} & ] \end{matrix} ∏_{1≤i≤j≤n} \frac{[2r + i + j]}{[i + j]}  if c = 2r  (7.11)

and

q^{\binom{p+1}{2}} [ \begin{matrix}n \\ p \end{matrix} ] ∏_{1≤i≤j≤n} \frac{[2r + i + j]}{[i + j]}  if c = 2r + 1.  (7.12)

The generating function ∑ q^{n(T)} for tableaux T with p odd rows, with at most c columns, and with only odd entries which lie between 1 and 2n − 1, is given by

q^{p^{2}} \frac{[2r + 2p]_{q^{2}} [r]_{q^{2}}}{[2r + p]_{q^{2}} [r + p]_{q^{2}}} [ \begin{matrix}n \\ p \end{matrix} ]_{q^{2}} \begin{matrix}[ \begin{matrix}n + 2r \\ n \end{matrix} ] & q^{2} \\ [ \begin{matrix}n + 2r + p \\ n \end{matrix} ] & q^{2} \end{matrix}

× ∏_{i=1}^{n} \frac{[r + i]_{q^{2}}}{[i]_{q^{2}}} ∏_{1≤i<j≤n} \frac{[2r + i + j]_{q^{2}}}{[i + j]_{q^{2}}} if c = 2r (7.13)

and

q^{p^{2}} [ \begin{matrix}n \\ p \end{matrix} ]_{q^{2}} ∏_{i=1}^{n} \frac{[r + i]_{q^{2}}}{[i]_{q^{2}}} ∏_{1≤i<j≤n} \frac{[2r + i + j]_{q^{2}}}{[i + j]_{q^{2}}}  if c = 2r + 1.  (7.14)

Proof. For proving (7.11), replace x_{i} by q^{i}, i = 1, 2, …, n, in (3.6). By (2.13), the left-hand side of (3.6) can be written as a quotient of two determinants which for this choice of x_{i}’s factor by means of (7.3). On the other hand, by (A.2) the right-hand side of (3.6) with x_{i} = q^{i}, i = 1, 2, …, n, clearly equals the generating function for the tableaux in the first assertion of Theorem 5.

The expression (7.12) is obtained without much effort from the p = 0 case of (7.11) as is described in [19, Proof of (4.3.2b)].

The proof of (7.13) proceeds in the same way as the proof of (7.11). To point out the differences, instead of substituting q^{i} now substitute q^{2i−1} for x_{i}, i = 1, 2, …, n, and use (7.4) instead of (7.3). The expression (7.14) is obtained without much effort from the p = 0 case of (7.13) as is described in [19, Proof of (3.3.3b)]. □

Our second application of Theorem 2 leads to different refinements of the Bender– Knuth and MacMahon (ex-)conjectures which are new. What we do is to use (3.7) to obtain a “column-analogue” of Theorem 5. Now, the tableaux generating functions in question do not factor completely in terms of cyclotomic polynomials, but it is still possible to write the results in a reasonably compact form.

Theorem 6. Let n(T) denote the sum of all the entries of a tableau T. The generating function ∑ q^{n(T)} for tableaux T with at most c columns, p of which being odd, and with entries between 1 and n, is given by

q^{p} \frac{[ \begin{matrix}p + n − 1 \\ p \end{matrix} ] [ \begin{matrix}c − p + n − 1 \\ c − p \end{matrix} ]}{2 [ \begin{matrix}c + n − 1 \\ c \end{matrix} ]} ∏_{1≤i<j≤n} \frac{[c + i + j − 2]}{[i + j]}

× ( ∑_{k=0}^{n} q^{k(k+c−1)} (q^{k} [ \begin{matrix}n − 1 \\ k \end{matrix} ] + q^{−p} [ \begin{matrix}n − 1 \\ k − 1 \end{matrix} ])^{2} + (1 − q^{c−2p}) ∏_{i=1}^{n−1}(1 − q^{c+2i})).

(7.15)

The generating function ∑ q^{n(T)} for tableaux T with at most c columns, p of which being odd, and with only odd entries which lie between 1 and 2n − 1, is given by

q^{p} \begin{matrix}[ \begin{matrix}p + n − 1 \\ p \end{matrix} ] & q^{2} & [ \begin{matrix}c − p + n − 1 \\ c − p \end{matrix} ] & q^{2} \\ [ \begin{matrix}c + n − 1 \\ c \end{matrix} ] & q^{2} \end{matrix} ∏_{i=1}^{n} \frac{1}{1 + q^{2(i−1)}} ∏_{1≤i<j≤n} \frac{[c + i + j − 2]_{q^{2}}}{[i + j − 2]_{q^{2}}}

× ((1 + q^{c−2p}) ∏_{i=1}^{n−1}(1 + q^{c+2i}) + (1 − q^{c−2p}) ∏_{i=1}^{n−1}(1 − q^{c+2i})). (7.16)

Proof. Since it is simpler, we start with the proof of (7.16). Replace c by c/2 and substitute q^{2i−1} for x_{i} in (3.7), i = 1, 2, …, n. By (2.12), the left-hand side of (3.7) can be written as a quotient of a sum of two determinants by another determinant. The determinants, with this choice of x_{i}’s, factor by means of (7.4) and (7.7), respectively. After simplification we arrive at the expression

q^{p} \begin{matrix}[ \begin{matrix}p + n − 1 \\ p \end{matrix} ] & q^{2} & [ \begin{matrix}c − p + n − 1 \\ c − p \end{matrix} ] & q^{2} \\ [ \begin{matrix}c + n − 1 \\ c \end{matrix} ] & q^{2} \end{matrix} ∏_{i=1}^{n} \frac{1}{1 + q^{2(i−1)}} ∏_{1≤i<j≤n} \frac{[c + i + j − 2]_{q^{2}}}{[i + j − 2]_{q^{2}}}

× ((1 + q^{c−2p}) ∏_{i=1}^{n−1}(1 + q^{c+2i}) + (−1)^{n}(1 − q^{c−2p}) ∏_{i=1}^{n−1}(1 − q^{c+2i})). (7.17)

Note that the only difference from (7.16) is the term (−1)^{n} in the last line of (7.17).

On the other hand, by (A.2) the right-hand side of (3.7) with c replaced by c/2 and with x_{i} = q^{2i−1}, i = 1, 2, …, n, equals the generating function for tableaux with at most c columns, p of which having parity different from n, and with only odd entries which lie between 1 and 2n − 1. Now we distinguish between n even or odd. If n is even then the right-hand side of (3.7) with these replacements equals the generating function for the tableaux in the second assertion of Theorem 6, and the expressions (7.17) and (7.16) agree. If n is odd then the right-hand side of (3.7), with the above replacements and with p replaced by c − p, equals the generating function for the tableaux in the second assertion of Theorem 6, and, as a few manipulations show, the expressions (7.17), with p replaced by c − p, and (7.16) agree.

For the proof of (7.15) we proceed in the same manner, only that things are more complicated here. Now we replace c by c/2 and substitute q^{i} for x_{i}, i = 1, 2, …, n, in (3.7). Again, by (2.12), the left-hand side of (3.7) can be written as a quotient of a sum of two determinants by another determinant. The determinant in the denominator, with this choice of x_{i}’s, can be evaluated by means of (7.5). The second determinant in the numerator, with this choice of x_{i}’s, can be evaluated by means of (7.3). The first determinant in the numerator is evaluated by means of (7.6). After simplification we arrive at the expression

q^{p} \frac{[ \begin{matrix}p + n − 1 \\ p \end{matrix} ] [ \begin{matrix}c − p + n − 1 \\ c − p \end{matrix} ]}{2 [ \begin{matrix}c + n − 1 \\ c \end{matrix} ]} ∏_{1≤i<j≤n} \frac{[c + i + j − 2]}{[i + j]}

× ( ∑_{k=0}^{n} q^{k(k+c−1)} (q^{k} [ \begin{matrix}n − 1 \\ k \end{matrix} ] + q^{−p} [ \begin{matrix}n − 1 \\ k − 1 \end{matrix} ])^{2} + (−1)^{n}(1 − q^{c−2p}) ∏_{i=1}^{n−1}(1 − q^{c+2i})).

(7.18)

Again, note that the only difference from (7.15) is the term (−1)^{n} in the last line of (7.18).

On the other hand, by (A.2) the right-hand side of (3.7) with c replaced by c/2 and with x_{i} = q^{i}, i = 1, 2, …, n, equals the generating function for tableaux with at most c columns, p of which having parity different from n, and with entries between 1 and n. Again, we distinguish between n even or odd. If n is even then the right-hand side of (3.7) with these replacements equals the generating function for the tableaux in the first assertion of Theorem 6, and the expressions (7.18) and (7.15) agree. If n is odd then the right-hand side of (3.7), with the above replacements and with p is replaced by c − p, equals the generating function for the tableaux in the first assertion of Theorem 6, and, as a few manipulations show, the expressions (7.18), with p replaced by c − p, and (7.15) agree. In particular, in the last step it is used that

∑_{k=0}^{n} q^{k(k+c−1)} (q^{k} [ \begin{matrix}n − 1 \\ k \end{matrix} ] + q^{−c+p} [ \begin{matrix}n − 1 \\ k − 1 \end{matrix} ])^{2}

= q^{−c+2p} ∑_{k=0}^{n} q^{k(k+c−1)} (q^{k} [ \begin{matrix}n − 1 \\ k \end{matrix} ] + q^{−p} [ \begin{matrix}n − 1 \\ k − 1 \end{matrix} ])^{2} ,

which is verified by expanding the squares.

This finishes the proof of Theorem 6. □

Since the results in Theorem 6 are completely combinatorial in nature, it would of course be desirable to find a combinatorial proof of Theorem 6. The papers [19, 20] (see also [18]) contain combinatorial proofs for the assertions in Theorem 5, in particular avoiding representation theory. But these are already quite difficult. The fact that the expressions in (7.15) and (7.16) are more complicated than those in (7.11)– (7.14) supports the suspicion that it will be even much harder to find combinatorial proofs for the assertions in Theorem 6.

We conclude by providing an application of Theorem 3, (3.13), (3.14).

Theorem 7. The number of plane partitions of trapezoidal shape (2n, 2n − 2, …,

2) with entries between 0 and N where the entries on the main diagonal are at least M and exactly p of them have parity different from N is

\binom{n}{p}\begin{matrix}( & {N − M + n \atop n + 1} & ) \\ ( & {N − M + n + p \atop n + 1} & ) \end{matrix} ∏_{1≤i≤j≤n} \frac{(N + M + i + j)(N − M + i + j)}{(i + j)^{2}}

if N + M is even (7.19)

and

\binom{n}{p}\begin{matrix}( & {N + M + n + 1 \atop n + 1} & ) \\ ( & {N + M + 1 + n + p \atop n + 1} & ) \end{matrix} ∏_{1≤i≤j≤n} \frac{(N + M + 1 + i + j)(N − M − 1 + i + j)}{(i + j)^{2}}

if N + M is odd. (7.20)

In particular, the number of plane partitions of trapezoidal shape (2n, 2n − 2, …, 2) with entries between 0 and N where the entries on the main diagonal are at least M equals

2^{n} ∏_{1≤i≤j≤n} \frac{(N + M + i + j)(N − M − 1 + i + j)}{(i + j)^{2}}.  (7.21)

Proof. We set c = (N + M)/2, d = (N − M)/2, x_{i} = 1, i = 1, 2, …, n, in (3.14) and we set c = (N − M − 1)/2, d = (N + M − 1)/2, x_{i} = 1, i = 1, 2, …, n, and replace p by n − p in (3.13). For this choice of x_{i}’s, a symplectic character reduces to a number (which is the dimension of the corresponding irreducible representation of Sp(2n, ℂ)) which has a nice closed form (see [6, Ex. 24.20; 39, Theorem 4.5.(1)]), and is therefore easily computed. Thus, the left-hand sides of (3.14) and (3.13) turn into (7.19) and (7.20), respectively. On the right-hand sides of (3.14) and (3.13), we have certain sums of symplectic characters evaluated at x_{i} = 1, i = 1, 2, …, n. In the same way as in the proof of Theorem 4, these sums can be interpreted as the cardinalities of certain sets of plane partitions of trapezoidal shape. These are exactly the plane partitions in the first assertion of Theorem 7, they are counted by the specialized right-hand side of (3.14) if N + M is even, and by the specialized right-hand side of (3.13) if N + M is odd. This proves the first assertion of Theorem 7.

To obtain (7.21), we sum the respective expressions in (7.19) and (7.20) by means of Kummer’s very well-poised _{2}F_{1}[−1] summation (cf. [35, (2.3.2.9), Appendix (III.5)]). Thus, Theorem 7 is proved. □

It would be easy to generalize the above theorem to trace generating functions of the type appearing in [31, Theorem 1; 17, sec. 5] by replacing x_{i} by q^{i} or q^{2i−1} in (3.13) and (3.14). We omit the details here.

Appendix

A1. Partitions and their diagrams. In Section 2 we already defined a partition to be a sequence λ = (λ_{1}, λ_{2}, …, λ_{r}) of integers such that λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{r} ≥ 0. A partition can be viewed geometrically, in terms of its Ferrers diagram. The Ferrers diagram of a partition λ = (λ_{1}, λ_{2}, …, λ_{r}) is an array of cells with r left-justified rows and λ_{i} cells in row i. Figure A.a shows the Ferrers diagram corresponding to (4, 3, 3, 1). We identify partitions with their Ferrers diagram. For example, if we say “the first row of the partition λ” then we mean “the first row of the Ferrers diagram of the partition λ.” The conjugate of a partition λ is the partition λ′ = (λ′_{1}, λ′_{2}, …, λ′_{λ_{1}}), where λ′_{j} is the length of the j-th column in the Ferrers diagram of λ.

. . . . .. . . . .^{.....}^{.....} ∗  . . . . .. . . . .. . . . .. . . . .^{.....}^{.....}^{.....} .....  ∗

a. Ferrers diagram b. skew Ferrers diagrams c. (4, 3, 3, 1)/(2, 1) d. (5, 4, 4, 2)/(3, 2, 1, 1)

Figure A

Given two partitions, half-partitions, or orthogonal (half-)partitions λ = (λ_{1}, λ_{2}, …) and μ = (μ_{1}, μ_{2}, …), we write λ + μ for the vector sum (λ_{1} + μ_{1}, λ_{2} + μ_{2}, …). We write μ ⊆ λ if μ_{i} ≤ λ_{i} for all i. Given two partitions λ, μ with μ ⊆ λ, the skew Ferrers diagram λ/μ consists of all cells that are contained in (the Ferrers diagram of) λ but not in (the Ferrers diagram of) μ. Figure A.b shows the skew Ferrers diagram (4, 3, 3, 1)/(2, 1). Of course, it also shows the skew Ferrers diagram (5, 4, 4, 2)/(3, 2, 1, 1). So, the notation for skew Ferrers diagrams is not unique. We might even allow vectors containing negative coordinates for denoting skew Ferrers diagrams, e.g., (3, 2, 2, 0)/(1, 0, −1, −1) for the same skew Ferrers diagram in Figure A.b, or vectors with half-integer coordinates, e.g., (9/2, 7/2, 7/2, 3/2)/(5/2, 3/2, 1/2, 1/2) for the same skew Ferrers diagram. We do all this freely in the text, without further notice. However, when we count columns of skew Ferrers diagrams λ/μ we do distinguish between the different notations for the same skew Ferrers diagram. Each column gets the number that it has as a column of λ. Thus, the first cell in the second row of the skew Ferrers diagram in Figure A.b is located in the second column of (4, 3, 3, 1)/(2, 1), see Figure A.c, in the third column of (5, 4, 4, 2)/(3, 2, 1, 1), see Figure A.d, in the first column of (3, 2, 2, 0)/(1, 0, −1, −1), in the 5/2-th column of (9/2, 7/2, 7/2, 3/2)/(5/2, 3/2, 1/2, 1/2), etc. A horizontal strip is a skew Ferrers diagram with no more than one cell in each of its columns. A vertical strip is a skew Ferrers diagram with no more than one cell in each of its rows.

A2. n-tableaux (ordinary tableaux). Let λ, μ be partitions with μ ⊆ λ. An n-tableau of shape λ, respectively of shape λ/μ, is a filling of the cells of λ, respectively λ/μ, with integers between 1 and n such that entries along rows are weakly increasing and entries along columns are strictly increasing. If we just say tableau instead of ntableau then we mean the same but without requiring that the entries are bounded above by n. Figure 4 shows a 6-tableau (7-tableau, …) of shape (8, 8, 5, 3, 2).

The weight x^{T} for an n-tableau T is defined by

x^{T} := x_{1}^{#(1’s in T)}x_{2}^{#(2’s in T)} ⋯ x_{n}^{#(n’s in T)}.  (A.1)

The vector (#(1’s in T), #(2’s in T), …, #(n’s in T)) of exponents in (A.1) is called the content of T and is denoted by con(T). For example, the weight and content of the tableau in Figure 4 are x_{1}^{4}x_{2}^{4}x_{3}^{5}x_{4}^{6}x_{5}^{5}x_{6}^{2} and (4, 4, 5, 6, 5, 2), respectively.

As is well-known (see [26, (5.12) with μ = 0; 34, Def. 4.4.1]), the irreducible general linear character (Schur function) s_{n}(λ; x) equals the generating function for all n-tableaux of shape λ,

s_{n}(λ; x) = _{∑_{T an n-tableau} of shape λ} x^{T} ,  (A.2)

with x^{T} as defined in (A.1).

A3. (2n)-symplectic tableaux. Let λ = (λ_{1}, λ_{2}, …, λ_{n}) be a partition. A (2n)- symplectic tableau of shape λ is a (2n)-tableau of shape 2λ = (2λ_{1}, 2λ_{2}, …, 2λ_{n}) such that columns 1, 2, columns 3, 4, …, columns 2λ_{1} − 1, 2λ_{1} form (2n)-symplectic admissible pairs.

Definition 1. A pair (C, D) of two columns of the length k ≤ n is called a (2n)-symplectic admissible pair if the following conditions are satisfied:

(a) Entries in C and D are between 1 and 2n and in strictly increasing order.

(b) If e is in D then 2n + 1 − e is not in D. The same holds for C.

(c) C arises from D by a (possibly empty) sequence of operations O of the following type: The operation O to be described applies only to columns E and integers e_{1}, e_{2} with e_{2} < e_{1} ≤ n, where e_{1} ∈ E, 2n + 1 − e_{2} ∈ E, and for all t between e_{2} and e_{1} either t or 2n + 1 − t belongs to E. The operation O itself consists of forming the new column O(E) out of E by replacing e_{1} by e_{2} and 2n + 1 − e_{2} by 2n + 1 − e_{1} and rearranging the new set of entries in strictly increasing order.

For example, Figure 2 displays a 12-symplectic tableau of shape (4, 4, 4, 4, 3, 3). There, the next-to-last column arises from the last by one operation, as described in item (c) of the Definition, with e_{1} = 4, e_{2} = 3.

Remark. Our description of (2n)-symplectic admissible pairs follows Lakshmibai [21]. The description in [24, Appendix A.2] is equivalent. Note that Littelmann’s rows are our columns.

There are a few observations that are immediate from the Definition.

Observation 1. C ≤ D, meaning that if the entries of C are c_{1}, c_{2}, …, c_{k} (from top to bottom) and those of D are d_{1}, d_{2}, …, d_{k} (from top to bottom), then c_{i} ≤ d_{i} for all i.

Observation 2. If (C, D) is a (2n)-symplectic admissible pair then the number of entries ≤ n in C is the same as that in D.

Observation 3. If C and D are columns of length n which satisfy (a), (b) in the Definition, C ≤ D, and have the same number of entries ≤ n, then (C, D) is a (2n)-symplectic admissible pair, i.e., condition (c) is satisfied automatically in this situation. This is due to the fact that a column of length n must contain either t or 2n + 1 − t, for all t = 1, 2, …, n. Hence, the most obvious way to transform D into C is a legal sequence of operations according to (c): Namely, apply the operation O described in (c) first with e_{1} the topmost entry of C and e_{2} the topmost entry of D (unless e_{1} = e_{2}), then apply O with e_{1} the next-to-the top entry of C and e_{2} the next-to-the-top entry of D, etc.

The weight (x^{±1})^{S} for a (2n)-symplectic tableau S is defined by

(x^{±1})^{S} := x_{1}^{\frac{1}{2}(#(1’s in S)−#((2n)’s in S))}x_{2}^{\frac{1}{2}(#(2’s in S)−#((2n−1)’s in S))}

⋯ x_{n}^{\frac{1}{2}(#(n’s in S)−#((n+1)’s in S))}. (A.3)

Again, the vector

\frac{1}{2}(#(1’s in S) − #((2n)’s in S), #(2’s in S) − #((2n − 1)’s in S),

…, #(n’s in S) − #((n + 1)’s in S))

of exponents in (A.3) is called the content of S and is denoted by con(S). For example, the weight and content of the tableau in Figure 2 are x_{3}x_{4}^{2}x_{5}x_{6}^{−2} and (0, 0, 1, 2, 1, −2), respectively.

It is a theorem (see [3, 4, 23]) that the irreducible symplectic character sp_{2n}(λ; x^{±1}) equals the generating function for all (2n)-symplectic tableaux of shape λ,

sp_{2n}(λ; x^{±1}) = _{∑_{S a (2n)-symplectic tableau} of shape λ}(x^{±1})^{S},  (A.4)

with (x^{±1})^{S} as defined in (A.3).

A4. (2n + 1)-orthogonal tableaux. Let λ = (λ_{1}, λ_{2}, …, λ_{n}) be a partition or half-partition. A (2n + 1)-orthogonal tableau of shape λ is a (2n)-tableau of shape 2λ = (2λ_{1}, 2λ_{2}, …, 2λ_{n}) such that columns 2λ_{1} − 1, 2λ_{1}, columns 2λ_{1} − 3, 2λ_{1} − 2, …, form (2n + 1)-orthogonal admissible pairs.

Definition 2. A pair (C, D) of two columns of the length k ≤ n is called a (2n + 1)-orthogonal admissible pair if the following conditions are satisfied:

(a) Entries in C and D are between 1 and 2n and in strictly increasing order.

(b) If e is in D then 2n + 1 − e is not in D. The same holds for C.

(c) C arises from D by a (possibly empty) sequence of operations that can be either operations of the type that are described in Definition 1.(c), or operations O of the following type: The operation O to be described applies only to columns E and an entry e of E, e > n, where for all t between n + 1 and e, n + 1 included, either t or 2n + 1 − t belongs to E. The operation O itself consists of forming the new column O(E) out of E by replacing e by 2n+1−e and rearranging the new set of entries in strictly increasing order.

For example, Figure 11 displays a 13-orthogonal tableau of shape (7/2, 7/2, 7/2, 7/2, 7/2, 1/2). There, the 4-th column arises from the 5-th by one operation as in item (c) of the Definition above, with e = 7, and by one operation as in Definition 1.(c), with e_{1} = 2, e_{2} = 1.

Remark. Again, our description of (2n + 1)-orthogonal admissible pairs follows Lakshmibai [21]. The description in [24, Appendix, Spin_{2m+1}-standard Young tableaux] is equivalent. Again, note that Littelmann’s rows are our columns.

We make similar observations here, also immediate from the Definition.

Observation 1. C ≤ D, meaning that if the entries of C are c_{1}, c_{2}, …, c_{k} (from top to bottom) and those of D are d_{1}, d_{2}, …, d_{k} (from top to bottom), then c_{i} ≤ d_{i} for all i.

Observation 2. If C and D are columns of length n which satisfy (a), (b) in the Definition, and C ≤ D, then (C, D) is a (2n + 1)-orthogonal admissible pair, i.e., condition (c) is satisfied automatically in this situation.

The weight (x^{±1})^{S} for a (2n + 1)-orthogonal tableau S is again defined by (A.3). Also here, the vector of exponents in (A.3) is called the content of S and is denoted by con(S).

It is a theorem (see [23]) that the irreducible orthogonal character so_{2n+1}(λ; x^{±1}) equals the generating function for all (2n + 1)-orthogonal tableaux of shape λ,

so_{2n+1}(λ; x^{±1}) = _{∑_{S a (2n+1)-orthogonal tableau} of shape λ}(x^{±1})^{S},  (A.5)

with (x^{±1})^{S} as defined in (A.3).

A5. (2n)-orthogonal tableaux. The definition of (2n)-orthogonal tableaux is the most intricate one. We provide the full definition for the sake of completeness. However, in the current paper we actually need only a special case, the one that is discussed in Observation 1 below. The reader who is only interested in this paper’s applications of (2n)-orthogonal tableaux can safely skip the full definition and move on directly to Observation 1.

We basically reproduce Littelmann’s description [24, Appendix, A.3], with a little modification in the description of (2n)-orthogonal admissible pairs, where we follow [21]. Note again that Littelmann’s rows are our columns.

Let λ = (λ_{1}, λ_{2}, …, λ_{n}) be an n-orthogonal partition or half-partition. A (2n)- orthogonal tableau of shape λ is a triple (S_{3}, S_{2}, S_{1}) of (2n)-tableaux of respective shapes ((λ_{n−1} + λ_{n})^{n}), ((λ_{n−1} − λ_{n})^{n}), and (2λ_{1} − 2λ_{n−1}, 2λ_{2} − 2λ_{n−1}, …, 2λ_{n−2} − 2λ_{n−1}), subject to conditions (0)–(4) below. Note that when S_{3}, S_{2}, and S_{1} are glued together, in that order, an array of shape (2λ_{1}, 2λ_{2}, …, 2λ_{n−2}, 2λ_{n−1}, 2λ_{n−1}) is obtained.

(0) If e is an element of a column of S_{3}, S_{2}, or S_{1} then 2n + 1 − e is not an element of the column.

(1) Columns 1, 2, columns 3, 4, …, columns 2λ_{1} − 2λ_{n−1} − 1, 2λ_{1} − 2λ_{n−1} of S_{1} form (2n)-orthogonal admissible pairs (see the Definition below). In addition, for i = 1, 2, …, λ_{1} − λ_{n−1} − 1, let the entries of the (2i)-th column of S_{1} be (from top to bottom) k_{1}, k_{2}, …, k_{s} and let the entries of the (2i + 1)-st column be (again, from top to bottom) l_{1}, l_{2}, …, l_{t}, s ≤ t. Then for all sequences 1 ≤ j_{1} < ⋯ < j_{q} ≤ s with

n + 1 − q ≤ k_{j_{1}} < ⋯ < k_{j_{q}} ≤ n + q

and

n + 1 − q ≤ l_{j_{1}} < ⋯ < l_{j_{q}} ≤ n + q

one has k_{j_{1}} + ⋯ + k_{j_{q}} ≡ l_{j_{1}} + ⋯ + l_{j_{q}} mod 2. (Note that this condition is empty if neither n nor n + 1 is an entry in one of the columns.)

(2) The number of entries > n in each column of S_{2} is odd. In addition, denote by R the column (of length n) that arises from the leftmost column of S_{1} by adding all integers e, n + 1 ≤ e ≤ 2n, that together with their “conjugate” 2n + 1 − e do not already appear in the leftmost column of S_{1}, arranging everything in strictly increasing order, and replacing the smallest added element, f say, by 2n + 1 − f in case that the number of entries > n would be odd otherwise. Denote by x the element of R that is closest to n + 1/2. To be precise, let k_{1}, k_{2}, …, k_{s} be the entries (from top to bottom) of the leftmost column of S_{1}. Then R consists of the entries k_{1}, …, k_{s}, l_{1}, …, l_{n−s−1}, x with the following properties:

2n ≥ l_{1} > ⋯ > l_{n−s−1} > n, l_{n−s−1} > x, l_{n−s−1} > 2n + 1 − x, l_{i} ≠ k_{j} and x ≠ k_{j} for all 1 ≤ i ≤ n − s − 1, 1 ≤ j ≤ s, and if e ∈ R then 2n + 1 − e ∉ R. Furthermore, if the number of integers strictly greater than n in R\{x} is odd then x > n else x ≤ n.

Let R′ be the column with entries (R\{x}) ∪ {2n + 1 − x} in increasing order. Then the concatenation S_{2} ∪ R′ forms a (2n)-tableau. By the concatenation S_{2} ∪ R′ we mean that R′ is glued from the right to S_{2} such that the topmost entries in each column are aligned in one row.

(3) The number of entries > n in each column of S_{3} is even. Denote by S′_{2} the tableau of shape ((λ_{n−1}−λ_{n}+1)^{n}) obtained from S_{2} as follows. The rightmost column of S′_{2} is R. Now assume that 1 ≤ i ≤ λ_{n−1} −λ_{n} and the (λ_{n−1} −λ_{n} +2−i)-th column of S′_{2} has already been defined. The (λ_{n−1} − λ_{n} + 1 − i)-th column of S′_{2} consists of the entries of the (λ_{n−1} − λ_{n} + 1 − i)-th column of S_{2} with one entry e replaced by 2n + 1 − e, arranged in strictly increasing order. The entry e to be chosen is the smallest possible such that rows will be weakly increasing (so that S′_{2} indeed becomes a tableau). Then the concatenation S_{3} ∪ S′_{2} is a (2n)-tableau. By the concatenation S_{3} ∪ S′_{2} we mean that S_{3} is glued to the left to S′_{2} such that the topmost entries in each column are aligned in one row.

Definition 3. A pair (C, D) of two columns of the length k ≤ n is called a (2n)-orthogonal admissible pair if the following conditions are satisfied:

(a) Entries in C and D are between 1 and 2n and in strictly increasing order.

(b) If e is in D then 2n + 1 − e is not in D. The same holds for C.

(c) C arises from D by a (possibly empty) sequence of operations that can be either operations of the type that are described in Definition 1.(c), or operations O of the following type: The operation O to be described applies only to columns E and entries e_{1}, e_{2} of E, n < e_{1} < e_{2}, where for all t between n+1 and e_{2}, n+1 included, either t or 2n+1−t belongs to E. The operation O itself consists of forming the new column O(E) out of E by replacing e_{1} by 2n + 1 − e_{1} and e_{2} by 2n + 1 − e_{2}, and rearranging the new set of entries in strictly increasing order.

Observation 1. (2n)-orthogonal tableaux of shape (λ_{n−1}, …, λ_{n−1}, λ_{n}) are just pairs (S_{3}, S_{2}) of (2n)-tableaux of respective shapes ((λ_{n−1} +λ_{n})^{n}) and ((λ_{n−1} −λ_{n})^{n}) such that each column of S_{3} or S_{2} does not contain 2n + 1 − e if it contains e, such that the number of entries > n in S_{2} is odd and each entry in the first row of S_{2} is ≤ n, such that the number of entries > n in S_{3} is even, and where the concatenation S_{3} ∪ S′_{2} is a (2n)-tableau, with S′_{2} the tableau that arises from S_{2} by replacing the topmost element, e_{i} say, in column i of S_{2} by its “conjugate” 2n+1−e_{i}, for all i = 1, 2, …, λ_{n−1} − λ_{n}, and by rearranging the columns in increasing order. For, in case of the above particular shape the tableau S_{1} is empty, hence R equals {n + 1, n + 2, …, 2n} or {n, n + 2, …, 2n}, depending on whether n is even or odd. Thus, R does not restrict S_{2} in item (2) above, except that for odd n it forces all the entries in the first row to be at most n. If n is even then all the entries in the first row have to be ≤ n as well. For, in each column the number of entries > n is odd, with n being even. This implies that the number of entries ≤ n has to be odd as well, in particular, it has to be at least 1. Finally, in item (3) above, when forming S′_{2} out of S_{2} always the smallest element in each column can be replaced by its “conjugate”.

The weight (x^{±1})^{S} for a (2n)-orthogonal tableau S is again defined by (A.3). Also here, the vector of exponents in (A.3) is called the content of S and is denoted by con(S).

It is a theorem (see [23]) that the irreducible orthogonal character so_{2n}(λ; x^{±1}) equals the generating function for all (2n)-orthogonal tableaux of shape λ,

so_{2n}(λ; x^{±1}) = _{∑_{S a (2n)-orthogonal tableau} of shape λ}(x^{±1})^{S},  (A.6)

with (x^{±1})^{S} as defined in (A.3).

A6. Littelmann’s decomposition rule and the Littlewood–Richardson rule. Littelmann’s rule [24] for the decomposition of the product of two general linear, two symplectic, or two special orthogonal characters can be stated uniformly. (In fact, it is also valid for the simple, simply connected algebraic groups of type G_{2} and E_{6}.) What is needed in the formulation of Littelmann’s theorem is the notion of (dominant) Weyl chamber associated to each of the characters.

The (dominant) Weyl chamber of type A, which is associated to s_{n}( .; x), is the set of points (cf. [6, p. 215])

{(x_{1}, x_{2}, …, x_{n}) : x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{n}}.  (A.7)

The (dominant) Weyl chamber of type C, which is associated to sp_{2n}( .; x^{±1}), is the set of points (cf. [6, p. 243, (16.5)])

{(x_{1}, x_{2}, …, x_{n}) : x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{n} ≥ 0}.  (A.8)

The (dominant) Weyl chamber of type B, which is associated to so_{2n+1}( .; x^{±1}), is the same set (A.8) of points (cf. [6, p. 272]).

Finally, the (dominant) Weyl chamber of type D, which is associated to so_{2n}( .; x^{±1}), is the set of points (cf. [6, p. 272])

{(x_{1}, x_{2}, …, x_{n}) : x_{1} ≥ x_{2} ≥ ⋯ ≥ |x_{n}|}.  (A.9)

Furthermore, if T is a tableau, then by T (ℓ) we denote the tableau that consists of the last ℓ columns of T.

Now we are in the position to state Littelmann’s theorem.

Theorem (Littelmann [24, Theorem. (a), p. 346]). Let χ_{n}( .) be any of the characters s_{n}( .; x), sp_{2n}( .; x^{±1}), so_{2n+1}( .; x^{±1}), or so_{2n}( .; x^{±1}). Then

χ_{n}(λ) · χ_{n}(μ) = ∑_{T} χ_{n}(λ + con(T)),  (A.10)

where the sum is over all corresponding tableaux (that is, n-tableaux in case χ_{n}( .) = s_{n}( .; x), (2n)-symplectic tableaux in case χ_{n}( .) = sp_{2n}( .; x^{±1}), etc.) of shape μ such that λ + con(T (ℓ)) is in the Weyl chamber of the corresponding type for all ℓ.

In case χ_{n}( .) = s_{n}( .; x) this rule translates to the classical Littlewood–Richardson rule (cf. [26, I, sec. 9; 34, (4.26) + Theorem 4.9.4]), which we want to describe next.

Definition 4. A Littlewood–Richardson filling (LR-filling) of shape ν/λ and content μ is an (ordinary) tableau F of shape ν/λ and content μ where the Littlewood– Richardson condition (LR-condition) is satisfied. The latter condition is the following

Read the entries of F row-wise from top to bottom and in each row from right to left. Then at any stage during the reading the number of 1’s is greater or equal the number of 2’s, which in turn is greater or equal the number of 3’s, etc.

Furthermore, define the Littlewood–Richardson coefficient LR_{λ,μ}^{ν} by

LR_{λ,μ}^{ν} = number of LR-fillings of shape ν/λ and content μ.  (A.11)

Then the Littlewood–Richardson rule reads as follows,

s_{n}(λ; x) · s_{n}(μ; x) = ∑_{ν} LR_{λ,μ}^{ν} s_{n}(ν; x).  (A.12)

The translation from (A.10) with χ_{n}( .) = s_{n}( .; x) to (A.12) proceeds as follows. It is basically the same idea as the one we use in the proof of Proposition 1. What we do is to construct, for any fixed λ, μ, ν, a bijection between n-tableaux T of shape μ, with ν = λ + con(T), and where λ + con(T (ℓ)) is in the Weyl chamber (A.7) of type A for all ℓ, and LR-fillings F of shape ν/λ and content μ. Clearly, this would establish the equivalence of (A.10) with χ_{n}( .) = s_{n}( .; x) and (A.12).

Given T as above, we construct a sequence F_{0}, F_{1}, …, F_{μ_{1}} of fillings by reading T column-wise, from right to left. The desired filling F will then be defined to be the last filling, F_{μ_{1}}. Define F_{0} to be the only filling of the shape λ/λ (which is of course the empty filling). Suppose that we already constructed F_{ℓ}. To obtain F_{ℓ+1}, we add for i = 1, 2, …, n an entry e to row i of F_{ℓ} if i is an entry occuring in the ℓ-th last column and the e-th row of T. As already announced, we define F to be F_{μ_{1}}.

A7. Littlewood’s branching rules. Here we quote the branching rules for the restriction of Schur functions to symplectic or orthogonal characters, which we use in Section 4.

Theorem (Littlewood). There holds (see [25, App., p. 295; 13, (3.8b); 39, Theorem 3.13]

s(λ; x) = ∑_{ν} sp(ν; x) ∑_{μ, μ′ even} LR_{μ,ν}^{λ}  (A.13)

(‘μ′ even’ means that all the columns of μ are even), and (see [25, p. 240, (II); 13, (3.8a); 39, Theorem 3.16])

s(λ; x) = ∑_{ν} o(ν; x) ∑_{μ, μ even} LR_{μ,ν}^{λ}  (A.14)

(‘μ even’ means that all the rows of μ are even), with LR_{μ,ν}^{λ} the Littlewood–Richardson coefficients as defined in (A.11).

References

1. A. J. Bracken and H. S. Green, Algebraic identities for parafermi statistics of given order, Nuovo Cimento 9A (1972), 349–365.

2. L. Carini, Combinatorial methods for computing plethysms of Schur functions, Ph. D. thesis, University of California, San Diego, 1995.

3. C. DeConcini, Symplectic standard tableaux, Adv. in Math. 34 (1979), 1–27.

4. C. DeConcini and C. Procesi, A characteristic-free approach to invariant theory, Adv. in Math. 21 (1976), 330–354.

5. M. Fulmek and C. Krattenthaler, Lattice path proofs for determinant formulas for symplectic and orthogonal characters, J. Combin. Theory Ser. A 77 (1997), 3–50.

6. W. Fulton and J. Harris, Representation Theory, Springer–Verlag, New York, 1991.

7. I. P. Goulden, A linear operator for symmetric functions and tableaux in a strip with given trace, Discrete Math. 99 (1992), 69—77.

8. Ph. Hanlon and S. Sundaram, On a bijection between Littlewood–Richardson fillings of conjugate shape, J. Combin. Theory Ser. A 60 (1992), 1–18.

9. M. Ishikawa and M. Wakayama, Minor summation formula for pfaffians, Linear and Multilinear Algebra 39 (1995), 285–305.

10. R. C. King, Modification rules and products of irreducible representations of the unitary, orthogonal, and symplectic groups, J. Math. Phys. 12 (1971), 1588–1598.

11. R. C. King, Weight multiplicities for the classical groups, Lect. Notes in Physics, vol. 50, Springer-Verlag, New York, 1975, pp. 490–499.

12. R. C. King, Branching rules for classical Lie groups using tensor and spinor methods, J. Phys. A: Math. Gen. 8 (1975), 429–449.

13. R. C. King, S-functions and characters of Lie algebras and superalgebras, Invariant theory and tableaux (D. Stanton, ed.), The IMA Volumes in Math. And Its Appl., Vol. 19, Springer–Verlag, New York, Berlin, Heidelberg, 1989, pp. 191–225.

14. D. E. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific J. Math. 34 (1970), 709—727.

15. K. Koike and I. Terada, Young–diagrammatic methods for the representation theory of the classical groups of type B_{n}, C_{n}, D_{n}, J. Algebra 107 (1987), 466–511.

16. K. Koike and I. Terada, Young diagrammatic methods for the restriction of representations of complex classical Lie groups to reductive subgroups of maximal rank, Adv. in Math. 79 (1990), 104–135.

17. C. Krattenthaler, Generating functions for shifted plane partitions, J. Statist. Plann. Inference 34 (1993), 197–208.

18. C. Krattenthaler, Non-crossing two-rowed arrays and summations for Schur functions, Proc. of the 5th Conference on Formal Power Series and Algebraic Combinatorics, Florence, 1993 (A. Barlotti, M. Delest, R. Pinzani, eds.), D.S.I., Università di Firenze, 1993, pp. 301–314.

19. C. Krattenthaler, The major counting of nonintersecting lattice paths and generating functions for tableaux, Mem. Amer. Math. Soc. 115, no. 552, Providence, R. I., 1995.

20. C. Krattenthaler, Non-crossing two-rowed arrays, in preparation.

21. V. Lakshmibai, Bases for fundamental representation of classical groups, C. R. Acad. Paris, Sér. I 302 (1986), 387–390.

22. V. Lakshmibai, C. Musili and C. S. Seshadri, Geometry of G/P – IV (Standard monomial theory for classical types), Proc. Indian Acad. Sci. 88A (1979), 279–362.

23. V. Lakshmibai and C. S. Seshadri, Geometry of G/P – V, J. Algebra 100 (1986), 462–557.

24. P. Littelmann, A generalization of the Littlewood–Richardson rule, J. Algebra 130 (1990), 328–368.

25. D. E. Littlewood, The theory of group characters and matrix representations of groups, Oxford University Press, Oxford, 1940.

26. I. G. Macdonald, Symmetric Functions and Hall Polynomials, second edition, Oxford University Press, New York/London, 1995.

27. S. Okada, Applications of minor summation formulas to rectangular-shaped representations of classical groups, J. Algebra (to appear).

28. R. A. Proctor, Shifted plane partitions of trapezoidal shape, Proc. Amer. Math. Soc. 89 (1983), 553–559.

29. R. A. Proctor, Bruhat lattices, plane partition generating functions, and minuscule representations, Europ. J. Combin. 5 (1984), 331–350.

30. R. A. Proctor, Odd symplectic groups, Invent. Math. 92 (1988), 307–332.

31. R. A. Proctor, New symmetric plane partition identities from invariant theory work of DeConcini and Procesi, Europ. J. Combin. 11 (1990), 289—300.

32. R. A. Proctor, A generalized Berele–Schensted algorithm and conjectured Young tableaux for intermediate symplectic groups, Trans. Amer. Math. Soc. 324 (1991), 655–692.

33. R. A. Proctor, Young tableaux, Gelfand patterns, and branching rules for classical groups, J. Algebra 164 (1994), 299–360.

34. B. E. Sagan, The symmetric group, Wadsworth & Brooks/Cole, Pacific Grove, California, 1991.

35. L. J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

36. R. P. Stanley, Symmetries of plane partitions, J. Combin. Theory A 43 (1986), 103–113; Erratum 44 (1987), 310.

37. J. R. Stembridge, Hall–Littlewood functions, plane partitions and the Rogers–Ramanujan identities, Trans. Amer. Math. Soc. 319 (1990), 469—498.

38. J. R. Stembridge, Nonintersecting paths, pfaffians and plane partitions, Adv. in Math. 83 (1990), 96—131.

39. S. Sundaram, Tableaux in the representation theory of the classical Lie groups, Invariant theory and tableaux (D. Stanton, ed.), The IMA Volumes in Math. And Its Appl., Vol. 19, Springer–Verlag, New York, Berlin, Heidelberg, 1989, pp. 191–225.

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.