\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

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

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

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
%\usepackage{mathrsfs}

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

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\newcommand{\lrf}[1]{\left\lfloor #1\right\rfloor}

\begin{document}

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

\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{center}
\vskip 1cm{\LARGE\bf Combinatorics of Generalized\\
\vskip .11in
Motzkin Numbers}
\vskip 1cm
{\large  Yi Wang and Zhi-Hai Zhang\\
School of Mathematical Sciences \\
Dalian University of Technology \\
Dalian 116024 \\
PR China \\
\href{mailto:wangyi@dlut.edu.cn}{\tt wangyi@dlut.edu.cn} \\
\href{mailto:zzhdlut008@dlut.edu.cn}{\tt zzhdlut008@dlut.edu.cn} \\
}
\end{center}

\vskip .2 in

\begin{abstract}
The generalized Motzkin numbers are common generalizations of the Motzkin numbers and the Catalan numbers.
We investigate their combinatorial properties,
including the combinatorial interpretation, the recurrence relation,
the binomial transform, the Hankel transform, the log-convexity,
the continued fraction of the generating function,
and the total positivity of the corresponding Hankel matrix.
\end{abstract}

\section{Introduction}

The Motzkin numbers $M_n$ 
count the number of lattice paths from $(0, 0)$ to $(n, 0)$
with steps $H=(1, 0), U=(1, 1)$ and $D=(1,-1)$, never going below the $x$-axis \cite{Aig98,DS77}.
It is well known that the Motzkin numbers satisfy the recursion
$$(n+3)M_{n+1}=(2n+3)M_n+3nM_{n-1}$$
(see \cite{Sul01} for a combinatorial proof).
The Motzkin numbers are closely related to the ubiquitous Catalan numbers $C_n=\frac{1}{n+1}\binom{2n}{n}$,
which count the number of lattice paths from $(0, 0)$ to $(2n, 0)$
with steps $U$ and $D$, never falling below the $x$-axis.
For example,
$$M_n=\sum_{k}\binom{n}{2k}C_k,\qquad
C_{n+1}=\sum_{k}\binom{n}{k}M_k.$$
It follows that
$$C_{n+1}=\sum_{k}\binom{n}{2k}C_k2^{n-2k}.$$
See \cite{Don77,DS77} for combinatorial interpretations of these identities.
On the other hand,
the Motzkin numbers and the Catalan numbers
enjoy some similar properties,
including the recurrence relations
$$M_{n+1}=M_n+\sum_{k=0}^{n-1}M_kM_{n-1-k},\qquad
C_{n+1}=\sum_{k=0}^nC_kC_{n-k}$$
and the generating functions
$$\sum_{n\ge 0}M_nx^n=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2},\qquad
\sum_{n\ge 0}C_nx^n=\frac{1-\sqrt{1-4x}}{2x}.$$

Very recently,
Z.-W. Sun~\cite{Sun14} introduced {\it the generalized Motzkin numbers}
\begin{equation}\label{gmn-def}
  M_n(b,c):=\sum_{k=0}^{\lrf{n/2}}\binom{n}{2k}C_kb^{n-2k}c^k,
  \quad n=0,1,2,\ldots,
\end{equation}
where $b,c\in\mathbb{N}$.
Clearly, the generalized Motzkin numbers are common generalizations of the Motzkin numbers and the Catalan numbers:
$$M_n(1,1)=M_n,\quad M_n(2,1)=C_{n+1}.$$
It is also known that
$M_n(3,1)=H_n$ are the restricted hexagonals numbers described in Harary and Read \cite{HR70}
and $M_n(0,1)$ form the sequence $(C_0,0,C_1,0,C_2,0,\ldots)$ of the Catalan numbers.

Sun~\cite{Sun14} established the recursion
\begin{equation*}\label{gmn-rr}
(n+3)M_{n+1}(b,c)=b(2n+3)M_n(b,c)-(b^2-4c)nM_{n-1}(b,c),
\end{equation*}
the generating function
\begin{equation}\label{gmn-gf}
M(b,c;x):=\sum_{n\ge 0}M_n(b,c)x^n=\frac{1-bx-\sqrt{(1-bx)^2-4cx^2}}{2cx^2},
\end{equation}
and applied them to study arithmetic properties of the generalized Motzkin numbers.
The object of this paper is to investigate combinatorial properties of the generalized Motzkin numbers,
including the combinatorial interpretation, the recurrence relation,
the binomial transform, the Hankel transform,
the log-convexity,
the continued fraction of the generating function,
and the total positivity of the corresponding Hankel matrix.

Let $\alpha=(a_n)_{n\ge 0}$ be a sequence of nonnegative numbers.
We say that the sequence is {\it log-convex} if $a_{i}a_{j+1}\ge a_{i+1}a_{j}$ for $0\le i<j$.
Many well-known combinatorial numbers form a log-convex sequence,
including the Catalan numbers $C_n$ and the Motzkin numbers $M_n$.
See \cite{LW07,WZ14,Zhu13} for details.
Define the {\it Hankel matrix} $H(\alpha)$ of a sequence $\alpha=(a_n)_{n\ge 0}$ by
$$H(\alpha)=[a_{i+j}]_{i,j\ge 0}
=\left[\begin{array}{lllll}
a_{0} & a_1 & a_2 & a_3 & \cdots\\
a_{1} & a_{2} & a_3 & a_4 & \cdots\\
a_{2} & a_{3} & a_{4} & a_5 & \cdots\\
a_{3} & a_{4} & a_{5} & a_{6} & \cdots\\
\vdots & \vdots &\vdots & \vdots & \ddots\\
\end{array}\right].$$
A matrix is called {\it totally positive of order $r$} ({\it TP$_r$} for short),
if its minors of all orders $\le r$ are nonnegative.
It is {\it TP} if all minors are nonnegative.
Clearly, a sequence is log-convex if and only if its Hankel matrix is TP$_2$.
We refer the reader to \cite{Kar68,Pin10} for more information about TP matrices.

\begin{theorem}\label{main-thm}
Let
$M_n:=M_n(b,c)$ be the generalized Motzkin numbers defined by \eqref{gmn-def}.
Then we have the following.
\begin{itemize}
  \item [\rm (i)] The recurrence relation
  \begin{equation*}\label{gmn-crr}
  M_{n+1}(b,c)=bM_n(b,c)+c\sum_{i=0}^{n-1}M_i(b,c)M_{n-1-i}(b,c)
  \end{equation*}
  for $n\ge 1$.
  \item [\rm (ii)] The generating function
  $$M(b,c;x)=\dfrac{1}{1-bx-\dfrac{cx^2}{1-bx-\dfrac{cx^2}{1-bx-\cdots}}}.$$
  \item [\rm (iii)] The binomial transform
  \begin{equation*}\label{bt}
  \sum_{k=0}^n\binom{n}{k}M_k(b,c)=M_n(b+1,c).
  \end{equation*}
  \item [\rm (iv)] The Hankel transform
  $$\det\left[\begin{array}{llll}
  M_0 & M_1 & \cdots & M_n \\
  M_1 & M_2 & \cdots & M_{n+1} \\
  \vdots & \vdots & \ddots & \vdots \\
  M_n & M_{n+1} & \cdots & M_{2n} \\
  \end{array}\right]=c^{\binom{n+1}{2}}.$$
  \item [\rm (v)] The Hankel matrix
  $$\left[\begin{array}{lllll}
  M_0 & M_1 & M_2 & \cdots \\
  M_1 & M_2 & M_3 & \cdots \\
  M_2 & M_3 & M_4 & \cdots \\
  \vdots & \vdots & \vdots & \ddots \\
  \end{array}\right]$$
  is totally positive if $b^2\ge 4c$.
  \item [\rm (vi)] The sequence $(M_n)_{n\ge 0}$ is log-convex if $b^2\ge c$.
\end{itemize}
\end{theorem}

\section{Proof of Theorem \ref{main-thm}}

The generalized Motzkin triangle is an infinite lower triangular matrix $M(b,c)=[M_{n,k}(b,c)]$ defined by
\begin{equation}\label{gmt}
M_{0,0}(b,c)=1,\quad
M_{n+1,k}(b,c)=M_{n,k-1}(b,c)+bM_{n,k}(b,c)+cM_{n,k+1}(b,c),\quad k\ge 1.
\end{equation}
Such a triangle has occurred in the literature.
For example,
it is called the $(b,c/b)$-Motzkin triangle in He \cite{He13}.
In particular,
$M(1,0)$ is the famous Pascal triangle,
$M(1,1)$ is the Motzkin triangle \cite{Aig99},
and $M(2,1)$ is the Catalan triangle of Aigner \cite{Aig01}.
Following Aigner \cite{Aig01},
$M(b,c)$ is a recursive matrix and
the entries $M_{n,0}(b,c)$ of its first column are the corresponding Catalan-like numbers.
In this section,
we first demonstrate that the generalized Motzkin numbers $M_n(b,c)$ is precisely the Catalan-like numbers
corresponding to the generalized Motzkin triangle $M(b,c)$, i.e., $M_n(b,c)=M_{n,0}(b,c)$,
and then apply this result to prove Theorem \ref{main-thm}.

The generalized Motzkin triangle is also a Riordan array.
A {\it Riordan array}, denoted by $(g(x), f(x))$, is an infinite lower triangular matrix
whose generating function of the $k$th column is $x^kf^k(x)g(x)$ for $k=0,1,2,\ldots$,
where $g(0)=1$ and $f(0)\neq 0$.
A basic example of Riordan array is the Pascal triangle
$$P=\left[\binom{n}{k}\right]_{n,k\ge 0}=\left(\frac{1}{1-x},\frac{1}{1-x}\right).$$
It is well known \cite{SGWW91,Spr94} that all Riordan arrays form a group under the matrix multiplication:
\begin{equation}\label{m-rg}
(g(x),f(x))*(d(x),h(x))=(g(x)d(xf(x)),f(x)h(xf(x))).
\end{equation}
A Riordan array $R=(g(x),f(x))=[r_{n,k}]_{n,k\ge 0}$
can be characterized by two sequences
$A=(a_n)_{n\ge 0}$ and $Z=(z_n)_{n\ge 0}$ such that
\begin{equation}\label{rrr-c}
r_{0,0}=1,\quad r_{n+1,0}=\sum_{j\ge 0}z_jr_{n,j},\quad r_{n+1,k+1}=\sum_{j\ge 0}a_jr_{n,k+j}
\end{equation}
for $n,k\ge 0$ (see \cite{HS09} for instance).
Let $A(x)$ and $Z(x)$ be the generating functions of $A$- and $Z$- sequences respectively.
Then it follows from (\ref{rrr-c}) that
\begin{equation}\label{fg}
  g(x)=\frac{1}{1-xZ(xf(x))},\qquad f(x)=A(xf(x)).
\end{equation}
See \cite{HS09} for details.
Now $M(b,c)$ is a Riordan array with $A(x)=1+bx+cx^2$ and $Z(x)=b+cx$.
Let $M(b,c)=(M(x),m(x))$.
Then by \eqref{fg},
\begin{equation}\label{f}
M(x)=\frac{1}{1-bx-cx^2m(x)},\qquad m(x)=1+bxm(x)+cx^2m^2(x).
\end{equation}
Note that $m(0)=1$. Solve \eqref{f} to obtain
$$M(x)=m(x)=\frac{1-bx-\sqrt{(1-bx)^2-4cx^2}}{2cx^2}.$$
Comparing with \eqref{gmn-gf}, we have $M(b,c;x)=M(x)$.
Thus $M_n(b,c)=M_{n,0}(b,c)$.
Furthermore,
\begin{equation}\label{mgf}
M(b,c;x)=1+bxM(b,c;x)+cx^2M^2(b,c;x).
\end{equation}

Now we are in a position to prove Theorem \ref{main-thm}.

(i)\quad
Comparing coefficients of $x^{n+1}$ on both sides of \eqref{mgf},
we have $M_0(b,c)=1$ and
$$M_{n+1}(b,c)=bM_n(b,c)+c\sum_{i=0}^{n-1}M_i(b,c)M_{n-1-i}(b,c)$$
for $n\ge 1$.

(ii)\quad
Rewrite \eqref{mgf} as
$$M(b,c;x)=\frac{1}{1-bx-cx^2M(b,c;x)},$$
which leads to the continued fraction
$$M(b,c;x)=\dfrac{1}{1-bx-\dfrac{cx^2}{1-bx-\dfrac{cx^2}{1-bx-\cdots}}}.$$

(iii)\quad
Let $P$ be the Pascal triangle.
Then by \eqref{m-rg},
\begin{eqnarray*}
P\cdot M(b,c)&=&\left(\frac{1}{1-x},\frac{1}{1-x}\right)\cdot (M(b,c;x);M(b,c;x))\\
&=&\left(\frac{1}{1-x} M\left(b,c;\frac{x}{1-x}\right),\frac{1}{1-x} M\left(b,c;\frac{x}{1-x}\right)\right)
\end{eqnarray*}
Note that
\begin{eqnarray*}
\frac{1}{1-x}M\left(b,c;\frac{x}{1-x}\right)
&=&\frac{1}{1-x}\frac{1-\frac{bx}{1-x}-\sqrt{\left(1-\frac{bx}{1-x}\right)^2-\frac{4cx^2}{(1-x)^2}}}{\frac{2cx^2}{(1-x)^2}}\\
&=&\frac{1-x-bx-\sqrt{(1-x-bx)^2-4cx^2}}{2cx^2}\\
&=&M(b+1,c;x).
\end{eqnarray*}
Hence $P\cdot M(b,c)=M(b+1,c)$.
Comparing entries of the first columns on both sides, we obtain
$$\sum_{k=0}^n\binom{n}{k}M_k(b,c)=M_n(b+1,c).$$

(iv)\quad
Let $H(b,c)=[M_{i+j}(b,c)]_{i,j\ge 0}$ be the Hankel matrix of the generalized Motzkin numbers
and $$H_n=[M_{i+j}(b,c)]_{0\le i,j\le n}
  =\left[\begin{array}{cccc}
  M_0 & M_1 & \cdots & M_n \\
  M_1 & M_2 & \cdots & M_{n+1} \\
  \vdots & \vdots & \ddots & \vdots \\
  M_n & M_{n+1} & \cdots & M_{2n} \\
  \end{array}\right]$$
the $n$th leading principal submatrices of $H$.
The fundamental theorem of Aigner on recursive matrices states that
\begin{equation*}\label{ft}
M_{m+n}(b,c)=M_{m+n,0}(b,c)=\sum_{k}c^kM_{m,k}(b,c)M_{n,k}(b,c),
\end{equation*}
or equivalently,
\begin{equation*}\label{mtm}
H=MTM^t,
\end{equation*}
where
$T=\textrm{diag}[1,c,c^2,c^3,\ldots]$ is a diagonal matrix \cite[p.\ 351]{Aig01}.
Since $M$ is a lower triangular matrix with all diagonal entries are $1$,
we have
$$\det(H_n)=c^{1+2+\cdots+n}=c^{\binom{n+1}{2}}.$$

To prove (v) and (vi),
we need the following result,
which is a special case of \cite[Theorem 2.8]{CLW-EuJC}.

\begin{lemma}\label{clw}
If the sequence $(1,b,c)$ is PF,
then $M(b,c)$ is TP.
If the sequence $(1,b,c)$ is log-concave,
then the sequence $(M_{n,0}(b,c))_{n\ge 0}$ is log-convex.
\end{lemma}

It is well known that
a finite sequence of nonnegative numbers is PF
if and only if its generating function has only real zeros
(see \cite[p.\ 399]{Kar68} for instance).
So, if $b^2\ge 4c$, then the matrix $M$ is TP, and so is its transpose $M^t$.
Clearly, the diagonal matrix $T$ is TP.
Also, the product of TP matrices is TP.
Thus the Hankel matrix $H=MTM^t$ is TP if $b^2\ge 4c$ by Lemma \ref{clw}.
This proves (v).

(vi) is an immediate consequence of Lemma \ref{clw}.
This completes the proof of the theorem.

\section{Remarks}

In this paper
we investigate the generalized Motzkin numbers
by setting them in a broader context (the generalized Motzkin triangle).
This approach gives us ˇ°more room to workˇ±
and is often more effective because the theory of matrices is more fruitful.

Aigner \cite{Aig01} used (weighted) lattice path techniques to give combinatorial interpretations of entries of a recursive matrix,
including the Catalan-like numbers.
Here we present a combinatorial interpretation of the generalized Motzkin numbers
from such a viewpoint.

Recall that a Motzkin path of length $n$ is a lattice path from $(0, 0)$ to $(n, 0)$
with steps $H=(1, 0), U=(1, 1)$ and $D=(1,-1)$, never going below the $x$-axis.
To the steps we assign weights $w(U)=1,w(H)=b,w(D)=c$.
Let $\mathcal{P}_n$ be the set of Motzkin paths of length $n$.
For $P\in\mathcal{P}_n$, define the weight $w(P)=\prod w(\textrm{steps})$.
Then
$$M_n(b,c)=\sum_{P\in\mathcal{P}_n}w(P).$$

Some combinatorial properties of the generalized Motzkin numbers follow immediately
from the point of view of weighted lattice paths,
including the recurrence relations, the generating functions and the log-convexity.
We refer the reader to \cite{Aig01,MSS07,SW14,Woa06} for more information.

\section{Acknowledgments}

The authors thank the anonymous referee for his/her careful reading and helpful comments.
This work was supported in part by the National Natural Science Foundation of China (Grant No.\ 11371078)
and the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No.\ 20110041110039).

\begin{thebibliography}{99}

\bibitem{Aig98}M. Aigner,
Motzkin numbers, {\it European J. Combin.} {\bf 19} (1998), 663--675.

\bibitem{Aig99}M. Aigner,
Catalan-like numbers and determinants, {\it J. Combin. Theory Ser. A} {\bf 87} (1999), 33--51.

\bibitem{Aig01}M. Aigner,
Catalan and other numbers: A recurrent theme,
in H. Crapo and D. Senato, eds., {\it Algebraic Combinatorics and Computer Science}, Springer, 2001, pp.~347--390.

\bibitem{CLW-EuJC}X. Chen, H. Liang, and Y. Wang,
Total positivity of Riordan arrays, {\it European J. Combin.} {\bf 46} (2015), 68--74.

\bibitem{Don77}R. Donaghey,
Restricted plane tree representations for four Motzkin-Catalan equations,
{\it J. Combin. Theory Ser. B} {\bf 22} (1977), 114--121.

\bibitem{DS77}R. Donaghey and L. W. Shapiro,
Motzkin numbers,
{\it J. Combin. Theory Ser. A} {\bf 23} (1977), 291--301.

\bibitem{HR70}F. Harary and R. Read,
The enumeration of tree-like polyhexes,
{\it Proc. Edinburgh Math. Soc.} {\bf 17} (1970), 1--13.

\bibitem{He13}T.-X. He,
Parametric Catalan numbers and Catalan triangles,
{\it Linear Algebra Appl.} {\bf 438} (2013), 1467--1484.

\bibitem{HS09}T.-X. He and R. Sprugnoli,
Sequence characterization of Riordan arrays,
{\it Discrete Math.} {\bf 309} (2009), 3962--3974.

\bibitem{Kar68}S. Karlin,
{\it Total Positivity}, Vol.~1,
Stanford University Press, 1968.

\bibitem{LW07}L. Liu and Y. Wang,
On the log-convexity of combinatorial sequences,
{\it Adv. in Appl. Math.} {\bf 39} (2007), 453--476.

\bibitem{MSS07}
T. Mansour, M. Schork, and Y. Sun,
Motzkin numbers of higher rank: Generating function and explicit expression,
{\it J. Int. Seq.} {\bf 10} (2007), Article 07.7.4.

\bibitem{Pin10}A. Pinkus,
{\it Totally Positive Matrices},
Cambridge University Press, 2010.

\bibitem{SGWW91}L. W. Shapiro, S. Getu, W.-J. Woan, and L. C. Woodson,
The Riordan group,
{\it Discrete Appl. Math.} {\bf 34} (1991), 229--239.


\bibitem{Spr94}R. Sprugnoli,
Riordan arrays and combinatorial sums,
{\it Discrete Math.} {\bf 32} (1994), 267--290.

\bibitem{Sul01}R. A. Sulanke,
Bijective recurrences for Motzkin paths,
{\it Adv. in Appl. Math.} {\bf 27} (2001), 627--640.

\bibitem{SW14}H. Sun and Y. Wang,
A combinatorial proof of the log-convexity of Catalan-like numbers,
{\it J. Integer Seq.} {\bf 17} (2014), Article 14.5.2.

\bibitem{Sun14}Z.-W. Sun,
Congruences involving generalized central trinomial coefficients,
{\it Sci. China Math.} {\bf 57} (2014), 1375--1400.

\bibitem{WZ14}Y. Wang and Z.-H. Zhang,
Log-convexity of Aigner-Catalan-Riordan numbers,
{\it Linear Algebra Appl.} {\bf 463} (2014), 45--55.

\bibitem{Woa06}W. J. Woan,
A relation between restricted and unrestricted weighted Motzkin paths,
{\it J. Integer Seq.} {\bf 9} (2006), Article 06.1.7.

\bibitem{Zhu13}B.-X. Zhu,
Log-convexity and strong q-log-convexity for some triangular arrays,
{\it Adv. in Appl. Math.} {\bf 50} (2013), 595--606.
\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: }
generalized Motzkin number,
Motzkin number,
Catalan number,
Hankel matrix,
total positivity,
log-convexity.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001006},
\seqnum{A000108},
\seqnum{A126120}, and
\seqnum{A002212}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 19 2014;
revised version received December 17 2014. 
Published in {\it Journal of Integer Sequences}, January 24 2015.

\bigskip
\hrule
\bigskip

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

\end{document}