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

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Exponential Generating Functions for Trees \\
\vskip .1in
with
Weighted Edges and Labeled Nodes
}
\vskip 1cm
\large
Wen-jin Woan\footnote{Author's current address:
2103 Opal Ridge, Vista, CA 92081, USA.}\\
Howard University \\
Washington, DC 20059\\ 
USA\\
\href{mailto:wjwoan@sbcglobal.net}{\tt wjwoan@sbcglobal.net}\\
\ \\
Barbara Tankersley \\
North Carolina Agricultural and Technical State University\\
Greensboro, NC 27411\\
USA \\
\href{mailto:tankers@ncat.edu}{\tt tankers@ncat.edu} \\
\end{center}


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}


\begin{abstract} We study labeled trees and find that this is a class of combinatorial objects which is perfect
for the study of some exponential generating functions.
\end{abstract}

\newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{%
defin}\normalfont\quad}{\end{defin}} \newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{remar}[theorem]{Remark} \newenvironment{remark}{\begin{remar}%
\normalfont\quad}{\end{remar}} \newtheorem{algo}[theorem]{Algorithm}
\newenvironment{algorithm}{\begin{algo}\normalfont\quad}{\end{algo}}

\section{Introduction}

In this paper we study the counting of various trees with labeled nodes and
weighted edges and its exponential generating functions. Section 1 is about
rooted plane trees. Section 2 is about labeled trees. In Section 3, we give
some examples of labeled trees and its exponential generating functions. In
Section 4, we discuss weighted and labeled trees and its exponential
generating functions. In Chapter 1 of \cite{RS}, two tree representations of permutations are studied, here we study the combinatorics of the second tree representation through generating functions and show the connections with some classical sequences. A similar study corresponding to the first tree representation of \cite{RS} has been done in \cite{CS,Z}.

The counting of trees (rooted plane trees) is the Catalan sequence, $%
c_0=1,1,2,5,14,42,\ldots$ Traverse the tree starting from the root going up on
the left side of the branches and coming down on the right side of the
branches. On the way down if we encounter a right branch we go up. Label the
nodes in order with $[n]=\{0,1,2,3,\ldots,n\}$ by preorder, i.e., label the
nodes at the first visit.

\begin{example}
Rooted plane trees of order $n=3,$ $c_3=5$
\end{example}

\setlength{\unitlength}{.9cm}
\begin{picture}(14,5)
\put(1,1){\line(0,1){3}}   % first tree for N=3 row 1

\put(3,1){\line(0,1){1}} \put(2,3){\line(1,-1){1}}
\put(3,2){\line(1,1){1}}

\put(6,1){\line(1,1){1}} \put(5,2){\line(1,-1){1}}
\put(5,2){\line(0,1){1}}

\put(9,1){\line(-1,1){1}} \put(9,1){\line(1,1){1}}
\put(10,2){\line(0,1){1}}

\put(12,1){\line(-1,1){1}} \put(12,1){\line(0,1){1}} \put(12,1){\line(1,1){1}}

\multiput(1,1)(0,1){4}{\circle{.5}}    % now I will add the vertices/Nodes to the trees
\multiput(3,1)(3,0){3}{\circle{.5}}
\multiput(3,2)(2,0){3}{\circle{.5}}
\multiput(2,3)(2,0){2}{\circle{.5}} \put(5,3){\circle{.5}}
\multiput(8,2)(2,0){2}{\circle{.5}} \put(10,3){\circle{.5}}
\put(12,1){\circle{.5}} \multiput(11,2)(1,0){3}{\circle{.5}}


\put(1.06,1){\tiny{0}} \put(1.06,2){\tiny{1}}\put(1.06,3){\tiny{2}} % numbers vertices
\put(1.06,4){\tiny{3}}

\put(3.06,1){\tiny{0}}
\put(3.07,1.86){\tiny{1}}\put(2.06,3){\tiny{2}}
\put(4.06,3){\tiny{3}}

\put(6.08,.9){\tiny{0}} \put(5.08,2){\tiny{1}}\put(5.05,3){\tiny{2}}
\put(7.06,2){\tiny{3}}

\put(9.08,.9){\tiny{0}}
\put(8.08,2){\tiny{1}}\put(10.06,2){\tiny{2}}
\put(10.06,3){\tiny{3}}

\put(12.08,.9){\tiny{0}} \put(11.08,2){\tiny{1}}\put(12.05,2){\tiny{2}} \put(13.06,2){\tiny{3}}


 \end{picture}

\section{Labeled Trees}

In this section we define labeled trees and study some well known partitions
of permutations. Let $P=a_1a_2a_3 \cdots a_n$ be a permutation, locate the
smallest number $a_i.$ Partition $P=Fa_iB$ by $F$ the part before $a_i$\ and
$B$ the part after $a_i$, then inductively label the first node of the left
most branch by $a_i\;$and put the subtree for $F$ on top of $a_i\;$and the
subtree for $B$ to the right of $a_i.\;$Note that the labeled tree satisfies
the following conditions:

(1)\ Increasing on any path going up,

(2)\ Increasing from left to right of the immediate siblings of a node.

\begin{definition}
A $labeled\;tree$ is a tree with nodes labeled by $[n]=\{0,1,2,3,4,\ldots,n\}$
which satisfies the above two conditions. It is also called an increasing tree,
please refer to \cite{RS}.
\end{definition}

\begin{example}
We read the labeled trees in postorder and they correspond to permutations
as follows: For $n=3,$ the third tree has two choices (2 or 3) for position $%
2$ and the count is

$s_3=$ $1+1+2+1+1=6.$

Permutations: $321,231,213,312,132,123.$

\setlength{\unitlength}{.7cm}
\begin{picture}(14,5)
\put(1,1){\line(0,1){3}}   % first tree for N=3 row 1

\put(3,1){\line(0,1){1}} \put(2,3){\line(1,-1){1}}
\put(3,2){\line(1,1){1}}

\put(6,1){\line(1,1){1}} \put(5,2){\line(1,-1){1}}
\put(5,2){\line(0,1){1}}

\put(9,1){\line(1,1){1}} \put(8,2){\line(1,-1){1}}
\put(8,2){\line(0,1){1}}

\put(12,1){\line(-1,1){1}} \put(12,1){\line(1,1){1}}
\put(13,2){\line(0,1){1}}

\put(15,1){\line(-1,1){1}} \put(15,1){\line(0,1){1}}
\put(15,1){\line(1,1){1}}

\multiput(1,1)(0,1){4}{\circle{.7}}    % now I will add the vertices/Nodes to the trees
\multiput(3,1)(0,1){2}{\circle{.7}}
\multiput(2,3)(2,0){2}{\circle{.7}}

\put(6,1){\circle{.7}} \multiput(5,2)(2,0){2}{\circle{.7}}
\put(5,3){\circle{.7}}

\put(9,1){\circle{.7}} \multiput(8,2)(2,0){2}{\circle{.7}}
\put(8,3){\circle{.7}}

\put(12,1){\circle{.7}} \multiput(11,2)(2,0){2}{\circle{.7}}
\put(13,3){\circle{.7}}

\put(15,1){\circle{.7}} \multiput(14,2)(1,0){3}{\circle{.7}}

\put(1.06,.9){\tiny{0}} \put(1.06,2){\tiny{1}}\put(1.06,3){\tiny{2}} % numbers vertices
\put(1.06,4){\tiny{3}}

\put(3.06,.9){\tiny{0}}
\put(3.06,1.82){\tiny{1}}\put(2.06,3){\tiny{2}}
\put(4.06,3){\tiny{3}}

\put(6.08,.8){\tiny{0}} \put(5.08,2){\tiny{1}}\put(5.06,3){\tiny{2}}
\put(7.06,2){\tiny{3}}

\put(9.08,.8){\tiny{0}} \put(8.08,2){\tiny{1}}\put(8.06,3){\tiny{3}}
\put(10.06,2){\tiny{2}}

\put(12.08,.8){\tiny{0}}
\put(11.08,2){\tiny{1}}\put(13.06,2){\tiny{2}}
\put(13.06,3){\tiny{3}}

\put(15.08,.8){\tiny{0}}
\put(14.08,2){\tiny{1}}\put(15.06,2){\tiny{2}}
\put(16.06,2){\tiny{3}}
\end{picture}
\end{example}

It is well known that the counting of labeled trees is $n!$, please refer to
\cite[Prop.\ 1.3.16]{RS} for the properties of this section. You  can
also find related subjects in \cite{BLL,RS2}.



\section{Some Examples of Labeled Trees}

In this section we study some examples of labeled trees and its exponential
generating functions(EGF). Let $A(x)=\sum \frac 1{n!}a_nx^n$ and $B(x)=\sum
\frac 1{n!}b_nx^n\;$be the exponential generating functions for the
sequences $\{a_n\},\;\{b_n\}$ , then

$A(x)B(x)=\sum \frac 1{n!}(\sum \binom nka_kb_{n-k})x^n\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(1)$

On the other hand, if we let $t_n\;$be the number of labeled trees and
partition the tree by the first node of the leftmost branch, then we have
the recurrence

$t_n=\sum_{k=0}^{n-1}\binom{n-1}kt_kt_{n-1-k}.$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
$(2)$

We choose $k$ numbers from $\{2,3,4,\ldots,n\}$ to form a subtree on top of
node $1$ and the rest to the right of node $1$.

By the similarity of (1) and (2), it certainly is appropriate to study its
exponential generating functions instead of ordinary generating functions.

\begin{remark}
\label{six} A tree is said to be a 1-2 $tree$, if every vertex has outdegree
at most two. The counting of 1-2 trees is the Motzkin sequence, $%
1,1,2,4,9,21,51,\ldots$. The counting of labeled 1-2 trees is the sequence of
zig-zag permutations, $t_0=1,1,2,5,16,61,272,\ldots$

The following are the list of labeled 1-2 trees for $n=3,4$

\setlength{\unitlength}{.7cm}
\begin{picture}(18,5)
\put(1,1){\line(0,1){3}}  % first tree for N=3 row 1

\put(4,1){\line(0,1){1}} \put(3,3){\line(1,-1){1}}
\put(4,2){\line(1,1){1}}

\put(8,1){\line(1,1){1}} \put(7,2){\line(1,-1){1}}
\put(7,2){\line(0,1){1}}

\put(12,1){\line(1,1){1}} \put(11,2){\line(1,-1){1}}
\put(11,2){\line(0,1){1}}

\put(16,1){\line(1,1){1}} \put(15,2){\line(1,-1){1}}
\put(17,2){\line(0,1){1}}

\multiput(1,1)(0,1){4}{\circle{.7}}    % now I will add the vertices/Nodes to the trees

\multiput(4,1)(0,1){2}{\circle{.7}}
\multiput(3,3)(2,0){2}{\circle{.7}}

\put(8,1){\circle{.7}} \multiput(7,2)(2,0){2}{\circle{.7}}
\put(7,3){\circle{.7}}

\put(12,1){\circle{.7}} \multiput(11,2)(2,0){2}{\circle{.7}}
\put(11,3){\circle{.7}}

\put(16,1){\circle{.7}} \multiput(15,2)(2,0){2}{\circle{.7}}
\put(17,3){\circle{.7}}


% Add Nodes
\put(1.06,1){\tiny{0}} \put(1.06,2){\tiny{1}} \put(1.06,3){\tiny{2}} % Numbered vertices Row 1
\put(1.06,4){\tiny{3}}

\put(4.08,1){\tiny{0}}
\put(4.06,1.8){\tiny{1}}\put(3.08,3){\tiny{2}}
\put(5.06,3){\tiny{3}}

\put(8.08,.8){\tiny{0}} \put(7.08,2){\tiny{1}}\put(7.06,3){\tiny{2}}
\put(9.06,2){\tiny{3}}

\put(12.08,0.8){\tiny{0}}
\put(11.08,2){\tiny{1}}\put(11.06,3){\tiny{3}}
\put(13.06,2){\tiny{2}}

\put(16.08,0.9){\tiny{0}}
\put(15.08,2){\tiny{1}}\put(17.06,2){\tiny{2}}
\put(17.06,3){\tiny{3}}
\end{picture}

$t_3=(1+1+2+1\ )\ =5,$

\setlength{\unitlength}{.7cm}
\begin{picture}(18,22)
\put(1,17){\line(0,1){4}} % first tree for N=4 row 2

\put(4,17){\line(0,1){2}} \put(4,19){\line(-1,1){1}}
\put(4,19){\line(1,1){1}}

\put(8,17){\line(0,1){1}} \put(7,19){\line(1,-1){1}}
\put(7,19){\line(0,1){1}} \put(8,18){\line(1,1){1}}


\put(12,17){\line(0,1){1}} \put(11,19){\line(1,-1){1}}
\put(11,19){\line(0,1){1}} \put(12,18){\line(1,1){1}}


\put(16,17){\line(0,1){1}} \put(16,18){\line(-1,1){1}}
\put(16,18){\line(1,1){1}} \put(17,19){\line(0,1){1}}

\put(2,12){\line(1,1){1}} \put(2,12){\line(-1,1){1}} % Row 2
\put(1,13){\line(0,1){1}} \put(3,13){\line(0,1){1}}

\put(6,12){\line(1,1){1}} \put(6,12){\line(-1,1){1}}
\put(5,13){\line(0,1){1}} \put(7,13){\line(0,1){1}}

\put(10,12){\line(1,1){1}} \put(10,12){\line(-1,1){1}}
\put(9,13){\line(0,1){1}} \put(11,13){\line(0,1){1}}

\put(14,12){\line(-1,1){1}} \put(14,12){\line(1,1){1}}
\put(13,13){\line(0,1){2}}

\put(2,6){\line(-1,1){1}} \put(2,6){\line(1,1){1}}   % Row 3
\put(1,7){\line(0,1){2}}

\put(6,6){\line(-1,1){1}} \put(6,6){\line(1,1){1}}
\put(5,7){\line(0,1){2}}

\put(10,6){\line(-1,1){1}} \put(10,6){\line(1,1){1}}
\put(11,7){\line(0,1){2}}

\put(15,6){\line(1,1){1}} \put(15,6){\line(-1,1){1}}
\put(14,7){\line(-1,1){1}} \put(14,7){\line(1,1){1}}

\put(3,1){\line(1,1){1}} \put(3,1){\line(-1,1){1}} %Row 4
\put(2,2){\line(-1,1){1}} \put(2,2){\line(1,1){1}}

\put(8,1){\line(1,1){1}} \put(8,1){\line(-1,1){1}}
\put(7,2){\line(-1,1){1}} \put(7,2){\line(1,1){1}}

\put(12,1){\line(-1,1){1}} \put(12,1){\line(1,1){1}}
\put(13,2){\line(-1,1){1}} \put(13,2){\line(1,1){1}}

% Add Nodes
\multiput(1,17)(0,1){5}{\circle{.7}} % ADD Nodes - Row 1

\multiput(4,17)(0,1){3}{\circle{.7}}
\multiput(3,20)(2,0){2}{\circle{.7}}

\multiput(8,17)(0,1){2}{\circle{.7}} \put(7,20){\circle{.7}}
\multiput(7,19)(2,0){2}{\circle{.7}}

\multiput(12,17)(0,1){2}{\circle{.7}} \put(11,20){\circle{.7}}
\multiput(11,19)(2,0){2}{\circle{.7}}

\multiput(16,17)(0,1){2}{\circle{.7}}
\multiput(15,19)(2,0){2}{\circle{.7}} \put(17,20){\circle{.7}}

\put(2,12){\circle{.7}} \multiput(1,13)(2,0){2}{\circle{.7}}
\multiput(1,14)(2,0){2}{\circle{.7}}

\put(6,12){\circle{.7}} \multiput(5,13)(2,0){2}{\circle{.7}}
\multiput(5,14)(2,0){2}{\circle{.7}}

\put(10,12){\circle{.7}} \multiput(9,13)(2,0){2}{\circle{.7}}
\multiput(9,14)(2,0){2}{\circle{.7}}

\put(14,12){\circle{.7}} \multiput(13,13)(2,0){2}{\circle{.7}}
\multiput(13,14)(0,1){2}{\circle{.7}}

\put(2,6){\circle{.7}} \multiput(1,7)(2,0){2}{\circle{.7}}
\multiput(1,8)(0,1){2}{\circle{.7}}

\put(6,6){\circle{.7}} \multiput(5,7)(2,0){2}{\circle{.7}}
\multiput(5,8)(0,1){2}{\circle{.7}}

\put(10,6){\circle{.7}} \multiput(9,7)(2,0){2}{\circle{.7}}
\multiput(11,8)(0,1){2}{\circle{.7}}

\put(15,6){\circle{.7}} \multiput(14,7)(2,0){2}{\circle{.7}}
\multiput(13,8)(2,0){2}{\circle{.7}}

\put(3,1){\circle{.7}} \multiput(2,2)(2,0){2}{\circle{.7}}
\multiput(1,3)(2,0){2}{\circle{.7}}

\put(8,1){\circle{.7}} \multiput(7,2)(2,0){2}{\circle{.7}}
\multiput(6,3)(2,0){2}{\circle{.7}}

\put(12,1){\circle{.7}} \multiput(11,2)(2,0){2}{\circle{.7}}
\multiput(12,3)(2,0){2}{\circle{.7}}

% Add numbers to vertices


\put(1.06,17){\tiny{0}} \put(1.06,18){\tiny{1}}  % Numbered vertices for Row 2
\put(1.06,19){\tiny{2}} \put(1.06,20){\tiny{3}}
\put(1.06,21){\tiny{4}}

\put(4.06,17){\tiny{0}} \put(4.06,18){\tiny{1}}
\put(4.06,18.8){\tiny{2}} \put(3.06,20){\tiny{3}}
\put(5.06,20){\tiny{4}}

\put(8.06,17){\tiny{0}} \put(8.06,17.8){\tiny{1}}
\put(7.07,19){\tiny{2}} \put(7.06,20){\tiny{3}}
\put(9.06,19){\tiny{4}}

\put(12.06,17){\tiny{0}} \put(12.06,17.8){\tiny{1}} \put(11.07,19){\tiny{2}} \put(11.06,20){\tiny{4}}
\put(13.06,19){\tiny{3}}

\put(16.06,17){\tiny{0}} \put(16.06,17.8){\tiny{1}}
\put(15.07,19){\tiny{2}} \put(17.06,19){\tiny{3}}
\put(17.06,20){\tiny{4}}

\put(2.06,11.8){\tiny{0}} \put(1.06,13){\tiny{1}}
\put(1.07,14){\tiny{2}} \put(3.06,13){\tiny{3}}
\put(3.06,14){\tiny{4}}

\put(6.06,11.8){\tiny{0}} \put(5.06,13){\tiny{1}}
\put(5.07,14){\tiny{3}} \put(7.06,13){\tiny{2}}
\put(7.06,14){\tiny{4}}

\put(10.06,11.8){\tiny{0}} \put(9.06,13){\tiny{1}}
\put(9.07,14){\tiny{4}} \put(11.06,13){\tiny{2}}
\put(11.06,14){\tiny{3}}

\put(14.06,11.8){\tiny{0}} \put(13.07,13){\tiny{1}}
\put(13.07,14){\tiny{2}} \put(13.06,15){\tiny{3}}
\put(15.06,13){\tiny{4}}

\put(2.06,5.8){\tiny{0}} \put(1.07,7){\tiny{1}} \put(1.07,8){\tiny{2}} \put(1.06,9){\tiny{4}}
\put(3.06,7){\tiny{3}}

\put(6.06,5.8){\tiny{0}} \put(5.07,7){\tiny{1}} \put(5.07,8){\tiny{3}} \put(5.06,9){\tiny{4}}
\put(7.06,7){\tiny{2}}

\put(10.06,5.8){\tiny{0}} \put(9.06,7){\tiny{1}}
\put(11.07,7){\tiny{2}} \put(11.06,8){\tiny{3}}
\put(11.06,9){\tiny{4}}

\put(15.06,5.8){\tiny{0}} \put(14.17,6.9){\tiny{1}}
\put(13.07,8){\tiny{2}} \put(15.06,8){\tiny{3}}
\put(16.06,7){\tiny{4}}

\put(3.06,0.8){\tiny{0}} \put(2.17,1.9){\tiny{1}}
\put(1.07,3){\tiny{2}} \put(3.06,3){\tiny{4}} \put(4.06,2){\tiny{3}}

\put(8.06,0.8){\tiny{0}} \put(7.17,1.9){\tiny{1}}
\put(6.07,3){\tiny{3}} \put(8.06,3){\tiny{4}} \put(9.06,2){\tiny{2}}

\put(12.06,0.8){\tiny{0}} \put(11.1,2){\tiny{1}}
\put(13.07,1.8){\tiny{2}} \put(12.06,3){\tiny{3}}
\put(14.06,3){\tiny{4}}
\end{picture}

$t_4=(1+1+2+1\ +3+3+1+3+1\ )\ =16.$
\end{remark}

\begin{theorem}
\label{seven} Let $b_i$ be the number of labeled 1-2 trees and $y=f(x)=\sum_{i=0}b_i\frac{x^{i+1}}{(i+1)!}\;$be the
exponential generating function. Then$\ f(x)=y=\tan \frac{2x+\pi }4-1=\sec x+
\tan x-1,$ the exponential generating
function of the sequence of {\it zig-zag} permutations.
\end{theorem}


\begin{proof}

Partition the trees by the out degrees of the root. We have the recurrence relation

$b_n=b_{n-1}+\sum_{k=0}^{n-2}\binom{n-1}kb_kb_{n-1-k-1}=b_{n-1}+%
\sum_{k=0}^{n-2}\ \frac{(n-1)!}{k!(n-k-1)!}b_kb_{n-k-2}\;\;\;\;\;\;\;\;\;\;%
\;\;(3)$

Thus $y=f(x)$ satisfies the differential equation

$\frac{dy}{dx}=1+y+\frac{y2}2.$

Note that the second part in (3) is the coefficient $[\frac{x^{n-1}}{(n-1)!}](y%
\frac{dy}{dx}),$\ since we need the coefficient of $[\frac{x^n}{n!}],$ so $%
\int y\frac{dy}{dx}dx=\frac{y^2}2.$\

Solving the above differential equation, yields

$\ f(x)=y=\tan \frac{2x+\pi }4-1=\sec x+\tan x-1$.
\end{proof}

\begin{example}
The counting of the complete binary tree is $1,0,1,0,2,0,5,0,\ldots$ and the
counting of labeled complete binary tree is $1,0,1,0,4,0,34,0,496,\ldots$

Let $b_i$ be the number of labeled complete binary trees and the exponential
generating function

$y=f(x)=\sum_{i=0}b_i\frac{x^{i+1}}{(i+1)!},$ then

$\ \frac{dy}{dx}=1\ +\frac 1{2!}y^2.$

Solve the differential equation

$\ y=\ \sqrt{2}\tan \ \frac x{\sqrt{2}}\ =x+\frac 16x^3+\frac 1{30}x^5+\frac{%
17}{2520}x^7+\frac{31}{22680}x^9+O(x^{11}).$
\end{example}

\begin{example}
The counting of the labeled complete ternary trees is the sequence $%
b_0=1,0,0,1,0,0,15,0,0,855,\ldots $ Its exponential generating function
satisfies the differential equation

$\frac{\ dy}{dx}=1+\frac{y^3}{3!}.$

Solving the differential equation and express $x$ in terms of $y$

$x=\frac 13(\sqrt[3]{6}\ln (y+\sqrt[3]{6})-\frac{\sqrt[3]{6}}2\ln (y^2-\sqrt[%
3]{6}y+(\sqrt[3]{6})^2)+\ \sqrt{3}(\sqrt[3]{6})(\arctan (\frac 2{\sqrt{3}%
\sqrt[3]{6}}y-\frac 1{\sqrt{3}}))+\frac 16\sqrt{3}\sqrt[3]{6}\pi )$

$=y-\frac 1{24}y^4+\frac 1{252}y^7-\frac 1{2160}y^{10}+\frac
1{16848}y^{13}-\frac 1{124416}y^{16}+O(y^{19}).$

Using the Lagrange Inversion Formula, we find

$y=x+\frac 1{4!}x^4+\frac{15}{7!}x^7+\frac{855}{10!}x^{10}+\frac{121605}{13!}%
x^{13}+\ldots $
\end{example}

\begin{example}
We define a Bell tree to be a 1-2 tree with the right branch a single file.
For labeled Bell trees, the counting is the Bell number sequence $%
1,1,2,5,15,52,203,\ldots $

The recurrence relation is $a_n=\sum \binom{n-1}ka_k*(1)$ and its
exponential generating function $y=\sum a_n\frac 1{(n+1)!}x^{n+1}\;$%
satisfies the differential equation

$\frac{dy}{dx}=ye^x.$

Solving the differential equation we have

$y=\ \exp (\exp (x)-1)=1+x+x^2+\frac 56x^3+\frac 58x^4+\frac{13}{30}x^5+%
\frac{203}{720}x^6+\frac{877}{5040}x^7+O\left( x^8\right) .$

$\ $For $n=4,$ there are $16$ labeled 1-2 trees. The only labeled 1-2 tree
 that is not counted as Bell trees is the last one in Remark \ref{six}.
\end{example}

\begin{example}
Trees of height at most two. The recurrence relation is the same as in the
previous example.
\end{example}

\begin{example}
Trees of height at most three. The recurrence relation is

$b_n=\sum \left( _k^{n-1}\right) a_k*b_{n-1-k},$ where $a_k\;$is the
counting of trees of height at most two.

$y^{^{\prime }}=\ yf,$ where $f$ is EGF of $\{a_n\}$ as in the previous
example.

$\ln \;y=\int f=\int \exp (\exp (x)-1),$

$y=\exp (\int (\exp (\exp (x)-1))dx)=1+x+x^2+x^3+\frac{23}{24}x^4+\frac{53}{%
60}x^5+O(x^6).$
\end{example}

\section{Weighted Labeled 1-2 Trees}

There is a bijection between labeled 1-2 trees and Motzkin paths. Here we
use the idea in weighted Motzkin paths by assigning weights to the edges.
For a node of out degree 1 we assign weight $b$ for that single edge and for
a node of out degree 2 we assign weight $1$ for the left edge and weight $c$
for the right edge. The weight of a weighted labeled tree is the product of
the weights of all edges. Let $WT_n(b,c)$ be the set of all labeled and
weighted increasing trees of order $n$ with weights $b,c$ and $w_n$ be the
total weight of all trees in $WT_n(b,c)$, then we have the following.

\setlength{\unitlength}{.7cm}
\begin{picture}(18,5)
\put(1,1){\line(0,1){3}}  % first tree for N=3 row 1

\put(4,1){\line(0,1){1}} \put(3,3){\line(1,-1){1}}
\put(4,2){\line(1,1){1}}

\put(8,1){\line(1,1){1}} \put(7,2){\line(1,-1){1}}
\put(7,2){\line(0,1){1}}

\put(12,1){\line(1,1){1}} \put(11,2){\line(1,-1){1}}
\put(11,2){\line(0,1){1}}

\put(16,1){\line(1,1){1}} \put(15,2){\line(1,-1){1}}
\put(17,2){\line(0,1){1}}



\multiput(1,1)(0,1){4}{\circle{.7}}    % now I will add the vertices/Nodes to the trees

\multiput(4,1)(0,1){2}{\circle{.7}}
\multiput(3,3)(2,0){2}{\circle{.7}}



\put(8,1){\circle{.7}} \multiput(7,2)(2,0){2}{\circle{.7}}
\put(7,3){\circle{.7}}

\put(12,1){\circle{.7}} \multiput(11,2)(2,0){2}{\circle{.7}}
\put(11,3){\circle{.7}}

\put(16,1){\circle{.7}} \multiput(15,2)(2,0){2}{\circle{.7}}
\put(17,3){\circle{.7}}


% Add Nodes
\put(1.06,1){\tiny{0}} \put(1.06,2){\tiny{1}} \put(1.06,3){\tiny{2}} % Numbered vertices Row 1
\put(1.06,4){\tiny{3}} \multiput(.7,1.4)(0,1){3}{\tiny{b}}

\put(4.08,1){\tiny{0}}
\put(4.06,1.8){\tiny{1}}\put(3.08,3){\tiny{2}}
\put(5.06,3){\tiny{3}} \put(3.7,1.4){\tiny{b}}
\put(3.4,2.2){\tiny{1}} \put(4.6,2.2){\tiny{c}}

\put(8.08,.8){\tiny{0}} \put(7.08,2){\tiny{1}}\put(7.06,3){\tiny{2}}
\put(9.06,2){\tiny{3}} \put(7.2,1.2){\tiny{1}}
\put(8.6,1.2){\tiny{c}} \put(6.7,2.4){\tiny{b}}

\put(12.08,0.8){\tiny{0}}
\put(11.08,2){\tiny{1}}\put(11.06,3){\tiny{3}}
\put(13.06,2){\tiny{2}} \put(11.2,1.2){\tiny{1}}
\put(12.6,1.2){\tiny{c}} \put(10.7,2.4){\tiny{b}}


\put(16.08,0.9){\tiny{0}}
\put(15.08,2){\tiny{1}}\put(17.06,2){\tiny{2}}
\put(17.06,3){\tiny{3}} \put(15.2,1.2){\tiny{1}}
\put(16.6,1.2){\tiny{c}} \put(16.7,2.4){\tiny{b}}
\end{picture}

$w_3=1(b^3)+1(bc)+2(bc)+1(bc)=b^3+4bc.$

\setlength{\unitlength}{.7cm}
\begin{picture}(18,22)
\put(1,17){\line(0,1){4}} % first tree for N=4 row 2

\put(4,17){\line(0,1){2}} \put(4,19){\line(-1,1){1}}
\put(4,19){\line(1,1){1}}

\put(8,17){\line(0,1){1}} \put(7,19){\line(1,-1){1}}
\put(7,19){\line(0,1){1}} \put(8,18){\line(1,1){1}}


\put(12,17){\line(0,1){1}} \put(11,19){\line(1,-1){1}}
\put(11,19){\line(0,1){1}} \put(12,18){\line(1,1){1}}


\put(16,17){\line(0,1){1}} \put(16,18){\line(-1,1){1}}
\put(16,18){\line(1,1){1}} \put(17,19){\line(0,1){1}}

\put(2,12){\line(1,1){1}} \put(2,12){\line(-1,1){1}} % Row 2
\put(1,13){\line(0,1){1}} \put(3,13){\line(0,1){1}}

\put(6,12){\line(1,1){1}} \put(6,12){\line(-1,1){1}}
\put(5,13){\line(0,1){1}} \put(7,13){\line(0,1){1}}

\put(10,12){\line(1,1){1}} \put(10,12){\line(-1,1){1}}
\put(9,13){\line(0,1){1}} \put(11,13){\line(0,1){1}}

\put(14,12){\line(-1,1){1}} \put(14,12){\line(1,1){1}}
\put(13,13){\line(0,1){2}}

\put(2,6){\line(-1,1){1}} \put(2,6){\line(1,1){1}}   % Row 3
\put(1,7){\line(0,1){2}}

\put(6,6){\line(-1,1){1}} \put(6,6){\line(1,1){1}}
\put(5,7){\line(0,1){2}}

\put(10,6){\line(-1,1){1}} \put(10,6){\line(1,1){1}}
\put(11,7){\line(0,1){2}}

\put(15,6){\line(1,1){1}} \put(15,6){\line(-1,1){1}}
\put(14,7){\line(-1,1){1}} \put(14,7){\line(1,1){1}}

\put(3,1){\line(1,1){1}} \put(3,1){\line(-1,1){1}} %Row 4
\put(2,2){\line(-1,1){1}} \put(2,2){\line(1,1){1}}

\put(8,1){\line(1,1){1}} \put(8,1){\line(-1,1){1}}
\put(7,2){\line(-1,1){1}} \put(7,2){\line(1,1){1}}

\put(12,1){\line(-1,1){1}} \put(12,1){\line(1,1){1}}
\put(13,2){\line(-1,1){1}} \put(13,2){\line(1,1){1}}

% Add Nodes
\multiput(1,17)(0,1){5}{\circle{.7}} % ADD Nodes - Row 1

\multiput(4,17)(0,1){3}{\circle{.7}}
\multiput(3,20)(2,0){2}{\circle{.7}}

\multiput(8,17)(0,1){2}{\circle{.7}} \put(7,20){\circle{.7}}
\multiput(7,19)(2,0){2}{\circle{.7}}

\multiput(12,17)(0,1){2}{\circle{.7}} \put(11,20){\circle{.7}}
\multiput(11,19)(2,0){2}{\circle{.7}}

\multiput(16,17)(0,1){2}{\circle{.7}}
\multiput(15,19)(2,0){2}{\circle{.7}} \put(17,20){\circle{.7}}

\put(2,12){\circle{.7}} \multiput(1,13)(2,0){2}{\circle{.7}}
\multiput(1,14)(2,0){2}{\circle{.7}}

\put(6,12){\circle{.7}} \multiput(5,13)(2,0){2}{\circle{.7}}
\multiput(5,14)(2,0){2}{\circle{.7}}

\put(10,12){\circle{.7}} \multiput(9,13)(2,0){2}{\circle{.7}}
\multiput(9,14)(2,0){2}{\circle{.7}}

\put(14,12){\circle{.7}} \multiput(13,13)(2,0){2}{\circle{.7}}
\multiput(13,14)(0,1){2}{\circle{.7}}

\put(2,6){\circle{.7}} \multiput(1,7)(2,0){2}{\circle{.7}}
\multiput(1,8)(0,1){2}{\circle{.7}}

\put(6,6){\circle{.7}} \multiput(5,7)(2,0){2}{\circle{.7}}
\multiput(5,8)(0,1){2}{\circle{.7}}

\put(10,6){\circle{.7}} \multiput(9,7)(2,0){2}{\circle{.7}}
\multiput(11,8)(0,1){2}{\circle{.7}}

\put(15,6){\circle{.7}} \multiput(14,7)(2,0){2}{\circle{.7}}
\multiput(13,8)(2,0){2}{\circle{.7}}

\put(3,1){\circle{.7}} \multiput(2,2)(2,0){2}{\circle{.7}}
\multiput(1,3)(2,0){2}{\circle{.7}}

\put(8,1){\circle{.7}} \multiput(7,2)(2,0){2}{\circle{.7}}
\multiput(6,3)(2,0){2}{\circle{.7}}

\put(12,1){\circle{.7}} \multiput(11,2)(2,0){2}{\circle{.7}}
\multiput(12,3)(2,0){2}{\circle{.7}}

% Add numbers to vertices


\put(1.06,17){\tiny{0}} \put(1.06,18){\tiny{1}}  % Numbered vertices for Row 2
\put(1.06,19){\tiny{2}} \put(1.06,20){\tiny{3}}
\put(1.06,21){\tiny{4}}  \multiput(.7,17.4)(0,1){4}{\tiny{b}}


\put(4.06,17){\tiny{0}} \put(4.06,18){\tiny{1}}
\put(4.06,18.8){\tiny{2}} \put(3.06,20){\tiny{3}}
\put(5.06,20){\tiny{4}} \multiput(3.7,17.4)(0,1){2}{\tiny{b}}
 \put(3.4,19.2){\tiny{1}} \put(4.6,19.2){\tiny{c}}


\put(8.06,17){\tiny{0}} \put(8.06,17.8){\tiny{1}}
\put(7.07,19){\tiny{2}} \put(7.06,20){\tiny{3}}
\put(9.06,19){\tiny{4}} \put(7.7,17.4){\tiny{b}}
 \put(7.4,18.2){\tiny{1}} \put(8.6,18.2){\tiny{c}} \put(6.7,19.4){\tiny{b}}

\put(12.06,17){\tiny{0}} \put(12.06,17.8){\tiny{1}} \put(11.07,19){\tiny{2}} \put(11.06,20){\tiny{4}}
\put(13.06,19){\tiny{3}} \put(11.7,17.4){\tiny{b}}
 \put(11.4,18.2){\tiny{1}} \put(12.6,18.2){\tiny{c}} \put(10.7,19.4){\tiny{b}}


\put(16.06,17){\tiny{0}} \put(16.06,17.8){\tiny{1}}
\put(15.07,19){\tiny{2}} \put(17.06,19){\tiny{3}}
\put(17.06,20){\tiny{4}} \put(15.7,17.4){\tiny{b}}
 \put(15.4,18.2){\tiny{1}} \put(16.6,18.2){\tiny{c}} \put(16.7,19.4){\tiny{b}}


\put(2.06,11.8){\tiny{0}} \put(1.06,13){\tiny{1}}
\put(1.07,14){\tiny{2}} \put(3.06,13){\tiny{3}}
\put(3.06,14){\tiny{4}} \put(1.4,12.2){\tiny{1}}
\put(2.6,12.2){\tiny{c}} \put(0.7,13.4){\tiny{b}}
\put(2.7,13.4){\tiny{b}}

\put(6.06,11.8){\tiny{0}} \put(5.06,13){\tiny{1}}
\put(5.07,14){\tiny{3}} \put(7.06,13){\tiny{2}}
\put(7.06,14){\tiny{4}} \put(5.4,12.2){\tiny{1}}
\put(6.6,12.2){\tiny{c}} \put(4.7,13.4){\tiny{b}}
\put(6.7,13.4){\tiny{b}}

\put(10.06,11.8){\tiny{0}} \put(9.06,13){\tiny{1}}
\put(9.07,14){\tiny{4}} \put(11.06,13){\tiny{2}}
\put(11.06,14){\tiny{3}} \put(9.4,12.2){\tiny{1}}
\put(10.6,12.2){\tiny{c}} \put(8.7,13.4){\tiny{b}}
\put(10.7,13.4){\tiny{b}}

\put(14.06,11.8){\tiny{0}} \put(13.07,13){\tiny{1}}
\put(13.07,14){\tiny{2}} \put(13.06,15){\tiny{3}}
\put(15.06,13){\tiny{4}} \put(13.4,12.2){\tiny{1}}
\put(14.6,12.2){\tiny{c}} \multiput(12.7,13.4)(0,1){2}{\tiny{b}}

\put(2.06,5.8){\tiny{0}} \put(1.07,7){\tiny{1}} \put(1.07,8){\tiny{2}} \put(1.06,9){\tiny{4}}
\put(3.06,7){\tiny{3}} \put(1.4,6.2){\tiny{1}} \put(2.6,6.2){\tiny{c}} \multiput(0.7,7.4)(0,1){2}{\tiny{b}}


\put(6.06,5.8){\tiny{0}} \put(5.07,7){\tiny{1}} \put(5.07,8){\tiny{3}} \put(5.06,9){\tiny{4}}
\put(7.06,7){\tiny{2}} \put(5.4,6.2){\tiny{1}} \put(6.6,6.2){\tiny{c}} \multiput(4.7,7.4)(0,1){2}{\tiny{b}}


\put(10.06,5.8){\tiny{0}} \put(9.06,7){\tiny{1}}
\put(11.07,7){\tiny{2}} \put(11.06,8){\tiny{3}}
\put(11.06,9){\tiny{4}} \put(9.4,6.2){\tiny{1}}
\put(10.6,6.2){\tiny{c}} \multiput(10.7,7.4)(0,1){2}{\tiny{b}}

\put(15.06,5.8){\tiny{0}} \put(14.17,6.9){\tiny{1}}
\put(13.07,8){\tiny{2}} \put(15.06,8){\tiny{3}}
\put(16.06,7){\tiny{4}} \put(14.4,6.2){\tiny{1}}
\put(15.6,6.2){\tiny{c}} \put(13.4,7.2){\tiny{1}}
\put(14.6,7.2){\tiny{c}}

\put(3.06,0.8){\tiny{0}} \put(2.17,1.9){\tiny{1}}
\put(1.07,3){\tiny{2}} \put(3.06,3){\tiny{4}} \put(4.06,2){\tiny{3}}
\put(2.4,1.2){\tiny{1}} \put(3.6,1.2){\tiny{c}}
\put(1.4,2.2){\tiny{1}} \put(2.6,2.2){\tiny{c}}

\put(8.06,0.8){\tiny{0}} \put(7.17,1.9){\tiny{1}}
\put(6.07,3){\tiny{3}} \put(8.06,3){\tiny{4}} \put(9.06,2){\tiny{2}}
\put(7.4,1.2){\tiny{1}} \put(8.6,1.2){\tiny{c}}
\put(6.4,2.2){\tiny{1}} \put(7.6,2.2){\tiny{c}}


\put(12.06,0.8){\tiny{0}} \put(11.1,2){\tiny{1}}
\put(13.07,1.8){\tiny{2}} \put(12.06,3){\tiny{3}}
\put(14.06,3){\tiny{4}} \put(11.4,1.2){\tiny{1}}
\put(12.6,1.2){\tiny{c}} \put(12.4,2.2){\tiny{1}}
\put(13.6,2.2){\tiny{c}}

\end{picture}

$w_4=1(b^4)+1(b^2c)+2(b^2c)+1(b^2c)+3(b^2c)+3(b^2c)+1(b^2c)+3(c^2)+1(c^2)$

\ \ \ \ $=b^4+11(b^2c)+4c^2.$

\begin{theorem}
\label{fifteen} Let $y=f(x)=\sum \frac{w_n}{(n+1)!}x^{n+1}\;$be the
exponential generating function of $\{w_n\}.$ Then it satisfies the
following differential equation \\ $y^{^{\prime }}=\frac{dy}{dx}=1+by+\frac
c{2!}y^2=\frac c2(y^2+\frac{2b}cy+\frac 2c)=\frac c2((y+\frac bc)^2+\frac{%
2c-b^2}{c^2}).\;$
 \\The solution is as follows:

Case 1. $2c-b^2\ =0.\;y=\frac{-b}c-\frac{2b}{c(bx-2)}=\frac{-bbx+2b-2b}{%
c(bx-2)}=\frac{b^2x}{c(2-bx)},$

Case 2. $\ 2c-b^2>0.\;y=\frac{-b}c+\frac{\sqrt{2c-b^2}}c\tan (\frac{\sqrt{%
2c-b^2}x}2\ \ +\arctan \frac b{\sqrt{2c-b^2}}),$

Case 3.\ $2c-b^2<0.$ \ $y=\ \frac{(\exp (x\sqrt{b^2-2c})-1)}{r_2-r_1\exp (x\sqrt{b^2-2c})%
}\ ,$ $r_2=\frac{b+\sqrt{b^2-2c}}2,r_1=\frac{b-\sqrt{b^2-2c}}2.$

\end{theorem}

\begin{proof}

 By similar idea in Theorem \ref{seven} we can obtain the differential
equation, then solve the separable differential equation.
\end{proof}

\begin{example}
Labeled 1-2 trees with weights $b=3$, $c=4$, the sequence is $%
1,1,3,13,75,541,\ldots$, (\seqnum{A000670}). The sequence counts the number of ways n competitors can rank
in a competition, allowing for the possibility of ties.

$y^{^{\prime }}=1+3y+\frac 4{2!}y^2,$

$y=\frac{\exp (x)-1}{2-\exp (x)}.$
\end{example}

\begin{example}
Labeled 1-2 trees with weights b=4, c=8, the sequence is $1,4,24,192,\ldots$
\seqnum{A002866}.

$y^{^{\prime }}=1+4y+\frac 8{2!}y^2,$

$y=\frac{16x}{8(2-4x)}=\frac x{1-2x}=\sum 2^nx^{n+1}=\sum \frac{2^n(n+1)!}{%
(n+1)!}x^{n+1}.$
\end{example}

\begin{example}
Labeled 1-2 trees with weights $b=1, c=2$ , the sequence is $%
1,1,3,9,39,189,\ldots$ (\seqnum{A080635}). It counts the number of permutations on $n$ letters without
double falls and without initial falls.

$y^{^{\prime }}=1+y+y^2,$

$\ y=\frac{\sqrt{3}}2\ \tan \frac{\sqrt{3}}2(x+\frac \pi {3\sqrt{3}})-\frac
12=x+\frac 12x^2+\frac 12x^3+\frac 38x^4+\frac{13}{40}x^5+\frac{21}{80}x^6+\
O\left( x^7\right) .$
\end{example}

\begin{example} Labeled 1-2 trees with weights $b=5, c=12$, the sequence is $1,5,37,365,\ldots $, (\seqnum{A050351}). It counts the number of 3-level labeled linear rooted trees with $n$ leaves.

$y^{^{\prime }}=1+5y+6y^2$ .

$y=\frac{\exp (x)-1}{3-2\exp (x)}\ =x+\frac 52x^2+\frac{37}6x^3+\frac{365}{24%
}x^4+\frac{4501}{120}x^5+\frac{13321}{144}x^6+\ O\left( x^7\right) .$
\end{example}

\begin{example}
Labeled 1-2 trees with weights  $b=2, c=4,$\ the sequence is $%
1,2,8,40,256,\ldots$ (\seqnum{A000828}).

$y^{^{\prime }}=1+2y+\frac{4y^2}2,$

$y=\frac{-2}4+\frac 24(\tan (x+\ \frac \pi 4))=x+x^2+\frac 43x^3+\frac 53x^4+%
\frac{32}{15}x^5+\frac{122}{45}x^6+O\left( x^7\right) .$
\end{example}

\begin{thebibliography}{26} \bibitem{BLL}  F. Bergeron, G. Labelle, P. Leroux, \textit{Combinatorial Species and
Tree-like Structures}, Cambridge University Press, 1998.

\bibitem{CS} L. Carlitz and R. Scoville, Some permutation problems, \textit{J. Combin. Theory Ser. A}, (2) \textbf{22} (1977), 129-145.

\bibitem{NS}  N. J. A. Sloane, {\it The On-line Encyclopedia of 
Integer Sequences},
\href{http://www.research.att.com/~njas/sequences}{\tt http://www.research.att.com/\symbol{126}~njas/sequences}.

\bibitem{RS}  R. P. Stanley, \textit{Enumerative Combinatorics}, Vol.\ 1,
Cambridge University Press, 1997.

\bibitem{RS2}  R. P. Stanley, \textit{Enumerative Combinatorics}, Vol.\ 2,
Cambridge University Press, 1999.

\bibitem{HW}  H. S. Wilf, \textit{Generatingfunctionology}, Academic Press,
1994.

\bibitem{Z} J. Zeng, Enum\'eration de permutations et J-fractions continues, \textit{European J. Combin.}, \textbf{14} (1993), 373--382.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15.

\noindent \emph{Keywords: } labeled tree, Motzkin path, Catalan path,
weighted labeled tree, exponential generating function.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000670},
\seqnum{A000828},
\seqnum{A002866},
\seqnum{A050351}, and
\seqnum{A080635}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 14 2007;
revised version received  August 7 2007.
Published in {\it Journal of Integer Sequences}, August 13 2007.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

