\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