% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Some new binomial sums related to the Catalan triangle } % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Yidong Sun$^\dag$ and Fei Ma \\ \small Department of Mathematics, \\[-0.8ex] \small Dalian Maritime University, 116026 Dalian, P.R. China\\[-0.8ex] %\small North Kentucky, U.S.A.\\ \small\tt $^\dag$sydmath@aliyun.com \\ %\and %Forgotten Second Author \qquad Forgotten Third Author\\ %\small School of Hard Knocks\\[-0.8ex] %\small University of Western Nowhere\\[-0.8ex] %\small Nowhere, Australasiaopia\\ %\small\tt \{fsa,fta\}@uwn.edu.ao } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Sep 7, 2013}{Dec,18, 2013}\\ \small Mathematics Subject Classifications: Primary 05A19; Secondary 05A15, 15A15.} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} In this paper, we derive many new identities on the classical Catalan triangle $\mathcal{C}=(C_{n,k})_{n\geq k\geq 0}$, where $C_{n,k}=\frac{k+1}{n+1}\binom{2n-k}{n}$ are the well-known ballot numbers. The first three types are based on the determinant and the fourth is relied on the permanent of a square matrix. It not only produces many known and new identities involving Catalan numbers, but also provides a new viewpoint on combinatorial triangles. % keywords are optional \bigskip\noindent \textbf{Keywords:} Catalan number, ballot number, Catalan triangle. \end{abstract} \section{Introduction} In 1976, by a nice interpretation in terms of pairs of paths on a lattice $\mathbb{Z}^2$, Shapiro \cite{ShapA} first introduced the Catalan triangle $\mathcal{B}=(B_{n,k})_{n\geq k\geq 0}$ with $B_{n,k}=\frac{k+1}{n+1}\binom{2n+2}{n-k}$ and obtained \begin{eqnarray} \sum_{k=0}^{n}B_{n,k}\hskip-.22cm &=&\hskip-.22cm (2n+1)C_{n}, \nonumber \\ \sum_{k=0}^{\min\{m,n\}}B_{n,k}B_{m,k}\hskip-.22cm &=&\hskip-.22cm C_{m+n+1}, \label{eqn 1.1.1} \end{eqnarray} where $C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{1}{2n+1}\binom{2n+1}{n}$ is the $n$th Catalan number. Table 1.1 illustrates this triangle for small $n$ and $k$ up to $6$. Note that the entries in the first column of the Catalan triangle $\mathcal{B}$ are indeed the Catalan numbers $B_{n,0}=C_{n+1}$, which is the reason why $\mathcal{B}$ is called the Catalan triangle. \begin{center} \begin{eqnarray*} \begin{array}{c|cccccccc}\hline n/k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline 0 & 1 & & & & & & \\ 1 & 2 & 1 & & & & & \\ 2 & 5 & 4 & 1 & & & & \\ 3 & 14 & 14 & 6 & 1 & & & \\ 4 & 42 & 48 & 27 & 8 & 1 & & \\ 5 & 132 & 165 & 110 & 44 & 10 & 1 & \\ 6 & 429 & 572 & 429 & 208 & 65 & 12 & 1 \\\hline \end{array} \end{eqnarray*} Table 1.1. The first values of $B_{n,k}$. \end{center} Since then, much attentions have been paid to the Catalan triangle and its generalizations. In 1979, Eplett \cite{Eplett} deduced the alternating sum in the $n$th row of $\mathcal{B}$, namely, \begin{eqnarray*} \sum_{k=0}^{n}(-1)^{k}B_{n,k}\hskip-.22cm &=&\hskip-.22cm C_{n}. \end{eqnarray*} In 1981, Rogers \cite{RogersA} proved that a generalization of Eplett's identity holds in any renewal array. In 2008, Guti\'{e}rrez et al. \cite{Gutierrez} established three summation identities %\begin{eqnarray*} %\sum_{k=0}^{n}(k+1)B_{n,k}^2 \hskip-.22cm &=&\hskip-.22cm \binom{n+3}{2}C_{n+1}C_{n}, \\ %\sum_{k=0}^{n}(k+1)^2B_{n,k}^2 \hskip-.22cm &=&\hskip-.22cm (3n+1)C_{2n}, \\ %\sum_{k=0}^{i}(n+2k+2-i)B_{n,k}B_{n,n+k-i} \hskip-.22cm &=&\hskip-.22cm (n+2)\binom{2n}{i}C_{n+1}, \ (0\leq i\leq n), %\end{eqnarray*} and proposed as one of the open problems to evaluate the moments $\Omega_m=\sum_{k=0}^{n}(k+1)^{m}B_{n,k}^2$. Using the WZ-theory (see \cite{Petkov, Zeilberger}), Miana and Romero computed $\Omega_m$ for $1\leq m\leq 7$. %and deduced that %\begin{eqnarray*} %\sum_{k=0}^{i}(n+2k+2-i)^3B_{n,k}B_{n,n+k-i} \hskip-.22cm &=&\hskip-.22cm (n+2)((n-i)^2+4(n+1))\binom{2n}{i}C_{n+1}, \ (0\leq i\leq n). %\end{eqnarray*} Later, based on the symmetric functions and inverse series relations with combinatorial computations, Chen and Chu \cite{ChenChu} resolved this problem in general. By using the Newton interpolation formula, Guo and Zeng \cite{GuoZeng} generalized the recent identities on the Catalan triangle $\mathcal{B}$ obtained by Miana and Romero \cite{Miana} as well as those of Chen and Chu \cite{ChenChu}. Some alternating sum identities on the Catalan triangle $\mathcal{B}$ were established by Zhang and Pang \cite{ZhangPang}, who showed that the Catalan triangle $\mathcal{B}$ can be factorized as the product of the Fibonacci matrix and a lower triangular matrix, which makes them build close connections among $C_n$, $B_{n,k}$ and the Fibonacci numbers. Motivated by a matrix identity related to the Catalan triangle $\mathcal{B}$ \cite{ShapGet}, Chen et al. \cite{ChenLi} derived many nice matrix identities on weighted partial Motzkin paths. \begin{center} \begin{eqnarray*} \begin{array}{c|cccccccc}\hline n/k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline 0 & 1 & & & & & & \\ 1 & 1 & 1 & & & & & \\ 2 & 2 & 3 & 1 & & & & \\ 3 & 5 & 9 & 5 & 1 & & & \\ 4 & 14 & 28 & 20 & 7 & 1 & & \\ 5 & 42 & 90 & 75 & 35 & 9 & 1 & \\ 6 & 132 & 297 & 275 & 154 & 54 & 11 & 1 \\ \hline \end{array} \end{eqnarray*} Table 1.2. The first values of $A_{n,k}$. \end{center} Aigner \cite{AignerA}, in another direction, came up with the admissible matrix, a kind of generalized Catalan triangle, and discussed its basic properties. The numbers in the first column of the admissible matrix are called Catalan-like numbers, which are investigated in \cite{AignerC} from combinatorial views. The admissible matrix $\mathcal{A}=(A_{n,k})_{n\geq k\geq 0}$ associated to the Catalan triangle $\mathcal{B}$ is defined by $A_{n,k}=\frac{2k+1}{2n+1}\binom{2n+1}{n-k}$, which is considered by Miana and Romero \cite{MianaRom} by evaluating the moments $\Phi_m=\sum_{k=0}^{n}(2k+1)^{m}A_{n,k}^2$. Table 1.2 illustrates this triangle for small $n$ and $k$ up to $6$. The interlaced combination of the two triangles $\mathcal{A}$ and $\mathcal{B}$ forms the third triangle $\mathcal{C}=(C_{n,k})_{n\geq k\geq 0}$, defined by the ballot numbers $$C_{n,k}=\frac{k+1}{2n-k+1}\binom{2n-k+1}{n-k}=\frac{k+1}{n+1}\binom{2n-k}{n}.$$ The triangle $\mathcal{C}$ is also called the ``Catalan triangle" in the literature, despite it has the most-standing form $\mathcal{C}'=(C_{n,n-k})_{n\geq k\geq 0}$ first discovered in 1961 by Forder \cite{Forder}, see for examples \cite{Mathworld, Aval, BarcVerri, FoatHan, KitLies, MianaRom, Sloane}. Table 1.3 illustrates this triangle for small $n$ and $k$ up to $7$. \begin{center} \begin{eqnarray*} \begin{array}{c|cccccccc}\hline n/k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\hline 0 & 1 & & & & & & & \\ 1 & 1 & 1 & & & & & & \\ 2 & 2 & 2 & 1 & & & & & \\ 3 & 5 & 5 & 3 & 1 & & & & \\ 4 & 14 & 14 & 9 & 4 & 1 & & & \\ 5 & 42 & 42 & 28 & 14 & 5 & 1 & & \\ 6 & 132 & 132 & 90 & 48 & 20 & 6 & 1 & \\ 7 & 429 & 429 & 297 & 165 & 75 & 27 & 7 & 1 \\\hline \end{array} \end{eqnarray*} Table 1.3. The first values of $C_{n,k}$. \end{center} Clearly, $$A_{n,k}=C_{n+k, 2k}\ \mbox{and} \ B_{n,k}=C_{n+k+1, 2k+1}.$$ Three relations, $C_{n,0}=C_n$, $C_{n+1,1}=C_{n+1}$ and $\sum_{k=0}^{n}C_{n,k}=C_{n+1}$ bring the Catalan numbers and the ballot numbers in correlation \cite{AignerB, Hilton, RogersB}. Many properties of the Catalan numbers can be generalized easily to the ballot numbers, which have been studied intensively by Gessel \cite{Gessel}. The combinatorial interpretations of the ballot numbers can be found in \cite{AignerC, Bailey, Baur, Bennett, ChenLi, Comtet, Earnshaw, EuLiuYeh, Fanti, HeuMan, Knuth, MerliSprug, Noonan, Riddle, ShapA, StanleyB, SunMa}. It was shown by Ma \cite{ShiMeiMa} that the Catalan triangle $\mathcal{C}$ can be generated by context-free grammars in three variables. The Catalan triangles $\mathcal{B}$ and $\mathcal{C}$ often arise as examples of the infinite matrix associated to generating trees \cite{BacchMerli, Bernini, Merlini, MerlVer}. In the theory of Riordan arrays \cite{ShapB, ShapGet, Sprug}, much interest has been taken in the three triangles $\mathcal{A}, \mathcal{B}$ and $\mathcal{C}$, see \cite{Agapito, ChenLi, CheonJin, CheonKim, CheonKimShap, Luzona, Merlini, Sprugnoli, SunMa}. In fact, $\mathcal{A}, \mathcal{B}$ and $\mathcal{C}$ are Riordan arrays \begin{eqnarray*} \mathcal{A}=(C(t), tC(t)^2), \ \ \mathcal{B}=(C(t)^2, tC(t)^2),\ \mbox{and}\ \mathcal{C}=(C(t), tC(t)), \end{eqnarray*} where $C(t)=\frac{1-\sqrt{1-4t}}{2t}$ is the generating function for the Catalan numbers $C_n$. Recently, Sun and Ma \cite{SunMa} studied the sums of minors of second order of $\mathcal{M}=(M_{n,k}(x,y))_{n\geq k\geq 0}$, a class of infinite lower triangles related to weighted partial Motzkin paths, and obtained the following theorem. \begin{theorem} For any integers $n, r\geq 0$ and $m\geq \ell\geq 0$, set $N_r=\min\{n+r+1, m+r-\ell\}$. Then there holds \small\begin{eqnarray} \sum_{k=0}^{N_r}\det\left(\begin{array}{cc} M_{n,k}(x,y) & M_{m,k+\ell+1}(x,y) \\[5pt] M_{n+r+1,k}(x,y) & M_{m+r+1,k+\ell+1}(x,y) \end{array}\right) \hskip-.22cm &=&\hskip-.22cm \sum_{i=0}^{r} M_{n+i,0}(x,y)M_{m+r-i,\ell}(y,y). \label{eqn 1.1.2} \end{eqnarray} \end{theorem} Recall that a {\em partial Motzkin path} is a lattice path from $(0, 0)$ to $(n, k)$ in the $XOY$-plane that does not go below the $X$-axis and consists of up steps $\mathbf{u}=(1, 1)$, down steps $\mathbf{d}=(1, -1)$ and horizontal steps $\mathbf{h}=(1, 0)$. A {\em weighted partial Motzkin path} (not the same as stated in \cite{ChenLi}) is a partial Motzkin path with the weight assignment that all up steps and down steps are weighted by $1$, the horizontal steps are endowed with a weight $x$ if they are lying on $X$-axis, and endowed with a weight $y$ if they are not lying on $X$-axis. The {\em weight} $w(P)$ of a path $P$ is the product of the weight of all its steps. The {\em weight} of a set of paths is the sum of the total weights of all the paths. Denote by $M_{n,k}(x,y)$ the weight sum of the set $\mathcal{M}_{n,k}(x,y)$ of all weighted partial Motzkin paths ending at $(n,k)$. \begin{center} \small\begin{eqnarray*} \begin{array}{|c|l|l|l|l|l|}\hline n/k & 0 & 1 & 2 & 3 & 4 \\\hline 0 & 1 & & & & \\ 1 & x & 1 & & & \\ 2 & x^2+1 & x+y & 1 & & \\ 3 & x^3+2x+y & x^2+xy+y^2+2 & x+2y & 1 & \\ 4 & x^4+3x^2+2xy+y^2+2 & x^3+x^2y+xy^2+3x+y^3+5y & x^2+2xy+3y^2+3 & x+3y & 1 \\\hline \end{array} \end{eqnarray*} Table 1.4. The first values of $M_{n,k}(x,y)$. \end{center} Table 1.4 illustrates few values of $M_{n,k}(x,y)$ for small $n$ and $k$ up to $4$ \cite{SunMa}. The triangle $\mathcal{M}$ can reduce to $\mathcal{A}, \mathcal{B}$ and $\mathcal{C}$ when the parameters $(x,y)$ are specalized, namely, \begin{eqnarray*} A_{n,k}=M_{n,k}(1,2),\ B_{n,k}=M_{n,k}(2,2) \ \mbox{and} \ C_{n,k}=M_{2n-k, k}(0,0). \end{eqnarray*} In this paper, we derive many new identities on the Catalan triangle $\mathcal{C}$. The first three types are special cases derived from (\ref{eqn 1.1.2}) which are presented in Section 2 and 3 respectively. Section 4 is devoted to the fourth type based on the permanent of a square matrix, and gives a general result on the triangle $\mathcal{M}$ in the $x=y$ case. It not only produces many known and new identities involving Catalan numbers, but also provides a new viewpoint on combinatorial triangles. \vskip.5cm \section{The first two operations on the Catalan triangle} Let $\mathcal{X}=(X_{n,k})_{n\geq k\geq 0}$ and $\mathcal{Y}=(Y_{n,k})_{n\geq k\geq 0}$ be the infinite lower triangles defined on the Catalan triangle $\mathcal{C}$ respectively by \begin{eqnarray*} X_{n,k} \hskip-.22cm &=&\hskip-.22cm \rm{det}\left(\begin{array}{cc} C_{n+k, 2k} & C_{n+k,2k+1} \\[5pt] C_{n+k+1, 2k} & C_{n+k+1,2k+1} \end{array}\right), \\ Y_{n,k} \hskip-.22cm &=&\hskip-.22cm \rm{det}\left(\begin{array}{cc} C_{n+k+1, 2k+1} & C_{n+k+1,2k+2} \\[5pt] C_{n+k+2, 2k+1} & C_{n+k+2,2k+2} \end{array}\right). \end{eqnarray*} Table 2.1 and 2.2 illustrate these two triangles $\mathcal{X}$ and $\mathcal{Y}$ for small $n$ and $k$ up to $5$, together with the row sums. It indicates that the two operations contact the row sums of $\mathcal{X}$ and $\mathcal{Y}$ with the first two columns of $\mathcal{C}$. \begin{center} \begin{eqnarray*} \begin{array}{c|cccccc|c}\hline n/k & 0 & 1 & 2 & 3 & 4 & 5 & row\ sums \\\hline 0 & 1 & & & & & & 1=1^2 \\ 1 & 0 & 1 & & & & & 1=1^2 \\ 2 & 0 & 3 & 1 & & & & 4=2^2 \\ 3 & 0 & 14 & 10 & 1 & & & 25=5^2 \\ 4 & 0 & 84 & 90 & 21 & 1 & & 196=14^2 \\ 5 & 0 & 594 & 825 & 308 & 36 & 1 & 1764=42^2 \\\hline \end{array} \end{eqnarray*} Table 2.1. The first values of $X_{n,k}$. \end{center} \begin{center} \begin{eqnarray*} \begin{array}{c|cccccc|c}\hline n/k & 0 & 1 & 2 & 3 & 4 & 5 & row\ sums \\\hline 0 & 1 & & & & & & 1=1\times 1 \\ 1 & 1 & 1 & & & & & 2=1\times 2 \\ 2 & 3 & 6 & 1 & & & & 10=2\times 5 \\ 3 & 14 & 40 & 15 & 1 & & & 70=5\times 14 \\ 4 & 84 & 300 & 175 & 28 & 1 & & 588=14\times 42 \\ 5 & 594 & 2475&1925 &504 & 45 & 1 & 5544=42\times 132 \\\hline \end{array} \end{eqnarray*} Table 2.2. The first values of $Y_{n,k}$. \end{center} More generally, we obtain the first result which is a consequence of Theorem 1.1. \begin{theorem} For any integers $m\geq \ell\geq 0$ and $n\geq 0$, set $N=\min\{n+1, m-\ell\}$. Then there hold \begin{eqnarray} \sum_{k=0}^{N}\det\left(\begin{array}{cc} C_{n+k,2k} & C_{m+k,2k+\ell+1} \\[5pt] C_{n+k+1,2k} & C_{m+k+1,2k+\ell+1} \end{array}\right) \hskip-.22cm &=&\hskip-.22cm C_{n}C_{m,\ell}, \label{eqn 2.1.1} \\ \sum_{k=0}^{N}\det\left(\begin{array}{cc} C_{n+k+1,2k+1} & C_{m+k+1,2k+\ell+2} \\[5pt] C_{n+k+2,2k+1} & C_{m+k+2,2k+\ell+2} \end{array}\right) \hskip-.22cm &=&\hskip-.22cm C_{n+1}C_{m,\ell}, \label{eqn 2.1.2} \end{eqnarray} or equivalently, \begin{eqnarray} C_{m,\ell}C_{n} \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{N}\frac{ (2k+1)(2k+\ell+2)\lambda_{n,k}(m,\ell)}{(2n+1)_3(2m-\ell)_3}\binom{2n+3}{n-k+1}\binom{2m-\ell+2}{m-k-\ell}, \label{eqn 2.1.3}\\ C_{m,\ell}C_{n+1} \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{N}\frac{ (2k+2)(2k+\ell+3)\mu_{n,k}(m,\ell)}{(2n+2)_3(2m-\ell+1)_3}\binom{2n+4}{n-k+1}\binom{2m-\ell+3}{m-k-\ell}, \label{eqn 2.1.4} \end{eqnarray} where $\lambda_{n,k}(m,\ell)=(2m-\ell)(2m-\ell+1)(n-k+1)(n+k+2)-(2n+1)(2n+2)(m-\ell-k)(m+k+2)$, $\mu_{n,k}(m,\ell)=(2m-\ell+1)(2m-\ell+2)(n-k+1)(n+k+3)-(2n+2)(2n+3)(m-\ell-k)(m+k+3)$ and $(a)_k=a(a+1)\cdots(a+k-1)$ for $k\geq 1$. \end{theorem} \proof Setting $(x,y)=(0,0)$ and $r=1$, replacing $n,m$ respectively by $2n, 2m-\ell-1$ in (\ref{eqn 1.1.2}), together with the relation $C_{n,k}=M_{2n-k, k}(0,0)$, where \begin{eqnarray}\label{eqn 2.1.5} \hskip1cm M_{n,k}(0,0) \hskip-.22cm &=&\hskip-.22cm \left\{ \begin{array}{ll} \frac{k+1}{n+1}\binom{n+1}{\frac{n-k}{2}}, & \mbox{if}\ n-k\ \mbox{even}, \\[5pt] 0, & \mbox{otherwise}. \end{array}\right. \hskip1cm\mbox{\cite[Example (iv)]{SunMa}} \end{eqnarray} we can get (\ref{eqn 2.1.1}). After some simple computation, one can easily derive (\ref{eqn 2.1.3}) from (\ref{eqn 2.1.1}). Similarly, the case $(x,y)=(0,0)$ and $r=1$, after replacing $n,m$ respectively by $2n+1, 2m-\ell$ in (\ref{eqn 1.1.2}), reduces to (\ref{eqn 2.1.2}), which, by some routine simplification, leads to (\ref{eqn 2.1.4}).\qed\vskip.2cm Taking $m=n$ in (\ref{eqn 2.1.3}) and (\ref{eqn 2.1.4}), we have \begin{eqnarray*} \lambda_{n,k}(n,\ell) \hskip-.22cm &=&\hskip-.22cm (\ell+1)(n+k+2)(2k(2n+1)+\ell(n-k+1)), \\ \mu_{n,k}(n,\ell) \hskip-.22cm &=&\hskip-.22cm (\ell+1)(n+k+3)((2k+1)(2n+2)+\ell(n-k+1)), \end{eqnarray*} which yield the following results. \begin{corollary} For any integers $n\geq\ell\geq 0$, there hold {\small\begin{eqnarray} \hskip-0.6cm \frac{1}{2n-\ell+1}\binom{2n-\ell+1}{n-\ell}C_{n} \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n-\ell}\frac{ (2k+1)(2k+\ell+2)\overline{\lambda}_{n,k}(\ell)}{(2n+1)_2(2n-\ell)_3}\binom{2n+2}{n-k+1}\binom{2n-\ell+2}{n-k-\ell}, \label{eqn 2.5.1}\\ \hskip-0.6cm \frac{1}{2n-\ell+1}\binom{2n-\ell+1}{n-\ell}C_{n+1} \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n-\ell}\frac{ (2k+2)(2k+\ell+3)\overline{\mu}_{n,k}(\ell)}{(2n+2)_2(2n-\ell+1)_3}\binom{2n+3}{n-k+1}\binom{2n-\ell+3}{n-k-\ell}, \label{eqn 2.5.2} \end{eqnarray} } where $\overline{\lambda}_{n,k}(\ell)=2k(2n+1)+\ell(n-k+1)$ and $\overline{\mu}_{n,k}(\ell)=(2k+1)(2n+2)+\ell(n-k+1)$. \end{corollary} It should be pointed out that both (\ref{eqn 2.5.1}) and (\ref{eqn 2.5.2}) are still correct for any integer $\ell\leq -1$ if one notices that they hold trivially for any integer $\ell> n$ and both sides of them can be transferred into polynomials in $\ell$. Specially, after shifting $n$ to $n-1$, the case $\ell=-1$ in (\ref{eqn 2.5.1}) and (\ref{eqn 2.5.2}) generates the following corollary. \begin{corollary} For any integer $n\geq 1$, there hold \begin{eqnarray*} \binom{2n}{n}C_{n-1}\hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\frac{(2k+1)^2(4nk-n-k)}{(2n-1)^2(2n)(2n+1)}\binom{2n}{n-k}\binom{2n+1}{n-k}, \\ \binom{2n}{n}C_{n}\hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\frac{(k+1)^2(4nk+n+k)}{n(n+1)(2n+1)^2}\binom{2n+1}{n-k}\binom{2n+2}{n-k}. \end{eqnarray*} \end{corollary} \vskip0.5cm \section{The third operation on the Catalan triangle } Let $\mathcal{Z}=(Z_{n,k})_{n\geq k\geq 0}$ be the infinite lower triangle defined on the Catalan triangle $\mathcal{C}$ by \begin{eqnarray*} Z_{2n,2k}=C_{n+k,2k}C_{n+k+1,2k+1},\ \ \ Z_{2n,2k+1}=C_{n+k+1,2k+1}C_{n+k+1,2k+2},\ \ (n\geq 0), \\ Z_{2n-1,2k}=C_{n+k,2k}C_{n+k,2k+1},\ \ \ Z_{2n-1,2k+1}=C_{n+k,2k+1}C_{n+k+1,2k+2},\ \ (n\geq 1). \end{eqnarray*} Table 3.1 illustrates the triangle $\mathcal{Z}$ for small $n$ and $k$ up to $6$, together with the row sums and the alternating sums of rows. It signifies that the sums and the alternating sums of rows of $\mathcal{Z}$ are in direct contact with the first column of $\mathcal{C}$. Generally, we have the second result which is another consequence of Theorem 1.1. \begin{center} \begin{eqnarray*} \begin{array}{c|ccccccc|c|c}\hline n/k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & row\ sums & alternating\ sums\ of\ rows\ \\\hline 0 & 1 & & & & & & & 1 & 1=1^2 \\ 1 & 1 & 1 & & & & & & 2 & 0\hskip.8cm \\ 2 & 2 & 2 & 1 & & & & & 5 & 1=1^2 \\ 3 & 4 & 6 & 3 & 1 & & & & 14 & 0\hskip.8cm \\ 4 & 10 & 15 & 12 & 4 & 1 & & & 42 & 4=2^2 \\ 5 & 25 & 45 & 36 & 20 & 5 & 1 & & 132 & 0 \hskip.8cm \\ 6 & 70 & 126 & 126 & 70 & 30 & 6 & 1 & 429 & 25=5^2 \\\hline \end{array} \end{eqnarray*} Table 3.1. The first values of $Z_{n,k}$. \end{center} \begin{theorem} For any integers $m, n\geq 0$, let $p=m-n+1$. Then there hold \begin{eqnarray} \sum_{k=0}^{\min\{m,n\}}C_{m+k+1,2k+1}(C_{n+k,2k}+C_{n+k+1,2k+2}) \hskip-.22cm &=&\hskip-.22cm C_{m+n+1}, \label{eqn 3.1.1} \\ \sum_{k=0}^{\min\{m,n\}} C_{m+k+1,2k+1}(C_{n+k,2k}-C_{n+k+1,2k+2}) \hskip-.22cm &=&\hskip-.22cm \left\{\begin{array}{rl} \sum_{i=0}^{p-1}C_{n+i}C_{m-i}, & if \ p\geq 1, \\ 0, & if \ p=0, \\ -\sum_{i=1}^{|p|}C_{n-i}C_{m+i}, & if \ p\leq -1, \end{array}\right. \label{eqn 3.1.2} \end{eqnarray} \end{theorem} \proof The identity (\ref{eqn 3.1.1}) is equivalent to (\ref{eqn 1.1.1}), if one notices that $$C_{m+k+1,2k+1}=B_{m,k}, B_{n,k}=C_{n+k+1,2k+1}=C_{n+k,2k}+C_{n+k+1,2k+2}.$$ For the case $p=m-n+1\geq 0$ in (\ref{eqn 3.1.2}), setting $(x,y)=(0,0)$ in (\ref{eqn 1.1.2}), together with the relation $C_{n,k}=M_{2n-k, k}(0,0)$ and (\ref{eqn 2.1.5}), we have \begin{eqnarray*} \lefteqn{\sum_{k=0}^{\min\{m,n\}} C_{m+k+1,2k+1}(C_{n+k,2k}-C_{n+k+1,2k+2}) }\\ \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\left\{\det\left(\begin{array}{cc} C_{n+k,2k} & 0 \\[5pt] 0 & C_{n+p+k,2k+1} \end{array}\right)+ \det\left(\begin{array}{cc} 0 & C_{n+k+1,2k+2} \\[5pt] C_{n+p+k,2k+1} & 0 \end{array}\right)\right\}\\ \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{2n}\det\left(\begin{array}{cc} M_{2n,k}(0,0) & M_{2n,k+1}(0,0) \\[5pt] M_{2n+2p-1,k}(0,0) & M_{2n+2p-1,k+1}(0,0) \end{array}\right) \\ \hskip-.22cm &=&\hskip-.22cm \sum_{i=0}^{2p-2} M_{2n+i,0}(0,0)M_{2n+2p-i-2,0}(0,0)\\ \hskip-.22cm &=&\hskip-.22cm \sum_{i=0}^{p-1} M_{2n+2i,0}(0,0)M_{2n+2p-2i-2,0}(0,0) \\ \hskip-.22cm &=&\hskip-.22cm \sum_{i=0}^{p-1}C_{n+i}C_{n+p-i-1}=\sum_{i=0}^{p-1}C_{n+i}C_{m-i}, \end{eqnarray*} as desired. Similarly, the case $p\leq -1$ can be proved, the details are left to interested readers.\qed\vskip.2cm Note that a weighted partial Motzkin path with no horizontal steps is just a partial Dyck path. Then the relation $C_{n,k}=M_{2n-k,k}(0,0)$ signifies that $C_{n,k}$ counts the set $\mathcal{C}_{n,k}$ of partial Dyck paths of length $2n-k$ from $(0,0)$ to $(2n-k, k)$ \cite{MerliSprug}. Such partial Dyck paths have exactly $n$ up steps and $n-k$ down steps. For any step, we say that it is at level $i$ if the $y$-coordinate of its end point is $i$. If $P=L_1L_2\dots L_{2n-k-1}L_{2n-k}\in \mathcal{C}_{n,k}$, denote by $\overline{P}=\overline{L}_{2n-k}\overline{L}_{2n-k-1}\dots \overline{L}_2\overline{L}_1$ the reverse path of $P$, where $\overline{L}_i=\mathbf{u}$ if $L_i=\mathbf{d}$ and $\overline{L}_i=\mathbf{d}$ if $L_i=\mathbf{u}$. For $k=0$, a partial Dyck path is an (ordinary) Dyck path. For any Dyck path $P$ of length $2n+2m+2$, its $(2n+1)$-th step $L$ (along the path) must end at odd level, say $2k+1$ for some $k\geq 0$, then $P$ can be uniquely partitioned into $P=P_1LP_2$, where $(P_1, \overline{P_2})\in \mathcal{C}_{n+k,2k}\times\mathcal{C}_{m+k+1,2k+1}$ if $L=\mathbf{u}$ and $(P_1, \overline{P_2})\in \mathcal{C}_{n+k+1,2k+2}\times\mathcal{C}_{m+k+1,2k+1}$ if $L=\mathbf{d}$. Hence, the cases $p=0, 1$ and $2$, i.e., $m=n-1, n$ and $n+1$ in (\ref{eqn 3.1.2}) produce the following corollary. \begin{corollary} For any integer $n\geq 0$, according to the $(2n+1)$-th step $\mathbf{u}$ or $\mathbf{d}$, we have (a) The number of Dyck paths of length $4n$ is bisected; (b) The parity of the number of Dyck paths of length $4n+2$ is $C_n^2$; (c) The parity of the number of Dyck paths of length $4n+4$ is $2C_nC_{n+1}$. \end{corollary} \vskip0.5cm \section{The fourth operation on the Catalan triangle } Let $\mathcal{W}=(W_{n,k})_{n\geq k\geq 0}$ be the infinite lower triangle defined on the Catalan triangle by \begin{eqnarray*} W_{2n,k} \hskip-.22cm &=&\hskip-.22cm \rm{per}\left(\begin{array}{cc} C_{n+k, 2k} & C_{n+k,2k+1} \\[5pt] C_{n+k+1, 2k} & C_{n+k+1,2k+1} \end{array}\right), \\ W_{2n+1,k} \hskip-.22cm &=&\hskip-.22cm {\rm per}\left(\begin{array}{cc} C_{n+k, 2k} & C_{n+k,2k+1} \\[5pt] C_{n+k+2, 2k} & C_{n+k+2,2k+1} \end{array}\right), \end{eqnarray*} where ${\rm per}(A)$ denotes the permanent of a square matrix $A$. Table 4.1 illustrates the triangle $\mathcal{W}$ for small $n$ and $k$ up to $8$, together with the row sums. \begin{center} \begin{eqnarray*} \begin{array}{c|ccccccccc|cc}\hline n/k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & row\ sums \\\hline 0 & 1 & & & & & & & & & 1 \\ 1 & 2 & & & & & & & & & 2 \\ 2 & 4 & 1 & & & & & & & & 5 \\ 3 & 10 & 4 & & & & & & & & 14 \\ 4 & 20 & 21 & 1 & & & & & & & 42 \\ 5 & 56 & 70 & 6 & & & & & & & 132 \\ 6 & 140 & 238 & 50 & 1 & & & & & & 429 \\ 7 & 420 & 792 & 210 & 8 & & & & & & 1430 \\ 8 & 1176 & 2604 & 990 & 91 & 1 & & & & & 4862 \\\hline \end{array} \end{eqnarray*} Table 4.1. The first values of $W_{n,k}$. \end{center} This, in general, motivates us to consider the permanent operation on the triangle $\mathcal{M}=(M_{n,k}(x,y))_{n\geq k\geq 0}$. Recall that $M_{n,k}(x,y)$ is the weight sum of the set $\mathcal{M}_{n,k}(x,y)$ of all weighted partial Motzkin paths ending at $(n,k)$. For any step of a partial weighted Motzkin path $P$, we say that it is at level $i$ if the $y$-coordinate of its end point is $i$. For $1\leq i\leq k$, an up step $\mathbf{u}$ of $P$ at level $i$ is $R$-$visible$ if it is the rightmost up step at level $i$ and there are no other steps at the same level to its right. If $P=L_1L_2\dots L_{n} \in \mathcal{M}_{n,k}(x,y)$, denote by $\overline{P}=\overline{L}_{n}\dots \overline{L}_2\overline{L}_1$ the reverse path of $P$, where $\overline{L}_i=\mathbf{u}, \mathbf{h}$ or $\mathbf{d}$ if $L_i=\mathbf{d}, \mathbf{h}$ or $\mathbf{u}$ respectively. \begin{theorem} For any integers $m, n, r$ with $m\geq n\geq 0$, there holds \begin{eqnarray}\label{eqn 4.1.1} \sum_{k=0}^{m}\rm{per}\left(\begin{array}{cc} M_{n,k}(y,y) & M_{n+r,k+1}(y,y) \\[5pt] M_{m,k}(y,y) & M_{m+r,k+1}(y,y) \end{array}\right) \hskip-.22cm &=&\hskip-.22cm M_{m+n+r,1}(y,y)+H_{n,m}(r), \end{eqnarray} where \begin{eqnarray*} H_{n,m}(r)=\left\{\begin{array}{rl} \sum_{i=0}^{r-1}M_{n+i,0}(y,y)M_{m+r-i-1,0}(y,y), & if \ r\geq 1, \\ 0, & if \ r=0, \\ -\sum_{i=1}^{|r|}M_{n-i,0}(y,y)M_{m-|r|+i-1,0}(y,y), & if \ r\leq -1. \end{array}\right. \end{eqnarray*} \end{theorem} \proof We just give the proof of the part when $r\geq 0$, the other part can be done similarly and is left to interested readers. Define \begin{eqnarray*} {\mathcal{A}}_{n,m,k}^{(r)} \hskip-.22cm &=&\hskip-.22cm \{(P, Q)|P\in \mathcal{M}_{n, k}(y,y), Q\in \mathcal{M}_{m+r, k+1}(y,y)\}, \\ {\mathcal{B}}_{n,m,k}^{(r)} \hskip-.22cm &=&\hskip-.22cm \{(P, Q)|P\in \mathcal{M}_{n+r, k+1}(y,y), Q\in \mathcal{M}_{m, k}(y,y)\}, \end{eqnarray*} and ${\mathcal{C}}_{n,m,k}^{(r,i)}$ to be the subset of ${\mathcal{A}}_{n,m,k}^{(r)}$ such that for any $(P, Q)\in {\mathcal{C}}_{n,m,k}^{(r,i)}$, $Q=Q_{1}\mathbf{u}Q_{2}$ with $Q_{1}\in \mathcal{M}_{i,k}(y,y)$ and $Q_2\in \mathcal{M}_{m+r-i-1,0}(y,y)$ for $k\leq i\leq r-1$, where the step $\mathbf{u}$ is the last R-visible up step of $Q$. Clearly, ${\mathcal{C}}_{n,m,k}^{(r,i)}$ is the empty set if $r=0$. It is easily to see that the weights of the sets ${\mathcal{A}}_{n,m,k}^{(r)}$ and ${\mathcal{B}}_{n,m,k}^{(r)}$ are \begin{eqnarray*} w({\mathcal{A}}_{n,m,k}^{(r)}) \hskip-.22cm &=&\hskip-.22cm M_{n, k}(y,y)M_{m+r, k+1}(y,y), \\ w({\mathcal{B}}_{n,m,k}^{(r)}) \hskip-.22cm &=&\hskip-.22cm M_{n+r, k+1}(y,y)M_{m, k}(y,y). \end{eqnarray*} For $0\leq i