% A LaTeX file for a 17-page document.

% Submitted to Electronic J. Combin. (Stanley Festschrift) Tue 15 Feb 2005
% Accepted Thu 12 May 2005

\documentclass[12pt]{article}

\usepackage{amssymb,amsmath,amsthm,graphicx,color}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setlength{\textwidth}{6.3in}
\setlength{\textheight}{8.7in}
\setlength{\topmargin}{0pt}
\setlength{\headsep}{0pt}
\setlength{\headheight}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}

\makeatletter
\newfont{\footsc}{cmcsc10 at 8truept}
\newfont{\footbf}{cmbx10 at 8truept}
\newfont{\footrm}{cmr10 at 10truept}
\renewcommand{\ps@plain}{%
\renewcommand{\@oddfoot}{\footsc the electronic journal of combinatorics
  {\footbf 11(2)} (2005), \#A3\hfil\footrm\thepage}}
\makeatother
\pagestyle{plain}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{defn}{Definition}

\title{Chess Tableaux}

\author{Timothy Y. Chow\\
\small 250 Whitwell Street \#2\\
\small Quincy, MA 02169, U.S.A.\\
\small \texttt{tchow [at] alum[.]mit[.]edu}\\
\and Henrik Eriksson\\
\small Nada, KTH\\
\small 100 44 Stockholm, Sweden\\
\small \texttt{henrik [at] nada[.]kth[.]se}\\
\and C. Kenneth Fan\\
\small 27 Jefferson Street \#6\\
\small Cambridge, MA 02141, U.S.A.\\
\small \texttt{ckfan [at] msn[.]com}}

\date{\small
Submitted: Feb 15, 2005; Accepted: May 12, 2005; Published: Jun 14, 2005\\
\small Mathematics Subject Classifications: 05A15, 05E10\\
\ \\
\small \em Dedicated to Richard Stanley on the occasion of his 60th birthday}

\begin{document}

\maketitle

\begin{abstract}
A {\em chess tableau\/} is a standard Young tableau
in which, for all $i$ and~$j$,
the parity of the entry in cell $(i,j)$ equals the parity of $i+j+1$.
Chess tableaux were first defined by Jonas Sj\"ostrand
in his study of the sign-imbalance of certain posets,
and were independently rediscovered by the authors
less than a year later
in the completely different context of
composing chess problems with interesting enumerative properties.
We prove that the number of $3\times n$ chess tableaux
equals the number of Baxter permutations of $n-1$,
as a corollary of a more general correspondence between
certain three-rowed chess tableaux and certain
three-rowed Dulucq-Guibert nonconsecutive tableaux.
The correspondence itself is proved by means of
an explicit bijection.
We also outline how lattice paths, or rat races,
can be used to obtain generating functions for chess tableaux.
We conclude by explaining the connection to chess problems,
and raising some unanswered questions, e.g.,
there are striking numerical coincidences between chess tableaux
and the Charney-Davis statistic; is there a combinatorial explanation?
\end{abstract}

% \begin{keyword}
% Baxter permutation, Charney-Davis statistic, rat race

\section{Introduction}
\label{Intro}

\def\chess{\mbox{\rm Chess}}
\def\syt{\mbox{\rm SYT}}
\def\ncon{\mbox{\rm NCon}}
\def\cd{\mbox{\rm CD}}
A {\em chess tableau\/} is a standard Young tableau
in which, for all $i$ and~$j$,
the parity of the entry in cell $(i,j)$ equals the parity of $i+j+1$.
If $i+j+1$ is even (respectively, odd), then cell $(i,j)$
is called an {\em even cell\/} (respectively, an {\em odd cell\/}),
and in a chess tableau it necessarily contains
an even (respectively, odd) entry.
See Figure~\ref{fig:chesstableau},
in which the odd cells are shaded as a visualization aid.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.4]{ct1.eps}
\caption{Example of a chess tableau}
\label{fig:chesstableau}
\end{center}
\end{figure}

We write $\chess(\lambda)$ for the number of chess tableaux
of shape~$\lambda$.
If the parts of~$\lambda$ are (for example) $a$, $b$, and~$c$,
then we often write $a,b,c$ instead of~$\lambda$;
for example, we sometimes write $\chess(a,b,c)$ for $\chess(\lambda)$.
We also adopt the convention that $\chess(\lambda)=0$
if $\lambda$ is not a partition
(i.e., if it contains negative integers or
does not decrease monotonically).

Chess tableaux were first defined by Jonas Sj\"ostrand~\cite{Sj03}
in his study of the sign-imbalance of certain posets.
In a remarkable coincidence, chess tableaux
were independently rediscovered shortly thereafter
by the present authors in the completely different context of
composing chess problems with interesting enumerative properties.
The connection with chess problems is explained
in Section~\ref{queue} below;
here it suffices to remark that our investigations led us
to search for a nice formula for $\chess(\lambda)$---if
not for all~$\lambda$, then at least for some~$\lambda$.
Sj\"ostrand considered the {\em signed\/} enumeration of chess tableaux,
but we are the first to consider their {\em direct\/} enumeration.

As we shall see shortly,
$\chess(\lambda)$ is easy to compute if
$\lambda$ has only one or two parts.
In Section~\ref{noncon},
we consider the much subtler case
when $\lambda$ has three parts,
showing that there is a surprising and mysterious relationship
between chess tableaux and so-called ``nonconsecutive tableaux.''
In particular, we compute $\chess(\lambda)$ exactly when
$\lambda$ is a $3\times n$ rectangle.
In Section~\ref{ratrace}, we
show how to derive a rational generating function
for $\chess(\lambda)$
when $\lambda$ has a bounded number of parts.
Finally, in Section~\ref{charney}, we describe some
further miscellaneous results and open problems.
Specifically, a formula for $\chess(\lambda)$ for arbitrary $\lambda$
remains an open question.

We now present a few basic facts about chess tableaux.
If $\lambda$ has only one row,
then the unique standard Young tableau of shape $\lambda$
is also a chess tableau; hence $\chess(\lambda)=1$.
If $\lambda$ has two rows, then it turns out that
computing $\chess(\lambda)$ reduces to
counting standard Young tableaux with two rows.
More precisely,
if we let $\syt(\lambda)$ denote the number of
standard Young tableaux of shape~$\lambda$,
then we have the following proposition.

\begin{prop}
\label{prop:tworows}
Let $a\ge b > 0$.
If $a$ is even and $b$ is odd, then $\chess(a,b)=0$.
Else,
$\chess(a,b) = \syt(\lfloor(a-1)/2\rfloor, \lfloor b/2\rfloor)$.
In particular,
$\chess(2k+1,2k+1)$ equals the $k$th Catalan number
and $\chess(2k,2k) = 0$.
% \begin{equation}
%  \chess(a,b) = \left\{
%   \begin{array}{ll}
%    0, & \quad \mbox{if $a=b$ and $a$ is even;} \\
%    \syt(\lfloor(a-1)/2\rfloor, \lfloor b/2\rfloor), & \quad \mbox{otherwise.}
%   \end{array}
%  \right.
% \end{equation}
\end{prop}

\begin{proof}
If $a$ is even and $b$ is odd, then
there are more even cells than odd cells,
so a chess tableau of shape $a,b$ cannot exist.
Otherwise, if one constructs a chess tableau of shape $a,b$
by writing down the entries in consecutive order,
then one quickly sees that for $i\ge1$,
the entry $2i+1$ (if it exists at all, i.e., if $2i+1\le a+b$)
is forced to appear immediately to the right of the entry~$2i$.
Therefore, in row~1, we may ``glue together''
the 2nd and 3rd cells, the 4th and 5th cells, and so on,
leaving the last cell in the row unglued if $a$ is even.
Similarly, in row~2, we may glue together
the 1st and 2nd cells, the 3rd and 4th cells, etc.,
leaving the last cell in the row unglued if $b$ is odd.
When constructing a chess tableau,
we enter~1, and then for all~$i$
we enter the numbers $2i$ and $2i+1$ together
into a pair of glued-together cells,
and put the largest entry $a+b$
in the remaining unglued cell (if it exists).
\relax From this construction one sees readily that
chess tableaux of shape~$a,b$
are equivalent to standard Young tableaux of shape
$\lfloor(a-1)/2\rfloor, \lfloor b/2\rfloor$.
\end{proof}

The above argument that $\chess(a,b)=0$
if $a$ is even and $b$ is odd
is a special case of an argument of Sj\"ostrand
that applies more generally.
The key observation is that
the set of numbers from $1$ to~$n$
either has an equal number of odd and even numbers
or has an excess of one odd number.
This fact easily yields the following proposition.

\begin{prop}
\label{prop:parity}
If $\lambda$ has three nonempty rows and
all three rows end with a cell of the same parity
(in other words, if the parities of the parts of~$\lambda$
alternate even-odd-even or odd-even-odd),
then $\chess(\lambda)=0$.
\end{prop}

\begin{proof}
If all three rows end in an odd cell,
then each of the first and third rows has one more odd cell
than it has even cells,
while the second row has the same number of even and odd cells,
for an overall excess of two odd cells.
Similarly,
if all three rows end in an even cell,
then each of the first and third rows has
the same number of even and odd cells,
while the second row has one more even cell
than it has odd cells,
for an overall excess of one even cell.
\end{proof}

% If $\lambda$ has three parts $a$, $b$, and~$c$,
% then by splitting into cases according to which of the three rows
% the largest entry of a tableau is in,
% we see that $\syt(a,b,c)$ satisfies the recurrence
% $$\syt(a,b,c) = \syt(a-1,b,c) + \syt(a,b-1,c) + \syt(a,b,c-1).$$
% (Again, we set $\syt(\lambda)=0$ if $\lambda$ is not a partition.)
% In particular, $\syt(\lambda)$ is a sum of
% (at most) three smaller terms.
% 
% Similar reasoning applies if $\syt(a,b,c)$ is replaced by $\chess(a,b,c)$,
% but an important consequence of Proposition~\ref{prop:parity}
% is that $\chess(a,b,c)$ is a sum of at most {\em two\/} of the smaller terms.
% 
% \begin{cor}
% \label{cor:recur}
% Let $a,b,c$ be a partition with at least two cells.
% If $\chess(a,b,c)\ne0$,
% then $\chess(a,b,c)$ is the sum of at most two of the terms
% $\chess(a-1,b,c)$, $\chess(a,b-1,c)$, and $\chess(a,b,c-1)$.
% \end{cor}
% 
% \begin{proof}
% The corollary is obvious if $c=0$.
% Otherwise, if $\chess(a,b,c)\ne0$, then
% Proposition~\ref{prop:parity} implies that
% the parities of the cells at the ends of the three rows
% are not all the same.
% But the largest entry of a chess tableau of shape $a,b,c$
% is $a+b+c$, so it must go at the end of a row
% in a cell with the same parity as that of $a+b+c$,
% and there are at most two such cells.
% This proves the corollary.
% For example,
% $$\chess(8,6,3) = \chess(8,5,3)+\chess(8,6,2),$$
% because the entry~$17$ in a chess tableau of shape $8,6,3$
% must go at the end of row~$2$ or row~$3$,
% the two rows ending in an odd cell.
% \end{proof}

The importance of the next definition
will become clear in the next section.

\begin{defn}
A partition or a tableau is {\em balanced\/} if
it has three parts (not necessarily nonzero)
and the parities of its parts are
even-even-odd or odd-odd-even.
\end{defn}

Note that if $T$ is a chess tableau with three parts
and the lengths of row~2 and row~3 have opposite parity,
then $T$ is balanced, by Proposition~\ref{prop:parity}.

\begin{prop}
\label{prop:bchain}
Let $T$ be a balanced chess tableau of shape $d,e,f$.
Let $T_0 \subset T_1 \subset T_2 \subset \dots \subset T_n = T$
be a maximal chain where each $T_k$ is a balanced chess tableau
and each containment is strict.
Then the chain is unique.
Furthermore, the chess tableau $T_0$
has an odd number of entries in row~1,
a single entry in row~2, and an empty row~3.
For any $1 \le k \le n$,
the number of entries in rows 2 and~3 of~$T_k$
is precisely two more than the number of entries
in rows 2 and~3 of~$T_{k-1}$.
We have $n = (e + f - 1)/2$.
\end{prop}

The chess tableau of Figure~\ref{fig:chesstableau} is balanced,
and Figure~\ref{fig:chesschain} illustrates the chain described in 
Proposition~\ref{prop:bchain} for this tableau.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.4]{pct1.eps}
\caption{Decomposition of a balanced chess tableau into a chain of balanced
subtableaux}
\label{fig:chesschain}
\end{center}
\end{figure}

\begin{proof}[Proof (of Proposition~\ref{prop:bchain})]
Because any subtableau of $T$ must consist of
a consecutive set of entries beginning with~1, the chain is unique.

Note that there are no balanced tableaux with a single row.
Let $y_0$ be the first entry in row~2 of~$T$.
Note that $y_0$ is even because $T$ is a chess tableau.
Therefore, the first $y_0$ entries of~$T$
comprise a balanced chess tableau, which must be~$T_0$.
If $T_0 = T$, the rest of the proposition follows and we are done.
Otherwise, suppose we have constructed $T_j$ for $j<k$ and $T_{k-1} \ne T$.
Let $x_k$ be the first entry in $T$ not in~$T_{k-1}$.
A simple parity argument shows that
because $T_{k-1}$ is balanced,
its largest entry must be in row 2 or~3.
Therefore, the parity of the last cell
in row~1 of~$T_{k-1}$ is the same as the parity of~$x_k$.
This implies that $x_k$ must be in row 2 or~3.
Let $y_k$ be the smallest entry in~$T$
greater than~$x_k$ which is also in row 2 or~3.
Such an entry must exist because if it did not exist,
rows 2 and~3 of~$T$ would have the same parity,
contrary to the fact that $T$ is balanced.

Let $T_k$ consist of all entries in~$T$ less than or equal to~$y_k$.
We claim that $T_k$ is balanced.
Because an even number of entries (in fact, exactly two)
are added to rows 2 and~3 of~$T_{k-1}$ to obtain~$T_k$,
the parity of the sum of the lengths of rows 2 and~3 remains odd.
Hence, the lengths of rows 2 and~3 of~$T_k$ have opposite parity.
% It remains to check that the length of row~1 of~$T_k$
% has the same parity as the length of its row~2.
% If $X_k$ and~$Y_k$ are in the same row,
% then they have opposite parity and
% the number of entries added to row~1 of~$T_{k-1}$ to obtain~$T_k$ is even.
% This implies that the parities of the lengths of row~1 and row~2
% both remain the same when going from $T_{k-1}$ to~$T_k$.
% If $X_k$ and~$Y_k$ are in different rows,
% then they have the same parity
% and the number of entries added to row~1 of~$T_{k-1}$
% to obtain~$T_k$ is odd.
% This implies that the parities of the lengths of row~1 and row~2
% both change when going from $T_{k-1}$ to~$T_k$.

Finally, note that there is no balanced tableau
strictly between $T_{k-1}$ and~$T_k$,
for such a tableau would differ in rows 2 and~3
from~$T_{k-1}$ by only one entry and therefore would not be balanced.

Because each step in the chain
increases the number of entries in rows 2 and~3 (combined)
by two and $T_0$ has exactly one entry in rows 2 and~3, it follows that
$n = (e + f - 1)/2$.
\end{proof}

\section{Nonconsecutive Tableaux and the Main Result}
\label{noncon}

A {\em nonconsecutive tableau\/} is a standard Young tableau
in which, for all~$i$, the entries $i$ and $i+1$ are in different rows.
See Figure~\ref{fig:noncon}.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.4]{nct1.eps}
\caption{Example of a nonconsecutive tableau}
\label{fig:noncon}
\end{center}
\end{figure}

We write $\ncon(\lambda)$ for the number of nonconsecutive tableaux
of shape~$\lambda$.
We write $\ncon_i(\lambda)$ for the number of nonconsecutive tableaux
of shape~$\lambda$ whose largest entry appears in row~$i$
(necessarily at the end of the row).
If $\lambda$ is not a partition, or if $\lambda$ is empty,
then we set $\ncon(\lambda)=\ncon_i(\lambda)=0$.
As far as we know,
nonconsecutive tableaux were first studied by
Dulucq and Guibert~\cite{DG96}.

Our main result is the following striking connection between
nonconsecutive tableaux and chess tableaux.

\begin{thm} \label{thm:main}
For any integers $a$, $b$, and $c$,
\begin{equation}
\label{eq:main}
\ncon_1(a,b,c) = \chess(a+b-c,a-b+c,1-a+b+c)
\end{equation}
\end{thm}

Theorem~\ref{thm:main} indicates an intimate relationship between
nonconsecutive tableaux and chess tableaux,
and one might suppose that there must be an obvious bijective proof.
Our proof is bijective, but not obvious,
and the reader is encouraged to find a simpler bijection.

Before proving Theorem~\ref{thm:main}, we deduce some easy corollaries.

\begin{cor} \label{cor:twochess}
If $a,b,c$ is a nonempty partition, then
$\ncon(a,b,c) = \chess(a+b-c,a-b+c,1-a+b+c) +
\chess(1+a+b-c,1+a-b+c,-a+b+c)$.
\end{cor}

\begin{proof}
If $T$ is a nonconsecutive tableau of shape $a+1,b,c$
whose largest entry is in row~1,
then by nonconsecutivity, the second-largest entry of~$T$
must be in either row~2 or row~3.
So by deleting the largest entry, we see that
$$\ncon_1(a+1,b,c) = \ncon_2(a,b,c) + \ncon_3(a,b,c).$$
On the other hand, it is obvious that
$$\ncon(a,b,c) = \ncon_1(a,b,c) + \ncon_2(a,b,c) + \ncon_3(a,b,c).$$
Therefore  $\ncon(a,b,c)=\ncon_1(a,b,c)
+\ncon_1(a+1,b,c)$.  Now apply Theorem~\ref{thm:main} to complete
the proof.
\end{proof}

\def\baxter{\mbox{Baxter}}
It is proved in \cite{DG96} that
$$\ncon(n,n,n) = \frac{2}{n(n+1)^2} \sum_{k=0}^{n-1} \binom{n+1}{k}
   \binom{n+1}{k+1}\binom{n+1}{k+2}.$$
(More specifically, Dulucq and Guibert prove that $\ncon(n,n,n)$
equals the number of {\em Baxter permutations of~$n$,}
for which the above explicit formula was already known.
The definition of a Baxter permutation is 
somewhat complicated and we do not need it,
so we omit it, but the reader can find it in~\cite{DG96}.)

This fact immediately yields an explicit formula for $\chess(n,n,n)$.

\begin{cor} \label{cor:baxter}
For $n>1$,
\begin{equation}
\label{eq:baxter}
\chess(n,n,n) = \frac{2}{(n-1)n^2} \sum_{k=0}^{n-2}\binom{n}{k}
   \binom{n}{k+1}\binom{n}{k+2}.
\end{equation}
\end{cor}

\begin{proof}
Setting $a=b=c=n-1$ in Corollary~\ref{cor:twochess} yields
$$\ncon(n-1,n-1,n-1) = \chess(n-1,n-1,n) + \chess(n,n,n-1).$$
But $n-1,n-1,n$ is not a partition so $\chess(n-1,n-1,n)=0$.
Moreover, the largest entry of a chess tableau of shape $n,n,n$
must go at the end of row~3, so
$\chess(n,n,n-1)=\chess(n,n,n)$.
Using the known explicit formula for $\ncon(n-1,n-1,n-1)$
yields the corollary.
\end{proof}

It would be nice to have a direct proof of Corollary~\ref{cor:baxter}.

\begin{proof}[Proof (of Theorem~\ref{thm:main})]
Let $d,e,f$ be a balanced partition and let $a=(d+e)/2$, $b=(d+f-1)/2$,
and $c=(e+f-1)/2$.
We construct a bijection~$\varphi$ from
chess tableaux of shape $d,e,f$
to nonconsecutive tableaux of shape $a,b,c$
with largest entry in row~1.

\medskip
{\bf Step 1: Description of the bijection~$\varphi$.}
Given a chess tableau~$T$ of balanced shape $d,e,f$,
first decompose it into a maximal set of balanced chess subtableaux
$T_0 \subset T_1 \subset T_2 \subset \dots \subset T_n = T$
and define $x_k$ and~$y_k$ as in the proof of Proposition~\ref{prop:bchain}.
That is, let $y_k$ be the largest entry of~$T_k$
and let $x_k = y_{k-1}+1$.
Recall that $x_k$ and~$y_k$ must be in row 2 or~3.

The image $U = \varphi(T)$ of~$T$ under our bijection
will be constructed in stages;
let $U_k$ denote the tableau
produced after stage~$k$ of the construction.

To construct~$U_0$, place the entries 1 through $y_0 - 1$
alternating in rows 1 and~2.

For $k>0$, exactly one of the four cases below holds;
carry out stage~$k$ of the construction accordingly.

{\em Case 1: $x_k$ and~$y_k$ are both in row~2.}
Construct $U_k$ by taking $U_{k-1}$,
appending $x_k - 1$ to row~3,
and then alternating $x_k$ through $y_k-1$ in rows 1 and~2,
starting with $x_k$ in row~1.

{\em Case 2: $x_k$ is in row~2, $y_k$ is in row~3.}
Construct $U_k$ by taking $U_{k-1}$,
appending $x_k - 1$ to row~3,
and then alternating $x_k$ through $y_k-1$ in rows 1 and~2,
starting with $x_k$ in row~2.

{\em Case 3: $x_k$ is in row~3, $y_k$ is in row~2.}
Construct $U_k$ by taking $U_{k-1}$,
appending $x_k - 1$ to row~2, $x_k$ to row~3,
and then alternating $x_k+1$ through $y_k-1$ in rows 1 and~2,
starting with $x_k+1$ in row~1.

{\em Case 4: $x_k$ and~$y_k$ are both in row~3.}
This case is unique in that $U_k$ is {\em not\/}
just an extension of~$U_{k-1}$.
Begin with $U_{k-1}$,
but first move its largest entry $x_k-2$
(along with the cell it's in) from row~1 to row~2 or row~3,
whichever choice preserves nonconsecutivity.
Then append $x_k-1$ to row~2 or row~3
(preserving nonconsecutivity),
and then alternate $x_k$ through $y_k-1$ in rows 1 and~2,
starting with $x_k$ in row~1, to obtain~$U_k$.

Before continuing with the proof, we give an
example, showing how the chess tableau of Figure~\ref{fig:chesstableau}
is carried to the nonconsecutive tableau of Figure~\ref{fig:noncon}.

\bigskip
\includegraphics[scale=0.3]{b1.eps}

\bigskip
\includegraphics[scale=0.3]{b2.eps}

\bigskip
\includegraphics[scale=0.3]{b3.eps}

\bigskip
\includegraphics[scale=0.25]{b4.eps}

\bigskip
\includegraphics[scale=0.25]{b5.eps}


\bigskip
{\bf Step 2: Proof that the description of~$\varphi$ makes sense.}
Denote the shape of~$T_k$ by $d_k,e_k,f_k$
and let $a_k=(d_k+e_k)/2$, $b_k=(d_k+f_k-1)/2$, and $c_k=(e_k+f_k-1)/2$.
Note that $a_k>b_k$.
We show by induction on~$k$ that
$U_k$ is a nonconsecutive tableau of shape $a_k,b_k,c_k$
with largest entry in row~1.

Observe that in Cases 1 and~4,
$x_k$ and~$y_k$ have opposite parity
(so that $y_k-x_k$ is odd),
while in Cases 2 and~3,
$x_k$ and~$y_k$ have the same parity
(so that $y_k-x_k$ is even).
This fact will be used implicitly below,
justifying our treating certain expressions
of the form $(\cdot)/2$ as integers.

\smallskip
In Case~1, $x_k$, the smallest integer not in $T_{k-1}$, is in row~2;
this means that $d_{k-1}>e_{k-1}$.
Therefore, $b_{k-1}>c_{k-1}$,
so there is no danger of creating an illegal shape
by appending $x_k-1$ to row~3 of~$U_{k-1}$.
Note that $d_k = d_{k-1} + y_k - x_k - 1$, $e_k=e_{k-1}+2$,
and $f_k = f_{k-1}$.
To~$U_{k-1}$, we have added $(y_k - x_k + 1)/2$ entries to row~1,
$(y_k-x_k-1)/2$ entries to row~2, and a single entry to row~3.
So $U_k$ has shape $a_k,b_k,c_k$.

In Case~2, the same argument as in Case~1 shows that
there is no danger of creating an illegal shape
by appending $x_k-1$ to row~3 of~$U_{k-1}$.
We have $d_k = d_{k-1} + y_k - x_k - 1$, $e_k=e_{k-1}+1$,
and $f_k = f_{k-1}+1$.
To~$U_{k-1}$, we have added $(y_k - x_k)/2$ entries to row~1,
$(y_k-x_k)/2$ entries to row~2, and a single entry to row~3.
So $U_k$ has shape $a_k,b_k,c_k$.

In Case~3, there is no danger of creating an illegal shape
by appending $x_k-1$ to row~2 of~$U_{k-1}$,
because, as we have already observed, $a_{k-1}>b_{k-1}$.
We have $d_k = d_{k-1} + y_k - x_k - 1$, $e_k=e_{k-1}+1$,
and $f_k = f_{k-1}+1$.
To~$U_{k-1}$, we have added $(y_k - x_k)/2$ entries to row~1,
$(y_k-x_k)/2$ entries to row~2, and a single entry to row~3.
So $U_k$ has shape $a_k,b_k,c_k$.

In Case~4, we have $e_{k-1}>f_{k-1}+2$
(strict inequality since $T_{k-1}$ is balanced).
Therefore, $a_{k-1}>b_{k-1}+1$.
In~$U_{k-1}$, if $x_k - 3$ is in row~3,
then $x_k - 2$ must be moved to row~2,
and there is no danger of creating an illegal shape.
On the other hand,
if $x_k - 3$ is not in row~3 of $U_{k-1}$
(and so, by nonconsecutivity, is necessarily in row~2),
then we claim that $b_{k-1}>c_{k-1}$.
If to the contrary, $b_{k-1}=c_{k-1}$,
then the last entry in row~2 of $U_{k-1}$,
namely $x_k-3$, could not exceed the last entry in row~3 of $U_{k-1}$.
However, the only entry in $U_{k-1}$
that is higher than $x_k - 3$ is $x_k - 2$,
which must be in row~1.
This contradiction shows that $b_{k-1}>c_{k-1}$,
so moving $x_k-2$ to row~3
will not create an illegal shape.
Moreover, since $a_{k-1}>b_{k-1}+1$,
row~1 is still longer than row~2 after the move,
so appending $x_k -1$ to row~2 also does not create an illegal shape.
We have $d_k = d_{k-1} + y_k - x_k - 1$, $e_k=e_{k-1}$,
and $f_k = f_{k-1}+2$.
To obtain~$U_k$,
we have increased row~1 of~$U_{k-1}$ by $(y_k - x_k-1)/2$ entries,
row~2 by $(y_k-x_k+1)/2$ entries, and row~3 by a single entry.
So $U_k$ has shape $a_k,b_k,c_k$.

\smallskip
Note that in Cases 1 through~3,
$x_k - 1$ is not placed next to $x_k - 2$,
which is in row~1 by induction.
Also note that in all four cases,
$y_k-1$ ends up in row~1 for parity reasons.

\bigskip
{\bf Step 3: Proving that $\varphi$ is a bijection.}
We construct $\varphi^{-1}$ by induction on the length of row~3.
But first, we remark that for parity reasons,
if we wish to enlarge any given balanced chess tableau of shape $d,e,f$,
we can always add $d+e+f+1$ to row~2 or row~3,
provided that $d>e$ or $e>f$, respectively.
However, it is never possible to add $d+e+f+1$ to row~1.
In other words, the parity of the last cell in rows 2 and~3
is equal to the parity of $d+e+f$,
whereas the last cell in row~1 has parity that of $d+e+f+1$.

Let $U$ be a nonconsecutive tableau of shape $a,b,c$
with largest entry in row~1.

If $c=0$, then we must have $a=b+1$
and $U$ is the unique nonconsecutive tableau
with the entries 1 through $a+b+1$ alternating in rows 1 and~2
starting with a 1 in row~1.
Map $U$ to the balanced chess tableau
with entries 1 through $a+b+1$ in row~1, $a+b+2$ in row~2, and empty row~3.

\smallskip
Now assume that $c>0$ and, by induction,
for all shapes $a',b',c'$ with $c'<c$,
we have constructed a map from nonconsecutive tableaux of shape $a',b',c'$
with largest entry in row~1
to balanced chess tableaux of shape $a'+b'-c'$, $a'-b'+c'$, $1-a'+b'+c'$.

Let $V$ be the tableau obtained from~$U$
by removing every entry greater than or equal to the last entry in row~3.

If $V$ has its largest entry in row~1, then let $U'=V$.
Let the shape of~$U'$ be given by $a',b',c'$.
By induction, $U'$ is mapped to a balanced chess tableau~$T'$.
Furthermore, the shape of~$T'$ is given by
$d'=a'+b'-c'$, $e'=a'+c'-b'$, $f'=1-a'+b'+c'$.
Let $x_n - 1$ and $y_n - 1$ be
the smallest and largest entries removed from~$U$ to obtain~$U'$.

Note that $c' < b'$ by construction of~$V$.  Therefore $d' > e'$.
Therefore, we can construct a chess tableau by adding
$x_n$ to row~2 of~$T'$, and then
adding the entries $x_n + 1$ through $y_n-1$ to row~1.
Finally, if $x_n$ and~$y_n$ have the same parity,
add $y_n$ to row~3; otherwise, add $y_n$ to row~2.
Map $U$ to the resulting tableau~$T$.

\smallskip
Now, suppose that the largest entry of~$V$ is not in row~1, but in row~2.
(By nonconsecutivity, the largest entry of~$V$ cannot be in row~3.)

If the penultimate entry in~$V$ is in row~1,
let $U'$ be the tableau obtained from~$V$
by deleting the largest entry (which is in row~2).
Let the shape of~$U'$ be given by $a',b',c'$.
Since $U'$ is a nonconsecutive tableau with largest entry in row~1,
by induction, $U'$ is mapped to a balanced chess tableau~$T'$.
Furthermore, the shape of~$T'$ is given by
$d'=a'+b'-c'$, $e'=a'+c'-b'$, $f'=1-a'+b'+c'$.
Let $x_n - 1$ and $y_n - 1$ be
the smallest and largest entries removed from~$U$ to obtain~$U'$.
Observe that since the largest entry of~$V$ is in row~2,
an even number of entries must have been removed from~$U$ to obtain~$V$.
This means that $x_n$ and~$y_n$ have the same parity.
Also, note that $a'>b'$ because $U'$ was obtained from~$V$
by removing the last entry in row~2.
This implies that $e'>f'$. 
Therefore, we can construct a chess tableau
by adding $x_n$ to row~3 of~$T'$,
and then adding the entries $x_n+1$ through $y_n-1$ to row~1.
Because $x_n$ and $y_n$ have the same parity,
we can finish by adding $y_n$ to row~2 to obtain
a chess tableau~$T$.  Map $U$ to this~$T$. 

\smallskip
Finally, assume that the penultimate entry in~$V$ is in row~3.
If an even number of entries were removed from~$U$ to obtain~$V$,
then let $U'$ be the nonconsecutive tableau
obtained by shifting the largest entry in~$V$,
along with its cell, into row~1.
If an odd number of entries were removed from~$U$ to obtain~$V$,
then let $U'$ be the nonconsecutive tableau obtained by adding to row~1
the largest entry in row~3 of~$U$.
Let the shape of~$U'$ be given by $a',b',c'$.
Since $U'$ is a nonconsecutive tableau with largest entry in row~1,
by induction, $U'$ is mapped to a balanced chess tableau~$T'$.
Furthermore, the shape of~$T'$ is given by
$d'=a'+b'-c'$, $e'=a'+c'-b'$, $f'=1-a'+b'+c'$.
Let $x_n - 1$ and $y_n - 1$ be
the smallest and largest entries removed from~$U$ to obtain~$U'$.
Because $U'$ has an even number of entries fewer than there are in~$U$,
we know that $x_n$ and~$y_n$ have opposite parity.
We claim that $a'>b'+1$.
To see this, first note that if the number of entries in $U$ and~$V$
have the same parity,
then $U'$ was obtained by shifting the last entry in row~2 to row~1,
so that $a'>b'+1$.
If the number of entries in $U$ and~$V$ have opposite parity,
then the lengths of rows 1 and~2 of~$V$ separately
differ from the lengths of rows 1 and~2 of~$U$ by equal amounts,
and since $a>b$, we know that the length of row~1 of~$V$
is greater than the length of its row~2.
Since $U'$ is obtained from~$V$ by adding an entry to row~1,
we conclude again that $a'>b'+1$.
Since $a'>b'+1$, we must have $e'>f'+1$.
Therefore, we can construct a chess tableau~$T$ from~$T'$
by adding $x_n$ to row~3,
adding the entries $x_n+1$ through $y_n-1$ to row~1,
and finally adding $y_n$ to row~3.
Map $U$ to this $T$. 

\smallskip
It is straightforward to check that this map and~$\varphi$
are inverse to each other, and hence are both bijections.

\smallskip
This completes the proof of the theorem for the case in which
$a+b-c, a-b+c, 1-a+b+c$ is a balanced partition.
Since $a-b+c$ and $1-a+b+c$ automatically have opposite parity,
the only remaining cases are those in which 
$a+b-c, a-b+c, 1-a+b+c$ is not a partition at all.
But note that if $a>b\ge c\ge 0$ and $a\le b+c+1$,
then $a+b-c\ge a-b+c\ge 1-a+b+c\ge0$.
Therefore if $a+b-c, a-b+c, 1-a+b+c$ is not a partition,
then $\ncon_1(a,b,c)=0$
(if $a>b+c+1$ then
every standard Young tableau of shape~$a,b,c$
must have consecutive entries in row~1),
and both sides of~(\ref{eq:main}) are zero.
\end{proof}

\bigskip
We conclude this section with an alternative
description of~$\varphi^{-1}$
that is surprisingly similar in form
to the description of~$\varphi$ itself.
We leave it to the reader to check that the following description
of a map makes sense and indeed coincides with~$\varphi^{-1}$.

Let $U$ be a nonconsecutive tableau with largest entry in its first row
of shape $a, b, c$.
Let $V$ be the nonconsecutive subtableau of $U$
obtained by removing the entries of~$U$
that are greater than the second largest entry in row~1.
Let $a', b', c'$ be the shape of~$V$.
Note that $a=a'+1$.

Assume by induction that we have already defined the bijection
on subshapes of $a, b, c$.
Let $S$ be the chess tableau that $V$ is mapped to by this bijection.
We show how to add entries to~$S$
to get a chess tableau~$T$ that will be the image of~$U$.

We consider four cases.

{\em Case 1.}
We have $b-b'=c-c'$ and the largest entry of~$U$ is in row~2.
In this case, form $T$ by first adding an entry to row~2 of~$S$,
then adding another entry to row~1 of~$S$,
and finally adding $2(b-b')-1$ entries to row~3 of~$S$.

{\em Case 2.}
We have $b-b'=c-c'+1$
(in which case the largest entry of~$U$ must be in row~2).
In this case, let $R$ be the row of the largest entry in~$S$.
Form $T$ by first moving the largest entry of~$S$ from row~$R$ to row~1,
then adding a new entry to row~1,
then adding an entry to row~$R$,
then adding $2(c-c')$ entries to row~3.

{\em Case 3.}
We have $b-b'=c-c'$ and the largest entry of~$U$ is in row~3.
In this case, form $T$ by first adding an entry to row~3 of~$S$,
then adding an entry to row~1,
followed by another entry to row~2,
followed by adding $2(b-b')-2$ entries to row~3.

{\em Case 4.}
We have $b-b'+1=c-c'$
(in which case the largest entry of~$U$ must be in row~3).
In this case, form $T$ by first adding two entries to row~2 of~$S$,
and then adding $2(b-b')$ entries to row~3.

\section{Generating Functions From Rat Races}
\label{ratrace}

\noindent
For SYT($\lambda$) there is the miraculous hook length formula,
but there seems to be no analogue for Chess($\lambda$). 
However, when $\lambda$ has two rows, there are nice expressions.
For example:

\begin{equation}\label{eq:tworowsrs}
\mbox{Chess}(2r+1,2s)= \binom{r+s}{r} - \binom{r+s}{r+1}
\end{equation}
Similar alternating sum formulas can be obtained for any number of rows
by interpreting tableaux as nontouching rat races, a concept
defined in~\cite{E93}.
It is equivalent to noncrossing lattice paths,
but suits our applications in the next section better.

A {\em rat race} is an event that takes place on the real line.
The rats have 
separate starting points, one unit apart to the left of the origin; in fact, 
rat $i$ starts at coordinate $-i$. The running distance for rat $i$ being 
$\lambda_i$ units, it will finish at coordinate $\lambda_i - i$.
Every time step, one of the rats moves one unit to the right. 
After $|\lambda|$ time steps, all rats have reached their final position.

\begin{figure}[ht]
\begin{center}
\definecolor{light}{gray}{0.90}
\noindent
\setlength{\unitlength}{0.3mm}
\begin{picture}(95,30)(0,0)
  \put(0,18.5){\colorbox{light}{\makebox(8,8){}}}
  \put(30,18.5){\colorbox{light}{\makebox(8,8){}}}
  \put(15,3.5){\colorbox{light}{\makebox(8,8){}}}
  \put(60,18.5){\colorbox{light}{\makebox(8,8){}}}
  \put( 0, 0){\line(1,0){45}}
  \put( 0,15){\line(1,0){75}}
  \put( 0,30){\line(1,0){75}}
  \put( 0, 0){\line(0,1){30}}
  \put(15, 0){\line(0,1){30}}
  \put(30, 0){\line(0,1){30}}
  \put(45, 0){\line(0,1){30}}
  \put(60,15){\line(0,1){15}}
  \put(75,15){\line(0,1){15}}
  \put( 4,19){1}
  \put(19,19){2}
  \put(34,19){3}
  \put(49,19){6}
  \put(64,19){7}
  \put( 4, 4){4}
  \put(19, 4){5}
  \put(34, 4){8}
\end{picture}
\setlength{\unitlength}{1.8pt}
\begin{picture}(80,20)(-20,-10)
\small
  \put(-10.1,0.1){\vector(1,0){70}}
  \put(-10, 0){\line(0,-1){2}}
  \put(  0, 0){\line(0,-1){2}}
  \put( 10, 0){\line(0,-1){2}}
  \put( 20, 7){\line(0,-1){9}}
  \put( 30, 0){\line(0,-1){2}}
  \put( 40, 0){\line(0,-1){2}}
  \put( 50, 7){\line(0,-1){9}}
  \put(0,3){\oval(3,5)}
  \put(-1.3,1){1}
  \put(-10,3){\oval(3,5)}
  \put(-11.3,1){2}
  \thicklines
  \put( 0,-0.3){\line(1,0){10}}
  \put(20,-0.3){\line(1,0){10}}
  \put(40,-0,3){\line(1,0){10}}
  \put(20,10){\oval(5.5,5.5)}
  \put(50,10){\oval(5.5,5.5)}
  \put(18.7, 8.2){2}
  \put(48.7, 8.2){1}
  \put(-14,-7){Rats start}
  \put(-14,-12){here\ldots}
  \put(20,-7){\ldots and finish}
  \put(28.5,-12){here.}

\end{picture}
\caption{A chess tableau and its nontouching rat race}
\label{fig:ratrace}
\end{center}
\end{figure}

The rat race is completely specified by recording which rat moves
in each time step. In Figure~\ref{fig:ratrace}, rat one moves in time
steps 1, 2, 3, 6,~7 and rat two in time steps 4, 5,~8. Standard Young
tableaux correspond to {\em nontouching rat races}, where two rats never
occupy the same coordinate simultaneously, for this condition means that
the columns are increasing.
{\em Touching rat races\/} are those that are not nontouching.

For a general rat race, there is no column condition and no condition 
on the row lengths. (Rat one may be a sprinter and rat two a marathon
runner.) However, the track segments are colored black and white, and
our rats run black segments only in odd time steps and white segments
only in even time steps. Therefore,  nontouching rat races will
correspond exactly to chess tableaux.
We let $\mbox{Rats}(\lambda)$ denote the number of rat races
(with the color restriction just described)
in which the $i$th rat moves $\lambda_i$ steps.

For the benefit of the rat crowd, all rats wear yellow T-shirts that
carry the row index in red digits. Once a year, on Involution Day, the
rat athletes play a prank on the unsuspecting crowd.
At the very first moment during the race that two rats meet,
the two rats in question switch T-shirts.
The spectators now believe that
they are watching a very different rat race.
If rats one and two switch shirts, rat one seems to run a distance
$\lambda_2-1$ while rat two seems to run $\lambda_1+1$. 
Nontouching races are not touched by the prank, but for the others a
bijection is established.
If $\lambda=a,b$ has just two parts $a\ge b$,
then the prank occurs if and only if rat two catches rat one,
and switching shirts gives a bijection between
touching rat races of shape $a,b$ and all rat races of shape $b-1,a+1$
(since the latter are necessarily touching).
Thus
\begin{equation}\label{eq:tworowsab}
\mbox{Chess}(a,b)=\mbox{Rats}(a,b)-\mbox{Rats}(b-1,a+1)
\end{equation}
Counting rat races is much easier than counting chess tableaux, and we 
readily obtain formula (\ref{eq:tworowsrs}) and similar ones for the other
parity cases.
A bivariate generating function $C(x,y)$ for $\mbox{Chess}(a,b)$
is also easy to compute.
\begin{equation}\label{eq:tworowsgen}
C(x,y)=\frac{(1+x-y)(1-2y^2)}{(1-y)(1-x^2-y^2)}
\end{equation}
Here, $\mbox{Chess}(a,b)$ is the coefficient of the term 
$x^a y^b$, unless $a<b$, in which case the term is uninteresting.

Rat races work for any number of rows; for three rows,
the touching rat races are of two types:
those in which rat two catches rat one first,
and those in which rat three catches rat two first.
So we must subtract $\mbox{Rats}(b-1,a+1,c)$
and $\mbox{Rats}(a,c-1,b+1)$ from
$\mbox{Rats}(a,b,c)$,
but then to handle double counting we must
follow through with alternating inclusion/exclusion terms.
We obtain the following relation.
\begin{eqnarray}\label{eq:threerowsabc}
\mbox{Chess}(a,b,c) & = & \mbox{Rats}(a,b,c)
-\mbox{Rats}(b-1,a+1,c)-\mbox{Rats}(a,c-1,b+1) \nonumber\\
& & \quad {} + \mbox{Rats}(c-2,a+1,b+1) +\mbox{Rats}(b-1,c-1,a+2) \nonumber\\
& & \quad {} -\mbox{Rats}(c-2,b,a+2)
\end{eqnarray}
Counting rat races is not too difficult if you use the obvious recursions.
Splitting the generating function for $\mbox{Rats}(a,b,c)$ into parity
cases, we can write 
\begin{equation}\label{eq:threerowsR}
R(x,y,z)= R_{bbw} + R_{bwb}  + R_{wbb} + R_{wwb} + R_{wbw} + R_{bww} .
\end{equation}
Here $R_{bbw}$ includes all shapes where the first row ends with a black 
square, the second with a black square and the third with a white square
(so the row lengths are odd, even, even). Note that $R_{bbb}$ and $R_{www}$
are zero. 

Now we have the following relations.

\bigskip
\label{eq:threerowsbbw}
$\begin{array}{clclclcl}
& R_{bbw} &=& xR_{wbw}&+&yR_{bww}\\
& R_{bwb} &=& xR_{wwb}&+&zR_{bww}\\
& R_{wbb} &=& yR_{wwb}&+&zR_{wbw}\\
& R_{wwb} &=& xR_{bwb}&+&yR_{wbb}\\
& R_{bww} &=& yR_{bbw}&+&zR_{bwb}\\
& R_{wbw} &=& xR_{bbw}&+&zR_{wbb}&+&1
\end{array}$
\bigskip

\noindent
Solving the system, we obtain the generating function for 
$\mbox{Rats}(a,b,c)$.
\begin{equation}\label{eq:}
R(x,y,z) = \frac{(1+y)(1+x-y+z)}{1-x^2-y^2-z^2-2xyz}
\end{equation}
If we substitute this into (\ref{eq:threerowsabc}), we get a
rational expression for $C(x,y,z)$, but with a forbidding numerator
and no obvious interesting properties. 
\begin{equation}
C(x,y,z)=\frac{1-\cdots\mbox{a hundred and forty-seven terms}\cdots -8y^3z^8}
{(1-x^2-y^2-z^2-2xyz)(1-y^2-z^2)^2(1-x^2-z^2)(1-z)}
\end{equation}

\noindent
But we know that $\mbox{Chess}(a,a,a)$ are interesting numbers, so we may try
to compute the {\em diagonal} of the ugly generating function. Indeed, for 
even $a$,  (\ref{eq:threerowsabc}) gives a simpler generating function, the 
$x^ay^az^a$-coefficient of which is $\mbox{Chess}(a,a,a)$.
\begin{eqnarray}
C_{\mbox{even}} & = & \frac{P
%1-\cdots\mbox{seventeen terms}\cdots +8y^4x^4
}{
((1-x^2-y^2-z^2)^2-4x^2y^2z^2)(1-x^2-y^2)} \\
\mbox{where } P & = &
1-3x^2-4y^2-z^2+4x^4+9y^2x^2+5y^4+3z^2y^2-2x^6-10y^2x^4 \nonumber\\
& & \qquad {}-6y^4x^2-2y^6+2z^2x^4-2z^2y^2x^2-2z^2y^4+8y^4x^4 \nonumber
\end{eqnarray}
For rectangles with odd row lengths we can obtain a similar but less
attractive expression. 

Extracting the diagonal of this rational generating function
can be done using residue calculus;
for example, Akalu Tefera's program MultInt~\cite{T02} can in principle
automatically find a recurrence satisfied by the diagonal coefficients.
This would yield a proof of Corollary~\ref{cor:baxter}
that, while not 100\% mechanical,
would require much less human ingenuity than our bijective proof.
Unfortunately, our rational generating function appears to be
too complex for this plan to be carried out with today's computers,
at least without any further tricks to simplify the computation.


\section{The Connection With Chess Problems}
\label{queue}

There is a class of composed chess problems
called {\em queue problems\/}
in which each solution comprises the same {\em set\/} of moves,
but in which the {\em order\/} of the moves varies from
solution to solution.
The goal is to find the total number of solutions.

Examples of queue problems may be found in~\cite{BPV92} and~\cite{St04}.
In all these examples,
the number of solutions equals the number of linear extensions
of some particular finite poset.
(The relations in the poset often correspond to
moves that must occur in a certain order because
one piece must vacate a square or a line
to allow the next piece to move;
this explains the term ``queue problem,''
and by thinking of chess pieces as rats,
one readily sees the connection to rat races.)
Moreover, all the examples are {\em series-movers,}
i.e., problems in which one side
executes a series of consecutive moves
while the other side passively stands by making no moves at all,
in violation of one of the official rules of chess.

Shortly before \cite{St04} was written,
it occurred to us that perhaps it would be possible to compose
combinatorially interesting chess problems
in which White and Black alternate moves.
For those familiar with the principle behind
the examples in~\cite{St04},
it is easy to see that instead of linear extensions of posets,
we now seek posets whose elements are each colored either black or white,
such that the number of {\em alternating linear extensions}---i.e.,
linear extensions in which black and white elements
strictly alternate---is a combinatorially interesting number.

There is an unlimited number of possible posets,
and black/white colorings of the posets,
that one can choose to investigate.
We chose to start by considering black/white colorings
of Young diagrams, and this quickly led to
the definition of a chess tableau.
(Ironically, even though we were motivated by composing chess problems,
we initially used the term ``checkerboard tableau,''
switching to the term ``chess tableau''
only after learning that that was what Sj\"ostrand had called them.)

Corollary~\ref{cor:baxter} shows that the number of
$3\times n$ chess tableaux is combinatorially interesting,
so the task presents itself of composing a chess problem
based on this fact.
The problem shown in Figure~\ref{fig:chessprob} below,
composed by the first author and
dedicated to Richard Stanley on his 60th birthday,
is a first attempt in that~direction.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.8]{chess_rstan.eps}
\caption{Helpstalemate with 2 solutions}
\label{fig:chessprob}
\end{center}
\end{figure}

The stipulation ``H=4.5'' means that it is White to move,
and that White and Black are to {\em cooperate\/} so as to
{\it stalemate\/} Black after White's fifth move.
White and Black alternate moves,
so Black makes a total of four moves.
The usual rules governing the legality of chess moves apply.
The expression ``7+7'' is a checksum,
indicating that there are 7~White units and
7~Black units on the board.

It turns out that there are precisely two solutions:
\def\Rd{{\bf Rd7}}
\def\Rb{{\bf Rb7}}
\def\Bc{{\bf Bc7}}
\def\Ba{{\bf Ba6}}
\begin{itemize}
\item 1.dxe7 \Rd\ 2.Rxd7 \Bc\ 3.Rxf5 \Ba\ 4.bxc7 \Rb\ 5.Bxa6
\item 1.dxe7 \Bc\ 2.bxc7 \Rd\ 3.Rxf5 \Rb\ 4.Rxd7 \Ba\ 5.Bxa6
\end{itemize}
(We have written Black's moves in boldface for clarity.)
These can be thought of as corresponding to the two
chess tableaux of shape $3,3,3$ as follows.
Observe that the following relationships must hold
between the individual moves of the solution:
\begin{itemize}
\item dxe7 must precede \Rd\ and \Bc.
\item \Rd\ must precede Rxd7 and Rxf5.
\item \Bc\ must precede bxc7 and Rxf5.
\item Rxf5 and Rxd7 must precede \Ba.
\item Rxf5 and bxc7 must precede \Rb.
\item \Rb\ and \Ba\ must precede Bxa6.
\end{itemize}
(Note: The reason \Rb\ must precede Bxa6 is that
the rook is pinning the bishop.
By convention, even in series-movers,
intermediate positions in which one of the kings is in check
are forbidden.)
These conditions impose a partial order on the moves;
see Figure~\ref{fig:poset}.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.35]{chess_poset.eps}
\caption{Ordering constraints among the moves}
\label{fig:poset}
\end{center}
\end{figure}

This poset has 42 linear extensions, corresponding to
the 42 standard Young tableaux of shape 3,3,3.
If Black and White were free to make the nine moves in question
in any order and were not required to alternate moves,
then these 42 tableaux would give rise to 42 solutions.
However, the requirement that Black and White alternate moves
imposes an additional constraint,
which is readily seen to force the tableaux to be chess tableaux.
By Corollary~\ref{cor:baxter}, there are just two chess tableaux
of shape 3,3,3, which give rise to the two solutions to the problem.

Clearly this example only scratches the surface of the possibilities
for composing chess problems of this sort.
There are presumably many other families of bicolored posets
whose alternating linear extensions have a nice enumeration
that can be exploited for compositional purposes.

\section{The Charney-Davis Statistic and Open Problems}
\label{charney}

Given a standard Young tableau~$T$ with $n$ cells,
let $des(T)$ denote the number of {\em descents\/} of~$T$, i.e.,
the number of positive integers $i<n$ such that
the entry $i+1$ appears in a lower-numbered row of~$T$
than the entry~$i$ does.
Given a partition~$\lambda$, we follow~\cite{RSW03}
and define the {\em Charney-Davis statistic\/} by
$$\cd(\lambda) = \sum_T (-1)^{des(T)},$$
where the sum is over all standard Young tableaux~$T$ of shape~$\lambda$.

In~\cite{RSW03}, the value of $\cd(\lambda)$ is computed explicitly
for $k\times n$ rectangles~$\lambda$ for $k=2,3,4$.
Strikingly,
we find that $|\cd(n,n)|=\chess(n,n)$
and $|\cd(n,n,n)|=\chess(n,n,n)$.
This cries out for a combinatorial explanation, but we do not have one.
If we compare $\cd(\lambda)$ and $\chess(\lambda)$
for other partitions $\lambda$ with a small number of parts,
then there are not many other numerical coincidences,
so a result like Theorem~\ref{thm:main} does not seem likely.
In particular, $|\cd(5,5,5,5)| = 580$ while $\chess(5,5,5,5) = 324$,
and $|\cd(5,5,5,5,5)| = 25100$ while $\chess(5,5,5,5,5) = 8716$.
% Note also that one of the keys to proving Theorem~\ref{thm:main}
% was the fact that both $\ncon_i$ and $\chess$ expand into
% a sum of {\em two\/} smaller terms,
% whereas the obvious analogous attempt to expand $\cd_i$
% results in {\em three\/} smaller terms,
% complicating any attempt to show that $\cd$ and $\chess$
% ``satisfy the same recurrence.''

As if three different relationships between $3\times n$ tableaux
and Baxter permutations were not enough,
Richard Stanley helped us observe that the summand in
equation~(\ref{eq:baxter}),
namely
\begin{equation}
\label{eq:summand}
\binom{n}{k} \binom{n}{k+1}\binom{n}{k+2}
   \bigg/ \binom{n}{0}\binom{n}{1}\binom{n}{2},
\end{equation}
is the number of $3\times k$ semistandard Young tableaux
with entries between $1$ and $n-k+1$ inclusive.
Dulucq and Guibert show that (\ref{eq:summand})
is the number of $3\times n$ nonconsecutive tableaux
with $k$ entries $i$ such that $i$ is in row~3
and $i+1$ is in row~1.
In terms of balanced chess tableaux,
the parameter $k$ counts the number of balanced subtableaux~$T_i$
falling into the first two of the four possible cases
in the proof of Theorem~\ref{thm:main}.
However, we have not found a direct bijection with
semistandard tableaux.

More generally, the number of Baxter permutations shows up
in other places in mathematics,
e.g., \cite{ABP04}, \cite{B03}, and \cite{C03}.
Are there bijections with chess tableaux?

Finally, an intriguing observation for which we have no explanation
is that the quantity $\sum_{\lambda\vdash n} \chess(\lambda)^2$,
where the sum ranges over all partitions of~$n$,
appears to be divisible by high powers of two.
Specifically, the sequence begins
\begin{equation*}
\begin{split}
1, \quad 2, &\quad 2, \quad 2^2, \quad 2^3, \quad 2^4, \quad 2^4\cdot3,
  \quad 2^5\cdot5, \quad 2^6\cdot7, \quad 2^{11}, \quad 2^8\cdot5^2,\\
&2^9\cdot61, \quad 2^{10}\cdot3\cdot41,
  \quad 2^{11}\cdot5\cdot59, \quad 2^{11}\cdot1523,
  \quad 2^{13}\cdot23\cdot83, \\
& \quad 2^{13}\cdot11411, \quad 2^{15}\cdot103\cdot163, \quad \ldots
\end{split}
\end{equation*}
Perhaps the Robinson-Schensted-Knuth correspondence
can be used to help explain this phenomenon.

\section{Acknowledgments}

The first author thanks Joost de Heer for helping him
learn to use the computer program Popeye to test his
chess problem for soundness.
We also thank Noam Elkies for typesetting the chess diagram,
and Jim Propp for drawing our attention to~\cite{C03}.

% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix

% \section{}
% \label{}

%%%  Squashing the bibliography together a bit

  \let\oldthebibliography=\thebibliography
  \let\endoldthebibliography=\endthebibliography
  \renewenvironment{thebibliography}[1]{%
    \begin{oldthebibliography}{#1}%
      \setlength{\parskip}{0.2ex}%
      \setlength{\itemsep}{0.2ex}%
  }%
  {%
    \end{oldthebibliography}%
  }


\begin{thebibliography}{00}

% \bibitem{label}
% Text of bibliographic item

\bibitem{ABP04}
E. Ackerman, G. Barequet and R. Pinter,
On the number of rectangular partitions,
{\em SODA '04} (Proceedings of the 15th Annual 
ACM-SIAM Symposium on Discrete Algorithms), 2004.

\bibitem{B03}
M. Bousquet-M\'elou,
Four classes of pattern-avoiding permutations under one roof:
Generating trees with two labels,
{\em Electronic J. Combin.}\ {\bf 9(2)} (2002--2003), \#R19.

\bibitem{C03}
H. Canary, Aztec diamonds and Baxter permutations,
{\tt math.CO/0309135}.

\bibitem{DG96}
S. Dulucq and O. Guibert, Stack words, standard tableaux and Baxter
permutations, {\em Disc.\ Math.}\ {\bf 157} (1996), 91--106.

\bibitem{E93}
H. Eriksson, Rat races and the hook length formula,
{\em FPSAC '93} (Proceedings of the 5th Conference on
Formal Power Series and Algebraic Combinatorics), 1993.

% \bibitem{FL02}
% B. Feigin and S. Loktev,
% Multi-dimensional Weyl modules and symmetric functions,
% {\tt math.QA/0212001}.

\bibitem{BPV92}
A. Puusa, Queue problems,
{\em Suomen Teht\"av\"aniekat}
(Finnish Chess Problem Society), 1992.

\bibitem{RSW03} 
V. Reiner, D. Stanton, and V. Welker,
The Charney-Davis quantity for certain graded posets,
{\em S\'em.\ Lothar.\ Combin.}\ {\bf 50} (2003--2004), B50c.

\bibitem{Sj03}
J. Sj\"ostrand,
On the imbalance of partition shapes,
{\tt math.CO/0309231}.

\bibitem{St04}
R. Stanley, Queue problems revisited,
{\em Suomen Teht\"av\"aniekat}
(Finnish Chess Problem Society), to appear.

\bibitem{T02}
A. Tefera,  MultInt, a Maple Package for Multiple Integration by the WZ
Method, {\em J. Symbolic Comp.}\ {\bf 34} (2002), 329--353.

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}


\end{thebibliography}

\end{document}

.
