\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