\input amstex
\input amspptbk.sty

\magnification1200

\TagsOnRight

\input path.sty

\def\BereAA{1}
\def\BrFoAA{2}
\def\BurrAA{3}
\def\BuMMAA{4}
\def\BuCFAA{5}
\def\ChDDAB{6}
\def\DeDFAA{7}
\def\DuSaAA{8}
\def\FomiAZ{9}
\def\FomiAB{10}
\def\FomiAF{11}
\def\GeZeAA{12}
\def\GoulAD{13}
\def\GrMrAA{14}
\def\GreCAA{15}
\def\KnutAA{16}
\def\KratBC{17}
\def\KratCE{18}
\def\LeeuAD{19}
\def\LeeuAH{20}
\def\MacdAC{21}
\def\ProcAA{22}
\def\RobiAA{23}
\def\RobyAA{24}
\def\RobyAD{25}
\def\SagaAQ{26}
\def\ScheAA{27}
\def\SchuAB{28}
\def\SchuAA{29}
\def\StanBI{30}
\def\SunaAE{31}
\def\SunaAD{32}
\def\SunaAC{33}

\def\SA{1}
\def\SB{2}
\def\SC{3}
\def\SD{4}

\def\TA{1}
\def\TB{2}
\def\TC{3}
\def\TD{4}

\def\FA{1}
\def\FB{2}
\def\FC{3}
\def\FD{4}
\def\FE{5}
\def\FF{6}
\def\FG{7}

\def\AA{4.1}

\topmatter 
\title Bijections between oscillating tableaux and (semi)standard
tableaux via growth diagrams
\endtitle 
\author C.~Krattenthaler 
\endauthor 
\affil 
Fakult\"at f\"ur Mathematik, Universit\"at Wien,\\
Oskar-Morgenstern-Platz~1, A-1090 Vienna, Austria.\\
WWW: {\tt http://www.mat.univie.ac.at/\~{}kratt}
\endaffil
\address Fakult\"at f\"ur Mathematik, Universit\"at Wien,
Oskar-Morgenstern-Platz~1, A-1090 Vienna,\linebreak Austria.\newline
WWW: \tt http://www.mat.univie.ac.at/\~{}kratt
\endaddress

\thanks Research partially supported 
by the Austrian Science Foundation FWF, grant Z130-N13, and
grant SFB F50 (Special Research Program
``Algorithmic and Enumerative Combinatorics")
\endthanks
\subjclass Primary 05A15;
 Secondary 05E10
\endsubjclass
\keywords standard Young tableaux, semistandard tableaux,
oscillating tableaux,
Robin\-son--Schensted correspondence, 
Robin\-son--Schensted--Knuth correspondence, 
growth diagrams
\endkeywords
\abstract 
We prove that 
the number of oscillating tableaux
of length $n$ with at most $k$ columns,
starting at $\emptyset$ and ending at the one-column shape $(1^m)$,
is equal to the number of standard Young tableaux of size~$n$
with $m$ columns of odd length, all columns of length
at most $2k$. This refines a conjecture of Burrill, 
which it thereby establishes. 
We prove as well a ``Knuth-type" extension stating a similar
equi-enumeration result between generalised oscillating tableaux
and semistandard tableaux.
\endabstract
\endtopmatter
\document


\subhead 1. Introduction \endsubhead
The {\it Robinson--Schensted correspondence} \cite{\RobiAA, \ScheAA}
(see \cite{\SagaAQ, Sec.~3.1}) is a bijection between {\it permutations}
of $\{1,2,\dots,n\}$ and pairs of {\it standard (Young) tableaux} of the
same shape of size $n$ (see Section~\SB\ for all definitions).
Knuth's extension, the so-called 
{\it Robinson--Schensted--Knuth} ({\it RSK}) {\it correspondence} 
\cite{\KnutAA}
(see \cite{\SagaAQ, Sec.~4.8}) is a bijection between {\it
non-negative integer matrices}
and pairs of {\it semistandard tableaux} of the
same shape. These correspondences are not only attractive in
their own right due to
their elegance, but are important since they map several natural
statistics of permutations, respectively matrices, to corresponding ones for
tableaux, and thus allow for numerous refinements. 
An important statistic in this context is the length of the
longest increasing (or decreasing) subsequence in a permutation
(or of certain chains of entries in a matrix) which, by Schensted's
theorem \cite{\ScheAA}, are mapped to the length of the first row
(or first column) of the shapes of the tableaux. Greene \cite{\GreCAA}
extended Schensted's theorem by describing precisely how lengths 
of increasing (or decreasing) subsequences in permutations (chains in
matrices) determine the shape of the tableaux in the image pair under
these correspondences.

Standard or semistandard 
tableaux may be seen as sequences of Ferrers diagrams, where 
an element in the sequence is followed by a Ferrers diagram which
is by one cell (in the case of standard tableaux) or by a horizontal
strip (in the case of semistandard tableaux) larger. A variation
consists in considering sequences of Ferrers diagrams where, from
one element in the sequence to the next, one also allows sometimes
to shrink by a cell or by a horizontal (or vertical) strip. This leads to the
notion of {\it oscillating tableaux}. Also in this context, there
are Robinson--Schensted(--Knuth) like algorithms which connect
oscillating tableaux to, for instance, 
involutions, matchings, or set partitions;
see \cite{\BereAA, \DeDFAA, \DuSaAA, 
\ProcAA, \RobyAA, \RobyAD, \SunaAE, \SunaAD, \SunaAC}.
Greene's theorem \cite{\GreCAA} still applies, which has been
particularly exploited in \cite{\ChDDAB, \KratCE}.

If one encounters families of tableaux, permutations, integer
matrices, etc. which seem to be enumerated by the same numbers,
then one must suspect that an RSK-like bijection lurks in the
background. The purpose of the present paper is 
to illustrate this ``principle" by
applying it to a recent conjecture of Burrill
\cite{\BurrAA, Conj.~6.2.1} (see 
\cite{\BuMMAA, Conj.~4} for the formulation below; 
again, for all undefined terminology
see Section~\SB).

\proclaim{Conjecture \smc(Burrill)}
Let $n$ and $k$ be given non-negative integers. 
The number of oscillating tableaux
of length $n$ with at most $k$ columns,
starting at $\emptyset$ and ending at some one-column shape
is the same as the number of
standard Young tableaux of size~$n$ (meaning that its shape has $n$~cells) 
with all columns of length at most $2k$.
\endproclaim

In Theorem~\TC\ in Section~\SC, a refinement of this conjecture will
be established, which in addition relates the length of the one-column shape
in which the oscillating tableaux end to the number of odd-length
columns of the standard tableaux. Moreover, in Theorem~\TD,
we present a ``Knuth-type" extension, in which we allow
more general oscillating tableaux, and the standard Young tableaux
get replaced by semistandard tableaux. We point out that a
different bijection proving Theorem~\TC\ has been presented
by Burrill, Courtiel, Fusy, Melczer and Mishna in \cite{\BuCFAA},
the difference lying in the way the parameter~$m$ (the number of
odd columns of the standard Young tableau, respectively the
size of the final shape of the oscillating tableau) is kept track of.

While, originally, RSK-like correspondences are based on
insertion-deletion algorithms, it is nowadays standard that the
most transparent way to present these correspondences is by
means of Fomin's {\it growth
diagrams} \cite{\FomiAZ, \FomiAB, \FomiAF}
(see \cite{\RobyAA, \RobyAD},
\cite{\SagaAQ, Sec.~5.2} and \cite{\StanBI, Sec.~7.13} for non-technical
expositions). This is also the point of view we shall adopt in
our (bijective) proofs of Theorems~\TC\ and \TD. It will be combined
with an application of Sch\"utzenberger's \cite{\SchuAA} jeu de
taquin (for which also geometric realisations have been proposed ---
see \cite{\LeeuAD} ---, which we shall however not use here).

In the final Section~4, we explain that --- non-illuminating ---
computational proofs of Theorems~\TC\ and \TD\ can be extracted
from the literature by appropriately combining results of Gessel and
Zeilberger \cite{\GeZeAA} and of Goulden \cite{\GoulAD}, we
comment on what happens if, instead of an even number, we bound
the length of columns of the standard Young tableaux in Theorem~\TC\
by an odd number, and we provide a more detailed discussion of
the differences between the bijection proving Theorem~\TC\ presented
here and the one in \cite{\BuCFAA}.

\subhead 2. Definitions and notation \endsubhead
We start by fixing the standard partition notation (cf.\
e.g.\ \cite{\StanBI, Sec.~7.2}).
A {\it partition} is a weakly decreasing sequence
$\la=(\la_1,\la_2,\dots,\la_\ell)$ of positive integers.
This also includes the {\it empty partition} $()$, denoted by
$\emptyset$. For the sake of convenience, we shall often tacitly
identify a partition $\la=(\la_1,\la_2,\dots,\la_\ell)$ with the
infinite sequence $(\la_1,\la_2,\dots,\la_\ell,0,0,\dots)$, that is,
the sequence which arises from $\la$ by appending infinitely
many $0$'s. To each partition $\la$, one
associates its {\it Ferrers diagram} (also called {\it Ferrers shape}), 
which is the left-justified
arrangement of squares with $\la_i$ squares in the $i$-th row,
$i=1,2,\dots$. The number of squares in the Ferrers diagram,
$\la_1+\la_2+\dots+\la_\ell$, is called the {\it size} of the
partition~$\la$, and is denoted by $\vert\la\vert$.
We define a {\it partial order} $\subseteq$ on partitions 
by containment of their Ferrers diagrams.
The {\it union} $\mu\cup\nu$ of two partitions $\mu$ and $\nu$
is the partition which arises by forming the union of the Ferrers
diagrams of $\mu$ and $\nu$. Thus, if
$\mu=(\mu_1,\mu_2,\dots)$ and
$\nu=(\nu_1,\nu_2,\dots)$, then $\mu\cup\nu$ is the partition 
$\la=(\la_1,\la_2,\dots)$, where $\la_i=\max\{\mu_i,\nu_i\}$ for 
$i=1,2,\dots$. The {\it intersection} 
$\mu\cap\nu$ of two partitions $\mu$ and $\nu$
is the partition which arises by forming the intersection of the Ferrers
diagrams of $\mu$ and $\nu$. Thus, if
$\mu=(\mu_1,\mu_2,\dots)$ and
$\nu=(\nu_1,\nu_2,\dots)$, then $\mu\cap\nu$ is the partition 
$\rh=(\rh_1,\rh_2,\dots)$, where $\rh_i=\min\{\mu_i,\nu_i\}$ for 
$i=1,2,\dots$.
%The {\it conjugate of\/} a partition $\lambda$ is the partition 
%$(\lambda^\prime_1, \dots, \lambda^\prime_{\lambda_1})$ where
%$\lambda_j'$ is the length of the $j$-th column in the Ferrers
%diagram of $\lambda$.

\medskip
Given a partition $\la=(\la_1,\la_2,\dots,\la_\ell)$, a {\it standard
(Young) tableau of shape\/} $\la$ is a left-justified arrangement
of positive integers with $\la_i$ entries in row~$i$, $i=1,2,\dots$,
such that the entries along rows and columns are increasing.
An arrangement $T$ of the same form as above is called
{\it semistandard tableau of shape\/} $\la$ if 
the entries along rows are weakly increasing
and such that the entries along columns are strictly increasing. 
By considering the sequence of partitions (Ferrers shapes)
$(\la^{i})_{i\ge0}$, where $\la^i$ is the shape formed by the
entries of $T$ which are at most~$i$,
$i=0,1,2,\dots$, one sees that standard tableaux of shape $\la$ are in
bijection with sequences 
$\emptyset=\la^0\subseteq\la^1\subseteq\dots\subseteq\la^n=\la$,
where $\la^{i-1}$ and $\la^i$ differ by exactly one square for all~$i$,
while semistandard tableaux of shape $\la$ are in bijection with
such sequences where $\la^{i-1}$ and $\la^i$ differ by a 
{\it horizontal strip} for all~$i$, that is, by an arrangement of squares with
at most one square in each column.

Generalising the above concepts, we call a sequence
$\emptyset=\la^0,\la^1,\dots,\la^n=\la$ of partitions an
{\it oscillating tableau of shape} $\la$ if either $\la^{i-1}\subseteq
\la^i$ or $\la^{i-1}\supseteq \la^i$ and $\la^{i-1}$ and $\la^i$
differ by exactly one square, $i=1,2,\dots,n$. 
The number~$n$ is called the {\it length\/} of the (generalised)
oscillating tableau.
If we say that an oscillating tableau has ``at most $k$ 
columns" then we mean that {\it all\/} partitions in the sequence
have at most $k$ columns.

\medskip
{\it Growth diagrams} are certain labellings of arrangements of cells.
The arrangements of cells which we need here are arrangements which
are left-justified (that is, they have a straight vertical left
boundary),
bottom-justified (that is, they have a straight horizontal bottom
boundary), and rows and columns in the arrangement are ``without"
holes, that is, if we move along the top-right boundary of the
arrangement, we always move either to the right or to the bottom.
Figure~\FA.a shows an example of such a cell arrangement.

\midinsert
$$
\Einheit.4cm
\Pfad(0,18),666666666666666666111111111111111\endPfad
\Pfad(0,18),111666666666666666666\endPfad
\Pfad(0,15),111111666666666666666\endPfad
\Pfad(0,12),111111666111666666666\endPfad
\Pfad(0,9),111111111666666111666\endPfad
\Pfad(0,6),111111111666111111666\endPfad
\Pfad(0,3),111111111111111666\endPfad
\hbox{\hskip7.5cm}
\Pfad(0,18),666666666666666666111111111111111\endPfad
\Pfad(0,18),111666666666666666666\endPfad
\Pfad(0,15),111111666666666666666\endPfad
\Pfad(0,12),111111666111666666666\endPfad
\Pfad(0,9),111111111666666111666\endPfad
\Pfad(0,6),111111111666111111666\endPfad
\Pfad(0,3),111111111111111666\endPfad
\Label\ro{\text {\seventeenpoint $0$}}(1,1)
\Label\ro{\text {\seventeenpoint $0$}}(4,1)
\Label\ro{\text {\seventeenpoint $0$}}(7,1)
\Label\ro{\text {\seventeenpoint $0$}}(10,1)
\Label\ro{\text {\seventeenpoint $0$}}(1,4)
\Label\ro{\text {\seventeenpoint $0$}}(7,4)
\Label\ro{\text {\seventeenpoint $0$}}(1,7)
\Label\ro{\text {\seventeenpoint $0$}}(4,7)
\Label\ro{\text {\seventeenpoint $0$}}(7,7)
\Label\ro{\text {\seventeenpoint $0$}}(4,10)
\Label\ro{\text {\seventeenpoint $0$}}(1,13)
\Label\ro{\text {\seventeenpoint $0$}}(4,13)
\Label\ro{\text {\seventeenpoint $0$}}(1,16)
\Label\ro{\text {\seventeenpoint $1$}}(4,4)
\Label\ro{\text {\seventeenpoint $1$}}(1,10)
\Label\ro{\text {\seventeenpoint $1$}}(13,1)
\hskip6cm
$$
\vskip10pt
\centerline{\eightpoint a. A cell arrangement
\hskip4cm
b. A filling of the cell arrangement}
\vskip6pt
\centerline{\smc Figure \FA}
\endinsert

We fill the cells of such an arrangement $C$ with non-negative integers.
Most of the time,
the fillings will be restricted to $0$-$1$-fillings
such that every row and every column contains at most one $1$.
See Figure~\FA.b for an example.

Next, the corners of the cells are labelled by partitions
such that the following two conditions are satisfied:

\roster
\item"(C1)" A partition is either equal to its right neighbour
or smaller by exactly one square, the same being true for a
partition and its top neighbour.
\item"(C2)" A partition and its right neighbour are equal if and only
if in the column of cells of $C$ below them there appears no $1$ and if
their bottom neighbours are also equal to each other.
Similarly, a partition and its top neighbour are equal if and only if
in the row of cells of $C$ to the left of them there appears no $1$ and if
their left neighbours are also equal to each other.
\endroster

See Figure~\FB\ for an example. (More examples can be found in
Figures~\FD--\FF.)
There, we use a short notation for partitions. For example,
$11$ is short for $(1,1)$.
Moreover, we changed the convention of representing the filling slightly
for better visibility,
by suppressing $0$'s and by replacing $1$'s by X's. Indeed, the
filling represented in Figure~\FB\ is the same as the one in
Figure~\FA.b.

Diagrams which obey the conditions (C1) and (C2) are called {\it
growth diagrams}.

\vskip10pt
\midinsert
$$
\Einheit.4cm
\Pfad(0,18),666666666666666666111111111111111\endPfad
\Pfad(0,18),111666666666666666666\endPfad
\Pfad(0,15),111111666666666666666\endPfad
\Pfad(0,12),111111666111666666666\endPfad
\Pfad(0,9),111111111666666111666\endPfad
\Pfad(0,6),111111111666111111666\endPfad
\Pfad(0,3),111111111111111666\endPfad
\Label\ro{\emptyset}(0,0)
\Label\ro{\emptyset}(0,3)
\Label\ro{\emptyset}(0,6)
\Label\ro{\emptyset}(0,9)
\Label\ro{\emptyset}(0,12)
\Label\ro{\emptyset}(0,15)
\Label\ro{\emptyset}(0,18)
\Label\ro{1}(3,18)
\Label\ro{1}(3,15)
\Label\ro{1}(3,12)
\Label\ro{\emptyset}(3,9)
\Label\ro{\emptyset}(3,6)
\Label\ro{\emptyset}(3,3)
\Label\ro{\emptyset}(3,0)
\Label\ro{\hphantom{1}11}(6,15)
\Label\ro{\hphantom{1}11}(6,12)
\Label\ro{1}(6,9)
\Label\ro{1}(6,6)
\Label\ro{\emptyset}(6,3)
\Label\ro{\emptyset}(6,0)
\Label\ro{1}(9,9)
\Label\ro{1}(9,6)
\Label\ro{\emptyset}(9,3)
\Label\ro{\emptyset}(9,0)
\Label\ro{\emptyset}(12,3)
\Label\ro{\emptyset}(12,0)
\Label\ro{1}(15,3)
\Label\ro{\emptyset}(15,0)
\Label\ro{\text {\seventeenpoint X}}(4,4)
\Label\ro{\text {\seventeenpoint X}}(1,10)
\Label\ro{\text {\seventeenpoint X}}(13,1)
\hskip6cm
$$
\vskip10pt
\centerline{\eightpoint A growth diagram}
\vskip6pt
\centerline{\smc Figure \FB}
\endinsert
\vskip10pt

We are interested in growth diagrams which
obey the following ({\it forward}) {\it local rules} 
(see Figure~\FC).

\vskip10pt
\midinsert
$$
\Pfad(0,0),1111222255556666\endPfad
\Label\lu{\rh}(0,0)
\Label\ru{\mu}(4,0)
\Label\lo{\nu}(0,4)
\Label\ro{\la}(4,4)
\hbox{\hskip6cm}
\Pfad(0,0),1111222255556666\endPfad
\Label\lu{\rh}(0,0)
\Label\ru{\mu}(4,0)
\Label\lo{\nu}(0,4)
\Label\ro{\la}(4,4)
\thicklines
\Pfad(1,1),33\endPfad
\raise.5pt\hbox to 0pt{\hbox{\hskip-.5pt}\Pfad(1,1),3\endPfad\hss}%
\raise.5pt\hbox to 0pt{\hbox{\hskip-.5pt}\Pfad(2,2),3\endPfad\hss}%
\raise1pt\hbox to 0pt{\hbox{\hskip-1pt}\Pfad(1,1),3\endPfad\hss}%
\raise1pt\hbox to 0pt{\hbox{\hskip-1pt}\Pfad(2,2),3\endPfad\hss}%
\raise-.5pt\hbox to 0pt{\hbox{\hskip.5pt}\Pfad(1,1),3\endPfad\hss}%
\raise-.5pt\hbox to 0pt{\hbox{\hskip.5pt}\Pfad(2,2),3\endPfad\hss}%
\raise-1pt\hbox to 0pt{\hbox{\hskip1pt}\Pfad(1,1),3\endPfad\hss}%
\raise-1pt\hbox to 0pt{\hbox{\hskip1pt}\Pfad(2,2),3\endPfad\hss}%
\Pfad(1,3),44\endPfad
\raise.5pt\hbox to 0pt{\hbox{\hskip.5pt}\Pfad(1,3),4\endPfad\hss}%
\raise.5pt\hbox to 0pt{\hbox{\hskip.5pt}\Pfad(2,2),4\endPfad\hss}%
\raise1pt\hbox to 0pt{\hbox{\hskip1pt}\Pfad(1,3),4\endPfad\hss}%
\raise1pt\hbox to 0pt{\hbox{\hskip1pt}\Pfad(2,2),4\endPfad\hss}%
\raise-.5pt\hbox to 0pt{\hbox{\hskip-.5pt}\Pfad(1,3),4\endPfad\hss}%
\raise-.5pt\hbox to 0pt{\hbox{\hskip-.5pt}\Pfad(2,2),4\endPfad\hss}%
\raise-1pt\hbox to 0pt{\hbox{\hskip-1pt}\Pfad(1,3),4\endPfad\hss}%
\raise-1pt\hbox to 0pt{\hbox{\hskip-1pt}\Pfad(2,2),4\endPfad\hss}%
\hskip2cm
$$
\vskip10pt
\centerline{\eightpoint a. A cell without cross\hskip3cm
b. A cell with cross}
\vskip6pt
\centerline{\smc Figure \FC}
\endinsert
\vskip10pt

\roster
\item"(F1)" If $\rh=\mu=\nu$, and if there is no cross in the
cell, then $\la=\rh$.
\item"(F2)" If $\rh=\mu\ne\nu$, then $\la=\nu$.
\item"(F3)" If $\rh=\nu\ne\mu$, then $\la=\mu$.
\item"(F4)" If $\rh,\mu,\nu$ are pairwise different, 
then $\la=\mu\cup\nu$.
\item"(F5)" If $\rh\ne \mu=\nu$, 
then $\la$ is formed by adding a square to the $(k+1)$-st row of
$\mu=\nu$, given that $\mu=\nu$ and $\rh$ differ in the $k$-th row.
\item"(F6)" If $\rh=\mu=\nu$, and if there is a cross in the
cell, then $\la$ is formed by adding a square to the first row of
$\rh=\mu=\nu$.
\endroster

Thus, if we label all the corners along the left and the bottom boundary
by empty partitions (which we shall always do in this paper), 
these rules allow one to determine all other labels
of corners uniquely.

It is not difficult to see that
the rules (F5) and (F6) are designed so that
one can also work one's way in the other direction, that is, given
$\la,\mu,\nu$, one can reconstruct $\rh$ {\it and\/} the filling of the cell.
The corresponding ({\it backward}) {\it local rules} are:

\roster
\item"(B1)" If $\la=\mu=\nu$, then $\rh=\la$.
\item"(B2)" If $\la=\mu\ne\nu$, then $\rh=\nu$.
\item"(B3)" If $\la=\nu\ne\mu$, then $\rh=\mu$.
\item"(B4)" If $\la,\mu,\nu$ are pairwise different, 
then $\rh=\mu\cap\nu$.
\item"(B5)" If $\la\ne \mu=\nu$, 
then $\rh$ is formed by deleting a square from the $(k-1)$-st row of
$\mu=\nu$, given that $\mu=\nu$ and $\la$ differ in the $k$-th row,
$k\ge2$.
\item"(B6)" If $\la\ne \mu=\nu$, and if $\la$ and $\mu=\nu$ differ in
the first row, then $\rh=\mu=\nu$.
\item""\hskip-36pt\vbox{\hsize13.76cm\noindent
In case (B6) the cell is filled with a $1$ (an X).
In all other cases the cell is filled with a $0$.}
\endroster

Thus, given a labelling of the corners along the right/up boundary of a
cell arrangement, one can algorithmically reconstruct the labels of
the other corners of the cells {\it and\/} of the $0$-$1$-filling 
by working one's way to the left and to the bottom.
These observations lead to the following theorem.

\proclaim{Theorem \TA} 
Let $C$ be an arrangement of cells.
The $0$-$1$-fillings of $C$ with the property that every row and
every column contains at most one $1$ are in bijection with labellings
$(\emptyset=\la^0,\la^1,\dots,\la^{k}=\emptyset)$ of the corners of
cells appearing along the top-right boundary of $C$, where $\la^{i-1}$
and $\la^i$ differ by at most one square, and
$\la^{i-1}\subseteq\la^i$ if $\la^{i-1}$ and $\la^i$ appear along
a horizontal edge, whereas
$\la^{i-1}\supseteq\la^i$ if $\la^{i-1}$ and $\la^i$ appear along
a vertical edge.
Moreover, $\la^{i-1}\subsetneqq\la^i$ if and only if there is a $1$
in the column of cells of $C$ below the corners labelled by $\la^{i-1}$ and
$\la^i$, and $\la^{i-1}\supsetneqq\la^i$ if and only if there is a $1$
in the row of cells of $C$ to the left of the corners labelled by
$\la^{i-1}$ and $\la^i$.
\endproclaim

\medskip
In addition to its local description,
the bijection of the above theorem has also a {\it global\/}
description. The latter is a consequence of a theorem of Greene
\cite{\GreCAA} (see also \cite{\BrFoAA, Theorems~2.1 and 3.2}). 
In order to formulate the
result, we need the following definitions: a {\it NE-chain} of a
$0$-$1$-filling is a sequence of $1$'s in the filling such that any $1$
in the sequence is above and to the right of the preceding $1$ in 
the sequence. Similarly, a {\it SE-chain} of a
$0$-$1$-filling is a set of $1$'s in the filling such that any $1$
in the sequence is below and to the right of the preceding $1$ in the sequence.

\proclaim{Theorem \TB} 
Given a growth diagram on a cell arrangement 
with empty partitions labelling all the
corners along the left boundary and the bottom boundary of the cell arrangement,
the partition $\la=(\la_1,\la_2,\dots,\la_\ell)$ labelling corner $c$ 
satisfies the following two properties:
\roster
\item"(G1)"For any $k$, the maximal cardinality of the union of $k$
NE-chains situated in the rectangular region to the left and
below of $c$ is equal to $\la_1+\la_2+\dots+\la_k$.
\item"(G2)"For any $k$, the maximal cardinality of the union of $k$
SE-chains situated in the rectangular region to the left and
below of $c$ is equal to $\la'_1+\la'_2+\dots+\la'_k$, where $\la'$
denotes the partition conjugate to $\la$.
\endroster
In particular, $\la_1$ is the length of the longest NE-chain
in the rectangular region to the left and below of $c$, and $\la'_1$
is the length of the longest SE-chain in the same
rectangular region.
\endproclaim


\subhead 3. The main theorems \endsubhead
Here, we state and prove our main results.
The theorem below proves and, at the same time, refines Burrill's
conjecture from the introduction. In the statement of the theorem and later,
the symbol $(1^m)$ stands for the partition 
$(1,1,\dots,1)$, with $m$ components
$1$, that is, the one-column shape of length~$m$.

\proclaim{Theorem \TC}
Let $n,m,k$ be given non-negative integers. 
The number of oscillating tableaux
of length $n$ with at most $k$ columns,
starting at $\emptyset$ and ending at the one-column shape $(1^m)$,
is equal to the number of standard Young tableaux of size~$n$
with $m$ columns of odd length, all columns of length at most $2k$.
\endproclaim

\demo{Proof}
We start with a standard Young tableau $T$ of size $n$ with at most $2k$ rows
and with $m$ columns of odd length. As a running example, we choose
$$
\matrix 1&3&4&8\\
2&6&7\\
5&10\\
9&12\\
11\endmatrix
$$
with $n=12$, $k=3$, and $m=2$. Indeed, this standard Young tableau has
$12$ entries, it has less than
or equal to $2k=6$ rows (namely~$5$) and $2$ columns of odd length.

\medskip
{\smc Step 1}. At the end of the odd-length columns, 
we put $I$, $II$, $III$, \dots,
from left to right. In our running example, we obtain
$$
\matrix 1&3&4&8\\
2&6&7&II\\
5&10\\
9&12\\
11\\
I\endmatrix
$$
We slide $I$, $II$, $III$, \dots, in this order, to the top-left of
the tableau, using (inverse) jeu de taquin (cf.\ \cite{\SagaAQ,
Sec.~3.7}).
That is, as long as above $I$
we find an entry belonging to $\{1,2,\dots,n\}$, we interchange $I$
with this entry; then, as long as to the left of or above $II$
we find entries belonging to $\{1,2,\dots,n\}$, we interchange $II$
with the larger of the two entries; then we do the same with $III$,
$IV$, etc. In the end, we obtain the
standard tableau $T'$ in the alphabet $I,II,III,\dots,1,2,\dots$.
In our running example, we get
$$
\matrix I&II&3&4\\
1&6&7&8\\
2&10\\
5&12\\
9\\
11\endmatrix
$$
It should be observed that, necessarily, $I$, $II$, $III$, \dots\
come to rest in the first row, in this order. The reason is
that successive jeu de taquin paths cannot cross each other, of which
one can easily convince oneself. More precisely, 
the jeu de taquin path of $I$ has to stay (weakly) to the left of the path
of~$II$, but strictly to the left along vertical pieces, the same
being true for the jeu de taquin paths of $II$ and $III$, etc.

\medskip
{\smc Step 2}. We interpret the tableau $T'$ as a sequence of
partitions 
$\emptyset=\la^0\subseteq\la^1\subseteq\dots\subseteq\la^{n+m}=\la$,
as described in Section~\SB. The partitions are placed along the
corners of the upper boundary of an $(n+m)\times(n+m)$ square
cell arrangement from right to left, 
and along the left boundary from bottom to top.
Then we apply the inverse growth diagram algorithm described in
Section~\SB, however, not in direction bottom/left but instead in direction
bottom/right. For the result in our running example see Figure~\FD.
\footnote{Alternatively, we could have applied
the inverse Robinson--Schensted algorithm to
the tableau pair $(T',T')$. This yields an involution
(since we started with a tableau pair consisting of two identical
tableaux) on $I,II,III,\dots,1,2,\dots$.
In our running example, we obtain the involution
$$
(I,5)(II,11)(1,9)(2,6)(3,7)(4,12)(8,10).
$$
We represent this involution as a 0-1-filling of a square,
where we label the rows $I,II,III,\dots,1,2,\dots$ from bottom to
top, and columns by the same labels from right to left
(skipping unconcerned labels). In our running example, this leads
to the $0$-$1$-filling in Figure~\FD\ (with $X$'s representing the $1$'s, while
empty cells represent the $0$'s). That this is indeed equivalent is
due to the fact (cf.\ \cite{\BrFoAA, pp.~95--98},
\cite{\StanBI, Theorem~7.13.5})
that the bijection between permutations and pairs of standard tableaux
defined by the growth diagram on the square coincides with
the Robinson--Schensted correspondence.}
In the figure, we have ``separated" the rows and columns corresponding
to the ``extra" letters $I$ and $II$ by thick lines.

\midinsert
$$
\Einheit.3cm
\Pfad(0,0),111111111111111111111111111111111111111111\endPfad
\Pfad(0,3),111111111111111111111111111111111111111111\endPfad
\Pfad(0,9),111111111111111111111111111111111111111111\endPfad
\Pfad(0,12),111111111111111111111111111111111111111111\endPfad
\Pfad(0,15),111111111111111111111111111111111111111111\endPfad
\Pfad(0,18),111111111111111111111111111111111111111111\endPfad
\Pfad(0,21),111111111111111111111111111111111111111111\endPfad
\Pfad(0,24),111111111111111111111111111111111111111111\endPfad
\Pfad(0,27),111111111111111111111111111111111111111111\endPfad
\Pfad(0,30),111111111111111111111111111111111111111111\endPfad
\Pfad(0,33),111111111111111111111111111111111111111111\endPfad
\Pfad(0,36),111111111111111111111111111111111111111111\endPfad
\Pfad(0,39),111111111111111111111111111111111111111111\endPfad
\Pfad(0,42),111111111111111111111111111111111111111111\endPfad
\Pfad(0,0),222222222222222222222222222222222222222222\endPfad
\Pfad(3,0),222222222222222222222222222222222222222222\endPfad
\Pfad(6,0),222222222222222222222222222222222222222222\endPfad
\Pfad(9,0),222222222222222222222222222222222222222222\endPfad
\Pfad(12,0),222222222222222222222222222222222222222222\endPfad
\Pfad(15,0),222222222222222222222222222222222222222222\endPfad
\Pfad(18,0),222222222222222222222222222222222222222222\endPfad
\Pfad(21,0),222222222222222222222222222222222222222222\endPfad
\Pfad(24,0),222222222222222222222222222222222222222222\endPfad
\Pfad(27,0),222222222222222222222222222222222222222222\endPfad
\Pfad(30,0),222222222222222222222222222222222222222222\endPfad
\Pfad(33,0),222222222222222222222222222222222222222222\endPfad
\Pfad(39,0),222222222222222222222222222222222222222222\endPfad
\Pfad(42,0),222222222222222222222222222222222222222222\endPfad
%
\PfadDicke{2pt}
\Pfad(0,6),111111111111111111111111111111111111111111\endPfad
\Pfad(36,0),222222222222222222222222222222222222222222\endPfad
%
\Label\ro{\text {\seventeenpoint X}}(22,1)
\Label\ro{\text {\seventeenpoint X}}(4,4)
\Label\ro{\text {\seventeenpoint X}}(10,7)
\Label\ro{\text {\seventeenpoint X}}(19,10)
\Label\ro{\text {\seventeenpoint X}}(16,13)
\Label\ro{\text {\seventeenpoint X}}(1,16)
\Label\ro{\text {\seventeenpoint X}}(40,19)
\Label\ro{\text {\seventeenpoint X}}(31,22)
\Label\ro{\text {\seventeenpoint X}}(28,25)
\Label\ro{\text {\seventeenpoint X}}(7,28)
\Label\ro{\text {\seventeenpoint X}}(34,31)
\Label\ro{\text {\seventeenpoint X}}(13,34)
\Label\ro{\text {\seventeenpoint X}}(37,37)
\Label\ro{\text {\seventeenpoint X}}(25,40)
%
\Label\u{\eightpoint\emptyset}(0,0)
\Label\u{\eightpoint\emptyset}(3,0)
\Label\u{\eightpoint\emptyset}(6,0)
\Label\u{\eightpoint\emptyset}(9,0)
\Label\u{\eightpoint\emptyset}(12,0)
\Label\u{\eightpoint\emptyset}(15,0)
\Label\u{\eightpoint\emptyset}(18,0)
\Label\u{\eightpoint\emptyset}(21,0)
\Label\u{\eightpoint\emptyset}(24,0)
\Label\u{\eightpoint\emptyset}(27,0)
\Label\u{\eightpoint\emptyset}(30,0)
\Label\u{\eightpoint\emptyset}(33,0)
\Label\u{\eightpoint\emptyset}(36,0)
\Label\u{\eightpoint\emptyset}(39,0)
\Label\ru{\eightpoint\emptyset}(42,0)
\Label\r{\eightpoint\emptyset}(42,3)
\Label\r{\eightpoint\emptyset}(42,6)
\Label\r{\eightpoint\emptyset}(42,9)
\Label\r{\eightpoint\emptyset}(42,12)
\Label\r{\eightpoint\emptyset}(42,15)
\Label\r{\eightpoint\emptyset}(42,18)
\Label\r{\eightpoint\emptyset}(42,21)
\Label\r{\eightpoint\emptyset}(42,24)
\Label\r{\eightpoint\emptyset}(42,27)
\Label\r{\eightpoint\emptyset}(42,30)
\Label\r{\eightpoint\emptyset}(42,33)
\Label\r{\eightpoint\emptyset}(42,36)
\Label\r{\eightpoint\emptyset}(42,39)
\Label\r{\eightpoint\emptyset}(42,42)
%
\Label\lo{\eightpoint\emptyset}(39,3)
\Label\lo{\eightpoint\emptyset}(36,3)
\Label\lo{\eightpoint\emptyset}(33,3)
\Label\lo{\eightpoint\emptyset}(30,3)
\Label\lo{\eightpoint\emptyset}(27,3)
\Label\lo{\eightpoint\emptyset}(24,3)
\Label\lo{\eightpoint1}(21,3)
\Label\lo{\eightpoint1}(18,3)
\Label\lo{\eightpoint1}(15,3)
\Label\lo{\eightpoint1}(12,3)
\Label\lo{\eightpoint1}(9,3)
\Label\lo{\eightpoint1}(6,3)
\Label\lo{\eightpoint1}(3,3)
\Label\lo{\eightpoint1}(0,3)
%
\Label\lo{\eightpoint\emptyset}(39,6)
\Label\lo{\eightpoint\emptyset}(36,6)
\Label\lo{\eightpoint\emptyset}(33,6)
\Label\lo{\eightpoint\emptyset}(30,6)
\Label\lo{\eightpoint\emptyset}(27,6)
\Label\lo{\eightpoint\emptyset}(24,6)
\Label\lo{\eightpoint1}(21,6)
\Label\lo{\eightpoint1}(18,6)
\Label\lo{\eightpoint1}(15,6)
\Label\lo{\eightpoint1}(12,6)
\Label\lo{\eightpoint1}(9,6)
\Label\lo{\eightpoint1}(6,6)
\Label\lo{\eightpoint2}(3,6)
\Label\lo{\eightpoint2}(0,6)
%
\Label\lo{\eightpoint\emptyset}(39,9)
\Label\lo{\eightpoint\emptyset}(36,9)
\Label\lo{\eightpoint\emptyset}(33,9)
\Label\lo{\eightpoint\emptyset}(30,9)
\Label\lo{\eightpoint\emptyset}(27,9)
\Label\lo{\eightpoint\emptyset}(24,9)
\Label\lo{\eightpoint1}(21,9)
\Label\lo{\eightpoint1}(18,9)
\Label\lo{\eightpoint1}(15,9)
\Label\lo{\eightpoint1}(12,9)
\Label\lo{\eightpoint2}(9,9)
\Label\lo{\eightpoint2}(6,9)
\Label\lo{\eightpoint21\ }(3,9)
\Label\lo{\eightpoint21\ }(0,9)
%
\Label\lo{\eightpoint\emptyset}(39,12)
\Label\lo{\eightpoint\emptyset}(36,12)
\Label\lo{\eightpoint\emptyset}(33,12)
\Label\lo{\eightpoint\emptyset}(30,12)
\Label\lo{\eightpoint\emptyset}(27,12)
\Label\lo{\eightpoint\emptyset}(24,12)
\Label\lo{\eightpoint1}(21,12)
\Label\lo{\eightpoint2}(18,12)
\Label\lo{\eightpoint2}(15,12)
\Label\lo{\eightpoint2}(12,12)
\Label\lo{\eightpoint21\ }(9,12)
\Label\lo{\eightpoint21\ }(6,12)
\Label\lo{\eightpoint211\ \ }(3,12)
\Label\lo{\eightpoint211\ \ }(0,12)
%
\Label\lo{\eightpoint\emptyset}(39,15)
\Label\lo{\eightpoint\emptyset}(36,15)
\Label\lo{\eightpoint\emptyset}(33,15)
\Label\lo{\eightpoint\emptyset}(30,15)
\Label\lo{\eightpoint\emptyset}(27,15)
\Label\lo{\eightpoint\emptyset}(24,15)
\Label\lo{\eightpoint1}(21,15)
\Label\lo{\eightpoint2}(18,15)
\Label\lo{\eightpoint3}(15,15)
\Label\lo{\eightpoint3}(12,15)
\Label\lo{\eightpoint31\ }(9,15)
\Label\lo{\eightpoint31\ }(6,15)
\Label\lo{\eightpoint311\ \ }(3,15)
\Label\lo{\eightpoint311\ \ }(0,15)
%
\Label\lo{\eightpoint\emptyset}(39,18)
\Label\lo{\eightpoint\emptyset}(36,18)
\Label\lo{\eightpoint\emptyset}(33,18)
\Label\lo{\eightpoint\emptyset}(30,18)
\Label\lo{\eightpoint\emptyset}(27,18)
\Label\lo{\eightpoint\emptyset}(24,18)
\Label\lo{\eightpoint1}(21,18)
\Label\lo{\eightpoint2}(18,18)
\Label\lo{\eightpoint3}(15,18)
\Label\lo{\eightpoint3}(12,18)
\Label\lo{\eightpoint31\ }(9,18)
\Label\lo{\eightpoint31\ }(6,18)
\Label\lo{\eightpoint311\ \ }(3,18)
\Label\lo{\eightpoint411\ \ }(0,18)
%
\Label\lo{\eightpoint1}(39,21)
\Label\lo{\eightpoint1}(36,21)
\Label\lo{\eightpoint1}(33,21)
\Label\lo{\eightpoint1}(30,21)
\Label\lo{\eightpoint1}(27,21)
\Label\lo{\eightpoint1}(24,21)
\Label\lo{\eightpoint11\ }(21,21)
\Label\lo{\eightpoint21\ }(18,21)
\Label\lo{\eightpoint31\ }(15,21)
\Label\lo{\eightpoint31\ }(12,21)
\Label\lo{\eightpoint311\ \ }(9,21)
\Label\lo{\eightpoint311\ \ }(6,21)
\Label\lo{\eightpoint3111\ \,\ \ }(3,21)
\Label\lo{\eightpoint4111\ \,\ \ }(0,21)
%
\Label\lo{\eightpoint1}(39,24)
\Label\lo{\eightpoint1}(36,24)
\Label\lo{\eightpoint1}(33,24)
\Label\lo{\eightpoint2}(30,24)
\Label\lo{\eightpoint2}(27,24)
\Label\lo{\eightpoint2}(24,24)
\Label\lo{\eightpoint21\ }(21,24)
\Label\lo{\eightpoint22\ }(18,24)
\Label\lo{\eightpoint32\ }(15,24)
\Label\lo{\eightpoint32\ }(12,24)
\Label\lo{\eightpoint321\ \ }(9,24)
\Label\lo{\eightpoint321\ \ }(6,24)
\Label\lo{\eightpoint3211\ \,\ \ }(3,24)
\Label\lo{\eightpoint4211\ \,\ \ }(0,24)
%
\Label\lo{\eightpoint1}(39,27)
\Label\lo{\eightpoint1}(36,27)
\Label\lo{\eightpoint1}(33,27)
\Label\lo{\eightpoint2}(30,27)
\Label\lo{\eightpoint3}(27,27)
\Label\lo{\eightpoint3}(24,27)
\Label\lo{\eightpoint31\ }(21,27)
\Label\lo{\eightpoint32\ }(18,27)
\Label\lo{\eightpoint33\ }(15,27)
\Label\lo{\eightpoint33\ }(12,27)
\Label\lo{\eightpoint331\ \ }(9,27)
\Label\lo{\eightpoint331\ \ }(6,27)
\Label\lo{\eightpoint3311\ \,\ \ }(3,27)
\Label\lo{\eightpoint4311\ \,\ \ }(0,27)
%
\Label\lo{\eightpoint1}(39,30)
\Label\lo{\eightpoint1}(36,30)
\Label\lo{\eightpoint1}(33,30)
\Label\lo{\eightpoint2}(30,30)
\Label\lo{\eightpoint3}(27,30)
\Label\lo{\eightpoint3}(24,30)
\Label\lo{\eightpoint31\ }(21,30)
\Label\lo{\eightpoint32\ }(18,30)
\Label\lo{\eightpoint33\ }(15,30)
\Label\lo{\eightpoint33\ }(12,30)
\Label\lo{\eightpoint331\ \ }(9,30)
\Label\lo{\eightpoint431\ \ }(6,30)
\Label\lo{\eightpoint4311\ \,\ \ }(3,30)
\Label\lo{\eightpoint4411\ \,\ \ }(0,30)
%
\Label\lo{\eightpoint1}(39,33)
\Label\lo{\eightpoint1}(36,33)
\Label\lo{\eightpoint2}(33,33)
\Label\lo{\eightpoint21\ }(30,33)
\Label\lo{\eightpoint31\ }(27,33)
\Label\lo{\eightpoint31\ }(24,33)
\Label\lo{\eightpoint311\ \ }(21,33)
\Label\lo{\eightpoint321\ \ }(18,33)
\Label\lo{\eightpoint331\ \ }(15,33)
\Label\lo{\eightpoint331\ \ }(12,33)
\Label\lo{\eightpoint3311\ \,\ \ }(9,33)
\Label\lo{\eightpoint4311\ \,\ \ }(6,33)
\Label\lo{\eightpoint43111\ \ \,\ \ }(3,33)
\Label\lo{\eightpoint44111\ \ \,\ \ }(0,33)
%
\Label\lo{\eightpoint1}(39,36)
\Label\lo{\eightpoint1}(36,36)
\Label\lo{\eightpoint2}(33,36)
\Label\lo{\eightpoint21\ }(30,36)
\Label\lo{\eightpoint31\ }(27,36)
\Label\lo{\eightpoint31\ }(24,36)
\Label\lo{\eightpoint311\ \ }(21,36)
\Label\lo{\eightpoint321\ \ }(18,36)
\Label\lo{\eightpoint331\ \ }(15,36)
\Label\lo{\eightpoint431\ \ }(12,36)
\Label\lo{\eightpoint4311\ \,\ \ }(9,36)
\Label\lo{\eightpoint4411\ \,\ \ }(6,36)
\Label\lo{\eightpoint44111\ \ \,\ \ }(3,36)
\Label\lo{\eightpoint44211\ \ \,\ \ }(0,36)
%
\Label\lo{\eightpoint1}(39,39)
\Label\lo{\eightpoint2}(36,39)
\Label\lo{\eightpoint21\ }(33,39)
\Label\lo{\eightpoint211\ \ }(30,39)
\Label\lo{\eightpoint311\ \ }(27,39)
\Label\lo{\eightpoint311\ \ }(24,39)
\Label\lo{\eightpoint3111\ \,\ \ }(21,39)
\Label\lo{\eightpoint3211\ \,\ \ }(18,39)
\Label\lo{\eightpoint3311\ \,\ \ }(15,39)
\Label\lo{\eightpoint4311\ \,\ \ }(12,39)
\Label\lo{\eightpoint43111\ \ \,\ \ }(9,39)
\Label\lo{\eightpoint44111\ \ \,\ \ }(6,39)
\Label\lo{\eightpoint441111\ \,\ \ \,\ \ }(3,39)
\Label\lo{\eightpoint442111\ \,\ \ \,\ \ }(0,39)
%
\Label\lo{\eightpoint1}(39,42)
\Label\lo{\eightpoint2}(36,42)
\Label\lo{\eightpoint21\ }(33,42)
\Label\lo{\eightpoint211\ \ }(30,42)
\Label\lo{\eightpoint311\ \ }(27,42)
\Label\lo{\eightpoint411\ \ }(24,42)
\Label\lo{\eightpoint4111\ \,\ \ }(21,42)
\Label\lo{\eightpoint4211\ \,\ \ }(18,42)
\Label\lo{\eightpoint4311\ \,\ \ }(15,42)
\Label\lo{\eightpoint4411\ \,\ \ }(12,42)
\Label\lo{\eightpoint44111\ \ \,\ \ }(9,42)
\Label\lo{\eightpoint44211\ \ \,\ \ }(6,42)
\Label\lo{\eightpoint442111\ \,\ \ \,\ \ }(3,42)
\Label\lo{\eightpoint442211\ \,\ \ \,\ \ }(0,42)
\hskip12.3cm
$$
\vskip10pt
\centerline{\smc Figure \FD}
\endinsert

Clearly, the growth diagram is symmetric with respect
to the main diagonal (i.e., the top/left--bottom/right diagonal). Furthermore,
by Greene's theorem, the lengths of north-east chains of $1$'s (i.e.,
of X's) are at most $2k$. 
Moreover, again by Greene's theorem (but now using item~(G2)),
since we started with a tableau with all columns of even length, 
there cannot be any crosses along the main diagonal.
(This is a fact observed earlier by Sch\"utzenberger
\cite{\SchuAB, p.~127} in a more general form.)

Finally, since the letters $I,II,III,\dots$ appeared in the
first row of $T'$ in that order, the $X$'s in the rows labelled by these
letters (the last rows; in the running example these are the last two rows)
form {\it one} SE-chain. (Also this follows from Greene's theorem.)
Together with the earlier observations that the diagram is symmetric
with respect to the main diagonal and that there are no crosses along
the main diagonal, it follows that the region
below the thick horizontal line and to the right of the thick vertical
horizontal line does not contain any crosses.

\medskip
{\smc Step 3}. Since the diagram is symmetric without crosses on the main
diagonal, we may forget about one half of the diagram, say the upper
half (including the main diagonal). 
In our running example, we arrive at the filling
of the staircase diagram displayed in
Figure~\FE.

\midinsert
$$
\Einheit.3cm
\Pfad(0,0),111111111111111111111111111111111111111111\endPfad
\Pfad(0,3),111111111111111111111111111111111111111\endPfad
\Pfad(0,9),111111111111111111111111111111111\endPfad
\Pfad(0,12),111111111111111111111111111111\endPfad
\Pfad(0,15),111111111111111111111111111\endPfad
\Pfad(0,18),111111111111111111111111\endPfad
\Pfad(0,21),111111111111111111111\endPfad
\Pfad(0,24),111111111111111111\endPfad
\Pfad(0,27),111111111111111\endPfad
\Pfad(0,30),111111111111\endPfad
\Pfad(0,33),111111111\endPfad
\Pfad(0,36),111111\endPfad
\Pfad(0,39),111\endPfad
\Pfad(0,0),222222222222222222222222222222222222222222\endPfad
\Pfad(3,0),222222222222222222222222222222222222222\endPfad
\Pfad(6,0),222222222222222222222222222222222222\endPfad
\Pfad(9,0),222222222222222222222222222222222\endPfad
\Pfad(12,0),222222222222222222222222222222\endPfad
\Pfad(15,0),222222222222222222222222222\endPfad
\Pfad(18,0),222222222222222222222222\endPfad
\Pfad(21,0),222222222222222222222\endPfad
\Pfad(24,0),222222222222222222\endPfad
\Pfad(27,0),222222222222222\endPfad
\Pfad(30,0),222222222222\endPfad
\Pfad(33,0),222222222\endPfad
\Pfad(39,0),222\endPfad
%
\PfadDicke{2pt}
\Pfad(0,6),111111111111111111111111111111111111\endPfad
\Pfad(36,0),222222\endPfad
%
\Label\ro{\text {\seventeenpoint X}}(22,1)
\Label\ro{\text {\seventeenpoint X}}(4,4)
\Label\ro{\text {\seventeenpoint X}}(10,7)
\Label\ro{\text {\seventeenpoint X}}(19,10)
\Label\ro{\text {\seventeenpoint X}}(16,13)
\Label\ro{\text {\seventeenpoint X}}(1,16)
%\Label\ro{\text {\seventeenpoint X}}(40,19)
%\Label\ro{\text {\seventeenpoint X}}(31,22)
%\Label\ro{\text {\seventeenpoint X}}(28,25)
\Label\ro{\text {\seventeenpoint X}}(7,28)
%\Label\ro{\text {\seventeenpoint X}}(34,31)
%\Label\ro{\text {\seventeenpoint X}}(13,34)
%\Label\ro{\text {\seventeenpoint X}}(37,37)
%\Label\ro{\text {\seventeenpoint X}}(25,40)
\hskip12.3cm
$$
\vskip10pt
\centerline{\smc Figure \FE}
\endinsert

Now we place empty partitions along the corners of the left and
the bottom boundary of the staircase diagram.
To the resulting diagram we apply the (forward) growth diagram construction
as described in Section~\SB, here in direction top/right.
Figure~\FF\ shows the result in our running example.

\vskip10pt
$$
\Einheit.3cm
\Pfad(0,0),111111111111111111111111111111111111111111\endPfad
\Pfad(0,3),111111111111111111111111111111111111111\endPfad
\Pfad(0,9),111111111111111111111111111111111\endPfad
\Pfad(0,12),111111111111111111111111111111\endPfad
\Pfad(0,15),111111111111111111111111111\endPfad
\Pfad(0,18),111111111111111111111111\endPfad
\Pfad(0,21),111111111111111111111\endPfad
\Pfad(0,24),111111111111111111\endPfad
\Pfad(0,27),111111111111111\endPfad
\Pfad(0,30),111111111111\endPfad
\Pfad(0,33),111111111\endPfad
\Pfad(0,36),111111\endPfad
\Pfad(0,39),111\endPfad
\Pfad(0,0),222222222222222222222222222222222222222222\endPfad
\Pfad(3,0),222222222222222222222222222222222222222\endPfad
\Pfad(6,0),222222222222222222222222222222222222\endPfad
\Pfad(9,0),222222222222222222222222222222222\endPfad
\Pfad(12,0),222222222222222222222222222222\endPfad
\Pfad(15,0),222222222222222222222222222\endPfad
\Pfad(18,0),222222222222222222222222\endPfad
\Pfad(21,0),222222222222222222222\endPfad
\Pfad(24,0),222222222222222222\endPfad
\Pfad(27,0),222222222222222\endPfad
\Pfad(30,0),222222222222\endPfad
\Pfad(33,0),222222222\endPfad
\Pfad(39,0),222\endPfad
%
\PfadDicke{2pt}
\Pfad(0,6),111111111111111111111111111111111111\endPfad
\Pfad(36,0),222222\endPfad
%
\Label\ro{\text {\seventeenpoint X}}(22,1)
\Label\ro{\text {\seventeenpoint X}}(4,4)
\Label\ro{\text {\seventeenpoint X}}(10,7)
\Label\ro{\text {\seventeenpoint X}}(19,10)
\Label\ro{\text {\seventeenpoint X}}(16,13)
\Label\ro{\text {\seventeenpoint X}}(1,16)
%\Label\ro{\text {\seventeenpoint X}}(40,19)
%\Label\ro{\text {\seventeenpoint X}}(31,22)
%\Label\ro{\text {\seventeenpoint X}}(28,25)
\Label\ro{\text {\seventeenpoint X}}(7,28)
%\Label\ro{\text {\seventeenpoint X}}(34,31)
%\Label\ro{\text {\seventeenpoint X}}(13,34)
%\Label\ro{\text {\seventeenpoint X}}(37,37)
%\Label\ro{\text {\seventeenpoint X}}(25,40)
\Label\u{\eightpoint\emptyset}(0,0)
\Label\u{\eightpoint\emptyset}(3,0)
\Label\u{\eightpoint\emptyset}(6,0)
\Label\u{\eightpoint\emptyset}(9,0)
\Label\u{\eightpoint\emptyset}(12,0)
\Label\u{\eightpoint\emptyset}(15,0)
\Label\u{\eightpoint\emptyset}(18,0)
\Label\u{\eightpoint\emptyset}(21,0)
\Label\u{\eightpoint\emptyset}(24,0)
\Label\u{\eightpoint\emptyset}(27,0)
\Label\u{\eightpoint\emptyset}(30,0)
\Label\u{\eightpoint\emptyset}(33,0)
\Label\u{\eightpoint\emptyset}(36,0)
\Label\u{\eightpoint\emptyset}(39,0)
\Label\u{\eightpoint\emptyset}(42,0)
\Label\l{\eightpoint\emptyset}(0,3)
\Label\l{\eightpoint\emptyset}(0,6)
\Label\l{\eightpoint\emptyset}(0,9)
\Label\l{\eightpoint\emptyset}(0,12)
\Label\l{\eightpoint\emptyset}(0,15)
\Label\l{\eightpoint\emptyset}(0,18)
\Label\l{\eightpoint\emptyset}(0,21)
\Label\l{\eightpoint\emptyset}(0,24)
\Label\l{\eightpoint\emptyset}(0,27)
\Label\l{\eightpoint\emptyset}(0,30)
\Label\l{\eightpoint\emptyset}(0,33)
\Label\l{\eightpoint\emptyset}(0,36)
\Label\l{\eightpoint\emptyset}(0,39)
\Label\l{\eightpoint\emptyset}(0,42)
%
\Label\ro{\eightpoint\emptyset}(3,3)
\Label\ro{\eightpoint\emptyset}(6,3)
\Label\ro{\eightpoint\emptyset}(9,3)
\Label\ro{\eightpoint\emptyset}(12,3)
\Label\ro{\eightpoint\emptyset}(15,3)
\Label\ro{\eightpoint\emptyset}(18,3)
\Label\ro{\eightpoint\emptyset}(21,3)
\Label\ro{\eightpoint1}(24,3)
\Label\ro{\eightpoint1}(27,3)
\Label\ro{\eightpoint1}(30,3)
\Label\ro{\eightpoint1}(33,3)
\Label\ro{\eightpoint1}(36,3)
%
\Label\ro{\eightpoint\emptyset}(3,6)
\Label\ro{\eightpoint1}(6,6)
\Label\ro{\eightpoint1}(9,6)
\Label\ro{\eightpoint1}(12,6)
\Label\ro{\eightpoint1}(15,6)
\Label\ro{\eightpoint1}(18,6)
\Label\ro{\eightpoint1}(21,6)
\Label\ro{\eightpoint11}(24,6)
\Label\ro{\eightpoint11}(27,6)
\Label\ro{\eightpoint11}(30,6)
\Label\ro{\eightpoint11}(33,6)
%
\Label\ro{\eightpoint\emptyset}(3,9)
\Label\ro{\eightpoint1}(6,9)
\Label\ro{\eightpoint1}(9,9)
\Label\ro{\eightpoint2}(12,9)
\Label\ro{\eightpoint2}(15,9)
\Label\ro{\eightpoint2}(18,9)
\Label\ro{\eightpoint2}(21,9)
\Label\ro{\eightpoint21}(24,9)
\Label\ro{\eightpoint21}(27,9)
\Label\ro{\eightpoint21}(30,9)
%
\Label\ro{\eightpoint\emptyset}(3,12)
\Label\ro{\eightpoint1}(6,12)
\Label\ro{\eightpoint1}(9,12)
\Label\ro{\eightpoint2}(12,12)
\Label\ro{\eightpoint2}(15,12)
\Label\ro{\eightpoint2}(18,12)
\Label\ro{\eightpoint3}(21,12)
\Label\ro{\eightpoint31}(24,12)
\Label\ro{\eightpoint31}(27,12)
%
\Label\ro{\eightpoint\emptyset}(3,15)
\Label\ro{\eightpoint1}(6,15)
\Label\ro{\eightpoint1}(9,15)
\Label\ro{\eightpoint2}(12,15)
\Label\ro{\eightpoint2}(15,15)
\Label\ro{\eightpoint3}(18,15)
\Label\ro{\eightpoint31}(21,15)
\Label\ro{\eightpoint\ \ 311}(24,15)
%
\Label\ro{\eightpoint1}(3,18)
\Label\ro{\eightpoint11}(6,18)
\Label\ro{\eightpoint11}(9,18)
\Label\ro{\eightpoint21}(12,18)
\Label\ro{\eightpoint21}(15,18)
\Label\ro{\eightpoint31}(18,18)
\Label\ro{\eightpoint\ \ 311}(21,18)
%
\Label\ro{\eightpoint1}(3,21)
\Label\ro{\eightpoint11}(6,21)
\Label\ro{\eightpoint11}(9,21)
\Label\ro{\eightpoint21}(12,21)
\Label\ro{\eightpoint21}(15,21)
\Label\ro{\eightpoint31}(18,21)
%
\Label\ro{\eightpoint1}(3,24)
\Label\ro{\eightpoint11}(6,24)
\Label\ro{\eightpoint11}(9,24)
\Label\ro{\eightpoint21}(12,24)
\Label\ro{\eightpoint21}(15,24)
%
\Label\ro{\eightpoint1}(3,27)
\Label\ro{\eightpoint11}(6,27)
\Label\ro{\eightpoint11}(9,27)
\Label\ro{\eightpoint21}(12,27)
%
\Label\ro{\eightpoint1}(3,30)
\Label\ro{\eightpoint11}(6,30)
\Label\ro{\eightpoint21}(9,30)
%
\Label\ro{\eightpoint1}(3,33)
\Label\ro{\eightpoint11}(6,33)
%
\Label\ro{\eightpoint1}(3,36)
%
\Label\ro{1}(3,39)
\Label\ro{11}(6,36)
\Label\ro{21}(9,33)
\Label\ro{22}(12,30)
\Label\ro{21}(15,27)
\Label\ro{31}(18,24)
\Label\ro{311}(21,21)
\Label\ro{3111}(24,18)
\Label\ro{311}(27,15)
\Label\ro{31}(30,12)
\Label\ro{21}(33,9)
\Label\ro{11}(36,6)
\Label\ro{1}(39,3)
\hskip13.1cm
$$
\vskip10pt
\centerline{\smc Figure \FF}
\vskip10pt

Along the corners on the main diagonal one reads an
oscillating tableau of length $n+m$. (In the running example in
Figure~\FF, this is the sequence of larger printed partitions.) 
However, since by one of the
previous observations (plus Greene's theorem) we know that the
last $m+1$ partitions (shapes) in the oscillating tableau will be
$(1^m),(1^{m-1}),(1^{m-2}),\dots,(1,1),(1),\emptyset$, we may discard all of
them except $(1^m)$, and in this way
obtain an oscillating tableau of length $n$, starting at $\emptyset$
and ending at $(1^m)$. Using Greene's theorem once more, we also see
that no shape along the main diagonal can have more than $k$ columns.

\medskip
Since every step in this construction can be reversed
in straightforward fashion, this yields the desired bijection.
\quad \quad \qed 
\enddemo

The announced ``Knuth-type" extension of Theorem~\TC\ is the following.

\proclaim{Theorem \TD}
Let $n,m,k$ and $j_1,j_2,\dots,j_n$ be non-negative integers.
The number of sequences of partitions
$\emptyset=\la^0,\la^1,\dots,\la^{2n}=(1^m)$
of length $2n$, with $\la^{2i-2}\supseteq\la^{2i-1}$ and
$\la^{2i-1}\subseteq\la^{2i}$ for $i=1,2,\dots,n$,
where each pair $(\la^{i-1},\la^i)$ differs by a vertical strip
{\rm(}that is, by a collection of cells which contains at most one  
cell in each row{\rm)}, $i=1,2,\dots,n$, 
where each partition $\la^i$ has at most $k$ columns,
and where 
$\vert\la^{2i-2}\vert-2\vert\la^{2i-1}\vert+\vert\la^{2i}\vert=j_{n-i+1}$
{\rm(}the left-hand side is the sum of the differences in sizes of
$(\la^{2i-2},\la^{2i-1})$ and of $(\la^{2i-1},\la^{2i})${\rm)},
$i=1,2,\dots,n$,
is equal to the number of semistandard tableaux with $j_i$ entries~$i$,
$i=1,2,\dots,n$,
with $m$ columns of odd length, all columns of length at most $2k$.
\endproclaim

\remark{Remark}
Theorem~\TC\ is the special case of Theorem~\TD\ where
$j_1=j_2=\dots=j_n=1$.
\endremark

\demo{Sketch of proof}
One proceeds in analogy with the proof of Theorem~\TC.
As a running example for illustration, we choose $n=4$, $m=2$, $k=2$, 
$j_1=5$, 
$j_2=2$, 
$j_3=6$, 
$j_4=3$, 
and the semistandard tableau
$$
\matrix 
1&1&1&1&1&3&3\\
2&2&3&3&4&4\\
3&3\\
4
\endmatrix
$$
Indeed, this semistandard tableau has $m=2$ columns of odd length,
all columns of length at most $2k=4$, 
$j_1=5$ entries~$1$, 
$j_2=2$ entries~$2$, 
$j_3=6$ entries~$3$, and
$j_4=3$ entries~$4$. 

\medskip
{\smc Step 1}. 
We place $I,II,\dots$ at the end of the columns of odd length,
from left to right. In our running example, we obtain
$$
\matrix 
1&1&1&1&1&3&3\\
2&2&3&3&4&4&II\\
3&3\\
4&I
\endmatrix
$$
Then we slide $I,II,\dots$ up to the first row. The result in our
example is
$$
\matrix 
I&II&1&1&1&3&3\\
1&1&2&3&3&4&4\\
2&3\\
3&4
\endmatrix
$$

\midinsert
$$
\Einheit.3cm
\Pfad(0,0),111111111111111111\endPfad
\Pfad(0,3),111111111111111111\endPfad
\Pfad(0,9),111111111111111111\endPfad
\Pfad(0,12),111111111111111111\endPfad
\Pfad(0,15),111111111111111111\endPfad
\Pfad(0,18),111111111111111111\endPfad
\Pfad(0,0),222222222222222222\endPfad
\Pfad(3,0),222222222222222222\endPfad
\Pfad(6,0),222222222222222222\endPfad
\Pfad(9,0),222222222222222222\endPfad
\Pfad(15,0),222222222222222222\endPfad
\Pfad(18,0),222222222222222222\endPfad
{\PfadDicke{2pt}
\Pfad(0,6),111111111111111111\endPfad
\Pfad(12,0),222222222222222222\endPfad}%
\Label\ro{\text {\seventeenpoint $0$}}(1,1)
\Label\ro{\text {\seventeenpoint $0$}}(4,1)
\Label\ro{\text {\seventeenpoint $0$}}(7,1)
\Label\ro{\text {\seventeenpoint $1$}}(10,1)
\Label\ro{\text {\seventeenpoint $0$}}(13,1)
\Label\ro{\text {\seventeenpoint $0$}}(16,1)
%
\Label\ro{\text {\seventeenpoint $0$}}(1,4)
\Label\ro{\text {\seventeenpoint $1$}}(4,4)
\Label\ro{\text {\seventeenpoint $0$}}(7,4)
\Label\ro{\text {\seventeenpoint $0$}}(10,4)
\Label\ro{\text {\seventeenpoint $0$}}(13,4)
\Label\ro{\text {\seventeenpoint $0$}}(16,4)
%
\Label\ro{\text {\seventeenpoint $1$}}(1,7)
\Label\ro{\text {\seventeenpoint $2$}}(4,7)
\Label\ro{\text {\seventeenpoint $1$}}(7,7)
\Label\ro{\text {\seventeenpoint $0$}}(10,7)
\Label\ro{\text {\seventeenpoint $0$}}(13,7)
\Label\ro{\text {\seventeenpoint $1$}}(16,7)
%
\Label\ro{\text {\seventeenpoint $0$}}(1,10)
\Label\ro{\text {\seventeenpoint $1$}}(4,10)
\Label\ro{\text {\seventeenpoint $0$}}(7,10)
\Label\ro{\text {\seventeenpoint $1$}}(10,10)
\Label\ro{\text {\seventeenpoint $0$}}(13,10)
\Label\ro{\text {\seventeenpoint $0$}}(16,10)
%
\Label\ro{\text {\seventeenpoint $2$}}(1,13)
\Label\ro{\text {\seventeenpoint $0$}}(4,13)
\Label\ro{\text {\seventeenpoint $1$}}(7,13)
\Label\ro{\text {\seventeenpoint $2$}}(10,13)
\Label\ro{\text {\seventeenpoint $1$}}(13,13)
\Label\ro{\text {\seventeenpoint $0$}}(16,13)
%
\Label\ro{\text {\seventeenpoint $0$}}(1,16)
\Label\ro{\text {\seventeenpoint $2$}}(4,16)
\Label\ro{\text {\seventeenpoint $0$}}(7,16)
\Label\ro{\text {\seventeenpoint $1$}}(10,16)
\Label\ro{\text {\seventeenpoint $0$}}(13,16)
\Label\ro{\text {\seventeenpoint $0$}}(16,16)
%
\Label\u{\eightpoint\emptyset}(0,0)
\Label\u{\eightpoint\emptyset}(3,0)
\Label\u{\eightpoint\emptyset}(6,0)
\Label\u{\eightpoint\emptyset}(9,0)
\Label\u{\eightpoint\emptyset}(12,0)
\Label\u{\eightpoint\emptyset}(15,0)
\Label\ru{\eightpoint\emptyset}(18,0)
\Label\r{\eightpoint\emptyset}(18,3)
\Label\r{\eightpoint\emptyset}(18,6)
\Label\r{\eightpoint\emptyset}(18,9)
\Label\r{\eightpoint\emptyset}(18,12)
\Label\r{\eightpoint\emptyset}(18,15)
\Label\r{\eightpoint\emptyset}(18,18)
%
\Label\lo{\eightpoint\emptyset}(15,3)
\Label\lo{\eightpoint\emptyset}(12,3)
\Label\lo{\eightpoint1}(9,3)
\Label\lo{\eightpoint1}(6,3)
\Label\lo{\eightpoint1}(3,3)
\Label\lo{\eightpoint1}(0,3)
%
\Label\lo{\eightpoint\emptyset}(15,6)
\Label\lo{\eightpoint\emptyset}(12,6)
\Label\lo{\eightpoint1}(9,6)
\Label\lo{\eightpoint1}(6,6)
\Label\lo{\eightpoint2}(3,6)
\Label\lo{\eightpoint2}(0,6)
%
\Label\lo{\eightpoint1}(15,9)
\Label\lo{\eightpoint1}(12,9)
\Label\lo{\eightpoint11\ }(9,9)
\Label\lo{\eightpoint21\ }(6,9)
\Label\lo{\eightpoint42\ }(3,9)
\Label\lo{\eightpoint52\ }(0,9)
%
\Label\lo{\eightpoint1}(15,12)
\Label\lo{\eightpoint1}(12,12)
\Label\lo{\eightpoint21\ }(9,12)
\Label\lo{\eightpoint22\ }(6,12)
\Label\lo{\eightpoint521\ \ }(3,12)
\Label\lo{\eightpoint531\ \ }(0,12)
%
\Label\lo{\eightpoint1}(15,15)
\Label\lo{\eightpoint2}(12,15)
\Label\lo{\eightpoint42\ }(9,15)
\Label\lo{\eightpoint521\ \ }(6,15)
\Label\lo{\eightpoint5511\ \,\ \ }(3,15)
\Label\lo{\eightpoint7521\ \,\ \ }(0,15)
%
\Label\lo{\eightpoint1}(15,18)
\Label\lo{\eightpoint2}(12,18)
\Label\lo{\eightpoint52\ }(9,18)
\Label\lo{\eightpoint531\ \ }(6,18)
\Label\lo{\eightpoint7521\ \,\ \ }(3,18)
\Label\lo{\eightpoint7722\ \,\ \ }(0,18)
\hbox{\hskip7.0cm}
\Pfad(0,0),111111111111111111\endPfad
\Pfad(0,3),111111111111111\endPfad
\Pfad(0,9),111111111\endPfad
\Pfad(0,12),111111\endPfad
\Pfad(0,15),111\endPfad
\Pfad(0,0),222222222222222222\endPfad
\Pfad(3,0),222222222222222\endPfad
\Pfad(6,0),222222222222\endPfad
\Pfad(9,0),222222222\endPfad
\Pfad(15,0),222\endPfad
{\PfadDicke{2pt}
\Pfad(0,6),111111111111\endPfad
\Pfad(12,0),222222\endPfad}%
\Label\ro{\text {\seventeenpoint $0$}}(1,1)
\Label\ro{\text {\seventeenpoint $0$}}(4,1)
\Label\ro{\text {\seventeenpoint $0$}}(7,1)
\Label\ro{\text {\seventeenpoint $1$}}(10,1)
\Label\ro{\text {\seventeenpoint $0$}}(13,1)
%
\Label\ro{\text {\seventeenpoint $0$}}(1,4)
\Label\ro{\text {\seventeenpoint $1$}}(4,4)
\Label\ro{\text {\seventeenpoint $0$}}(7,4)
\Label\ro{\text {\seventeenpoint $0$}}(10,4)
%
\Label\ro{\text {\seventeenpoint $1$}}(1,7)
\Label\ro{\text {\seventeenpoint $2$}}(4,7)
\Label\ro{\text {\seventeenpoint $1$}}(7,7)
%
\Label\ro{\text {\seventeenpoint $0$}}(1,10)
\Label\ro{\text {\seventeenpoint $1$}}(4,10)
%
\Label\ro{\text {\seventeenpoint $2$}}(1,13)
%
\Label\u{\eightpoint\emptyset}(0,0)
\Label\u{\eightpoint\emptyset}(3,0)
\Label\u{\eightpoint\emptyset}(6,0)
\Label\u{\eightpoint\emptyset}(9,0)
\Label\u{\eightpoint\emptyset}(12,0)
\Label\u{\eightpoint\emptyset}(15,0)
\Label\u{\eightpoint\emptyset}(18,0)
%
\Label\l{\eightpoint\emptyset}(0,3)
\Label\ro{\eightpoint\emptyset}(3,3)
\Label\ro{\eightpoint\emptyset}(6,3)
\Label\ro{\eightpoint\emptyset}(9,3)
\Label\ro{\eightpoint1}(12,3)
\Label\ro{\eightpoint1}(15,3)
%
\Label\l{\eightpoint\emptyset}(0,6)
\Label\ro{\eightpoint\emptyset}(3,6)
\Label\ro{\eightpoint1}(6,6)
\Label\ro{1}(9,6)
\Label\ro{\ 11}(12,6)
%
\Label\l{\eightpoint\emptyset}(0,9)
\Label\ro{\eightpoint1}(3,9)
\Label\ro{\ \ \ \ 1111}(6,9)
\Label\ro{\ \ \ \ 2111}(9,9)
%
\Label\l{\eightpoint\emptyset}(0,12)
\Label\ro{1}(3,12)
\Label\ro{\ \ \ \ 2111}(6,12)
%
\Label\l{\emptyset}(0,15)
\Label\ro{\ \ 111}(3,15)
%
\Label\l{\emptyset}(0,18)
\hskip5.2cm
$$
\vskip10pt
\centerline{\eightpoint a. Second step
\hskip5cm
b. Third step}
\vskip6pt
\centerline{\smc Figure \FG}
\endinsert

\medskip
{\smc Step 2}. 
Instead of applying the (ordinary) inverse growth diagram algorithm,
we apply its Knuth-type extension as described
in \cite{\KratCE, Sec.~4.1} or \cite{\RobyAA, Sec.~4.1}. 
Instead of a symmetric $0$-$1$-filling,
here we obtain a symmetric matrix with non-negative integer entries.
Again, along the diagonal there will be only $0$'s.
Figure~\FG.a shows what we
obtain in our running example.

\medskip
{\smc Step 3}. For the final step, in place of the
(ordinary) growth diagram algorithm, we apply its
Knuth-type extension described in \cite{\KratCE, Sec.~4.4} or
\cite{\LeeuAH, Sec.~3.2}.
The result for our running example is shown in
Figure~\FG.b. To obtain the (generalised) oscillating tableau, we
must read {\it all\/} partitions along the top-right boundary of
the cell arrangement (that is, including those which label ``inner"
corners), again skipping the ones in the region 
to the right of the thick vertical line. 
In Figure~\FG, these are the large printed
partitions, namely
$$
\emptyset,\ 
\emptyset,\
111,\
1,\
2111,\
1111,\
2111,\
1,\
11.
$$
It is not difficult to see that this map has all
the desired properties.
\quad \quad \qed
\enddemo

\subhead 4. Concluding remarks\endsubhead 

\medskip
(1) For both numbers in Theorem~\TC, there are explicit formulae
available. As pointed out in \cite{\BuCFAA, paragraphs around Theorem~19}, 
Gessel and Zeilberger's general result \cite{\GeZeAA} 
on enumeration of lattice paths by means of the reflection principle
yields (see Eq.~(38) in \cite{\GrMrAA}
with $n$ replaced by $k$, $\lambda=(k,k-1,\dots,1)$, and
$\eta=(m+k,k-1,k-2,\dots,1)$) that the number of oscillating
tableaux in Theorem~\TC\ is given by the coefficient of $t^n/n!$ in
$$
\det\left(
I_{i-j+m\cdot\chi(i=k)}(2t)
-
I_{i+j+m\cdot\chi(i=k)}(2t)
\right)_{1\le i,j\le k},
\tag\AA
$$
where $I_\alpha(x)$ is the modified Bessel function of the first kind
$$I_\al(x)=\sum _{\ell=0} ^{\infty}\frac {(x/2)^{2\ell+\al}}
{\ell!\,(\ell+\al)!},
$$
and $\chi(\Cal A)=1$ if $\Cal A$ is true and $\chi(\Cal A)=0$ otherwise.
On the other hand, one obtains the same formula for the number of
standard Young tableaux in Theorem~\TC\ from a result of
Goulden \cite{\GoulAD} (see \cite{\KratBC, Eq.~(3.6)} for a different
proof). Namely, if one extracts the coefficient of 
$x_1x_2\cdots x_n$ in Theorem~2.6 of 
\cite{\GoulAD} with $m$ and $k$ interchanged, and after having applied
the involution $\omega$ on symmetric functions which maps the
complete homogeneous symmetric functions to the elementary symmetric
functions (cf\. \cite{\MacdAC}), 
then the conclusion is that the number of standard Young
tableaux in Theorem~\TC\ is given by the coefficient of $t^n/n!$ in (\AA).
This amounts to an alternative --- albeit very roundabout and involved,
non-illuminating --- computational proof of Theorem~\TC. 
A proof of Theorem~\TD\ along the same lines is also possible.

\medskip
(2) What happens if we want to count standard Young tableaux
of size~$n$ with $m$ columns of odd length, all columns of length at
most $2k+1$ (instead of at most~$2k$)? As it turns out, the
corresponding number equals $\binom nm$ times 
the number of all standard Young tableaux
of size~$n-m$ with {\it all columns of even length not
exceeding~$2k$}. (In other words: the above problem can be reduced
to the $m=0$ case in Theorem~\TC.)
This is seen as follows: 
let $T$ be a standard Young tableau of size~$n$ with $m$ columns of
odd length, all columns of length at most $2k+1$.
To the last entries in the odd columns of $T$ one applies
the inverse mapping of Robinson--Schensted insertion
(cf\. \cite{\SagaAQ, Proof of Theorem~3.1.1}),
starting with the last entry in the right-most odd column, continuing
with the last entry in the (then) right-most odd column, until all
odd columns have disappeared. This produces a standard Young tableau
of size $n-m$ with only even columns, all of which have length at
most~$2k$, and a subset of $\{1,2,\dots,n\}$ of cardinality~$m$.
It is easy to see that all the steps in this mapping can be reversed
so that this describes a bijection. 

\medskip
(3) As indicated in the introduction, the difference between the
bijection proving Theorem~\TC\ presented here and that
of \cite{\BuCFAA} lies in the way one keeps track of 
the parameter~$m$ in Theorem~\TC.
Namely, in Step~1 of our proof of Theorem~\TC, we introduce the auxiliary
letters $I,II,III,\dots$ in order to ``make the $m$ odd columns even,"
and move the letters inside the tableau by jeu de taquin.
Then, in Step~2, we apply the (inverse) growth diagram construction to the
complete square, and finally, in Step~3, we apply the (forward) growth
diagram construction to half of the square to obtain the corresponding
oscillating tableau. 

On the other hand, if one realises the construction in \cite{\BuCFAA}
by means of growth diagrams, then
Burrill, Courtiel, Fusy, Melczer and Mishna apply the (inverse) growth
diagram construction directly, without any ``preprocessing."
The ``price to pay" is that they do obtain X's on the main diagonal.
These $m$ X's must be somehow moved ``into the half-square," and in order to
be able to do this without creating any unwanted chains, the growth
diagram construction has to be first played forth and back on the
half-square. Only then, the X's on the diagonal can be ``moved
inside," and a final application of the (forward) growth diagram
construction on the half-square completes the bijection. As far as I
can see, other than that, the two constructions do not seem to be more
deeply related.


\Refs

\ref\no \BereAA \by A. Berele\paper A Schensted-type correspondence for the
symplectic group\jour J. Combin\. Theory Ser.~A \vol 43\yr 1986\pages 
320--328\endref

\ref\no \BrFoAA \by T. Britz and S. Fomin\paper 
Finite posets and Ferrers shapes\jour
Adv.\ Math\.\vol 158\yr 2001\pages 86--127\endref

\ref\no \BurrAA \by S. Burrill\book
A generating tree approach to $k$-nonnesting arc diagrams\bookinfo
Ph.D. thesis\publ Simon Fraser University\publaddr Burnaby,
Canada\yr 2014\finalinfo available at
{\tt http://summit.sfu.ca/item/14390}
\endref

\ref\no \BuMMAA \by S. Burrill, S. Melczer and M. Mishna\paper 
 A Baxter class of a different kind, and other bijective results using
 tableau sequences ending with a row shape
\jour manuscript; {\tt ar$\chi$iv:1411.6606}\vol \yr \pages \endref

\ref\no \BuCFAA \by 
S. Burrill, J. Courtiel, E. Fusy, S. Melczer and M. Mishna
\paper Tableau sequences, open diagrams, and Baxter families
\jour preprint; {\tt ar$\chi$iv:1506.03544v1}\vol \yr \pages \endref

\ref\no \ChDDAB\by W. Y. C. Chen, E. Y. P. Deng, R. R. X. Du,
R. P. Stanley and C. H.
Yan\paper Crossings and nestings of matchings and partitions\jour
Trans\. Amer\. Math\. Soc\. \vol359 \yr 2007\pages1555--1575\endref

\ref\no \DeDFAA\by M.-P. Delest, S. Dulucq and L. Favreau\paper
An analogue to Robinson--Schensted correspondence for oscillating
tableaux\jour S\'em. Lotharingien Combin.\vol B20\yr 1988\pages
Article~B20b, 11~pp\endref

\ref\no \DuSaAA\by  S. Dulucq and B. E. Sagan\paper
La correspondance de Robinson--Schensted pour les tableaux oscillants
gauches\jour Discrete Math\.\vol 139\yr 1995\pages 129--142\endref

\ref\no \FomiAZ\by S. V. Fomin\paper Generalized Robinson--Schensted--Knuth
correspondence\paperinfo (Russian)\jour
Zap.\ Nauchn.\ Sem.\ Leningrad.\ Otdel.\ Mat.\ Inst.\ 
Steklov.\ (LOMI) \vol 155\yr
1986\finalinfo translation in  J. Soviet Math.\ {\bf 41} (1988),
979--991\endref

\ref\no \FomiAB\by S.    Fomin\paper 
Schensted algorithms for graded graphs\jour
J. Alg.\ Combin\. \vol 4\yr 1995\pages 5--45\endref

\ref\no \FomiAF\by S.    Fomin\paper 
Schur operators and Knuth correspondences\jour
J.~Combin.\ Theory Ser.~A \vol 72\yr 1995\pages 277--292\endref

\ref\no \GeZeAA\by I. M. Gessel and D. Zeilberger \yr 1992 \paper
Random walk in a Weyl chamber\jour Proc\. Amer\. Math\. Soc\.\vol
115\pages 27--31\endref 

\ref\no \GoulAD\by I. P. Goulden\paper A linear operator for symmetric
functions and tableaux in a strip with given trace\jour 
Discrete Math\.\vol 99\yr 1992\pages 69--77\endref

\ref\no \GrMrAA\by D. J. Grabiner and P. Magyar \yr 1993 \paper Random
walks in Weyl chambers and the decomposition of tensor products\jour
J. Alg\. Combin\.\vol 2\pages 239--260\endref 

\ref\no \GreCAA\by C. Greene\paper An extension of Schensted's theorem
\jour Adv.\ Math\.\vol 14\yr 1974\pages 254--265\endref

\ref\no \KnutAA\by D. E. Knuth \yr 1970 \paper Permutations, matrices,
and generalized Young tableaux\jour Pacific J. Math\. \vol 34\pages
709--727\endref 

\ref\no \KratBC\by C.    Krattenthaler \yr 1998 \paper Identities for
classical group characters of nearly rectangular shape\jour
J. Algebra \vol 209\pages 1--64\endref 

\ref\no \KratCE\by C.    Krattenthaler \yr 2006 \paper Growth
diagrams, and increasing and decreasing chains in fillings of Ferrers
shapes\jour Adv\. Appl\. Math\.\vol 37\pages 404--431\endref 

\ref\no \LeeuAD\by M.van Leeuwen \yr 1996 \paper The
Robinson--Schensted and Sch\"utzenberger algorithms, an elementary
approach\jour Electron\. J. Combin\.\vol 3 \rm(no.~2, ``The Foata
Festschrift")\pages Article~\#R15, 32~pp\endref 

\ref\no \LeeuAH\by M.\ van Leeuwen\yr 2005\paper 
Spin-preserving Knuth correspondences for ribbon 
tableaux\jour Electron.\ J. Combin\.\vol 12\rm(1)\pages Article~\#R10,
65~pp\endref

\ref\no \MacdAC\by I. G. Macdonald \yr 1995 \book Symmetric Functions
and Hall Polynomials \bookinfo second edition\publ Oxford University
Press\publaddr New York/Lon\-don\endref 

\ref\no \ProcAA\by R. A. Proctor\paper
A generalized Berele--Schensted algorithm and conjectured Young
tableaux for intermediate symplectic groups\jour
Trans\. Amer\. Math\. Soc\.\vol 324 \yr 1991\pages 655--692\endref

\ref\no \RobiAA\by G. de B. Robinson \yr 1938 \paper On
representations of the symmetric group
\jour Amer\. J. Math\.\vol 60\pages 745--760\endref 

\ref\no \RobyAA\by T. W. Roby\book Applications and extensions of 
Fomin's generalization 
of the Robinson--Schensted correspondence to differential posets\publ
Ph.D. thesis, M.I.T.\publaddr Cambridge, Massachusetts\yr 1991\endref

\ref\no \RobyAD\by T. W. Roby\paper 
The connection between the Robinson--Schensted
correspondence for skew oscillating tableaux and graded graphs\jour
Discrete Math\.\vol 139\yr 1995\pages 481--485\endref

\ref\no \SagaAQ\by B. E. Sagan\book The symmetric group
\bookinfo 2nd edition\publ Springer--Verlag\publaddr New York
\yr 2001\endref

\ref\no \ScheAA\by C. Schensted \yr 1961 \paper Longest increasing and
decreasing subsequences\jour Canad\. J. Math\.\vol 13\pages 179--191\endref

\ref\no \SchuAB\by M.-P. Sch\"utzenberger \yr 1963 \paper Quelques
remarques sur une construction de Schensted\jour Math\. Scand\.\vol 14
\pages 117--128\endref

\ref\no \SchuAA\by M.-P. Sch\"utzenberger \yr 1977 \paper La
correspondance de Robinson\inbook Combinatoire et Repr\'esentation du
Groupe Sym\'etrique\publ Lecture Notes in Math\., vol.~579,
Springer--Verlag\publaddr Ber\-lin--Hei\-del\-berg--New York\pages
59--113\endref    

\ref\no \StanBI\by R. P. Stanley \yr 1999 \book Enumerative
Combinatorics\bookinfo vol.~2\publ Cambridge University Press\publaddr
Cambridge\endref 

\ref\no \SunaAE\by S.    Sundaram \yr 1989 \paper Tableaux in the
representation theory of the classical Lie groups\inbook Invariant
theory and tableaux\ed D.~Stanton\publ The IMA Volumes in Math\. And
Its Appl\., Vol.~19, Sprin\-ger--Ver\-lag\publaddr New York, Berlin,
Heidelberg\pages 191--225\endref

\ref\no \SunaAD\by S.    Sundaram \yr 1990 \paper Orthogonal tableaux
and an insertion algorithm for $SO(2n+1)$\jour J. Combin\. Theory
Ser.~A\vol 53\pages 239--256\endref

\ref\no \SunaAC\by S.    Sundaram \yr 1990 \paper The Cauchy identity
for $Sp(2n)$\jour J. Combin\. Theory Ser.~A\vol 53\pages
209--238\endref 

\endRefs

\enddocument




