% 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 $j1$, \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' 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