CLASSIFICATION OF STANDARD YOUNG TABLEAUX IN A -HOOK

SUHYUNG AN; HYUNSOO CHO

doi:10.1017/S0004972726101397

CLASSIFICATION OF STANDARD YOUNG TABLEAUX IN A $(3,0)$- AND $(2,1)$-HOOK

Part of:Combinatorics

Published online by Cambridge University Press: 25 June 2026

SUHYUNG AN

and

HYUNSOO CHO

Show author details

SUHYUNG AN: Affiliation:
Department of Mathematics, Yonsei University , Seoul, Republic of Korea e-mail: hera1973@yonsei.ac.kr
HYUNSOO CHO*: Affiliation:
Institute of Mathematical Sciences, Ewha Womans University , Seoul, Republic of Korea
*: e-mail: hyunsoo@ewha.ac.kr

Article contents

Abstract
Introduction
Classification of S(3,0;n)$\mathfrak {S}(3,0;n)$
Classification of S(2,1;n)$\mathfrak {S}(2,1;n)$
Footnotes
References

Rights & Permissions

Abstract

We explore the combinatorial properties of the set $\mathfrak {S}(k,\ell; n)$ consisting of standard Young tableaux with specific shape constraints. Using bijections with Motzkin and free Motzkin paths, we enumerate $\mathrm {S}_m(3,0;n)$ and $\mathrm {S}_m(2,1;n)$ for all m, and $\mathrm {S}_m(0,3;n)$ and $\mathrm {S}_m(1,2;n)$ for small values of m. We derive explicit formulae such as $\mathrm {S}_2(3,0;n)=M_n - M_{n-1}$ and $\mathrm {S}_4(3,0;n)=M_{n-3}$, where $M_n$ denotes the number of Motzkin paths of length n. Furthermore, we offer an alternative proof of Regev’s identity $\mathrm {S}(2,1;n)=1+\mathrm { S}_{\mathrm {odd}}(2,1;n+1)$, thereby deepening the connection between standard Young tableaux and lattice path combinatorics.

Keywords

standard Young tableaux Motzkin paths free Motzkin paths

MSC classification

Primary:05A19: Combinatorial identities, bijective combinatorics

Secondary:05A15: Exact enumeration problems, generating functions

Information

Type: Research Article
Information: Bulletin of the Australian Mathematical Society , First View , pp. 1 - 12
DOI: https://doi.org/10.1017/S0004972726101397 [Opens in a new window]
Copyright: © The Author(s), 2026. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.

1 Introduction

Throughout the paper, we assume that n is a positive integer. For a partition ${\lambda }$ of n, let $\text {SYT}({\lambda })$ be the set of standard Young tableaux of shape ${\lambda }$ . For nonnegative integers k and $\ell $ , $\mathcal {H}(k,\ell; n)$ and $\mathfrak {S}(k,\ell; n)$ denote the set of partitions in a $(k,\ell )$ -hook and the set of standard Young tableaux in a $(k,\ell )$ -hook, respectively. Equivalently,

$$ \begin{align*}\mathcal{H}(k,\ell; n)=\{{\lambda}=({\lambda}_1,{\lambda}_2,\ldots) \vdash n ~|~{\lambda}_{k+1} \le \ell \}\end{align*} $$

and

$$ \begin{align*}\mathfrak{S}(k,\ell; n)=\bigcup_{{\lambda} \in \mathcal{H}(k,\ell; n)}\text{SYT}({\lambda}).\end{align*} $$ German upper S left parenthesis k comma script l semicolon n right parenthesis equals union Underscript lamda element of script upper H left parenthesis k comma script l semicolon n right parenthesis Endscripts SYT left parenthesis lamda right parenthesis period

Regev [Reference Regev5–Reference Regev7] focused on the combinatorial and asymptotic properties of $\mathfrak {S}(k,\ell; n)$ . By studying different values of k and $\ell $ , Regev showed that larger hooks lead to more complex behaviours in combinatorial structures. We write $\mathrm {S}(k,\ell; n)=|\mathfrak {S}(k,\ell; n)|$ . We list the known numbers $\mathrm {S}(k,\ell ;n)$ . When $\ell =0$ , Regev [Reference Regev5] showed that

$$ \begin{align*} \mathrm{S}(2,0;n)=\binom{n}{\lfloor n/2 \rfloor} \quad \text{and} \quad \mathrm{S}(3,0;n)=\sum_{i \ge 0} \frac{1}{i+1}\binom{n}{2i}\binom{2i}{i}; \end{align*} $$

Gouyou-Beauchamps [Reference Gouyou-Beauchamps4] proved that

$$ \begin{align*} \mathrm{S}(4,0;n)=C_{\lfloor (n+1)/2 \rfloor}C_{\lceil (n+1)/2 \rceil} \quad \text{and} \quad \mathrm{S}(5,0;n)=6\sum_{i=0}^{\lfloor n/2 \rfloor} \binom{n}{2i}C_i \frac{(2i+2)!}{(i+2)!(i+3)!}, \end{align*} $$

where $C_n$ is the nth Catalan number. When $\ell =1$ , Regev [Reference Regev6, Reference Regev7] derived

$$ \begin{align*} \mathrm{S}(2,1;n)=\frac{1}{2}\sum_{i\ge 1}\binom{n}{i}\binom{n-i}{i} +1 \quad \text{and} \quad \mathrm{S}(3,1;n)=\frac{1}{2}\bigg[ \binom{n}{\lfloor n/2 \rfloor}+\sum_{i=0}^{n} R_i\binom{n}{i} \bigg], \end{align*} $$

where $R_n$ is the nth Riordan number. Based on the results for $\mathrm {S}(3,0;n)$ and $\mathrm {S}(2,1;n)$ , Regev conjectured that these identities could be proven combinatorially.

A path is called a Motzkin path of length n if it is a path from $(0,0)$ to $(n,0)$ that stays weakly above the x-axis and consists of steps $U=(1,1)$ , $F=(1,0)$ and $D=(1,-1)$ . Let $\mathcal {M}_n$ be the set of Motzkin paths of length n and let $M_n=|\mathcal {M}_n|$ be the nth Motzkin number. It is known that

$$ \begin{align*}M_n=\sum_{i\ge 0}\frac{1}{i+1}\binom{n}{2i}\binom{2i}{i},\end{align*} $$ upper M Subscript n Baseline equals sigma summation Underscript i greater than or equals 0 Endscripts StartFraction 1 Over i plus 1 EndFraction StartBinomialOrMatrix n Choose 2 i EndBinomialOrMatrix StartBinomialOrMatrix 2 i Choose i EndBinomialOrMatrix comma

so we have $\mathrm {S}(3,0;n)=M_n$ . Eu [Reference Eu3] proved this combinatorially.

Theorem 1.1 [Reference Eu3, Theorem 2.1]

There is a bijection between $\mathfrak {S}(3,0;n)$ and $\mathcal {M}_n$ .

If a Motzkin path is allowed to go below the x-axis, we call it a free Motzkin path. Let $\mathcal {FM}_n$ be the set of free Motzkin paths of length n and $\mathcal {FM}^{D}_n$ be the set of paths in $\mathcal {FM}_n$ whose last nonflat step is a down step if such a step exists. We denote by $FM_n=|\mathcal {FM}_n|$ and $FM^{D}_n=|\mathcal {FM}^{D}_n|$ . It is easy to check that

$$ \begin{align*} FM_n=\sum_{i\ge 0}\binom{n}{i}\binom{n-i}{i} \quad\text{and}\quad FM^D_n=\frac{1}{2}\sum_{i\ge 1}\binom{n}{i}\binom{n-i}{i} +1, \end{align*} $$

so we have $\mathrm {S}(2,1;n)=FM^D_n$ . Du and Yu [Reference Du and Yu1] gave the following result.

Theorem 1.2 [Reference Du and Yu1, Theorems 2.1 and 3.3]

There is a bijection between $\mathfrak {S}(2,1;n)$ and $\mathcal {FM}^{D}_n$ .

Let $T_{\lambda }$ be a standard Young tableau of shape ${\lambda }$ . In [Reference Regev6], Regev introduced a restriction on $\mathfrak {S}(k,\ell ;n)$ regarding the parity of $T_{\lambda }(1,2)$ , defining

$$ \begin{align*}\mathfrak{S}_{\mathrm{odd}}(k,\ell;n)=\{T_{\lambda} \in \mathfrak{S}(k,\ell;n) \mid T_{\lambda} (1,2)~\text{is odd}\} \quad\text{and}\quad \mathrm{S}_{\mathrm{odd}}(k,\ell;n)=|\mathfrak{S}_{\mathrm{odd}}(k,\ell;n)|. \end{align*} $$

Regev [Reference Regev6, Conjecture 10.1] conjectured that $\mathrm{S}_\mathrm{odd}(3,0;n)$ is given by $\mathrm {S}_{\mathrm {odd}}(3,0;n)=\mathrm {S}(3,0;n-1)-\, \mathrm { S}(3,0; n-3)=M_{n-1}-M_{n-3}$ . This was proved by Ekhad and Zeilberger [Reference Ekhad and Zeilberger2] and Eu [Reference Eu3, Theorem 3.1] independently. Regev [Reference Regev6, Proposition 9.2] also found $\mathrm {S}(2,1;n)=1+\mathrm {S}_{\mathrm {odd}}(2,1;n+1)$ and asked for a combinatorial proof.

In this paper, we classify $\mathfrak {S}(3,0;n)$ and $\mathfrak {S}(2,1;n)$ according to the value of $T_{\lambda }(1,2)$ and extend this classification to other entries $T_{\lambda }(i,j)$ for some $i,j\in \mathbb {N}$ .

For positive integers i, j and m, let

$$ \begin{align*} \mathfrak{S}^{(i,j)}_m(k,\ell;n)=\{T_{\lambda} \in \mathfrak{S}(k,\ell;n) \mid T_{\lambda} (i,j)=m\} \quad\text{and}\quad \mathrm{ S}^{(i,j)}_m(k,\ell;n)=|\mathfrak{S}^{(i,j)}_m(k,\ell;n)|. \end{align*} $$

By convention, we omit the superscript when $(i,j)=(1,2)$ , so $\mathfrak {S}_m(k,\ell ;n)=\mathfrak {S}^{(1,2)}_m(k,\ell ;n)$ and $\mathrm { S}_m(k,\ell ;n)=\mathrm {S}^{(1,2)}_m(k,\ell ;n)$ . Note that $\mathrm {S}(k,\ell ;n)=\sum _{m\ge 2} \mathrm {S}_m(k,\ell ;n)$ and $\mathrm {S}_{\mathrm {odd}}(k,\ell ;n)=\sum _{m\ge 1} \mathrm {S}_{2m+1}(k,\ell ;n)$ . In particular, $\mathrm {S}_{\mathrm {odd}}(3,0;n)=\mathrm { S}_3(3,0;n)$ since $T_{\lambda } (1,2)\le 4$ when ${\lambda } \in \mathcal {H}(3,0;n)$ .

In Section 2, we provide a lattice path interpretation for $\mathfrak {S}_m(3,0;n)$ for ${m=2,3,4}$ . Since the identity $\mathrm { S}_3(3,0;n)=M_{n-1}-M_{n-3}$ is already known, we enumerate $\mathrm {S}_2(3,0;n)$ and $\mathrm {S}_4(3,0;n)$ .

Theorem 1.3. We have $\mathrm {S}_2(3,0;n)=M_n - M_{n-1}$ and $\mathrm {S}_4(3,0;n)=M_{n-3}$ .

We also provide a lattice path interpretation for $\mathfrak {S}_m(0,3;n)$ and enumerate $\mathrm {S}_m(0,3;n)$ for small m. In Section 3, we provide a lattice path interpretation for $\mathfrak {S}_m(2,1;n)$ for all $m\ge 2$ using the bijection of Du and Yu [Reference Du and Yu1]. We compute $\mathrm {S}_m(2,1;n)$ as follows.

Theorem 1.4. We have $\mathrm {S}_2(2,1;n)=FM^{D}_n-FM^{D}_{n-1}-FM^{D}_{n-2}$ and $\mathrm {S}_m(2,1;n)=FM^{D}_{n-m+2}-FM^{D}_{n-m}$ for $m\ge 3$ .

From Theorem 1.4, we derive the following result, which gives an alternative proof that $\mathrm {S}(2,1;n)=1+\mathrm {S}_{\mathrm {odd}}(2,1;n+1)$ .

Corollary 1.5. We have $\mathrm {S}_{\mathrm {odd}}(2,1;n)=FM^{D}_{n-1}-1$ .

Similarly to Section 2, we provide a lattice path interpretation for $\mathfrak {S}_m(1,2;n)$ and enumerate $\mathrm { S}_m(1,2;n)$ for small m.

2 Classification of $\mathfrak {S}(3,0;n)$

In this section, we present the classification results for $\mathfrak {S}(3,0;n)$ .

2.1 The bijection between $\mathfrak {S}(3,0;n)$ and $\mathcal {M}_n$

First, we summarise the bijection established by Eu [Reference Eu3] between $\mathfrak {S}(3,0;n)$ and $\mathcal {M}_n$ . Given a standard Young tableau T with n entries, the corresponding Yamanouchi word $W=\chi (T)=w_1 w_2 \cdots w_n$ is defined by $w_j=i$ when the entry of T labelled j is in the ith row. See Figure 1 for an example.

We define $\mathcal {W}_3(n)=\{\chi (T) \mid T\in \mathfrak {S}(3,0;n)\}$ , which consists of Yamanouchi words of length n over the alphabet $\{1, 2, 3\}$ . The bijection $\xi $ between $\mathcal {W}_3(n)$ and $\mathcal {M}_n$ is described below (we provide only the injective map; see [Reference Eu3, Section 2] for full details).

For a word $W=w_1 w_2 \cdots w_n \in \mathcal {W}_3(n)$ , the corresponding Motzkin path $P=\xi (W)=P_1 P_2 \cdots P_n$ satisfies the following conditions.

(1) If all letters of W are $1$ , then all steps of P are flat steps.
(2) Otherwise, there exists an index j such that $w_i=1$ for all $i<j$ and $w_j=2$ . Let k be the smallest integer such that $k>j$ and $w_k=2$ or $3$ .
1. (a) If there is no such k, or if $w_k$ is $2$ , set $P_{j-1}=U$ and $P_{j}=D$ . Create a new word $W'$ by removing the letters $w_{j-1}$ and $w_j$ .
2. (b) If $w_k$ is $3$ , set $P_{j-1}=U$ , $P_j=F$ and $P_k=D$ . Create a new word $W'$ by removing the letters $w_{j-1}$ , $w_j$ and $w_k$ .
(3) Repeat steps ( $1$ ) and ( $2$ ) until W is empty.

See Figure 2 for an example with $W=w_1 w_2 w_3 w_4 w_5 w_6 w_7 w_8=12132123 \in \mathcal {W}_3(8)$ . It follows from $w_2=2$ and $w_4=3$ that $P_1=U$ , $P_2=F$ , $P_4=D$ and $W'=w_3 w_5 w_6 w_7 w_8 =12123$ . In addition, $w_5=2$ and $w_7=2$ imply that $P_3=U$ , $P_5=D$ and $W"=w_6w_7w_8=123$ . Finally, from $w_7=2$ and $w_8=3$ , we have $P_6=U$ , $P_7=F$ , $P_8=D$ and $W"'=\emptyset $ . The resulting path is $P=\xi (W)=UFUDDUFD$ .

Figure 1

A standard Young tableau T and the corresponding Yamanouchi word $\chi (T)$ .

A three-row Standard Young tableau with entries 1,3,6 in row 1, 2,5,7 in row 2, and 4,8 in row 3 maps to the Yamanouchi word 1,2,1,3,2,1,2,3.

Figure 2

A Yamanouchi word W and the corresponding Motzkin path $P=\xi (W)$ .

A vertical sequence chart shows W, its derived forms, and a Motzkin path P with segments labeled U, F, D. Red highlights indicate elements removed at each step. See long description.

Figure 2 Long description

From top to bottom, this figure shows five rows. The first row shows the Yamanouchi word W, equals 1,2,1,3,2,1,2,3 with leftmost 1,2,3 in red. The second row shows W prime, equals 1,2,1,2,3 with leftmost 1,2 in red. The third row shows W double prime, equals 1,2,3 with 1,2,3 in red. The fourth row shows W triple prime, is blank. The fifth row shows the Motzkin path P, equals U,F,U,D,D,U,F,D.

In conclusion, $\xi \circ \chi $ is a bijection between $\mathfrak {S}(3,0;n)$ and $\mathcal {M}_n$ .

2.2 Results on $\mathfrak {S}_m(3,0;n)$ and $\mathfrak {S}_m(0,3;n)$

We now provide a path interpretation for $\mathfrak {S}_m(3,0;n)$ and $\mathfrak {S}_m(0,3;n)$ , and enumerate $\mathrm {S}_m(3,0;n)$ and $\mathrm {S}_m(0,3;n)$ . For nonnegative integers i and j, let $\mathcal {M}(i,j;n)$ be the set of lattice paths from $(i,j)$ to $(n,0)$ that stay weakly above the x-axis and consist of steps U, F and D. Note that $\mathcal {M}(i,j;n)=\emptyset $ when $i+j>n$ and $|\mathcal {M}(i,0;n)|=M_{n-i}$ for $i \le n$ .

Lemma 2.1. For nonnegative integers i and j, the cardinality of $\mathcal {M}(i,j;n)$ satisfies:

(i) $|\mathcal {M}(i,0;n)|=|\mathcal {M}(i+1,1;n)| + |\mathcal {M}(i+1,0;n)|$ for $i\le n-1$ ;
(ii) $|\mathcal {M}(i,j;n)|=|\mathcal {M}(i+1,j+1;n)| + |\mathcal {M}(i+1,j;n)| + |\mathcal {M}(i+1,j-1;n)|$ for $j\ge 1$ and $i+j \le n-1$ .

Proof. (i) Let $P=P_1P_2\cdots P_{n-i} \in \mathcal {M}(i,0;n)$ . Since P never goes below the x-axis, $P_1$ must be either U or F. Thus, $\tilde {P}=P_2\cdots P_{n-i}$ belongs to $\mathcal {M}(i+1,1;n)$ if $P_1=U$ and to $\mathcal {M}(i+1,0;n)$ if $P_1=F$ .

(ii) Let $P=P_1P_2 \cdots P_{n-i-j} \in \mathcal {M}(i,j;n)$ . In this case, $P_1$ can be U, F or D. The remainder of the proof is analogous to the proof of item (i).

Using Lemma 2.1, we provide an alternative proof of the following proposition.

Proposition 2.2 [Reference Eu3, Proposition 3.2]

For integers i and j with $0 \le j \le i$ , the cardinality of $\mathcal {M}(i,j;n)$ can be expressed as a linear combination of Motzkin numbers. In particular:

(i) $|\mathcal {M}(i,1;n)|=M_{n-i+1}-M_{n-i}$ for $i\ge 1$ ;
(ii) $|\mathcal {M}(i,2;n)|=M_{n-i+2}-2M_{n-i+1}$ for $i \ge 2$ .

Proof. By Lemma 2.1(i),

$$ \begin{align*} |\mathcal{M}(i,1;n)|=|\mathcal{M}(i-1,0;n)|-|\mathcal{M}(i,0;n)|=M_{n-i+1}-M_{n-i}. \end{align*} $$

Similarly, it follows from Lemma 2.1 that

$$ \begin{align*} |\mathcal{M}(i,2;n)|&=|\mathcal{M}(i-1,1;n)|-|\mathcal{M}(i,0;n)|-|\mathcal{M}(i,1;n)| \\ &=(M_{n-i+2}-M_{n-i+1})-M_{n-i}-(M_{n-i+1}-M_{n-i})=M_{n-i+2}-2M_{n-i+1}. \end{align*} $$

Applying Lemma 2.1 repeatedly, we can express $|\mathcal {M}(i,j;n)|$ as a linear combination of Motzkin numbers.

Recall that Eu [Reference Eu3, Theorem 3.1] proved $\mathrm {S}_3(3,0;n)=M_{n-1}-M_{n-3}$ using the bijection in Section 2.1 and Proposition 2.2. Now, we give Motzkin path interpretations for $\mathfrak {S}_2(3,0;n)$ and $\mathfrak {S}_4(3,0;n)$ to prove Theorem 1.3.

Theorem 2.3. There is a bijection between the set $\mathfrak {S}_2(3,0;n)$ and the set of Motzkin paths of length n that start with $FF$ , $FU$ or $UU$ . There is a bijection between the set $\mathfrak {S}_4(3,0;n)$ and the set of Motzkin paths of length n that start with $UFD$ .

Proof. For $T \in \mathfrak {S}(3,0;n)$ , let $W=\chi (T)=w_1w_2\cdots w_n$ and $P=\xi (W)=P_1P_2 \cdots P_n$ . When $T \in \mathfrak {S}_2(3,0;n)$ , W satisfies $w_1=w_2=1$ . Note that $P_i$ is either U or F when $w_i=1$ and $P_1P_2$ cannot be $UF$ according to the construction of $\xi $ . Therefore, $P_1P_2$ must be one of $FF$ , $FU$ or $UU$ .

When $T \in \mathfrak {S}_4(3,0;n)$ , W satisfies $w_1=1$ , $w_2=2$ , $w_3=3$ and $w_4=1$ . Hence, $P_1P_2P_3=UFD$ according to condition (2b) for $\xi $ .

Proof of Theorem 1.3

Applying Proposition 2.2 and Theorem 2.3, we get $\mathrm { S}_2(3,0;n)=|\mathcal {M}(2,0;n)|+|\mathcal {M}(2,1;n)|+|\mathcal {M}(2,2;n)|=M_{n-2}+(M_{n-1}-M_{n-2})+(M_n-2M_{n-1})=M_n-M_{n-1}$ . Similarly, we have $\mathrm {S}_4(3,0;n)=|\mathcal {M}(3,0;n)|=M_{n-3}$ .

Note that $\mathfrak {S}(k,\ell ;n)$ and $\mathfrak {S}(\ell ,k;n)$ are in bijection because ${\lambda } \in \mathcal {H}(k,\ell ;n)$ if and only if ${\lambda }' \in \mathcal {H}(\ell ,k;n)$ , where ${\lambda }'$ is the conjugate of ${\lambda }$ . However, $\mathfrak {S}_m(k,\ell ;n)$ and $\mathfrak {S}_m(\ell ,k;n)$ are different, in general. From the conjugation of a partition, we observe that $\mathfrak {S}^{(2,1)}_m(k,\ell ;n)$ and $\mathfrak {S}_m(\ell ,k;n)$ are in bijection. Thus, we consider the set $\mathfrak {S}^{(2,1)}_m(3,0;n)$ instead of $\mathfrak {S}_m(0,3;n)$ .

Theorem 2.4. For an integer $m\ge 2$ , there is a bijection between the set $\mathfrak {S}^{(2,1)}_m(3,0;n)$ and the set of Motzkin paths of length n that start with $F^i U^j D$ or $F^i U^j F$ , where $i\ge 0$ , $j\ge 1$ and $i+j=m-1$ .

Proof. For $T \in \mathfrak {S}(3,0;n)$ , let $W=\chi (T)=w_1w_2\cdots w_n$ and $P=\xi (W)=P_1P_2 \cdots P_n$ ; $T \in \mathfrak {S}^{(2,1)}_m(3,0;n)$ implies that $w_i=1$ for $i=1,2,\ldots ,m-1$ and $w_m=2$ . Similar to the proof of Theorem 2.3, $w_i=1$ for $i=1,2,\ldots ,m-1$ corresponds to $P_1P_2\cdots P_{m-1}=F^iU^j$ for $i\ge 0$ , $j\ge 1$ and $i+j=m-1$ . In addition, $w_m=2$ implies that $P_m$ is D or F according to condition (2) for $\xi $ .

In Figure 3, we give an example of Theorem 2.4. Using Proposition 2.2 and Theorem 2.4, we derive the following corollary.

Figure 3

A standard Young tableau $T\in \mathfrak {S}_4^{(2,1)}(3,0;8)$ , $W=\chi (T)$ and $P=\xi (W)$ .

A three-row Standard Young tableau with entries 1,2,3 in row 1, 4,5,7 in row 2, and 6,8 in row 3 maps to the Yamanouchi word 1,1,1,2,2,1,2,3, and the Motzkin path F,U,U,D,D,U,F,D.

Corollary 2.5. We have $\mathrm {S}_2(0,3;n)=M_{n-1}$ , $\mathrm {S}_3(0,3;n)=M_{n-1}-M_{n-3}$ and $\mathrm {S}_4(0,3;n)=M_{n-1}-M_{n-2}-M_{n-3}$ .

Proof. Let $T \in \mathfrak {S}(3,0;n)$ and $P=\xi \circ \chi (T)$ . By Theorem 2.4, $T \in \mathfrak {S}^{(2,1)}_2(3,0;n)$ if and only if P starts with $UD$ or $UF$ . Thus, $\mathrm { S}_2(0,3;n)=\mathrm {S}^{(2,1)}_2(3,0;n)=|\mathcal {M}(2,1;n)|+|\mathcal {M}(2,0;n)|= M_{n-1}$ . Similarly, $\mathrm {S}_3(0,3;n)=|\mathcal {M}(3,2;n)|+2|\mathcal {M}(3,1;n)|+|\mathcal {M}(3,0;n)|= M_{n-1}-M_{n-3}$ and $\mathrm {S}_4(0,3;n){\kern-1pt}={\kern-1pt}|\mathcal {M}(4,3;n)|{\kern-1pt}+{\kern-1pt}2|\mathcal {M}(4,2;n)|{\kern-1pt}+{\kern-1pt}2|\mathcal {M}(4,1;n)|{\kern-1pt}+{\kern-1pt}|\mathcal {M}(4,0;n)| = M_{n-1}-M_{n-2}-M_{n-3}$ .

In a similar manner, we can enumerate $\mathrm {S}_m(0,3;n)$ for all positive integers m. However, these numbers do not seem to follow a regular pattern. For example, we computed that $\mathrm {S}_5(0,3;n)= M_{n-1}-2M_{n-2}-M_{n-3}+2M_{n-4}$ and $\mathrm {S}_6(0,3;n)= M_{n-1}-3M_{n-2}+4M_{n-4}-M_{n-6}$ . We hope that an explicit formula for $\mathrm {S}_m(0,3;n)$ can be discovered in future research.

3 Classification of $\mathfrak {S}(2,1;n)$

In this section, we classify the set $\mathfrak {S}(2,1;n)$ .

3.1 The bijection between $\mathfrak {S}(2,1;n)$ and $\mathcal {FM}_n^D$

We summarise the bijection between $\mathfrak {S}(2,1;n)$ and $\mathcal {FM}_n^D$ , as presented in [Reference Du and Yu1, Sections 2 and 3]. Let ${W=w_1 w_2 \cdots w_n}$ be a word of length n, where $w_i \in \{0,1,2\}$ for all $i=1,2,\ldots ,n$ , and let $f_k(W)$ denote the number of k’s in W for $k=0,1,2$ . We call W a tight $012$ -word of length n if:

(1) $f_0(w_1 w_2 \cdots w_j) \ge f_2(w_1 w_2 \cdots w_j)$ for all $j=1,2,\ldots ,n$ ; and
(2) for each $j=1,2,\ldots ,n-1$ , $f_0(w_1 w_2 \cdots w_j)> f_2(w_1 w_2 \cdots w_j)$ whenever $w_{j+1}=1$ .

We denote by $\mathfrak {W}_n$ the set of all tight $012$ -words of length n and by $\mathfrak {W}^{(2)}_n$ the set of words in $\mathfrak {W}_n$ whose last nonzero number is $2$ if it exists.

We construct a map $\phi $ from $\mathfrak {S}(2,1;n)$ to $\mathfrak {W}^{(2)}_n$ . For $T\in \mathfrak {S}(2,1;n)$ , the corresponding word $W=\phi (T)\in \mathfrak {W}^{(2)}_n$ is constructed by the following rules.

(1) Let $A=\{a_1,a_2,\ldots ,a_{{\lambda }_1}\}$ be the set of entries in the first row of T and ${B=\{b_1,b_2,\ldots ,b_{n-{\lambda }_1}\}=[n]\setminus A}$ .
(2) Set $w_{a_i}=0$ for all $i=1,2,\ldots ,{\lambda }_1$ , $w_{b_{n-{\lambda }_1}}=2$ and
$$ \begin{align*}w_{b_i}= \begin{cases} 2 \quad \text{if } b_{i+1 } \text{ is in row } 2 \text{ of } T, \\ 1 \quad \text{otherwise}. \end{cases} \end{align*} $$

Du and Yu [Reference Du and Yu1] showed that $\phi $ is a bijection. Figure 4 illustrates a standard Young tableau $T\in \mathfrak {S}(2,1;8)$ and its corresponding tight $012$ -word $\phi (T)\in \mathfrak {W}^{(2)}_8$ .

Theorem 3.1 [Reference Du and Yu1, Theorem 2.1]

For any positive integer n, the map $\phi $ is a bijection between the sets $\mathfrak {S}(2,1;n)$ and $\mathfrak {W}^{(2)}_n$ such that, if $T \in \mathfrak {S}(2,1;n)$ has shape $({\lambda }_1,{\lambda }_2,1^{n-{\lambda }_1 -{\lambda }_2})$ , then $W=\phi (T)\in \mathfrak {W}^{(2)}_n$ satisfies $f_0(W)={\lambda }_1$ , $f_2(W)={\lambda }_2$ and ${f_1(W)=n-{\lambda }_1 - {\lambda }_2}$ .

Now, we describe the bijection $\psi $ between the sets $\mathfrak {W}_n$ and $\mathcal {FM}_n$ . Note that $\psi $ induces a bijection between $\mathfrak {W}^{(2)}_n$ and $\mathcal {FM}^D_n$ . (We only outline the injective map; for details, see [Reference Du and Yu1, Section 3].)

Figure 4

A standard Young tableau T and the corresponding tight $012$ -word $\phi (T)$ .

A five-row standard Young tableau with rows 1,3,6 in row 1, 2,4 in row 2, 5 in row 3, 7 in row 4, 8 in row 5 mpas to the tight 012-word 0,2,0,1,1,0,1,2.

Let $W=w_1 w_2 \cdots w_n \in \mathfrak {W}_n$ . The corresponding free Motzkin path $P=\psi (W)=P_1 P_2 \cdots P_n$ is constructed by the following steps.

(1) If $w_n=0$ , set $P_n=F$ and create a new word $W'$ by removing $w_n$ .
(2) If $w_n=1$ , let $w_j$ be the rightmost $0$ such that ${f_0(w_j \cdots w_n)=f_2(w_j \cdots w_n)+1}$ . In this case, we set $P_i=D,F,U$ when $w_i=0,1,2$ , respectively, for $i=j, j+1,\ldots ,n-1$ and $P_n=U$ . Create a new word $W'$ by removing the suffix $w_j w_{j+1} \cdots w_n$ .
(3) If $w_n=2$ , let $w_j$ be the rightmost $0$ such that $f_0(w_j \cdots w_n)=f_2(w_j \cdots w_n)$ . In this case, we set $P_i=U,F,D$ when $w_i=0,1,2$ , respectively, for $i=j,j+1,\ldots ,n$ . Similarly, we create a new word $W'$ by removing the suffix $w_j w_{j+1} \cdots w_n$ .
(4) Repeat steps ( $1$ ) to ( $3$ ) until W is empty.

See Figure 5 for an example with $W=02011012 \in \mathfrak {W}_8$ . Since $w_8=2$ and $f_0(012)=f_2(012)$ , we have $P_6=U$ , $P_7=F$ , $P_8=D$ and $W'=02011$ . Now, $w_5=1$ and $f_0(011)=f_2(011)+1$ imply that $P_3=D$ , $P_4=F$ , $P_5=U$ and $W"=02$ . Finally, it follows from $w_2=2$ and $f_0(02)=f_2(02)$ that $P_1=U$ and $P_2=D$ .

Figure 5

A tight 012-word W and the corresponding free Motzkin path $P=\psi (W)$ .

The tight 012-word 0,2,0,1,1,0,1,2 maps to the free Motzkin path U,D,D,F,U,U,F,D.

Thus, $\psi \circ \phi $ establishes a bijection between $\mathfrak {S}(2,1;n)$ and $\mathcal {FM}_n^D$ .

3.2 Results on $\mathfrak {S}_m(2,1;n)$ and $\mathfrak {S}_m(1,2;n)$

Now, we give lattice path interpretations for $\mathfrak {S}_m(2,1;n)$ and $\mathfrak {S}_m(1,2;n)$ . For integers i and j with $i \ge 0$ , let $\mathcal {F}(i,j;n)$ be the set of paths from $(i,j)$ to $(n,0)$ consisting of steps U, F and D. Note that $\mathcal {F}(i,j;n)=\emptyset $ if $i+|j|>n$ and $|\mathcal {F}(i,0;n)|=FM_{n-i}$ for $i \le n$ .

Lemma 3.2. For integers i and j with $i\ge 0$ , the cardinality of $\mathcal {F}(i,j;n)$ satisfies

$$ \begin{align*}|\mathcal{F}(i,j;n)|=|\mathcal{F}(i+1,j+1;n)|+|\mathcal{F}(i+1,j;n)|+|\mathcal{F}(i+1,j-1;n)|,\end{align*} $$

where $i+|j| \le n-1$ .

Proof. Let $P=P_1P_2\cdots P_{n-i-j} \in \mathcal {F}(i,j;n)$ and $\tilde {P}=P_2P_3 \cdots P_{n-i-j}$ . Since $P_1$ is either U, F or D, we have $\tilde {P} \in \mathcal {F}(i+1,j+1;n)$ if $P_1=U$ , $\tilde {P} \in \mathcal {F}(i+1,j;n)$ if $P_1=F$ , and $\tilde {P} \in \mathcal {F}(i+1,j-1;n)$ if $P_1=D$ .

Proposition 3.3. For a nonnegative integer i:

(i) $|\mathcal {F}(i,1;n)|+|\mathcal {F}(i,0;n)|+|\mathcal {F}(i,-1;n)|=FM_{n-i+1}$ for $i \le n-1$ ; and
(ii) $|\mathcal {F}(i,2;n)|+|\mathcal {F}(i,1;n)|+|\mathcal {F}(i,0;n)|+|\mathcal {F}(i,-1;n)|+|\mathcal {F}(i,-2;n)|$

$=FM_{n-i+2}-FM_{n-i+1}-FM_{n-i}$ for $i \le n-2$ .

Proof. Setting $j=0$ in Lemma 3.2 gives

$$ \begin{align*} |\mathcal{F}(i,1;n)|+|\mathcal{F}(i,0;n)|+|\mathcal{F}(i,-1;n)|=|\mathcal{F}(i-1,0;n)|=FM_{n-i+1}. \end{align*} $$

Similarly, setting $j=1$ and $j=-1$ in Lemma 3.2 gives

$$ \begin{align*} &|\mathcal{F}(i,2;n)|+|\mathcal{F}(i,1;n)|+|\mathcal{F}(i,0;n)|+|\mathcal{F}(i,-1;n)|+|\mathcal{F}(i,-2;n)| \\ &\quad=|\mathcal{F}(i-1,1;n)|+|\mathcal{F}(i-1,-1;n)|-|\mathcal{F}(i,0;n)|. \end{align*} $$

Applying item (i), we have $|\mathcal {F}(i-1,1;n)|+|\mathcal {F}(i-1,-1;n)|=FM_{n-i+2}-FM_{n-i+1}$ . Therefore, ${|\mathcal {F}(i{\kern-1pt}-{\kern-1pt}1,1;n)|{\kern-1pt}+{\kern-1pt}|\mathcal {F}(i{\kern-1pt}-{\kern-1pt}1,-1;n)|-|\mathcal {F}(i,0;n)|{\kern-1pt}={\kern-1pt}FM_{n-i+2}-FM_{n-i+1}-FM_{n-i}}$ .

We divide $\mathcal {F}(i,j;n)$ into two subsets, $\mathcal {F}^U(i,j;n)$ and $\mathcal {F}^D(i,j;n)$ . Let $\mathcal {F}^U(i,j;n)$ (respectively $\mathcal {F}^D(i,j;n)$ ) be the set of paths in $\mathcal {F}(i,j;n)$ whose last nonflat step is U (respectively D) if it exists. Note that $|\mathcal {F}^U(i,j;n)|=|\mathcal {F}^D(i,-j;n)|$ for integers i, j and n with $i,n\ge 0$ .

Corollary 3.4. For nonnegative integers i and n:

(i) $|\mathcal {F}^D(i,1;n)|+|\mathcal {F}^D(i,0;n)|+|\mathcal {F}^D(i,-1;n)|=FM^D_{n-i+1}$ for $i \le n-1$ ; and
(ii) $|\mathcal {F}^D(i,2;n)|+|\mathcal {F}^D(i,1;n)|+|\mathcal {F}^D(i,0;n)|+|\mathcal {F}^D(i,-1;n)|+|\mathcal {F}^D(i,-2;n)|$

$=FM^D_{n-i+2}-FM^D_{n-i+1}-FM^D_{n-i}$ for $i \le n-2$ .

Proof. It is clear that $|\mathcal {F}^U(i,1;n)|=|\mathcal {F}^D(i,-1;n)|$ , $|\mathcal {F}^U(i,-1;n)|=|\mathcal {F}^D(i,1;n)|$ and $|\mathcal {F}^U(i,0;n)|=|\mathcal {F}^D(i,0;n)|=(FM_{n-i}+1)/2$ . Therefore,

$$ \begin{align*} &|\mathcal{F}^D(i,1;n)|+|\mathcal{F}^D(i,0;n)|+|\mathcal{F}^D(i,-1;n)| \\ &\quad =(|\mathcal{F}(i,1;n)|+|\mathcal{F}(i,0;n)|+|\mathcal{F}(i,-1;n)|+1)/2=(FM_{n-i+1}+1)/2=FM^D_{n-i+1}. \end{align*} $$

The proof of item (ii) is almost the same and we omit it.

Now, we give a free Motzkin path interpretation for $\mathfrak {S}_m(2,1;n)$ for all $m \ge 2$ and prove Theorem 1.4.

Theorem 3.5. There is a bijection between the set $\mathfrak {S}_2(2,1;n)$ and the set of paths in $\mathcal {FM}^D_n$ that start with $UU$ , $FU$ , $FF$ , $FD$ or $DD$ . For $m\ge 3$ , there is a bijection between the set $\mathfrak {S}_m(2,1;n)$ and the set of paths in $\mathcal {FM}^D_n$ that start with $UF^{m-2}U$ , $DF^{m-3}UU$ , $DF^{m-3}UF$ , $DF^{m-3}UD$ , $DF^{m-2}D$ , $UF^{m-3}DU$ , $UF^{m-3}DF$ or $UF^{m-3}DD$ .

Proof. For $T \in \mathfrak {S}(2,1;n)$ , let $w=\phi (T)=w_1w_2\cdots w_n$ and $P=\psi (w)=P_1P_2 \cdots P_n$ . When $T\in \mathfrak {S}_2(2,1;n)$ , w satisfies $w_1=w_2=0$ . Note that $0$ in w corresponds to F at the x-axis, U above the x-axis and D below the x-axis in the corresponding path $P=\psi (w)$ . Thus, w satisfies $w_1=w_2=0$ if and only if P satisfies $P_1P_2=UU,FU,FF,FD$ or $DD$ .

Now, consider $T\in \mathfrak {S}_m(2,1;n)$ for $m\ge 3$ . From the construction of $\phi $ , the first m letters of w are $01^{m-3}20$ if $T(2,2)=m+1$ and $01^{m-2}0$ otherwise. Similarly, we note that $1$ in w corresponds to F except at the x-axis or U that ends at the x-axis, and $2$ in w corresponds to D above the x-axis or U below the x-axis that does not end at the x-axis. When $w \in \mathfrak {W}_n$ starts with $01^{m-2}0$ , P starts with $UF^{m-2}U$ , $DF^{m-3}UU$ , $DF^{m-3}UF$ , $DF^{m-3}UD$ or $DF^{m-2}D$ . When $w \in \mathfrak {W}_n$ starts with $01^{m-3}20$ , the corresponding path P starts with $UF^{m-3}DU$ , $UF^{m-3}DF$ or $UF^{m-3}DD$ .

For example, when $T\in \mathfrak {S}_3(2,1;n)$ in Figure 4, we can check that $P=\psi \circ \phi (T)$ starts with $UDU$ .

Proof of Theorem 1.4

It follows from Theorem 3.5 and Corollary 3.4 that

$$ \begin{align*} \mathrm{S}_2(2,1;n)&=|\mathcal{F}^D(2,2,0)|+|\mathcal{F}^D(2,1,0)|+|\mathcal{F}^D(2,0,0)| \\ &\quad +|\mathcal{F}^D(2,-1,0)|+|\mathcal{F}^D(2,-2,0)|\\ &=FM^D_{n}-FM^D_{n-1}-FM^D_{n-2}. \end{align*} $$

StartLayout 1st Row 1st Column normal upper S 2 left parenthesis 2 comma 1 semicolon n right parenthesis 2nd Column equals StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis 2 comma 2 comma 0 right parenthesis EndAbsoluteValue plus StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis 2 comma 1 comma 0 right parenthesis EndAbsoluteValue plus StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis 2 comma 0 comma 0 right parenthesis EndAbsoluteValue 2nd Row 1st Column Blank 2nd Column plus StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis 2 comma negative 1 comma 0 right parenthesis EndAbsoluteValue plus StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis 2 comma negative 2 comma 0 right parenthesis EndAbsoluteValue 3rd Row 1st Column Blank 2nd Column equals upper F upper M Subscript n Superscript upper D Baseline minus upper F upper M Subscript n minus 1 Superscript upper D Baseline minus upper F upper M Subscript n minus 2 Superscript upper D Baseline period EndLayout

Similarly, for $m\ge 3$ ,

$$ \begin{align*} \begin{aligned} \mathrm{S}_m(2,1;n)&=|\mathcal{F}^D(m,2,0)|+|\mathcal{F}^D(m,1,0)|+|\mathcal{F}^D(m,0,0)|+|\mathcal{F}^D(m,-1,0)| \\ &\quad +|\mathcal{F}^D(m,-2,0)|+|\mathcal{F}^D(m,1,0)|+|\mathcal{F}^D(m,0,0)|+|\mathcal{F}^D(m,-1,0)| \\ &=(FM_{n-m+2}^D-FM_{n-m+1}^D-FM_{n-m}^D)+FM_{n-m+1}^D =FM^{D}_{n-m+2}-FM^{D}_{n-m}. \end{aligned}\\[-42pt] \end{align*} $$

StartLayout 1st Row StartLayout 1st Row 1st Column normal upper S Subscript m Baseline left parenthesis 2 comma 1 semicolon n right parenthesis 2nd Column equals StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis m comma 2 comma 0 right parenthesis EndAbsoluteValue plus StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis m comma 1 comma 0 right parenthesis EndAbsoluteValue plus StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis m comma 0 comma 0 right parenthesis EndAbsoluteValue plus StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis m comma negative 1 comma 0 right parenthesis EndAbsoluteValue 2nd Row 1st Column Blank 2nd Column plus StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis m comma negative 2 comma 0 right parenthesis EndAbsoluteValue plus StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis m comma 1 comma 0 right parenthesis EndAbsoluteValue plus StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis m comma 0 comma 0 right parenthesis EndAbsoluteValue plus StartAbsoluteValue script upper F Superscript upper D Baseline left parenthesis m comma negative 1 comma 0 right parenthesis EndAbsoluteValue 3rd Row 1st Column Blank 2nd Column equals left parenthesis upper F upper M Subscript n minus m plus 2 Superscript upper D Baseline minus upper F upper M Subscript n minus m plus 1 Superscript upper D Baseline minus upper F upper M Subscript n minus m Superscript upper D Baseline right parenthesis plus upper F upper M Subscript n minus m plus 1 Superscript upper D Baseline equals upper F upper M Subscript n minus m plus 2 Superscript upper D Baseline minus upper F upper M Subscript n minus m Superscript upper D Baseline period EndLayout EndLayout

Similarly to Section 2, we consider the set $\mathfrak {S}^{(2,1)}_m(2,1;n)$ instead of $\mathfrak {S}_m(1,2;n)$ .

Lemma 3.6. For a positive integer $m\ge 2$ , there is a bijection between the set $\mathfrak {S}^{(1,m)}_m(2,1;n)$ and the set of paths in $\mathcal {FM}^D_n$ which start with $F^m$ , $F^i U^j$ or $F^i D^j$ with $i\ge 0$ , $j> 0$ and $i+j=m$ .

Proof. From the construction of $\phi $ , a standard Young tableau $T\in \mathfrak {S}^{(1,m)}_m(2,1;n)$ if and only if the corresponding tight $012$ -word $w=\phi (T)$ starts with m consecutive zeros. Recall that, for $P=\psi (w)$ , $0$ in w corresponds to F at the x-axis, U above the x-axis and D below the x-axis. Hence, w starts with m consecutive zeros if and only if $P=\psi (w)$ starts with $F^i U^j$ or $F^i D^j$ with $i>1$ , $j\ge 0$ and $i+j=m$ .

From Lemma 3.6, we get $\mathrm {S}^{(1,m)}_m(2,1;n)=\sum _{i=-m}^{m} |\mathcal {F}^D(m,i,0)|$ . We also have the following result using Corollary 3.4.

Corollary 3.7. We have $\mathrm {S}^{(1,3)}_3(2,1;n)=FM^D_n - 2FM^D_{n-1} -FM^D_{n-2} +2FM^D_{n-3}$ .

Proof. Putting $m=3$ in Lemma 3.6 gives $\mathrm {S}^{(1,3)}_3(2,1;n)=\sum _{i=-3}^{3} |\mathcal {F}^D(3,i,0)|$ . We first compute $\sum _{i=-3}^{3} |\mathcal {F}(3,i,0)|$ . By Lemma 3.2, it is clear that

$$ \begin{align*} |\mathcal{F}(2,i,0)|=|\mathcal{F}(3,i+1,0)|+|\mathcal{F}(3,i,0)|+|\mathcal{F}(3,i-1,0)| \end{align*} $$

for $i=-2,-1,0,1,2$ . Summing from $i=-2$ to $2$ ,

$$ \begin{align*} \sum_{i=-2}^{2}|\mathcal{F}(2,i,0)|=\sum_{i=-3}^{3} |\mathcal{F}(3,i,0)|+\sum_{i=-2}^{2} |\mathcal{F}(3,i,0)|+\sum_{i=-1}^{1} |\mathcal{F}(3,i,0)|. \end{align*} $$

By Proposition 3.3,

$$ \begin{align*} \sum_{i=-2}^{2}|\mathcal{F}(2,i,0)|&=FM_n-FM_{n-1}-FM_{n-2}, \\ \sum_{i=-2}^{2}|\mathcal{F}(3,i,0)|&=FM_{n-1}-FM_{n-2}-FM_{n-3}, \\ \sum_{i=-1}^{1}|\mathcal{F}(3,i,0)|&=FM_{n-2}. \end{align*} $$

StartLayout 1st Row 1st Column sigma summation Underscript i equals negative 2 Overscript 2 Endscripts StartAbsoluteValue script upper F left parenthesis 2 comma i comma 0 right parenthesis EndAbsoluteValue 2nd Column equals upper F upper M Subscript n Baseline minus upper F upper M Subscript n minus 1 Baseline minus upper F upper M Subscript n minus 2 Baseline comma 2nd Row 1st Column sigma summation Underscript i equals negative 2 Overscript 2 Endscripts StartAbsoluteValue script upper F left parenthesis 3 comma i comma 0 right parenthesis EndAbsoluteValue 2nd Column equals upper F upper M Subscript n minus 1 Baseline minus upper F upper M Subscript n minus 2 Baseline minus upper F upper M Subscript n minus 3 Baseline comma 3rd Row 1st Column sigma summation Underscript i equals negative 1 Overscript 1 Endscripts StartAbsoluteValue script upper F left parenthesis 3 comma i comma 0 right parenthesis EndAbsoluteValue 2nd Column equals upper F upper M Subscript n minus 2 Baseline period EndLayout

Therefore, $\sum _{i=-3}^{3} |\mathcal {F}(3,i,0)|=FM_n - 2FM_{n-1} -FM_{n-2} +2FM_{n-3}$ . Similarly to Corollary 3.4, $\sum _{i=-3}^{3} |\mathcal {F}^D(3,i,0)|=FM^D_n - 2FM^D_{n-1} -FM^D_{n-2} +2FM^D_{n-3}$ .

Corollary 3.8. We have $\mathrm {S}_2(1,2;n)=FM^D_{n-1}+FM^D_{n-2}$ and $\mathrm {S}_3(1,2;n)=FM^D_{n-1}-2FM^D_{n-3}$ .

Proof. If $T\in \mathfrak {S}_2^{(2,1)}(2,1;n)$ , then $T(1,2)\neq 2$ . Therefore, by Theorem 1.4,

$$ \begin{align*} \mathrm{S}_2(1,2;n)&=\mathrm{S}_2^{(2,1)}(2,1;n)=\mathrm{S}(2,1;n)-\mathrm{S}_2(2,1;n) \\ &=FM_n^D-(FM_n^D-FM_{n-1}^D-FM_{n-2}^D )=FM_{n-1}^D+FM_{n-2}^D. \end{align*} $$

If $T\in \mathfrak {S}_3^{(2,1)}(2,1;n)$ , then $T(1,2)=2$ and $T(1,3)\neq 3$ . Therefore,

$$ \begin{align*} \mathrm{S}_3(1,2;n)&=\mathrm{S}_3^{(2,1)}(2,1;n)=\mathrm{S}_2(2,1;n)-\mathrm{S}_3^{(1,3)}(2,1;n) \\ &=(FM_n^D-FM_{n-1}^D-FM_{n-2}^D )-(FM_n^D-2FM_{n-1}^D-FM_{n-2}^D+2FM_{n-3}^D ) \\ &=FM_{n-1}^D-2FM_{n-3}^D \end{align*} $$

StartLayout 1st Row 1st Column normal upper S 3 left parenthesis 1 comma 2 semicolon n right parenthesis 2nd Column equals normal upper S 3 Superscript left parenthesis 2 comma 1 right parenthesis Baseline left parenthesis 2 comma 1 semicolon n right parenthesis equals normal upper S 2 left parenthesis 2 comma 1 semicolon n right parenthesis minus normal upper S 3 Superscript left parenthesis 1 comma 3 right parenthesis Baseline left parenthesis 2 comma 1 semicolon n right parenthesis 2nd Row 1st Column Blank 2nd Column equals left parenthesis upper F upper M Subscript n Superscript upper D Baseline minus upper F upper M Subscript n minus 1 Superscript upper D Baseline minus upper F upper M Subscript n minus 2 Superscript upper D Baseline right parenthesis minus left parenthesis upper F upper M Subscript n Superscript upper D Baseline minus 2 upper F upper M Subscript n minus 1 Superscript upper D Baseline minus upper F upper M Subscript n minus 2 Superscript upper D Baseline plus 2 upper F upper M Subscript n minus 3 Superscript upper D Baseline right parenthesis 3rd Row 1st Column Blank 2nd Column equals upper F upper M Subscript n minus 1 Superscript upper D Baseline minus 2 upper F upper M Subscript n minus 3 Superscript upper D EndLayout

by Theorem 1.4 and Corollary 3.7.

Similarly, we can enumerate $\mathrm {S}_m(1,2;n)$ for $m\ge 4$ , but the computation is more complicated. We hope that there is an explicit formula for $\mathrm {S}_m(1,2;n)$ for each m.

Acknowledgement

We thank the referees for careful reading and valuable comments.

Footnotes

The first author was supported by NRF grant No. 2022R1I1A1A01072724. The second author was supported by NRF grant Nos. 2021R1C1C2007589 and RS–2026–25481081.

References

Du, R. R. X. and Yu, J., ‘Standard Young tableaux in a $\left(2,1\right)$

-hook and Motzkin paths’, Discrete Math. 344(7) (2021), Article no. 112395.Google Scholar

Ekhad, S. B. and Zeilberger, D., ‘Proof of a conjecture of Amitai Regev about three-rowed Young tableaux (and much more!)’, Preprint, 2006, available online at https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/regev.pdf.Google Scholar