# Cyclic Sieving of Increasing Tableaux and Small Schröder Paths

Oliver Pechenik†

*Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA.*

**Abstract.** An increasing tableau is a semistandard tableau with strictly increasing rows and columns. It is well known that the Catalan numbers enumerate both rectangular standard Young tableaux of two rows and also Dyck paths. We generalize this to a bijection between rectangular 2-row increasing tableaux and small Schröder paths. Using the jeu de taquin for increasing tableaux of [Thomas–Yong '09], we then present a new instance of the cyclic sieving phenomenon of [Reiner–Stanton–White '04].

**Résumé.** Un tableau croissant est un tableau semi-standard avec les lignes et les colonnes croissantes au sens strict. Il est bien connu que les nombres de Catalan énumèrent les tableaux de Young standard rectangulaires de deux lignes et aussi les chemins de Dyck. Nous généralisons ceci pour une bijection entre tableaux croissants rectangulaires à 2 lignes et petits chemins de Schröder. Utilisant le jeu de taquin de [Thomas–Yong '09] pour tableaux croissants, nous présentons ensuite une nouvelle instance du phénomène du crible cyclique de [Reiner–Stanton–White '04].

**Keywords:** increasing tableaux, cyclic sieving phenomenon, K-promotion, Schröder path, Schröder number, non-crossing partition

## 1 Introduction

An increasing tableau is a semistandard tableau such that all rows and columns are strictly increasing and the set of entries is an initial segment of $\mathbb{Z}_{>0}$. For $\lambda$ a partition of $N$, we write $|\lambda| = N$. We denote by $\text{Inc}_k(\lambda)$ the set of increasing tableaux of shape $\lambda$ with maximum value $|\lambda| - k$. Similarly $\text{SYT}(\lambda)$ denotes standard Young tableaux of shape $\lambda$. Notice $\text{Inc}_0(\lambda) = \text{SYT}(\lambda)$. We routinely identify a partition $\lambda$ with its Young diagram; hence for us the notations $\text{SYT}(m \times n)$ and $\text{SYT}(n^m)$ are equivalent.

A small Schröder path is a planar path from the origin to $(n, 0)$ that is constructed from three types of line segment: *upsteps* by $(1, 1)$, *downsteps* by $(1, -1)$, and *horizontal steps* by $(2, 0)$, so that the path never falls below the horizontal axis and no horizontal step lies on the axis. The $n^{th}$ small Schröder number is defined to be the number of such paths. A Dyck path is a small Schröder path without horizontal steps.

Our first result is an extension of the classical fact that Catalan numbers enumerate both Dyck paths and rectangular standard Young tableaux of two rows, $\text{SYT}(2 \times n)$. For $T \in \text{Inc}_k(2 \times n)$, let $\text{maj}(T)$ be the sum of all $i$ in row 1 such that $i + 1$ appears in row 2.

<footnote>†Supported by an Illinois Distinguished Fellowship from the University of Illinois, an NSF Graduate Research Fellowship, and NSF grant DMS 0838434 "EMSW21MCTP: Research Experience for Graduate Students."</footnote>
**Theorem 1.1** There are explicit bijections between $\mathrm{Inc}_k(2 \times n)$, small Schröder paths with $k$ horizontal steps, and $\mathrm{SYT}(n-k, n-k, 1^k)$. This implies the identity

$$ \sum_{T \in \mathrm{Inc}_k(2 \times n)} q^{\mathrm{maj}(T)} = q^{n+\frac{1}{2}(k^2+k)} \frac{\begin{bmatrix} n-1 \\ k \end{bmatrix}_q \begin{bmatrix} 2n-k \\ n-k-1 \end{bmatrix}_q}{[n-k]_q}. \qquad (1) $$

In particular, the total number of increasing tableaux of shape $2 \times n$ is the $n^{th}$ small Schröder number.

The “flag-shaped” standard Young tableaux of Theorem 1.1 were previously considered by R. Stanley [Sta96] in relation to polygon dissections.

Suppose $X$ is a finite set, $C_n = \langle c \rangle$ a cyclic group acting on $X$, and $f \in \mathbb{Z}[q]$ a polynomial. The triple $(X, C_n, f)$ has the cyclic sieving phenomenon [RSW04] if for all $m$, the number of elements of $X$ fixed by $c^m$ is $f(\zeta^m)$, where $\zeta$ is any primitive $n^{th}$ root of unity. D. White [Whi07] discovered a cyclic sieving for $2 \times n$ standard Young tableaux. For this, he used a $q$-analogue of the hook-length formula (that is, a $q$-analogue of the Catalan numbers) and a group action by jeu de taquin promotion. B. Rhoades [Rho10, Theorem 1.3] generalized this result from $\mathrm{SYT}(2 \times n)$ to $\mathrm{SYT}(m \times n)$. Our main result is a generalization of D. White’s result in another direction, from $\mathrm{SYT}(2 \times n) = \mathrm{Inc}_0(2 \times n)$ to $\mathrm{Inc}_k(2 \times n)$.

We first define $K$-promotion for increasing tableaux. Define the $\mathrm{SE-neighbors}$ of a box to be the (at most two) boxes immediately below it or right of it. Let $T$ be an increasing tableau with maximum entry $M$. Delete the entry 1 from $T$, leaving an empty box. Repeatedly perform the following operation simultaneously on all empty boxes until no empty box has a $\mathrm{SE-neighbor}$: Label each empty box by the minimal label of its $\mathrm{SE-neighbors}$ and then remove that label from the $\mathrm{SE-neighbor(s)}$ in which it appears. If an empty box has no $\mathrm{SE-neighbors}$, it remains unchanged. We illustrate the local changes in Figure 1.

<figure><img src="image_1.png" /><figcaption>Fig. 1: Local changes during $K$-promotion for $i < j$.</figcaption></figure>

Notice that the number of empty boxes may change during this process. Finally we obtain the $K$-promotion $P(T)$ by labeling all empty boxes by $M+1$ and then subtracting one from every label. Figure 2 shows a full example of $K$-promotion.

<figure><img src="image_2.png" /><figcaption>Fig. 2: $K$-promotion.</figcaption></figure>

Our definition of $K$-promotion is analogous to that of ordinary promotion, but uses the $K$-jeu de taquin of H. Thomas–A. Yong [TY09] in place of ordinary jeu de taquin. (The ‘$K$’ reflects their original development of $K$-jeu de taquin in application to $K$-theoretic Schubert calculus.) Observe that on standard Young tableaux, promotion and $K$-promotion coincide.

We will need:
**Theorem 1.2** For all $n$ and $k$, there is an action of the cyclic group $C_{2n-k}$ on $T \in \mathrm{Inc}_k(2 \times n)$, where a generator acts by K-promotion.

In the case $k = 0$, Theorem 1.2 is implicit in work of M.-P. Schützenberger (cf. [?, ?]). We provide two combinatorial proofs of Theorem 1.2, which we believe provide different insights. Finally we construct the following cyclic sieving.

**Theorem 1.3** For all $n$ and $k$, the triple $(\mathrm{Inc}_k(2 \times n), C_{2n-k}, f)$ has the cyclic sieving phenomenon, where

$$f(q) := \frac{\begin{bmatrix} n-1 \\ k \end{bmatrix}_q \begin{bmatrix} 2n-k \\ n-k-1 \end{bmatrix}_q}{[n-k]_q}$$

is the q-enumerator from Theorem 1.1.

Our proof of Theorem 1.3 is elementary. In contrast, all proofs [Rho10, ?] of B. Rhoades' theorem for standard Young tableaux use representation theory or geometry. (Also [PPR09], where the authors give new proofs of the 2- and 3-row cases of B. Rhoades' result, uses representation theory.) It is natural to ask also for such proofs of Theorem 1.3. For $k > 0$, Theorem 1.2 does not generalize in the obvious way to tableaux of more than 3 rows. We do not know a common generalization of our Theorem 1.3 and B. Rhoades' theorem.

This note is an extended abstract of [Pec12]. Here we omit or sketch most of the proofs. The organization is as follows. In Section 2, we prove Theorem 1.1. We include an additional bijection (to be used in Section 4) between $\mathrm{Inc}_k(2 \times n)$ and certain noncrossing partitions that we interpret as generalized non-crossing matchings. In Section 3, we develop a strengthening of Theorem 1.2 through combinatorics of small Schröder paths. We also provide a counterexample to the analogous statement for 4-row increasing tableaux. In Section 4, we use noncrossing partitions to give a second proof of Theorem 1.2 and to prove Theorem 1.3.

## 2 Bijections and Enumeration

**Proposition 2.1** There is an explicit bijection between $\mathrm{Inc}_k(2 \times n)$ and $\mathrm{SYT}(n-k, n-k, 1^k)$.

**Proof:** Let $T \in \mathrm{Inc}_k(2 \times n)$. The following algorithm produces a corresponding $S \in \mathrm{SYT}(n-k, n-k, 1^k)$. Observe that every value in $\{1, \dots, 2n-k\}$ appears in $T$ either once or twice. Let $A$ be the set of numbers that appear twice. Let $B$ be the set of numbers that appear in the second row immediately right of an element of $A$. Note $|A| = |B| = k$.

Let $T'$ be the tableau of shape $(n-k, n-k)$ formed by deleting all elements of $A$ from the first row of $T$ and all elements of $B$ from the second. The standard Young tableau $S$ is given by appending $B$ to the first column. An example is shown in Figure 3.

This algorithm is reversible. Given the standard Young tableau $S$ of shape $(n-k, n-k, 1^k)$, let $B$ be the set of entries below the first two rows. By inserting $B$ into the second row of $S$ while maintaining increasingness, we reconstruct the second row of $T$. Let $A$ be the set of elements immediately left of an element of $B$ in this reconstructed row. By inserting $A$ into the first row of $S$ while maintaining increasingness, we reconstruct the first row of $T$. $\square$
**Corollary 2.2** For all $n$ and $k$,

$$ \sum_{T \in \mathrm{Inc}_k(2 \times n)} q^{\mathrm{maj}(T)} = q^{n+\frac{1}{2}(k^2+k)} \frac{\begin{bmatrix} n-1 \\ k \end{bmatrix}_q \begin{bmatrix} 2n-k \\ n-k-1 \end{bmatrix}_q}{[n-k]_q}. $$

□

**Proof of Theorem 1.1:** The bijection between $\mathrm{Inc}_k(2 \times n)$ and $\mathrm{SYT}(n-k, n-k, 1^k)$ is given by Proposition 2.1. The $q$-enumeration (1) is exactly Corollary 2.2.

We now give a bijection between $\mathrm{Inc}_k(2 \times n)$ and small Schröder paths with $k$ horizontal steps. Let $T \in \mathrm{Inc}_k(2 \times n)$. For each integer $j$ from $1$ to $2n-k$, we create one segment of a small Schröder path $P_T$. If $j$ appears only in the first row, then the $j^{\text{th}}$ segment of $P_T$ is an upstep. If $j$ appears only in the second row of $T$, the $j^{\text{th}}$ segment of $P_T$ is a downstep. If $j$ appears in both rows of $T$, the $j^{\text{th}}$ segment of $P_T$ is horizontal. It is clear that the tableau $T$ can be reconstructed from the small Schröder path $P_T$, so this operation gives a bijection. Thus increasing tableaux of shape $(n, n)$ are counted by small Schröder numbers. □

<figure><img src="image_3.png" /><figcaption>Fig. 3: A rectangular increasing tableau $T \in \mathrm{Inc}_2(5, 5)$ with its corresponding standard Young tableau of shape $(3, 3, 1, 1)$, small Schröder path, noncrossing partition of $\{1, \dots, 8\}$ with all blocks of size at least two, and heptagon dissection.</figcaption></figure>

The following bijection will play an important role in our proof of Theorem 1.3 in Section 4. A partition of $\{1, \dots, N\}$ is *noncrossing* if the convex hulls of the blocks are pairwise disjoint when the values $1, \dots, N$ are equally spaced around a circle with $1$ in the upper left and values increasing counterclockwise (cf. Figure 3(D)).
**Proposition 2.3** *There is an explicit bijection between $\text{Inc}_k(2 \times n)$ and noncrossing partitions of $2n-k$ into $n-k$ blocks all of size at least 2.*

**Proof:** Let $T \in \text{Inc}_k(2 \times n)$. For each $i$ in the second row of $T$, let $s_i$ be the largest number in the first row that is less than $i$ and that is not $s_j$ for some $j < i$. Form a partition of $2n-k$ by declaring, for every $i$, that $i$ and $s_i$ are in the same block. We see this partition has $n-k$ blocks by observing that the largest elements of the blocks are precisely the numbers in the second row of $T$ that do not also appear in the first row. Clearly there are no singleton blocks.

If the partition were not noncrossing, there would exist some elements $a < b < c < d$ with $a, c$ in a block $B$ and $b, d$ in a distinct block $B'$. Observe that $b$ must appear in the first row of $T$ and $c$ must appear in the second row of $T$ (not necessarily exclusively). We may assume $c$ to be the least element of $B$ that is greater than $b$. We may then assume $b$ to be the greatest element of $B'$ that is less than $c$. Now consider $s_c$, which must exist since $c$ appears in the second row of $T$. By definition, $s_c$ is the largest number in the first row that is less than $c$ and that is not $s_j$ for some $j < c$. By assumption, $b$ appears in the first row, is less than $c$, and is not $s_j$ for any $j < c$; hence $s_c \ge b$. Since however $b$ and $c$ lie in distinct blocks, $s_c \ne b$, whence $b < s_c < c$. This is impossible, since we took $c$ to be the least element of $B$ greater than $b$. Thus the partition is necessarily noncrossing.

To reconstruct the increasing tableau, read the partition from 1 to $2n-k$. Place the smallest elements of blocks in only the first row, place the largest elements of blocks in only the second row, and place intermediate elements in both rows. $\square$

The set $\text{Inc}_k(2 \times n)$ is also in bijection with $(n+2)$-gon dissections by $n-k-1$ diagonals. We do not describe this bijection, as it is well known (cf. [Sta96]) and will not be used except in Section 4 for comparison with previous results. The existence of a connection between increasing tableaux and polygon dissections was first suggested in [?]. An example of all these bijections is shown in Figure 3.

**Remark 2.1** A noncrossing matching is a noncrossing partition with all blocks of size two. Like Dyck paths, polygon triangulations, and 2-row rectangular standard Young tableaux, noncrossing matchings are enumerated by the Catalan numbers. Since increasing tableaux were developed as a K-theoretic analogue of standard Young tableaux, it is tempting also to regard small Schröder paths, polygon dissections, and noncrossing partitions without singletons as K-theory analogues of Dyck paths, polygon triangulations, and noncrossing matchings, respectively. In particular, by analogy with [PPR09], it is tempting to think of noncrossing partitions without singletons as “K-webs” for $s_1$, although their representation-theoretic significance is unknown.

# 3 K-Promotion and K-Evacuation

In this section, we prove Theorem 1.2. Let $\max(T)$ denote the largest entry in a tableau $T$. For a rectangular tableau $T$, we write $\text{rot}(T)$ for the tableau formed by rotating 180 degrees and reversing the alphabet, so that label $x$ becomes $\max(T) + 1 - x$. We define $\text{K-evacuation} \mathcal{E}$ as in [TY09, §4] by analogy with evacuation for standard Young tableaux, using K-jeu de taquin in place of ordinary jeu de taquin. Define *dual K-evacuation* $\mathcal{E}^*$ by $\mathcal{E}^* := \text{rot} \circ \mathcal{E} \circ \text{rot}$. (This definition of $\mathcal{E}^*$ only makes sense for rectangular tableaux. For a tableau $T$ of general shape $\lambda$, in place of applying $\text{rot}$, one should dualize $\lambda$ (thought of as a poset) and reverse the alphabet. We will not make any essential use of this more general definition.)
Towards Theorem 1.2, we first develop basic combinatorics of the above operators that are well-known in the standard Young tableau case (cf. [?]). From these results, we observe that Theorem 1.2 follows from the claim that $\mathrm{rot}(T) = \mathcal{E}(T)$ for every $T \in \mathrm{Inc}_k(2 \times n)$. We first saw this approach in [?] for the standard Young tableau case, although similar ideas appear in [?, ?, ...]; we are not sure where it first appeared.

Finally, beginning at Lemma 3.3, we prove that for $T \in \mathrm{Inc}_k(2 \times n)$, $\mathrm{rot}(T) = \mathcal{E}(T)$. Here the situation is more subtle than in the standard case. (For example, we will show that the claim is not generally true for $T$ a rectangular increasing tableau with more than 3 rows.) We proceed by careful analysis of how $\mathrm{rot}$, $\mathcal{E}$, $\mathcal{E}^*$, and $\mathcal{P}$ act on the corresponding small Schröder paths.

**Remark 3.1** It is not hard to see that K-promotion is reversible, and hence permutes the set of increasing tableaux.

**Lemma 3.1** K-evacuation and dual K-evacuation are involutions, $\mathcal{P} \circ \mathcal{E} = \mathcal{E} \circ \mathcal{P}^{-1}$, and for any increasing tableau $T$, $(\mathcal{E}^* \circ \mathcal{E})(T) = \mathcal{P}^{\max(T)}(T)$.

Before proving Lemma 3.1, we briefly recall the *K-theory growth diagrams* of [TY09, §2, 4], which extend the standard Young tableau growth diagrams of S. Fomin (cf. [?, Appendix 1]). We will write $[T]_j$ for the subtableau of $T$ formed by deleting all entries $> j$. For $T \in \mathrm{Inc}_k(\lambda)$, consider the sequence of Young diagrams (shape($[T]_j$))$_{0 \le j \le |\lambda|-k}$. Note that this sequence of diagrams uniquely encodes $T$. We draw this sequence of Young diagrams horizontally from left to right. Below this sequence, we draw, in successive rows, the sequences of Young diagrams associated to $\mathcal{P}^i(T)$ for $1 \le i \le |\lambda|-k$. Hence each row encodes the K-promotion of the row above it. We offset each row one space to the right. We will refer to this entire array as the *K-theory growth diagram for $T$*. (There are other K-theory growth diagrams for $T$ that one might consider, but this is the only one we will need.) Figure 4 shows an example.

<figure><img src="image_4.png" /><figcaption>Fig. 4: The K-theory growth diagram for the tableau $T$ of Figure 3(A).</figcaption></figure>
We will write $YD_{ij}$ for the Young diagram shape$([\mathcal{P}^{i-1}(T)]_{j-i})$. This indexing is nothing more than imposing "matrix-style" or "English" coordinates on the K-theory growth diagram. For example in Figure 4, $YD_{58}$ denotes $\boxplus$, the Young diagram in the fifth row from the top and the eighth column from the left.

**Remark 3.2** [TY09, Proposition 2.2] In any $2 \times 2$ square $\begin{array}{cc} \lambda & \mu \\ \nu & \xi \end{array}$ of Young diagrams in a K-theory growth diagram, $\xi$ is uniquely and explicitly determined by $\lambda, \mu$ and $\nu$. Similarly $\lambda$ is uniquely and explicitly determined by $\mu, \nu$ and $\xi$. Furthermore these rules are symmetric, in the sense that if $\begin{array}{cc} \lambda & \mu \\ \nu & \xi \end{array}$ and $\begin{array}{cc} \xi & \mu \\ \nu & \rho \end{array}$ are both $2 \times 2$ squares of Young diagrams in K-theory growth diagrams, then $\lambda = \rho$.

**Proof of Lemma 3.1:** Fix a tableau $T \in \text{Inc}_k(\lambda)$. All of these facts are proven as in the standard case (cf. [?, §5]), except one uses K-theory growth diagrams instead of ordinary growth diagrams. The proof that K-evacuation is an involution appears in greater detail as [TY09, Theorem 4.1]. For rectangular shapes, the fact that dual K-evacuation is an involution follows from the fact that K-evacuation is, since $\mathcal{E}^* = \text{rot} \circ \mathcal{E} \circ \text{rot}$.

Essentially by definition, the central column (the column containing the rightmost $\emptyset$) of the K-theory growth diagram for $T$ encodes the K-evacuation of the first row as well as the dual K-evacuation of the last row. The first row encodes $T$ and the last row encodes $\mathcal{P}^{|\lambda|-k}(T)$. Hence $\mathcal{E}(T) = \mathcal{E}^*(\mathcal{P}^{|\lambda|-k}(T))$.

By the symmetry mentioned in Remark 3.2, one observes that the first row encodes the K-evacuation of the central column and that the last row encodes the dual K-evacuation of the central column. This yields $\mathcal{E}(\mathcal{E}(T)) = T$ and $\mathcal{E}^*(\mathcal{E}^*(\mathcal{P}^{|\lambda|-k}(T))) = \mathcal{P}^{|\lambda|-k}(T)$, showing that K-evacuation and dual K-evacuation are involutions. Combining the above observations, yields $(\mathcal{E}^* \circ \mathcal{E})(T) = \mathcal{P}^{|\lambda|-k}(T)$.

Finally to show $\mathcal{P} \circ \mathcal{E} = \mathcal{E} \circ \mathcal{P}^{-1}$, it is easiest to append an extra $\emptyset$ to the lower-right of the diagonal line of $\emptyset$s that appears in the K-theory growth diagram. This extra $\emptyset$ lies in the column just right of the central one. This column now encodes the K-evacuation of the second row. Hence by the symmetry mentioned in Remark 3.2, the K-promotion of this column is encoded by the central column. Thus if $S = \mathcal{P}(T)$, the central column encodes $\mathcal{P}(\mathcal{E}(S))$. But certainly $\mathcal{P}^{-1}(S) = T$ is encoded by the first row, and we have already observed that the central column encodes $\mathcal{E}(T)$. Therefore $\mathcal{P}(\mathcal{E}(S)) = \mathcal{E}(\mathcal{P}^{-1}(S))$. $\square$

Let $\text{er}(T)$ be the least positive integer such that $(\mathcal{E}^* \circ \mathcal{E})^{\text{er}(T)}(T) = T$. We call this number the *evacuation rank* of $T$. Similarly we define the *promotion rank* $\text{pr}(T)$ to be the least positive integer such that $\mathcal{P}^{\text{pr}(T)}(T) = T$.

**Corollary 3.2** Let $T$ be a increasing tableau. Then $\text{er}(T)$ divides $\text{pr}(T)$, $\text{pr}(T)$ divides $\max(T) \cdot \text{er}(T)$, and the following are equivalent:

(a) $\mathcal{E}(T) = \mathcal{E}^*(T)$,

(b) $\text{er}(T) = 1$,

(c) $\text{pr}(T)$ divides $\max(T)$.

Moreover if $T$ is rectangular and $\mathcal{E}(T) = \text{rot}(T)$, then $\mathcal{E}(T) = \mathcal{E}^*(T)$. $\square$
Thus to prove Theorem 1.2, it suffices to show that $\mathcal{E}(T) = \text{rot}(T)$ for every $T \in \text{Inc}_k(2 \times n)$. We use the bijection between $\text{Inc}_k(2 \times n)$ and small Schröder paths from Theorem 1.1. These paths are themselves in bijection with the sequence of their node heights, which we call the *height word*. Figure 3(C) shows an example. For $T \in \text{Inc}_k(2 \times n)$, we write $P_T$ for the corresponding small Schröder path and $S_T$ for the corresponding height word.

**Lemma 3.3** For $T \in \text{Inc}_k(2 \times n)$, the $i^{th}$ letter of the height word $S_T$ is the difference between the lengths of the first and second rows of the Young diagram shape($[T]_{i-1}$). $\square$

**Lemma 3.4** Let $T \in \text{Inc}_k(2 \times n)$. Then $P_{\text{rot}(T)}$ is the reflection of $P_T$ across a vertical line and $S_{\text{rot}(T)}$ is the word formed by reversing $S_T$. $\square$

**Lemma 3.5** Let $T \in \text{Inc}_k(2 \times n)$ and $M = 2n - k$. Let $x_i$ denote the $(M + 2 - i)^{th}$ letter of the height word $S_{P^{i-1}(T)}$. Then $S_{\mathcal{E}(T)} = x_{M+1}x_M \dots x_1$.

**Proof:** By consideration of the K-theory growth diagram for $T$. $\square$

**Lemma 3.6** Let $T \in \text{Inc}_k(2 \times n)$.

(a) The word $S_T$ may be written in exactly one way as $0w_10w_3$ or $0w_11w_20w_3$, where $w_1$ is a sequence of strictly positive integers that ends in 1 and contains no consecutive 1s, $w_2$ is a (possibly empty) sequence of strictly positive integers, and $w_3$ is a (possibly empty) sequence of nonnegative integers.

(b) Let $w_1^-$ be the sequence formed by decrementing each letter of $w_1$ by 1. Similarly, let $w_3^+$ be formed by incrementing each letter of $w_3$ by 1.

If $S_T$ is of the form $0w_10w_3$, then $S_{P(T)} = w_1^-1w_3^+0$. If $S_T$ is of the form $0w_11w_20w_3$, then $S_{P(T)} = w_1^-1w_21w_3^+0$. $\square$

For $T \in \text{Inc}_k(2 \times n)$, take the first $2n-k+1$ columns of the K-theory growth diagram for $T$. Replace each Young diagram in the resulting array by the difference between the lengths of its first and second rows. Figure 5 shows an example. We write $a_{ij}$ for the number corresponding to the Young diagram $YD_{ij}$. By Lemma 3.3, we see that the $i^{th}$ row of this array of nonnegative integers is exactly the first $2n-k+2-i$ letters of $S_{P^{i-1}(T)}$. Therefore we will refer to this array as the *height growth diagram* for $T$, and denote it by $\text{hgd}(T)$. Observe that the rightmost column of $\text{hgd}(T)$ corresponds to the central column of the K-theory growth diagram for $T$.

**Lemma 3.7** In $\text{hgd}(T)$ for $T \in \text{Inc}_k(2 \times n)$, we have for all $j$ that $a_{1j} = a_{j,2n-k+1}$.

**Proof:** By induction on the length of the height word. $\square$

**Corollary 3.8** In the notation of Lemma 3.5, $S_T = x_1x_2 \dots x_{M+1}$. $\square$

**Proposition 3.9** Let $T \in \text{Inc}_k(2 \times n)$. Then $\mathcal{E}(T) = \text{rot}(T)$.

**Proof:** By Corollary 3.8, $S_T = x_1x_2 \dots x_{2n-k+1}$. Hence $S_{\text{rot}(T)} = x_{2n-k+1}x_{2n-k} \dots x_1$, by Lemma 3.4. However Lemma 3.5 says that also $S_{\mathcal{E}(T)} = x_{2n-k+1}x_{2n-k} \dots x_1$. By the bijective correspondence between tableaux and height words, this yields $\mathcal{E}(T) = \text{rot}(T)$. $\square$
<figure><img src="image_5.png" /><figcaption>Fig. 5: The height growth diagram hgd($T$) for the tableau $T$ shown in Figure 3(A). The $i^{th}$ row shows the first $10 - i$ letters of $S_{\mathcal{P}^{i-1}(T)}$. Lemma 3.7 says that row 1 is the same as column 9, read from top to bottom.</figcaption></figure>

This completes our first proof of Theorem 1.2. We will obtain an alternate proof in Section 4. We now show a counterexample to the obvious generalization of Theorem 1.2 to increasing tableaux of more than two rows.

**Example 3.10** If $T$ is the increasing tableau
$$ \begin{array}{c|cccc} 1 & 2 & 4 & 7 \\ \cline{2-4} 3 & 5 & 6 & 8 \\ \cline{2-4} 5 & 7 & 8 & 10 \\ \cline{2-4} 7 & 9 & 10 & 11 \end{array} $$
then $\mathcal{P}^{11}(T) = \begin{array}{c|cccc} 1 & 2 & 4 & 7 \\ \cline{2-4} 3 & 4 & 6 & 8 \\ \cline{2-4} 5 & 6 & 8 & 10 \\ \cline{2-4} 7 & 9 & 10 & 11 \end{array}$ (The underscores mark entries that differ between the two tableaux.) It can be verified that the promotion rank of this tableau is 33.

Computer checks of small examples (including all with at most seven columns) did not identify such a counterexample for $T$ a 3-row rectangular increasing tableau.

# 4 Cyclic Sieving

**Proof of Theorem 1.3:** Recall we defined

$$ f(q) := \frac{\begin{bmatrix} n-1 \\ k \end{bmatrix}_q \begin{bmatrix} 2n-k \\ n-k-1 \end{bmatrix}_q}{[n-k]_q} $$

to be the $q$-enumerator for $\mathrm{Inc}_k(2 \times n)$ obtained in Theorem 1.1. Our strategy (modeled throughout on [RSW04, §7]) is to explicitly evaluate $f$ at roots of unity and compare the result with a count of increasing tableaux. To count tableaux, we use the bijection with noncrossing partitions given in Proposition 2.3. We will find that the symmetries of these partitions more transparently encode the promotion ranks of the corresponding tableaux.
**Lemma 4.1** Let $\zeta$ be any primitive $d^{th}$ root of unity, for $d$ dividing $2n-k$. Then

$$f(\zeta) = \begin{cases} \frac{\binom{2n-k}{d}}{\binom{k}{d}!\binom{n-k}{d}!(\frac{n-k}{d}-1)!\frac{n}{d}}, & \text{if } d|n \\ \frac{\binom{2n-k}{d}}{\binom{k+2}{d}-1}!\binom{n-k-1}{d}!(\frac{n-k-1}{d})!\frac{n+1}{d}, & \text{if } d|n+1 \\ 0, & \text{otherwise.} \end{cases}$$

**Proof:** By explicit evaluation, as in [RSW04, §7]. □

We will write $\pi$ for the bijection of Proposition 2.3 from $\text{Inc}_k(2 \times n)$ to noncrossing partitions of $2n-k$ into $n-k$ blocks all of size at least 2. In a noncrossing partition, there is at most one block whose convex hull contains the center of the disk; we call such a block the *central block*. For $\Pi$ a noncrossing partition of $N$, we write $\mathcal{R}(\Pi)$ for the noncrossing partition given by rotating $\Pi$ clockwise by $2\pi/N$.

**Lemma 4.2** For any $T \in \text{Inc}_k(2 \times n)$, $\pi(\mathcal{P}(T)) = \mathcal{R}(\pi(T))$. □

It remains now to count noncrossing partitions of $2n-k$ into $n-k$ blocks all of size at least 2 that are invariant under rotation by $2\pi/d$, and to show that we obtain the formula of Lemma 4.1. It is easy to show for such a partition $\Pi$ that $d|n+1$ if and only if $\Pi$ has a central block and that $d|n$ if and only if $\Pi$ has no central block.

Arrange the numbers $1, 2, \dots, n, -1, \dots, -n$ counterclockwise at equally spaced points around a circle. Consider a partition of these points such that, for every block $B$, the set formed by negating all elements of $B$ is also a block. If the convex hulls of the blocks are pairwise nonintersecting, we call such a partition a *noncrossing B-partition* or *type-B noncrossing partition* (cf. [Rei97]). There is an obvious bijection between noncrossing partitions of $2n-k$ that are invariant under rotation by $2\pi/d$ and noncrossing $B_{(2n-k)/d}$-partitions. The needed enumerations of type-B noncrossing partitions may be obtained from work of C. Athanasiadis, V. Reiner, and C. Savvidou [AR04, AS12]. □

Lemma 4.2 yields a second proof of Theorem 1.2. We observe that under the reformulation of Lemma 4.2, Theorem 1.3 bears a striking similarity to Theorem 7.2 of [RSW04] which gives a cyclic sieving on the set of all noncrossing partitions of $2n-k$ into $n-k$ parts with respect to the same cyclic group action.

Additionally, under the correspondence mentioned in Section 2 between $\text{Inc}_k(2 \times n)$ and dissections of an $(n+2)$-gon with $n-k-1$ diagonals, Theorem 1.3 bears a strong resemblance to Theorem 7.1 of [RSW04], which gives a cyclic sieving on the same set with the same $q$-enumerator, but with respect to an action by $C_{n+2}$ instead of $C_{2n-k}$. S.-P. Eu-T.-S. Fu [?] reinterpret the $C_{n+2}$-action as the action of a Coxeter element on the $k$-faces of an associahedron. We do not know such an interpretation of our action by $C_{2n-k}$. In [RSW04], the authors note many similarities between their Theorems 7.1 and 7.2 and ask for a unified proof. It would be very satisfying if such a proof could also account for our Theorem 1.3.

## Acknowledgements

Aisha Arroyo provided help with some computer experiments. The author thanks Victor Reiner for helpful comments on an early draft and Christos Athanasiadis for bringing [AS12] to his attention. The author is especially grateful to Alexander Yong for his many useful suggestions about both the mathematics and the writing of this paper.
References

[AR04] C. A. Athanasiadis and V. Reiner. Noncrossing partitions for the group $D_n$. *SIAM J. Discrete Math.*, 18(2):397-417, 2004.

[AS12] C. A. Athanasiadis and C. Savvidou. The local *h*-vector of the cluster subdivision of a simplex. *Sém. Lothar. Combin.*, 66(B66c), 2012.

[Pec12] O. Pechenik. Cyclic sieving of increasing tableaux and small Schröder paths. *arXiv:1209.1355*, 2012.

[PPR09] T. K. Petersen, P. Pylyavskyy, and B. Rhoades. Promotion and cyclic sieving via webs. *J. Algebraic Combin.*, 30:19-41, 2009.

[Rei97] V. Reiner. Non-crossing partitions for classical reflection groups. *Discrete Math.*, 177:195-222, 1997.

[Rho10] B. Rhoades. Cyclic sieving, promotion, and representation theory. *J. Combin. Theory Ser. A*, 117:38-76, 2010.

[RSW04] V. Reiner, D. Stanton, and D. White. The cyclic sieving phenomenon. *J. Combin. Theory Ser. A*, 108:17-50, 2004.

[Sta96] R. Stanley. Polygon dissections and standard Young tableaux. *J. Combin. Theory Ser. A*, 76:175-177, 1996.

[TY09] H. Thomas and A. Yong. A jeu de taquin theory for increasing tableaux, with applications to K-theoretic Schubert calculus. *Algebra Number Theory*, 3(2):121-148, 2009.

[Whi07] D. White. Personal communication to B. Rhoades (see [Rho10]). 2007.