\documentclass[12pt,reqno]{article}
 
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{tikz}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{url}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm)}}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\DeclareMathOperator{\SYT}{{\rm SYT}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}


\begin{center}
\vskip 1cm{\LARGE\bf Humps in Motzkin Paths and Standard\\
\vskip .1in
Young Tableaux in a $(2,1)$-Hook}
\vskip 1cm
\large
Xiaomei Chen\\
School of Mathematics and Statistics\\
Hunan University of Science and Technology\\
Xiangtan 411201\\
China\\
\href{mailto:email}{\tt xmchen@hnust.edu.cn} \\
\end{center}

\vskip .2 in
\begin{abstract}
  We calculate the number of humps and peaks in Motzkin paths with a given height, and calculate the number of standard Young tableaux (SYTs) in a $(2,1)$-hook with the difference of the first two parts fixed, which refine Regev's results. We also give new bijective proofs of Regev's results, and reveal some new recurrence relations related to humps, free Motzkin paths, and SYTs.
\end{abstract}

\section{Introduction}
A {\it Motzkin path} of order $n$ is a lattice path from $(0,0)$ to $(n,0)$, using up steps $U=(1,1)$, down steps $D=(1,-1)$ and flat steps $F=(1,0)$, and never going below the $x$-axis. A {\it free Motzkin path} is an unrestricted lattice path from $(0,0)$ to $(n,0)$ consisting of the steps $U$, $D$ and $F$. We use $\mathcal{M}_n$ to denote the set of all Motzkin paths of order $n$. The cardinality of $\mathcal{M}_n$ is the $n$th Motzkin number $m_n$, listed as \seqnum{A001006} in the On-Line Encyclopedia of Integer Sequences (OEIS) \cite{Sloane}.

A {\it hump} in a Motzkin path is a subpath of the form $UF^kD$ for some $k\in \mathbb{N}$. In particular, a hump with no flat steps is called a {\it peak}. See Figure~\ref{fig:0} for an example.
\begin{figure}[ht]
  \centering
  \begin{tikzpicture}[scale=0.6]
    \node[fill,circle,scale=0.5] at (0,0) (A1){};
    \node[fill,circle,scale=0.5] at (1,1) (A2){};
    \node[fill,circle,scale=0.5] at (2,1) (A3){};
    \node[red,fill,circle,scale=0.5] at (3,2) (A4){};
    \node[red,fill,circle,scale=0.5] at (4,2) (A5){};
    \node[red,fill,circle,scale=0.5] at (5,2) (A6){};
    \node[fill,circle,scale=0.5] at (6,1) (A7){};
    \node[blue,fill,circle,scale=0.5] at (7,0) (A8){};
    \node[blue,fill,circle,scale=0.5] at (8,1) (A9){};
    \node[blue,fill,circle,scale=0.5] at (9,0) (A10){};

    \node[above=5pt] at (4,2) (){$P_1$};
    \node[above=5pt] at (8,1) (){$P_2$};
    \draw plot coordinates {(A1) (A2) (A3)};
    \draw[red] plot coordinates {(A3) (A4) (A5) (A6) (A7)};
    \draw plot coordinates {(A7) (A8)};
    \draw[blue] plot coordinates {(A8) (A9) (A10)};
  \end{tikzpicture}
  \caption{An example of hump and peak, where the hump $P_1$ is colored red, and the peak $P_2$ is colored blue.}
\label{fig:0} 
\end{figure}

Let $H_{n}$ (OEIS \seqnum{A097861}) denote the total number of humps in all Motzkin paths of order $n$. Let $S_n$ (OEIS \seqnum{A002426}) denote the number of free Motzkin paths of order $n$. By applying the Wilf-Zeilberger method \cite{Petkovesk,Zeilberger}, Regev \cite{Regev1} proved that 
\begin{equation}\label{equ:1}
  H_n=\frac{1}{2}(S_n-1)=\frac{1}{2} \sum_{j\geq 1}\binom{n}{j}\binom{n-j}{j} .
\end{equation}
A bijective proof of (\ref{equ:1}) was given by Ding and Du~\cite{Ding}, and generalizations of this study to $(k,a)$-paths were given by Du, Nie and Sun~\cite{Du}, Mansour and Shattuck~\cite{Mansour}, and Yan~\cite{Yan}.

Regev pointed out that (\ref{equ:1}) is also related to the number of standard Young tableaux (SYT) in a $(2,1)$-hook, where a $(k,\ell)$-hook is a partition $\lambda=(\lambda_1,\lambda_2,\dots)$ with $\lambda_{k+1}\leq \ell$. Let $\SYT(k,\ell;n)$ denote the number of all SYTs with order equal to $n$ and shape being a $(k,\ell)$-hook. It is obvious that $\SYT(1,1;n)=2^{n-1}$. Regev \cite{Regev1,Regev2} proved that
\begin{equation}\label{equ:2}
  \SYT(2,1;n)-1=H_n=\frac{1}{2} \sum_{j\geq 1}\binom{n}{j}\binom{n-j}{j} .
\end{equation}
Du and Yu \cite{Du2} gave a bijective proof of (\ref{equ:2}) by showing that
\begin{equation*}
  \SYT(2,1;n)=\frac{1}{2}(S_n+1).
\end{equation*}

The goal of this paper is to reveal some further relations between humps of Motzkin paths and Young tableaux, and obtain some refinements of identities (\ref{equ:1}) and (\ref{equ:2}). The statistic {\it height} for a hump in a Motzkin path is defined to be the $y$-coordinate reached by the up step of the hump. Note that the number of peaks in Dyck paths with a given height has been studied in several papers~\cite{Mansour2, Peart}. We set
\begin{align*}
  \mathcal{H}_{n,k}&=\{(M,P)\mid M\in \mathcal{M}_n, \text{$P$\ is a hump of $M$ with height $k$}\},\\
  \mathcal{P}_{n,k}&=\{(M,P)\mid M\in \mathcal{M}_n, \text{$P$\ is a peak of $M$ with height $k$}\}.
\end{align*}
Let $H_{n,k}$ and $P_{n,k}$ denote the cardinality of $\mathcal{H}_{n,k}$ and $\mathcal{P}_{n,k}$, respectively.

To count humps with a given height, we consider a relation between humps and Motzkin prefixes. Here a {\it Motzkin prefix} is a lattice path that is a prefix of a Motzkin path. We let $\mathcal{M}_{n,k}$ denote the set of Motzkin prefixes from $(0,0)$ to $(n,k)$, and set 
\begin{align*}
  \mathcal{M}_{n,k}^{*U}&=\{M\mid M\in \mathcal{M}_{n,k}\ \text{whose last non-flat step is $U$}\},\\
  \mathcal{M}_{n,k}^{D*}&=\{M\mid M\in \mathcal{M}_{n,k}\ \text{whose first non-up step is $D$}\}.
\end{align*}
See the work of Krattenthaler and Yaqubi~\cite{Krattenthaler} as well as Yaqubi, Farrokhi Derakhshandeh Ghouchan and Ghasemian Zoeram~\cite{Yaqubi} for some further results on Motzkin prefix numbers.  

In Section \ref{sec:2}, by constructing a bijection from $\mathcal{H}_{n,k}$ to $\mathcal{M}_{n,2k}^{*U}$, we show that
  \begin{align}
    H_{n,k}&=S_{n,k},\label{equ:3}\\
    H_{n,k}&=\sum\limits_{i=2k-1}^{n-1}M_{i,2k-1},\label{equ:4}\\
    M_{n,2k}&=H_{n,k}+H_{n,k+1},\label{equ:5}
  \end{align}
where $S_{n,k}$ denotes the number of free Motzkin paths of order $n$ whose smallest $y$-coordinate is $-k$ and last non-flat step is $U$, and $M_{n,k}$ denotes the cardinality of $\mathcal{M}_{n,k}$ (OEIS \seqnum{A064189}). Note that Eq.~(\ref{equ:3}) can be viewed as a generalization of Eq.~(\ref{equ:1}).

Our first main result gives the following formulas for $H_{n,k}$ and $P_{n,k}$.
\begin{theorem}\label{thm:22}
  Let $H_{n,k}$ (resp., $P_{n,k}$) be the total number of humps (resp., peaks) with height~$k$ in all Motzkin paths of order $n$. Then for $n\geq 2$ and $k\geq 1$, we have
  \begin{align*}
    H_{n,k}&=\sum_{j=0}^{n-2k} [j\equiv \modd{n} {2}]\frac{4k}{n-j+2k}\binom{n}{j}\binom{n-j-1}{(n-j)/2+k-1},\\
    P_{n,k}&=\sum_{j=0}^{n-2k} [j\equiv \modd{n} {2}]\frac{4k}{n-j+2k}\binom{n-1}{j}\binom{n-j-1}{(n-j)/2+k-1},
  \end{align*}
  where $[P]$ is the Iverson bracket, equal to $1$ if $P$ holds and
  $0$ otherwise. 
  Moreover, the number $j$ in the sum tracks the number of flat steps of the Motzkin paths. 
\end{theorem}

We also consider a relation between SYTs contained in a $(2,1)$-hook and Motzkin prefixes. Let $\SYT_k(2,1;n)$ denote the number of SYTs with shape~$\lambda$, 
where $\lambda=(\lambda_1,\lambda_2,\dots)$ ranges over all $(2,1)$-hooks with $\lambda_1-\lambda_2=k$ and order equal to $n$. We first show that
\begin{equation}
  \SYT_{2k-1}(2,1;n+1)+\SYT_{2k-1}(2,1;n)=H_{n+1,k}-H_{n,k}.
\end{equation}
Then in Section \ref{sec:3}, we give a new bijective proof of (\ref{equ:2}), and obtain the following formula for $\SYT_k(2,1;n)$.
\begin{theorem}\label{thm:33}
For integers $n,k$ with $n-2\geq k\geq 0$, we have

\smallskip

\resizebox{.95\linewidth}{!}{
  \begin{minipage}{\linewidth}
    \begin{align*}
      & \SYT_k(2,1;n) \\
      &=(-1)^{n+k}+\sum_{i=0}^{\lfloor\frac{n-k-1}{2}\rfloor}\sum_{j=0}^{n-k-1-2i} [j\equiv \modd{n+k-1} {2}]
      \cdot \frac{2k+2}{n+k+1-2i-j}\binom{n-2i-2}{j}\binom{n-2i-j-1}{(n+k-j-1)/2-i}.
    \end{align*}
    \end{minipage}
}
\end{theorem}

\section{The number of humps and peaks with height $k$}\label{sec:2}
A Motzkin prefix $M$ of order $n$ can be represented as a word $M=w_1w_2\cdots w_n$ with $w_i\in\{U,D,F\}$. We use $\overline{M}$ to denote the path obtained from $M$ by reading the steps in reverse order and then swapping the $U$'s and $D$'s.
\begin{lemma}\label{lem:21}
  There is a bijection 
  \begin{equation*}
    \psi: \bigcup_{1\leq k\leq \lfloor\frac{n}{2}\rfloor}\mathcal{H}_{n,k}\mapsto \bigcup_{1\leq k\leq \lfloor\frac{n}{2}\rfloor}\mathcal{M}_{n,2k}^{*U},
  \end{equation*}
  such that $(M, P)\in \mathcal{H}_{n,k}$ if and only if $\psi(M, P)\in \mathcal{M}_{n,2k}^{*U}$. In particular, the subpath $P$ is a peak of $M$ if and only if $\psi(M, P)$ ends with an up step.
\end{lemma}
\begin{proof}
  Given $(M,P)\in \mathcal{H}_{n,k}$, we assume that $P=UF^rD$, and decompose $M$ as $M=M_1PM_2$. Let  
  \begin{equation*}
    \psi(M,P)=M_1U\overline{M_2}UF^r.
  \end{equation*}
  It is not difficult to see that $\psi(M,P)\in \mathcal{M}_{n,2k}^{*U}$. In particular, if $M=M_1PM_2$ with $P=UD$ a peak, then $\psi(M,P)=M_1U\overline{M_2}U$ ends with an up step. See Figure \ref{fig:1} for an example of $\psi$.
  \begin{figure}[ht]
    \centering
    \begin{tikzpicture}[scale=0.5]
      \node[fill,circle,scale=0.5] at (0,0) (A1){};
      \node[fill,circle,scale=0.5] at (1,1) (A2){};
      \node[fill,circle,scale=0.5] at (2,1) (A3){};
      \node[red,fill,circle,scale=0.5] at (3,2) (A4){};
      \node[red,fill,circle,scale=0.5] at (4,2) (A5){};
      \node[red,fill,circle,scale=0.5] at (5,2) (A6){};
      \node[fill,circle,scale=0.5] at (6,1) (A7){};
      \node[fill,circle,scale=0.5] at (7,0) (A8){};
      \node[fill,circle,scale=0.5] at (8,1) (A9){};
      \node[fill,circle,scale=0.5] at (9,0) (A10){};
  
      \node[above=5pt] at (1,1) (){$M_1$};
      \node[above=5pt] at (4,2) (){$P$};
      \node[above=5pt] at (8,1) (){$M_2$};
      \draw plot coordinates {(A1) (A2) (A3)};
      \draw[red] plot coordinates {(A3) (A4) (A5) (A6) (A7)};
      \draw plot coordinates {(A7) (A8) (A9) (A10)};
  
      \path[line width=1.5pt, ->] (9.5,1) edge node [above] {$\psi$} (11,1);
  
      \node[fill,circle,scale=0.5] at (12,0) (B1){};
      \node[fill,circle,scale=0.5] at (13,1) (B2){};
      \node[fill,circle,scale=0.5] at (14,1) (B3){};
      \node[fill,circle,scale=0.5] at (15,2) (B4){};
      \node[fill,circle,scale=0.5] at (16,3) (B5){};
      \node[fill,circle,scale=0.5] at (17,2) (B6){};
      \node[fill,circle,scale=0.5] at (18,3) (B7){};
      \node[red,fill,circle,scale=0.5] at (19,4) (B8){};
      \node[red,fill,circle,scale=0.5] at (20,4) (B9){};
      \node[red,fill,circle,scale=0.5] at (21,4) (B10){};
      \draw plot coordinates {(B1) (B2) (B3)};
      \draw[red] plot coordinates {(B3) (B4)};
      \draw plot coordinates {(B4) (B5) (B6) (B7)};
      \draw[red] plot coordinates {(B7) (B8) (B9) (B10)};
  
      \node[above=5pt] at (13,1) (){$M_1$};
      \node[below=5pt] at (17,2) (){$\overline{M_2}$};
  
    \end{tikzpicture}
    \caption{An example of $\psi$ with $(M,P)\in \mathcal{H}_{9,2}$, where the hump $P$ is colored red.}
  \label{fig:1} 
  \end{figure}

  Conversely, given $M\in \mathcal{M}_{n,2k}^{*U}$, let $M=M_1UM_2UF^r$ be the decomposition of $M$, such that the rightmost endpoint of $M_1$ is the last endpoint of $M$ with $y$-coordinate $k-1$. Then we have $\psi^{-1}(M)=(M_1UF^rD\overline{M_2},P)$, where~$P$ is the hump connecting $M_1$ and $\overline{M_2}$.
\end{proof}

Similar to the proof of Lemma \ref{lem:21}, we can give a bijective proof of 
Eq.~(\ref{equ:3}).
 \begin{proof}[Proof of Eq.~(\ref{equ:3})]
  Given $(M,P)\in \mathcal{H}_{n,k}$, assume that $P=UF^rD$. We decompose $M$ as $M=M_1PM_2$, and define  
  \begin{equation*}
    \psi_1(M,P)=M_2DM_1UF^r.
  \end{equation*}
  It is not difficult to check that $\psi_1$ is a bijection from $\mathcal{H}_{n,k}$ to the set of free Motzkin paths of order $n$ whose smallest $y$-coordinate is $-k$ and last non-flat step is $U$, which implies Eq.~(\ref{equ:3}).
 \end{proof} 

Eqs.~(\ref{equ:4}) and (\ref{equ:5}) can be deduced from Lemma \ref{lem:21}.
\begin{proof}[Proof of Eqs.~(\ref{equ:4}) and (\ref{equ:5})]
   Given $P\in\mathcal{M}_{n,2k}^{*U}$, we assume that $P=M_1UH^r$, and define $\psi_2(P)=M_1$. It is not difficult to check that 
   \begin{equation*}
    \psi_2: \mathcal{M}_{n,2k}^{*U}\longrightarrow \bigcup\limits_{i=2k-1}^{n-1}\mathcal{M}_{i,2k-1}
   \end{equation*}
   is a bijection. Thus, Eq.~(\ref{equ:4}) can be deduced from Lemma \ref{lem:21}. 
 
   On the other hand, given $P\in \mathcal{M}_{n,2k}$, we define $\psi_3(P)$ as follows.
   \begin{itemize}
    \item If $P\in\mathcal{M}_{n,2k}^{*U}$, we define $\psi_3(P)=P$.
    \item If the last non-flat step of $P$ is $D$, we define $\psi_3(P)$ to be the path obtained from $P$ by replacing the last $D$ step with $U$.
   \end{itemize}
  Then $\psi_3$ is a bijection from $\mathcal{M}_{n,2k}$ to the union of $\mathcal{M}_{n,2k}^{*U}$ and $\mathcal{M}_{n,2k+2}^{*U}$, and Eq.~(\ref{equ:5}) follows.
 \end{proof}

We are now ready to give the proof of Theorem \ref{thm:22}. A {\it Dyck prefix} is a Motzkin prefix with no flat steps. It is well known that the number of Dyck paths of semilength $n$ ending with $UD^m$ is counted by $\frac{m}{n}\binom{2n-m-1}{n-1}$, which is also equal to the number of Dyck prefixes from $(0,0)$ to $(2n-m,m)$ ending with $U$. See the OEIS \seqnum{A033184}.

\begin{proof}[Proof of Theorem \ref{thm:22}]
  A path $M\in\mathcal{M}_{n,2k}^{*U}$ with $j$ flat steps can be obtained uniquely by inserting $j$ flat steps into $n-j+1$ positions of a Dyck prefix from $(0,0)$ to $(n-j,2k)$ ending with $U$. In particular, the path $M$ ends with an up step if and only if the above insertion is not allowed at the end of the path. Combining the above fact and Lemma \ref{lem:21}, we obtain the identities in Theorem \ref{thm:22}.     
\end{proof}
\begin{table}[th]
\begin{center}
\begin{tabular}{c|cccccc}
&$k=1$&$2$&$3$&$4$&$5$&$6$\\\hline
$n=2$&1&&&&&\\
$3$&3&&&&&\\
$4$&8&1&&&&\\
$5$&20&5&&&&\\
$6$&50&19&1&&&\\
$7$&126&63&7&&&\\
$8$&322&196&34&1&&\\
$9$&834&588&138&9&&\\
$10$&2187&1728&507&53&1&\\
$11$&5797&5016&1749&253&11&\\
$12$&15510&14454&5786&1067&76&1
\end{tabular}\caption{The first few entries of $(H_{n,k})_{n,k\in \mathbb{N}}$.}
\end{center}\vspace{-0.8cm}
\end{table}
\begin{remark}
 The sequences $(H_{n,k})_{n\geq 2,k\geq 1}$ and $(H_{n,1})_{n\geq 1}$ are entries \seqnum{A379838} and \seqnum{A140662} in the OEIS \cite{Sloane}, respectively.
\end{remark}

We can also consider the generating function of $(H_{n,k})_{n\geq 2,k\geq 1}$. For fixed~$k$, it is well known that the generating function of $(M_{n,k})_{n\geq k}$ is
\begin{equation}\label{equ:2.1}
  \sum_{n\geq k}M_{n,k}x^n=x^kM^{k+1}(x),
\end{equation} 
where $M(x)$ is the generating function of the Motzkin numbers. See \seqnum{A064189} in the OEIS \cite{Sloane} for instance. Combining Eqs.~(\ref{equ:5}) and (\ref{equ:2.1}), we obtain the following result.
\begin{corollary}
  The lower triangular array $(H_{n,k})_{n,k\in \mathbb{N}}$ is the Riordan array $(\frac{1}{1-x}, x^2M^2(x))$. Equivalently, for $k\geq 1$, we have
  \begin{equation*}
    \sum_{n\geq 2k}H_{n,k}x^n=\frac{x^{2k}M^{2k}(x)}{1-x},
  \end{equation*}
  where $M(x)$ is the generating function of the Motzkin numbers.
\end{corollary}

\section{The number of SYTs in a $(2,1)$-hook}\label{sec:3}
In this section, our first goal is to give a new bijective proof of Eq.~(\ref{equ:2}). Let $\mathcal{S}_k(2,1;n)$ denote the set of SYTs with shape $\lambda$, 
where $\lambda=(\lambda_1,\lambda_2,\dots)$ ranges over all $(2,1)$-hooks with $\vert \lambda\vert=n$ and $\lambda_1-\lambda_2=k$. Given
\begin{equation*}
  T\in \bigcup_{0\leq k\leq n-2}\mathcal{S}_k(2,1;n),
\end{equation*}
we define $\phi(T)=w_1w_2\cdots w_n$, where
\begin{displaymath}
  w_i=\begin{cases}
    U, &\text{if $i$ appears in the first row of $T$;}\\
    D, &\text{if $i$ appears in the second row of $T$;}\\
    F, &\text{otherwise.}
  \end{cases}
\end{displaymath}

It is obvious that
\begin{equation*}
  \phi: \bigcup_{0\leq k\leq n-2}\mathcal{S}_k(2,1;n) \mapsto \bigcup_{0\leq k\leq n-2}\mathcal{M}_{n,k}^{D*}
\end{equation*}
is a bijection. Therefore, to prove Eq.~(\ref{equ:2}), it is sufficient to prove the following result.
\begin{lemma}
  There is a bijection
  \begin{equation*}
    \varphi: \bigcup_{0\leq k\leq n-2}\mathcal{M}_{n,k}^{D*}\mapsto \bigcup_{1\leq k\leq \lfloor\frac{n}{2}\rfloor}\mathcal{M}_{n,2k}^{*U}.
  \end{equation*}
\end{lemma}
\begin{proof}
  Given $0\leq k\leq n-2$ and $M\in \mathcal{M}_{n,k}^{D*}$, we define $\varphi(M)$ as follows.
  \begin{itemize}
    \item If $k$ is odd, we assume that $M=U^{r}DM_1$, and define $\varphi(M)=U^{r-1}FM_1U$.
    \item If $k$ is even, we define $\varphi(M)$ as follows.
    \begin{itemize}
      \item[*] If the last non-flat step of $M$ is $U$, then $\varphi(M)=M$.
      \item[*] If $M=U^{r_1}DM_1DF^{r_2}$, then $\varphi(M)=U^{r_1-1}FM_1UF^{r_2+1}$.
      \item[*] If $M=U^{r_1}DF^{r_2}$, then $\varphi(M)=U^{r_1+1}F^{r_2}$. 
    \end{itemize}
  \end{itemize}

  Conversely, given $1\leq k\leq \lfloor\frac{n}{2}\rfloor$ and $M\in \mathcal{M}_{n,2k}^{*U}$, we can obtain $\varphi^{-1}(M)$ in the following way.
  \begin{itemize}
    \item If the first non-up step of $M$ is $D$, we have $\varphi^{-1}(M)=M$. 
    \item If the first non-up step of $M$ is $F$ or $M=U^n$, we obtain $\varphi^{-1}(M)$ as follows.
    \begin{itemize}
      \item[*] If $M=U^rFM_1U$, then $\varphi^{-1}(M)=U^{r+1}DM_1$.
      \item[*] If $M=U^{r_1}FM_1UF^{r_2}$ with $r_2\geq 1$, then
      \begin{equation*}
        \varphi^{-1}(M)=U^{r_1+1}DM_1DF^{r_2-1}.
      \end{equation*}
      \item[*] If $M=U^{2k}F^{n-2k}$, then $\varphi^{-1}(M)=U^{2k-1}DF^{n-2k}$.
    \end{itemize}
  \end{itemize} 
\end{proof} 

We define
$$\varPhi: \bigcup_{1\leq k\leq \lfloor\frac{n}{2}\rfloor}\mathcal{H}_{n,k}\mapsto \bigcup_{0\leq k\leq n-2}\mathcal{S}_k(2,1;n)$$
as $\varPhi=\phi^{-1} \circ \varphi^{-1} \circ \psi$. Then $\varPhi$
is a bijection, which implies a bijective proof of Eq.~(\ref{equ:2}). See Figure \ref{fig:2} for an example.
\begin{figure}[th]
    \centering
    \begin{tikzpicture}[scale=0.5]
      \node[fill,circle,scale=0.5] at (0,0) (A1){};
      \node[fill,circle,scale=0.5] at (1,1) (A2){};
      \node[fill,circle,scale=0.5] at (2,1) (A3){};
      \node[red,fill,circle,scale=0.5] at (3,2) (A4){};
      \node[red,fill,circle,scale=0.5] at (4,2) (A5){};
      \node[red,fill,circle,scale=0.5] at (5,2) (A6){};
      \node[fill,circle,scale=0.5] at (6,1) (A7){};
      \node[fill,circle,scale=0.5] at (7,0) (A8){};
      \node[fill,circle,scale=0.5] at (8,1) (A9){};
      \node[fill,circle,scale=0.5] at (9,0) (A10){};
  
      \node[above=0pt] at (4,0) () {$(M,P)$};
      \draw[line width=1.5pt, ->] (4,-0.5) --node [right] {$\varPhi$} (4,-2);

      \draw plot coordinates {(A1) (A2) (A3)};
      \draw[red] plot coordinates {(A3) (A4) (A5) (A6) (A7)};
      \draw plot coordinates {(A7) (A8) (A9) (A10)};

      \draw[line width=1.5pt, ->] (9.5,1) --node [above] {$\psi$} (11.5,1);

      \node[fill,circle,scale=0.5] at (12,0) (B1){};
      \node[fill,circle,scale=0.5] at (13,1) (B2){};
      \node[fill,circle,scale=0.5] at (14,1) (B3){};
      \node[fill,circle,scale=0.5] at (15,2) (B4){};
      \node[fill,circle,scale=0.5] at (16,3) (B5){};
      \node[fill,circle,scale=0.5] at (17,2) (B6){};
      \node[fill,circle,scale=0.5] at (18,3) (B7){};
      \node[fill,circle,scale=0.5] at (19,4) (B8){};
      \node[fill,circle,scale=0.5] at (20,4) (B9){};
      \node[fill,circle,scale=0.5] at (21,4) (B10){};
      \draw plot coordinates {(B1) (B2) (B3)};
      \draw plot coordinates {(B3) (B4)};
      \draw plot coordinates {(B4) (B5) (B6) (B7)};
      \draw plot coordinates {(B7) (B8) (B9) (B10)};


      \draw[line width=1.5pt, ->] (16,-0.5) --node [right] {$\varphi^{-1}$} (16,-2);

      \node[fill,circle,scale=0.5] at (12,-5.5) (C1){};
      \node[fill,circle,scale=0.5] at (13,-4.5) (C2){};
      \node[fill,circle,scale=0.5] at (14,-3.5) (C3){};
      \node[fill,circle,scale=0.5] at (15,-4.5) (C4){};
      \node[fill,circle,scale=0.5] at (16,-3.5) (C5){};
      \node[fill,circle,scale=0.5] at (17,-2.5) (C6){};
      \node[fill,circle,scale=0.5] at (18,-3.5) (C7){};
      \node[fill,circle,scale=0.5] at (19,-2.5) (C8){};
      \node[fill,circle,scale=0.5] at (20,-3.5) (C9){};
      \node[fill,circle,scale=0.5] at (21,-3.5) (C10){};

      \draw plot coordinates {(C1) (C2) (C3)(C4) (C5) (C6) (C7)(C8) (C9) (C10)};
  
      \draw[line width=1.5pt, ->]  (11.5,-4)--node [above] {$\phi^{-1}$} (9.5,-4);
      \foreach \x in {2.5,...,6.5}
        \foreach \y in {-3}
        {
          \draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
        }
      \foreach \x in {2.5,...,4.5}
        \foreach \y in {-4}
        {
          \draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
        }

      \draw (2.5,-5) +(-.5,-.5) rectangle ++(.5,.5);

      \draw (2.5,-3) node{1};
      \draw (3.5,-3) node{2};
      \draw (4.5,-3) node{4};
      \draw (5.5,-3) node{5};
      \draw (6.5,-3) node{7};

      \draw (2.5,-4) node{3};
      \draw (3.5,-4) node{6};
      \draw (4.5,-4) node{8};

      \draw (2.5,-5) node{9};
    \end{tikzpicture}
    \caption{An example of $\varPhi$ with $(M,P)\in \mathcal{H}_{9,2}$, where the hump $P$ is colored red.}
  \label{fig:2} 
\end{figure}

Next we calculate $\SYT_k(2,1;n)$. Let 
\begin{equation*}
  T_{n,k}=\SYT_{k}(2,1;n)+(-1)^{n+k+1},
\end{equation*}
where we set $T_{0,0}=0$. We have the following result for the generating function of $(T_{n,k})_{n\geq k}$ for fixed $k$.
\begin{lemma}\label{lem:32}
  The lower triangular array $(T_{n,k})_{n,k\in \mathbb{N}}$ is the Riordan array $(\frac{xM(x)}{1+x}, xM(x))$. Equivalently, we have
  \begin{equation*}
    T_k(x)=\sum_{n\geq k} T_{n,k}x^n=\frac{1}{1+x}(xM(x))^{k+1},
  \end{equation*}
  where $M(x)$ is the generating function of the Motzkin numbers.
\end{lemma}
\begin{proof}
For $n\geq k$, we first show that
  \begin{equation}\label{rec:31}
    T_{n+1,k}+T_{n,k}=M_{n,k}.
  \end{equation}
It is obvious that $T_{k,k}=0$ and $T_{k+1,k}=1$ for $k\geq 0$, which implies (\ref{rec:31}) for $n=k$. For $n> k$ and $M\in \mathcal{M}_{n,k}$, we define $\varphi_1(M)$ as follows.
\begin{itemize}
  \item If $M\in \mathcal{M}_{n,k}^{D*}$, we define $\varphi_1(M)=M$.
  \item If $M=U^rFM_1$, we define $\varphi_1(M)=U^{r+1}DM_1$.
\end{itemize}
It is not difficult to check that 
\begin{equation*}
  \varphi_1: \mathcal{M}_{n,k}\mapsto \mathcal{M}_{n+1,k}^{D*}\bigcup \mathcal{M}_{n,k}^{D*}
\end{equation*}
is a bijection. Since the left-hand side of (\ref{rec:31}) counts the number of paths in $\mathcal{M}_{n+1,k}^{D*}\bigcup \mathcal{M}_{n,k}^{D*}$, and the right-hand side counts the number of paths in $\mathcal{M}_{n,k}$, we obtain the recurrence relation (\ref{rec:31}).

Combining Eqs.~(\ref{equ:2.1}) and (\ref{rec:31}), we obtain Lemma \ref{lem:32}.
\end{proof}

\begin{remark}
  For $k=0$ and $k=1$, the sequences $(T_{n,k})_{n\geq k}$ are entries \seqnum{A187306} and \seqnum{A284778} in the OEIS \cite{Sloane}, respectively.
\end{remark}

As a direct consequence of Lemma \ref{lem:32}, we have the following result.
\begin{corollary}
For integers $k\geq 0$, we have
\begin{equation}
  \sum_{n\geq k}\SYT_k(2,1;n)x^n=\frac{x^k}{1+x}(1+xM^{k+1}(x)),
\end{equation}
 where $M(x)$ is the generating function of the Motzkin numbers.
\end{corollary}

The proof of Eq.~(\ref{rec:31}) also implies a bijective proof of the following recurrence relation.
\begin{corollary}
For $1\leq k\leq  \lfloor\frac{n}{2}\rfloor$, we have
\begin{equation*}
  \SYT_{2k-1}(2,1;n+1)+\SYT_{2k-1}(2,1;n)=H_{n+1,k}-H_{n,k}.
\end{equation*}
\end{corollary}
\begin{proof}
  By the proof of (\ref{rec:31}), the left-hand side counts the number of paths in $\mathcal{M}_{n,2k-1}$. By Lemma \ref{lem:21}, the right-hand side counts the number of paths in $\mathcal{M}_{n+1,2k}^{*U}$ ending with $U$, which is also equal to the number of paths in $\mathcal{M}_{n,2k-1}$.
\end{proof}

We are now ready to give the proof of Theorem \ref{thm:33}. The weight $w$ of~a Motzkin prefix $M\in \mathcal{M}_{n,k}^{*U}$ is defined as $w(M)=(-1)^r$, where $r$ is the number of flat steps after the last up step.
\begin{proof}[Proof of Theorem \ref{thm:33}]
  By Lemma \ref{lem:32}, we have 
  \begin{equation*}
    T_{n,k}=\sum_{M\in \mathcal{M}_{n,k+1}^{*U}}w(M).
  \end{equation*}

Given $M\in \mathcal{M}_{n,k+1}^{*U}$ with weight $-1$, we define $\varphi_2(M)$ to be the path obtained from $M$ by moving the last flat step to the beginning. Then $\varphi_2$ is~a bijection from the set of paths in $\mathcal{M}_{n,k+1}^{*U}$ with weight $-1$ to those with weight $1$ beginning with a flat step. 

As a consequence of the above bijection, we know that $T_{n,k}$ equals the number of paths in $\mathcal{M}_{n,k+1}^{*U}$ beginning with $U$ and ending with an even number of flat steps. Since those paths can be obtained from the corresponding Dyck prefixes by inserting an even number of flat steps to the end and inserting some flat steps between the first up step and the last up step, we obtain the identity in Theorem \ref{thm:33}.
\end{proof}
\begin{table}[th]
\begin{center}
\begin{tabular}{c|ccccccccc}
&$k=0$&$1$&$2$&$3$&$4$&$5$&$6$&$7$&$8$\\\hline
$n=0$&1&&&&&&&&\\ 
$1$&0&1&&&&&&&\\ 
$2$&1&0&1&&&&&&\\ 
$3$&1&2&0&1&&&&&\\ 
$4$&3&3&3&0&1&&&&\\ 
$5$&6&9&6&4&0&1&&&\\ 
$6$&15&21&19&10&5&0&1&&\\ 
$7$&36&55&50&34&15&6&0&1&\\ 
$8$&91&141&139&99&55&21&7&0&1
\end{tabular}\caption{The first few entries of $(\SYT_k(2,1;n))_{n,k\in\mathbb{N}}$.}
\end{center}\vspace{-0.8cm}
\end{table}
\begin{remark}
  The sequence $(\SYT_k(2,1;n))_{n\geq k}$ is entry \seqnum{A379893} in the OEIS \cite{Sloane}. The sequence $(\SYT_0(2,1;n))_{n\geq 0}$ gives a standard-Young-tableaux interpretation of Riordan numbers, which was first pointed out by Regev (OEIS \seqnum{A005043}).
\end{remark}

\section{Acknowledgments}
The author was supported by the {\it Natural Science Foundation of Hunan Province} (No.\ 2021JJ40186). We greatly appreciate the referees for their valuable comments and helpful suggestions adopted in this revised version. We are also grateful to anonymous for providing helpful advice that improved some of the paper's results.

\begin{thebibliography}{10}
\bibitem{Ding}
Y. Ding and R. R. X. Du, Counting humps in Motzkin paths, \emph{Discrete Appl. Math.} \textbf{160} (2012), 187--191.
\bibitem{Du}
R. R. X. Du, Y. Nie, and X. Sun, Enumerations of humps and peaks in $(k, a)$-paths and $(n, m)$-Dyck paths via bijective proofs, \emph{Discrete Appl. Math.} \textbf{190-191} (2015), 42--49.
\bibitem{Du2}
R. R. X. Du and J. Yu, Standard Young tableaux in a $(2,1)$-hook and Motzkin paths, \emph{Discrete Math.} \textbf{344} (2021), 112395.
\bibitem{Krattenthaler}
C. Krattenthaler and D. Yaqubi, Some determinants of path generating functions, II, \emph{Adv. Appl. Math.} \textbf{101} (2018), 232--265.
\bibitem{Mansour}
T. Mansour and M. Shattuck, Counting humps and peaks in generalized Motzkin paths, \emph{Discrete Appl. Math.} \textbf{161} (2013), 2213--2216.
\bibitem{Mansour2}
T. Mansour, Counting peaks at height $k$ in a Dyck path, \emph{J. Integer Sequences} \textbf{5} (2002), \href{https://cs.uwaterloo.ca/journals/JIS/VOL5/Mansour/mansour6.html}{Article 02.1.1}.
\bibitem{Peart}
P. Peart and W. J. Woan, Dyck paths with no peaks at height $k$, \emph{J. Integer Sequences} \textbf{4} (2001), \href{https://cs.uwaterloo.ca/journals/JIS/VOL4/PEART/pwatjis2.html}{Article 01.1.3}.
\bibitem{Petkovesk}
M. Petkov\v{s}ek, H. S. Wilf, and D. Zeilberger, \textit{$A=B$}, A. K. Peters, 1996.
\bibitem{Regev1}
A. Regev, Humps for Dyck and for Motzkin paths, arxiv preprint arXiv:1002.4504 [math.CO], 2010. \newblock{Available at \url{http://arxiv.org/abs/1002.4504}}.
\bibitem{Regev2}
A. Regev, Probabilities in the $(k, l)$-hook, \emph{Israel J. Math.} \textbf{169} (2009), 61--88.
\bibitem{Sloane}
N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2024. \newblock{Available at \url{https://oeis.org}}.
\bibitem{Yan}
S. H. F. Yan, Bijective counting of humps and peaks in $(k, a)$-paths, \emph{Discrete Appl. Math.} \textbf{193} (2015), 208--212.
\bibitem{Yaqubi}
D. Yaqubi, M. Farrokhi Derakhshandeh Ghouchan, and H. Ghasemian Zoeram, Lattice paths inside a table, \emph{Math. Commun.} \textbf{28} (2023), 181--201.
\bibitem{Zeilberger}
D. Zeilberger, The method of creative telescoping, \emph{J. Symbolic Comput.} \textbf{11} (1991), 195--204.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}: Primary 05A15;  Secondary 05A19.

\noindent \emph{Keywords:} Motzkin path, hump, peak, standard Young tableau, Motzkin prefix, Riordan array.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001006},
\seqnum{A002426},
\seqnum{A005043},
\seqnum{A033184},
\seqnum{A064189},
\seqnum{A097861},
\seqnum{A140662},
\seqnum{A187306},
\seqnum{A284778},
\seqnum{A379838}, and
\seqnum{A379893}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 3 2025;
revised versions received  January 6 2025; September 26 2025.
Published in {\it Journal of Integer Sequences}, December 10 2025.

\bigskip
\hrule
\bigskip

\noindent
Return to \href{https://cs.uwaterloo.ca/journals/JIS/}{Journal of Integer Sequences home page}.
\vskip .1in


\end{document}

                                                                                

