# On the Limiting Vacillating Tableaux for Integer Sequences

Zhanar Berikkyzy  ,  Pamela E. Harris  ,  Anna Pun  ,  Catherine Yan  and
Chenchen Zhao  Department of Mathemtics, Fairfield University, Fairfield, CT
06824<EMAIL_ADDRESS>Department of Mathematical Sciences,
University of Wisconsin Milwaukee, Milwaukee, WI 53211<EMAIL_ADDRESS>Department of Mathematics, CUNY Baruch College, New York, NY 10010
<EMAIL_ADDRESS>Department of Mathematics, Texas A&M University,
College Station, TX 77843<EMAIL_ADDRESS>Department of Mathematics,
University of Southern California, Los Angeles, CA 90089<EMAIL_ADDRESS>
###### Abstract.

A fundamental identity in the representation theory of the partition algeba is
$n^{k}=\sum_{\lambda}f^{\lambda}m_{k}^{\lambda}$ for $n\geq 2k$, where
$\lambda$ ranges over integer partitions of $n$, $f^{\lambda}$ is the number
of standard Young tableaux of shape $\lambda$, and $m_{k}^{\lambda}$ is the
number of vacillating tableaux of shape $\lambda$ and length $2k$. Using a
combination of RSK insertion and jeu de taquin, Halverson and Lewandowski
constructed a bijection $DI_{n}^{k}$ that maps each integer sequence in
$[n]^{k}$ to a pair consisting of a standard Young tableau and a vacillating
tableau. In this paper, we show that for a given integer sequence
$\boldsymbol{i}$, when $n$ is sufficiently large, the vacillating tableaux
determined by $DI_{n}^{k}(\boldsymbol{i})$ become stable when
$n\rightarrow\infty$; the limit is called the limiting vacillating tableau for
$\boldsymbol{i}$. We give a characterization of the set of limiting
vacillating tableaux and presents explicit formulas that enumerate those
vacillating tableaux.

##  1\. Introduction

In [3] Halverson and Lewandowski presented combinatorial proofs of two
identities arising in the representation theory of the partition algebra
$\mathcal{C}A_{k}(n)$. One of the identities is that for $n\geq 2k$,

(1) $n^{k}=\sum_{\lambda\vdash n}f^{\lambda}m_{k}^{\lambda},$

where the sum is over integer partitions $\lambda$ of $n$, $f^{\lambda}$ is
the number of standard Young tableaux (SYT) of shape $\lambda$, and
$m_{k}^{\lambda}$ is the number of vacillating tableaux of shape $\lambda$ and
length $2k$, whose definition is given below. To emphasize the dependency on
the parameter $n$, we call such tableaux $n$-vacillating tableaux.

######  Definition 1.

[3] For $n\geq 2k$, an _$n$ -vacillating tableau of shape $\lambda$ and length
$2k$_ is a sequence of integer partitions

$((n)=\lambda^{(0)},\lambda^{(\frac{1}{2})},\lambda^{(1)},\lambda^{(1\frac{1}{2})},\dots,\lambda^{(k-\frac{1}{2})},\lambda^{(k)}=\lambda),$

satisfying the condition that for each integer $j$,

  1. (a)

$\lambda^{(j)}\vdash n$ and $\lambda^{(j+\frac{1}{2})}\vdash(n-1)$,

  2. (b)

$\lambda^{(j)}\supseteq\lambda^{(j+\frac{1}{2})}$ and
$|\lambda^{(j)}/\lambda^{(j+\frac{1}{2})}|=1$,

  3. (c)

$\lambda^{(j+\frac{1}{2})}\subseteq\lambda^{(j+1)}$, and
$|\lambda^{(j+1)}/\lambda^{(j+\frac{1}{2})}|=1$.

Let $\mathcal{VT}_{n,k}(\lambda)$ denote the set of $n$-vacillating tableaux
of shape $\lambda$ and length $2k$. Note that $\mathcal{VT}_{n,k}(\lambda)$ is
non-empty only when the shape $\lambda$ has at most $k$ boxes not in the first
row.

The bijective proof of (1) given in [3] uses a combination of the Robinson-
Schensted-Knuth (RSK) insertion algorithm and jeu de taquin. For any integer
sequence $\boldsymbol{i}=(i_{1},i_{2},\dots,i_{k})\in[n]^{k}$ where
$[n]=\\{1,2,\dots,n\\}$, Halverson and Lewandowski define an iterative
“delete-insert” process that associates to $\boldsymbol{i}$ a pair
$DI_{n}^{k}(\boldsymbol{i})=(T^{k}_{n,\lambda}(\boldsymbol{i}),P^{k}_{n,\lambda}(\boldsymbol{i}))$,
where $\lambda$ is an integer partition of $n$,
$T^{k}_{n,\lambda}(\boldsymbol{i})$ is a SYT of shape $\lambda$ and
$P^{k}_{n,\lambda}(\boldsymbol{i})\in\mathcal{VT}_{n,k}(\lambda)$.

The paper [3] has an equivalent notion of vacillating tableaux that does not
use the parameter $n$, which was also independently introduced in [1] to study
the crossings and nestings of matchings and set partitions. To distinguish
from the $n$-vacillating tableaux, we call this second notion the _simplified
vacillating tableaux_. For an integer partition
$\lambda=(\lambda_{1},\lambda_{2},\dots,\lambda_{t})\vdash n$, let
$\lambda^{*}=(\lambda_{2},\dots,\lambda_{t})\vdash(n-\lambda_{1})$. For an
$n$-vacillating tableaux
$P_{\lambda}=(\lambda^{(j)}:j=0,\frac{1}{2},1,1\frac{1}{2},\dots,k)$ in
$\mathcal{VT}_{n,k}(\lambda)$, the _simplified vacillating tableaux
$(P_{\lambda})^{*}$_ is the sequence
$(\mu^{(j)}:\mu^{(j)}=(\lambda^{(j)})^{*}\text{ for
}j=0,\frac{1}{2},1,1\frac{1}{2},\dots,k)$. One can also define the simplified
vacillating tableaux in terms of integer partitions.

######  Definition 2.

[1] A _simplified vacillating tableau_ $P_{k}^{*}(\mu)$ of shape $\mu$ and
length $2k$ is a sequence $(\mu^{(j)}:j=0,\frac{1}{2},1,1\frac{1}{2},\dots,k)$
of integer partitions such that $\mu^{(0)}=\emptyset$, $\mu^{(k)}=\mu$, and
for each integer $j=0,1,\dots,k-1$:

  1. (a)

$\mu^{(j+\frac{1}{2})}$ is obtained from $\mu^{(j)}$ by doing nothing (i.e.,
$\mu^{(j+\frac{1}{2})}=\mu^{(j)}$) or deleting a box;

  2. (b)

$\mu^{(j+1)}$ is obtained from $\mu^{(j+\frac{1}{2})}$ by doing nothing or
adding a box.

Denote by $\mathcal{SVT}_{k}(\lambda^{*})$ the set of simplified vacillating
tableaux of shape $\lambda^{*}$ and length $2k$. If $n\geq 2k$, it is clear
that $P_{\lambda}\leftrightarrow(P_{\lambda})^{*}$ is a bijection between
$\mathcal{VT}_{n,k}(\lambda)$ and $\mathcal{SVT}_{k}(\lambda^{*})$.

The objective of this paper is to study the vacillating tableaux defined by
the map $DI_{n}^{k}$ for integer sequences, and it is more convenient to use
the simplified notion to describe our result. For a fixed integer sequence
$\boldsymbol{i}\in[n]^{k}$, one observes that
$P^{k}_{m,\lambda}(\boldsymbol{i})$ can be different from
$P^{k}_{m+1,\lambda}(\boldsymbol{i})$, even if one considers the corresponding
simplified vacillating tableaux. However, we show in Section 2 that when $m$
is sufficiently large, the simplified vacillating tableaux
$(P^{k}_{m,\lambda}(\boldsymbol{i}))^{*}$ become stable, which is denoted by
$P^{*}(\boldsymbol{i})$ and is called the limiting vacillating tableau of
$\boldsymbol{i}$. We will give a characterization of the set of limiting
vacillating tableaux. In Section 3, we enumerate the number of limiting
vacillating tableaux of length $2k$. First, we express this number as a sum of
Stirling numbers of the second kind and the number of involutions in the
symmetric group, and then we prove that this coincides with the sequence
A004211 in OEIS [5], which counts certain bi-colored set partitions.

##  2\. Limiting vacillating tableaux

First, we recall the bijection $DI_{n}^{k}$ of [3] to give the exact
construction of the $n$-vacillating tableaux
$P^{k}_{n,\lambda}(\boldsymbol{i})$ for an integer sequence $\boldsymbol{i}$.
In the following an integer partition is virtually represented by the Young
diagram, which contains $\lambda_{j}$ boxes in the $j$-th row. Here we use
English notation in which the diagrams are aligned in the upper-left corner.
We will consider partial tableaux, that is, integer partitions whose boxes are
filled with distinct integers that are increasing in rows and columns. The set
of integers in the boxes of a partial tableau $T$, denoted content$(T)$, is
call the _content_ of $T$. A standard Young tableaux with $n$ boxes is a
partial tableaux whose content is exactly $[n]$.

The main ingredients of the bijection $DI_{n}^{k}$ are the RSK row insertion
algorithm and a special case of the Schützenberger’s jeu de taquin algorithm,
which removes a box containing the entry $x$ from a partial tableau and
produces a new partial tableau. We adopt the description from [3], while the
full version and in-depth discussion of these algorithms can be found in [6,
chapter 3] or [7, Chapter 7].

The RSK row insertion. Let $T$ be a partial tableau of partition shape
$\lambda$ with $|\lambda|<n$ and with district entries from
$\\{1,2,\dots,n\\}$. Let $x$ be a positive integer that is not in $T$. The
operation $x\xrightarrow{RSK}T$ is defined as follows.

  1. (a)

Let $R$ be the first row of $T$.

  2. (b)

While $x$ is less than some element in $R$, do

    1. i)

Let $y$ be the smallest element of $R$ greater than $x$;

    2. ii)

Replace $y\in R$ with $x$;

    3. iii)

Let $x:=y$ and let $R$ be the next row.

  3. (c)

Place $x$ at the end of $R$ (which is possibly empty).

The result is a partial tableau of shape $\mu$ such that $|\mu/\lambda|=1$.

Jeu de taquin. Let $T$ be a partial tableau of partition shape $\lambda$ with
distinct entries in $\\{1,2,\dots,n\\}$. Let $x$ be an entry in $T$. The
following operation will delete $x$ from $T$ and yield a partial tableau $S$.

  1. (a)

Let $c=T_{i,j}$ be the box of $T$ containing $x$, which is the $j$-th box in
the $i$-th row of $T$.

  2. (b)

While $c$ is not a corner, i.e., a box both at the end of a row and the end of
a column, do

    1. i)

Let $c^{\prime}$ be the box containing $\min\\{T_{i+1,j},T_{i,j+1}\\}$; if
only one of $T_{i+1,j},T_{i,j+1}$ exists, then the minimum is taken to be that
single entry;

    2. ii)

Exchange the positions of $c$ and $c^{\prime}$.

  3. (c)

Delete $c$.

We denote this process by $x\xleftarrow{jdt}T$.

Both of the above two processes are invertible. Examples can be found in [3,
Section 3]. The bijection $DI_{n}^{k}$ from integer sequences to the set of
pairs consisting of a SYT and an $n$-vacillating tableau is built by iterating
alternatively between the two processes.

The bijection $DI_{n}^{k}$. Let $(i_{1},i_{2},\dots,i_{k})\in[n]^{k}$ be an
integer sequence of length $k$. First we define a sequence of partial tableaux
recursively: the $0$-th tableau is the unique SYT of shape $(n)$ with the
filling $1,2,\dots,n$, namely,

$T^{(0)}=$$1$$2$$\dots$$n$.

Then for integers $j=0,1,\dots,k-1$, the partial tableaux
$T^{(j+\frac{1}{2})}$ and $T^{(j+1)}$ are defined by

(2) $\displaystyle T^{(j+\frac{1}{2})}$ $\displaystyle=$
$\displaystyle\left(i_{j+1}\xleftarrow{jdt}T^{(j)}\right),$ (3) $\displaystyle
T^{(j+1)}$ $\displaystyle=$
$\displaystyle\left(i_{j+1}\xrightarrow{RSK}T^{(j+\frac{1}{2})}\right).$

Let $\lambda^{(j)}$ be the shape of $T^{(j)}$ for all $j$, and
$\lambda=\lambda^{(k)}$ be the shape of the last partial tableau $T^{(k)}$.
Finally, let

(4) $\displaystyle T^{k}_{n,\lambda}(\boldsymbol{i})=T^{(k)},\qquad
P^{k}_{n,\lambda}(\boldsymbol{i})=\left(\lambda^{(0)},\lambda^{(\frac{1}{2})},\lambda^{(1)},\lambda^{(1\frac{1}{2})},\dots,\lambda^{(k)}\right),$

so that $T^{k}_{n,\lambda}(\boldsymbol{i})$ is a SYT of shape $\lambda$ and
$P^{k}_{n,\lambda}(\boldsymbol{i})$ is an $n$-vacillating tableau of shape
$\lambda$ and length $2k$. The image of $\boldsymbol{i}$ under the map
$DI_{n}^{k}$ is given by
$DI_{n}^{k}(\boldsymbol{i})=(T^{k}_{n,\lambda}(\boldsymbol{i}),P^{k}_{n,\lambda}(\boldsymbol{i}))$.

######  Example 3.

Consider the integer sequence $\boldsymbol{i}=(4,4)$. First let $n=4$ and
apply the map $DI_{4}^{2}$. The $(T^{(j)})$ sequence is

$1$$2$$3$$4$$\rightarrow$$1$$2$$3$$\rightarrow$$1$$2$$3$$4$$\rightarrow$$1$$2$$3$$\rightarrow$$1$$2$$3$$4$

Hence for $DI_{4}^{2}(\boldsymbol{i})$, $\lambda=(4)$,
$T^{2}_{4,\lambda}(\boldsymbol{i})=$ $1$$2$$3$$4$ , and

$P^{2}_{4,\lambda}(\boldsymbol{i}):$$\big{(}$,,,,$\big{)}$.

It follows that the simplified vacillating tableau for
$P^{2}_{4,\lambda}(\boldsymbol{i})$ is
$(\emptyset,\emptyset,\emptyset,\emptyset,\emptyset)$.

Similarly, for $n=5$ and $6$ we can compute that

$T^{2}_{5,\lambda}(\boldsymbol{i})=$$1$$2$$3$$4$$5$,$T^{2}_{6,\lambda}(\boldsymbol{i})=$$1$$2$$3$$4$$5$$6$.

The simplified vacillating tableaufor $P^{2}_{5,\lambda}(\boldsymbol{i})$ is
$(\emptyset,\emptyset,\square,\square,\square)$, while the simplified
vacillating tableau for $P^{2}_{6,\lambda}(\boldsymbol{i})$ is
$(\emptyset,\emptyset,\square,\square,\ytableausetup{boxsize=7px}\ydiagram{2})$.

From the above example we see that the vacillating tableaux defined by
$DI_{n}^{k}(\boldsymbol{i})$ and $DI_{m}^{k}(\boldsymbol{i})$ may not be the
same, even if we consider the simplified version. Nevertheless, we prove that
for any integer sequence $\boldsymbol{i}$, the simplified vacillating tableaux
$(P^{k}_{m,\lambda}(\boldsymbol{i}))^{*}$ eventually stabilize when $m$ is
sufficiently large.

######  Theorem 4.

Let $\boldsymbol{i}=(i_{1},\dots,i_{k})\in[n]^{k}$ be an integer sequence. For
$m>n+2k$, the vacillating tableaux $P^{k}_{m,\lambda}(\boldsymbol{i})$ and
$P^{k}_{m+1,\lambda}(\boldsymbol{i})$ have the same simplified version, i.e.,
the two vacillating tableaux become the same after removing the first row from
each integer partition in the sequences.

###### Proof.

Comparing the sequences of partial tableaux $(T_{m}^{(j)})$ and
$(T_{m+1}^{(j)})$, for $0\leq j\leq k$ and $j\in\mathbb{Z}/2$, determined by
the maps $DI_{m}^{k}(\boldsymbol{i})$ and $DI_{m+1}^{k}(\boldsymbol{i})$,
respectively, we will prove by induction that $T_{m+1}^{(j)}$ can be obtained
from $T_{m}^{(j)}$ by adding the entry $m+1$ at the end of the first row. The
claim is obviously true for $j=0$. In the following, we let $j$ represent
integers only and prove that if the claim is true for $j$, then it is true for
the indices $j+\frac{1}{2}$ and $j+1$.

Note that for any partial tableau involved, there are at most $k$ boxes not in
the first row. When an entry $i_{j}$ is inserted in the application of either
$DI_{m}^{k}$ or $DI_{m+1}^{k}$, since $i_{j}\leq n$, it can bump at most one
integer larger than $n$ to the second row. Hence any integer larger than $n+k$
stays in the first row in all the partial tableaux during the delete-insert
process. In addition, for any partial tableau, there are at most $k$ integers
not in the first row, hence the first row has length greater than or equal to
$m-k>n+k$, which is strictly longer than the second row.

For integers $j=0,1,\dots,k-1$,

  1. (1)

Consider the tableaux $T_{*}^{(j+\frac{1}{2})}$ obtained by
$(i_{j+1}\xleftarrow{jdt}T_{*}^{(j)})$, where $*$ is $m$ or $m+1$.

    1. (a)

If the shapes of $T_{m}^{(j+\frac{1}{2})}$ and $T_{m}^{(j)}$ differ by a
corner box in the first row, then the jeu de taquin process only shifts boxes
in the first row of $T_{m}^{(j)}$. Since the first row of $T_{m}^{(j)}$ is
strictly longer than its second row, and $T_{m+1}^{(j)}$ has one more entry,
$m+1$, at the end of the first row, applying the jeu de taquin to
$T_{m+1}^{(j)}$ will only involve the boxes in the first row and have $m+1$ at
the end, and hence leave the simplified tableau unaffected.

    2. (b)

If the shape of $T_{m}^{(j+\frac{1}{2})}$ and $T_{m}^{(j)}$ differ by a corner
box not in the first row, then the boxes exchanged in
$(i_{j+1}\xleftarrow{jdt}T_{m+1}^{(j)})$ are exactly the same as those boxes
exchanged in $(i_{j+1}\xleftarrow{jdt}T_{m}^{(j)})$, which do not involve the
box containing $m$. Hence, the entry $m+1$ in $T_{m+1}^{(j)}$ stays at the end
of the first row and has never been involved in the deleting process.

  2. (2)

Consider the tableaux $T_{*}^{(j+1)}$ obtained by
$(i_{j+1}\xrightarrow{RSK}T_{*}^{(j+\frac{1}{2})})$, where $*$ is $m$ or
$m+1$.

Since the entry $m$ is in the same position of the first row of
$T_{m}^{(j+\frac{1}{2})}$ and $T_{m+1}^{(j+\frac{1}{2})}$, and $i_{j+1}\leq
n<m$, we know $i_{j+1}$ will bump an entry no larger than $n+j+1$ to the
second row in the RSK insertion. In other words, all the entries larger than
$n+j+1$ in $T_{m+1}^{(j+1)}$ will stay in the first row, including $m+1$.

Now removing the first rows from $(T_{m}^{(j)})$ and $(T_{m+1}^{(j)})$ for all
$j$ will give us the same integer partition sequence; that is,
$P^{k}_{m,\lambda}(\boldsymbol{i})$ and $P^{k}_{m+1,\lambda}(\boldsymbol{i})$
have the same simplified version. ∎

For any integer sequence $\boldsymbol{i}\in[n]^{k}$, let
$P^{*}(\boldsymbol{i})$ be the simplified vacillating tableau
$\left(P^{k}_{m,\lambda}(\boldsymbol{i})\right)^{*}$ when $m>n+2k$. By Theorem
4, $P^{*}(\boldsymbol{i})$ is well-defined. We call $P^{*}(\boldsymbol{i})$
the limiting vacillating tableau of the integer sequence $\boldsymbol{i}$. It
is in the set $\mathcal{SVT}_{k}(\lambda^{*})$ for some ending shape
$\lambda^{*}$ with at most $k$ boxes.

Next theorem gives a characterization of the limiting vacillating tableaux for
integer sequences of length $k$. Note that two integer sequences may have the
same limiting vacillating tableaux. From the proof of Theorem 4, when we apply
jeu de taquin to delete an entry, we remove one box either from the first row,
in which case the simplified tableau has the same shape, or from a row below
the first, resulting in a simplified tableau with a box removed. When we
perform RSK insertion, since $m$ is sufficiently large, the entry $m$ always
stays in the first row, which guarantees that an entry is bumped down, that
is, a box must be added in the simplified tableau. In conclusion, if we look
at the simplified vacillating tableaux, during deletion we know that the shape
is either invariant or has one box removed, and during insertion there is
always a box added to the shape.

######  Proposition 5.

A sequence of integer partitions
$(\lambda^{(j)}:j=0,\frac{1}{2},1,1\frac{1}{2},\dots,k)$ is the limiting
vacillating tableau for some integer sequence of length $k$ if and only if
$(\lambda^{(0)})=\emptyset$ and the sequence satisfies the following
conditions for each integer $j=0,1,\dots,k-1$:

  1. (a)

$(\lambda^{(j+\frac{1}{2})})$ is obtained from $(\lambda^{(j)})$ by either
doing nothing or deleting a box;

  2. (b)

$(\lambda^{(j+1)})$ is obtained from $(\lambda^{(j+\frac{1}{2})})$ by adding a
box.

###### Proof.

The necessity is proved in the preceding paragraph. We just need to show the
sufficient part.

Let $P=(\lambda^{(j)}:j=0,\frac{1}{2},1,1\frac{1}{2},\dots,k)$ be a simplified
vacillating tableau of length $2k$ that satisfies the conditions listed.
Assume there are $\ell$ boxes in $\lambda^{(k)}$, then we have $\ell\leq k$.
Take an integer $n$ such that $n>2k$. Let $\tilde{P}=(\tilde{\lambda}^{(j)})$
be the sequence of integer partitions obtained from $P$ by adding a row of
boxes to each $\lambda^{(j)}$ such that $\tilde{\lambda}^{(j)}$ has $n$ boxes
if $j$ is an integer, and $n-1$ boxes if $j$ is a half-integer. Let $F$ be a
SYT of shape $\tilde{\lambda}^{(k)}$ that has
$1,2,\dots,2k-\ell,2k+1,2k+2,\dots,n$ in the first row. Since the map
$DI_{n}^{k}$ is a bijection, there is a unique integer sequence
$\boldsymbol{i}=(i_{1},\dots,i_{k})\in[n]^{k}$ such that
$DI_{n}^{k}(\boldsymbol{i})=(F,\tilde{{P}})$. By Condition b, each time we
perform the RSK algorithm to insert $i_{j}$, an entry is bumped down from the
first row. Hence $i_{j}\neq n$ for all $j$. Furthermore, $n$ cannot be bumped
into the second row during the entirety of the delete-insert process,
otherwise it will stay under the first row and be an entry in $F$, which
contradicts the construction of $F$. Therefore the entry $n$ must stay at the
end of the first row when we apply $DI_{n}^{k}(\boldsymbol{i})$.

Now let $m>n$ and compare $DI_{n}^{k}(\boldsymbol{i})$ and
$DI_{m}^{k}(\boldsymbol{i})$. When we construct the partial tableaux
$(T^{(j)})$ in $DI_{m}^{k}(\boldsymbol{i})$, the integers $n+1,\dots,m$ always
stay at the end of the first row and do not interfere with the delete-insert
process. In other words, the simplified vacillating tableau obtained from
$DI_{m}^{k}(\boldsymbol{i})$ is the same as the one obtained from
$DI_{n}^{k}(\boldsymbol{i})$, which is ${P}$. This proves that ${P}$ is a
limiting vacillating tableau. ∎

The diagram in Figure 1 gives the limiting vacillating tableaux of length up
to 3. The number next to each integer partition indicates the number of
simplified vacillating tableaux ending at that integer partition.

$k=0:$$\emptyset$$1$$k=\frac{1}{2}:$$\emptyset$$1$$k=1$:$1$$k=1\frac{1}{2}:$$\emptyset$$1$$1$$k=2:$$1$$1$$1$$k=2\frac{1}{2}:$$\emptyset$$1$$3$$1$$1$$k=3:$$1$$3$$3$$1$$2$$1$
Figure 1. Limiting vacillating tableaux of length up to $3$.

##  3\. Enumeration of the limiting vacillating tableaux

Let $a_{k}$ be the number of limiting vacillating tableaux of length $2k$. We
set $a_{0}=1$. The initial values of the sequence $(a_{k})_{k=0}^{\infty}$ are
$1,1,3,11,49,257,\dots.$ Checking the data on OEIS [5] reveals that these
values coincide with the initial values of the sequence A004211, which is
described as “shifts one place left under 2nd-order binomial transformation”
and “equals the eigensequence of the box of Pascal’s triangle.” A
combinatorial interpretation of the sequence A004211 is given by Goyt and
Pudwell [2], who proved that the $k$-th term counts the number of arrangements
of the multiset $\\{1,1,2,2,\dots,k,k\\}$ satisfying the following two
conditions:

  1. (a)

All entries between the two occurrences of any given value $i$ exceed $i$, and

  2. (b)

No three entries increase from left to right with the last two adjacent.

Furthermore, $c_{k}$, the $k$-th term of A004211, can be computed by the
formula

(5) $c_{k}=\sum_{m=1}^{k}2^{k-m}\begin{Bmatrix}k\\\ m\end{Bmatrix},$

where $\genfrac{\\{}{\\}}{0.0pt}{2}{k}{m}$ is the Stirling number of the
second kind that counts the number of set partitions of $[k]$ into $m$ blocks.
Let $\mathcal{P}_{k}$ be the set of set partitions of the set $[k]$ such that
each element is colored either red or blue, and for each block the minimal
element is colored red. We call such a set partition a _bi-colored set
partition of $[k]$_. Clearly the summation in (5) counts the number of bi-
colored set partitions in $\mathcal{P}_{k}$. Goyt and Pudwell proved (5) by
constructing a bijection between the set $\mathcal{P}_{k}$ and the set of the
special arrangements of the multiset $\\{1,1,2,2,\dots,k,k\\}$ described
above.

We claim that the sequence $(a_{k})_{k=0}^{\infty}$ is exactly A004211. To do
this first we give an explicit formula of $a_{k}$ in terms of Stirling numbers
of the second kind and numbers of standard Young tableaux. Then we show this
formula is equivalent to (5) through a bijective proof.

######  Proposition 6.

Let $k$ be a positive integer. Then

(6) $a_{k}=\sum\limits_{j=1}^{k}\Bigg{(}\begin{Bmatrix}k\\\
j\end{Bmatrix}\sum\limits_{\lambda\vdash j}f^{\lambda}\Bigg{)}.$

###### Proof.

We will show that there is a bijection between the set of limiting vacillating
tableaux of length $2k$ and the set of all pairs

$\\{(\boldsymbol{B},T):\boldsymbol{B}\mbox{ is a set partition of $[k]$ and
$T$ is a partial tableau with }\textrm{content}(T)=\max(\boldsymbol{B})\\},$

where $\max(\boldsymbol{B})$ is the set of maximal elements in the blocks of
$\boldsymbol{B}$. The bijection is essentially the one constructed in [1,
Section 2] to count the total number of simplified vacillating tableaux. Here
we restrict the bijection to the set of simplified vacillating tableaux
satisfying the conditions (a) and (b) listed in Proposition 5. We remark that
the basic operation of this bijection was first given by Sundaram [8] in the
study of the Cauchy identity in the symplectic group $Sp(2n)$.

The Bijection $\psi$ from limiting vacillating tableaux to pairs
$(\boldsymbol{B},T)$. Given a simplified vacillating tableaux
${P}=(\emptyset=\lambda^{(0)},\lambda^{(\frac{1}{2})},\lambda^{(1)},\dots,\lambda^{(k)})$
satisfying the two conditions listed in Proposition 5, we will recursively
define a sequence
$(E_{0},T_{0}),(E_{\frac{1}{2}},T_{\frac{1}{2}}),\dots,(E_{k},T_{k})$ where
$E_{i}$ is a set of ordered pairs of integers in $[k]$ (which are viewed as
“edges”), and $T_{j}$ is a partial tableau of shape $\lambda^{(j)}$. Let
$E_{0}$ be the empty set and $T_{0}$ be the empty tableau (on the empty
alphabet). For each integer $j=1,2,\dots,k$,

  1. (a)

If $\lambda^{(j-\frac{1}{2})}=\lambda^{(j-1)}$, then
$(E_{j-\frac{1}{2}},T_{j-\frac{1}{2}})=(E_{j-1},T_{j-1})$.

  2. (b)

If $\lambda^{(j-\frac{1}{2})}\subsetneq\lambda^{(j-1)}$, let
$T_{j-\frac{1}{2}}$ be the unique partial tableau (on a suitable alphabet) of
shape $\lambda^{(j-\frac{1}{2})}$ such that $T_{j-1}$ is obtained from
$T_{j-\frac{1}{2}}$ by row-inserting some integer $m$. Note that $m$ must be
less than $j$. Let $E_{j-\frac{1}{2}}$ be obtained from $E_{j-1}$ by adding
the ordered pair $(m,j)$.

  3. (c)

For a limiting vacillating tableau we always have
$\lambda^{(j)}\supsetneq\lambda^{(j-\frac{1}{2})}$. Let
$E_{j}=E_{j-\frac{1}{2}}$. and $T_{j}$ is obtained from $T_{j-\frac{1}{2}}$ by
adding the entry $j$ in the box $\lambda^{(j)}/\lambda^{(j-\frac{1}{2})}$.

It is clear from the above construction that $E_{0}\subseteq
E_{\frac{1}{2}}\subseteq\cdots\subseteq E_{k}$. Let $G=(V,E_{k})$ be a graph
with the vertex set $V=[k]$ and edge set $E_{k}$, and $\boldsymbol{B}$ be the
set partition of $[k]$ whose blocks are connected components of $G$. Finally
we define $\psi({P})=(\boldsymbol{B},T_{k})$.

In [1] it is shown that $\psi$ is a bijection from the set of all simplified
vacillating tableaux of length $2k$ to the pairs of $(\boldsymbol{B},T)$ where
$\boldsymbol{B}$ is a set partition of $[k]$ and $T$ is a partial tableau with
content$(F)\subseteq\max(\boldsymbol{B})$. The equality may not hold for a
general simplified vacillating tableau, since it allows
$\lambda^{(j)}=\lambda^{(j-\frac{1}{2})}$ for an integer $j$. (In that case
just let $E_{j}=E_{j-\frac{1}{2}}$ and $T_{j}=T_{j-\frac{1}{2}}$.) If ${P}$ is
a limiting vacillating tableau, then each integer $i$ either appears as the
first component of an ordered pair in $E_{k}$, or appears in the last tableau
$T_{k}$. Hence in this case $T=T_{k}$ is a partial tableau with
content$(T)=\max(\boldsymbol{B})$.

Now we count the number of pairs $(\boldsymbol{B},T)$. For each integer
$j\in[k]$, there are $\sum\limits_{\lambda\vdash j}f^{\lambda}$ choices for
STYs with $j$ boxes and $\displaystyle\genfrac{\\{}{\\}}{0.0pt}{2}{k}{j}$ set
partitions of $[k]$ with $j$ blocks. Replacing the content set $[j]$ with the
set of maximal block elements in the set partition yield the pair
$(\boldsymbol{B},T)$. Hence (6) follows. ∎

######  Example 7.

An example of the map $\psi$ follows. Let the limiting vacillating tableaux
${P}$ be the following sequence with $k=4$:

$\emptyset$$\emptyset$

Then the sequence of $(E_{i},T_{i})$ is

$i$:$0$$\frac{1}{2}$$1$$1\frac{1}{2}$$2$$2\frac{1}{2}$$3$$3\frac{1}{2}$$4$$T_{i}$:$\emptyset$$\emptyset$1112223224$E_{i}$:$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\\{(1,3)\\}$$\\{(1,3)\\}$$\\{(1,3)$$(3,4)\\}$$\\{(1,3)$$(3,4)\\}$

and hence $\psi(P)=(\boldsymbol{B},T_{4})$, where $\boldsymbol{B}$ is the set
partition $\\{\\{134\\},\\{2\\}\\}$.

######  Corollary 8.

Let $k$ be a positive integer. Then

$a_{k}=\sum\limits_{j=1}^{k}\Bigg{(}\begin{Bmatrix}k\\\
j\end{Bmatrix}(\\#\mbox{ involutions in $\mathfrak{S}_{j}$})\Bigg{)}.$

###### Proof.

It follows from the fact that the number of involutions in the symmetric group
$\mathfrak{S}_{j}$ equals the number of SYT with $j$ boxes, which is given by
$\sum\limits_{\lambda\vdash j}f^{\lambda}$. ∎

######  Theorem 9.

Let $k$ be a positive integer. Then

(7) $\sum\limits_{j=1}^{k}\Bigg{(}\begin{Bmatrix}k\\\ j\end{Bmatrix}(\\#\mbox{
involutions in
$\mathfrak{S}_{j}$})\Bigg{)}\Bigg{)}=\sum\limits_{t=1}^{k}\Bigg{(}\begin{Bmatrix}k\\\
t\end{Bmatrix}2^{k-t}\Bigg{)}.$

Consequently, the sequence $(a_{k})_{k=0}^{\infty}$ is exactly the OEIS
sequence A004211.

###### Proof.

For a set partition of $[k]$ with $j$ blocks, we order the blocks according to
the minimal element in each block. That is, if
$\boldsymbol{B}=\\{B_{1},\dots,B_{j}\\}$ is a set partition of $[k]$, then
$\min{B_{1}}<\min{B_{2}}<\cdots<\min{B_{j}}$. Let $\sigma\in\mathfrak{S}_{j}$
be an involution. Then $\sigma$ is a product of disjoint 1 or 2-cycles. Denote
by $\mathcal{B}_{k}$ the set of all pairs $\\{(\boldsymbol{B},\sigma)\\}$
where $\boldsymbol{B}$ is a set partition of $[k]$ and $\sigma$ is an
involution whose length equals the number of blocks of $\boldsymbol{B}$.

Let $\mathcal{P}_{k}$ be the set of bi-colored set partitions of $[k]$ such
that each number in $[k]$ is colored either red or blue, and the minimal
element of each block is colored red. By [2], $\mathcal{P}_{k}$ is enumerated
by the OEIS sequence A004211 and $|\mathcal{P}_{k}|$ can be expressed by the
right side of (7).

We define a bijection $\phi:\mathcal{B}_{k}\mapsto\mathcal{P}_{k}$ as follows.
Let $(\boldsymbol{B},\sigma)\in\mathcal{B}_{k}$ where
$B=\\{B_{1},\dots,B_{j}\\}$.

  1. (a)

Construct a set partition. For every 2-cycle $(a,b)$ in $\sigma$, we form a
new block by merging $B_{a}$ with $B_{b}$. For every 1-cycle $(r)$ in
$\sigma$, we keep $B_{r}$ as a new block. The collection of all the new blocks
forms $\boldsymbol{B^{\prime}}$.

  2. (b)

In each block $B$ of $\boldsymbol{B}^{\prime}$, color the element $\min{B}$
red. For each non-minimal element $x$ of $B$, color it red if and only if $x$
and $\min{B}$ are in the same block of $\boldsymbol{B}$. Otherwise, $x$ is
blue.

This gives a bi-colored set partition in the set $\mathcal{P}_{k}$.

Conversely, for a bi-colored set partition $\boldsymbol{B^{\prime}}$ in
$\mathcal{P}_{k}$, where the minimal element in each block is red, we can
recover the pair $(\boldsymbol{B},\sigma)$ by the following steps.

  1. (a’)

First for each block of $\boldsymbol{B^{\prime}}$, split it into two blocks by
putting the red elements into one block and blue elements into another block.
If there is no blue elements, then we just keep it as one block.

The collection of all the blocks obtained this way forms $\boldsymbol{B}$.

  2. (b’)

Assume there are $j$ blocks in $\boldsymbol{B}$. Label the blocks of
$\boldsymbol{B}$ as $B_{1},B_{2},\dots,B_{j}$ according to their minimal
elements so that $\min{B_{1}}<\min{B_{2}}<\cdots<\min{B_{j}}$. For any block
$B_{i}$, if there is another block $B_{k}$ such that $B_{i}\cup B_{k}$ is one
block of $\boldsymbol{B^{\prime}}$, then $(i,k)$ is a 2-cycle of $\sigma$.
Otherwise, $(i)$ is a 1-cycle of $\sigma$. This creates an involution $\sigma$
in $\mathfrak{S}_{j}$.

Note that this process gives $\phi^{-1}$ which proves that $\phi$ is bijective
and (7) follows. ∎

######  Example 10.

We give an example illustrating the bijection $\phi$ in the proof of Theorem
9. Let $k=10$,
$\boldsymbol{B}=\\{\\{1,3,4,8\\},\\{2,5\\},\\{6\\},\\{7,9,10\\}\\}$, and
$\sigma=(14)(23)$ in cycle notation. Then the set partition
$\boldsymbol{B^{\prime}}$ is obtained from $\boldsymbol{B}$ by merging $B_{1}$
with $B_{4}$ and merging $B_{2}$ with $B_{3}$. The coloring is indicated by
the superscript:
$\boldsymbol{B^{\prime}}=\\{\\{1^{r},3^{r},4^{r},7^{b},8^{r},9^{b},10^{b}\\},\\{2^{r},5^{r},6^{b}\\}\\}$.

##  4\. Final Remarks and Future Projects

The limiting vacillating tableaux induce an equivalence relation on the
integer sequences. So it is natural to ask the following question.

_Question 1. Determine when two integer sequences have the same limiting
vacillating tableau._

For $k=2$ we have a complete answer, which can be easily checked.

######  Example 11.

Let $P^{*}(\boldsymbol{i})$ be the limiting vacillating tableau of the integer
sequence $\boldsymbol{i}=(i_{1},i_{2})$, where both $i_{1}$ and $i_{2}$ are
positive integer. Then

  1. (a)

$P^{*}(\boldsymbol{i})=(\emptyset,\emptyset,\square,\emptyset,\square)$ if and
only if $i_{2}=i_{1}+1$ or $i_{1}=i_{2}=1$.

  2. (b)

$P^{*}(\boldsymbol{i})=(\emptyset,\emptyset,\square,\square,\ytableausetup{boxsize=7px}\ydiagram{2})$
if and only if $i_{1}=i_{2}>1$, or $i_{1}<i_{2}-1$.

  3. (c)

$P^{*}(\boldsymbol{i})=(\emptyset,\emptyset,\square,\square,\ytableausetup{aligntableaux=center,boxsize=7px}\ydiagram{1,1})$
if and only if $i_{1}>i_{2}$.

The question for longer sequences is much more complicated and the general
case remains open. The proofs of Proposition 5, 6, and Theorem 9 suggest some
possible approaches and related questions, which we plan to investigate next.

In the proof of Proposition 5, for a simplifed vacillating tableau $P$
satisfying the conditions listed, we constructed an integer sequence
$\boldsymbol{i}$ such that $P^{*}(\boldsymbol{i})=P$, using the bijective map
$DI_{n}^{k}$ with $n>2k$. In the proof we used a SYT $F$, which is clearly not
unique. Hence a related question is:

_Question 2. Fix $n$ and $k$ with $n\geq 2k$. Determine which integer
sequences correspond to the same vacillating tableau under the bijection
$DI_{n}^{k}$. That is, find the criterion such that for two integer sequences
$\boldsymbol{i}$ and $\boldsymbol{j}$, $DI_{n}^{k}(\boldsymbol{i})$ and
$DI_{n}^{k}(\boldsymbol{j})$ yield the same shape $\lambda$ and
$P_{n,\lambda}^{k}(\boldsymbol{i})=P_{n,\lambda}^{k}(\boldsymbol{j})$. _

By results in Section 3, we can represent a limiting vacillating tableau of
length $2k$ by certain enriched set partition, for example, either as a set
partition with an involution built on its blocks, or as a bi-colored set
partition in $\mathcal{P}_{k}$. This suggests the following question.

_Question 3. What can one say about the integer sequences based on some given
information on those enriched structures on set partitions? For example, does
the number of blocks, or the number of fixed points in the involution, have an
interpretation in the integer sequences?_

## Acknowledgement

We thank ICERM for hosting the “Research Community in Algebraic Combinatorics”
program in 2021, which facilitated and supported this research project. The
fourth author is supported in part by the Simons Collaboration Grant for
Mathematics 704276. The second author is supported by an EDGE Karen Uhlenbeck
fellowship.

## References

  * [1] W.Y.C. Chen, E.Y.P. Deng, R.R.X. Du, R.P. Stanley and C.H. Yan. Crossings and nestings of matchings and set partitions . _Trans. Amer. Math. Soc_. volume 359, no. 4, (2007) 1555–1575.
  * [2] A.M. Goyt and L.K. Pudwell. Solution to Monthly problem 11567. May, 2011. https://faculty.valpo.edu/lpudwell/papers/MonthlyStirling.pdf
  * [3] T. Halverson and T. Lewandowski. RSK insertion for set partitions and diagram algebras. _Electron J. Combin._ 11 (2004/2006), 24.
  * [4] T. Halverson and N. Thiem. $q$-Partition algebra combinatorics. _J. Combin. Theory A_ , 117(2010), 507–527.
  * [5] N.J.A. Sloane. The On-line Encyclopedia of Integer Sequences. https://oeis.org.
  * [6] B. Sagan. the Symmetric Groups, Representations, Combinatorial Algorithms, and Symmetric Functions, second edition, Springer-Verlag, New York, 2001.
  * [7] R.P. Stanley. Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.
  * [8] S. Sundaram, The Cauchy identity for Sp(2n), _J. Combin. Theory Ser. A_ , 53 (1990), 209–238.