\documentclass[reqno,twoside,12pt]{amsart}
\setlength{\textwidth}{15.6cm} \setlength{\textheight}{21.5cm}
\hoffset-2truecm
\voffset-.5truecm

\usepackage{url}
%\usepackage[all, 2cell, dvips]{xy}
\usepackage{latexsym,amsmath, amsfonts, graphics, epsf, epic}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsopn}
\usepackage{amscd}
%\usepackage[vcentermath,enableskew]{youngtab}
\usepackage{color}




\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{mlem}[thm]{Main Lemma}
\newtheorem{vnlem}[thm]{Von-Neumann's Lemma}
\newtheorem{defcor}[thm]{Definition/Corollary}
%
\theoremstyle{definition}
\newtheorem{rmk}[thm]{Remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem{example}[thm]{Example}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exc}{Exercise}
\newtheorem{conjecture}[thm]{Conjecture}



%11111111111111111
\font\sym=msam10
\def\Vdash{\hbox{\sym\char'015}}






\parindent=0pt % paragraph indentation
\usepackage{amssymb}
\newcommand{\ZZ}{\mathbb Z}
\newcommand{\NN}{\mathbb N}
\def\QQ{\mathbb{Q}}
\def\FF{\mathbb{F}}
\def\CC{\mathbb{C}}
\def\Om{\Omega}


\def\om{\omega}
\def\tr{\mbox{\rm tr}}
\def\sg{\sigma}
\def\LL{\mathcal L}
\def\BB{\mathcal B}
\def\AA{\mathcal A}
\def\D{{\mathcal D}}
\def\lm{\lambda}
\def\lam{\lambda}
\def\KK{\mathcal K}
\def\dim{\mbox{\rm dim }}
\def\ins{\mbox{\rm ins}}
\def\al{\alpha}
\def\tl{T_{\lambda}}
\def\gm{\gamma}
\def\tm{T_{\mu}}
\def\l.l.o.{\it l.l.o}
\def\E{\eta}
\def\ep{\epsilon}
\def\eps{\varepsilon}
\def\f{\varphi}
\def\p{\psi}
\def\A{{\mathcal A}}
\def\B{{\mathcal B}}
\def\K{{\mathcal K}}
\def\BE{{\mathcal E}}
\def\C{{\mathcal C}}
\def\O{{\mathcal O}}
\def\R{{\mathcal R}}

\def \SST{{semi-standard tableau~}}%99999999999999999


\def\ctr#1{\hfill{#1}\hfill}
\def\hten{\hskip 10pt}
\def\medno{\medskip\noindent}
\def\sksix{\noalign{\vskip 6pt}}
\def\sstyle{\scriptstyle}
\def\half{{1\over 2}}
\def\quart{{1\over 4}}
\def\ol{\overline}
\def\wtil{\widetilde}
\def\gam{\gamma}
\def\pr{^{\prime}}
\def\ofmu{(\mu)}
\def\ofnu{(\nu)}
\def\sig{\sigma}
\def\ofsig{(\sig)}
\font\amsy=msbm10
\def\rline{\hbox{\amsy\char'122}}
\def\zline{\hbox{\amsy\char'132}}
\font\diff=msbm10
\def\leneq{\hbox{\diff\char'010}}
\def\geneq{\hbox{\diff\char'011}}
\font\sdiff=msbm5
\def\sleneq{\hbox{\sdiff\char'010}}
\font\goth=eufm10
\def\gothA{\hbox{\goth A}}
\def\notexists{\hbox{$\exists$\hskip -5pt / }}
\def\rslash{\delimiter"26E30F }
\def\lan{\langle}
\def\ran{\rangle}
\def\chiup{\raise 2pt\hbox{$\chi$}}
\def\rmpar{\hbox{par}}
\def\card{\hbox{card}}


%Math Abbreviation


\DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\End}{End}
\DeclareMathOperator{\sgn}{sgn}
%\DeclareMathOperator{\D}{Det}
\DeclareMathOperator{\Char}{char}
\DeclareMathOperator{\M}{\textsf{M}}
\DeclareMathOperator{\PW}{P^+(n,r)}
\DeclareMathOperator{\LW}{\Lambda^+}
\DeclareMathOperator{\W}{P^+(n,r)}


\def\GL{\mbox{\rm GL}}


\newcommand{\To}{\longrightarrow}
\newcommand{\id}{\rm{id}}
\DeclareMathOperator{\he}{\hat{e}}
\DeclareMathOperator{\hv}{\hat{v}}




\newcommand{\di}{\underline{i}}
\newcommand{\kk}{\underline{k}}
\newcommand{\db}{\underline{b}}
\newcommand{\da}{\underline{a}}
\newcommand{\jj}{\underline{j}}
\newcommand{\dk}{\underline{k}}
\newcommand{\dl}{\underline{l}}
\newcommand{\un}{\underline}
\newcommand{\ov}{\overline}
\newcommand{\ka}{{\kappa}}


\pagestyle{myheadings}


\newenvironment{pf}{\noindent \textit{Proof.}\,}{\hfill$\square$ \vskip5pt}









\begin{document}
\title{Identities for the number of standard Young
tableaux in some $(k,\ell)$-hooks}
\author{A. Regev}

\address{Mathematics Department, The Weizmann Institute, Rehovot 76100,
Israel}

\email{amitai.regev at weizmann.ac.il}

\begin{abstract}
Closed formulas are known for $S(k,0;n)$,
the number of standard Young tableaux of size $n$ and with at most
$k$ parts, where $1\le k\le 5$. Here we study the analogous problem
for $S(k,\ell;n)$, the number of standard Young tableaux of size
$n$ which are contained in the $(k,\ell)$-hook. We deduce some
formulas for the cases $k+\ell\le 4$.
\end{abstract}

\subjclass[2000]{05C30}

\maketitle

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 63 \rms (2010), Article~B63c\hfill}
\def\thepage{}

\section{Introduction}
Given a partition $\lm$ of $n$, which we denote as usual by $\lm\vdash n$, let $\chi^\lm$
denote the corresponding irreducible $S_n$ character. Its degree
is denoted by $\deg \chi^\lm=f^\lm$ and is equal to the number of
standard Young tableaux (SYT) of shape
$\lm$. (The reader is referred to 
\cite{kerber,macdonald,sagan,stanley} for introductions into character
theory of the symmetric group and symmetric functions.)
The number $f^\lm$ can be calculated for example by the hook
formula~(see \cite[Theorem~2.3.21]{kerber},
\cite[Section~3.10]{sagan}, \cite[Corollary~7.21.6]{stanley}. We consider the
number of  SYT in the $(k,\ell)$-hook. More precisely, given
integers $k,\ell,n\ge 0$, we write
\[
H(k,\ell;n)=\{\lm=(\lm_1,\lm_2,\ldots)\mid \lm\vdash n~\mbox{and}~
\lm_{k+1}\le \ell\}\quad\mbox{and}\quad S(k,\ell;n)=\sum_{\lm\in
H(k,\ell;n)}f^\lm.
\]
\subsection{The cases where $S(k,\ell;n)$ are known}\label{s1}
For the ``strip" sums $S(k,0;n)$ it is
known~(see \cite{regev1} and \cite[Ex.~7.16.b]{stanley}) that
\[
S(2,0;n)={\binom n {\lfloor\frac{n}{2}\rfloor}}\quad\mbox{and}\quad
S(3,0;n)=\sum_{j\ge 0}\frac{1}{j+1}{\binom n {2j}}\binom{2j}{ j}.
\]
Let $C_j=\frac{1}{j+1}\binom {2j} j$ be the Catalan numbers.
Gouyou-Beauchamps~\cite{gouyon} (see also \cite[Ex.~7.16.b]{stanley}) 
proved that
\[
S(4,0;n)=C_{\lfloor\frac{n+1}{2}\rfloor}\cdot
C_{\lceil\frac{n+1}{2}\rceil}\quad\mbox{and}\quad
S(5,0;n)=6\sum_{j=0}^{\lfloor\frac{n}{2}\rfloor}\binom n { 2j}\cdot
C_j\cdot\frac{(2j+2)!}{(j+2)!(j+3)!}.
\]
\medskip
As for the ``hook" sums, until recently only $S(1,1;n)$ and
$S(2,1;n)=S(1,2;n)$ have been calculated:

\medskip
1. ~It easily follows that $S(1,1;n)=2^{n-1}$.

\medskip
2. ~The following identity was proved in~\cite[Theorem~8.1]{regev2}:
\begin{multline}\label{motzkin.path.3}
S(2,1;n)
=\frac{1}{4}\Bigg(\sum_{r=0}^{n-1}{\binom {n-r}{\lfloor\frac{n-r}{2}\rfloor}}
{\binom n r}\\
+\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor-1}\frac{n!}{k!\cdot
(k+1)!\cdot (n-2k-2)!\cdot (n-k-1)\cdot(n-k)}\Bigg)+1.
\end{multline}

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL A. REGEV}{\SMALL IDENTITIES FOR THE NUMBER OF STANDARD TABLEAUX}
%
%

\subsection{The main results}
In Section~\ref{s2} we prove Equation~\eqref{rewrite8}, which
gives (sort of) a closed formula for $S(3,1;n)$ in terms of the
Motzkin-sums function. For the Motzkin-sums function
see~\cite[sequence A005043]{sloane}.  Equation~\eqref{rewrite8} is in
fact a ``degree" consequence of a formula for $S_n$ characters,
of interest in its own right, see Equation~\eqref{rewrite3}.

\medskip
In Section~\ref{s3} we find some intriguing relations between the
sums $S(4,0;n)$ and the ``rectangular" sub-sums $S^*(2,2,;n)$
(see Section~\ref{s3} for their definition), see
 identities~\eqref{b3} and~\eqref{b4} below.

\medskip

Finally, in Section~\ref{s4} we review some cases where the
hook sums $S(k,\ell;n)$ are related, in some rather mysterious
ways, to hump enumerations on Dyck and on Motzkin paths,
see~\eqref{eq1},~\eqref{eq2}, and Theorem~\ref{motzkin.humps.1}.

\medskip
As usual, in some of the above identities it is of interest to
find bijective proofs, which might explain these identities.

\medskip
{\bf Acknowledgement.} We thank D. Zeilberger for verifying some
of the identities here by the WZ method.



\section{The sums $S(3,1;n)$ and the characters $\chi
(3,1;n)$}\label{s2}

 Define the $S_n$ character
\begin{eqnarray}\label{rewrite5}
\chi(k,\ell;n)=\sum_{\lm\in H(k,\ell;n)}
\chi^\lm,\qquad\mbox{so that}\qquad\deg(\chi(k,\ell;n))=S(k,\ell;n).
\end{eqnarray}
\subsection{The Motzkin-sums function}

Define the $S_n$ character
\begin{eqnarray}\label{rewrite6}
\Psi(n)=\sum_{k=0}^{\lfloor
n/2\rfloor}\chi^{(k,k,1^{n-2k})},\qquad\mbox{and
denote}\qquad\deg\Psi(n)=a(n).
\end{eqnarray}
We call $\Psi(n)$ {\it the Motzkin-sums} character. Note that
\[
\deg\chi^{(k,k,1^{n-2k})}=f^{(k,k,1^{n-2k})}=\frac{n!}{(k-1)!\cdot
k!\cdot (n-2k)!\cdot (n-k)\cdot (n-k+1)},
\] hence
\begin{eqnarray}\label{a2}
a(n)=\sum_{k=1}^{\lfloor{n}/{2}\rfloor}\frac{n!}{(k-1)!\cdot
k!\cdot (n-2k)!\cdot (n-k)\cdot (n-k+1)}.
\end{eqnarray}
By~\cite[sequence A005043]{sloane}, it follows that $a(n)$ is the
Motzkin-sums function. The reader is referred to~\cite{sloane} for
various properties of $a(n)$. For example, $a(n)+a(n+1)=M_n$,
where $M_n$ are the Motzkin numbers. Also $a(1)=0$, $a(2)=1$, and
$a(n)$ satisfies the recurrence
\begin{eqnarray} \label{a1} a(n)=\frac{n-1}{n+1}\cdot(2\cdot
a(n-1)+3\cdot a(n-2)),\quad \quad \mbox{for $n\ge 3$}.
\end{eqnarray}

 Note also that for $n\ge 2~$ Equation~\eqref{motzkin.path.3} can be
written as
\begin{eqnarray}\label{a3}
S(2,1;n)
=\frac{1}{4}\left(\sum_{r=0}^{n-1}{\binom {n-r}{\lfloor\frac{n-r}{2}\rfloor}}
{\binom n r}+a(n)-1\right)+1.
\end{eqnarray}


The asymptotic behavior of $a(n)$ can be deduced from that of
$M_n$. We deduce it here, even though it is not needed in the
sequel.

\begin{remark} As $n$ tends to infinity,
\[
a(n)\simeq \frac{\sqrt 3}{8\cdot\sqrt{2\pi}}\cdot\frac{1}{n\sqrt
n}\cdot 3^n\qquad\mbox{and}\qquad a(n)\simeq\frac{1}{4} \cdot M_n.
\]
\begin{proof}
By standard techniques it can be shown that $a(n)$ has asymptotic
behavior $$a(n)\simeq c\cdot \left(\frac{1}{n}\right)^g\cdot
\al^n$$ for some constants $c,g$ and $\al$ --- which we now
determine. By~\cite{regev1}, we have
\[
M_n\simeq
%\sqrt{\frac{3}{8\pi}}
\frac{\sqrt 3}{2\sqrt{2\pi}}
\cdot\left(\frac{1}{n}\right)^{3/2}\cdot 3^n.
\]
Together with
\[
%\sqrt{\frac{3}{8\pi}}\cdot\left(\frac{1}{n}\right)^{3/2}\cdot
%3^n\simeq
M_n=a(n)+a(n+1)\simeq c\cdot
(1+\al)\cdot\left(\frac{1}{n}\right)^g\cdot\al^n,
\]
this implies that $\al=3$, that $g=3/2$, and that $c=\frac{\sqrt
3}{8\cdot\sqrt{2\pi}}$.





\end{proof}
\end{remark}




\subsection{The outer product of $S_m$ and  $S_n$ characters}

Given an $S_m$ character $\chi_m$ and  an $S_n$ character
$\chi_n$, we can form their {\it outer} product $\chi_n\hat\otimes
\chi_n$. The exact decomposition of $\chi_m\hat\otimes \chi_n$ is
given by the Littlewood--Richardson
rule, see~\cite{kerber,macdonald,sagan,stanley}.
In the special case that $\chi_n=\chi^{(n)}$, this decomposition
is given, below, by Young's rule. Furthermore, we have
\begin{eqnarray}\label{rewrite7}
\deg (\chi_n\hat\otimes \chi^{(n)})=\deg (\chi_n)\cdot\binom {n+m}
n.
\end{eqnarray}

\medskip {\bf Young's Rule}~(see \cite[Ch.~I, Sec.~7 and
(5.16)]{macdonald}): 
Let $\lm=(\lm_1,\lm_2,\ldots)\vdash m$
and denote by $\lm^{+n}$ the following set of partitions of $m+n$:
\[
\lm^{+n}=\{\mu\vdash n+m\mid \mu_1\ge \lm_1\ge \mu_2\ge
\lm_2\ge\cdots\}.
\]
Then
\[
\chi^\lm\hat\otimes \chi^{(n)}=\sum_{\mu\in\lm^{+n}}\chi^\mu.
\]
\begin{example}\label{rewrite4}
Given $n$, it follows that (see \cite{regev1},~\cite[Ex.~7.16.b]{stanley})
\begin{eqnarray}\label{rewrite1}
\chi^{(\lfloor n/2\rfloor)}\hat\otimes \chi^{(\lceil
n/2\rceil)}=\chi(2,0;n),\quad\mbox{and by taking degrees,}\quad
S(2,0;n)=\binom n {\lfloor n/2 \rfloor}.
\end{eqnarray}
\end{example}




\subsection{A character formula for $\chi(3,1;n)$}

\begin{prop}\label{rewrite2}
With the notations of~\eqref{rewrite5} and~\eqref{rewrite6},
\begin{eqnarray}\label{rewrite3}
\chi(3,1;n)=\frac{1}{2}\cdot\left[\chi(2,0,n)+\sum_{j=0}^n
\Psi(j)\hat\otimes \chi^{(n-j)} \right].
\end{eqnarray}
By taking degrees, Example~\ref{rewrite4} together
with~\eqref{rewrite6} and~\eqref{rewrite7} imply that
%
\begin{eqnarray}\label{rewrite8}
S(3,1;n)=\frac{1}{2}\cdot
\left[\binom n{\lfloor\frac{n}{2}\rfloor}+\sum_{j=0}^n
a(j)\cdot{\binom n j} \right].
\end{eqnarray}
%
\end{prop}
\begin{proof}
Denote
\[
\Omega(n)=\sum_{j=0}^n \Psi(j)\hat\otimes \chi^{(n-j)},
\]
and analyze this $S_n$ character. Young's rule implies the
following:

\medskip
%Given $\lm\vdash m$, denote by $[\lm]$ the corresponding
%irreducible $S_m$ character (whose degree is $f^\lm$).
%Consider the $S_j$ character
%\begin{eqnarray}\label{p1}
%\chi^{(j)}=\sum_{k=1}^{\lfloor{j}/{2}\rfloor}[(k,k,1^{j-2k})],
%\qquad\mbox{then}\qquad a(j)=\deg \chi^{(j)}.
%\end{eqnarray}
%Let $\hat\otimes$ denote the {\it outer} product of characters of
%symmetric groups; it is calculated by Young's rule [reference!].
%Since $\deg[(n-j)]=1,$ in particular
%\[
%\deg\chi^{(j)}\hat\otimes [(n-j)]=a(j)\cdot{\binom n j}
%\]
%Now construct the $S_n$ character
%\begin{eqnarray}\label{p2}
%\chi=\sum_{j=0}^n \chi^{(j)}\hat\otimes [(n-j)],\qquad\mbox{so
%that}\qquad \deg\chi=\sum_{j=0}^na(j)\cdot{\binom n j}.
%\end{eqnarray}
%The essence of the proof is the following analysis of $\chi$. Draw
%the diagrams involved in the terms $\chi^{(j)}\hat\otimes
%[(n-j)]$.

If $\mu\vdash n$, then, by Young's rule, $\chi^\mu$ has a positive
coefficient  in $\Omega(n)$ if and only if $\mu\in H(3,1;n)$.
Moreover, all these coefficients are either $1$ or $2$, and such a
coefficient equals $1$ if and only if $\mu$ is a 
partition with at most two rows, say $\mu=(\mu_1,\mu_2)$. It follows that
\begin{eqnarray}\label{p3}
\chi(2,0;n)+\Omega(n)=2\cdot\sum_{\lm\in H(3,1;n)}\chi^\lm.
\end{eqnarray}
This implies~\eqref{rewrite3} and completes the proof of
Proposition~\ref{rewrite2}.
\end{proof}

\section{The sums $S(4,0;n)$ and $S^*(2,2;n)$}\label{s3}
\begin{defn}
\begin{enumerate}
\item
Let $n=2m$, $m\ge 2$, and let $H^*(2,2;2m)\subset H(2,2;2m)$ denote
the set of partitions $H^*(2,2;2m)=\{(k+2,k+2,2^{m-2-k})\vdash
2m\mid k=0,\ldots m-2\}$ (the partitions in the $(2,2)$-hook with
both arm and leg being rectangular). Furthermore, write
\[
S^*(2,2;2m)=\sum _{\lm\in H^*(2,2;2m)} f^\lm.
\]
\item
Let $n=2m+1$, $m\ge 2$, and let $H^*(2,2;2m+1)\subset H(2,2;2m+1)$
denote the set of partitions
$H^*(2,2;2m+1)=\{(k+3,k+2,2^{m-2-k})\vdash 2m+1\mid k=0,\ldots
m-2\}$ (the partitions in the $(2,2)$-hook with arm nearly
rectangular and leg rectangular). Furthermore, let
\[
S^*(2,2;2m+1)=\sum _{\lm\in H^*(2,2;2m+1)} f^\lm.
\]
\end{enumerate}
\end{defn}

Recall from Section~\ref{s1} that $S(4,0;2m-1)=C_m^2$ and
$S(4,0;2m)=C_m\cdot C_{m+1}$. We have the following intriguing
identities.
\begin{prop}\label{b1}
\begin{enumerate}
\item
Let $n=2m$. Then \[S(4,0;2m-2)=C_{m-1}\cdot C_{m}=S^*(2,2;2m).\]
Explicitly, we have the following identity:
\begin{align}\notag
C_{m-1}\cdot C_m&=\frac{1}{m\cdot (m+1)}\cdot{\binom {2m-2}
{m-1}}\cdot\binom {2m}
m\\
\label{b3}
&=
\sum_{k=0}^{m-2}\frac{(2m)!}{k!\cdot
(k+1)!\cdot(m-k-2)!\cdot (m-k-1)! \cdot (m-1)\cdot m^2\cdot
(m+1)}.
\end{align}

\item
Let $n=2m+1$. Then 
\[\frac{2m+1}{m+2}\cdot
S(4,0;2m-1)=\frac{2m+1}{m+2}\cdot C_{m}^2=S^*(2,2;2m+1).\]
 Explicitly, we have
the following identity:
\begin{multline}
\frac{2m+1}{ m+2}\cdot C_{m}^2=
 \frac{1}{(m+1)\cdot(m+2)}\cdot\binom {2m}
m \binom {2m+1} m\\
\label{b4}
=\sum_{k=0}^{m-2}\frac{(2m+1)!\cdot 2}{k!\cdot
(k+2)!\cdot(m-k-2)!\cdot (m-k-1)! \cdot (m-1)\cdot m\cdot
(m+1)\cdot (m+2)}. 
\end{multline}
\end{enumerate}
\end{prop}

\begin{proof}
Equation~\eqref{b3} is the specialization of Gau\ss's
$_2F_1(a,b;c;1)$ with $a=2-m,b=1-m, c=2$~(cf.\ \cite{askey}),
and~\eqref{b4} is similar.
 Alternatively,
the identities~\eqref{b3} and~\eqref{b4} can be verified by the WZ
method~(cf.\ \cite{doron3,doron2}).
\end{proof}





\section{Hook sums and humps for paths}\label{s4}

 A Dyck path of length
$2n$ is a lattice path, in $\mathbb{Z}\times \mathbb{Z}$, from
$(0,0)$ to $(2n,0)$, using up-steps $(1,1)$ and down-steps
$(1,-1)$ and never going below the $x$-axis.  A {\it hump} in a
Dyck path is an up-step followed by  a down-step.\footnote{In
the Dyck path context, humps are usually called {\it peaks}. However,
we prefer the term ``hump" because, in the context of Motzkin paths,
this term will indeed differ from ``peak."} 

\medskip
A  Motzkin path of length $n$ is a lattice path from $(0,0)$ to
$(n,0)$, using flat-steps $(1,0)$, up-steps $(1,1)$ and down-steps
$(1,-1)$, and never going below the $x$-axis. A hump in a Motzkin
path is an up-step followed by zero or more flat-steps followed by
a down-step.


\medskip
We now count {\it humps} for Dyck and for Motzkin paths and
observe the following intriguing phenomena: The hump enumeration
in the Dyck case associates the $2\times n$ rectangular shape
$\lm=(n,n)$ to the $(1,1)$-hook shape $\mu=(n,1^n)$. Moreover, in the
Motzkin case we show below that it
associates the $(3,0)$ strip shape partitions $H(3,0;n)$ to the
$(2,1)$-hook shape partitions $H(2,1;n)$.

\subsection{The Dyck case}
%The number of Dyck paths of length $2n$ is

The Catalan number
\[C_n=\frac{(2n)!}{n!(n+1)!}\]
is the cardinality of a variety of sets~(see \cite[Ex.~6.19]{stanley}); here we
are interested in two such sets. First, $C_n=f^{(n,n)}$, the
number of SYT of shape $(n,n)$. Second, $C_n$ is the number of
Dyck paths of length $2n$.
%\medskip
 Let ${\mathcal H} D_n$ denote
the total number of humps in all Dyck paths of length $2n$.
Then 
\[ {\mathcal H} D_n=\binom {2n-1} n,\]
see~\cite{dershowitz1,dershowitz2,deutsch}. Since
$\binom {2n-1} n=f^{(n,1^n)}$, we have
\[
C_n=f^{(n,n)}\qquad\mbox{and}\qquad{\mathcal H} D_n=f^{(n,1^n)}.
\]
We denote this association by
\begin{eqnarray}\label{eq1}
{\mathcal H}: (n,n)\longrightarrow (n,1^n).
\end{eqnarray}

\subsection{The Motzkin case}

Like the Catalan numbers, also the Motzkin numbers $M_n$ are the
cardinality of a variety of sets (cf.\ ~\cite[Ex.~6.38]{stanley},
\cite [sequence A001006]{sloane}).
The result from \cite{regev1} that $M_n=S(3,0;n)$
gives the Motzkin numbers a  SYT
interpretation. Moreover, $M_n$ is the number of Motzkin paths of
length $n$. Let ${\mathcal H} M_n$ denote the total number of humps in
all Motzkin paths of length $n$. Then, according to~\cite [sequence
A097861]{sloane},
\begin{eqnarray}\label{motzkin.path.2}
{\mathcal H}M_n=\frac{1}{2}\sum_{j\ge 1}{\binom n j}\binom {n-j}j.
\end{eqnarray}
We show below that this implies the intriguing identity ${\mathcal
H}M_n=S(2,1;n)-1,$ which gives a SYT-interpretation of the numbers
${\mathcal H}M_n$. Thus, the hump enumeration in the Motzkin case
associates the $(3,0)$ strip shape partitions $H(3,0;n)$ to the
$(2,1)$-hook shape partitions $H(2,1;n)$. We denote this by
\begin{eqnarray}\label{eq2}
{\mathcal H}: H(3,0;n)\longrightarrow H(2,1;n).
\end{eqnarray}

\begin{thm}\label{motzkin.humps.1}
The number of humps of all Motzkin paths of length $n$ satisfies
\[
{\mathcal H}M_n=S(2,1;n)-1.
\]
\end{thm}
%This gives a SYT-interpretation of the numbers ${\mathcal H}M_n$.

%\begin{proof}
Combining Equations~\eqref{motzkin.path.3}
and~\eqref{motzkin.path.2}, the proof of
Theorem~\ref{motzkin.humps.1} will follow once  the following
binomial identity --- of interest in its own right --- is proved.
\begin{lem}\label{motzkin.humps.11}
For $n\ge 2$, we have
\begin{multline}\label{motzkin.path.222}
2\sum_{j=1}^{\lfloor n/2\rfloor}{\binom n j}\binom {n-j}
j=\sum_{r=0}^{n-1}{\binom {n-r}{\lfloor\frac{n-r}{2}\rfloor}}
{\binom n r}+a(n)-1\\
=\sum_{r=0}^{n-1}{\binom {n-r}{\lfloor\frac{n-r}{2}\rfloor}}
{\binom n r}
+\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor-1}\frac{n!}{k!\cdot
(k+1)!\cdot (n-2k-2)!\cdot (n-k-1)\cdot(n-k)}.
\end{multline}
\end{lem}

Equation~\eqref{motzkin.path.222} was first verified by the WZ
method. About this method, see~\cite{doron3,doron2}. Here
is an elementary proof which is due to Ira Gessel~\cite{gessel}.
\begin{proof}
%Here is a sketch of a simple proof of  Regev's identity
%%({\tt arXiv:1003.1835})
%\begin{equation}
%\label{e1} 2\sum_{j=1}^{\lfloor n/2\rfloor} \binom nj \binom{n-j}j
%=\sum_{r=0}^{n-1}\binom {n-r}{\lfloor{\frac{n-r}{2}}}\binom nr
%+a(n) -1
%\end{equation}
Note first that $a(n)$ is the $n$th Riordan number,~\cite[sequence
A005043]{sloane}, defined (for example) by
\[\sum_{n=0}^\infty a(n) x^n = \frac{2}{1+x+\sqrt{1-2x-3x^2}}.\]
Adding 2 to both sides of \eqref{motzkin.path.222}
%{e1}
 gives the
equivalent identity
\begin{equation}
\label{e2} 2\sum_{j=0}^{\lfloor n/2\rfloor} \binom nj \binom{n-j}j
=\sum_{r=0}^{n}\binom {n-r}{\lfloor{\frac{n-r}{2}}\rfloor}\binom
nr +a(n).
\end{equation}



Now let us replace $r$ by $n-r$ in the sum  on the right-hand side of
\eqref{e2}, thereby getting
\begin{equation*}
\sum_{r=0}^{n}\binom {r}{\lfloor{\frac{r}{2}\rfloor}}\binom nr,
\end{equation*}
and then separate the even and odd values of $r$ so that this sum
is equal to $u(n)+v(n)$ where
\[u(n) =\sum_j \binom{2j}{j}\binom{n}{2j}\]
and
\[v(n) = \sum_j\binom{2j+1}{j}\binom{n}{2j+1}.\]
Noting that the left-hand side of \eqref{e2} is $2u(n)$, we see that
the identity to be proved is equivalent to
\begin{equation}
\label{e3} u(n) = v(n) + a(n).
\end{equation}


It is straightforward to show that $u(n)$ is the coefficient of
$x^n$ in $(1+x+x^2)^n$ ~\cite[sequence A002426, central trinomial
coefficients]{sloane} and that $v(n)$ is the coefficient of
$x^{n-1}$ (or of $x^{n+1}$) in $(1+x+x^2)^n$ ~\cite[sequence
A005717]{sloane}. With these interpretations for $u(n)$ and
$v(n)$, a combinatorial proof of the identity $u(n) - v(n) =a(n)$
has been given by David Callan
%[Riordan numbers are differences of trinomial coefficients, 2006,\url
[Riordan numbers are differences of trinomial coefficients, 2006,
\url{http://www.stat.wisc.edu/~callan/notes/riordan/riordan.pdf}].
%{http://www.stat.wisc.edu/~callan/notes/riordan/riordan.pdf}].
Alternatively, Equation~\eqref{e3} follows easily from the known generating
functions for $u(n)$, $v(n)$, and $a(n)$, which can all be found
in~\cite{sloane} (or derived directly).
\end{proof}
This completes the proof of Theorem~\ref{motzkin.humps.1}.







\begin{thebibliography}{99}

\bibitem{askey} G. E. Andrews, R. Askey and R. Roy, {\em Special
Functions}, Encyclopedia of Mathematics and its Applications,
Cambridge University Press (1999).

\bibitem{darasathy}  C. Darasathy ans A. Yang, {\em A transformation on
ordered trees}, Computer J. {\bf 23} (1980), 161--164.

\bibitem{dershowitz1} N. Dershowitz and  S. Zaks, {\em Enumeration of
ordered trees}, Discrete Math. {\bf 31} (1980), 9--28.

\bibitem{dershowitz2} N. Dershowitz and  S. Zaks, {\em Applied tree
enumeration}, Lecture Notes in Computer Science, vol.~112,
Springer, Berlin, 1981, pp.~180--193.

\bibitem{gessel} I. Gessel, private letter.

\bibitem{deutsch} E. Deutsch, {\em Dyck path enumeration}, 
Discrete Math {\bf 204} (1999), 167--202.

\bibitem{gouyon} D. Gouyou-Beauchamps, {\em Standard Young tableaux of
height $4$ and $5$}, Europ. J. Combin. {\bf 10} (1989), 69--82.

\bibitem{kerber} G.D. James and A. Kerber, {\em The Representation
Theory of the Symmetric Group}, Encyclopedia of Mathematics and its
Applications, vol.~16, Addison--Wesley, Reading, MA (1981).

\bibitem{macdonald} I.G. Macdonald, {\em 
Symmetric Functions and Hall Polynomials},
2nd edition, Oxford University Press (1995).

\bibitem{doron3} M. Petkov\v sek, H.S. Wilf and D Zeilberger, {\em A=B},
A.K.~Peters Ltd. (1996).

\bibitem{regev1}  A. Regev, {\em Asymptotic values of degrees associated
with strips of Young diagrams}, Adv. Math. {\bf 41} (1981),
115--136.


\bibitem{regev2}  A. Regev, {\em Probabilities in the $(k,\ell)$ hook},
Israel J. Math. {\bf 169} (2009), 61--88.

\bibitem{sagan} B. E. Sagan, {\em The Symmetric Group: Representations,
Combinatorial Algorithms, and Symmetric Functions}, 2nd edition,
Graduate Texts in Mathematics {\bf 203}, Springer-Verlag (2000).

\bibitem{sloane} N.J.A. Sloane, {\em The On-Line Encyclopedia of
Integer Sequences},\newline 
{\tt http://www.research.att.com/\~{}njas/sequences}.

\bibitem{stanley} R. P. Stanley, {\em Enumerative Combinatorics}, vol.~2,
Cambridge University Press, Cambridge (1999).

\bibitem{doron2} D. Zeilberger, {\em The method of creative
telescoping},  J. Symbolic Comput.
{\bf 11} (1991), 195--204.

\end{thebibliography}





\end{document}