% An AmS-TeX file for a 51-page document
% to be published in the Electronic Journal of Combinatorics
\define\paperno{R12}  % paper number
\documentstyle{amsppt}
\raggedbottom \vsize7.5truein
\input psfig \pssilent
%\define\psfig#1{\relax}
%%%% Definitions
\define\N{\bold{N}} \define\R{\bold{R}} \define\Z{\bold{Z}}
\define\C{\bold{C}} \define\0{\phantom{0}}
\define\Bee{\frak{B}} \define\Cee{\frak{C}} \define\Gee{\frak{G}}
\define\bee{\frak{b}} \define\cee{\frak{c}} \define\gee{\frak{g}}
\define\what{{\hat w}} \define\wcheck{{\check w}}
\define\wtilde{{\tilde w}}
\define\phihat{{\hat\varphi}} \define\phitld{{\tilde\varphi}}
\define\phichk{{\check\varphi}}
\define\nctwo{{[n]\choose2}} \define\rchoose{\atopwithdelims<>}
\define\nrctwo{{[n]\rchoose2}}
\define\taubar{\overline\tau} \define\barT{\overline T}
\define\kappabar{\overline\kappa}
\define\Pow{\operatorname{Pow}}
\define\today{\ifcase\month\or January\or February\or March\or April\or
May\or June\or July\or August\or September\or October\or November\or
December\fi\ \number\day, \number\year}
\let\<\langle \let\>\rangle
%%%% snoitinifeD
\refstyle{A}
\topmatter
\title Three generalizations of Weyl's denominator formula\endtitle
\author Todd Simpson\\
{\rm 7661 Tred Avon Circle, Easton, MD 21601, USA}\\
{\tt todo\@ora.nobis.com}\endauthor
\address Department of Mathematics,
Penn State University, University Park, PA 16802, USA\endaddress
\curraddr 7661 Tred Avon Circle,
Easton, MD 21601, USA\endcurraddr
\email todo\@ora.nobis.com\endemail
\thanks Partially supported by NSA Grants MDA904-90-H1010,
MDA904-92-H3043\endthanks
\keywords Weyl's denominator formula, Schur functions, partitions, digraphs
\endkeywords
\subjclass Primary 05A19\endsubjclass
\date Submitted: July 28, 1995; Accepted: March 15, 1996\enddate
\abstract
We give combinatorial proofs of three identities, each of which
generalizes Weyl's denominator formula for two of the three root
systems $B_n$, $C_n$, $D_n$. Two
of the three identities are due to S. Okada; the third appears in
the author's doctoral thesis, upon which this work is based.

Each of the identities we prove has a ``sum side'' and a
``product side''; both sides are polynomials in several commuting
indeterminates. We use weighted digraphs to represent the terms on
each side; the set of such digraphs that corresponds to the sum side
is a proper subset of the set corresponding to the product side.
\endabstract
\endtopmatter
% running heads
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1{\smcp the electronic journal of combinatorics 3 (1996), \#\paperno\hfill\folio}\fi}

\document
\leftline{{\it ``Why don't we pair 'em up in threes''}\quad---attributed to Yogi Berra}

\specialhead 1.\quad Introduction\endspecialhead

Our purpose is to give combinatorial proofs of three identities that
generalize Weyl's denominator formula. In this section, we provide
some background for our work, describe how the paper is organized, and
introduce some basic notation.

\head Background\endhead

Weyl's denominator formula (\cite{C}, Theorem 10.1.8) is a collection
of identities involving polynomials in any finite number $n$ of
commuting indeterminates. There is an identity for each root system
of rank $n$; a root system (\cite{H}, Chapter III) is a finite set of
vectors that satisfies certain axioms. Root systems correspond to
compact Lie groups and can be used to describe the characters of their
representations. For details of this correspondence, see \cite{W} or
\cite{BtD}. Weyl's character formula (\cite{W}, Kapitel IV, Satz 5;
\cite{BtD}, Chapter VI, (1.7)) gives a complete description of the
characters of irreducible representations of any compact, connected
Lie group. The formula expresses these characters as ratios of
polynomials, the denominators of which are given by Weyl's denominator
formula.

It suffices to prove Weyl's denominator formula for irreducible root
systems. A root system is irreducible if it cannot be written as a
disjoint union of two nonempty, mutually orthogonal subsets. With five
exceptions, every irreducible root system belongs to one of four
infinite families, denoted $A$, $B$, $C$, and $D$ (cf\. \cite{H}, 11.4,
12.1). The root system of rank $n$ in family $A$ is called $A_n$, and
similarly for the other families. Gessel \cite{G} was the first to
prove Weyl's formula combinatorially for an infinite family of root
systems. He gave a combinatorial proof of Vandermonde's determinant
formula
$$\sum_{\sigma\in S_n}(-1)^\sigma x_{\sigma(1)}^{n-1}
x_{\sigma(2)}^{n-2} \cdots x_{\sigma(n-1)}^{\0}
=\det\left[x_i^{n-j}\right]_{i,j=1}^n=\prod_{1\le i<j\le
n}(x_i-x_j),$$ where $S_n$ is the symmetric group on $\{1$, $2$,
$\ldots\,$, $n\}$ and $(-1)^\sigma$ denotes the sign of the
permutation $\sigma$. This identity is equivalent to Weyl's formula
for $A_{n-1}$. Later, Bressoud \cite{B} found combinatorial proofs
of Weyl's formula for $B_n$, $C_n$, and $D_n$.

Each of the three identities we shall prove implies Weyl's formula for
two of the three root systems $B_n$, $C_n$, $D_n$. Two of the
identities proved here are due to Okada \cite{O}, though one of them
is stated there without proof. The third identity appears in the
author's doctoral thesis \cite{S}, upon which this work is based.

\head Organization\endhead

In Section 2, we introduce the concepts and notation we need in order
to state our results. The results themselves are given in Theorems
2.2 and 2.4. We also show how one of the three identities implies
two cases of Weyl's formula.

We begin proving the identities in Section 3. Each of them has a ``sum
side'' and a ``product side.'' Our method is like that of \cite{G} and
\cite{B}, using weighted digraphs to represent the terms on each side
of each identity. Section 3 introduces digraph terminology and the
particular sets of digraphs and weight functions we shall use. We show
that the product side of each identity can be written as a sum of
weights of digraphs belonging to a particular set.

We claim that the sum side of each identity can be written as a sum of
weights of digraphs belonging to a proper subset of the set that
corresponds to the product side. In Section 4, we describe such a
subset for each of the identities to be proved. In Section 5, we state
and prove some technical lemmas to be used in the next two sections.

Sections 6 and 7 are where most of the work is done. To prove the
claim above, we show in Section 6 that the digraphs {\sl not\/}
belonging to the subset described in Section 4 have weights that add
to 0. In Section 7, we show that the digraphs that do belong to this
subset have weights that add to the sum side of the identity.

Finally, there is an Appendix, which contains some discussion of the
connection between the usual way of writing Weyl's denominator formula
and the way we write it in Section 2.

\head Notational Conventions\endhead

We write $\N$, $\N_0$, and $\Z$ for the sets of positive integers,
nonnegative integers, and all integers; $\R$ denotes the set of all
real numbers.

For any $n\in\N$, we define $[n]=\{1,2,\ldots,n\}$. If $X$ is any
set, then $X^n$ denotes the Cartesian product of $n$ copies of $X$. If
$X$ has an algebraic structure, then so does $X^n$; for instance, $\R^n$
is a real vector space and $\Z^n$ a free Abelian group.

We use cycle notation for permutations. For instance,
$\sigma=(1\,3\,4)$ means that $\sigma(1)=3$, $\sigma(3)=4$,
$\sigma(4)=1$, and $\sigma(i)=i$ otherwise. Permutations are composed
right-to-left.

Given a statement $A$, we define $\chi(A)$ to be $1$ if $A$ is true,
$0$ if $A$ is false.

\specialhead 2.\quad Statement of Results\endspecialhead

We begin this section by introducing partitions and Schur functions,
which we need in order to state Theorems 2.2 and 2.4.

\head Partitions\endhead

A {\sl partition\/} is a nonincreasing sequence $\lambda=(\lambda_1,
\lambda_2,\ldots\,)$ of nonnegative integers, with only finitely many
nonzero terms. The nonzero terms of $\lambda$ are called its {\sl
parts}. The number of parts of a partition $\lambda$ is its {\sl
length}, which we denote $\ell(\lambda)$. For any $n\ge\ell(\lambda)$,
we may identify $\lambda$ with the finite sequence $(\lambda_1,
\lambda_2,\ldots,\lambda_n)\in\N_0^n$. Thus the expressions $(5,4,2,1)$,
$(5,4,2,1,0,0,0)$, and $(5,4,2,1,0,\ldots\,)$ all describe the same
partition of length $4$. The {\sl weight\/} of a partition
$\lambda$, which we denote $|\lambda|$, is the sum of its parts. We say
that $\lambda$ is a partition of $n$ into $k$ parts if $|\lambda|=n$ and
$\ell(\lambda)=k$. For instance, $(5,4,2,1,0,\ldots\,)$ is a partition
of $12$ into $4$ parts. We denote the unique partition of length and
weight zero by $0$.

A useful idea in the study of partitions is that of the {\sl
Ferrers diagram\/} of a partition $\lambda$. This is the set
$D(\lambda)=\{(i,j)\in\N^2: 1\le i\le\ell(\lambda), 1\le j\le\lambda_i\}$.
One often thinks of $D(\lambda)$ as a left-justified array of unit
squares, in which the number of squares in the $i$th highest row is
$\lambda_i$. Figure 2.1 portrays the Ferrers diagram of
$(5,4,2,1)$.

\medpagebreak
\centerline{\psfig{figure=fig2.1.eps}}
\centerline{\smc Figure 2.1}
\medpagebreak

The {\sl rank\/} of a partition $\lambda$, denoted $p(\lambda)$,
is the largest $i$ such that $(i,i)\in D(\lambda)$.
Equivalently, $p(\lambda)=\max\{i:\lambda_i\ge i\}$. For example,
the partition $(5,4,2,1)$ has rank $2$.

If $\lambda$ is a partition, then the set $\{(j,i):(i,j)\in
D(\lambda)\}$ is the Ferrers diagram of a partition $\lambda'$, called
the {\sl conjugate\/} of $\lambda$. For example, the conjugate of
$(5,4,2,1)$ is $(4,3,2,2,1)$. We have $\ell(\lambda')=\lambda_1$,
$|\lambda'| =|\lambda|$, $p(\lambda')=p(\lambda)$, and
$\lambda''=\lambda$ for any partition $\lambda$. We say that $\lambda$ is
{\sl self-conjugate\/} if $\lambda=\lambda'$. An alternative definition
of $\lambda'$, which does not require Ferrers diagrams, is given by
$\lambda'_i=\max\{j:\lambda_j\ge i\}$.

We now define the {\sl Frobenius representation\/} of a
partition $\lambda$. For each $i\in[p(\lambda)]$, let $\alpha_i=\lambda_i-i$
and $\beta_i=\lambda'_i-i$. Both
$(\alpha_1,\ldots,\alpha_{p(\lambda)})$ and
$(\beta_1,\ldots,\beta_{p(\lambda)})$ are strictly decreasing
sequences of nonnegative integers. The Frobenius
representation of $\lambda$ is
$(\alpha_1,\ldots,\alpha_{p(\lambda)}\,|\,\beta_1,
\ldots,\beta_{p(\lambda)})$, or more concisely
$(\alpha\,|\,\beta)$. We note that $|\lambda|=p(\lambda)+
\sum_{i=1}^{p(\lambda)}(\alpha_i+\beta_i)$. And if the Frobenius
representation of $\lambda$ is $(\alpha\,|\,\beta)$, then
$\lambda'=(\beta\,|\,\alpha)$.

If $\lambda$ and $\mu$ are partitions, then $D(\mu)\subseteq
D(\lambda)$ if and only if $\mu_i\le\lambda_i$ for all $i\ge1$. It is
customary to identify partitions with their Ferrers diagrams, so one
usually writes $\mu\subseteq\lambda$ instead of $D(\mu)\subseteq
D(\lambda)$. The relation $\subseteq$ is a partial order on the set of
all partitions. In case $\mu\subseteq\lambda$, we define the {\sl skew
diagram\/} $\lambda-\mu$; this is simply the set-theoretic difference
$D(\lambda)\setminus D(\mu)$. One may think of it as an array of
unit squares in which the $i$th highest row is indented $\mu_i$ units
and contains $\lambda_i-\mu_i$ squares. For example, Figure 2.2
depicts the skew diagrams $(5,3,3,1)-(3,2,2,1)$ and $(4,2,2,1)-(3,2,1)$.

\medpagebreak
\centerline{\psfig{figure=fig2.2.eps}}
\centerline{\smc Figure 2.2}
\medpagebreak

Observe that no row of $(4,2,2,1)-(3,2,1)$ contains more than one
square. A skew diagram with this property is called a {\sl vertical strip}.
Evidently $\lambda-\mu$ is a vertical strip if $0\le\lambda_i-\mu_i\le 1$
for all $i$.

\head Schur Functions\endhead

Let $x_1,x_2,\ldots,x_n$ be commuting indeterminates and let
$\alpha=(\alpha_1,\ldots,\alpha_n)\in\N_0^n$. We denote by $x^\alpha$
the {\sl monomial} $x_1^{\alpha_1}x_2^{\alpha_2}\cdots
x_n^{\alpha_n}$. The ring $\Z[x_1,\ldots,x_n]$ of polynomials in
$x_1,\ldots,x_n$ with integer coefficients is generated as a free
$\Z$-module by the monomials.

The symmetric group $S_n$ acts on $\Z[x_1,\ldots,x_n]$ by permuting
indeterminates. We define
$x^{\sigma(\alpha)}=x_{\sigma(1)}^{\alpha_1}x_{\sigma(2)}^{\alpha_2}\cdots
x_{\sigma(n)}^{\alpha_n}$ for any $\sigma\in S_n$ and
$\alpha\in\N_0^n$. A polynomial $f=\sum_\alpha f_\alpha
x^\alpha\in\Z[x_1,\ldots,x_n]$ is said to be {\sl symmetric\/} if it
is invariant under this action of $S_n$, in other words, if
$$f(x_1,\ldots,x_n)=\sum_\alpha f_\alpha x^\alpha=\sum_\alpha
f_\alpha x^{\sigma(\alpha)}=f(x_{\sigma(1)},\ldots,x_{\sigma(n)})$$
for all $\sigma\in S_n$. A polynomial $a\in\Z[x_1,\ldots,x_n]$ such
that $$a(x_1,\ldots,x_n)=(-1)^\sigma
a(x_{\sigma(1)},\ldots,x_{\sigma(n)})$$ for all $\sigma\in S_n$ is
called {\sl antisymmetric}. If $a$ is antisymmetric, then $a=0$
whenever $x_i=x_j$ for some $i\ne j$. This implies that $a$ is
divisible by $$\Delta_n=\prod_{1\le i<j\le n}(x_i-x_j).$$ And since
$\Delta_n$ is itself antisymmetric, the quotient $a/\Delta_n$ is
symmetric.

Let $\lambda$ be a partition of length at most $n$ and let
$\delta=\delta_n=(n-1,\ldots,1,0)$. The polynomial
$$a_{\lambda+\delta}(x_1,\ldots,x_n)=\sum_{\sigma\in S_n} (-1)^\sigma
x^{\sigma(\lambda+\delta)}=\det\left[x_i^{\lambda_j+n-j}
\right]_{i,j=1}^{n}$$ is antisymmetric, and therefore
$$s_\lambda(x_1,\ldots,x_n)=\frac{a_{\lambda+\delta}(x_1,\ldots,x_n)}
{\Delta_n(x_1,\ldots,x_n)}=\frac{a_{\lambda+\delta}}
{a_\delta}\tag2.1$$ is a symmetric polynomial, called the {\sl Schur
function\/} corresponding to $\lambda$. Note that Vandermonde's
determinant formula implies the equality of the two
denominators in \thetag{2.1}.

\head Littlewood's Identities\endhead

In his study of the characters of representations of orthogonal
groups, Littlewood derived several identities involving Schur
functions (\cite{L}, p\. 238). Our results are generalizations of
three of these identities.

For any integer $t$, let $P_t(n)$ denote the set of all
partitions $$\lambda=
(\alpha_1+t,\alpha_2+t,\ldots,\alpha_p+t\,
|\,\alpha_1,\alpha_2,\ldots,\alpha_p)$$
such that $\ell(\lambda)\le n$. For instance, $(5,4,2,1)\in P_1(n)$
for all $n\ge4$. We write $P_t$ to denote the set of all partitions
belonging to $P_t(n)$ for sufficiently large $n$. If $t$ is odd, then
the partitions in $P_t$ all have even weight; if $t$ is even, then
$|\lambda|+p(\lambda)$ is even for all $\lambda\in P_t$.

We now state the three of Littlewood's Schur function identities that
our results generalize:
$$\align
\prod_{i=1}^n\,(1-x_i)\!\!\prod_{1\le i<j\le n}\!(1-x_ix_j)&=
\sum_{\lambda\in P_0(n)}
(-1)^{(|\lambda|+p(\lambda))/2}s_\lambda(x_1,\ldots,x_n);\tag2.2b\\
\prod_{i=1}^n\,(1-x_i^2)\!\!\prod_{1\le i<j\le n}\!(1-x_ix_j)&=
\sum_{\lambda\in P_1(n)}
(-1)^{|\lambda|/2}s_\lambda(x_1,\ldots,x_n);\tag2.2c\\
\prod_{1\le i<j\le n}\!(1-x_ix_j)&=
\sum_{\lambda\in P_{-\!1}(n)}
(-1)^{|\lambda|/2}s_\lambda(x_1,\ldots,x_n).\tag2.2d
\endalign$$
Multiply these by Vandermonde's determinant to obtain the
equivalent identities
$$\align
\prod_{i=1}^n\,(1-x_i)\!\!\prod_{1\le i<j\le n}\!(1-x_ix_j)(x_i-x_j)&=
\sum\Sb\lambda\in P_0(n)\\\sigma\in S_n\endSb
(-1)^{(|\lambda|+p(\lambda)/2)}
(-1)^\sigma x^{\sigma(\lambda+\delta_n)};\tag2.3b \\
\prod_{i=1}^n\,(1-x_i^2)\!\!\prod_{1\le i<j\le n}\!(1-x_ix_j)(x_i-x_j)&=
\sum\Sb\lambda\in P_1(n)\\\sigma\in S_n\endSb
(-1)^{|\lambda|/2}
(-1)^\sigma x^{\sigma(\lambda+\delta_n)};\tag2.3c \\
\prod_{1\le i<j\le n}\!(1-x_ix_j)(x_i-x_j)&=
\sum\Sb\lambda\in P_{-\!1}(n)\\\sigma\in S_n\endSb
(-1)^{|\lambda|/2}
(-1)^\sigma x^{\sigma(\lambda+\delta_n)}.\tag2.3d
\endalign$$

We think of the latter identities as cases of Weyl's denominator
formula. Macdonald (\cite{M}, p\. 46) observed that Weyl's formula for
the root system $B_n$ (respectively, $C_n$, $D_n$) implies
\thetag{2.2b} (respectively, \thetag{2.2c}, \thetag{2.2d}).
Bressoud's \cite{B} combinatorial proofs of Weyl's formula for $B_n$,
$C_n$, and $D_n$ are in fact proofs of \thetag{2.3b}, \thetag{2.3c},
and \thetag{2.3d}. See the Appendix for details on the relation
between Littlewood's identities and Weyl's formula.

\head Generalizations\endhead

We begin by defining the sets of partitions that will index the
terms on the ``sum sides'' of our generalizations of Weyl's formula:

\medpagebreak
$P_{-\!1,0}(n)$ consists of all $\lambda=(\alpha_1,\ldots,\alpha_p\,|\,
\beta_1,\ldots,\beta_p)$ such that $$n-1\ge\beta_1\ge\alpha_1\ge
\beta_2\ge\alpha_2\ge\cdots\ge\beta_p\ge\alpha_p.$$

$P_{0,1}(n)$ consists of all $\lambda=(\alpha_1,\ldots,\alpha_p\,|\,
\beta_1,\ldots,\beta_p)$ such that $$n\ge\beta_1+1\ge\alpha_1\ge
\beta_2+1\ge\alpha_2\ge\cdots\ge\beta_p+1\ge\alpha_p.$$

$P_{-\!1,1}(n)$ is the set of all $\lambda$ with $\ell(\lambda)\le n$
such that for some $\kappa\in P_{-\!1}(n)$, we have $0\le\lambda_i-
\kappa_i\le2$ for all $i\in [n]$ and $\{i\in [n]:\lambda_i-\kappa_i=1\}$
is a disjoint union of pairs $\{j,j+1\}$ with $\kappa_j=\kappa_{j+1}$.

\medpagebreak
An alternative definition of $P_{-\!1,1}(n)$ may be given in terms of
Ferrers diagrams. A {\sl domino\/} is a subset of $\Z^2$ of the form
$\{(i,j)$, $(i,j+1)\}$ or $\{(i,j)$, $(i+1,j)\}$. Just as we visualize
Ferrers diagrams as arrays of unit squares, we think of dominos as pairs
of squares having a common edge. A partition $\lambda$ of length at most
$n$ is in $P_{-\!1,1}(n)$ if and only if $\lambda-\kappa$
can be written as a disjoint union of dominos, with at most one domino
per row, for some $\kappa\in P_{-\!1}(n)$. In Figure 2.3, we have two
partitions $\lambda$ such that $\lambda-\kappa$ is a
disjoint union of dominos for $\kappa=(3,2,2,1)\in P_{-\!1}(4)$. The
diagram on the left shows that $(5,3,3,1)$ is in $P_{-\!1,1}(n)$ for any
$n\ge4$, because no row has more than one domino. This condition is
violated on the right, as indeed it must be, since the partition
$(4,4,3,1)$ is not in $P_{-\!1,1}(4)$.

\medpagebreak
\centerline{\psfig{figure=fig2.3.eps}}
\centerline{\smc Figure 2.3}
\medpagebreak

We have $P_i(n)\cup P_j(n)\subset P_{i,j}(n)$ for $-1\le i<j\le 1$.
We also note that $|\lambda|$ is even whenever $\lambda\in P_{-\!1,1}(n)$.

To state the first of our three generalizations, we shall need to
describe, for any partition $\lambda\in P_{-\!1,0}(n)$, the largest
$\mu\in P_{-\!1}(n)$ such that $\mu\subseteq\lambda$. To state the
second generalization, we shall need, given $\lambda\in P_{0,1}(n)$,
the largest $\nu\in P_0(n)$ such that $\nu\subseteq\lambda$. The
partitions $\mu$ and $\nu$ may be described in terms of their Ferrers
diagrams as follows.

For any partition $\lambda$, we define the following subsets of $\N^2$:
$$\align M(\lambda)&=\{(i,j-1):i<j,\;\lambda_i+\lambda_j\ge i+j-1\};\\
M'(\lambda)&=\{(j,i):(i,j-1)\in M(\lambda)\};\\
N(\lambda)&=\{(i,j):\lambda_i+\lambda_j\ge i+j\}.\endalign$$
The sets
$M(\lambda)\cup M'(\lambda)$ and $N(\lambda)$ are Ferrers diagrams of
partitions. Let $\mu=\mu(\lambda)$ and $\nu=\nu(\lambda)$ denote these
partitions, so that $D(\mu)=M(\lambda)\cup M'(\lambda)$ and
$D(\nu)=N(\lambda)$. There is some
$p\ge0$ and $\alpha_1>\alpha_2>\cdots>\alpha_p\ge1$ such that $$D(\mu)
=\bigcup_{i=1}^p\{(i,i),\ldots,(i,i+\alpha_i-1),(i+1,i),\ldots,
(i+\alpha_i,i)\}.$$ This shows that $\mu(\lambda)\in P_{-\!1}(n)$ for
all sufficiently large $n$.
Meanwhile, we have $(i,j)\in N(\lambda)$ if and only if $(j,i)\in
N(\lambda)$, which implies that $\nu(\lambda)$ is self-conjugate, or
equivalently that $\nu(\lambda)\in P_0(n)$ for large enough $n$.
The table in Figure 2.4
compares $\lambda_i+\lambda_j$ to $i+j-1$, where
$\lambda=(5,4,4,3,2)$. The diagram depicts $D(\mu)$, the bold line
separating $M(\lambda)$ from $M'(\lambda)$.

\medpagebreak
\centerline{\psfig{figure=fig2.4.eps}}
\centerline{\smc Figure 2.4}
\medpagebreak

The following lemma tells us that $\mu$ and $\nu$ have the properties
we need. We shall prove it in Section 7.

\proclaim{Lemma 2.1} {\rm (\cite{S}, Lemma 3.1.1) (a)} If $\lambda\in
P_{-\!1,0}(n)$, then $\mu(\lambda)\subseteq\lambda$, and we have
$\xi\subseteq\mu(\lambda)$ for any $\xi\in P_{-\!1}(n)$ such that
$\xi\subseteq\lambda$.

\rom{(b)} If $\lambda\in P_{0,1}(n)$, then $\nu(\lambda)\subseteq\lambda$,
and we have $\xi\subseteq\nu(\lambda)$ for any $\xi\in P_0(n)$ such that
$\xi\subseteq\lambda$.\endproclaim

Given any partition $\lambda$, we define
$$\align y(\lambda)&=|\{(i,j):\,i<j,\lambda_i+\lambda_j=i+j-1\}|\\
\noalign{\hbox{and}}
z(\lambda)&=|\{(i,j):\,i<j,\lambda_i+\lambda_j=i+j\}|.\endalign$$ We
are ready to state the first two of our three generalizations of
Weyl's formula:

\proclaim{Theorem 2.2} {\rm (\cite{S}, Theorem 3.1.2)} We have
$$\prod_{1\le i\le n} \!\!(1-tx_i)\!\!\!\prod_{1\le i<j\le
n}\!\!\!(1-x_ix_j)(x_i-x_j)\tag BD$$
$$=\!\!\!\!\sum\Sb\lambda\in P_{-\!1,0}(n)\\\sigma\in S_n\endSb
\!\!\!\!(-1)^{|\lambda|-|\mu|/2}\,t^{|\lambda|-|\mu|}(1-t^2)^{y(\lambda)}
(-1)^\sigma x^{\sigma(\lambda+\delta_n)}$$
and
$$\prod_{1\le i\le n}\!\!(1-x_i)(1+tx_i)\!\!\!\prod_{1\le i<j\le n}
\!\!\!(1-x_ix_j)(x_i-x_j)\tag BC$$
$$=\!\!\sum\Sb\lambda\in P_{0,1}(n)\\\sigma\in S_n\endSb
\!\!\!(-1)^{(|\nu|+p(\nu))/2}\,t^{|\lambda|-|\nu|}
(1-t)^{\chi(\exists i,\lambda_i=i)}(1-t^2)^{z(\lambda)}
(-1)^\sigma x^{\sigma(\lambda+\delta_n)}$$
for all $n\ge1$.
\endproclaim

In \cite{O}, Okada proves an identity (Lemma 3.5) equivalent to
\thetag{BC}. He also states without proof an identity equivalent to
\thetag{BD}.

At the end of this section, we shall show how \thetag{BD} specializes
to \thetag{2.3d} at $t=0$ and to \thetag{2.3b} at $t=1$. A similar
argument shows that \thetag{BC} gives us \thetag{2.3b} and
\thetag{2.3c} at $t=0$ and $t=1$ respectively.

In order to state the third of our generalizations of Weyl's formula,
we shall need, given $\lambda\in P_{-\!1,1}(n)$, the largest
$\kappa\in P_{-\!1}(n)$ such that $\kappa\subseteq\lambda$ and
$\lambda-\kappa$ is a disjoint union of dominos with no more than
one domino per row. We have not found an elegant description of
this partition $\kappa$ like those of $\mu$ and $\nu$ above.

Given a partition $\lambda$, let $K(\lambda)$ be the set of all
partitions $\eta\subseteq\lambda$ such that: $\eta\in P_{-\!1}(n)$ for
some $n$, and $\lambda-\eta$ is a disjoint union of dominos with no
more than one domino in any one row of $D(\lambda)$. Observe that
$\lambda\in P_{-\!1,1}(n)$ for some $n$ if and only if
$K(\lambda)\ne\emptyset$.

Figure 2.5 shows that $\lambda=(6,5,5,3,3,2)$ is in $P_{-\!1,1}(n)$ for
$n\ge6$. The partitions $(3,2,1\,|\,4,3,2)$ and $(3,1,0\,|\,4,2,1)$ belong
to $K(\lambda)$. On the other hand, $\eta=(3,2,0\,|\,4,3,1)$ is not in
$K(\lambda)$, even though $0\le\lambda_i-\eta_i\le2$ for all $i$, because
$\lambda-\eta$ cannot be written as a disjoint union of
dominos.

\medpagebreak
\centerline{\psfig{figure=fig2.5.eps}}
\centerline{\smc Figure 2.5}
\medpagebreak

Lemma 2.3 tells us that there is a largest partition in $K(\lambda)$
for any $\lambda\in P_{-\!1,1}(n)$. We shall prove it in Section 7.

\proclaim{Lemma 2.3} {\rm (\cite{S}, Lemma 3.1.3)} For any $\lambda\in
P_{-\!1,1}(n)$, there is a partition $\kappa=\kappa(\lambda)\in
K(\lambda)$ such that $\eta\subseteq \kappa$ for all $\eta\in
K(\lambda)$. \endproclaim

The role $\kappa$ will play in our third generalization is like that
of $\mu$ in \thetag{BD} and of $\nu$ in \thetag{BC}. We remark that
$\kappa$ is defined only for partitions in $P_{-\!1,1}(n)$, whereas
the definitions of $\mu$ and $\nu$ make sense for any partition.

Given $\lambda\in P_{-\!1,1}(n)$, let $q(\lambda)$ be the number of
``horizontal'' dominos in $\lambda-\kappa$. Equivalently, $q(\lambda)$
is the cardinality of the set $\{i\in[n]:\lambda_i-\kappa_i=2\}$. For
instance, with $\lambda$ as in Figure 2.5, we have
$\kappa=(3,2,1\,|\,4,3,2)$ and $q(\lambda)=2$. We can now state our
third generalization of Weyl's formula:

\proclaim{Theorem 2.4} {\rm (\cite{S}, Theorem 3.1.4)} We have
$$\prod_{1\le i\le n}\!\!(1-tx_i^2)\!\!\!\prod_{1\le i<j\le n}
\!\!\!(1-x_ix_j)(x_i-x_j)\tag CD$$
$$=\!\!\sum\Sb\lambda\in P_{-\!1,1}(n)\\\sigma\in S_n\endSb
\!\!\!(-1)^{|\kappa|/2+q(\lambda)}\,t^{(|\lambda|-|\kappa|)/2}
(1-t)^{\chi(\exists i,\lambda_i=i)}(1-t^2)^{z(\lambda)}
(-1)^\sigma x^{\sigma(\lambda+\delta_n)}$$
for any $n\ge1$.
\endproclaim

We obtain \thetag{2.3d} from \thetag{CD} by setting $t=0$ and \thetag{2.3c}
by setting $t=1$.

\head Obtaining \thetag{2.3d} and \thetag{2.3b} from \thetag{BD}\endhead

If $t=0$, then the product side of \thetag{BD} is the same as that of
\thetag{2.3d}. The sum side of \thetag{BD}, meanwhile, is
$$\sum\Sb\lambda\in P_{-\!1,0}(n):\,|\lambda|=|\mu|\\\sigma\in S_n\endSb
\!\!\!\!(-1)^{|\lambda|/2}(-1)^\sigma
x^{\sigma(\lambda+\delta_n)}.$$ Lemma 2.1(a) tells us that
$\mu\subseteq\lambda$ for any $\lambda\in P_{-\!1,0}(n)$. If
$\mu\subseteq\lambda$ and $|\lambda|=|\mu|$, then clearly
$\lambda=\mu$. Therefore the latter sum is taken over $P_{-\!1}(n)$;
it is the sum side of \thetag{2.3d}.

Now suppose $t=1$. The product sides of \thetag{BD} and \thetag{2.3b}
coincide, whereas the sum side of \thetag{BD} is $$\sum\Sb\lambda\in
P_{-\!1,0}(n):\,y(\lambda)=0\\\sigma\in S_n\endSb
\!\!\!\!(-1)^{|\lambda|-|\mu|/2} (-1)^\sigma
x^{\sigma(\lambda+\delta_n)}.$$ If $\lambda\in P_{-\!1,0}(n)$ and
$y(\lambda)=0$, then the quantities $|\lambda_i-i+{1\over2}|$, $i\in
[n]$, are distinct. And they are not larger than $n-{1\over2}$, since
$\lambda_1\le n$. In this situation, Lemma A.1 (in the Appendix)
implies that $\lambda\in P_0(n)$, and it remains only to show that
$|\lambda|-{|\mu|\over2}={|\lambda|+p(\lambda)\over2}$, or
equivalently, $|\lambda|-|\mu|=p(\lambda)$. To this end, let
$p=p(\lambda)$ and $q=p-\chi(\lambda_p=p)$. Then for $1\le i\le q$ and
$i<j\le\lambda_i$, we have $(i,j)\in D(\lambda)$, and since
$\lambda=\lambda'$, we have $(j,i)\in D(\lambda)$. Therefore
$\lambda_i\ge j$, $\lambda_j\ge i$, $\lambda_i +\lambda_j>i+j-1$, and
we have $(i,j-1),(j,i)\in D(\mu)$. Meanwhile, for $1\le i\le p$ and
$j\ge\lambda_i+1$, we have $\lambda_i+\lambda_j<i+j-1$. This means that
if $\lambda=(\alpha_1,\ldots,\alpha_p\,|\,\alpha_1, \ldots,\alpha_p)$,
then $\mu=(\alpha_1-1,\ldots,\alpha_q-1\,|\,\alpha_1,
\ldots,\alpha_q)$. We conclude that $|\lambda|-|\mu|=p$ as required.

\specialhead 3.\quad The Product Sides\endspecialhead

We shall now introduce the digraphs and weight functions to be used
in proving \thetag{BD}, \thetag{BC}, and \thetag{CD}.

Let $V$ be a set, whose elements we call {\sl vertices}. We shall say
that a subset $\gee$ of $V\times V$ is a {\sl digraph\/} on $V$ if it
has the following two properties:

\smallpagebreak
For all $i\in V$, $(i,i)\notin \gee$.

If $(i,j)\in \gee$, then $(j,i)\notin \gee$.
\smallpagebreak

\noindent We call the elements of $\gee$ {\sl arcs\/}; we say that
$(i,j)$ is an arc from $i$ to $j$. Observe that by our definition, a
digraph cannot have an arc from a vertex to itself, nor can it have
more than one arc between two distinct vertices. We say that $\gee$ is
{\sl complete\/} if it has an arc between any two distinct
vertices. In other words, $\gee$ is complete if we have either
$(i,j)\in \gee$ or $(j,i)\in \gee$ whenever $i\ne j$. Complete
digraphs on finite sets of vertices are often called {\sl
tournaments}.

We shall work exclusively with digraphs on finite vertex sets. Such
digraphs can be visualized, using points in the plane to represent
vertices and arrows from one point to another to represent arcs. In
Figure 3.1, $\gee_1=\{(a,d)$, $(b,a)$, $(b,d)$, $(e,c)\}$ and
$\gee_2=\{(1,2)$, $(1,3)$, $(2,3)$, $(3,4)$, $(4,1)$, $(4,2)\}$ are
digraphs on $\{a,b,c,d,e\}$ and $[4]$ respectively.

\medpagebreak
\centerline{\psfig{figure=fig3.1.eps}}
\centerline{\smc Figure 3.1}
\medpagebreak

The {\sl out-degree\/} of a vertex $i$ in a digraph $\gee$ is the
number of arcs in $\gee$ from $i$ to other vertices. We denote this
number by $o(i,\gee)$. In Figure 3.1, for example, $o(b,\gee_1)=2$ and
$o(3,\gee_2)=1$. A {\sl path\/} from $i$ to $j$ is a sequence of arcs
$(i,k_1)$, $(k_1,k_2)$, $\ldots\,$, $(k_{n-1},j)$ in $\gee$. The {\sl
length\/} of a path is the number of arcs it contains. A {\sl cycle\/}
is a path from a vertex to itself. By our definition of digraphs, any
cycle must have length at least $3$. We say $\gee$ is {\sl
transitive\/} if it contains no cycles. For instance, $\gee_1$ is
transitive, but $\gee_2$ has a cycle. If $\gee$ is a digraph on $V$
and $W\subseteq V$, then $\gee\cap(W\times W)$ is a digraph on $W$,
the {\sl restriction\/} of $\gee$ to $W$. For example, the restriction
of $\gee_2$ to $[3]$ is $\{(1,2),(1,3),(2,3)\}$.

We are ready to define the sets of digraphs we shall use in our proofs
of Theorems 2.2 and 2.4. Given a positive integer $n$, let
$V_n=\{-n,\ldots,-1,0,1,\ldots,n\}$. Define sets $\Cee_n$ and $\Bee_n$
of digraphs on $V_n$ as follows:

\medpagebreak
$\Cee_n$ consists of all complete digraphs $\cee$ on $V_n$ such that
$(-j,-i)\in\cee$ whenever $(i,j)\in\cee$.

$\Bee_n$ consists of all digraphs $\bee$ on $V_n$ such that: for all
$i\in V_n$, $(i,-i)\notin\bee$; for all $i,j\in V_n$ with $j\ne\pm i$,
either $(i,j)\in\bee$ or $(j,i)\in\bee$; and $(-j,-i)\in\bee$ whenever
$(i,j)\in\bee$. (Given $\cee\in\Cee_n$, the digraph $\bee$ we obtain
from $\cee$ by deleting all arcs of the form $(i,-i)$ is in $\Bee_n$.)
\medpagebreak

We shall use $\Bee_n$ in our proof of \thetag{BD} and $\Cee_n$ in our
proofs of \thetag{BC} and \thetag{CD}. Observe that for any
$\gee\in\Bee_n\cup\Cee_n$, the restriction of $\gee$ to $[n]$ is a
complete digraph, which we call the {\sl positive
subtournament\/} of $\gee$ and denote by $\gee^+$.

Our proofs begin with the assignment of a weight to each digraph in
the appropriate set. Given a digraph $\gee$, we assign a weight
$w(i,j)$ to each arc $(i,j)$ in $\gee$. The product of all these
weights is the weight of $\gee$:
$w(\gee)=\prod_{(i,j)\in\gee}w(i,j)$. We use the following functions
to assign weights to arcs:
$$\align\what(i,j)&=(-1)^{\chi(i>|j|)}(x_it^{\chi(j=0)})^{\chi(i>0)};\\
\wtilde(i,j)&=(-1)^{\chi(i>|j|)}(x_it^{\chi(j=-i)})^{\chi(i>0)};\\
\wcheck(i,j)&=(-1)^{\chi(i>|j|)}
(x_it^{\chi(j=0\text{ or }j=-i)/2})^{\chi(i>0)}.\endalign$$
We remark that if $p\le0$, then $\what(p,q)=\wtilde(p,q)=\wcheck(p,q)=1$
for all $q$, and that if $p$ and $q$ are nonzero and $q\ne-p$, then
$\what(p,q)=\wtilde(p,q)=\wcheck(p,q)$. For example,
if $\gee$ is the digraph in $\Bee_3$ shown in Figure 3.2,
then $\what(\gee)= tx_1^4x_2^{\0}x_3^3$.

\medpagebreak
\centerline{\psfig{figure=fig3.2.eps}}
\centerline{\smc Figure 3.2}
\medpagebreak

We can now write the product sides of \thetag{BD},
\thetag{BC}, and \thetag{CD} as sums indexed by digraphs:
$$\align\prod_{1\le i\le n}\!\!(1-tx_i)\!\!\!\prod_{1\le i<j\le
n}\!\!\!(1-x_ix_j)(x_i-x_j)&=\sum_{\bee\in\Bee_n}\what(\bee),\tag3.1bd\\
\prod_{1\le i\le n}\!\!(1-x_i)(1+tx_i)\!\!\!\prod_{1\le
i<j\le n}\!\!\!(1-x_ix_j)(x_i-x_j)&=\sum_{\cee\in\Cee_n}\wtilde(\cee),
\tag3.1bc\\
\prod_{1\le i\le n}\!\!(1-tx_i^2)\!\!\!\prod_{1\le i<j\le
n}\!\!\!(1-x_ix_j)(x_i-x_j)&=\sum_{\cee\in\Cee_n}\wcheck(\cee).
\tag3.1cd
\endalign$$

To prove \thetag{3.1cd}, consider a digraph $\cee\in\Cee_n$. For
each pair $i,j$ of integers with $1\le i<j\le n$, we have either
$(i,j)$ and $(-j,-i)$ in $\cee$, contributing $x_i$ and $1$ to
$\wcheck(\cee)$, or we have $(j,i)$ and $(-i,-j)$ in $\cee$,
contributing $-x_j$ and $1$. We have either $(i,-j),(j,-i)\in\cee$,
contributing $-x_ix_j$ to $\wcheck(\cee)$, or $(-i,j),(-j,i)\in\cee$,
contributing $1$. For each $i$ with $1\le i\le n$, we have either
$(i,-i)$ or $(-i,i)$, contributing either $t^{1/2}x_i$ or $1$, and
either $(i,0),(0,-i)$ or $(0,i),(-i,0)$, contributing either
$-t^{1/2}x_i$ or $1$. This accounts for all the arcs of $\cee$. We
conclude that the sum of $\wcheck(\cee)$ as $\cee$ ranges over
$\Cee_n$ is equal to
$$\prod_{1\le i\le n}\!\!(1-t^{1/2}x_i)(1+t^{1/2}x_i)\!\!\!\prod_{1\le
i<j\le n}\!\!\!(1-x_ix_j)(x_i-x_j),$$ which is equal to the product side
of \thetag{CD}. The proofs of \thetag{3.1bd} and \thetag{3.1bc} are
similar.

\specialhead 4.\quad The Sum Sides\endspecialhead

To describe the subsets of $\Bee_n$ and $\Cee_n$ that correspond to
the sum sides of \thetag{BD}, \thetag{BC}, and \thetag{CD}, we need to
study these sets of digraphs in more detail. The positive subtournaments
of digraphs in $\Bee_n\cup\Cee_n$ will be important in this study, and
we shall also use partially ordered sets.

\head Transitive Tournaments and Permutations\endhead

Suppose $\gee$ is a digraph on $V$ such that no two vertices of $V$
have the same out-degree in $\gee$. We claim that $\gee$ is complete
and transitive, or in other words, that it is a transitive
tournament. This is obvious (and vacuous) if $|V|=1$. Otherwise,
observe that the possible out-degrees of any vertex in any digraph on
$V$ are $0$, $1$, $\ldots\,$, $|V|-1$; therefore $\gee$ must have
exactly one vertex of each possible out-degree. If $i$ is the vertex
whose out-degree is $|V|-1$, then $i$ is not part of any cycle and
there is an arc between $i$ and any other vertex in $\gee$. The
restriction of $\gee$ to $V\setminus\{i\}$ has no two vertices with
the same out-degree, and if it is complete and transitive, then so is
$\gee$. Conversely, suppose $\gee$ is complete and transitive. If
$(i,j)\in \gee$, then we have $(i,k)\in \gee$ whenever $(j,k)\in
\gee$. Since $(j,j)$ is not in $\gee$, we see that
$\{k:(j,k)\in\gee\}$ is a proper subset of $\{k:(i,k)\in\gee\}$. We
conclude that $o(i,\gee)>o(j,\gee)$. This means that no two vertices
have the same out-degree in $\gee$. We have shown that a digraph
$\gee$ on (a finite set) $V$ is complete and transitive if and only if
$\{o(i,\gee):i\in V\}=\{0,1,\ldots,|V|-1\}$.

The above result allows us to identify transitive tournaments
$\gee$ on $[n]$ with permutations $\sigma\in S_n$. Given such an $\gee$,
define $\sigma(i)$ to be the unique $j$ such that $o(j,\gee)=n-i$. Then
$\gee=\{(\sigma(i), \sigma(j)):1\le i<j\le n\}$. This correspondence
between permutations and digraphs is of great importance here and in
\cite{G} and \cite{B}.

\head Alternative Description of $\gee$ When $\gee^+$ is Transitive\endhead

Let $\gee$ be a digraph in $\Bee_n\cup\Cee_n$ whose positive
subtournament $\gee^+$ is transitive. There is a unique permutation
$\sigma=\sigma(\gee)\in S_n$ such that $o(\sigma(i),\gee^+)=n-i$ for
each $i\in [n]$. Observe that $\sigma$ completely determines all arcs
in $\gee$ between two positive vertices or between two negative
vertices. We now introduce some sets that, together with $\sigma$,
will determine all arcs in $\gee$ not between two positive or two
negative vertices.

First, we introduce $\nctwo$ (``$[n]$ choose 2'') and $\nrctwo$
(``$[n]$ repeat-choose 2'' or ``$[n]$ choose 2 with repetition''):
$\nctwo=\{(i,j):1\le i<j\le n\}$ and $\nrctwo=\{(i,j):1\le i\le j\le
n\}$. Then we define
$$\align\tau=\tau(\gee)&=
\tsize\{(i,j)\in\nctwo:(\sigma(i),-\sigma(j))\in\gee\},\\
\taubar=\taubar(\gee)&=\tau(\gee)\cup\{(i,i):(\sigma(i),0)\in\gee)\},\\
\omega_0=\omega_0(\gee)&=\{i:(\sigma(i),0)\in\gee\},\\
\noalign{\hbox{and for $\gee\in\Cee_n$,}}
\omega_\pm=\omega_\pm(\gee)&=\{i:(\sigma(i),-\sigma(i))\in\gee\}.\endalign$$
We shall use these sets throughout Sections 6 and 7. For instance, if
$\gee$ is the digraph in Figure 3.2, then $\gee^+$ is transitive with
$\sigma(\gee)=(2\,3)$, $\taubar(\gee)=\{(1,2)$, $(1,3)$, $(2,2)\}$,
and $\omega_0(\gee)=\{2\}$.

We are going to define a partial order on $\nctwo$ and
$\nrctwo$. Recall (\cite{St}, Chapter 3) that a partial order is a
binary relation $\preceq$ that is reflexive ($x\preceq x$ for any
$x$), antisymmetric (if $x\preceq y$ and $y\preceq x$, then $x=y$),
and transitive (if $x\preceq y$ and $y\preceq z$, then $x\preceq
z$). One writes $x\prec y$ if $x\preceq y$ and $x\ne y$; also, if
$x\preceq y$ or $x\prec y$, one may write $y\succeq x$ or $y\succ
x$. A set on which a partial order is defined is called a partially
ordered set, or {\sl poset\/} for short.

Let $P$ be a poset with partial order $\preceq$. A subset $Q$ of $P$
is an {\sl order ideal\/} with respect to $\preceq$ if we have $x\in
Q$ whenever $x\preceq y$ and $y\in Q$. A {\sl dual order ideal\/} is a
subset $Q$ of $P$ such that $y\in Q$ whenever $x\preceq y$ and $x\in
Q$. Evidently $Q$ is a dual order ideal of $P$ if and only if
$P\setminus Q$ is an order ideal.

Given ordered pairs of integers $(i,j)$ and $(k,l)$, we say that
$(i,j)\preceq (k,l)$ if and only if $i\le k$ and $j\le l$. It is easy
to see that $\preceq$ is a partial order on $\nctwo$ and $\nrctwo$. We
shall visualize $\nctwo$ and $\nrctwo$ as in Figure 4.1, which shows
$T_1=\{(1,2)$, $(2,3)\}\subseteq{[3]\choose2}$ and $T_2=\{(1,1)$,
$(1,2)$, $(2,2)\}\subseteq{[3]\rchoose2}$. Observe that $T_2$ is an
order ideal and $T_1$ is not.

\medpagebreak
\centerline{\psfig{figure=fig4.1.eps}}
\centerline{\smc Figure 4.1}
\medpagebreak

The map $\bee\mapsto(\sigma(\bee),\taubar(\bee))$ is a bijection of
$\{\bee\in\Bee_n:\bee^+\text{ transitive}\}$ onto
$S_n\times\Pow\nrctwo$, where $\Pow X$ denotes the set of all subsets
of $X$. We also have bijections
$\cee\mapsto(\sigma(\cee),\taubar(\cee), \omega_\pm(\cee))$ and
$\cee\mapsto(\sigma(\cee),\tau(\cee),\omega_0(\cee),
\omega_\pm(\cee))$ of $\{\cee\in\Cee_n:\cee^+\text{ transitive}\}$
onto $S_n\times\Pow\nrctwo\times\Pow[n]$ and
$S_n\times\Pow\nctwo\times\Pow[n] \times\Pow[n]$ respectively. In
Chapter 2 of \cite{S}, it is shown that $\bee\in \Bee_n$ is transitive if
and only if $\bee^+$ is transitive and $\taubar(\bee)$ is an order ideal
of $\nrctwo$. Similarly, $\cee\in\Cee_n$ is transitive if and only if
$\cee^+$ is transitive, $\taubar(\cee)$ is an order ideal of $\nrctwo$,
and $\omega_0(\cee)=\omega_\pm(\cee)$.

The last concept we need in this section is that of interchangeability.
Let $T$ be a subset of $\nctwo$ or of $\nrctwo$ and let $i$ and $j$ be
distinct integers in $[n]$. Suppose without loss of generality that
$i<j$. We say $i$ and $j$ are {\sl interchangeable\/} in $T$ if the
following conditions hold:

\smallpagebreak
For $1\le k<i$, $(k,i)\in T$ if and only if $(k,j)\in T$.

For $i<k<j$, $(i,k)\in T$ if and only if $(k,j)\in T$.

For $j<k\le n$, $(i,k)\in T$ if and only if $(j,k)\in T$.

$(i,i)\in T$ if and only if $(j,j)\in T$ (this is vacuous if
$T\subseteq\nctwo$).
\smallpagebreak

We are ready to define the sets of digraphs that will index the sum
sides of our three generalizations of Weyl's formula. These sets are
$\Bee_n^*\subset\Bee_n$, $\Cee_n^*\subset\Cee_n$, and
$\Cee_n^{**}\subset\Cee_n$, defined as follows:

\medpagebreak
$\bee\in\Bee_n^*$ if $\bee^+$ is transitive, $\tau(\bee)$ is an order
ideal of $\nctwo$, and
$$o(\sigma(1),\bee)>o(\sigma(2),\bee)>\cdots> o(\sigma(n),\bee).$$

$\cee\in\Cee_n^*$ if $\cee^+$ is transitive, $\taubar(\cee)$ is an
order ideal of $\nrctwo$, and
$$o(\sigma(1),\cee)>o(\sigma(2),\cee)>\cdots> o(\sigma(n),\cee).$$

$\cee\in\Cee_n^{**}$ if $\cee^+$ is transitive, $\tau(\cee)$ is an order
ideal of $\nctwo$, $$o(\sigma(1),\cee)>o(\sigma(2),\cee)>\cdots>
o(\sigma(n),\cee),$$ and $\omega_0(\cee)\subseteq\omega_\pm(\cee)$, with
$\omega_\pm(\cee)\setminus\omega_0(\cee)$ being a disjoint union of pairs
$\{j,j+1\}$ such that the elements of each such pair are interchangeable
in $\tau(\cee)$.
\medpagebreak

Section 6 will be devoted to the proof of

\proclaim{Lemma 4.1} {\rm (\cite{S}, Lemma 3.3.1)} We have
$$\sum_{\bee\in\Bee_n\setminus\Bee_n^*}
\what(\bee)=\sum_{\cee\in\Cee_n\setminus\Cee_n^*}\wtilde(\cee)
=\sum_{\cee\in\Cee_n\setminus\Cee_n^{**}}\wcheck(\cee)=0$$ for all
$n\ge1$.
\endproclaim

In Section 7, we shall prove

\proclaim{Lemma 4.2} {\rm (\cite{S}, Lemma 3.4.1)} We have
$$\align\sum_{\bee\in\Bee_n^*} \what(\bee) &=\!\!\!\sum\Sb\lambda\in
P_{-\!1,0}(n)\\\sigma\in S_n\endSb
\!\!\!\!(-1)^{|\lambda|-|\mu|/2}t^{|\lambda|-|\mu|}(1-t^2)^{y(\lambda)}
(-1)^\sigma x^{\sigma(\lambda+\delta_n)};\\
\sum_{\cee\in\Cee_n^*}\wtilde(\cee)\\
&\kern-16pt=\!\!\!\sum\Sb\lambda\in P_{0,1}(n)\\\sigma\in S_n\endSb
\!\!\!\!(-1)^{(|\nu|+p(\nu))/2}t^{|\lambda|-|\nu|}(1-t)^{\chi(\exists
i, \lambda_i=i)}(1-t^2)^{z(\lambda)}(-1)^\sigma
x^{\sigma(\lambda+\delta_n)};\\
\sum_{\cee\in\Cee_n^{**}}\wcheck(\cee)\\
&\kern-16pt=\!\!\!\sum\Sb\lambda\in P_{-\!1,1}(n)\\\sigma\in S_n\endSb
\!\!\!\!(-1)^{|\kappa|/2+q(\lambda)}t^{(|\lambda|-|\kappa|)/2}
(1-t)^{\chi(\exists i,\lambda_i=i)}(1-t^2)^{z(\lambda)}(-1)^\sigma
x^{\sigma(\lambda+\delta_n)},\endalign$$ for all $n\ge1$, where $\mu$,
$\nu$, $\kappa$, $y$, $z$, and $q$ are as defined in Section 2.
\endproclaim

Theorems 2.2 and 2.4 follow from these lemmas and from \thetag{3.1bd},
\thetag{3.1bc}, and \thetag{3.1cd}.

\specialhead 5.\quad Lemmas on Order Ideals and Partitions\endspecialhead

Before we begin to prove Lemmas 4.1 and 4.2, we shall need some more
results concerning order ideals, partitions, and interchangeability.

Let $T$ be a subset of $\nrctwo$. For any $i\in[n]$ and any $t\ge-1$,
we define
$$\#_t(i,T)=|\{j:j<i,(j,i)\in T\}|+|\{j:j>i,(i,j)\in T\}|+
(t+1)\chi((i,i)\in T).$$ In other words, $\#_t(i,T)$ is the number of
ordered pairs in $T$ with at least one component equal to $i$, plus
$t$ times the number of ordered pairs in $T$ with both components
equal to $i$. Observe that $\#_t$ is independent of $t$ whenever
$T\subseteq\nctwo$. We shall write $\#$ instead of $\#_t$ in case $T$
is known to be a subset of $\nctwo$. We remark that
$\#(i,T\cap\nctwo)=\#_{-\!1}(i,T)$ for any $T\subseteq\nrctwo$.

The following lemma establishes an important correspondence between
partitions and order ideals of $\nctwo$ and $\nrctwo$.

\proclaim{Lemma 5.1} {\rm (\cite{S}, Lemma 2.3.3) (a)} If $T$ is an
order ideal of $\nctwo$ and $\lambda=(\#(1,T),\ldots,\#(n,T))$, then
$\lambda\in P_{-\!1}(n)$ and $|T|=|\lambda|/2$.

\rom{(b)} If $T$ is an order ideal of $\nrctwo$ and
$\lambda=(\#_t(1,T),\ldots,\#_t(n,T))$, then $\lambda\in P_t(n)$ and,
if $t\ge0$, then $|T|=(|\lambda|+(1-t)p(\lambda))/2$.
\endproclaim

\demo{Proof}(a) Suppose $T$ is an order ideal of $\nctwo$. Consider
the set $$D=\{(i,j-1),(j,i):(i,j)\in T\}.$$ We visualize $D$ as being
made of two copies of $T$, one copy reflected about the diagonal of
$\N^2$ and glued to the other as shown in Figure 5.1.

\medpagebreak
\centerline{\psfig{figure=fig5.1.eps}}
\centerline{\smc Figure 5.1}
\medpagebreak

We claim that $D$ is the Ferrers diagram of a partition $\lambda\in
P_{-\!1}(n)$. Indeed, if $T$ is an order ideal of $\nctwo$, then $T$
is of the form $$\{(1,2),(1,3),\ldots,(1,1+\alpha_1),
(2,3),\ldots,(2,2+\alpha_2),\ldots,(p,p+1),\ldots,(p,p+\alpha_p)\}$$
for some $p\le n-1$ and $\alpha_1>\alpha_2>\cdots>\alpha_p\ge1$, and
$D$ is the Ferrers diagram of
$\lambda=(\alpha_1-1,\ldots,\alpha_p-1\,|\,
\alpha_1,\ldots,\alpha_p)$. It is clear that
$|T|=|\lambda|/2$. So we can complete the proof of (a) by showing that
$\lambda_i=\#(i,T)$ for each $i\in[n]$. This is not hard to see. Given
$(i,j)\in D$, either $j<i$ and $(i,j)$ corresponds to $(j,i)\in T$, or
$j\ge i$ and $(i,j)$ corresponds to $(i,j+1)\in T$; so each of the
$\lambda_i$ squares in the $i$th row of $D$ corresponds to a distinct
ordered pair in $T$ with one component equal to $i$, and this is
clearly a one-to-one correspondence.

(b) Suppose $T$ is an order ideal of $\nrctwo$. Then $T\cap\nctwo$ is
an order ideal of $\nctwo$, and since
$\#_{-\!1}(i,T)=\#(i,T\cap\nctwo)$ for all $i\in[n]$, the case $t=-1$
reduces to the case considered in (a).

Now suppose $t=0$. Consider the set $$D=\{(i,j),(j,i):(i,j)\in T\};$$
we think of $D$ as being made of two copies of $T$, one copy being
reflected about the diagonal and glued to the other with overlap along
the diagonal. Observe that $D$ is the Ferrers diagram of a partition
$\lambda\in P_0(n)$. We see that $p(\lambda)$ is the largest $i$ such
that $(i,i)\in T$, and that $|T|=(\lambda+p(\lambda))/2$. To see that
$\lambda_i=\#_0(i,T)$ for each $i$, observe that for any given
$(i,j)\in D$, either $j<i$ and $(j,i)\in T$, or $j\ge i$ and $(i,j)\in
T$. Each of the $\lambda_i$ squares in the $i$th row of $D$
corresponds to a distinct ordered pair in $T$ with at least one
component equal to $i$. This takes care of the case $t=0$.

If $t\ge1$, then let $$D=\{(i,j+t),(j,i):(i,j)\in T\}
\cup\{(i,i+1),\ldots,(i,i+t-1):1\le i\le p\},$$ where $p$ is the
largest $i$ such that $(i,i)\in T$. In this case, $D$ is made of two
copies of $T$, with one copy reflected about the diagonal as before,
but the copies are separated by a diagonal strip of width $t-1$ and
length $p$. Figure 5.2 shows an example in the case $t=2$.

\medpagebreak
\centerline{\psfig{figure=fig5.2.eps}}
\centerline{\smc Figure 5.2}
\medpagebreak

We find that $D$ is the Ferrers diagram of a partition $\lambda\in
P_t(n)$, that $p(\lambda)=p$, and that
$|T|=(|\lambda|+(1-t)p(\lambda))/2$. To see that $\lambda_i=\#_t(i,T)$
for each $i$, observe that if $(i,j)\in D$, then either: $j<i$ and
$(j,i)\in T$, or $i\le j\le i+t$ and $(i,i)\in T$, or $j>i+t$
and $(i,j-t)\in T$. So the $i$th row of $D$ contains one square for
each ordered pair in $T$ having just one component equal to $i$, and
$t+1$ squares for the ordered pair $(i,i)$ if it is in $T$.
\qed \enddemo

The correspondence described by Lemma 5.1(a) is one-to-one, as is
that described by Lemma 5.1(b) for $t\ge0$. Given
$\lambda\in P_{-\!1}(n)$, then $T=\nctwo\cap\{(i,j+1):(i,j)\in
D(\lambda)\}$ is the unique order ideal of $\nctwo$ for which
$\#(i,T)=\lambda_i$ for all $i$; if $\lambda\in P_t(n)$ and $t\ge0$,
then $T=\nrctwo\cap\{(i,j-t):(i,j)\in D(\lambda)\}$ is the unique
order ideal of $\nrctwo$ such that $\#_t(i,T)=\lambda_i$ for all $i$.
\medpagebreak

The next lemma we shall prove concerns interchangeability. Consider
the subset $\tau$ of $[6]\choose2$ shown in Figure 5.3. The arrows
indicate which pairs of elements of $[6]\choose2$ must be examined for
membership in $\tau$ to decide whether $2$ and $4$ are interchangeable in
$\tau$. For each arrow, the element of $[6]\choose2$ at one end belongs
to $\tau$ if and only if the element at the other end belongs to $\tau$;
this shows that $2$ and $4$ are interchangeable.

\medpagebreak
\centerline{\psfig{figure=fig5.3.eps}}
\centerline{\smc Figure 5.3}
\medpagebreak

It is easy to see that if $i$ and $j$ are interchangeable in
$T\subseteq\nrctwo$, then $\#_t(i,T)=\#_t(j,T)$ for any $t\ge-1$, and
if $i$ and $j$ are interchangeable in $T\subseteq\nctwo$, then
$\#(i,T)=\#(j,T)$. For instance, we have $\#(2,\tau)=\#(4,\tau)$
when $\tau$ is as in Figure 5.3. We also have
$\#(5,\tau)=\#(6,\tau)$ in this case, although $5$ and $6$ are not
interchangeable in $\tau$. The following lemma tells us that this
cannot happen when $T$ is an order ideal:

\proclaim{Lemma 5.2} {\rm (\cite{S}, Lemma 3.2.1) (a)} If $T$ is an
order ideal of $\nctwo$ and $\#(i,T)=\#(j,T)$, then $i$ and $j$ are
interchangeable in $T$.

\rom{(b)} If $T$ is an order ideal of $\nrctwo$ and
$\#_t(i,T)=\#_t(j,T)$ for some $t\ge0$, then $i$ and $j$ are
interchangeable in $T$.
\endproclaim

\demo{Proof} Assuming the hypothesis of (a), with $i<j$,
let $r$ be the common value of $\#(i,T)$ and $\#(j,T)$. It is easy
to see that $r\le i-1$ if $(i,j)\notin T$ and $r\ge j-1$ if $(i,j)\in
T$. In the former case, we find that $(k,i)\in T$ if and only if
$(k,j)\in T$ if and only if $1\le k\le r$, while any other $(k,l)$
with $k$ or $l$ equal to $i$ or $j$ is not in $T$. The latter case is
similar, except that we have: $(k,i),(k,j)\in T$ whenever $1\le k<i$;
$(i,k),(k,j)\in T$ whenever $i<k<j$; for $k>j$, $(i,k)\in T$ if
and only if $(j,k)\in T$ if and only if $j+1\le k\le r+1$. This proves
(a); the proof of (b) is almost identical. We mention that the
condition $t\ge0$ in (b) is necessary to ensure that $(i,i)$ and
$(j,j)$ are counted by $\#_t(i,T)$ and $\#_t(j,T)$ whenever they belong
to $T$.\qed
\enddemo

Suppose $\barT$ is a subset of $\nrctwo$ and $T=\barT\cap\nctwo$.
Clearly, $T$ is an order ideal of $\nctwo$ if $\barT$ is an order
ideal of $\nrctwo$, but the converse does not hold. For $\barT$ to be
an order ideal of $\nrctwo$, it is necessary that $T$ be an order
ideal of $\nctwo$, but not sufficient. The last lemma of this section
gives the additional conditions we need in order for $\barT$ to be an
order ideal. To state it, we need to introduce what we shall call
extreme points of an order ideal of a poset.

Let $P$ be a poset and $T$ an order ideal of $P$. We say that $p\in T$
is an {\sl inner extreme point\/} of $T$ if $T\setminus\{p\}$ is an
order ideal of $P$. Meanwhile, $p$ is an {\sl outer extreme point\/}
of $T$ if $p\notin T$ and $T\cup\{p\}$ is an order ideal of $P$. We
denote by $I(T)$ and $O(T)$ the sets of all inner and outer extreme
points of $T$. Evidently $I(T)$ is the smallest set $S$ such that
$T=\{p:p\preceq s\text{ for some }s\in S\}$, while $O(T)$ is the
smallest $S$ for which $P\setminus T=\{q:q\succeq s \text{ for some
}s\in S\}$. Figure 5.4 portrays order ideals $T\subset{[5]\choose2}$
and $T'\subset{[5]\rchoose2}$; we see that $I(T)=\{(3,4),(1,5)\}$,
$O(T)=\{(2,5)\}$, $I(T')=\{(2,3),(1,5)\}$, and
$O(T')=\{(3,3),(2,4)\}$.

\medpagebreak
\centerline{\psfig{figure=fig5.4.eps}}
\centerline{\smc Figure 5.4}
\medpagebreak

We are ready to state and prove:

\proclaim{Lemma 5.3} {\rm (\cite{S}, Lemma 3.2.2)} Let
$\taubar\subseteq\nrctwo$ and $\tau=\taubar\cap\nctwo$. Then $\taubar$
is an order ideal of $\nrctwo$ if and only if all the following
conditions hold:

\smallpagebreak
\rom{(i)} $\tau$ is an order ideal of $\nctwo$.

\rom{(ii)} For all $(i,j)\in I(\tau)$, $(i,i)\in\taubar$
or $(j,j)\in\taubar$.

\rom{(iii)} For all $(i,j)\in O(\tau)$, $(i,i)\notin\taubar$ or
$(j,j)\notin\taubar$.

\rom{(iv)} $\{i:(i,i)\in\taubar\}$ is of the form
$\{1,2,\ldots,r\}$ for some $r$, $0\le r\le n$.
\smallpagebreak

Furthermore, if \rom{(i)--(iii)} hold and \rom{(iv)} does not, there exists
$i\in [n]$ such that $(i,i)\notin\taubar$, $(i+1,i+1)\in\taubar$, and
$i$ and $i+1$ are interchangeable in $\tau$.
\endproclaim

\demo{Proof} ``Only if'': Suppose $\taubar$ is an order ideal of
$\nrctwo$. If $(i,j)\in\tau$ and $(k,l)\prec(i,j)$, then
$(k,l)\in\taubar$; if $(k,l)\in\nctwo$, then
$(k,l)\in\tau$. Therefore (i) holds. If $(i,j)\in I(\tau)$, then
$(i,j)\in\tau$, which implies $(i,i)\in \taubar$, so (ii)
holds. Similarly, for $(i,j)\in O(\tau)$ we have $(i,j)
\notin\taubar$, which means $(j,j)\notin\taubar$, and (iii) holds.
If $(i,i)\in\taubar$, then $(j,j)\in\taubar$ for any $j\le
i$, so (iv) holds.

``If'': Suppose $\taubar$ is not an order ideal of
$\nrctwo$. Then there exist $i,j\in [n]$ with $i\le j$ and either
$(i,j)\notin\taubar$, $(i,j+1)\in \taubar$ or $(i-1,j)\notin\taubar$,
$(i,j)\in\taubar$. If $i<j$, then $\tau$ is not an order ideal of
$\nctwo$. If $\tau$ is an order ideal of $[n] \choose2$ but
$(i,i)\notin\taubar$, $(i,i+1)\in\taubar$ for some $i$, then there
exist $j,k$ with $k>j\ge i$ and $(j,k)\in I(\tau)$. If either $(j,j)$
or $(k,k)$ is in $\taubar$, then (iv) is violated; otherwise (ii) does
not hold. If $\tau$ is an order ideal of $\nctwo$ and
$(i-1,i)\notin\taubar$, $(i,i)\in\taubar$, then we have $(j,k)\in
O(\tau)$ for some $j,k$ with $i\ge k>j$. If $(j,j)\notin\taubar$ or
$(k,k)\notin\taubar$, then (iv) does not hold; otherwise (iii) fails.

``Furthermore'': Suppose $\taubar\subseteq\nrctwo$ is such
that (i)--(iii) hold and (iv) does not. Choose $i$ such that
$(i,i)\notin\taubar$, $(i+1,i+1)\in\taubar$. If $i$ and $i+1$ are
interchangeable in $\tau$, we are done. If not, then either
$(i,j)\in\tau$, $(i+1,j)\notin\tau$ for some $j\ge i+2$ or
$(k,i)\in\tau$, $(k,i+1)\notin\tau$ for some $k\le i-1$. In the former
case, choose the smallest $j$ with this property. Then $(i+1,j)\in
O(\tau)$; since (iii) holds and $(i+1,i+1)\in \taubar$, we must have
$(j,j)\notin\taubar$. There is some $l\ge j$ such that $(i,l)\in
I(\tau)$, and since (ii) holds and $(i,i)\notin\taubar$, we must have
$(l,l)\in\taubar$, which tells us $l>j$. We find that $\#(q,\tau)=i$
for each $q$ with $j\le q\le l$; Lemma 5.2(a) tells us that $j$, $j+1$,
$\ldots\,$, $l$ are pairwise interchangeable in $\tau$, and for some
$q$ with $j\le q<l$, we must have $(q,q)\notin\taubar$,
$(q+1,q+1)\in\taubar$. A similar argument applies in the latter
case.\qed \enddemo

Figure 5.5 shows a subset $\taubar$ of $[7]\rchoose2$ for which only
condition (iv) fails. The bold line separates $[7]\choose2$ from pairs
of the form $(i,i)$. We have $(6,6)\notin\taubar$, $(7,7)\in\taubar$,
but $6$ and $7$ are not interchangeable in $\tau$. We see that
$(2,7)\in O(\tau)$ and $(4,6) \in I(\tau)$; $3$ and $4$ are
interchangeable in $\tau$ and $(3,3)\notin\taubar$, $(4,4)\in\taubar$.

\medpagebreak
\centerline{\psfig{figure=fig5.5.eps}}
\centerline{\smc Figure 5.5}
\medpagebreak

\specialhead 6.\quad Cancellation\endspecialhead

Before beginning the proof of Lemma 4.1, we need to introduce some
operations on digraphs. We shall use these operations to ``pair off''
the digraphs in $\Bee_n\setminus\Bee_n^*$, $\Cee_n\setminus\Cee_n^*$,
and $\Cee_n\setminus\Cee_n^{**}$. Each such digraph will be paired
with another, whose weight is $-1$ times that of the first.

\head Arc Reversal and Vertex Interchange\endhead

Given a digraph $\gee$ on $V$, we can obtain other digraphs on $V$ by
reversing some of the arcs in $\gee$. Specifically, we reverse the
arcs in a subset $R$ of $\gee$ by replacing $R$ with
$R'=\{(j,i):(i,j)\in R\}$. This gives us the digraph
$\gee'=R'\cup\gee\setminus R$. If $R$ is a disjoint union of cycles,
then we have $o(i,\gee')=o(i,\gee)$ for every $i\in V$. In this case,
$R'$ is also a disjoint union of cycles. Whatever $R$ may be, we
recover $\gee$ from $\gee'$ by reversing the arcs in $R'$.

Another way of obtaining a new digraph on $V$ from an existing one is
by interchanging vertices. Let $\gee$ be a digraph on $V$ and let
$p,q\in V$. Let $\phi_{pq}$ be the bijection on $V$ that interchanges
$p$ and $q$ while fixing everything else in $V$. Then
$\gee_{pq}=\{(\phi_{pq}(i),\phi_{pq}(j)):(i,j)\in\gee\}$ is another
digraph on $V$; we say that $\gee_{pq}$ is obtained from $\gee$
by interchanging $p$ and $q$. Observe that $o(p,\gee_{pq})=o(q,\gee)$,
$o(q,\gee_{pq})=o(p,\gee)$, and $o(r,\gee_{pq})=o(r,\gee)$ for any $r$
other than $p$ or $q$. Evidently $\gee$ is obtained from $\gee_{pq}$ by
interchanging $p$ and $q$.

Suppose that $\gee$, $p$, and $q$ satisfy the following condition: for
each $r\in V\setminus\{p,q\}$, the digraph $\gee$ has an arc between
$p$ and $r$ if and only if it has an arc between $q$ and $r$. (This
condition holds for all $p,q\in V$ if $\gee$ is complete.) Then the
digraph obtained from $\gee$ by interchanging $p$ and $q$ can also be
obtained from $\gee$ by reversing arcs. Let $R$ consist of all pairs
of arcs $\{(p,r)$, $(r,q)\}$ or $\{(q,r)$, $(r,p)\}$ such that both
arcs are in $\gee$, plus the arc between $p$ and $q$ if there is one
in $\gee$. Then $\gee_{pq}$ is obtained from $\gee$ by reversing the
arcs in $R$. Recall the digraphs of Figure 3.1. We find that reversing
the arcs $(2,3)$, $(3,4)$, and $(4,2)$ has the same effect on $\gee_2$
as interchanging $2$ and $3$. On the other hand, there is no set of
arcs in $\gee_1$ whose reversal gives us the digraph we obtain from
$\gee_1$ by interchanging $b$ and $c$.

\head Proof of Lemma 4.1\endhead

Given a set $X$, on whose elements a weight function $w$
is defined, one way to prove that $\sum_{x\in X}w(x)=0$ is by
defining a function $\phi:X\to X$ such that $w(\phi(x))=-w(x)$
and $\phi(\phi(x))=x$ for all $x\in X$. We say that $\phi$ is
a weight-preserving and sign-reversing involution on $X$ if
it has these properties. In effect, $\phi$ ``pairs off'' each
$x$ with $\phi(x)$.

We shall prove Lemma 4.1 by constructing weight-preserving and
sign-reversing involutions $\phihat$, $\phitld$, and $\phichk$ on the
sets $\Bee_n\setminus\Bee_n^*$, $\Cee_n\setminus\Cee_n^*$, and
$\Cee_n\setminus\Cee_n^{**}$ respectively. The construction will
involve arc reversal and will proceed in several phases. In the first
two phases, the arcs to be reversed will all be of the form $(i,j)$
and $(-j,-i)$, where $|i|$ and $|j|$ are distinct and nonzero. This
will allow $\phihat$, $\phitld$, and $\phichk$ to be defined
simultaneously, because $\what(i,j)=\wtilde(i,j)=\wcheck(i,j)$
whenever $j$ is not $0$ or $-i$. In later phases, the functions will
be defined separately. In Phases 1 and 3, we shall assume a total
order has been defined on the set $\nctwo$.

\head Phase 1\endhead

This phase takes care of all those $\gee\in\Bee_n\cup\Cee_n$ for which
$\gee^+$ is not transitive.

If $\gee^+$ is not transitive, then we have $o(i,\gee^+)=o(j,\gee^+)$
for some $(i,j)\in\nctwo$. Let $(i_0,j_0)$ be the smallest
$(i,j)$ (relative to the total order on $\nctwo$) with this property.
Let $\gee^-$ be the negative subtournament of $\gee$, i.e.,
$\gee^-=\{(-j,-i):(i,j)\in\gee^+\}$. We obtain $\phihat(\gee)$,
$\phitld(\gee)$, or $\phichk(\gee)$ by interchanging $i_0$ and $j_0$
in $\gee^+$ and interchanging $-i_0$ and $-j_0$ in $\gee^-$. This
corresponds to reversing the arc between $i_0$ and $j_0$, the arc
between $-i_0$ and $-j_0$, and all the arcs that belong to subsets of
$\gee$ of the forms
$$\align\{(i_0,k),(k,j_0),(-j_0,-k),(-k,-i_0)\},&\quad k>0
\tag a\\
\noalign{\hbox{and}}
\{(j_0,k),(k,i_0),(-i_0,-k),(-k,-j_0)\},&\quad k>0.
\tag b\endalign$$

Let $\gee'$ denote the result of interchanging $i_0$ and $j_0$ in
$\gee^+$ and $-i_0$ and $-j_0$ in $\gee^-$. We find that $(\gee')^+$
is not transitive and that $o(k,(\gee')^+)=o(k,\gee^+)$ for all $k\in
[n]$, so we interchange the same vertices when applying $\phihat$,
$\phitld$, or $\phichk$ to $\gee'$ as we had interchanged to obtain
$\gee'$ from $\gee$. This means that we recover $\gee$ from $\gee'$
by applying the same function that gave us $\gee'$ when applied to
$\gee$.

We must now show that the weight of $\gee'$ is $-1$ times the weight
of $\gee$. Let $a$ and $b$ be the number of subsets of $\gee$ of types
\thetag{a} and \thetag{b} respectively. We have
$$0=o(i_0,\gee^+)-o(j_0,\gee^+)=a-b+\cases 1&\text{if
}(i_0,j_0)\in\gee,\\ -1&\text{if }(j_0,i_0)\in\gee.\endcases$$ Observe
that reversing the arcs in a subset of type \thetag{a} multiplies the
weight of $\gee$ by $x_{j_0}/x_{i_0}$, while reversing the arcs in a
subset of type \thetag{b} multiplies the weight by $x_{i_0}/x_{j_0}$.
If $(i_0,j_0)\in\gee$, then there is one more subset of type \thetag{b}
than of type \thetag{a}, so reversing the arcs in all subsets of
both types multiplies the weight by $x_{i_0}/x_{j_0}$. Reversing
$(-j_0,-i_0)$ has no effect on the weight, whereas reversing
$(i_0,j_0)$ multiplies the weight by $-x_{j_0}/x_{i_0}$. So the
weight of $\gee'$ is $-1$ times the weight of $\gee$ as required.
Similarly if $(j_0,i_0)\in\gee$.

This completes Phase 1. From now on, we shall work only with digraphs
whose positive subtournaments are transitive. Recall the definitions
of $\sigma(\gee)$, $\tau(\gee)$, $\taubar(\gee)$, $\omega_0(\gee)$,
and $\omega_\pm(\gee)$ for digraphs $\gee$ with $\gee^+$ transitive.

\head Phase 2\endhead

In this phase, we define $\phihat$, $\phitld$, and $\phichk$ for all
$\gee$ such that $\gee^+$ is transitive but $\tau(\gee)$ is not
an order ideal of $\nctwo$. We begin with a discussion of how
reversing a certain set of arcs in $\gee$ affects $\tau(\gee)$ and
$\taubar(\gee)$.

Suppose $T$ and $T'$ are subsets of a set $A$. If there exist disjoint
subsets of $A$ of the form $\{a_i:i\in I\}$ and $\{a'_i:i\in I\}$ such
that for each $i\in I$, we have $a_i\in T$ if and only if $a'_i\in T'$
and $a'_i\in T$ if and only if $a_i\in T'$, then we say that $T'$ is
obtained from $T$ by {\sl exchanging\/} the pairs $a_i$ and $a'_i$ for
each $i\in I$. For example, we obtain $\{1,4,5,6,10\}$ from
$\{2,3,5,6,9\}$ by exchanging $1$ and $2$, $3$ and $4$, $5$ and $6$,
$7$ and $8$, and $9$ and $10$. If $\gee$ is a digraph on the set $V$ and
$\gee_{pq}$ is obtained from $\gee$ by interchanging the vertices $p$ and
$q$, then $\gee_{pq}$ is also obtained from $\gee$ by exchanging $(p,r)$ and
$(q,r)$ for all $r\in V\setminus\{p,q\}$; exchanging $(r,p)$ and
$(r,q)$ for all $r\in V\setminus\{p,q\}$; and exchanging $(p,q)$ and
$(q,p)$. Evidently if $T'$ is obtained from $T$ by exchanging $a_i$
and $a'_i$ for each $i\in I$, then $T$ is obtained from $T'$ by the
same process.

Now let $\gee\in\Bee_n\cup\Cee_n$ with $\gee^+$ transitive and
$\sigma=\sigma(\gee)$. Given $i,j\in[n]$ with $i<j$, we create a new
digraph $\gee'$ by reversing the arcs
$$(\sigma(i),\sigma(k)),(\sigma(k),\sigma(j)),
(-\sigma(k),-\sigma(i)),(-\sigma(j),-\sigma(k)),\quad i<k<j,$$ and
reversing $(\sigma(i),\sigma(j))$ and $(-\sigma(j),-\sigma(i))$. It is
easy to see that $(\gee')^+$ is transitive, with
$\sigma(\gee')=\sigma\cdot(i\,j)$. We find that $\tau(\gee')$ and
$\taubar(\gee')$ are generally not the same as $\tau(\gee)$ and
$\taubar(\gee)$. This is because $\tau$ and $\taubar$ depend upon
$\sigma$. Indeed, $\tau(\gee')$ and $\taubar(\gee')$ are obtained from
$\tau(\gee)$ and $\taubar(\gee)$ by exchanging $(k,i)$ and $(k,j)$,
$1\le k<i$; $(i,k)$ and $(k,j)$, $i<k<j$; $(i,k)$ and $(j,k)$, $j<k\le
n$; and $(i,i)$ and $(j,j)$. For instance, if
$\gee\in\Bee_6\cup\Cee_6$ is such that $\tau(\gee)$ is the set shown
in Figure 5.3, with $i=2$ and $j=4$, then the pairs of elements of
$[6]\choose2$ to be exchanged to obtain $\tau(\gee')$ are those
connected by arrows in the figure. Observe that $\tau(\gee')
=\tau(\gee)$ exactly when $i$ and $j$ are interchangeable in
$\tau(\gee)$, and similarly for $\taubar$.

We now begin the second phase of the description of $\phihat$,
$\phitld$, and $\phichk$. Given $\gee\in\Bee_n\cup\Cee_n$ with
$\tau=\tau(\gee)$ not an order ideal of $\nctwo$, we either have
$(q,p)\notin\tau$, $(q,p+1)\in\tau$ for some $q<p$ or
$(p,q)\notin\tau$, $(p+1,q)\in\tau$ for some $q>p+1$. In either case,
$\gee$ contains a pair of cycles of the form
$$\aligned&\{(\sigma(p),\sigma(p+1)),\,(\sigma(p+1),-\sigma(q)),\,
(-\sigma(q),\sigma(p))\}\\
\text{and }&\{(-\sigma(p),\sigma(q)),\,(\sigma(q),-\sigma(p+1)),\,
(-\sigma(p+1),-\sigma(p))\}.\endaligned\tag\dag$$

We shall reverse some such pair of cycles (i.e., reverse all the arcs
in the cycles) to obtain $\phihat(\gee)$, $\phitld(\gee)$, or
$\phichk(\gee)$. Let $\gee'$ denote the result of this cycle
reversal. It is easy to see that $(\gee')^+$ is transitive, with
corresponding permutation $\sigma(\gee')=\sigma\cdot(p\,p+1)$, and
that $\what(\gee')=-\what(\gee)$, $\wtilde(\gee')=-\wtilde(\gee)$, and
$\wcheck(\gee')=-\wcheck(\gee)$. To ensure that we recover $\gee$ by
applying $\phihat$, $\phitld$, or $\phichk$ to $\gee'$, we must have
some way of choosing which cycles to reverse. This is the purpose of
the following discussion.

We say there is a {\sl violation\/} in the $i$th row of $\tau$ if
there is some $l$ such that $(i,l)\notin\tau$ and $(i,l+1)\in\tau$. We
say the $k$th row of $\tau$ {\sl extends farther\/} than the $i$th row
if $\max\{j:(k,j)\in\tau\}>\max\{j:(i,j)\in\tau\}$. Find the smallest
$i$ such that either there is a violation in the $i$th row of $\tau$,
or there is a $k>i$ such that the $k$th row of $\tau$ extends farther
than the $i$th row. (Since $\tau$ is not an order ideal, there is an
$i$ satisfying one of these two conditions.) Find the smallest $j$
such that $(k,l)\notin\tau$ whenever $k\ge i$ and $l>j$. Then we have
$(k,l)\in\tau$ whenever $k<i$ and $l\le j$, since there are no
violations in the first $i-1$ rows and no row below the $(i-1)$st
extends farther than any of the first $i-1$ rows. For example, with
$\tau$ as in Figure 6.1, we find that $i=2$ and $j=6$.

\medpagebreak
\centerline{\psfig{figure=fig6.1.eps}}
\centerline{\smc Figure 6.1}
\medpagebreak

Now either $(i,j)$ is in $\tau$, or it is not. If $(i,j)\notin\tau$,
as is the case for $\tau$ as in Figure 6.1, then there must be a row
below the $i$th that extends farther than the $i$th row, since we
found the smallest $j$ such that $(k,l)\notin\tau$ whenever $k\ge i$
and $l>j$. So there must be an $l$ with $i+1\le l\le j-1$,
$(l-1,j)\notin\tau$, and $(l,j)\in\tau$. Choose the smallest such
$l$; then let $p=l-1$ and $q=j$ and reverse the cycles shown in
\thetag{\dag}. If $\gee'$ is the digraph that results from these
cycle reversals, then $\sigma(\gee')=\sigma\cdot(l-1\,l)$ and
$\tau'=\tau(\gee')$ is obtained from $\tau$ by exchanging $(k,l-1)$
and $(k,l)$ for $1\le k\le l-2$ and exchanging $(l-1,k)$ and $(l,k)$
for $l+1\le k\le n, k\ne j$. In the situation of Figure 6.1, we have
$l=4$, and the arrows in the figure indicate the exchanges by which
$\tau'$ is obtained from $\tau$. Observe that the $j$th column of
$\tau'$ is the same as that of $\tau$; $(k,l)\notin\tau'$ whenever
$k\ge i$ and $l>j$; and $(k,l)\in\tau'$ whenever $k<i$ and $l\le
j$. This means that when we examine $\tau'$ to choose which cycles in
$\gee'$ to reverse, we shall find the same $i$ and $j$ and the same
$l$ as we had found for $\tau$. So we recover $\gee$ by applying
$\phihat$, $\phitld$, or $\phichk$ to $\gee'$, as required.

If $(i,j)\in\tau$, then no row below the $i$th extends farther than
the $i$th row, so there must be a violation in the $i$th row of
$\tau$; we must have some $k$ with $i+1\le k\le j-1$ such that
$(i,k)\notin\tau$ and $(i,k+1)\in\tau$. Choose the largest such
$k$. Let $p=k$ and $q=i$ and reverse the cycles shown in
\thetag{\dag}. If $\gee'$ is the digraph that results from these
reversals, then we have $\sigma(\gee')=\sigma\cdot(k\,k+1)$ and
$\tau'=\tau(\gee')$ is obtained from $\tau$ by exchanging $(l,k)$ and
$(l,k+1)$ for $1\le l\le k-1$, $l\ne i$, and exchanging $(k,l)$ and
$(k+1,l)$ for $k+2\le l\le n$. We find that the $i$th row of $\tau'$
is the same as that of $\tau$, and that $(k,l)$ is in $\tau$ whenever
$k<i$ and $l\le j$ and not in $\tau$ whenever $k\ge i$ and $l>j$. So
when we look at $\tau'$ to decide which cycles in $\gee'$ to reverse,
we shall find the same $i$, $j$, and $k$ as we had found for
$\tau$. Again, we recover $\gee$ from $\gee'$ by applying $\phihat$,
$\phitld$, or $\phichk$. We are finished with Phase 2.

\head Phase 3\endhead

From now on, we assume $\gee^+$ is transitive and $\tau=\tau(\gee)$ is
an order ideal of $\nctwo$. Lemma 5.1(a) implies that
$\#(1,\tau)\ge\#(2,\tau)\ge\cdots\ge\#(n,\tau)$. If $\gee\in\Bee_n$,
then we have
$$o(\sigma(i),\gee)=n-i+\#(i,\tau)+\chi(i\in\omega_0)$$ for all
$i\in [n]$; if $\gee\in\Cee_n$, then
$$\align o(\sigma(i),\gee)&=n-i
+\#(i,\tau)+\chi(i\in\omega_0)+\chi(i\in\omega_\pm)\\
&=n-i+\#_0(i,\taubar)+\chi(i\in\omega_\pm)\endalign$$
for all $i\in [n]$.

\subhead Construction of $\phihat$\endsubhead
Given $\gee\in\Bee_n$, with $\gee^+$ transitive and $\tau$ an order
ideal of $\nctwo$, we have $\gee\in\Bee_n^*$ unless
$o(\sigma(i),\gee)\le o(\sigma(i+1),\gee)$ for some $i$. Since
$\#(1,\tau)\ge\#(2,\tau)\ge\cdots\ge\#(n,\tau)$, the only way we can
have $o(\sigma(i),\gee)\le o(\sigma(i+1),\gee)$ is if
$\#(i,\tau)=\#(i+1,\tau)$, $i\notin\omega_0$, and $i+1\in\omega_0$;
this gives us $o(\sigma(i),\gee)=o(\sigma(i+1),\gee)$. Let $i_0$ be
the smallest $i$ with these properties. We obtain $\phihat(\gee)$ from
$\gee$ by reversing the pair of cycles
$$\align&\{(\sigma(i_0),\sigma(i_0+1)),\,(\sigma(i_0+1),0),\,
(0,\sigma(i_0))\}\\
\text{and }&\{(-\sigma(i_0),0),\,(0,-\sigma(i_0+1)),\,
(-\sigma(i_0+1),-\sigma(i_0))\}.\endalign$$
We find that $\phihat(\gee)^+$ is transitive, with
$\sigma(\phihat(\gee))=\sigma\cdot(i_0\,i_0+1)$, and that
$\what(\phihat(\gee))=-\what(\gee)$. Lemma 5.2(a) tells us that $i_0$
and $i_0+1$ are interchangeable in $\tau$; therefore
$\tau(\phihat(\gee))=\tau$. Finally, we observe that
$\omega_0(\phihat(\gee))=\omega_0(\gee)$. We conclude that
$\phihat(\phihat(\gee))=\gee$, as required. This completes the proof
that $\sum_{\gee\in\Bee_n\setminus\Bee_n^*}\what(\gee)=0$.

\subhead Construction of $\phitld$\endsubhead
Suppose $\gee$ is in $\Cee_n$, with $\gee^+$ transitive, $\tau$ an
order ideal of $\nctwo$, but $\taubar$ not an order ideal of
$\nrctwo$. For any $\barT\subseteq\nrctwo$ such that
$T=\barT\cap\nctwo$ is an order ideal of $\nctwo$, let
$X(\barT)$ be the set of all $(i,j)\in\nctwo$ such that either
$$\align (i,j)\in I(T)&\quad\text{and}\quad(i,i),(j,j)\notin\barT\\
\noalign{\hbox{or}}
(i,j)\in O(T)&\quad\text{and}\quad(i,i),(j,j)\in\barT.\endalign$$
In Figure 6.2, for example, we have a subset $\taubar$ of $[6]\rchoose2$
for which $X(\taubar)=\{(2,5)\}$.

\medpagebreak
\centerline{\psfig{figure=fig6.2.eps}}
\centerline{\smc Figure 6.2}
\medpagebreak

If $X(\taubar)\ne\emptyset$, then let $(i_0,j_0)$ be the smallest
element of $X(\taubar)$ relative to our total order on $\nctwo$.
If $(i_0,j_0)\in I(\tau)$, then we obtain $\phitld(\gee)$ from $\gee$
by reversing the cycles
$$\align&\{(\sigma(i_0),-\sigma(j_0)),
(-\sigma(j_0),0),(0,\sigma(i_0))\}\\
\text{and }&\{(-\sigma(i_0),0),(0,\sigma(j_0)),
(\sigma(j_0),-\sigma(i_0))\}.\endalign$$
Otherwise, $(i_0,j_0)\in O(\tau)$, in which case we obtain
$\phitld(\gee)$ by reversing
$$\align&\{(\sigma(i_0),0),
(0,-\sigma(j_0)),(-\sigma(j_0),\sigma(i_0))\}\\
\text{and }&\{(-\sigma(i_0),\sigma(j_0)),
(\sigma(j_0),0),(0,-\sigma(i_0))\}.\endalign$$
It is easy to see that $\wtilde(\phitld(\gee))=-\wtilde(\gee)$.
Observe that $\phitld(\gee)^+=\gee^+$, so $\phitld(\gee)^+$ is
transitive. We also have
$\omega_\pm(\phitld(\gee))=\omega_\pm(\gee)$.

Let $\tau'=\tau(\phitld(\gee))$ and $\taubar'=\taubar(\phitld(\gee))$.
We see that if $(i_0,j_0)\in I(\tau)$ (respectively, $O(\tau)$), then
$(i_0,j_0)\in O(\tau')$ (respectively, $I(\tau')$). If $k$ is not
$i_0$ or $j_0$, then $(k,k)\in\taubar'$ if and only if
$(k,k)\in\taubar$, whereas $(i_0,i_0)$ and $(j_0,j_0)$ are in
$\taubar'$ if and only if they are not in $\taubar$. This tells us
that $(i_0,j_0)\in X(\taubar')$; we shall now prove that
$X(\taubar')=X(\taubar)$, which implies that $(i_0,j_0)$ is the
smallest element in $X(\taubar')$. This in turn means that
$\phitld(\phitld(\gee))=\gee$ if $X(\taubar)$ is nonempty.

Suppose $(i,j)\in X(\taubar')\setminus X(\taubar)$. Either $(i,j)\in
I(\tau')$ or $(i,j)\in O(\tau')$. Assuming the former, we have
$(i,i),(j,j)\notin\taubar'$. If $i\ne i_0$ and $j\ne j_0$, then
$(i,i),(j,j)\notin\taubar$. In this case, we must have $(i,j)\notin
I(\tau)$ in order to have $(i,j)\notin X(\taubar)$. For this to happen
with $(i,j)$ in $I(\tau')$, one of $(i+1,j)$, $(i,j+1)$ must be in
$\tau$ and must be removed from $\tau$ to yield $\tau'$. Since $\tau'$
is either $\tau\cup\{(i_0,j_0)\}$ or $\tau\setminus\{(i_0,j_0)\}$, it
must be that $(i_0,j_0)$ equals $(i+1,j)$ or $(i,j+1)$. This
contradicts our assumption that $i\ne i_0$ and $j\ne j_0$. So assume
that $i=i_0$ or $j=j_0$. Then either $(i_0,i_0)\notin\taubar'$ or
$(j_0,j_0)\notin\taubar'$, by our assumption that $(i,j)\in
I(\tau')$. But $(i_0,j_0)\in X(\taubar')$, so
$(i_0,i_0)\notin\taubar'$ if and only if $(j_0,j_0)\notin\taubar'$ if
and only if $(i_0,j_0)\in I(\tau')$. Since no row or column of
$\nctwo$ can contain two distinct inner extreme points of $\tau'$, our
assumption that $i=i_0$ or $j=j_0$ now tells us that
$(i,j)=(i_0,j_0)$, which contradicts our assumption that $(i,j)\notin
X(\taubar)$. The argument is similar if we begin by assuming $(i,j)\in
O(\tau')$. We conclude that $X(\taubar')\subseteq X(\taubar)$;
similarly, $X(\taubar)\subseteq X(\taubar')$.

There is another possibility to be considered if $\tau$ is an order
ideal of $\nctwo$ but $\taubar$ is not an order ideal of $\nrctwo$:
that $X(\taubar)$ is empty (this is the case for $\taubar$ as in
Figure 5.5). In this case, Lemma 5.3 tells us that there is some $i\in
[n]$ such that $(i,i)\notin\taubar$, $(i+1,i+1)\in\taubar$, and $i$
and $i+1$ are interchangeable in $\tau$. Let $i_0$ be the smallest
such $i$. Then we obtain $\phitld(\gee)$ from $\gee$ by reversing the
cycles
$$\align&\{(\sigma(i_0),\sigma(i_0+1)),(\sigma(i_0+1),0),
(0,\sigma(i_0))\}\\
\text{and }&\{(-\sigma(i_0),0),(0,-\sigma(i_0+1)),(-\sigma(i_0+1),
-\sigma(i_0))\}.\endalign$$

We see that $\phitld(\gee)^+$ is transitive, with
$\sigma(\phitld(\gee))=\sigma\cdot(i_0\,i_0+1)$, and that
$\wtilde(\phitld(\gee))=-\wtilde(\gee)$. We obtain
$\omega_\pm(\phitld(\gee))$ from $\omega_\pm(\gee)$ by exchanging
$i_0$ and $i_0+1$, but $\omega_0(\phitld(\gee))=\omega_0(\gee)$.
Meanwhile, $\tau(\phitld(\gee))=\tau$, due to the interchangeability
of $i_0$ and $i_0+1$ in $\tau$. So $\taubar(\phitld(\gee))=\taubar$,
and this ensures that we shall obtain $\gee$ by applying $\phitld$ to
$\phitld(\gee)$.

\subhead Construction of $\phichk$\endsubhead Let $\gee\in\Cee_n$ with
$\gee^+$ transitive, $\tau$ an order ideal of $\nctwo$, and
$o(\sigma(i),\gee)=o(\sigma(j),\gee)$ for some $i,j\in [n]$ with
$i<j$. Let $i_0$ be the smallest $i$ for which this occurs. Then $j$
must be either $i_0+1$ or $i_0+2$, since we have
$o(\sigma(k),\gee)\le\#(k,\tau)+n-k+2
<\#(k,\tau)+n-i_0\le\#(i_0,\tau)+n-i_0\le o(\sigma(i_0),\gee)$ whenever
$k>i_0+2$.

Suppose $o(\sigma(i_0),\gee)=o(\sigma(i_0+1),\gee)$. There are several
ways in which this can occur:

\medpagebreak
(1) $\#(i_0,\tau)=\#(i_0+1,\tau)$, $i_0\notin\omega_0$, $i_0+1\in\omega_0$,
and $i_0\in\omega_\pm$ if and only if $i_0+1\in\omega_\pm$.

(2) $\#(i_0,\tau)=\#(i_0+1,\tau)$, $i_0\notin\omega_\pm$, $i_0+1\in\omega_\pm$,
and $i_0\in\omega_0$ if and only if $i_0+1\in\omega_0$.

(3) $\#(i_0,\tau)=\#(i_0+1,\tau)+1$, $i_0\notin\omega_0$,
$i_0\notin\omega_\pm$, $i_0+1\in\omega_0$, $i_0+1\in\omega_\pm$.
\medpagebreak

For (1), we obtain $\phichk(\gee)$ from $\gee$ by reversing the cycles
$$\align&\{(\sigma(i_0),\sigma(i_0+1)),(\sigma(i_0+1),0),
(0,\sigma(i_0))\}\\
\text{and }&\{(-\sigma(i_0),0),(0,-\sigma(i_0+1)),
(-\sigma(i_0+1),-\sigma(i_0))\}.\endalign$$

We observe that $\phichk(\gee)^+$ is transitive, with corresponding
permutation $\sigma\cdot(i_0\,i_0+1)$. Meanwhile,
$\omega_0(\phichk(\gee))=\omega_0$ and $\omega_\pm(\phichk(\gee))
=\omega_\pm$. Since $\#(i_0,\tau)=\#(i_0+1,\tau)$ in this case, $i_0$
and $i_0+1$ are interchangeable in $\tau$ and we have
$\tau(\phichk(\gee))=\tau$. From these observations, we conclude that
$\phichk(\phichk(\gee))=\gee$. And it is easy to see that
$\wcheck(\phichk(\gee))=-\wcheck(\gee)$.

(2) is very similar to (1). We obtain $\phichk(\gee)$ by reversing the
cycle
$$\{(\sigma(i_0),\sigma(i_0+1)),(\sigma(i_0+1),-\sigma(i_0+1)),
(-\sigma(i_0+1),-\sigma(i_0)),(-\sigma(i_0),\sigma(i_0))\}.$$ The
observations in (1) apply in this case, and we have
$\phichk(\phichk(\gee))= \gee$ and
$\wcheck(\phichk(\gee))=-\wcheck(\gee)$.

(3) is a little more difficult. Suppose that
$\#(i_0,\tau)=\#(i_0+1,\tau)+1=r$. Observe that $r\ne i_0$: it is not
hard to see that if $\tau$ is an order ideal of $\nctwo$ and
$\#(i,\tau)=i$ for some $i$, then $\#(i+1,\tau)=i$ as well. If
$r<i_0$, then we have
$$\align (1,i_0),(2,i_0),\ldots,(r-1,i_0),(r,i_0)&\in\tau,\\
(1,i_0+1),(2,i_0+1),\ldots,(r-1,i_0+1)&\in\tau,
\quad(r,i_0+1)\notin\tau,\endalign$$
and $$(k,i_0),(k,i_0+1)\notin\tau\text{ for }r<k<i,\quad(i_0,k),(i_0+1,k)\notin
\tau\text{ for }i_0+1<k<n.$$
The only thing preventing $i_0$ and $i_0+1$ from being interchangeable in
$\tau$ is that $(r,i_0)\in\tau$ but $(r,i_0+1)\notin\tau$. So if we reverse
the arcs $(\sigma(i_0),\sigma(i_0+1))$ and $(-\sigma(i_0+1),-\sigma(i_0))$,
we must also reverse the arcs connecting $\pm\sigma(r)$ to $\mp\sigma(i_0)$
and to $\mp\sigma(i_0+1)$ in order to preserve $\tau$. This is part of what
we do to obtain $\phichk(\gee)$. In addition, we reverse the arcs
connecting $0$, $\sigma(i_0)$, and $-\sigma(i_0)$ and the arcs connecting
$0$, $\sigma(i_0+1)$, and $-\sigma(i_0+1)$. The set of all these arcs may
be written as a disjoint union of cycles:
$$\align&\{(\sigma(i_0),\sigma(i_0+1)),(\sigma(i_0+1),0),
(0,-\sigma(i_0+1))\},\\
&\{(-\sigma(i_0+1),-\sigma(i_0)),(-\sigma(i_0),0),(0,\sigma(i_0))\},\\
\noalign{\hbox{and}}
&\{(\sigma(i_0),-\sigma(r)),(-\sigma(r),\sigma(i_0+1)),
(\sigma(i_0+1),-\sigma(i_0+1)),\\
&\qquad(-\sigma(i_0+1),\sigma(r)),(\sigma(r),-\sigma(i_0)),(-\sigma(i_0),
\sigma(i_0))\}.\endalign$$
If $r>i_0$, then the only thing preventing $i_0$ and $i_0+1$ from
being interchangeable in $\tau$ is that $(i_0,r+1)\in\tau$ but
$(i_0+1,r+1)\notin\tau$. The cycles we reverse to obtain
$\phichk(\gee)$ are those shown above, except that $r$ is replaced
with $r+1$.

The digraph $\gee\in\Cee_3$ portrayed in Figure 6.3 gives an example
of the situation in case (3). We have $\sigma(2)=1$, $\sigma(3)=3$, and
$o(1,\gee)=o(3,\gee)=2$. We obtain $\phichk(\gee)$ by reversing the
bold arcs, which contribute $tx_1^2x_2^{\0}x_3^2$ to $\wcheck(\gee)$.

\medpagebreak
\centerline{\psfig{figure=fig6.3.eps}}
\centerline{\smc Figure 6.3}
\medpagebreak

We find that $\phichk(\gee)^+$ is transitive, corresponding to
$\sigma\cdot (i_0\,i_0+1)$; meanwhile, $\tau(\phichk(\gee))=\tau$,
$\omega_0(\phichk(\gee)) =\omega_0$, and
$\omega_\pm(\phichk(\gee))=\omega_\pm$. So once again, we have
$\phichk(\phichk(\gee))=\gee$ and
$\wcheck(\phichk(\gee))=-\wcheck(\gee)$. This completes the
description of $\phichk$ in case
$o(\sigma(i_0),\gee)=o(\sigma(i_0+1),\gee)$.

Now suppose $o(\sigma(i_0),\gee)=o(\sigma(i_0+2),\gee)$. There is only
one way this can happen: $\#(i_0,\tau)=\#(i_0+1,\tau) =\#(i_0+2,\tau)$
and $i_0\notin\omega_0$, $i_0\notin\omega_\pm$, $i_0+2\in\omega_0$,
$i_0+2\in\omega_\pm$. To obtain $\phichk(\gee)$, we reverse the arcs
between $0$ and $\pm\sigma(i_0)$, between $0$ and $\pm\sigma(i_0+2)$,
between $\sigma(i_0)$, $\sigma(i_0+1)$, and $\sigma(i_0+2)$, and
between $-\sigma(i_0)$, $-\sigma(i_0+1)$, and $-\sigma(i_0+2)$. This
set of arcs may be written as a disjoint union of cycles:
$$\align&\{(\sigma(i_0),\sigma(i_0+1)),(\sigma(i_0+1),\sigma(i_0+2)),
(\sigma(i_0+2),0),(0,\sigma(i_0))\},\\
&\{(-\sigma(i_0),0),(0,-\sigma(i_0+2)),(-\sigma(i_0+2),-\sigma(i_0+1)),
(-\sigma(i_0+1),-\sigma(i_0))\},\\ \noalign{\hbox{and}}
&\{(\sigma(i_0),\sigma(i_0+2)),(\sigma(i_0+2),-\sigma(i_0+2)),
(-\sigma(i_0+2),-\sigma(i_0)),(-\sigma(i_0),\sigma(i_0))\}.\endalign$$
Now $\phichk(\gee)^+$ is transitive, with $\sigma(\phichk(\gee))=
\sigma\cdot(i_0\,i_0+2)$, and we have
$\omega_0(\phichk(\gee))=\omega_0$ and
$\omega_\pm(\phichk(\gee))=\omega_\pm$. Meanwhile, $i_0$ and $i_0+2$
are interchangeable in $\tau$, so $\tau(\phichk(\gee)) =\tau$. These
observations tell us that $\phichk(\phichk(\gee))=\gee$, and it is
easy to see that $\wcheck(\phichk(\gee))=-\wcheck(\gee)$.

We are now done with Phase 3.

\head Phase 4\endhead

This will be the last phase of our construction of $\phitld$ and
$\phichk$; we are already finished with $\phihat$.

\subhead Construction of $\phitld$\endsubhead Given
$\gee\in\Cee_n\setminus\Cee_n^*$, with $\gee^+$ transitive and
$\taubar=\taubar(\gee)$ an order ideal of $\nrctwo$, we must have
$o(\sigma(i),\gee)\le o(\sigma(i+1),\gee)$ for some $i$. Let $i_0$ be
the smallest $i$ with this property. Then we have
$\#_0(i_0,\tau)=\#_0(i_0+1,\tau)$, $i_0\notin\omega_\pm$, and
$i_0+1\in\omega_\pm$. We obtain $\phitld(\gee)$ from $\gee$ by
reversing the cycle $$\{(\sigma(i_0),\sigma(i_0+1)),
(\sigma(i_0+1),-\sigma(i_0+1)),(-\sigma(i_0+1),-\sigma(i_0)),
(-\sigma(i_0),\sigma(i_0))\}.$$ Evidently $\wtilde(\phitld(\gee))=
-\wtilde(\gee)$. Meanwhile, $\phitld(\gee)^+$ is transitive, with
corresponding permutation $\sigma\cdot(i_0\,i_0+1)$, and
$\omega_\pm(\phitld(\gee)) =\omega_\pm$. Finally, Lemma 5.2(b) tells
us that $i_0$ and $i_0+1$ are interchangeable in $\taubar$; this means
that $\taubar(\phitld(\gee))=\taubar$. We conclude that
$\phitld(\phitld(\gee))=\gee$. This completes the proof that
$\sum_{\gee\in\Cee_n\setminus\Cee_n^*}\wtilde(\gee)=0$.

\subhead Construction of $\phichk$\endsubhead
The only $\gee\in\Cee_n\setminus\Cee_n^{**}$ that remain after Phases
1--3 are those for which $\gee^+$ is transitive and $\tau$ is an order
ideal of $\nctwo$, but at least one of the following conditions holds:

\smallpagebreak
(i) $o(\sigma(i),\gee)<o(\sigma(i+1),\gee)$ for
some $i$;

(ii) $\omega_0\not\subseteq\omega_\pm$;

(iii) $\omega_\pm\setminus\omega_0$ cannot be written as a disjoint
union of pairs $\{j,j+1\}$ with the elements of each pair being
interchangeable in $\tau$.
\smallpagebreak

For such $\gee$, we shall obtain $\phichk(\gee)$ by
reversing a cycle of one of the following forms:
$$\align&\{(\sigma(i),0),(0,-\sigma(i)),(-\sigma(i),\sigma(i))\},\\
&\{(\sigma(i),-\sigma(i)),(-\sigma(i),0),(0,\sigma(i))\},\\
\noalign{\hbox{or}}
&\{(\sigma(i),\sigma(i+1)),(\sigma(i+1),-\sigma(i+1)),
(-\sigma(i+1),-\sigma(i)),(-\sigma(i),\sigma(i))\}.\endalign$$
It is easy to see that for any $\gee'$ obtained from $\gee$ by
reversing such a cycle, we have $\wcheck(\gee')=-\wcheck(\gee)$. To
ensure that $\phichk(\gee)\in\Cee_n\setminus\Cee_n^{**}$ and
$\phichk(\phichk(\gee))=\gee$, we need some way of deciding which
cycle to reverse. The following discussion explains how this decision
is made.

Let $c_1=\{i\in[n-1]:o(\sigma(i),\gee)<o(\sigma(i+1),\gee)\}$ and let
$c_2=\omega_0\setminus\omega_\pm$. These sets correspond to conditions
(i) and (ii) above. To describe a set corresponding to (iii) takes a
little more effort. We begin by writing $\omega_\pm\setminus\omega_0$
as a disjoint union of sets $R_j=\{i_j,i_j+1,\ldots,i_j+r_j-1\}$ such
that (a), the elements of $R_j$ are pairwise interchangeable in
$\tau$; and (b), no subset of $\omega_\pm\setminus\omega_0$ with
elements pairwise interchangeable in $\tau$ contains $R_j$ as a proper
subset. Observe that $\gee\in\Cee_n^{**}$ only if every $r_j$ is even.

Figure 6.4 shows a triple $(\tau,\omega_0,\omega_\pm)$ of sets
corresponding to some digraphs in $\Cee_6$. In this and several later
figures, the sets $\omega_0$ and $\omega_\pm$ are described by the
squares on the diagonal: the square $(i,i)$ is vertically lined if
$i\in\omega_0$ and horizontally lined if $i\in\omega_\pm$. Here, we see
that $\omega_\pm\setminus\omega_0=\{2,3,4,5\}$ and the sets $R_j$ are
$\{2,3,4\}$ and $\{5\}$.

\medpagebreak
\centerline{\psfig{figure=fig6.4.eps}}
\centerline{\smc Figure 6.4}
\medpagebreak

Having written $\omega_\pm\setminus\omega_0$ as a disjoint union of
sets $R_j$ in the manner described above, let $c_3$ be the set
containing the largest element of each set $R_j$ of odd cardinality.
This is the set corresponding to condition (iii). For a digraph
corresponding to the sets shown in Figure 6.4, we would have
$c_3=\{4,5\}$. Observe that the sets $c_1$, $c_2$, and $c_3$ are
pairwise disjoint: $c_2=\omega_0\setminus\omega_\pm$ and
$c_3\subseteq\omega_\pm\setminus\omega_0$, whereas if $i\in c_1$, then
we must have $i\notin\omega_0$ and $i\notin\omega_\pm$.

Now we are ready to define $\phichk(\gee)$. If $\gee$ survived Phases
1--3 and the sets $c_1$, $c_2$, and $c_3$ described above are all
empty, then $\gee$ is in $\Cee_n^{**}$. Otherwise, let $i_0=\min(c_1\cup
c_2\cup c_3)$. Exactly one of the following conditions holds:

\medpagebreak
(1) $i_0\in c_1$: in this case, $i_0\notin\omega_0$, $i_0\notin\omega_\pm$,
$i_0+1\in\omega_0$, $i_0+1\in\omega_\pm$, and $i_0$ and $i_0+1$ are
interchangeable in $\tau$.

(2a) $i_0\in c_2$, with $i_0<n$; $i_0$ and $i_0+1$ interchangeable in
$\tau$; and $i_0+1\in\omega_\pm\setminus\omega_0$.

(2b) $i_0\in c_2$, with $i_0=n$, or $i_0$ and $i_0+1$ not
interchangeable in $\tau$, or $i_0+1\in\omega_0$, or
$i_0+1\notin\omega_\pm$.

(3) $i_0\in c_3$: in this case, $i_0=n$, or $i_0$ and $i_0+1$ are not
interchangeable in $\tau$, or $i_0+1\in\omega_0$, or
$i_0+1\notin\omega_\pm$.
\medpagebreak

Suppose (1) holds. Then we obtain $\phichk(\gee)$ by reversing the cycle
$$\{(\sigma(i_0),\sigma(i_0+1)),
(\sigma(i_0+1),-\sigma(i_0+1)),(-\sigma(i_0+1),-\sigma(i_0)),
(-\sigma(i_0),\sigma(i_0))\}.$$ We find that
$\sigma(\phichk(\gee))=\sigma\cdot(i_0\,i_0+1)$ and that
$\tau(\phichk(\gee))=\tau$, since $i_0$ and $i_0+1$ are
interchangeable in $\tau$. Furthermore,
$\omega_0(\phichk(\gee))=\{i_0\}\cup\omega_0\setminus\{i_0+1\}$ and
$\omega_\pm(\phichk(\gee))=\omega_\pm$. These observations imply that
when we apply $\phichk$ to $\phichk(\gee)$, we shall find the same
$i_0$ as before, but condition (2a) will hold.

If (2a) holds, then we obtain $\phichk(\gee)$ by reversing the same cycle
described in the previous paragraph, and we find that (1) holds for
$\phichk(\gee)$. Combined with the previous paragraph, this shows that
$\phichk(\phichk(\gee))=\gee$ for all $\gee$ such that (1) or (2a) is
satisfied.

If (2b) holds, then we obtain $\phichk(\gee)$ by reversing the cycle
$$\{(\sigma(i_0),0),(0,-\sigma(i_0)),(-\sigma(i_0),\sigma(i_0))\}.$$
Evidently this reversal does not change $\sigma$ or $\tau$; it simply
removes $i_0$ from $\omega_0$ and adds it to $\omega_\pm$. So when we
apply $\phichk$ to $\phichk(\gee)$, we shall find the same $i_0$ as
before, and (3) will hold.
Finally, if (3) holds, then to obtain $\phichk(\gee)$, we
reverse the cycle $$\{(\sigma(i_0),-\sigma(i_0)),(-\sigma(i_0),0),
(0,\sigma(i_0))\};$$ condition (2b) will hold for the digraph we obtain from
this cycle reversal. We conclude that $\phichk(\phichk(\gee))=\gee$ whenever
$\gee$ is such that (2b) or (3) is satisfied.

With this, we have completed the proof of Lemma 4.1.

\specialhead 7.\quad Correspondence\endspecialhead

We shall prove Lemma 4.2 by showing that the weight of each digraph in
$\Bee^*_n$ is a term on the sum side of \thetag{BD}, and similarly for
$\Cee^*_n$ and \thetag{BC} and for $\Cee^{**}_n$ and \thetag{CD}.

\head From Digraphs to Partitions\endhead

For any $\gee\in\Bee_n\cup\Cee_n$ with $\gee^+$ transitive, let
$\lambda=\lambda(\gee)\in\N_0^n$ be such that
$\lambda_i+n-i=o(\sigma(i),\gee)$ for each $i\in [n]$. In other words,
$\lambda_i=\#(i,\tau)+ \chi(i\in\omega_0)$ if $\gee\in\Bee_n$ and
$\lambda_i=\#_0(i,\taubar)+
\chi(i\in\omega_\pm)=\#(i,\tau)+\chi(i\in\omega_0)+\chi(i\in\omega_\pm)$
if $\gee\in\Cee_n$. We can express the weight(s) of $\gee$ in terms of
$\lambda$. Namely,
$$\align\what(\gee)&=(-1)^\sigma(-1)^{|\tau|+|\omega_0|}t^{|\omega_0|}
x^{\sigma(\lambda+\delta_n)},\quad\text{for }\gee\in\Bee_n;\tag7.1\\
\wtilde(\gee)&=(-1)^\sigma(-1)^{|\taubar|}t^{|\omega_\pm|}
x^{\sigma(\lambda+\delta_n)},\quad\text{for }\gee\in\Cee_n;\tag7.2\\
\wcheck(\gee)&=(-1)^\sigma(-1)^{|\tau|+|\omega_0|}
t^{(|\omega_0|+|\omega_\pm|)/2}
x^{\sigma(\lambda+\delta_n)},\quad\text{for }\gee\in\Cee_n.\tag7.3
\endalign$$
Now if $\gee\in\Bee_n^*\cup\Cee_n^*\cup\Cee_n^{**}$, then
$o(\sigma(1),\gee)>o(\sigma(2),\gee)>\cdots>o(\sigma(n),\gee)$. This
implies that $\lambda(\gee)$ is a partition with at most $n$ parts.
For $\gee\in\Bee_n^*\cup\Cee_n^{**}$, let $\zeta=(\#(1,\tau),
\ldots,\#(n,\tau))$; for $\gee\in\Cee_n^*$, let $\eta=
(\#_0(1,\taubar),\ldots,\#_0(n,\taubar))$. Lemma 5.1 implies that
$\zeta\in P_{-\!1}(n)$ and $\eta\in P_0(n)$. We observe that:

\smallpagebreak
If $\gee\in\Bee_n^*$, then $0\le\lambda_i-\zeta_i=\chi(i\in\omega_0)
\le 1$ for all $i\in [n]$.

If $\gee\in\Cee_n^*$, then $0\le\lambda_i-\eta_i=\chi(i\in\omega_\pm)
\le 1$ for all $i\in [n]$.

If $\gee\in\Cee_n^{**}$, then
$0\le\lambda_i-\zeta_i=\chi(i\in\omega_0) +\chi(i\in\omega_\pm)\le 2$
for all $i\in [n]$. Furthermore, we have
$\{i:\lambda_i-\zeta_i=1\}=\omega_\pm\setminus\omega_0$, which is a
disjoint union of pairs $\{j,j+1\}$ such that $j$ and $j+1$ are
interchangeable in $\tau$, or equivalently, such that
$\zeta_j=\zeta_{j+1}$.
\smallpagebreak

The latter observation tells us that $\lambda(\gee)\in P_{-\!1,1}(n)$
whenever $\gee\in\Cee_n^{**}$. We see also that if $\gee\in\Bee_n^*$
(respectively, $\Cee_n^*$), then there exists a partition $\xi\in
P_{-\!1}(n)$ (respectively, $P_0(n)$) such that the skew diagram
$\lambda(\gee)-\xi$ is a vertical strip. We claim that $\lambda(\gee)
\in P_{-\!1,0}(n)$ if $\gee\in\Bee_n^*$ and $\lambda(\gee)\in P_{0,1}(n)$
if $\gee\in\Cee_n^*$. These are consequences of:

\proclaim{Lemma 7.1} {\rm (\cite{S}, Lemma 3.4.2) (a)} Let
$\lambda=(\alpha_1,\ldots,\alpha_p\, |\,\beta_1,\ldots,\beta_p)$. Then
there exists $\xi\in P_{-\!1}$ such that $\lambda-\xi$ is a vertical
strip if and only if
$\beta_1\ge\alpha_1\ge\beta_2\ge\alpha_2\ge\cdots\ge\beta_p\ge\alpha_p$.

\rom{(b)} Let
$\lambda=(\alpha_1,\ldots,\alpha_p\,|\,\beta_1,\ldots,\beta_p)$.
Then there exists $\xi\in P_0$ such that $\lambda-\xi$ is a vertical
strip if and only if $\beta_1+1\ge\alpha_1\ge\beta_2+1\ge\alpha_2\ge
\cdots\ge\beta_p+1\ge\alpha_p$.
\endproclaim

Statement (b) is due to Okada. The ``if'' part follows from Lemma 3.7 of
\cite{O}, and the ``only if'' part is contained in Lemma 3.8 of the same work.
Okada does not state Lemma 7.1(a), but it is implicit in the identity
equivalent to \thetag{BD} that he states without proof in \cite{O}.

\demo{Proof of Lemma \rom{7.1(a)}} ``Only if'': Suppose $\lambda=
(\alpha_1,\ldots,\alpha_p\,|\,\beta_1,\ldots,\beta_p)$ with either
$\alpha_i <\beta_{i+1}$ for some $i$ ($1\le i\le p-1$) or
$\beta_i<\alpha_i$ for some $i$ ($1\le i\le p$). Let $\xi\in P_{-\!1}$
be such that $\xi\subseteq \lambda$. If
$\xi=(\gamma_1-1,\ldots,\gamma_q-1\,|\,\gamma_1,\ldots,\gamma_q)$,
then $q\le p$ and we have $\gamma_j-1\le\alpha_j$ and
$\gamma_j\le\beta_j$ for each $j$, $1\le j\le q$. If
$\alpha_i<\beta_{i+1}$ and $i\le q$, then we have
$\xi'_i=\gamma_i+i<\beta_{i+1}+i+1=\lambda'_{i+1}$. Let
$k=\beta_{i+1}+i+1$. Then $\lambda_k\ge i+1$, but $\xi_k<i$. If
$\alpha_i<\beta_{i+1}$ and $i>q$, then $\alpha_i>\alpha_{i+1}$ implies
$\alpha_i\ge 1$; we have $\lambda_i\ge i+1$ but $\xi_i\le q<i$. In
either case, $\lambda_i-\xi_i\ge 2$. And if $\beta_i<\alpha_i$, we
must have $\gamma_i<\alpha_i$, so that $\lambda_i
-\xi_i=\alpha_i-(\gamma_i-1)\ge 2$. We have shown that $\lambda-\xi$
is not a vertical strip.

``If'': Given $\lambda=(\alpha_1,\ldots,\alpha_p\,|\,\beta_1,\ldots,
\beta_p)$ with $\beta_1\ge\alpha_1\ge\beta_2\ge\alpha_2\ge\cdots
\ge\beta_p\ge\alpha_p$, let $q=p-\chi(\beta_p=0)$. For $1\le i\le q$,
let $\gamma_i=\alpha_i+\chi(\beta_i>\alpha_i)$. It is not hard to show
that $\gamma_1>\gamma_2>\cdots>\gamma_q\ge0$ (assuming otherwise, we
would conclude that $\beta_i\le\beta_{i+1}$ for some $i$). So it makes
sense to define
$\xi=(\gamma_1-1,\ldots,\gamma_q-1\,|\,\gamma_1,\ldots,\gamma_q)$, and
we have $\xi\in P_{-\!1}$ and $\xi\subseteq\lambda$. For example, if
$\lambda=(2,1,0\,|\,4,1,0)$, as in the diagram on the left in Figure
7.1, then $\xi=(2,0\,|\,3,1)$; if $\lambda=(4,1,0\,|\,4,3,1)$, then
$\xi=(3,1,0\,|\, 4,2,1)$, as we see in the diagram on the right.

\medpagebreak
\centerline{\psfig{figure=fig7.1.eps}}
\centerline{\smc Figure 7.1}
\medpagebreak

\noindent Now if $1\le i\le q$, then
$\lambda_i-\xi_i=1-\chi(\beta_i>\alpha_i)$. If $q=p-1$, then
$\beta_p=0$, which implies that $\alpha_p=0$ and $\lambda_p=p$;
meanwhile, we have $\gamma_{p-1} \ge\alpha_{p-1}\ge1$, so
$\xi_p=p-1$. We have shown that $0\le\lambda_i-\xi_i \le 1$ whenever
$1\le i\le p$. Suppose $i>p$ and $\lambda_i-\xi_i\ge2$. Let
$k=\xi_i+1$, so that $\xi_i<k$ and $p\ge\lambda_i\ge k+1$. Then
$k+\gamma_k=\xi'_k<i$ and $k+1+\beta_{k+1}=\lambda'_{k+1}\ge i$, so
we have $\beta_{k+1}+1>\gamma_k$. If $\gamma_k=\alpha_k+1$, then
$\alpha_k< \beta_{k+1}$; otherwise, $\gamma_k=\alpha_k=\beta_k$ and
$\beta_k\le \beta_{k+1}$. We conclude from this contradiction that
$0\le\lambda_i-\xi_i \le 1$ for all $i>p$.\qed
\enddemo

The proof of Lemma 7.1(b) is very similar. One way to define $\xi$ in
this case is to put $\gamma_i=\alpha_i-\chi(\alpha_i>\beta_i)$ for $1
\le i\le p$, then let $\xi=(\gamma_1,\ldots,\gamma_p\,|\,\gamma_1,\ldots,
\gamma_p)$.

Recall that in Section 2, we defined $P_{-\!1,1}(n)$ in terms of
dominos: $\lambda\in P_{-\!1,1}(n)$ if and only if
$\lambda-\kappa$ is a disjoint union of dominos, with
no more than one domino per row of $D(\lambda)$, for some $\kappa\in
P_{-\!1}(n)$. If we call any single-element subset of $\N^2$ a
``monomino,'' then Lemma 7.1 tells us that $\lambda\in P_{-\!1,0}(n)$
(respectively, $\lambda\in P_{0,1}(n)$) if and only if
$D(\lambda)\setminus D(\xi)$ is a disjoint union of monominos, with no
more than one such in any one row of $D(\lambda)$, for some $\xi\in
P_{-\!1}(n)$ (respectively, $P_0(n)$).

By virtue of Lemma 7.1 and formulas \thetag{7.1}--\thetag{7.3}, we have the
following: $$\align\sum_{\bee\in\Bee_n^*}\what(\bee)&=\!\!\!
\sum\Sb\lambda\in P_{-\!1,0}(n)\\\sigma\in S_n\endSb
\!\!\!(-1)^\sigma x^{\sigma(\lambda+\delta_n)}
\sum_{\tau,\omega_0}
(-1)^{|\tau|+|\omega_0|}t^{|\omega_0|},\tag7.4bd\\
\noalign{
\hbox{where $\lambda_i=\#(i,\tau)+\chi(i\in\omega_0)$ for all $i\in [n]$;}}
\sum_{\cee\in\Cee_n^*}\wtilde(\cee)&=\!\!\!
\sum\Sb\lambda\in P_{0,1}(n)\\\sigma\in S_n\endSb
\!\!\!(-1)^\sigma x^{\sigma(\lambda+\delta_n)}
\sum_{\taubar,\omega_\pm}
(-1)^{|\taubar|}t^{|\omega_\pm|},\tag7.4bc\\
\noalign{
\hbox{where $\lambda_i=\#_0(i,\taubar)%
+\chi(i\in\omega_\pm)$ for all $i\in [n]$;}}
\sum_{\cee\in\Cee_n^{**}}\wcheck(\cee)&=\!\!\!
\sum\Sb\lambda\in P_{-\!1,1}(n)\\\sigma\in S_n\endSb
\!\!\!(-1)^\sigma x^{\sigma(\lambda+\delta_n)}\!\!
\sum_{\tau,\omega_0,\omega_\pm}\!\!
(-1)^{|\tau|+|\omega_0|}t^{(|\omega_0|+|\omega_\pm|)/2},\tag7.4cd\\
\noalign{
\hbox{where $\lambda_i=\#(i,\tau)%
+\chi(i\in\omega_0)+\chi(i\in\omega_\pm)$ for all $i\in [n]$.}}
\endalign$$

In these formulas, $\tau$ and $\taubar$ are order ideals of $\nctwo$
and $\nrctwo$ respectively, and $\omega_0$ and $\omega_\pm$ are
subsets of $[n]$. We can now complete the proof of Lemma 4.2 by proving:

\proclaim{Lemma 7.2}\rom{(bd)} For each $\lambda\in P_{-\!1,0}(n)$,
the inner sum on the right side of \thetag{7.4bd} is
$$(-1)^{|\lambda|-|\mu|/2}t^{|\lambda|-|\mu|}(1-t^2)^{y(\lambda)}.$$

\rom{(bc)} For each $\lambda\in P_{0,1}(n)$, the inner sum on the
right side of \thetag{7.4bc} is
$$(-1)^{(|\nu|+p(\nu))/2}t^{|\lambda|-|\nu|}(1-t)^{\chi(\exists i,
\lambda_i=i)}(1-t^2)^{z(\lambda)}.$$

\rom{(cd)} For each $\lambda\in P_{-\!1,1}(n)$, the inner sum on the
right side of \thetag{7.4cd} is
$$(-1)^{|\kappa|/2+q(\lambda)}t^{(|\lambda|-|\kappa|)/2}
(1-t)^{\chi(\exists i,\lambda_i=i)}(1-t^2)^{z(\lambda)}.$$
\endproclaim

\head Proofs of Lemmas 2.1 and 2.3\endhead

We require Lemma 2.1 in our proofs of (bd) and (bc) and Lemma 2.3 in
our proof of (cd). Since we have not yet proved these lemmas, we do so
now. It should be mentioned that the proof in \cite{S} of Lemma 3.1.3,
which is the same as Lemma 2.3 here, is invalid.

\demo{Proof of Lemma \rom{2.1}} (a) Let $\lambda\in P_{-\!1,0}(n)$
with Frobenius representation $(\alpha_1$, $\ldots\,$,
$\alpha_p\,|\,\beta_1$, $\ldots\,$, $\beta_p)$. We claim that
$\mu(\lambda)\subseteq\lambda$. Suppose $i,j$ are such that $i<j$ and
$(i,j-1)\notin D(\lambda)$. We have $j-1>\lambda_i$, so
$\lambda_i+\lambda_j<\lambda_j+j-1$. If $i\ge p$, then we have $j>p$
and $\lambda_j\le p\le i$. If $i<p$, then
$j>\lambda_i+1=\alpha_i+i+1\ge\beta_{i+1}+i+1=\lambda'_{i+1}$, which
means that $\lambda_j<i+1$. In either case,
$\lambda_i+\lambda_j<i+j-1$, so $(i,j-1)\notin D(\mu)$. If $i<j$ and
$(j,i)\notin D(\lambda)$, then $\lambda_i+\lambda_j<\lambda_i+i$, and
we shall show that $\lambda_i\le j-1$. If $i>p$, then $\lambda_i<i\le
j-1$; if $i\le p$, then $\lambda_i=\alpha_i+i\le\beta_i+i=\lambda'_i$,
and $\lambda'_i\le j-1$ since $(j,i)\notin D(\lambda)$. Again we have
$\lambda_i+\lambda_j<i+j-1$, and $(j,i)\notin D(\mu)$. This proves our
claim. It remains to show that if $\xi\subseteq\lambda$ and $\xi\in
P_{-\!1}$, then $\xi\subseteq\mu$. This is fairly easy. If $\xi\in
P_{-\!1}$ and $\xi\not\subseteq\mu$, then $(i,j-1)$, $(j,i)\in
D(\xi)\setminus D(\mu)$ for some $i,j$ with $i<j$. For such $i,j$ we
have $\lambda_i+\lambda_j<i+j-1$, but if both $(i,j-1)$ and $(j,i)$
are in $D(\lambda)$, then $\lambda_i\ge j-1$ and $\lambda_j\ge i$,
meaning that $\lambda_i+\lambda_j\ge i+j-1$. So $(i,j-1)$ and $(j,i)$
are not both in $D(\lambda)$, and we conclude
$\xi\not\subseteq\lambda$.

(b) The proof is much like that of (a). Let $\lambda=(\alpha_1$,
$\ldots\,$, $\alpha_p\,|\,\beta_1$, $\ldots\,$, $\beta_p)\in
P_{0,1}(n)$. If $(i,j)\notin D(\lambda)$, then $j>\lambda_i$. We shall
show that $i\ge\lambda_j$, from which it will follow that $(i,j)\notin
D(\nu)$. If $i<p$, then
$j>\lambda_i=\alpha_i+i\ge\beta_{i+1}+i+1=\lambda'_{i+1}$, from which
we conclude $\lambda_j<i+1$. If $i\ge p$, then if $j>p$, then
$\lambda_j\le p\le i$. Otherwise, $j\le p$; write $\lambda'_j+1=
\beta_j+j+1\ge\alpha_j+j=\lambda_j$, and observe that since
$(i,j)\notin D(\lambda)$, we have $i\ge\lambda'_j+1$. We have shown
that $\nu\subseteq\lambda$, and the proof that $\xi\subseteq\nu$ for
any other $\xi\in P_0$ such that $\xi\subseteq\lambda$ is easy. \qed
\enddemo

\demo{Proof of Lemma \rom{2.3}} Let $\lambda\in P_{-\!1,1}(n)$. To
prove that there is a partition $\kappa\in K(\lambda)$ such that
$\eta\subseteq\kappa$ for all $\eta\in K(\lambda)$, we shall show that
if $\kappa,\eta\in K(\lambda)$ with $\eta\not\subseteq\kappa$, then
there exists $\kappabar\in K(\lambda)$ such that $D(\kappa)$ is
strictly smaller than $D(\kappabar)$. We shall describe $\kappabar$ in
two ways: by giving its Frobenius representation and by identifying
the dominos that are removed from $\lambda-\kappa$ to give
$\lambda-\kappabar$.

Write $\kappa=(\alpha_1-1$, $\ldots\,$, $\alpha_p-1\,|\,\alpha_1$,
$\ldots\,$, $\alpha_p)$ and $\eta=(\beta_1-1$, $\ldots\,$,
$\beta_q-1\,|\,\beta_1$, $\ldots\,$, $\beta_q).$ There are two ways in
which we can have $\eta\not\subseteq\kappa$: (1) $\alpha_i\ge\beta_i$
for all $i\in [p]$, but $p<q$; and (2) $\alpha_i<\beta_i$ for some
$i\le\min\{p,q\}$. We consider these two cases separately.

\medpagebreak
In case (1), we must have $\alpha_p\ge2$, meaning
$\kappa_p>\kappa_{p+1}=\kappa_{p+2}=p$. Since $0\le
\lambda_i-\kappa_i\le2$ for all $i\in[n]$, we have
$p+1\le\eta_{p+1}\le\lambda_{p+1}\le p+2$ and
$p+1\le\eta_{p+2}\le\lambda_{p+2}\le p+2$. We consider three subcases:

\smallpagebreak
\begingroup\advance\leftskip by\parindent  % shift right
(i) $\lambda_{p+1}=p+1$: We have $\lambda_{p+2}=p+1$, since
$\kappa$ would not be in $K(\lambda)$ otherwise. Let $\kappabar=
(\alpha_1-1,\ldots,\alpha_p-1,0\,|\,\alpha_1,\ldots,\alpha_p,1)$.

{\sl Dominos\/}: Remove $\{(p+1,p+1),(p+2,p+1)\}$.

\smallpagebreak
(ii) $\eta_{p+1}=p+1,\,\lambda_{p+1}=p+2$: We have $\beta_{p+1}=1$, so
$\eta_{p+2}=p+1$. If $\lambda_{p+2}=p+1$, then we must have
$\eta_p=p+1$ (otherwise $\eta$ could not be in $K(\lambda)$) and
$\lambda_p=p+2$. Meanwhile, $\lambda_{p+1}-\kappa_{p+1}=2$ and
$\lambda_{p+2}-\kappa_{p+2}=1$, so we must have $\lambda_{p+3}=p+1$
and $\kappa_{p+3}=\kappa_{p+2}=p$. This tells us that $\alpha_p\ge3$
(in fact, $\alpha_p=3$, since otherwise
$\kappa_p>p+2=\lambda_p$). Let $\kappabar=
(\alpha_1-1,\ldots,\alpha_p-1,1\,|\,\alpha_1,\ldots,\alpha_p,2)$. If
$\lambda_{p+2}=p+2$, then let $\kappabar=
(\alpha_1-1,\ldots,\alpha_p-1,0\,|\,\alpha_1,\ldots,\alpha_p,1)$.

{\sl Dominos\/}: If $\lambda_{p+2}=p+1$, remove $\{(p+1,p+1),(p+1,p+2)\}$
and $\{(p+2,p+1),(p+3,p+1)\}$. If $\lambda_{p+2}=p+2$, replace
$\{(p+1,p+1),(p+1,p+2)\}$ and $\{(p+2,p+1),(p+2,p+2)\}$ with
$\{(p+1,p+2),(p+2,p+2)\}$.

\smallpagebreak
(iii) $\eta_{p+1}=p+2$: We have $\eta_{p+2}=\eta_{p+3}=p+1$. Since
$\lambda_{p+1}=\eta_{p+1}$ in this case, we must have
$p+1\le\lambda_{p+2}=\lambda_{p+3}\le p+2$ in order that $\eta$ be in
$K(\lambda)$. We must also have $\alpha_p\ge3$, since
$\beta_{p+1}=2$. Let $\kappabar=
(\alpha_1-1,\ldots,\alpha_p-1,1\,|\,\alpha_1,\ldots,\alpha_p,2)$.

{\sl Dominos\/}: Remove $\{(p+1,p+1),(p+1,p+2)\}$; if $\lambda_{p+2}=p+1$,
remove $\{(p+2,p+1),(p+3,p+1)\}$, otherwise, replace $\{(p+2,p+1),(p+2,p+2)\}$
and $\{(p+3,p+1),(p+3,p+2)\}$ with $\{(p+2,p+2),(p+3,p+2)\}$.

\smallpagebreak
We are now done with (1).

\endgroup  % end shift right

\medpagebreak

In case (2), choose the smallest $i$ for which $\alpha_i<\beta_i$. We
have $\alpha_j\ge\beta_j$ for all $j<i$, meaning that
$\kappa_j\ge\eta_j$ whenever $j<i$ or $j>i+\beta_i$ and that
$\kappa_{i-1}\ge\eta_{i-1}\ge\eta_i>\kappa_i$ if $i>1$.

Given a subset $X$ of $\N^2$ and a domino $D$, we shall say that $D$
{\sl crosses the border\/} of $X$ if one of the two elements of $D$ is
in $X$ and the other is not. Observe that whenever $\zeta\in
K(\lambda)$, the cardinality of $X\cap(\lambda-\zeta)$ is congruent
modulo $2$ to the number of dominos in $\lambda-\zeta$ that cross the
border of $X$. If $X$ is a subset of $\N^2$ such that $X\cap
D(\zeta)$ has even cardinality whenever $\zeta\in P_{-\!1}$, then we
have
$$\aligned\#\text{(dominos in $\lambda-\zeta$ that cross the border
of $X$)}&\equiv|X\cap(\lambda-\zeta)|\\
&\equiv|X\cap D(\lambda)|-|X\cap D(\zeta)|\\
&\equiv|X\cap D(\lambda)|\endaligned\tag7.5$$
for each $\zeta\in K(\lambda)$, where $\equiv$ stands for congruence
modulo $2$. We observe that if $X$ can be written as a (possibly
infinite) union of sets of the form $\{(k,l-1),(l,k):k<l\}$, then
$|X\cap D(\zeta)|$ is even for all $\zeta\in P_{-\!1}$.

We now begin the description of $\kappabar$ in case (2). Let
$r=i+\alpha_i$ in what follows. There are two subcases to consider:

\smallpagebreak
\begingroup\advance\leftskip by\parindent  % shift right
(i) $\alpha_i=\beta_i-2$: We have $\lambda_i=\eta_i=\kappa_i+2$,
$\kappa_r>\kappa_{r+1}=\kappa_{r+2}=i-1$, $\eta_{r+1}\ge\eta_{r+2}\ge i$,
and $i+1\ge\lambda_{r+1}\ge\lambda_{r+2}\ge i$.

Let $X=\{(k,l)\in\N^2:k,l>i\}$; then $|X\cap D(\zeta)|$ is
even for all $\zeta\in P_{-\!1}$. Since $\lambda_i-\kappa_i\ne1$,
there is no ``vertical'' domino in $\lambda-\kappa$ that crosses the
border of $X$. Similarly, no vertical domino in $\lambda-\eta$ crosses
the border of $X$. Any ``horizontal'' domino in $\lambda-\eta$ that
crosses the border of $X$ is of the form $\{(k,i),(k,i+1)\}$ for some
$k>r+2$ such that $\eta_k=i-1$ and $\lambda_k=i+1$. Since
$r+2=i+\beta_i$, we see that
$i-1=\eta_k\le\kappa_k\le\kappa_{r+2}=i-1$. This means that the domino
$\{(k,i),(k,i+1)\}$ is also in $\lambda-\kappa$. Now \thetag{7.5}
implies that the number of dominos in $\lambda-\kappa$ that cross the
border of $X$ is congruent modulo $2$ to the number of such dominos in
$\lambda-\eta$. So we must have an even number of horizontal dominos
in $\lambda-\kappa$ that cross the border of $X$ and are {\sl not\/}
in $\lambda-\eta$. The only possible dominos with these properties are
$\{(r+1,i),(r+1,i+1)\}$ and $\{(r+2,i),(r+2,i+1)\}$; either
$\lambda-\kappa$ contains both of these (in which case
$\lambda_{r+1}=i+1$), or it contains neither (in which case
$\lambda_{r+1}=i$). In each case, we obtain $\kappabar$ by replacing
$\alpha_i$ with $\beta_i=\alpha_i+2$. In terms of dominos, we remove
$\{(i,\kappa_i+1),(i,\kappa_i+2)\}$ from $\lambda-\kappa$; if
$\lambda_{r+1}=i+1$, then we replace $\{(r+1,i),(r+1,i+1)\}$ and
$\{(r+2,i),(r+2,i+1)\}$ with $\{(r+1,i+1),(r+2,i+1)\}$, otherwise, we
remove $\{(r+1,i),(r+2,i)\}$.

\smallpagebreak
(ii) $\alpha_i=\beta_i-1$: We have $\kappa_r>\kappa_{r+1}=i-1$ and
$\eta_{r+1}\ge i>\eta_{r+2}$. Either $\lambda_{r+1}=i+1$ or
$\lambda_{r+1}=i$. We consider these subsubcases separately.

If $\lambda_{r+1}=i+1$, let $X=\{(k,l)\in\N^2:k,l>i\}$. The horizontal
domino $\{(r+1,i),(r+1,i+1)\}$ crosses the border of $X$; it is in
$\lambda-\kappa$ but not in $\lambda-\eta$. Any horizontal domino in
$\lambda-\eta$ that crosses the border of $X$ must be of the form
$\{(k,i),(k,i+1)\}$ for some $k>r+1$ such that $\eta_k=i-1$ and
$\lambda_k=i+1$. Such a domino must also be in $\lambda-\kappa$. So
the number of horizontal dominos in $\lambda-\kappa$ that cross the
border of $X$ is one greater than the number of such dominos in
$\lambda-\eta$. Now \thetag{7.5} implies that the number of vertical
dominos in $\lambda-\kappa$ that cross the border of $X$ must differ
from the number of such dominos in $\lambda-\eta$ by an odd
integer. Since at most one vertical domino in either $\lambda-\kappa$
or $\lambda-\eta$ can cross the border of $X$, we either have the
domino $\{(i,\kappa_i+1),(i+1,\kappa_i+1)\}$ in $\lambda-\kappa$ (in
which case $\lambda_i=\eta_i=\kappa_i+1$) or the domino
$\{(i,\eta_i+1), (i+1,\eta_i+1)\}$ in $\lambda-\eta$ (in which case
$\lambda_i=\eta_i+1=\kappa_i+2$). In each case, we obtain $\kappabar$
from $\kappa$ by replacing $\alpha_i$ with $\alpha_i+1$ and
$\alpha_{i+1}$ with $\alpha_{i+1}+1$. (If $i=p$, then instead of the
latter replacement, we add to the rank of $\kappa$ by appending
$(0\,|\,1)$ to its Frobenius representation.) To obtain
$\lambda-\kappabar$ from $\lambda-\kappa$, we remove
$\{(r+1,i),(r+1,i+1)\}$, and we either remove
$\{(i,\kappa_i+1),(i+1,\kappa_i+1)\}$ or replace $\{(i,\kappa_i+1),
(i,\kappa_i+2)\}$ and $\{(i+1,\kappa_i+1),(i+1,\kappa_i+2)\}$ with
$\{(i,\kappa_i+2),(i+1,\kappa_i+2)\}$ according as
$\lambda_i-\kappa_i$ is $1$ or $2$.

If $\lambda_{r+1}=i$, then let $X=[r+1]\times[r]$. Observe that
$r=\kappa_i+1$. Since $\kappa_r>\kappa_{r+1}=\lambda_{r+1}-1$,
$\lambda-\kappa$ must contain the vertical domino
$\{(r+1,i),(r+2,i)\}$, which crosses the border of $X$. There is no
vertical domino in $\lambda-\eta$ that crosses the border of $X$.
Suppose $\{(k,r),(k,r+1)\}$ is a horizontal domino in $\lambda-\eta$
that crosses the border of $X$. Then $k>i$, since
$\eta_i=\kappa_i+1=r$. We have $\kappa_k\le\kappa_i=r-1$; since
$\lambda_k=r+1$, we conclude $\kappa_k=r-1$. This means that
$\{(k,r),(k,r+1)\}$ is also a domino in $\lambda-\kappa$. Now
\thetag{7.5} tells us we must have an odd number of horizontal dominos
in $\lambda-\kappa$ that cross the border of $X$ and are not in
$\lambda-\eta$. The only possible domino with these properties is
$\{(i,r),(i,r+1)\}$, since $\kappa_k\ge r$ whenever $k<i$. We obtain
$\lambda-\kappabar$ from $\lambda-\kappa$ by removing $\{(r+1,i),(r+2,i)\}$
and $\{(i,r),(i,r+1)\}$; the Frobenius representation of $\kappabar$ is
obtained from that of $\kappa$ by replacing $\alpha_i$ with $\alpha_i+2$.

This completes subcase (ii) of case (2); we have finished the proof of
Lemma 2.3.\qed

\endgroup  % end shift right

\enddemo

\head Proof of Lemma \rom{7.2(bd)}\endhead

For each $\lambda\in P_{-\!1,0}(n)$, we must identify which partitions
$\xi\in P_{-\!1}(n)$ are such that $\lambda-\xi$ is a
vertical strip. For example, Figure 7.2 shows that there are four
such partitions $\xi$ corresponding to $\lambda=(4,2,2,2,1)\in
P_{-\!1,0}(5)$.

\medpagebreak
\centerline{\psfig{figure=fig7.2.eps}}
\centerline{\smc Figure 7.2}
\medpagebreak

Let $\lambda\in P_{-\!1,0}(n)$. Suppose $\xi,\xi^*\in P_{-\!1}(n)$ are
such that $\lambda-\xi$ and $\lambda-\xi^*$ are vertical strips and
$\xi^*\subseteq\xi\subseteq\lambda$. Let $\tau$ and $\tau^*$ be the
order ideals of $\nctwo$ that correspond to $\xi$ and $\xi^*$ in the
sense of Lemma 5.1(a), and let $\omega_0=\{i\in[n]:\lambda_i-\xi_i=1\}$
and $\omega_0^*=\{i\in[n]:\lambda_i-\xi^*_i=1\}$. We have
$\tau^*\subseteq\tau$ and $\omega_0^*\supseteq\omega_0$;
if the elements of $\omega_0^*\setminus\omega_0$ are
$i_1<i_2<\cdots<i_{2r}$, then $\tau\setminus\tau^*=\{(i_1,i_{2r})$,
$(i_2,i_{2r-1})$, $\ldots\,$, $(i_r,i_{r+1})\}$. This means that if
$\gee,\gee^*\in\Bee_n^*$ are such that $\gee^+=(\gee^*)^+$,
$\tau=\tau(\gee)$, $\tau^*=\tau(\gee^*)$, $\omega_0=\omega_0(\gee)$,
and $\omega_0^*=\omega_0(\gee^*)$, then
$\what(\gee^*)=(-t^2)^{|\tau\setminus\tau^*|}\what(\gee)$. Also,
if $(i,j)\in\tau\setminus\tau^*$, then there is no other
ordered pair in $\tau\setminus\tau^*$ having $i$ or $j$ as one of its
components. So we see that if $(i,j)\in\tau\setminus\tau^*$, then
$(i,j)\in I(\tau)$: otherwise, $\tau\setminus\tau^*$ would contain
$(i,j+1)$ or $(i+1,j)$, or $\tau^*$ would not be an order ideal of
$\nctwo$. These observations imply that $\tau\setminus\tau^*$ is a
subset of $Y(\tau,\omega_0)=\{(i,j)\in I(\tau):i,j\notin\omega_0\}$.

Fix $\sigma\in S_n$ and $\lambda\in P_{-\!1,0}(n)$, and let $\xi$ be the
largest partition in $P_{-\!1}(n)$ such that $\lambda-\xi$ is a vertical
strip. Let $\tau$ be the order ideal of $\nctwo$ corresponding to
$\xi$ and let $\omega_0=\{i\in [n]:\lambda_i-\xi_i=1\}$. Observe
that $|\lambda|=2|\tau|+|\omega_0|$ and $|\xi|=2|\tau|$. We conclude
from the discussion in the previous paragraph that $\sum\what(\gee)$,
where $\gee$ ranges over all digraphs in $\Bee_n^*$ such that
$o(\sigma(i),\gee^+)=n-i$ and $o(\sigma(i),\gee)=\lambda_i+n-i$, is
$$\align&(-1)^\sigma x^{\sigma(\lambda+\delta_n)}
(-1)^{|\tau|+|\omega_0|} t^{|\omega_0|} \!\!\!\sum_{A\subseteq
Y(\tau,\omega_0)}\!\!\!(-t^2)^{|A|}\\ &\quad=(-1)^\sigma
x^{\sigma(\lambda+\delta_n)}(-1)^{|\lambda|-|\xi|/2}
t^{|\lambda|-|\xi|}(1-t^2)^{|Y(\tau,\omega_0)|}.\endalign$$ For
example, if $\lambda$ is as in Figure 7.2, then $\xi=(4,2,2,1,1)$ and
$Y(\tau,\omega_0)=\{(1,5),(2,3)\}$. We shall now prove that
$\xi=\mu(\lambda)$ and that $|Y(\tau,\omega_0)|=y(\lambda)$; this
will complete the proof of Lemma 7.2(bd).

Lemma 2.1(a) tells us that $\mu(\lambda)$ is the largest partition in
$P_{-\!1}(n)$ whose Ferrers diagram is contained in $D(\lambda)$. To
conclude that $\xi=\mu(\lambda)$, we need only show that $\lambda-\mu$
is a vertical strip. Write $\lambda=(\alpha_1$, $\ldots\,$,
$\alpha_p\,|\,\beta_1$, $\ldots\,$, $\beta_p)$ and suppose that
$\lambda_i-\mu_i>1$ for some $i\in [n]$. Then $(i,\lambda_i-1)\notin
D(\mu)$. If $i<\lambda_i$, then we have
$\lambda_i+\lambda_{\lambda_i}<i+\lambda_i-1$; otherwise,
$i>\lambda_i-1$ and we have
$\lambda_{\lambda_i-1}+\lambda_i<i+\lambda_i-2$. In the first case,
$\lambda_{\lambda_i}<i-1$, which means $\lambda'_{i-1} <\lambda_i$.
Since $i<\lambda_i$, we must have $i\le p$, so
$$\lambda'_{i-1}=i-1+\beta_{i-1}<i+\alpha_i=\lambda_i.$$ This implies
$\alpha_{i-1}>\beta_{i-1}$, meaning $\lambda\notin P_{-\!1,0}(n)$. In
the second case, $\lambda_{\lambda_i-1}<i-2$, meaning
$\lambda'_{i-2}<\lambda_i-1$. We have $\lambda_i\le i$ and
$\lambda'_{i-2}\le\lambda_i-2\le i-2$, so
$\lambda_i=\max\{j\in[p]:j+\beta_j\ge i\}$ and
$\lambda'_{i-2}=\max\{j\in[p]:j+\alpha_j \ge i-2\}$. Let
$k=\lambda_i-1$. Then $k<p$, since $\lambda_i\le i$ implies
$\lambda_i\le p$; we have $$k+\alpha_k<i-2<i\le k+1+\beta_{k+1},$$ so
$\alpha_k<\beta_{k+1}$ and $\lambda\notin P_{-\!1,0}(n)$. We have
shown that if $\lambda\in P_{-\!1,0}(n)$, then $\lambda_i-\mu_i\le 1$
for all $i\in [n]$, as required.

Let $\tau$ be the order ideal of $\nctwo$ corresponding to
$\mu(\lambda)$ and let $\omega_0=\{i:\lambda_i-\mu_i=1\}$. We shall
show that $|Y(\tau,\omega_0)|=y(\lambda)$. For any
$(i,j)\in\nctwo$, we have $(i,j)\in\tau$ if and only if
$(i,j-1)\in D(\mu)$ if and only if $\lambda_i+\lambda_j\ge i+j-1$. If
$(i,j)\in I(\tau)$, then $\#(i,\tau)=j-1$ and $\#(j,\tau)=i$, so
$\mu_i+\mu_j=i+j-1$; if in addition $i,j\notin\omega_0$, then
$\lambda_i+\lambda_j=i+j-1$. Conversely, suppose $i<j$ and
$\lambda_i+\lambda_j=i+j-1$. Then $(i,j-1)\in D(\mu)$ and
$(i,j)\in\tau$, implying that $\#(i,\tau)\ge j-1$ and $\#(j,\tau)\ge
i$, so we must have $i,j\notin\omega_0$. Furthermore,
$\lambda_{i+1}+\lambda_j$ and $\lambda_i+\lambda_{j+1}$ are both at
most $i+j-1$, so $(i,j+1)$ and $(i+1,j)$ are not in $\tau$; we
conclude that $(i,j)\in I(\tau)$. We have shown
$$Y(\tau,\omega_0)=\{(i,j): i<j,\,\lambda_i+\lambda_j=i+j-1\},$$ and
$y(\lambda)$ is defined to be the cardinality of this set.

With this, we have completed the proof of Lemma 7.2(bd) and of
\thetag{BD}.

\head Proof of Lemma \rom{7.2(bc)}\endhead

This proof is much like the preceding one. We must identify, for each
$\lambda\in P_{0,1}(n)$, those $\xi\in P_0(n)$ for which $\lambda-\xi$
is a vertical strip. Given such a $\lambda$, suppose $\xi,\xi^*\in
P_0(n)$ are such that $\lambda-\xi$ and $\lambda-\xi^*$ are vertical
strips and $\xi^*\subseteq\xi\subseteq\lambda$. Let $\taubar$ and
$\taubar^*$ be the order ideals of $\nrctwo$ corresponding to
$\xi$ and $\xi^*$ in the sense of Lemma 5.1(b). Let
$\omega_\pm=\{i\in[n]:\lambda_i-\xi_i=1\}$ and
$\omega^*_\pm=\{i\in[n]:\lambda_i-\xi^*_i=1\}$. We find that
$\taubar\setminus\taubar^*$ is a subset of ${\overline
Z}(\taubar,\omega_\pm)=\{(i,j)\in I(\taubar): i,j\notin\omega_\pm\}$.

Observe that it is possible to have $(i,i)\in I(\taubar)$ for some
$i$. If $\tau=\taubar\cap\nctwo$ and
$\tau^*=\taubar^*\cap\nctwo$, then we have
$$\wtilde(\gee^*)=(-t^2)^{|\tau\setminus\tau^*|}(-t)^{\chi((i,i)\in
\taubar\setminus\taubar^*)}\wtilde(\gee),\tag\dag$$ whenever
$\gee,\gee^*\in\Cee_n^*$ are such that $\gee^+=(\gee^*)^+$,
$\taubar=\taubar(\gee)$, $\taubar^*=\taubar(\gee^*)$,
$\omega_\pm=\omega_\pm(\gee)$, and $\omega^*_\pm=\omega_\pm(\gee^*)$.
Now if $(i,i)\in I(\taubar)$, then $\#_0(i,\taubar)=i$; if in
addition $i\notin\omega_\pm$, then $\lambda_i=i$. Conversely, if
$\lambda_i=i$ and $\xi\in P_0(n)$ is such that $\lambda-\xi$ is a
vertical strip, and if $\taubar$ is the order ideal of $\nrctwo$
corresponding to $\xi$, then either $\xi_i=i$ and $(i,i)\in
I(\taubar)$, or $\xi_i=i-1$ and $(i,i)\in O(\taubar)$. This means that
the case $(i,i)\in I(\taubar)$, $i\notin\omega_\pm$ can occur if and
only if $\lambda_i=i$ for some $i\in[n]$, and otherwise the exponent
of $t$ on the right side of \thetag{\dag} must be even.

Let $Z(\taubar,\omega_\pm)={\overline Z}(\taubar,\omega_\pm)\cap\nctwo$.
Fix $\sigma\in S_n$ and $\lambda\in P_{0,1}(n)$; let $\xi$ be the largest
partition in $P_0(n)$ such that $\lambda-\xi$ is a vertical strip.
Let $\taubar$ denote the order ideal of $\nrctwo$ corresponding to
$\xi$ and $\omega_\pm$ the set $\{i:\lambda_i-\xi_i=1\}$. The sum of
$\wtilde(\gee)$, as $\gee$ ranges over all digraphs in $\Cee_n^*$ such
that $o(\sigma(i),\gee^+)=n-i$ and $o(\sigma(i),\gee)=\lambda_i+n-i$, is
$$(-1)^\sigma x^{\sigma(\lambda+\delta_n)}(-1)^{|\taubar|}t^{|\omega_\pm|}
(1-t)^{\chi(\exists i,\lambda_i=i)}(1-t^2)^{|Z(\taubar,\omega_\pm)|}.$$
Evidently $|\taubar|=(|\xi|+p(\xi))/2$ and $|\omega_\pm|=|\lambda|-|\xi|$,
so we need only show that $\xi=\nu(\lambda)$ and $|Z(\taubar,\omega_\pm)|
=z(\lambda)$ to finish the proof of Lemma 7.2(bc).

By Lemma 2.1(b), $\nu(\lambda)$ is the largest partition in $P_0(n)$ with
Ferrers diagram contained in $D(\lambda)$. So we need only show that
$\lambda-\nu$ is a vertical strip. Write $\lambda=(\alpha_1$,
$\ldots\,$, $\alpha_p\,|\,\beta_1$, $\ldots\,$, $\beta_p)$ and suppose
$\lambda_i-\nu_i>1$. We have $(i,\lambda_i-1)\notin D(\nu)$,
which means that $\lambda_i+\lambda_{\lambda_i-1}<i+\lambda_i-1$.
Subtracting $\lambda_i$ from both sides, we have
$\lambda_{\lambda_i-1} <i-1$; equivalently,
$\lambda'_{i-1}<\lambda_i-1$. If $i\le p$, then
$\lambda'_{i-1}=\beta_{i-1}+i-1$ and $\lambda_i=\alpha_i+i$. Therefore
$\alpha_i>\beta_{i-1}$, and we conclude that
$\alpha_{i-1}\ge\alpha_i+1>\beta_{i-1}+1$, which contradicts the
assumption that $\lambda\in P_{0,1}(n)$. Suppose instead that $i>p$.
Then $\lambda_i\le p$, so $\lambda_{\lambda_i-1}=\alpha_{\lambda_i-1}
+\lambda_i-1$. Meanwhile, $\lambda'_{\lambda_i}\ge i$ for any
$\lambda$, and since $i>p\ge\lambda_i$, we can write
$\lambda'_{\lambda_i}=\beta_{\lambda_i}+\lambda_i$. We see that
$$\beta_{\lambda_i}+1\ge i-\lambda_i+1>i-\lambda_i>
\lambda_{\lambda_{i-1}}-\lambda_i+1=\alpha_{\lambda_i-1},$$
which again implies $\lambda\notin P_{0,1}(n)$. We have proved that
$\lambda_i-\nu_i\le1$ for all $i\in[n]$ whenever $\lambda\in P_{0,1}(n)$.

Observe that $\taubar$, the order ideal of $\nrctwo$
corresponding to $\nu$, is $\{(i,j)\in D(\nu):i\le j\}$. If $(i,j)\in
Z(\taubar,\omega_\pm)$, then $i<j$ and we have
$\nu_i=\#_0(i,\taubar)=j$ and $\nu_j=\#_0(j,\taubar)=i$. And since
$i,j\notin\omega_\pm$, we have $\lambda_i=\nu_i$ and
$\lambda_j=\nu_j$; therefore $\lambda_i+\lambda_j=i+j$. Meanwhile, if
$i<j$ and $\lambda_i+\lambda_j=i+j$, then $(i,j)\in\taubar$. This
implies that $\nu_i\ge j$ and $\nu_j\ge i$, so we must have $\nu_i=j$
(which implies $(i,j+1)\notin\taubar$); $\nu_j=i$ (meaning
$(i+1,j)\notin \taubar$); and $i,j\notin\omega_\pm$. We conclude
$(i,j)\in Z(\taubar, \omega_\pm)$, and we have shown that
$|Z(\taubar,\omega_\pm)|=z(\lambda)$.

\head Proof of Lemma \rom{7.2(cd)}\endhead

This proof differs somewhat from the previous two. Lemma 2.3 tells us
that for any $\lambda\in P_{-\!1,1}(n)$, there is a unique largest
partition $\kappa=\kappa(\lambda)$ among those partitions $\eta\in
P_{-\!1}(n)$ for which $\lambda-\eta$ is a disjoint
union of dominos with no more than one domino per row of $D(\lambda)$.
Now given $\lambda\in P_{-\!1,1}(n)$, let $\tau$ be the order ideal of
$\nctwo$ corresponding to $\kappa(\lambda)$. Let
$\omega_0=\{i\in[n]:\lambda_i-\kappa_i=2\}$ and $\omega_\pm=
\{i\in[n]:\lambda_i-\kappa_i=1\text{ or }2\}$. Observe that
$q(\lambda)=|\omega_0|$. For each $\sigma\in S_n$, there exists
$\gee\in\Cee_n^{**}$ such that: $o(\sigma(i),\gee^+)=n-i$ and
$o(\sigma(i),\gee)=\lambda_i+n-i$ for each $i\in[n]$;
$\tau=\tau(\gee)$; $\omega_0=\omega_0(\gee)$; and
$\omega_\pm=\omega_\pm(\gee)$. For example, if $\lambda=(3,3,2)$, then
$\kappa=(2,2,2)$, $\tau=\{(1,2),(1,3), (2,3)\}$, $\omega_0$ is empty,
and $\omega_\pm=\{1,2\}$. Figure 7.3 shows $\gee\in\Cee_3$
corresponding to this $\lambda$ and to the identity permutation.

\medpagebreak
\centerline{\psfig{figure=fig7.3.eps}}
\centerline{\smc Figure 7.3}
\medpagebreak

When $\gee$ is defined as in the preceding paragraph, we have
$$\wcheck(\gee)=(-1)^\sigma
x^{\sigma(\lambda+\delta_n)}(-1)^{|\kappa|/2+q(\lambda)}
t^{(|\lambda|-|\kappa|)/2}.$$
Fix $\lambda\in P_{-\!1,1}(n)$ and $\sigma\in S_n$ and let $\gee\in\Cee_n^{**}$
be as in the preceding paragraph. If $\gee^*$ is any digraph in
$\Cee_n^{**}$ with $(\gee^*)^+=\gee^+$ and $o(\sigma(i),\gee^*)=o(\sigma(i),\gee)$
for each $i\in[n]$, then $\tau(\gee^*)\subseteq\tau$, $\omega_0(\gee^*)\supseteq
\omega_0$, and $\omega_\pm(\gee^*)\supseteq\omega_\pm$.
Let $Z(\lambda)=\{(i,j):i<j,\,\lambda_i+
\lambda_j=i+j\}$, so that $|Z(\lambda)|=z(\lambda)$.
Now it suffices to prove the following:

\medpagebreak
(i) For every subset $A$ of $Z(\lambda)$, there is a digraph
$\gee_A\in\Cee_n^{**}$ such that: $\gee_A^+=\gee^+$;
$o(\sigma(i),\gee_A)=o(\sigma(i),\gee)$ for each $i\in[n]$; and
$\wcheck(\gee_A)=(-t^2)^{|A|}\wcheck(\gee)$.

(ii) If $\lambda_i=i$ for some $i\in[n]$, then for each $\gee_A$
there is a $\gee'_A\in\Cee_n^{**}$ with the same positive subtournament
and out-degrees as $\gee_A$ and with $\wcheck(\gee'_A)=-t\wcheck(\gee_A)$.

(iii) Every $\gee^*\in\Cee_n^{**}$ having the same positive subtournament
and out-degrees as $\gee$ is of the form $\gee_A$ or $\gee'_A$ for some
$A\subseteq Z(\lambda)$.
\medpagebreak

To prove (i), suppose first of all that $A=\{(i,j)\}$. Since
$0\le\lambda_k-\kappa_k\le 2$ for all $k\in[n]$, we must have
$i+j-4\le\kappa_i+\kappa_j\le i+j$. Observe that $\kappa_i+\kappa_j$ is
at most $i+j-3$ if $(i,j)\notin\tau$ and at least $i+j-1$ if $(i,j)\in
\tau$, so we can rule out $\kappa_i+\kappa_j=i+j-2$. The remaining
possibilities are as follows:

\medpagebreak
$\kappa_i+\kappa_j=i+j$. We have $(i,j)\in\tau$, and there is exactly
one $k$ such that either $k>j$ and $(i,k)\in\tau$ or $k>i$ and $(k,j)
\in\tau$. Either $k=i+1$ and $(i+1,j)\in I(\tau)$, or $k=j+1$ and
$(i,j+1)\in I(\tau)$. We have $i\notin\omega_0$, $i\notin\omega_\pm$,
$j\notin\omega_0$, and $j\notin\omega_\pm$. Suppose $(i+1,j)\in
I(\tau)$. We find that $i$ and $i+1$ are interchangeable in $\tau$, so
$\kappa_{i+1}=\kappa_i=\lambda_i\ge\lambda_{i+1}$; this means that
$i+1$ cannot be in $\omega_0$ or $\omega_\pm$. We define $\gee_A$ by
putting $\tau(\gee_A)=\tau\setminus\{(i,j),(i+1,j)\}$;
$\omega_0(\gee_A) =\omega_0\cup\{j\}$; and
$\omega_\pm(\gee_A)=\omega_\pm\cup\{i,i+1,j\}$. A similar argument
applies if $(i,j+1)\in I(\tau)$: we have $\tau(\gee_A)=\tau\setminus
\{(i,j),(i,j+1)\}$, $\omega_0(\gee_A)=\omega_0\cup\{i\}$, and
$\omega_\pm(\gee_A)=\omega_\pm\cup\{i,j,j+1\}$. Figure 7.4 gives an
example of this construction in the situation $\lambda=(6,3,2,2,1)$,
with $A=\{(2,3)\}$. On the left are $\tau$, $\omega_0$, and
$\omega_\pm$ for $\gee$, and on the right, the corresponding sets for
$\gee_A$. As in Figure 6.4, each square $(k,k)$ is vertically lined
if $k\in\omega_0$ and horizontally lined if $k\in\omega_\pm$.

\medpagebreak
\centerline{\psfig{figure=fig7.4.eps}}
\centerline{\smc Figure 7.4}
\medpagebreak

$\kappa_i+\kappa_j=i+j-1$. We have $(i,j)\in I(\tau)$; neither $i$ nor
$j$ is in $\omega_0$ and exactly one of them is in $\omega_\pm$. If
$j<n$, then $j$ and $j+1$ are not interchangeable in $\tau$; if
$j>i+1$, then $i$ and $i+1$ are not interchangeable in $\tau$.
Suppose $j\in\omega_\pm$. Then $j$ and $j-1$ must be interchangeable
in $\tau$, $j-1\in\omega_\pm$, and $j-1\notin\omega_0$: otherwise,
$\lambda-\kappa$ would not be a disjoint union of
dominos with at most one domino per row. If $j-1=i$, then we would
have $\lambda_i+\lambda_j=i+j+1$, so we must have
$j>i+1$. Alternatively, suppose $i\in\omega_\pm$. Then $i-1$ or $i+1$
must be in $\omega_\pm$ and not in $\omega_0$; $i$ and $i+1$ are not
interchangeable in $\tau$ unless $i+1=j$, but $j\notin\omega_\pm$; we
conclude that $i$ and $i-1$ are interchangeable in $\tau$,
$i-1\in\omega_\pm$, and $i-1\notin\omega_0$. If $j\in\omega_\pm$, then
let $\tau(\gee_A)=\tau\setminus\{(i,j-1),(i,j)\}$;
$\omega_0(\gee_A)=\omega_0\cup\{i,j-1,j\}$; and $\omega_\pm(\gee_A)
=\omega_\pm\cup\{i\}$. If $i\in\omega_\pm$, then $\tau(\gee_A)$ is
$\tau\setminus\{(i-1,j),(i,j)\}$, $\omega_0(\gee_A)=\omega_0\cup\{i-1,
i,j\}$, and $\omega_\pm(\gee_A)=\omega_\pm\cup\{j\}$. In Figure 7.5,
we have an example of this construction for $\lambda=(4,3,3,2,2)$ and
$A= \{(1,5)\}$.

\medpagebreak
\centerline{\psfig{figure=fig7.5.eps}}
\centerline{\smc Figure 7.5}
\medpagebreak

$\kappa_i+\kappa_j=i+j-3$. We have $(i,j)\in O(\tau)$ and one of $i$
and $j$ is in both $\omega_0$ and $\omega_\pm$, while the other is in
$\omega_\pm$ only. If $j\notin\omega_0$, then we must have $j$ and
$j+1$ interchangeable in $\tau$, $j+1\in\omega_\pm$, and $j+1\notin
\omega_0$. This is because $j$ has to be ``paired off'' with either
$j-1$ or $j+1$ according to the definition of $\Cee_n^{**}$, and
assuming it is paired off with $j-1$ leads to a contradiction. But in
this case, we can replace $\tau$ with $\tau\cup\{(i,j),(i,j+1)\}$,
remove $i$, $j$, and $j+1$ from $\omega_\pm$, and remove $i$ from
$\omega_0$; this contradicts our assumption that $\tau$ corresponds to
$\kappa$. We also derive this contradiction if $i\notin\omega_0$.
We find that if $i>1$, then $i$ and $i-1$ are not interchangeable in
$\tau$, $i$ is paired off with $i+1$, and $j>i+1$; we can replace
$\tau$ with $\tau\cup\{(i,j),(i+1,j)\}$.
\medpagebreak

$\kappa_i+\kappa_j=i+j-4$. Here too we have a contradiction of the
assumption that $\tau$ corresponds to $\kappa$. We can add either
$\{(i,j-1),(i,j)\}$ or $\{(i-1,j),(i,j)\}$ to $\tau$ and change
$\omega_0$ and $\omega_\pm$ accordingly. For instance, one possibility
is $(i,j-1)\in O(\tau)$, with $j-1$ and $j$ interchangeable in
$\tau$. We have both $i$ and $j$ in $\omega_0$ and $\omega_\pm$; $j-1$
is also in $\omega_0$ and $\omega_\pm$, as otherwise we would have
$\lambda_{j-1}<\lambda_j$. We can add $\{(i,j-1),(i,j)\}$ to $\tau$.
\medpagebreak

We have proved (i) whenever $|A|=1$. In this case, we obtain
$\tau(\gee_A)$ by removing from $\tau$ a set of the form
$\{(i,j),(i+1,j)\}$ or $\{(i,j),(i,j+1)\}$. Such a set is a domino. In
case $|A|>1$, we can find a domino to remove from $\tau$ for each
$(i,j)\in A$. If no two of these dominos intersect, then we can
construct $\gee_A$ ``one domino at a time'' by repeating the above
construction for one-element sets $A$. (This is essentially what we
did in proving the first two parts of Lemma 7.2, only with monominos
instead of dominos.) On the other hand, it is possible for two dominos
to intersect. For instance, this happens if $\lambda=(3,3,2,2)$ and
$A=\{(1,4),(2,3)\}$: the dominos corresponding to $(1,4)$ and $(2,3)$
are respectively $\{(1,4),(2,4)\}$ and $\{(2,3),(2,4)\}$.

We claim, however, that given any three dominos that correspond to
elements of $Z(\lambda)$, one of them is disjoint from the other
two. This is because $i\ne k$ and $j\ne l$ whenever $(i,j)$ and
$(k,l)$ are distinct elements of $Z(\lambda)$. The only way two
dominos can intersect is if they are of the form $\{(i,j-1),(i,j)\}$
and $\{(i-1,j),(i,j)\}$, with $(i,j-1),(i-1,j)\in Z(\lambda)$. It is
not hard to see that no third domino corresponding to an element of
$Z(\lambda)$ can intersect either of these. So to complete the proof
of (i), we need only show that if $A=\{(i,j-1),(i-1,j)\}$, with
corresponding dominos $\{(i,j-1),(i,j)\}$ and $\{(i-1,j),(i,j)\}$,
then we can create $\gee_A\in\Cee_n^{**}$ having the same positive
subtournament and out-degrees as $\gee$ and with
$\wcheck(\gee_A)=t^4\wcheck(\gee)$. For such an $A$, we have: none of
$i-1$, $i$, $j-1$, $j$ is in $\omega_0$ or $\omega_\pm$; $i-1$ and $i$
are interchangeable in $\tau$; $j-1$ and $j$ are interchangeable in
$\tau$; and $(i,j)\in I(\tau)$. We define
$$\align\tau(\gee_A)&=\tau\setminus\{(i-1,j-1),
(i-1,j),(i,j-1),(i,j)\};\\
\omega_0(\gee_A)&=\omega_0\cup\{i-1,i,j-1,j\};\\
\omega_\pm(\gee_A)&=\omega_\pm\cup\{i-1,i,j-1,j\}.\endalign$$
We think of $\tau(\gee_A)$ as being obtained from $\tau$ by removing
two dominos. This completes the proof of claim (i).
\medpagebreak

We now begin the proof of (ii). Let $\gee_A\in\Cee_n^{**}$ be the
digraph corresponding to some $A\subseteq Z(\lambda)$, where $\lambda$
is such that $\lambda_i=i$ for some $i\in[n]$. Recall that $\tau$
denotes the order ideal of $\nctwo$ corresponding to
$\kappa=\kappa(\lambda)$ and that
$\omega_0=\{i\in[n]:\lambda_i-\kappa_i=2\}$ and $\omega_\pm=
\{i\in[n]:\lambda_i-\kappa_i=1\text{ or }2\}$. Let
$\tau_A=\tau(\gee_A)$. We claim that either $(i,i+1)\in I(\tau_A)$ or
$(i-1,i)\in I(\tau_A)$. There are three possible values for
$\kappa_i$: $i$, $i-1$, and $i-2$. If $\kappa_i=i$, then $(i,i+1)\in
I(\tau)$. If $\kappa_i=i-1$, then $(i-1,i)\in\tau$ and
$(i,i+1)\notin\tau$. We have $i\in\omega_\pm$ and
$i\notin\omega_0$. Assuming that $(i-1,i+1)\in\tau$, we conclude that
$i-1$ and $i$ are not interchangeable in $\tau$, so $i$ and $i+1$ must
be, and we must have $i+1\in\omega_\pm$ and $i+1\notin\omega_0$. But
this contradicts the maximality of $\tau$, since we can add $(i,i+1)$
to it and remove $i$ and $i+1$ from $\omega_\pm$. So we must have
$(i-1,i+1)\notin\tau$, and therefore $(i-1,i)\in I(\tau)$. Similarly,
if $\kappa_i=i-2$, we find that we can add $(i-1,i)$ to $\tau$ and
remove $i-1$ and $i$ from $\omega_0$. We have proved the claim for
$\tau_A=\tau$ (this is the case $A=\emptyset$). If $A$ is not empty,
then we obtain $\tau_A$ by removing dominos from $\tau$. If $(i,i+1)$
is in $\tau_A$, then it is in $I(\tau_A)$. If $(i,i+1)$ is in
$I(\tau)$ but not $\tau_A$, then it must be contained in a domino
removed from $\tau$; the other member of this domino must be
$(i-1,i+1)$. Having removed this domino, we have $(i-1,i)\in
I(\tau_A)$, unless $(i-1,i)$ is also in a domino removed from
$\tau$, which it cannot be, since the other member of the domino
would be $(i-2,i)$; removing both dominos would reduce $\#(i,\tau)$ by
$3$, and we could not have $o(\sigma(i),\gee_A)=o(\sigma(i),\gee)$. A
similar argument proves that if $(i-1,i)\in I(\tau)$, then we must
have $(i-1,i)\in I(\tau_A)$. We have proved that $(i,i+1)$ or $(i-1,i)$
is in $I(\tau_A)$ for any $A\subseteq Z(\lambda)$.

Now we know that either $(i,i+1)\in I(\tau_A)$,
$i\notin\omega_0(\gee_A)$, and $i\notin\omega_\pm(\gee_A)$; or
$(i-1,i)\in I(\tau_A)$, $i\in\omega_\pm (\gee_A)$, and
$i\notin\omega_0(\gee_A)$. In the former case, we see that $i$ and
$i+1$ are interchangeable in $\tau$ and that $i+1$ is not in
$\omega_0(\gee_A)$ or $\omega_\pm(\gee_A)$: otherwise we would have
$o(\sigma(i),\gee_A)\le o(\sigma(i+1),\gee_A)$. So we create $\gee'_A$
by putting $\tau(\gee'_A)=\tau(\gee_A)\setminus\{(i,i+1)\}$;
$\omega_0(\gee'_A)=\omega_0(\gee_A)$; and
$\omega_\pm(\gee'_A)=\omega_\pm (\gee_A)\cup\{i,i+1\}$. In the latter
case, we must have $i-1\in\omega_\pm(\gee_A)$ and
$i-1\notin\omega_0(\gee_A)$, since $i$ and $i+1$ are not
interchangeable in $\tau(\gee_A)$. We construct $\gee'_A$ by putting
$\tau(\gee'_A)=\tau(\gee_A) \setminus\{(i-1,i)\}$;
$\omega_0(\gee'_A)=\omega_0(\gee_A)\cup\{i-1,i\}$; and
$\omega_\pm(\gee'_A)=\omega_\pm(\gee_A)$. This completes the proof
of~(ii).
\medpagebreak

We shall prove (iii) by constructing a subset $A$ of $Z(\lambda)$ for
each $\gee^*\in\Cee_n$ having the same positive subtournament and
out-degrees as $\gee$. Recall the definitions of $\tau$, $\omega_0$,
and $\omega_\pm$ relative to $\sigma\in S_n$ and $\lambda\in
P_{-\!1,1}(n)$; in particular, $\tau$ is the order ideal of
$\nctwo$ corresponding to $\kappa(\lambda)$. Let
$\tau^*=\tau(\gee^*)$, $\omega^*_0=\omega_0(\gee^*)$, and
$\omega^*_\pm=\omega_\pm(\gee^*)$. Observe that if $\tau^*\ne\tau$,
then there exists $(i,j)\in I(\tau)\setminus\tau^*$. This is because
$\tau$ and $\tau^*$ are order ideals and we obtain $\tau^*$ from
$\tau$ by removing some elements. Now to construct $A$, we begin by
setting $A=\emptyset$ and do the following for each $(i,j)\in
I(\tau)\setminus\tau^*$:

When $j=i+1$, we distinguish between two cases: $(i-1,i+1)\in\tau^*$
and $(i-1,i+1)\in\tau\setminus\tau^*$. In the first case, we find that
$\#(i,\tau)=\#(i+1,\tau)=i$ and that $\#(i,\tau^*)=\#(i+1,\tau^*)
=i-1$. We have either $i,i+1\in\omega_\pm\setminus\omega_0$, meaning
$\lambda_{i+1}=i+1$, or $i,i+1\notin\omega_\pm$, meaning
$\lambda_i=i$. We do not add anything to $A$, but we see that
$\gee^*$ is of the form $\gee'_A$ rather than $\gee_A$. In the second
case, $\#(i+1,\tau)=i$ and $\#(i+1,\tau^*)=i-2$; we must have
$i+1\notin\omega_\pm$ and $i+1\in\omega^*_0$. So $\lambda_{i+1}=i$ in
this case. Meanwhile, $\#(i-1,\tau^*)=\#(i-1,\tau)-1$ and
$\#(i,\tau^*)=\#(i,\tau)-1$; this means $i-1$ and $i$ are ``paired''
as members of $\omega_\pm\setminus\omega_0$ or of
$\omega^*_\pm\setminus\omega^*_0$, so they must be interchangeable in
$\tau$. Since $\#(i,\tau)=i$, we must have $\#(i-1,\tau)=i$. If
$i-1$ and $i$ are in $\omega_\pm\setminus\omega_0$, then $\lambda_i=i+1$;
we add $(i,i+1)$ to $A$. Otherwise, $i-1$ and $i$ are not in $\omega_\pm$
and $\lambda_{i-1}=i$; we add $(i-1,i+1)$ to $A$. In the latter situation,
we may also have $\gee^*$ of the form $\gee'_A$. This happens if $(i-1,i)
\in\tau\setminus\tau^*$, in which case $\#(i,\tau^*)=\#(i,\tau)-2$, so
$i$ cannot be in $\omega_\pm$.

If $j>i+1$, then it is impossible to remove $(i,j)$ from $\tau$ and
not remove either $(i-1,j)$ or $(i,j-1)$. The removal of only $(i,j)$
would force a violation of the pairing condition for members of
$\omega_\pm\setminus\omega_0$.