\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}
\usepackage{epic}

\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}}}

\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}

\def\m{{\cal M}}
\def\L{\mathscr{L}}
\def\C{\mathscr{C}}
\def\S{{\cal S}}
\def\O{{\cal O}}
\def\E{{\cal E}}
\def\I{{\cal I}}

\begin{center}
\vskip 1cm{\LARGE\bf A Combinatorial Proof of the Log-Convexity  \\
\vskip .1in
of Catalan-Like Numbers}
\vskip 1cm
{\large Hua Sun and Yi Wang \\
School of Mathematical Sciences \\
Dalian University of Technology \\
Dalian 116024 \\ 
PR China \\
\href{mailto:hanch.sun@gmail.com}{\tt hanch.sun@gmail.com} \\
\href{mailto:wangyi@dlut.edu.cn}{\tt wangyi@dlut.edu.cn} \\
}
\end{center}

\vskip .2 in

\def\m{{\cal M}}
\def\L{\mathscr{L}}
\def\C{\mathscr{C}}
\def\S{{\cal S}}
\def\O{{\cal O}}
\def\E{{\cal E}}
\def\I{{\cal I}}

\begin{abstract}
The Catalan-like numbers $c_{n,0}$, defined by
\begin{align*}
&c_{n+1,k}=r_{k-1}c_{n,k-1}+s_kc_{n,k}+t_{k+1}c_{n,k+1}\text{ for $n,k\geq 0$},\\
&c_{0,0}=1, c_{0,k}=0 \text{ for $k\neq 0$},
\end{align*}
unify a substantial amount of well-known counting coefficients.
Using an algebraic approach,
Zhu showed that the sequence $(c_{n,0})_{n\geq 0}$ is log-convex
if $r_{k}t_{k+1}\leq s_{k}s_{k+1}$ for all $k\geq 0$.
Here we give a combinatorial proof of this result
from the point of view of weighted Motzkin paths.
\end{abstract}

\section{Introduction}

A sequence $a_{0},a_{1},a_{2},\ldots$ of nonnegative numbers
is called {\it log-convex} if $a^{2}_{n}\leq a_{n+1}a_{n-1}$ for all $n\geq 1$.
Many well-known combinatorial sequences are log-convex
(see Liu and Wang~\cite{LW07} for instance).
One of the simplest classes of log-convex sequences,
yet still large enough to include many important instance,
is the class of the Catalan-like numbers.
The Catalan-like numbers $c_{n,0}$, introduced by Aigner~\cite{Aig99,Aig01}, are defined by the recursive system
\begin{align}\label{gcln}
&c_{n+1,k}=r_{k-1}c_{n,k-1}+s_kc_{n,k}+t_{k+1}c_{n,k+1}\text{ for $n,k\geq 0$},\\
&c_{0,0}=1, c_{0,k}=0 \text{ for $k\neq 0$},\nonumber
\end{align}
where $(r_{n})_{n\geq 0}$, $(s_{n})_{n\geq 0}$ and $(t_{n})_{n\geq 1}$ are three sequences of nonnegative numbers.
The Catalan-like numbers unify many well-known counting coefficients.
For example, let $r_k\equiv 1, \sigma=(s_0,s_1,\ldots)$ and $\tau=(t_1,t_2,\ldots)$ in (\ref{gcln}).
Then $c_{n,0}$ are
\begin{itemize}
  \item [\rm (1)] the Catalan numbers $C_n$ if $\sigma=(1,2,2,\ldots)$ and $\tau=(1,1,1,\ldots)$;
  \item [\rm (2)] the Motzkin numbers $M_n$ if $\sigma=\tau=(1,1,1,\ldots)$;
  \item [\rm (3)] the middle binomial coefficients $\binom{2n}{n}$ if $\sigma=(2,2,2,\ldots)$ and $\tau=(2,1,1,\ldots)$;
  \item [\rm (4)] the Schr\"oder numbers $S_n$ if $\sigma=(2,3,3,\ldots)$ and $\tau=(2,2,2,\ldots)$;
  \item [\rm (5)] the Bell numbers $B_n$ if $\sigma=\tau=(1,2,3,4,\ldots)$;
  \item [\rm (6)] the (restricted) hexagonal numbers $H_n$ if $\sigma=(3,3,3,\ldots)$ and $\tau=(1,1,1,\ldots)$;
  \item [\rm (7)] the Fine numbers $F_n$ if $\sigma=(0,2,2,\ldots)$ and $\tau=(1,1,1,\ldots)$;
  \item [\rm (8)] the Riordan numbers $R_n$ if $\sigma=(0,1,1,\ldots)$ and $\tau=(1,1,1,\ldots)$.
\end{itemize}

Recently,
Zhu~\cite{Zhu13} established the following criterion for the log-convexity of the Catalan-like numbers.

\begin{theorem}{\rm (\cite[Theorem\ 3.1]{Zhu13})}\label{zhubx}
Assume that $r_{k}t_{k+1}\leq s_{k}s_{k+1}$ for all $k\geq 0$.
Then the sequence $(c_{n,0})_{n\ge 0}$ defined recursively by (\ref{gcln}) is log-convex.
\end{theorem}

Theorem~\ref{zhubx} leads to the log-convexity of many well-known combinatorial sequences,
including the Catalan numbers, the Motzkin numbers, the Bell numbers,
the middle binomial coefficients, the (restricted) hexagonal numbers, the Schr\"oder numbers,
and so on
(see \cite{Zhu13} for details).
On the other hand,
Callan~\cite{Cal} gave an injective proof for the log-convexity of the Motzkin numbers.
Liu and Wang~\cite{LW07} did the same for the Catalan numbers,
and asked for a combinatorial proof for the log-convexity of the Bell numbers.
The object of the present paper is to give a combinatorial proof for Theorem~\ref{zhubx}
from the point of view of weighted Motzkin paths.

A {\it Motzkin path} of length $n$ is a lattice path from $(0,0)$ to $(n,0)$
consisting of up steps $U=(1,1)$,
down steps $D=(1,-1)$ and horizontal steps $H=(1,0)$
that never falls below the $x$-axis.
The {\it height} of a step in a Motzkin path is the $y$ coordinate of the starting point.
We assign a weight $r_{k}$ ($s_{k}, t_{k}$, resp.) to all up steps (all horizontal steps, all down steps, resp.) of height $k$.
Define the {\it weight of a Motzkin path} to be the product of weights of its steps.
%See Figure 1 for an example.
Similarly, we may define a general Motzkin path from $(0,0)$ to $(n,k)$ for $n\geq k$ (see \cite{Fla80} for instance).
Then $c_{n,k}$ defined by (\ref{gcln}) is the sum of weights of all paths from $(0,0)$ to $(n,k)$.
In particular, the Catalan-like number
\begin{equation}\label{cn0}
c_{n,0}=\sum_{P\in\mathcal{M}_{n}}w(P),
\end{equation}
where $\mathcal{M}_{n}$ denotes the set of the Motzkin paths of length $n$ \cite{Aig01}.

In the next section
we give a combinatorial proof of Theorem~\ref{zhubx} by means of (\ref{cn0}).
In Section 3 we point out that the same idea may be applied to show the $q$-version of Theorem~\ref{zhubx}.
We also propose a couple of problems.

\section{Combinatorial proof of Theorem~\ref{zhubx}}

To show the log-convexity of the sequence $(c_{n,0})_{n\geq 0}$,
it suffices to show that
\begin{equation*}
\sum_{P\in\m_{n}}w(P)\sum_{P\in\m_{n}}w(P)\leq\sum_{P\in\m_{n+1}}w(P)\sum_{P\in\m_{n-1}}w(P),
\end{equation*}
or equivalently,
\begin{equation}\label{inq}
\sum_{(P_{1},P_{2})\in (\m_{n},\m_{n})}w(P_1,P_2)
\leq\sum_{(P'_{1},P'_{2})\in (\m_{n+1},\m_{n-1})}w(P'_{1},P'_{2}),
\end{equation}
where $w(Q_1,Q_2)=w(Q_1)w(Q_2)$ denotes the weight of a pair of paths $(Q_1,Q_2)$.

Let $\S$ be a set of pairs of paths.
Denote
$$w(\S)=\sum_{(Q_{1},Q_{2})\in \S} w(Q_1,Q_2).$$
Then (\ref{inq}) is equivalent to
\begin{equation}\label{inq-2}
w(\m_{n},\m_{n})\leq w(\m_{n+1},\m_{n-1}).
\end{equation}

Recall that the Motzkin number $M_n$ is precisely the Catalan-like number $c_{n,0}$
when the all weights $r_k,s_k,t_k$ equal to $1$.
In other words, $M_n$ counts the Motzkin paths of length $n$.
Callan~\cite{Cal} proved the log-convexity of the Motzkin numbers by establishing an injection
from $(\m_{n},\m_{n})$ to $(\m_{n+1},\m_{n-1})$.
We rewrite his proof as follows for our purposes.

For each pair of Motzkin paths $(Q_1,Q_2)$ in $(\m_{n},\m_{n})$ or $(\m_{n+1},\m_{n-1})$,
place the first beginning from $(0,0)$
and the second beginning from $(1,0)$.
Callan introduced the following operation on $(Q_1,Q_2)$
at each possible ``close encounter"
to obtain a new pair of Motzkin paths.
\begin{itemize}
  \item [\rm 1.] Assume that $Q_1$ and $Q_2$ intersect at a lattice point.
  Then reassign the two initial segments to the other path.
  \item [\rm 2.] Assume that $Q_1$ and $Q_2$ intersect at the center point of crossing diagonal steps.
  Then swing the crossing steps $45^{\circ}$ so they become horizontal.
  \item [\rm 3.] Assume that $Q_1$ and $Q_2$ possess a pair of flatsteps forming the top and bottom of a unit square.
  Then change the lower horizontal step to an upstep and the upper one to a downstep.
\end{itemize}

For example,
for a pair of Motzkin paths $(P_1,P_2)$ in $(\m_{n},\m_{n})$,
we place $P_1$ from $(0,0)$ to $(n,0)$ and $P_2$ from $(1,0)$ to $(n+1,0)$.
Clearly, $P_1$ and $P_2$ must intersect,
so they have at least one close encounter.
Callan's operation at each close encounter of $(P_1,P_2)$
will lead to a pair of Motzkin paths in $(\m_{n+1},\m_{n-1})$.

\begin{center}
\setlength{\unitlength}{10mm}
\begin{picture}(8,2.5)(0,0)\thicklines
%%%%% horizontal line
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%% vertex
\put(0,0){\circle*{0.1}}\put(1,1){\circle*{0.1}}\put(2,2){\circle*{0.1}}\put(3,1){\circle*{0.1}}
\put(4,1){\circle*{0.1}}\put(6,1){\circle*{0.1}}\put(7,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}\put(2,1){\circle*{0.1}}\put(3,2){\circle*{0.1}}\put(4,2){\circle*{0.1}}
\put(5,1){\circle*{0.1}}\put(6,0){\circle*{0.1}}\put(7,1){\circle*{0.1}}\put(8,0){\circle*{0.1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(-0.5,-0.5){$(0,0)$}\put(6.5,-0.5){$(7,0)$}\put(0.5,-0.5){$(1,0)$}\put(7.5,-0.5){$(8,0)$}
\put(0.2,0.5){$r_{0}$}\put(1.2,1.5){$r_{1}$}\put(2.7,1.3){$t_{2}$}\put(3.3,1.1){$s_{1}$}
\put(4.4,1.1){$s_{1}$}\put(5.3,1.1){$s_{1}$}\put(6.7,0.3){$t_{1}$}
\put(1.1,0.5){{$r_{0}$}}\put(1.9,1.4){{$r_{1}$}}\put(3.3,2.2){{$s_{2}$}}
\put(4.6,1.5){{$t_{2}$}}\put(5.6,0.5){{$t_{1}$}}\put(6.0,0.5){{$r_{0}$}}
\put(7.6,0.5){{$t_{1}$}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(0,0){\line(1,1){1}}\put(1,1){\line(1,1){1}}\put(2,2){\line(1,-1){1}}\put(3,1){\line(1,0){3}}
\put(6,1){\line(1,-1){1}}
\multiput(1,0)(0.1,0.1){10}{\circle*{0.05}}
\multiput(2,1)(0.1,0.1){10}{\circle*{0.05}}
\multiput(3,2)(0.1,0){10}{\circle*{0.05}}
\multiput(4,2)(0.1,-0.1){10}{\circle*{0.05}}
\multiput(5,1)(0.1,-0.1){10}{\circle*{0.05}}
\multiput(6,0)(0.1,0.1){10}{\circle*{0.05}}
\multiput(7,1)(0.1,-0.1){10}{\circle*{0.05}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{picture}
\end{center}
\bigskip

\begin{center}
\setlength{\unitlength}{5mm}
\begin{picture}(28,2.5)(0,0)\thicklines
%%%%% horizontal line
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%% vertex
\put(0,0){\circle*{0.2}}\put(1,1){\circle*{0.2}}\put(2,2){\circle*{0.2}}\put(3,1){\circle*{0.2}}
\put(4,1){\circle*{0.2}}\put(6,1){\circle*{0.2}}\put(7,0){\circle*{0.2}}
\put(1,0){\circle*{0.2}}\put(2,1){\circle*{0.2}}\put(3,2){\circle*{0.2}}\put(4,2){\circle*{0.2}}
\put(5,1){\circle*{0.2}}\put(6,0){\circle*{0.2}}\put(7,1){\circle*{0.2}}\put(8,0){\circle*{0.2}}

\put(10,0){\circle*{0.2}}\put(11,1){\circle*{0.2}}\put(12,2){\circle*{0.2}}\put(13,1){\circle*{0.2}}
\put(14,1){\circle*{0.2}}\put(16,1){\circle*{0.2}}\put(17,0){\circle*{0.2}}
\put(11,0){\circle*{0.2}}\put(12,1){\circle*{0.2}}\put(13,2){\circle*{0.2}}\put(14,2){\circle*{0.2}}
\put(15,1){\circle*{0.2}}\put(16,0){\circle*{0.2}}\put(17,1){\circle*{0.2}}\put(18,0){\circle*{0.2}}

\put(20,0){\circle*{0.2}}\put(21,1){\circle*{0.2}}\put(22,2){\circle*{0.2}}\put(23,1){\circle*{0.2}}
\put(24,1){\circle*{0.2}}\put(26,1){\circle*{0.2}}\put(27,0){\circle*{0.2}}
\put(21,0){\circle*{0.2}}\put(22,1){\circle*{0.2}}\put(23,2){\circle*{0.2}}\put(24,2){\circle*{0.2}}
\put(25,1){\circle*{0.2}}\put(26,0){\circle*{0.2}}\put(27,1){\circle*{0.2}}\put(28,0){\circle*{0.2}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\put(-0.5,-0.5){$(0,0)$}\put(6.5,-0.5){$(7,0)$}\put(0.5,-0.5){$(1,0)$}\put(7.5,-0.5){$(8,0)$}
%\put(9.5,-0.5){$(0,0)$}\put(16.5,-0.5){$(7,0)$}\put(10.5,-0.5){$(1,0)$}\put(17.5,-0.5){$(8,0)$}
%\put(19.5,-0.5){$(0,0)$}\put(26.5,-0.5){$(7,0)$}\put(0.5,-0.5){$(1,0)$}\put(27.5,-0.5){$(8,0)$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(0,0){\line(1,1){2}}\put(2,2){\line(1,0){2}}\put(4,2){\line(1,-1){2}}
\put(6,0){\line(1,1){1}}\put(7,1){\line(1,-1){1}}
\multiput(1,0)(0.1,0.1){10}{\circle*{0.05}}\multiput(2,1)(0.1,0){40}{\circle*{0.05}}
\multiput(6,1)(0.1,-0.1){10}{\circle*{0.05}}

\put(10,0){\line(1,1){2}}\put(12,2){\line(1,-1){1}}\put(13,1){\line(1,1){1}}
\put(14,2){\line(1,-1){2}}\put(16,0){\line(1,1){1}}\put(17,1){\line(1,-1){1}}
\multiput(11,0)(0.1,0.1){20}{\circle*{0.05}}
\multiput(13,2)(0.1,-0.1){10}{\circle*{0.05}}
\multiput(14,1)(0.1,0){20}{\circle*{0.05}}
\multiput(16,1)(0.1,-0.1){10}{\circle*{0.05}}

\put(20,0){\line(1,1){2}}\put(22,2){\line(1,-1){1}}\put(23,1){\line(1,0){2}}\put(25,1){\line(1,-1){1}}
\put(26,0){\line(1,1){1}}\put(27,1){\line(1,-1){1}}
\multiput(21,0)(0.1,0.1){20}{\circle*{0.05}}
\multiput(23,2)(0.1,0){10}{\circle*{0.05}}
\multiput(24,2)(0.1,-0.1){10}{\circle*{0.05}}
\multiput(25,1)(0.1,0){10}{\circle*{0.05}}
\multiput(26,1)(0.1,-0.1){10}{\circle*{0.05}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(3.5,-1.5){(1)}\put(13.5,-1.5){(2)}\put(23.5,-1.5){(3)}
\end{picture}
\\
\vspace{1cm}
{Figure 1.\quad Callan's operation on a pair of Motzkin paths.}
\end{center}

The above row in Figure 1 is a pair of Motzkin paths of length $7$
with one lattice point of intersection, two pairs of crossing steps and one pair of flatsteps.
The below low is obtained by carrying out Callan's operation
at the first three close encounters of the pair of Motzkin paths.

Now for $(P_1,P_2)\in (\m_n,\m_n)$,
let $(P'_1,P'_2)$ be the pair of paths obtained
by carrying out Callan's operation at the first close encounter of $P_1$ and $P_2$.
Note that the location of the first close encounter will remain invariant.
Hence the mapping
\begin{equation*}\label{tau}
\tau:\quad (P_1,P_2)\mapsto (P'_1,P'_2)
\end{equation*}
is an injection from $(\m_{n},\m_{n})$ to $(\m_{n+1},\m_{n-1})$.
This gives a combinatorial interpretation of the log-convexity of the Motzkin numbers.

Note that the inequality $w(P_1,P_2)\leq w(\tau(P_1,P_2))$ does not hold in general.
For example,
if the first close encounter of $(P_1,P_2)$ is a pair of flatsteps with heights $k$ and $k+1$ respectively,
then $\tau(P_1,P_2)$ is the pair of paths obtained by changing this pair of flatsteps of $(P_1,P_2)$ to a pair of crossing steps.
Thus $w(P_1,P_2)=s_ks_{k+1}\overline{w}\geq r_kt_{k+1}\overline{w}=w(\tau(P_1,P_2))$,
where $\overline{w}$ is the product of weights of steps in $(P_1,P_2)$ except that pair of flatsteps.
Hence Callan's injection $\tau$ can not be used to prove the inequality (\ref{inq-2}).
However, we may still prove (\ref{inq-2}) by means of Callan's operation.

We divide $(\m_{n},\m_{n})$ into two parts:
$\L$ consists of pairs of paths that there is at least one lattice point of intersection
and $\C$ consists of the remain pairs.
Let $(\m_{n+1},\m_{n-1})^*$ consist of pairs of paths in $(\m_{n+1},\m_{n-1})$
that there is at least one close encounter
and divide $(\m_{n+1},\m_{n-1})^*$ into two parts $\L^*$ and $\C^*$ similarly.
We show the inequality (\ref{inq-2}) by showing that
\begin{equation}\label{a}
w(\L)=w(\L^*)
\end{equation}
and
\begin{equation}\label{b}
w(\C)\leq w(\C^*).
\end{equation}

Consider a pair of paths $(P_1,P_2)\in\L$.
Let $p$ be their first lattice point of intersection.
Assume that $p$ splits $P_1$ into parts $P_{11}$ and $P_{12}$,
and splits $P_2$ into parts $P_{21}$ and $P_{22}$.
Then the concatenation $P^*_1$ of $P_{11}$ and $P_{22}$ is a path of length $n+1$,
and the concatenation $P^*_2$ of $P_{12}$ and $P_{21}$ is a path of length $n-1$.
Clearly, $(P^*_1,P^*_2)\in\L^*$ and $p$ is also their first lattice point of intersection.
Furthermore,
$$w(P^*_1,P^*_2)=w(P_{11})w(P_{22})w(P_{12})w(P_{21})=w(P_1,P_2).$$
So the mapping
$$\tau^*:\quad (P_1,P_2)\mapsto (P^*_1,P^*_2)$$
is a weight-preserving bijection from $\L$ to $\L^*$.
Thus the equality (\ref{a}) follows.

It remains to show that the inequality (\ref{b}) holds.
Let $(P_1,P_2)\in\C$.
Then each close encounter of $(P_1,P_2)$ is a pair of crossing steps or a pair of flatsteps.
Define the {\it height} of such a close encounter as the smaller of heights of two corresponding steps.
%Then the weight of a pair of crossing steps (a pair of flatsteps, resp.) of height $k$ is $r_kt_{k+1}$ ($s_ks_{k+1}$, resp.).
%Denote the set of locations of close encounters of $P_1$ and $P_2$ by
%$$\I(P_1,P_2)=\{i: \text{ $P_1$ and $P_2$ have a close encounter at the $i$th step of $P_1$}\}.$$
Callan's operation changes a pair of crossing steps to a pair of flatsetps of the same height,
and vice versa.
%or conversely, changes a pair of flatsetps to a pair of crossing steps of the same height.
%Let $(Q_1,Q_2)$ be a pair of paths in $\C$ or $\C^*$.
If $(P'_1,P'_2)$ is obtained by carrying out Callan's operation on $(P_1,P_2)$ at a pair crossing steps of height $k$,
then $w(P_1,P_2)=s_ks_{k+1}\overline{w}$ and $w(P'_1,P'_2)=r_kt_{k+1}\overline{w}$,
where $\overline{w}$ is the product of weights of steps in $(P_1,P_2)$ except that pair of crossing steps,
and vice versa.

Denote by $\O(P_1,P_2)$ and $\E(P_1,P_2)$ the sets of pairs of paths
obtained by carrying out Callan's operation on $(P_1,P_2)$ at odd and even close encounters respectively.
Then $\O(P_1,P_2)\subseteq (\m_{n+1},\m_{n-1})$ and $\E(P_1,P_2)\subseteq(\m_{n},\m_{n})$.
Let $\{i_1,i_2,\ldots,i_m\}$ be the set of heights of close encounters of $(P_1,P_2)$.
%Then $|\O(P_1,P_2)|=|\E(P_1,P_2)|=2^{m-1}$.
Note that each pair of paths in $\O(P_1,P_2)$ and $\E(P_1,P_2)$ has even and odd pairs of crossing steps respectively.
Hence
\begin{eqnarray*}
w(\O(P_1,P_2))-w(\E(P_1,P_2))
&=&\sum_{(Q_1,Q_2)\in \O(P_1,P_2)}w(Q_1,Q_2)-\sum_{(Q'_1,Q'_2)\in \E(P_1,P_2)}w(Q'_1,Q'_2)\\
&=&(S_{i_1}-R_{i_1})(S_{i_2}-R_{i_2})\cdots (S_{i_m}-R_{i_m})W,
\end{eqnarray*}
where $R_{k}=r_{k}t_{{k+1}},S_{k}=s_{k}s_{{k+1}}$ and
$W$ is the product of weights of steps in $(P_1,P_2)$ except those close encounters.

For example, let $(P_1,P_2)$ be the first pair of paths in Figure 2.
Then
$$\E(P_1,P_2)=\{(P_1,P_2),(Q_1,Q_2)\},\quad O(P_1,P_2)=\{(P'_1,P'_2),(Q'_1,Q'_2)\}.$$
So
\begin{eqnarray*}
% \nonumber to remove numbering (before each equation)
  w(\O(P_1,P_2))-w(\E(P_1,P_2))
   &=& \left[w(P'_1,P'_2)+w(Q'_1,Q'_2)\right]-\left[w(P_1,P_2)+w(Q_1,Q_2)\right] \\
   &=& (R_0R_1+S_0S_1-S_0R_1-R_0S_1)r^2_0r_1t^2_0t_1\\
   &=& (S_0-R_0)(S_1-R_1)r^2_0r_1t^2_0t_1.
\end{eqnarray*}
%$$w(\O(P_1,P_2))-w(\E(P_1,P_2))=(s_0s_1-r_0t_1)(s_1s_2-r_1t_2)r^2_0r_1t^2_0t_1.$$

\begin{center}
\setlength{\unitlength}{5mm}
\begin{picture}(30,3)(0,0)\thicklines
%%%%% horizontal line
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%% vertex
\put(0,0){\circle*{0.2}}
\put(1,0){\circle*{0.2}}\put(1,1){\circle*{0.2}}
\put(2,0){\circle*{0.2}}\put(2,1){\circle*{0.2}}
\put(3,1){\circle*{0.2}}\put(3,2){\circle*{0.2}}
\put(4,1){\circle*{0.2}}\put(4,2){\circle*{0.2}}
\put(5,0){\circle*{0.2}}\put(5,1){\circle*{0.2}}
\put(6,0){\circle*{0.2}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(0,0){\line(1,1){1}}\put(1,1){\line(1,0){1}}\put(2,1){\line(1,1){1}}\put(3,2){\line(1,-1){2}}
\multiput(1,0)(0.1,0){10}{\circle*{0.05}}
\multiput(2,0)(0.1,0.1){20}{\circle*{0.05}}
\multiput(4,2)(0.1,-0.1){20}{\circle*{0.05}}
\put(2.5,-1.5){$(P_1,P_2)$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%% vertex
\put(8,0){\circle*{0.2}}
\put(9,0){\circle*{0.2}}\put(9,1){\circle*{0.2}}
\put(10,0){\circle*{0.2}}\put(10,1){\circle*{0.2}}
\put(11,1){\circle*{0.2}}\put(11,2){\circle*{0.2}}
\put(12,1){\circle*{0.2}}\put(12,2){\circle*{0.2}}
\put(13,0){\circle*{0.2}}\put(13,1){\circle*{0.2}}
\put(6,0){\circle*{0.2}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(8,0){\line(1,1){1}}\put(9,1){\line(1,-1){1}}\put(10,0){\line(1,1){1}}\put(11,1){\line(1,0){1}}\put(12,1){\line(1,-1){1}}
\multiput(9,0)(0.1,0.1){20}{\circle*{0.05}}
\multiput(11,2)(0.1,0){10}{\circle*{0.05}}
\multiput(12,2)(0.1,-0.1){20}{\circle*{0.05}}
\put(10.5,-1.5){$(Q_1,Q_2)$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%% vertex
\put(16,0){\circle*{0.2}}
\put(17,0){\circle*{0.2}}\put(17,1){\circle*{0.2}}
\put(18,0){\circle*{0.2}}\put(18,1){\circle*{0.2}}
\put(19,1){\circle*{0.2}}\put(19,2){\circle*{0.2}}
\put(20,1){\circle*{0.2}}\put(20,2){\circle*{0.2}}
\put(21,0){\circle*{0.2}}\put(21,1){\circle*{0.2}}
\put(22,0){\circle*{0.2}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(16,0){\line(1,1){1}}\put(17,1){\line(1,-1){1}}\put(18,0){\line(1,1){2}}\put(20,2){\line(1,-1){2}}
\multiput(17,0)(0.1,0.1){20}{\circle*{0.05}}
\multiput(19,2)(0.1,-0.1){20}{\circle*{0.05}}
\put(18.5,-1.5){$(P'_1,P'_2)$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%% vertex
\put(24,0){\circle*{0.2}}
\put(25,0){\circle*{0.2}}\put(25,1){\circle*{0.2}}
\put(26,0){\circle*{0.2}}\put(26,1){\circle*{0.2}}
\put(27,1){\circle*{0.2}}\put(27,2){\circle*{0.2}}
\put(28,1){\circle*{0.2}}\put(28,2){\circle*{0.2}}
\put(29,0){\circle*{0.2}}\put(29,1){\circle*{0.2}}
\put(30,0){\circle*{0.2}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(24,0){\line(1,1){1}}\put(25,1){\line(1,0){1}}\put(26,1){\line(1,1){1}}\put(27,2){\line(1,0){1}}\put(28,2){\line(1,-1){2}}
\multiput(25,0)(0.1,0){10}{\circle*{0.05}}
\multiput(26,0)(0.1,0.1){10}{\circle*{0.05}}
\multiput(27,1)(0.1,0){10}{\circle*{0.05}}
\multiput(28,1)(0.1,-0.1){10}{\circle*{0.05}}
\put(26.5,-1.5){$(Q'_1,Q'_2)$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{picture}
\\
\vspace{1cm}
{Figure 2.}
\end{center}

It follows that $w(\E(P_1,P_2))\leq w(\O(P_1,P_2))$
since $R_{k}\leq S_{k}$ for all $k\geq 0$
by the assumption in Theorem \ref{zhubx}.
Clearly, Callan's operation induces an equivalence relation on $\C$
and $\O(P_1,P_2)$ is an equivalence class.
So we have
$$w(\C)=\sum w(\E(P_1,P_2))
\leq \sum w(\O(P_1,P_2))
\leq w(\C^*),$$
where the summation runs over such equivalence classes of $(P_1,P_2)$.
This completes the proof of the inequality (\ref{b}), as required.

\section{Concluding remarks and further work}

Our proof adapts to all Catalan-like numbers satisfying the assumption in Theorem~\ref{zhubx},
and in particular, to the Catalan numbers and the Bell numbers.
A more interesting problem is to construct an injection $\sigma: (\m_n,\m_n)\rightarrow (\m_{n+1},\m_{n-1})$ such that
$w(P_1,P_2)\leq w(\sigma(P_1,P_2))$.
The Catalan-like numbers have various combinatorial interpretations~\cite{Aig99,Aig01,Sta99,Sta11},
so it is natural to find out other combinatorial proof of Theorem~\ref{zhubx}.
We refer the reader to \cite{Do10,GV85,Sag88,Sag92} for some related techniques and topics.

It is well known that the sequence $(a_n)_{n\ge 0}$ is log-convex
if and only if $a_ma_n\leq a_{n+1}a_{m-1}$ for $n\ge m\ge 1$.
So the inequality (\ref{inq-2}) is equivalent to the inequality
\begin{equation}\label{inq-3}
w(\m_m,\m_n)\leq w(\m_{n+1},\m_{m-1}).
\end{equation}
Place each pair of Motzkin paths in $(\m_m,\m_n)$ or $(\m_{n+1},\m_{m-1})$
such that the first begins from $(0,0)$ and the second ends at $(n+1,0)$.
Then the inequality (\ref{inq-3}) can be showed
by the same technique used in the proof of the inequality (\ref{inq-2}).

Zhu~\cite{Zhu13} also gave the $q$-version of Theorem~\ref{zhubx}.
For two polynomials $f(q)$ and $g(q)$, denote $f(q)\leq_{q} g(q)$
if the difference $g(q)-f(q)$ has only nonnegative coefficients.
Let $(f_{n}(q))_{n\geq 0}$ be a polynomial sequence.
It is called {\it $q$-log-convex}
if $f^{2}_{n}(q)\leq_{q}f_{n+1}(q)f_{n-1}(q)$ for all $n\geq 1$.
It is called {\it strongly $q$-log-convex}
if $f_{m}(q)f_{n}(q)\leq_{q}f_{n+1}(q)f_{m-1}(q)$ for any $n\geq m\geq 1$.
It is well known that the strong $q$-log-convexity implies the $q$-log-convexity
but the converse is not true (see \cite{CWY10} for instance).
The method of proof used in the log-convexity can be carried over verbatim to the $q$-log-convexity.

\begin{theorem}{\rm (\cite[Theorem\ 2.1]{Zhu13})}\label{zhubx-q}
Let $(r_{n}(q))_{n\geq 0}$, $(s_{n}(q))_{n\geq 0}$ and $(t_{n}(q))_{n\geq 1}$
be three sequences of polynomials with nonnegative coefficients.
Assume that the triangular array $(c_{n,k}(q))_{0\leq k\leq n}$ satisfies the recurrence
\begin{align*}
&c_{n+1,k}(q)=r_{k-1}(q)c_{n,k-1}(q)+s_k(q)c_{n,k}(q)+t_{k+1}(q)c_{n,k+1}(q)\text{ for $n,k\geq 0$},\\
&c_{0,0}(q)=1, c_{0,k}(q)=0 \text{ for $k\neq 0$}.
\end{align*}
If $r_{k}(q)t_{k+1}(q)\leq_{q} s_{k}(q)s_{k+1}(q)$ for all $k\geq 0$,
then the sequence $(c_{n,0}(q))_{n\geq0}$ is strongly $q$-log-convex.
\end{theorem}

Liu and Wang~\cite{LW07} conjectured
the $q$-log-convexity of sequences of Narayana polynomials of two types
and Chen et al.~\cite{CTWY10,CWY10} proved them by means of the theory of symmetric functions.
It immediately follows from Theorem~\ref{zhubx-q} that
such two sequences are actually strongly $q$-log-convex respectively.
See Zhu~\cite{Zhu13} for details.

\section{Acknowledgment}

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 (Nos.\ 11071030, 11371078) 
and the Specialized Research Fund for the Doctoral Program of Higher Education of China (No.\ 20110041110039).

\begin{thebibliography}{99}
\bibitem{Aig99}M. Aigner,
\textrm{Catalan-like numbers and determinants},
\textit{J. Combin. Theory Ser. A} \textbf{87} (1999), 33--51.

\bibitem{Aig01}M. Aigner,
\textrm{Catalan and other numbers: a recurrent theme},
in H. Crapo and D. Senato, eds., \textit{Algebraic Combinatorics and Computer Science}, Spinger, Berlin, 2001, pp. 347--390.

\bibitem{Cal}D. Callan,
\textrm{Notes on Motzkin and Schr\"{o}der numbers},\\
\url{http://www.stst.wisc.edu/~callan/papersother/}.

\bibitem{CTWY10}
W. Y. C. Chen, R. L. Tang, L. X. W. Wang, and A. L. B. Yang,
\textrm{The $q$-log-convexity of the Narayana polynomials of type B},
\textit{Adv. in Appl. Math.} \textbf{44} (2010), 85--110.

\bibitem{CWY10}
W. Y. C. Chen, L. X. W. Wang, and A. L. B. Yang,
\textrm{Schur positivity and the $q$-log-convexity of the Narayana polynomials},
\textit{J. Algebraic Combin.} \textbf{32} (2010), 303--338.

\bibitem{Do10}
T. Do\v{s}li\'{c},
\textrm{Seven (lattice) paths to log-convexity},
\textit{Acta Appl. Math.} \textbf{110} (2010), 1373--1392.

\bibitem{Fla80}P. Flajolet,
\textrm{Combinatorial aspects of continued fractions},
\textit{Discrete Math.} \textbf{32} (1980), 125--161.

\bibitem{GV85}I. Gessel and G. Viennot,
\textrm{Binomial determinants, paths, and hook length formulae},
\textit{Adv. Math.} \textbf{58} (1985), 300--321.

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

\bibitem{Sag88}B. E. Sagan,
\textrm{Inductive and injective proofs of log concavity results},
\textit{Discrete Math.} \textbf{68} (1988), 281--292.

\bibitem{Sag92}B. E. Sagan,
\textrm{Log concave sequences of symmetric functions and analogs of the Jacobi-Trudi determinants},
\textit{Trans. Amer. Math. Soc.} \textbf{329} (1992), 795--811.

\bibitem{Sta99}R. P. Stanley,
\textit{Enumerative Combinatorics}, Vol.~2, Cambridge Studies in Advanced Mathematics \textbf{62}, 
Cambridge University Press, 1999.

\bibitem{Sta11}R. P. Stanley, \textrm{Catalan addendum},\\
\url{http://www-math.mit.edu/~rstan/ec/catadd.pdf}.

\bibitem{Zhu13}B. X. Zhu,
\textrm{Log-convexity and strong $q$-log-convexity for some triangular arrays},
\textit{Adv. in Appl. Math.} \textbf{50} (2013), 595--606.

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: }
Catalan-like number, log-convexity, weighted Motzkin path.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A000110},
\seqnum{A000957},
\seqnum{A000984},
\seqnum{A001006},
\seqnum{A002212},
\seqnum{A005043}, and
\seqnum{A006318}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 28 2014;
revised version received  March 17 2014.
Published in {\it Journal of Integer Sequences}, March 23 2014.

\bigskip
\hrule
\bigskip

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

\end{document}