<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}
\DeclareMathOperator{\internal}{\text{int}}
\DeclareMathOperator{\leave}{\text{lev}}

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

	\begin{center}
		\vskip 1cm{\LARGE\bf A Combinatorial
			Identity Concerning Plane  \\
			\vskip .1in
			Colored Trees and its Applications}
		\vskip 1cm
		Ricky X. F. Chen and Christian M. Reidys\\
		Biocomplexity Institute and Department of Mathematics\\
		Virginia Polytechnic Institute and State University\\
		1015 Life Science Circle\\
		Blacksburg, VA 24061\\
		USA\\
		\href{mailto:cxiaof6@vt.edu}{\tt cxiaof6@vt.edu} \\
		\href{mailto:duck@santafe.edu}{\tt duck@santafe.edu} 
	\end{center}

\vskip .2in
	
	\begin{abstract}
In this note, we obtain a
combinatorial identity by counting some colored plane trees. This identity has a plethora of implications. In particular, it solves a bijective problem in Stanley's collection
``Bijective Proof Problems'', and gives a formula for the Narayana polynomials,
as well as an equivalent expression for
the Harer-Zagier formula enumerating unicellular maps. 
	\end{abstract}
	

	
	\section{Introduction}
This note is motivated by giving a combinatorial proof for the following bijective problem in Stanley's collection
``Bijective Proof Problems'' \cite[(15)]{stan2}:
	\begin{align}\label{1e4}
	\sum_{k=0}^n{n\choose k}^2x^k=\sum_{j=0}^n{n\choose j}{2n-j\choose
		n}(x-1)^j.
	\end{align}
	Identities involving the Narayana numbers $N_{n,k}=\frac{1}{n}{n\choose k}{n\choose k-1}$ \cite[\seqnum{A001263}]{OEIS} have been well studied; for instance, see the work~\cite{chen2,li-m,ms}.
	The authors found that the new expression of the Narayana polynomials
	obtained by Mansour and Sun~\cite{ms} (and independently by Chen and Pang~\cite{chen2}) is
	related to \eqref{1e4}. The new expression of the Narayana polynomials reads
	\begin{align}\label{1e5}
	\sum_{k=1}^n N_{n,k}y^k=\sum_{k=0}^n \frac{1}{n+1}{n+1\choose k}{2n-k\choose n}(y-1)^k.
	\end{align}
	\par
	This note is organized as follows. In Section~\ref{sec2}, we
	obtain an elementary identity by counting some kind of colored plane trees.
	This identity implies the
	identities \eqref{1e4} and \eqref{1e5} as special cases.
	Furthermore, it gives a new
	expression for the well-known Harer-Zagier formula, i.e., the generating polynomials for unicellular
	maps~\cite{hz}. The new expression allows us to present a new explicit formula for the numbers $A(n,g)$~\cite[\seqnum{A035309}]{OEIS} counting unicellular maps having $n$ edges and genus $g$~\cite{chr} and achieve the most recent advance on the subject, i.e., Chapuy's recursion for $A(n,g)$, in a different way~\cite{chr}.
	In Section~\ref{sec3}, we enumerate some variations of the colored plane trees so that additional 
	binomial identities are obtained.
	
	\section{A fundamental identity and consequences}\label{sec2}
	In this section, we prove the following identity:

	\begin{theorem}\label{2t1}
		For $n,q\geq 0$, $c\in\mathbb{C}$, we have
		\begin{align}\label{3e3}
		\sum_{k=0}^n{n\choose k}{2n+c+q-k-2\choose
			n+q-1}z^k=
		\sum_{k=0}^n{n\choose k}{n+c+q-2\choose k+q-1}(z+1)^k.
		\end{align}
	\end{theorem}

	
	
	A \emph{colored-labeled plane tree} with $n+1$ vertices is a plane tree where its vertices
	are uniquely labeled by $[n+1]=\{1,2,\ldots,n+1\}$ and its leaves are either not
	colored, or colored $N$ or $Y$. A vertex which is not a leaf is an \emph{internal} vertex.
	Let $\internal(T)$, $\leave_Y(T)$ and $\leave_N(T)$ denote the set of the internal vertices, $Y$-leaves and $N$-leaves
	in a colored-labeled plane tree $T$, respectively.
	As usual, the cardinality of a set $S$ is denoted by $|S|$.
	\par
To begin, we recall a bijection between labeled plane trees and sets of matches,
	called \emph{Chen's bijective algorithm}~\cite{chen1}.
	A \emph{match} is a labeled plane tree with two vertices, i.e., consists of a root and a leaf.
	
	\begin{proposition}(Chen \cite{chen1})\label{2pro1}
		There is a bijection $\phi$ from labeled plane trees with labels in $[n+1]$ to sets of n
		matches with labels in $\{1,\ldots, n+1,(n+2)^*,\ldots,(2n)^*\}$. For a labeled plane tree
		$T$, every internal vertex in $T$ will appear as the root of some match in $\phi(T)$,
		while every leaf of $T$ will appear as the leaf of some match in $\phi(T)$, and vice versa.
	\end{proposition}
	
	Note there are $n$ matches in $\phi(T)$ in total. Except these matches having (unstarred) roots
	which correspond to internal vertices, every match of the rest must have a starred root (i.e., with a label marked with $^*$).
	For details with respect to \emph{Chen's bijective algorithm}, we refer the reader
	to Chen~\cite{chen1}.
	
	
	Let $\Gamma_{n,c,q}$ denote the set of colored-labeled plane trees on $[n+c+q]$ in which
	all vertices with labels in $[q]$ are all uncolored leaves, and all vertices with labels in
	$\{q+1,\dots, q+c\}$ are internal. Using Proposition~\ref{2pro1}, we obtain
	

	\begin{lemma}\label{2lem2}
		There is a bijection between the set of colored-labeled plane
		trees $T\in \Gamma_{n,c,q}$ with $|\internal(T)|+|\leave_Y(T)|=k+c$ and the set of pairs $(A,\chi)$ where $A\subseteq
		[n+c+q]\setminus [c+q]$ with $|A|=k$ and $\chi$ is a set of $n+c+q-1$ matches
		with labels in $\{1,\ldots,n+c+q,(n+c+q+1)^*,\ldots,2(n+c+q-1)^*\}$
		such that all vertices with labels in $\{q+1,\ldots,q+c\}$ are roots and
		other unstarred roots of $\chi$ are in $A$.
	\end{lemma}

	\begin{proof} 
		Given $T\in \Gamma_{n,c,q}$ with $|\internal(T)|+|\leave_Y(T)|=k+c$, clearly the summation of the number of internal vertices other than
	those in $\{q+1,\ldots, q+c\}$ and the number of $Y$-leaves is $k$.
	Let $A$ denote the union of this set of internal vertices and $Y$-leaves.
	According to Proposition~\ref{2pro1}, without considering the coloring of leaves, $T$ corresponds to
	a set of $n+c+q-1$ matches
	with labels in $\{1,\ldots,n+c+q,(n+c+q+1)^*,\ldots,2(n+c+q-1)^*\}$
	such that all vertices with labels in $\{q+1,\dots,q+c\}$ are roots and
	any other unstarred root of $\chi$ is contained in $A$.
	Accordingly, $T$ corresponds to the pair $(A,\chi)$.
	
	Conversely, given a pair $(A,\chi)$, the set of matches $\chi$ corresponds to a
	tree $T\in \Gamma_{n,c,q}$ according to Proposition~\ref{2pro1}.
	It thus remains to color the leaves of $T$. Note, there are three
	classes of leaves: those in $[q]$ which are uncolored by assumption,
	those in $A$ and those not in $A$. We color those leaves in $A$ color $Y$ and
	those not in $A$ color $N$. Thus,
	vertices in $A$ are either internal or $Y$-leaves.
	Hence,  $|\internal(T)|+|\leave_Y(T)|=k+c$,
	completing the proof. 
	\end{proof}
	
	
	

	
	Figure~$1$ illustrates the bijection.
	
	\begin{center}
		\setlength{\unitlength}{1mm}
		\begin{picture}(120,40)
		\put(15,35){\circle*{1.5}}\put(15,35){\line(-4,-5){8}}
		\put(15,35){\line(0,-1){10}}\put(15,35){\line(4,-5){8}}
		\multiput(7,25)(8,0){3}{\circle*{1.5}}
	
		\put(7,25){\line(-1,-2){5}} \put(7,25){\line(2,-5){4}}
		\put(2,15){\circle*{1.5}}\put(11,15){\circle*{1.5}}
	
		\put(15,25){\line(0,-1){10}} \put(15,15){\circle*{1.5}}
		\put(15,15){\line(-1,-3){4}}\put(15,15){\line(1,-3){4}}
		\put(11,3){\circle*{1.5}}\put(19,3){\circle*{1.5}}
		\put(15,25){\line(4,-5){8}}\put(23,15){\circle*{1.5}}
		\put(23,15){\line(0,-1){12}}\put(23,3){\circle*{1.5}}
		\put(16,35){\text{3}}\put(4,26){\text{10}}\put(0,12){\text{2}}\put(10,11){\text{6}}
		\put(7,14){\text{N}}\put(16,26){\text{8}}
		\put(16,14){\text{11}}\put(7,2){\text{5}}\put(12,-1){\text{Y}}
		\put(17,-1){\text{1}}\put(24,25){\text{Y}}\put(23,21){\text{7}}
		\put(25,15){\text{4}}\put(24,-1){\text{9}}\put(25,3){\text{N}} 
		\put(30,26){\vector(1,0){8}}\put(38,25){\vector(-1,0){8}}
		\multiput(50,17)(7,0){10}{\circle*{1}}\multiput(50,4)(7,0){10}{\circle*{1}}
		\multiput(50,17)(7,0){10}{\line(0,-1){13}}
		\put(49,19){\text{4}}\put(49,0){\text{9}}\put(55,19){\text{10}}\put(56,0){\text{2}}
		\put(62,19){\text{$13^*$}}\put(63,0){\text{6}}\put(70,19){\text{3}}
		\put(69,0){\text{$14^*$}}\put(76,19){\text{$11$}}\put(77,0){\text{5}}
		\put(83,19){\text{$16^*$}}\put(84,0){\text{$1$}}\put(91,19){\text{$8$}}
		\put(90,0){\text{$17^*$}}\put(97,19){\text{$18^*$}}\put(97,0){\text{$12^*$}}
		\put(104,19){\text{$15^*$}}\put(105,0){\text{$19^*$}}
		\put(113,19){\text{$20^*$}}\put(113,0){\text{7}} 
		\put(42,28){\text{$A=\{5,7,8,10,11\}$}}\put(42,20){\text{$\chi:$}}
		\put(40,24){\text{$\Big\{$}}
		\end{picture}
	\end{center}
	\begin{center}
		Figure~$1$: A tree in $\Gamma_{11,2,2}$ and its
		corresponding pair $(A,\chi)$.
	\end{center}
	
	\begin{proof}[Proof of Theorem~\ref{2t1}]
 
	firstly, we claim that the number of trees
	$T\in \Gamma_{n,c,q}$ such that $|\internal(T)|+|\leave_Y(T)|=k+c$ is
	$$
	{n\choose k}{k+n+c+q-2\choose n+q-1}(n+c+q-1)!.
	$$
	Based on Lemma~\ref{2lem2}, there are ${n\choose k} $ ways
	to choose $A$. Besides those $c$ prescribed roots
	in $\{q+1,\ldots, q+c\}$, the rest of $(n+c+q-1)-c=n+q-1$ roots
	can only come from the set $A\cup \{(n+c+q+1)^*,\ldots, 2(n+c+q-1)^*\}$
	so that there are
	${k+n+c+q-2\choose n+q-1}$ ways to determine the
	rest of $n+q-1$ roots of $\chi$. At last, there are $(n+c+q-1)!$ ways of pairing up all
	roots and leaves to obtain $n+c+q-1$ matches, whence the claim.
	
	Next we weigh each tree $T\in \Gamma_{n,c,q}$ by
	$z^{|\leave_{_N}(T)|}$. Then, the total weight over all
	trees in $\Gamma_{n,c,q}$ is
	$$
	\sum_{k=0}^nz^{n-k}{n\choose k}{k+n+c+q-2\choose n+q-1}(n+c+q-1)!.
	$$
	
	Counting in a different way, we inspect that the total weight over all trees
	$T \in \Gamma_{n,c,q}$ with $|\internal(T)|=c+k$ equals
	$$
	{n\choose k}{n+c+q-2\choose n+q-1-k}(n+c+q-1)!(z+1)^{n-k}.
	$$
	It follows from Proposition~\ref{2pro1} that a tree $T \in \Gamma_{n,c,q}$
	with $|\internal(T)|=c+k$ (without considering the coloring of leaves) corresponds to a set of
	$n+c+q-1$ matches $\chi$ where there are $c+k$ unstarred roots in total.
	Since vertices in $\{q+1,\ldots, q+c\}$ are always unstarred roots of $\chi$ by assumption,  there are ${n\choose k}$ ways to
	choose from $\{q+c+1,\ldots, n+q+c\}$ $k$ additional unstarred roots of $\chi$. Furthermore, there are ${n+c+q-2\choose
		(n+c+q-1)-c-k}$ ways to choose starred roots
	and $(n+c+q-1)!$ different ways of pairing up. Finally, all
	$n-k$ leaves other than those in $[q]$ can be either
	colored $Y$ or $N$, whence each of them contributes a weight of $(z+1)$.
	Summing over all $0\leq k\leq n$, we also obtain the
	total weight over all trees in $\Gamma_{n,c,q}$
	$$
	\sum_{k=0}^n{n\choose k}{n+c+q-2\choose
		n+q-1-k}(n+c+q-1)!(z+1)^{n-k}.
	$$
	Accordingly we arrive at the identity
	$$
	\sum_{k=0}^nz^{n-k}{n\choose k}{k+n+c+q-2\choose
		n+q-1}=\sum_{k=0}^n{n\choose k}{n+c+q-2\choose n+q-1-k}(z+1)^{n-k}.
	$$
	Since both sides of~\eqref{3e3} can be viewed as polynomials in $c$, it holds for
	any $c\in\mathbb{C}$, completing the proof of Theorem~\ref{2t1}.
	\end{proof}
	
	Theorem~\ref{2t1} can be proved alternatively, e.g., directly working with matchings instead of plane trees.
	However, to the best of our knowledge, this was not presented elsewhere. 
	
	As the first application, it can solve the bijective proof problem of Stanley \cite[(15)]{stan2}:
	\begin{corollary}[Stanley {\cite[(15)]{stan2}}] For $n\geq 0$, we have
		\begin{align}\label{stanbij}
		\sum_{k=0}^n{n\choose k}^2z^k=\sum_{j=0}^n{n\choose j}{2n-j\choose
			n}(z-1)^j.
		\end{align}
	\end{corollary}
	\begin{proof}
		Applying the same combinatorial argument of Theorem~\ref{2t1} to the set $\Gamma_{n,1,1}$ (with $z$ replaced by $z-1$) completes the proof.	
	\end{proof}
	
	
	Second we obtain a combinatorial proof for
	the new expression of the Narayana polynomials obtained
	in Chen and Pang~\cite{chen2} as well as Mansour and Sun~\cite{ms} via studying statistics of lattice paths:
	\begin{corollary}
		For $n\geq 0$, the Narayana numbers $N_{n,k}=\frac{1}{n}{n\choose k}{n\choose k-1}$ satisfy
		
		\begin{align}
		\sum_{k=1}^n N_{n,k}z^k=\sum_{k=0}^n \frac{1}{n+1}{n+1\choose k}{2n-k\choose n}(z-1)^k.
		\end{align}
	\end{corollary}
	\begin{proof}
		Applying the same combinatorial argument of Theorem~\ref{2t1} to the set $\Gamma_{n,2,0}$ (with $z$ replaced by $z-1$) completes the proof.
	\end{proof}
	
	
	It is well-known that, the large Schr\"{o}der numbers (\seqnum{A006318}) $S_n$ \cite{fz,shapiro} which counts the number of
	plane trees having $n$ edges with leaves colored by one of two colors (say color $Y$
	and color $N$), equals the evaluation at $z=2$ in the $n$-th Narayana polynomial, i.e.,
	$$
	S_n=\sum_{k=1}^n N_{n,k}2^k.
	$$
In particular, for $q=0,x=2$, i.e., $\Gamma_{n,2,0}$, Theorem~\ref{2t1} implies the following theorem.
	
	\begin{theorem}\label{2t7}
		Let $T_{n+1}$ denote the number of plane trees of $n+1$ edges with $2$ different internal, marked
		vertices and bi-colored leaves.
		Then, $T_{n+1}={n+1\choose 2}S_n$.
	\end{theorem}
	
	\begin{proof}
		From the proof of Theorem~\ref{2t1}, we know that the number of trees in $\Gamma_{n,2,0}$ is given by
		\begin{align*}
		\sum_{k=0}^n{n\choose k}{n\choose
			k+1}(n+1)!2^{k}.
		\end{align*}
	Ignoring labels we obtain the number of (unlabelled) plane trees of $n+1$ edges
		with $2$ different internal, marked vertices and bi-colored leaves to be
		\begin{align*}
		\frac{1}{2!n!}\sum_{k=0}^n{n\choose k}{n\choose
			k+1}(n+1)!2^{k}=\frac{(n+1)n}{2}\sum_{k=1}^n N_{n,k}2^k={n+1\choose 2}S_n,
		\end{align*}
		which completes the proof.
	\end{proof}
	
	Since the large (and small) Schr\"{o}der numbers 
	satisfy the recurrence \cite{fz}
	\begin{align}
	3(2n-1)S_{n-1}=(n+1)S_{n}+(n-2)S_{n-2}, \quad n\geq 2
	\end{align}
	and $S_0=1,\ S_1=2$, we have the following corollary.
	
	\begin{corollary}\label{2c8}
		The numbers $(T_n)_{n\geq 1}$ satisfy
		\begin{align}
	3(2n-1)T_n=(n-1)T_{n+1}+nT_{n-1}.
		\end{align}
	\end{corollary}
	
	
	\par
	
	Based on Eq.\ \eqref{3e3}, we can also give a new expression for the generating polynomials of
	unicellular maps.
	A \emph{unicellular map} is a graph embedded in a closed orientable surface such that the complement is homeomorphic to an open disk.
	The number of handles of the surface is called the \emph{genus} of the unicellular map. Let $A(n,g)$ denote the number
	of unicellular maps of genus $g$ with $n$ edges. The Harer-Zagier formula \cite{hz} gives a generating
	polynomial for these numbers, which reads
	\begin{align}\label{2e3}
	\sum_{g\geq 0} A(n,g)x^{n+1-2g}=\frac{(2n)!}{2^n n!}\sum_{k\geq 1}2^{k-1}{n\choose k-1}{x\choose k}.
	\end{align}
	Now we can give a new expression via Theorem~\ref{2t1}:
	\begin{corollary}
		\begin{align}\label{2e4}
		\frac{(2n)!}{2^n n!}\sum_{k\geq 1}{n\choose k-1}{x\choose k}2^{k-1}=\frac{(2n)!}{2^n n!}\sum_{k\geq 0}{n\choose k}{x+n-k\choose n+1}.
		\end{align}
	\end{corollary}
	\begin{proof}
		Setting $q=2, x=x-n, z=1$ in \eqref{3e3} completes the proof.
	\end{proof}
	
	From the RHS of Eq.\ \eqref{2e4}, we can obtain a new explicit formula for $A(n,g)$ in terms of a convolution of the Stirling numbers of the first kind $C(n,k)$ (\seqnum{A132393}) and a new way to obtain Chapuy's recursion~\cite{chr}.
	

	
	
	
	
	
	

	
	
	\section{A variation}\label{sec3}
	
	In this section, we count a special subclass of colored plane trees and 
	obtain further identities.
	
	\begin{theorem}\label{3th1}
		For $0\leq n, 1\leq k, 0\leq t&lt;k, q\in \mathbb{Z},x\in \mathbb{C},\omega_k=e^{\frac{j2\pi}{k}}, j^2=-1$,
		we have
		\begin{multline}\label{3e36}
		\sum_{l=0}^n{kn+t\choose kl+t}{kl+x+q+kn+2t-2\choose q+kn+t-1}z^{kl}=\\
		\frac{1}{k}\sum_{i=0}^{kn+t}{kn+t\choose i}{x+q+kn+t-2\choose q+kn+t-1-i}
		z^{i-t}\sum_{l=1}^k \frac{(1+z\omega_k^l)^{kn+t-i}}{(\omega_k^l)^{t-i}}.
		\end{multline}
	\end{theorem}
	\begin{proof}
		Considering the trees $T\in \Gamma_{kn,x,q}$ with $|\internal(T)|+|\leave_Y(T)|=x+kl+t, l\geq 0$,
		we obtain, along the lines of Theorem \ref{2t1}
		\begin{multline*}
		\sum_{l=0}^n {kn+t\choose kl+t}{kl+kn+x+q+2t-2\choose kn+t+q-1}z^{kn-kl}=\\
		\sum_{i=0}^{kn+t}{kn+t\choose i}{kn+t+x+q-2\choose kn+t+q-i-1}\sum_{kl+t\geq i}{kn+t-i\choose kl+t-i}z^{kn-kl}.
		\end{multline*}
		Canceling the term $z^{kn}$ and setting $z=z^{-1}$ in the above identity, the
		second summation on the right hand side becomes
		\begin{align*}
		z^{i-t}\sum_{l\geq 0}{kn+t-i\choose kl+t-i}z^{kl+t-i}.
		\end{align*}
		From the identity~\cite[Eq.\ $(1.53)$]{sprug}, we have
		\begin{align*}
		\sum_{i\geq 0}{n\choose a+ki}x^{a+ki}=\frac{1}{k}\sum_{i=1}^k (\omega_k^i)^{-a}(1+x\omega_k^i)^{n}, k-1\geq a, a\in \mathbb{Z}.
		\end{align*}
		Therefore, setting $a=t-i,n=kn+t-i,k=k$ we obtain
		\begin{align*}
		\sum_{l\geq 0}{kn+t-i\choose kl+t-i}z^{kl+t-i}=\frac{1}{k}\sum_{l=1}^k(\omega_k^l)^{i-t}(1+z\omega_k^l)^{kn+t-i}
		\end{align*}
		and the proof follows.
	\end{proof}
	
	As the first application of Theorem~\ref{3th1}, we 
	obtain two identities involving the Narayana numbers.
	
	\begin{corollary}
		\begin{align}
		\sum_l N_{n,l+1}z^l (1+z)^{n-l}&amp;=\sum_l \frac{1}{n}{n\choose l}{n+l \choose l-1}z^l,\\
		\sum_{l=0}^{2n+s_1}N_{2n+s_1,l+1}2^{2n+s_1-l}&amp;=\sum_{l=0}^n \frac{1}{n}{2n+s_1\choose 2l+s_1}{2n+2l+2s_1\choose 2l+s_1+1}.
		\end{align}
	\end{corollary}
	
	\begin{proof}
	 Setting $k=1$ in Eq.\ \eqref{3e36}, we obtain the first identity.
	Setting $k=2$, $q=0,~x=2,~z=1$ leads to the second one. 
	\end{proof}
	
	
	
	
	Furthermore, we derive the following relations which can be viewed as
	analogues of the well-known relation:
	$$
	\sum_{i=1, ~i\in odd}^n {n \choose i}=\sum_{i=0, ~i\in even}^n {n \choose i}.
	$$
	\begin{corollary}For $n\geq 0$, we have
		\begin{align}
		\sum_{l=0}^n{2n\choose 2l}{2l+2n\choose 2l}&amp;=\sum_{l=0}^{n-1}{2n\choose 2l+1}{2n+2l+1\choose 2l+1}+1,\\
		\sum_{l=0}^n{2n+1\choose 2l}{2l+2n+1\choose 2l}&amp;=\sum_{l=0}^{n}{2n+1\choose 2l+1}{2n+2l+2\choose 2l+1}-1.
		\end{align}
	\end{corollary}
	\begin{proof}
		Setting $x=q=1, ~z=1, ~k=2$ in Eq.\ \eqref{3e36}, we obtain, for $0\leq s_1 &lt;2$,
		$$
		\sum_{l=0}^n2{2n+s_1\choose 2l+s_1}{2l+2n+2s_1\choose 2n+s_1}-1=\sum_{l=0}^{2n+s_1}{2n+s_1\choose l}^22^{2n+s_1-l}.
		$$
		However, from Eq.\ \eqref{stanbij}, we have
		
		\begin{align*}
		\sum_{l=0}^{2n+s_1}{2n+s_1\choose l}^22^{2n+s_1-l}=\sum_{j=0}^{2n+s_1}{2n+s_1\choose j}{2n+s_1+j\choose
			j}.
		\end{align*}
		Then,
		$$
		\sum_{l=0}^n2{2n+s_1\choose 2l+s_1}{2l+2n+2s_1\choose 2l+s_1}-1=\sum_{j=0}^{2n+s_1}{2n+s_1\choose j}{2n+s_1+j\choose
			j},
		$$
		from which the corollary follows.
		
		
	\end{proof}
	

	\section{Acknowledgments}
	The authors thank the anonymous referees for their valuable feedback.
	
	

	\begin{thebibliography}{99}
		
		\bibitem{chen1}W. Y. C. Chen, A general bijective algorithm for trees, {\it Proc. Natl. Acad. Sci. USA} {\bf 87} (1990), 9635--9639.
		\bibitem{chen2}W. Y. C. Chen and S. X. M. Pang, On the combinatorics of the Pfaff identity, {\it Discrete Math.} {\bf 309} (2009), 2190--2196.
		
		
		\bibitem{chr} R. X. F. Chen and C. M. Reidys,  New formulas counting one-face maps and Chapuy's recursion, in revision.
		
		
	
		\bibitem{fz}D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, {\it J. Combin. Theory Ser. A} {\bf 80} (1997), 380--384.

		\bibitem{hz} J. Harer and D. Zagier, The Euler characteristic of the moduli space of curves, {\it Invent. Math.} {\bf 85} (1986), 457--485.

      \bibitem{li-m} N. Y. Li and T. Mansour, An
identity involving Narayana numbers, {\it European J. Combin.} {\bf 29} (2008), 672--675.
		
		
		\bibitem{ms}T. Mansour and Y. Sun, Identities involving Narayana polynomials and Catalan numbers, {\it Discrete Math.} {\bf 309} (2009), 4079--4088.
		
		
		

		

		\bibitem{stan2} R. P. Stanley, {Bijective proof problems}, 2009, \url{http://www-math.mit.edu/~rstan/bij.pdf}.
	
		

		\bibitem{shapiro} L. W. Shapiro and R. A. Sulanke, Bijections for the Schr\"{o}der numbers, {\it Math. Mag.} {\bf 73} (2000), 369--376.

\bibitem{sprug} R. Sprugnoli, {Riordan array proofs of identities in
Gould's book}, 2006, \\
\url{http://www.dsi.dsi.unifi.it/~resp/GouldBK.pdf}.

		
		
	
		
		\bibitem{OEIS} N. J. A. Sloane, {The On-line Encyclopedia of Integer Sequences}, \url{http://oeis.org}.
		
		
		
		
		
	\end{thebibliography}
	
	
	
	
	\bigskip
	\hrule
	\bigskip
	
	\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A19.
	
	\noindent \emph{Keywords:} Narayana polynomial, colored tree,
	Stanley's bijective proof problem, Harer-Zagier formula.

	
	\bigskip
	\hrule
	\bigskip
	
	
	\noindent
	(Concerned with sequences
	\seqnum{A001263}, \seqnum{A006318}, \seqnum{A035309} and \seqnum{A132393}.)
	
	\bigskip
	\hrule
	\bigskip
	

\vspace*{+.1in}
\noindent
Received September 13 2016;
revised versions received  January 18 2017; January 23 2017; January
25 2017.
Published in {\it Journal of Integer Sequences}, January 26 2017.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                






</pre></body></html>