\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://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf
On Sequences $G_n$ Satisfying \\
\vskip .1in
$G_n=(d+2)G_{n-1}-G_{n-2}$
}
\vskip 1cm
\large
Ricky X. F. Chen\\
Center for Combinatorics\\
LPMC\\
Nankai University\\
Tianjin, 300071\\
P. R. China\\
\href{mailto:ricky\_chen@mail.nankai.edu.cn}{\tt ricky\_chen@mail.nankai.edu.cn}\\
\ \\
Louis W. Shapiro\footnote{The second author is partially
supported by NSF grant HRD 0401697.}\\
Howard University\\
Washington, DC 20059\\
USA\\
\href{mailto:lshapiro@Howard.edu}{\tt lshapiro@Howard.edu}\\
\end{center}
\vskip .2 in
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\begin{abstract}
In this note, we study a class of sequences $G_n$ satisfying $%
G_n=(d+2)G_{n-1}-G_{n-2}$. Note that the Fibonacci numbers $
G_{n}=F_{2n},n>1$ and $G_{n}=F_{2n+1},n>0$ occur when $d=1$ with
suitable initial conditions. We present a general interpretation for
this class of sequences in terms of ordered trees which we count by
nodes and outdegrees. Further more, several other related integer
sequences are also studied.
\end{abstract}
\section{Introduction}
In this note, we study a class of sequences $G_{n}$ satisfying $
G_{n}=(d+2)G_{n-1}-G_{n-2}$. Note that the Fibonacci numbers $
G_{n}=F_{2n},n>1$ and $G_{n}=F_{2n+1},n>0$ occur when $d=1$ with
suitable initial conditions. We present a general interpretation for
this class of sequences in terms of ordered trees which we count by
nodes and outdegrees.
A \emph{node} is a non-root vertex which is
not a leaf. A \emph{skinny tree} is an ordered tree which has at
most one node on each level, where the level of a vertex is the
number of edges between it and the root. If we also mark a vertex at
the bottom level, the skinny tree will be called \emph{augmented},
and the special vertex will be called a \emph{marked leaf}. This is
a model of a process where at each stage exactly one choice is made.
This could be choosing a college, a spouse, a job, and so on or just
taking a multiple choice test. This problem gives rise to new
interpretations for many integer sequences in Sloane's Encyclopedia
\cite{3}, such as sequences \seqnum{A030267}, \seqnum{A038731}, and
\seqnum{A000045} (the
Fibonacci numbers). We would like to propose this tree
representation even though these integer sequences have been
interpreted by other combinatorial structures. We will also present
some bijections between skinny trees and these other combinatorial
structures.
This paper is organized as follows. In Section 2, we consider the sequences $%
G_{n}$ with $G_{0}=1,G_{1}=1$. We will show that these sequences count the
number of skinny trees in which the outdegree of each vertex is multiple of $%
d$ for all $d\geq 1$. We then study the sequences $G_{n}$ when $d=1$ and $2$
in greater detail. In Section 3, we consider the sequences $G_{n}$ with $%
G_{0}=1,G_{1}=d$. Most of results in this section are in parallel with those
in section 2. In the last section, we consider the average height of skinny
trees, and other asymptotic results.
\section{Sequences with $G_0=1, G_1=1$}
In this section, we first count the number of skinny trees in which
the outdegree of each vertex is multiple of $d$ for all $d\geq 1$.
We will show in a combinatorial way that the sequences $G_{n}$ with
$G_{0}=1,G_{1}=1$ actually count this kind of skinny trees. Next, we
will study some properties of the sequences $G_{n}$ when $d=1$ and
$2$.
For the sake of convenience, we will abbreviate skinny tree to $ST$ and
augmented skinny tree to $AST$. The set of all skinny trees (augmented
skinny trees, resp.) will be denoted as $\mathbb{ST}$ ($\mathbb{AST}$,
resp.). A skinny tree (augmented skinny tree, resp.) of height one will be
called a small $ST$ (small $AST$, resp.). The Fibonacci sequence $F_n$ used
here satisfies
\begin{equation*}
\frac{z}{1-z-z^{2}}=F_{0}+F_{1}z+F_{2}z^{2}+\cdots
=z+z^{2}+2z^{3}+3z^{4}+5z^{5}+\cdots .
\end{equation*}%
We also use the fact that
\begin{equation*}
\frac{z}{1-3z+z^{2}}=\sum_{n\geq 0}F_{2n+2}z^{n+1}.
\end{equation*}
\begin{theorem}
\label{2t1} The generating function for the number of skinny trees
in which the outdegree of each vertex is multiple of $d$ is denoted
by $S_{d}\left( z\right) $ and satisfies the equation
\begin{equation*}
S_{d}(z)=\sum_{T\in \mathbb{ST}}z^{\#\mbox{edges of
$T$}}=\frac{1-(d+1)z^{d}}{1-(d+2)z^{d}+z^{2d}}.
\end{equation*}
\end{theorem}
\begin{proof}
%{\bf proof. }
Consider the outdegree of the root. If the root has no children, then
its contribution is 1; If the root has outdegree $k\geq d$ and $d|k$
but no grandchildren, its contribution to the generating function is
$z^k$, otherwise its contribution is $kz^k(S_d(z)-1)$. Hence
\[
S_d(z)=1+\sum_{k\geq d,d|k}z^k+\sum_{k\geq d,d|k}kz^{k}(S_d(z)-1).
\]
Solving for $S_d(z)$ we obtain
\[
S_d(z)=\frac{1-(d+1)z^{d}}{1-(d+2)z^{d}+z^{2d}}.
\]
\end{proof}Let
\begin{equation*}
S_d(z)=\frac{1-(d+1)z^{d}}{1-(d+2)z^{d}+z^{2d}}=\sum_{n\geq
0}S_{d,n}z^{nd}.
%\quad
%\frac{1}{1-(d+2)z^{d}+z^{2d}}=\sum_{n\geq 0}s_{d,n}z^{nd}.
\end{equation*}%
From the theory of rational generating functions \cite{2}, we can
obtain the following theorem. However, we will give a combinatorial
proof.
\begin{theorem}
\label{2t2} The sequences $S_{d,n}$ satisfy
$S_{d,n}=(d+2)S_{d,n-1}-S_{d,n-2} $ and $S_{d,0}=1,S_{d,1}=1$.
\end{theorem}
\begin{proof}
We count the number of skinny trees in which the outdegree of each
vertex is multiple of $d\geq 1$ (denoted by $STd$) with $dn$ edges.
First note that there are just $dS_{d,n-1}$ $STd$'s with $dn$ edges
when the degree of the root is $d$.
\par
For the $STd$'s with $dn$ edges
where the degree of the root is larger than $d$, we can construct
these trees by adding $d$ leaves to the root of $STd$'s with $dn-d$
edges. These $d$ leaves can be added to the root on the left or the
right of the existing tree. We get a total number of $2S_{d,n-1}$
trees this way but we have over counted a bit. The trees that are
counted twice are those which could have resulted from either type
of addition of edges and there are $S_{d,n-2}$ such trees.
Hence the exact number of $STd$'s with $dn$ edges is
$(d+2)S_{d,n-1}-S_{d,n-2}$. So,
\[
S_{d,n}=(d+2)S_{d,n-1}-S_{d,n-2}, \mbox{ for $n\geq 2$}.
\]
The initial conditions $S_{d,0}=1,S_{d,1}=1$ are obvious. This
completes the proof.
\end{proof}Note Theorem \ref{2t2} implies $G_{n}=S_{d,n}$ for $G_{n}$
satisfying $G_{0}=1,G_{1}=1$. From Theorem \ref{2t1}, we obtain the
following corollary.
\begin{corollary}
\label{2c1} The number of $ST$'s with $n$ edges is $F_{2n-1}$ for
$n\geq 1$.
\end{corollary}
\begin{proof}
Taking $d=1$, we have
$$
\sum_{n\geq
0}S_{1,n}z^{n}=\frac{1-2z}{1-3z+z^2}=1+\frac{z-z^2}{1-3z+z^2}.
$$
For $n\geq 1$, the coefficient of $z^{n}$ is $
F_{2n}-F_{2n-2}=F_{2n-1} $. This completes the proof.
\end{proof}
\begin{proposition}
\label{2p1} The number of $ST$'s with $n+1$ edges and $k$ $(k\geq 0)$ nodes
is ${\binom{n+k}{{2k}}}$.
\end{proposition}
\begin{proof}
%{\bf proof. }
We can build any $ST$ with $k$ nodes and $n+1$ edges as follows. Start with
a path with $k+1$ edges. We then have $n+1 -(k+1)=n-k$ edges left to
distribute. At each level other than the bottom, the remaining edges
go either to the left or the right of the path. At the bottom level,
we just attach the edges. This is equivalent to putting $n-k$ balls
into $2k+1$ boxes with repetition allowed, thus we have
\[
{(2k+1)+(n-k)-1\choose n-k}={n+k\choose {2k}}
\]
possibilities.
\end{proof}
Summing over $0\leq k\leq {n}$, we can get the total number of $ST$'s with $%
n+1$ edges, which leads to the following famous Fibonacci identity
\cite{1}.
\begin{corollary}
\label{2c2}
\begin{align*}
F_{2n+1}=\sum_{k=0}^n{\binom{n+k}{{2k}}},\mbox{ for $n\geq 0$}.
\end{align*}
\end{corollary}
More generally, we have the following proposition.
\begin{proposition}
\label{2p2}The sequences $S_{d,n}$ satisfy
\begin{equation*}
S_{d,n+1}=\sum_{k=0}^{n}{\binom{n+k}{2k}}d^{k}.
\end{equation*}
\end{proposition}
\begin{proof}
We can construct a $STd$ with $dn+d$ edges from a $ST$ with $n+1$
edges by subdividing each vertex (except the root) into $d$
vertices. If the vertex is a node, it will be subdivided into a new
node and $d-1$ leaves; Otherwise, $d$ leaves. But note that if the
$ST$ has $k$ nodes for each subdivided node one of the newly created
vertices becomes the new node while the rest become leaves. If the
tree has height $k$ this gives ${n+k\choose {2k}}d^k$ possibilities.
Summing over $0\leq k\leq n$, we will obtain the total number of
$STd$'s with $dn+d$ edges. Hence
\[
S_{d,n+1}=\sum_{k=0}^n{n+k\choose {2k}}d^k.
\]
\end{proof}
The Fibonacci sequences $\left( F_{2n}\right) _{n\geq 1}$ and
$\left( F_{2n+1}\right) _{n\geq 0}$ have many combinatorial
interpretations. For instance in van Lint and Wilson's book
\cite{4}, they propose a problem counting the lattice paths on
$X$-$Y$ plane from the origin $(0,0)$ to the line $x+y=n$ $(n\geq
0)$ using as possible steps $(1,0)$ (horizontal step) and $(0,p)$
(vertical step), where $p$ can be any positive integer. It is known
that $F_{2n+1}$ is the number of possible such paths. We show this
via a bijection with $\mathbb{ST}$ in Theorem \ref{2t3}. Figure 1.
presents an example to illustrate the bijection.
\begin{theorem}
\label{2t3} There is a bijection between $ST$'s with $n+1$ edges and lattice
paths ending on $x+y=n$ using steps $(1,0)$ and $(0,p)$, where $p$ can be
any positive integer.
\end{theorem}
\begin{proof}
%{\bf proof.}
Given a $ST$ with $n+1$ edges, we construct a lattice path from
$(0,0)$ as follows. Read the edges level by level starting at the
top level just below the root. If there are $h$ edges to the left of
the node on the present level, these $h$ edges correspond to $h$
consecutive horizontal steps; The remaining $v$ edges on the level
correspond to a vertical step $(0,v)$. At the bottom level there are
just $m$ edges and no node, these correspond to $m-1$ consecutive
horizontal steps.
To recover the $ST$ from a lattice path, we read the lattice path
from $(0,0)$ step by step until the last vertical step and start a
new level of $ST$ right after each vertical step. If there are $h$
consecutive horizontal steps between the present vertical step and
the next vertical step $(0,v)$, then the new starting level consists
of $h+v$ edges and the $(h+1)$-th edge is the edge leading to the
node of the new level. Finally, suppose there are $m-1$ horizontal
steps after the last vertical step, then the bottom level of the
$ST$ has $m$ edges. In this way, we eventually obtain a $ST$ with
$n+1$ edges.
%\begin{figure}[ht]
%\hspace{30pt} \epsfxsize=4in \epsffile{lattice.eps} \vspace{-1pt}
%\caption{Example}
%\end{figure}
\end{proof}\setlength{\unitlength}{1mm}
\begin{center}
\begin{picture}(100,45)
\put(10,40){\circle*{1.10}}
\put(10,40){\line(-1,-1){10}}\put(10,40){\line(0,-1){10}}\put(10,40){\line(1,-1){10}}
\multiput(0,30)(10,0){3}{\circle*{1.5}} %%%%%%%%%%% first layer
\put(20,30){\line(-1,-1){10}}\put(20,30){\line(0,-1){10}}\put(20,30){\line(1,-1){10}}
\multiput(10,20)(10,0){3}{\circle*{1.5}}%%%%%%%%%%%%%%%% second layer
\put(10,20){\line(-1,-1){10}}\put(10,20){\line(1,-1){10}}
\multiput(0,10)(20,0){2}{\circle*{1.5}} %%%%%%%%%%%%%%%% third layer
\put(20,10){\line(0,-1){10}}
\multiput(20,0)(10,0){1}{\circle*{1.5}}%%%%%%%%% end of ST
\put(50,0){\vector(1,0){45}}\put(50,0){\vector(0,1){45}}
\put(97,0){x}\put(48,45){y}%%%%%%%%%
\put(50,40){\line(1,-1){40}}%%%%%%%
{\linethickness{0.01mm} \multiput(50,5)(2,0){18}{\line(1,0){1}}
\multiput(50,10)(2,0){15}{\line(1,0){1}}
\multiput(50,15)(2,0){13}{\line(1,0){1}}
\multiput(50,20)(2,0){10}{\line(1,0){1}}
\multiput(50,25)(2,0){8}{\line(1,0){1}}
\multiput(50,30)(2,0){5}{\line(1,0){1}}
\multiput(50,35)(2,0){3}{\line(1,0){1}}
\multiput(50,40)(2,0){0}{\line(1,0){1}}%%%%%%%%%%% horizontal line
\multiput(55,0)(0,2){18}{\line(0,1){1}}
\multiput(60,0)(0,2){15}{\line(0,1){1}}
\multiput(65,0)(0,2){12}{\line(0,1){1}}
\multiput(70,0)(0,2){10}{\line(0,1){1}}
\multiput(75,0)(0,2){8}{\line(0,1){1}}
\multiput(80,0)(0,2){5}{\line(0,1){1}}
\multiput(85,0)(0,2){3}{\line(0,1){1}}
\multiput(90,0)(0,2){0}{\line(0,1){1}} \put(72,20){x+y=8}}
%%%%%%%%%%%%%% lattice line
\put(50,0){\circle*{1.5}} \put(55,0){\circle*{1.5}}
\put(60,0){\circle*{1.5}}\put(60,5){\circle*{1.5}}
\put(60,20){\circle*{1.5}}\put(65,20){\circle*{1.5}}
\put(65,25){\circle*{1.5}} %%%%%%%%%%
{ \linethickness{0.4mm}
\put(50,0){\line(1,0){5}}\put(55,0){\line(1,0){5}}
\put(60,0){\line(0,1){5}}
\put(60,5){\line(0,1){15}}\put(60,20){\line(1,0){5}}\put(65,20){\line(0,1){5}}}
\end{picture}
\end{center}
\begin{center}
Figure 1. A $ST$ with $9$ edges and its corresponding lattice path.
\end{center}
When $d=2$, the first few terms of $S_{2}(z)=\sum_{n\geq 0}S_{2,n}z^{2n}$ are
\begin{equation*}
S_{2}(z)=1+z^{2}+3z^{4}+11z^{6}+41z^{8}+153z^{10}+571z^{12}+\cdots.
\end{equation*}%
There are many interesting properties of this $S_{2,n}$ sequence (see \cite[%
p.292]{4} and \\seqnum{A001835}). For instance, $S_{2,n}$ is the number of
ways of packing a $3\times 2(n-1)$ rectangle with dominoes (by David
Singmaster \seqnum{A001835}); Or equivalently the number of perfect
matchings of the $P_{3}\times P_{2(n-1)}$ lattice graph (by Emeric Deutsch
\seqnum{A001835}); also $S_{2,n}(n)=S(n-1,4)-S(n-2,4)$ where the $%
S(n,x)=U(n,x/2)$ and the $U(n,x)$ are the Chebyshev polynomials of the
second kind (see \seqnum{A001835}), etc.
Here we present a bijection between $ST2$'s with $2n$ edges and tilings of a
$3\times 2(n-1)$ board with dominoes, horizontal dominoes and vertical
dominoes (for an illustration see Figure 2.). To start, some obvious
properties about the tilings of a $3\times 2(n-1)$ board with dominoes are
mentioned here.
\begin{proposition}
\label{2p3} There are an even number of vertical dominoes in every tiling.
From left to right where the vertical dominoes are partitioned into
consecutive pairs, the vertical dominoes in a pair are parallel and
justified. And the distance between any two consecutive vertical dominoes is
even.
\end{proposition}
\begin{theorem}
\label{2t4} There is a bijection between $ST2$'s with $2n$ edges and tilings
of a $3\times 2(n-1)$ board with dominoes.
\end{theorem}
\begin{proof}
%{\bf proof. }
We will use a standard numbering where the leftmost
bottom square is labelled $(1,1)$ and the rightmost top square is
labelled $(2n,3)$. The whole $3\times 2n$ board will be denoted by
$<(1,1),(2n,3)>$.
%\par
%\begin{figure}[ht]
%\hspace{30pt} \epsfxsize=4in \epsffile{ti1.eps} \vspace{-1pt}
%\caption{Example}
%\end{figure}
Given a $ST2$, suppose that level $1$ has $2l$ edges. Number the
vertices from $1$ to $2l$ going from left to right. If the node is
vertex $2p-1$, we tile squares $(2p-1,1)$ and $(2p-1,2)$ with a red
vertical domino and tile the squares $(2l,1)$ and $(2l,2)$ with a
green vertical domino. Dually if the node is vertex $2p$, we tile
the squares $(2p-1,2)$ and $(2p-1,3)$ with a red vertical domino and
tile squares $(2l,2)$ and $(2l,3)$ with a green vertical domino.
(These rules are guided by Proposition \ref{2p3}.) In other words,
if the node number is odd, we put in the pair of vertical dominoes
on the bottom. If the node number is even, we put in the pair of
vertical dominoes towards the top. We then tile the remainder of the
$<(1,1),(2l,3)>$-board completely with horizontal dominoes. In the
same manner, each level (except the bottom level) of the $ST2$
corresponds to a closed subboard. At the bottom level, tile the
remaining subboard of the $<(1,1),(2(n-1),3)>$-board completely with
horizontal dominoes. If there is but one pair of vertices on the
bottom level, then we add nothing. In each case we obtain a tiling
of the $3\times 2(n-1)$ board.
To recover the $ST2$ from a given tiling, we first color the
vertical dominoes alternately with red and green colors. From
Proposition \ref{2p3}, the last vertical domino must be a green one.
Suppose that the subboard ended with the first green vertical domino
yields a $<(1,1),(2l,3)>$-board. If the red vertical domino in this
subboard covers squares $(2p-1,1)$ and $(2p-1,2)$, then level $1$ of
the $ST2$ has $2l$ edges so that the node is the vertex $2p-1$. If
the red vertical domino in this subboard covers squares $(2p-1,2)$
and $(2p-1,3)$, then the node is the vertex $2p$. Treat other levels
in the same way. If the right hand end of the board consists of $m$
columns of horizontal dominoes, then the bottom level of the $ST2$
has $2(m+1)$ vertices. This gives us the corresponding $ST2$.
\end{proof}
\begin{center}
\setlength{\unitlength}{1mm}
\begin{picture}(100,30)
\put(10,30){\circle*{1.5}}\put(10,30){\line(-1,-1){10}}
\put(10,30){\line(-2,-5){4}}\put(10,30){\line(2,-5){4}}\put(10,30){\line(1,-1){10}}
\put(0,20){\circle*{1.5}}\put(6,20){\circle*{1.5}}\put(14,20){\circle*{1.5}}
\put(20,20){\circle*{1.5}}%%%%%%%%%% first layer
\put(14,20){\line(-1,-1){10}}
\put(14,20){\line(-2,-5){4}}\put(14,20){\line(2,-5){4}}\put(14,20){\line(1,-1){10}}
\put(4,10){\circle*{1.5}}\put(10,10){\circle*{1.5}}\put(18,10){\circle*{1.5}}
\put(24,10){\circle*{1.5}}%%%%%%%%%%% second layer
\put(10,10){\line(-1,-1){10}}
\put(10,10){\line(-2,-5){4}}\put(10,10){\line(2,-5){4}}\put(10,10){\line(1,-1){10}}
\put(0,0){\circle*{1.5}}\put(6,0){\circle*{1.5}}\put(14,0){\circle*{1.5}}
\put(20,0){\circle*{1.5}} %%%%%%%%%%%%%%%% end of tree
%\multiput(30,20)(0,-2){2}{\line(1,0){10}}\put(41,19){\line(-1,1){3.6}}\put(41,19){\line(-1,-1){3.6}}
%\put(29,19){\line(1,1){3.6}}\put(29,19){\line(1,-1){3.5}}
\linethickness{0.4mm}
\put(50,30){\line(1,0){50}}{\put(50,25){\line(1,0){20}}\put(75,25){\line(1,0){10}}\put(90,25){\line(1,0){10}}}
{\put(50,20){\line(1,0){10}}\put(70,20){\line(1,0){30}}}\put(50,15){\line(1,0){50}} %%%%%%%%%
\multiput(50,30)(10,0){3}{\line(0,-1){15}}\put(75,30){\line(0,-1){10}}
\put(85,30){\line(0,-1){10}}\put(90,30){\line(0,-1){10}}\put(100,30){\line(0,-1){15}}
\put(65,25){\line(0,-1){10}}%%%%%%%%
\multiput(80,20)(10,0){2}{\line(0,-1){5}}%%%%%%%%%%
\thinlines
\multiput(50,30)(0,-1){15}{\line(1,0){10}}\multiput(60,30)(0,-1){5}{\line(1,0){10}}
%%%%%%%%%%%%%%55
\multiput(66,25)(0,-1.5){7}{\line(0,-1){1}}
\multiput(67,25)(0,-1.5){7}{\line(0,-1){1}}
\multiput(68,25)(0,-1.5){7}{\line(0,-1){1}}
\multiput(69,25)(0,-1.5){7}{\line(0,-1){1}} %%%%%%%%%%%
\multiput(86,30)(0,-1.5){7}{\line(0,-1){1}}
\multiput(87,30)(0,-1.5){7}{\line(0,-1){1}}
\multiput(88,30)(0,-1.5){7}{\line(0,-1){1}}
\multiput(89,30)(0,-1.5){7}{\line(0,-1){1}}%%%%%%%%%
\multiput(75,30)(0,-1){10}{\line(1,0){10}}
\multiput(90,30)(0,-1){15}{\line(1,0){10}}
\multiput(70,20)(0,-1){5}{\line(1,0){20}} %%%%%%%%%%%%%%5
{\linethickness{0.4mm} \put(50,10){\line(1,0){10}}
\put(50,5){\line(1,0){10}}
\put(50,10){\line(0,-1){5}}\put(60,10){\line(0,-1){5}} \thinlines
\multiput(50,10)(0,-1){5}{\line(1,0){10}}
\put(43,0){horizontal}\put(43,-5){ domino}} %%%%%%%%%%
{ \linethickness{0.4mm}
\put(75,13){\line(0,-1){10}}\put(80,13){\line(0,-1){10}}
\put(75,13){\line(1,0){5}} \put(75,3){\line(1,0){5}} \put(65,-1){red
vertical}\put(68,-5){domino}
} %%%%%%%%%%%%%%%%
{ \linethickness{0.4mm}
\put(95,13){\line(0,-1){10}}\put(100,13){\line(0,-1){10}}
\put(95,13){\line(1,0){5}} \put(95,3){\line(1,0){5}} \thinlines
\multiput(96,13)(0,-1.5){7}{\line(0,-1){1}}
\multiput(97,13)(0,-1.5){7}{\line(0,-1){1}}
\multiput(98,13)(0,-1.5){7}{\line(0,-1){1}}
\multiput(99,13)(0,-1.5){7}{\line(0,-1){1}}%%%%%%%%%
\put(87,-1){green vertical}\put(90,-5){domino}}
\end{picture}
\end{center}
\vskip 0.6cm
\begin{center}
Figure 2. An example
\end{center}
Figure 2. shows an example of a $ST2$ with $2\times 6$ edges and its
corresponding tiling of a $3\times 2\cdot(6-1)$ board. %\begin{theorem}
\section{Sequences with $G_0=1, G_1=d$}
In this section, we present parallel results for augmented skinny trees.
Since almost all of the results have same reasoning as the corresponding one
in Section 2, we will only give brief proofs or just comments. Recall that $%
AST$ denotes augmented skinny tree.
\begin{theorem}
\label{3t1} The generating function for the number of augmented
skinny trees in which the outdegree of each vertex is multiple of
$d$ is denoted by $A_d(z)$ and satisfies the equation
\begin{equation*}
A_d(z)=\sum_{T\in \mathbb{AST}} z^{\#\mbox{edges of
$T$}}=\frac{(1-z^d)^2}{1-(d+2)z^{d}+z^{2d}}.
\end{equation*}
\end{theorem}
\begin{proof}
%{\bf proof. }
We proceed as in the proof of Theorem \ref{2t1} and consider the
outdegree of the root. We find that
\[
A_d(z)=1+\sum_{k\geq d,d|k}kz^{k}A_d(z)
=1+A_d(z)\frac{dz^d}{(1-z^d)^2}.
\]
Solving for $A_d(z)$ will complete the proof.
\end{proof}Let
\begin{equation*}
A_{d}\left( z\right) =\frac{(1-z^{d})^{2}}{1-(d+2)z^{d}+z^{2d}}=\sum_{n\geq
0}A_{d,n}z^{nd}.
\end{equation*}%
With the same kind of argument as in the constructive proof of Theorem \ref%
{2t2}, we obtain
\begin{theorem}
\label{3t2} The sequences $A_{d,n}$ satisfy
$A_{d,n}=(d+2)A_{d,n-1}-A_{d,n-2} $ and $A_{d,0}=1,A_{d,1}=d$.
\end{theorem}
Taking $d=1$, we obtain
\begin{corollary}
\label{3c1} The number of $AST$'s with $n$ edges is $F_{2n}$ for $n\geq 1$.
\end{corollary}
Stanley has presented a result similar to Corollary \ref{3c1} which
is attributed to Gessel (see \cite[p.46]{2}). With the same
technique as in the proof of Proposition \ref{2p1}, we obtain
\begin{proposition}
\label{3p1} The number of $AST$'s with $n$ edges and $k$ $(k\geq 0)$ nodes
is ${\binom{n+k}{2k+1}}$.\newline
\end{proposition}
Summing over $0\leq k\leq n-1$, we get the total number of $AST$'s
with $n$ edges. This leads to the following corollary \cite{1}.
\begin{corollary}
\label{3c2}
\begin{equation*}
F_{2n}=\sum_{k=0}^{n-1}{\binom{n+k}{{2k+1}}},\mbox{ for $n\geq 1$}.
\end{equation*}
\end{corollary}
By similar argument as the proof of Proposition \ref{2p2}, now noting that
the augmented leaf will be subdivided into $d-1$ leaves and a new augmented
leaf, we obtain the following proposition.
\begin{proposition}
The sequences $A_{d,n}$ satisfy \label{3p2}
\begin{equation*}
A_{d,n}=\sum_{k=0}^{n-1}{\binom{n+k}{2k+1}}d^{k+1}.
\end{equation*}
\end{proposition}
When $d=2$, the first few terms of $A_2(z)$ are
\begin{equation*}
A_{2}(z)=\sum_{n\geq
0}A_{2,n}z^{2n}=1+2z^{2}+8z^{4}+30z^{6}+112z^{8}+418z^{10}+\cdots .
\end{equation*}%
These integers $A_{2,n}$ are those integer solutions of the Diophantine
equation $3\ast n^{2}+4$ which are perfect squares (see \seqnum{A052530}).
This reduces to a Pells equation $m^{2}-3n^{2}=1$ and to computing $A_{n}$
via the relation $2(2+\sqrt{3})^{n}=A_{n}+A_{2,n}$. The sequence $S_{2,n}$
of $ST2$'s is essentially the sequence $A_{n}-A_{2,n}$.
In the same way, we can obtain the generating functions for (augmented)
skinny trees in which each node and the root have odd outdegree.
\begin{theorem}
\label{3t3} The generating function for the number of $ST$'s where
each node and the root have odd outdegree is (see \seqnum{A105309})
\begin{equation*}
\frac{z-z^3}{z^4-z^3-2z^2-z+1}=z+z^2+2z^3+5z^4+9z^5+20z^6+\cdots,
\end{equation*}
while the generating function for the number of $AST$'s where each
node and the root have odd outdegree is (see \seqnum{A119749})
\begin{equation*}
\frac{z+z^3}{z^4-z^3-2z^2-z+1}=z+z^2+4z^3+7z^4+15z^5+32z^6+\cdots.
\end{equation*}
\end{theorem}
\section{Average height of skinny trees}
Another question we can ask is what is the average height of $AST$'s with n
edges (The result for $ST$'s is similar). Let
\begin{equation*}
H(z)=\sum_{\#\mbox{edges of $T$=$n$}}H_{n}z^{n}
\end{equation*}%
denote the total height generating function where $H_{n}$ is the sum of all
heights over all $AST$'s with $n$ edges.
\begin{proposition}
\label{4p1} The generating function for the total height of $AST$'s is (see
\seqnum{A030267})
\begin{equation*}
H(z)=\frac{z(1-z)^2}{(1-3z+z^2)^2}=z+4z^2+14z^3+46z^4+145z^5+444z^6+\cdots.
\end{equation*}
\end{proposition}
\begin{proof}
%{\bf proof.}
First we observe that the generating function for total height of
$AST$'s of height $k$ is
\[
k\left(\frac{z}{(1-z)^2}\right)^k,
\]
since these trees can be decomposed into $k$ small $AST$'s. Set
$y=\frac{z}{(1-z)^2}$. Summing over $k\geq 1$, we obtain $H(z)$,
\[
H(z)=\sum_{k\geq 1}ky^k=y\frac{\textrm{d}}{\textrm{dy}}\left(
\frac{y}{1-y}\right)=\frac{y}{(1-y)^2}.
\]
So
\[
H(z)=\frac{z(1-z)^2}{(1-3z+z^2)^2}.
\]
\end{proof}
\begin{theorem}
\label{4t1}
The average height of $AST$'s with $n$ edges approaches $\frac{n}{\sqrt{5}}$.
\end{theorem}
\begin{proof}
%{\bf proof. }
From Proposition \ref{4p1}, we obtain that the total height of
$AST$'s with $n$ edges is
\[
H_n=\frac{2nF_{2n+1}+(2-n)F_{2n}}{5}.
\]
Since the average height is $\frac{H_n}{F_{2n}}$ and
$\frac{F_{2n+1}}{F_{2n}}\sim \frac{1+\sqrt{5}}{2}$, we have
\[
\frac{H_n}{F_{2n}}\sim \frac{2n}{5}\cdot
\frac{1+\sqrt{5}}{2}+\frac{2-n}{5}\sim \frac{n}{\sqrt{5}}.
\]
It follows that the average height approaches $\frac{n}{%
\sqrt{5}}$.
\end{proof}For $ST$'s, we find that the generating function for
the total height is
\begin{equation*}
h\left( z\right) =\sum_{n=0}^{\infty }h_{n}z^{n}=\frac{z\left( 1-z\right)
^{3}}{\left( 1-3z+z^{2}\right) ^{2}}%
=z+3z^{2}+10z^{3}+32z^{4}+99z^{5}+299z^{6}+\cdots .
\end{equation*}%
We have $h_{n}=H_{n}-H_{n-1}$ and $h_{n}=\sum_{k=1}^{n}k{\binom{n+k-2}{2k-2}}
$ (see \seqnum{A038731}). So the average height for $ST$'s approaches the
same limit,
\begin{equation*}
\frac{h_{n}}{F_{2n-1}}=\frac{(n+4)F_{2n-1}+(2n-1)F_{2n-2}}{5F_{2n-1}}\sim
\frac{n}{\sqrt{5}}.
\end{equation*}%
{\noindent \textbf{Remarks.}} Actually, the sequences $G_n$ with
other different initial conditions also have analogous
interpretation. For instance, the sequences $G_n$ with
$G_0=1,G_1=d+2$ count augmented skinny trees $STd$'s except that we
number the bottom row from 1 to $kd$ and the marked leaf must have a
number congruent to 1 modulo d.
%And it would be also interesting to
%interpret the average height of $AST$ in a more combinatorial way.
\section{Acknowledgements}
We would like to thank the referee for his detailed comments which helped to
improve the presentation of this paper. This work was supported by the 973
Project, the PCSIRT Project of the Ministry of Education, the Ministry of
Science and Technology and the National Science Foundation of China.
\begin{thebibliography}{9}
\bibitem{1} Arthur T. Benjamin, Jennifer Quinn, {\it Proofs that Really Count:
The Art of Combinatorial Proof}, Mathematical Association of America,
2003.
\bibitem{2} R. P. Stanley, {\it Enumerative Combinatorics I}, Cambridge Univ.
Press, Cambridge, 1997.
\bibitem{3} N. J. A. Sloane, \href{http://www.research.att.com/~njas/sequences/%
}{The On-Line Encyclopedia of Integer Sequences}, published electronically
at \href{http://www.research.att.com/~njas/sequences/}{%
http://www.research.att.com/$\sim$njas/sequences/}.
\bibitem{4} J. H. van Lint and R. M. Wilson,
{\it A Course in Combinatorics}, 2nd
edition, Cambridge University Press, 2001.
\end{thebibliography}
\bigskip \hrule
\bigskip
\noindent 2000 \textit{Mathematics Subject Classification}: Primary
05C05; Secondary 11B39, 05A15.
\noindent \emph{Keywords:} skinny trees, outdegree, tilings,
Fibonacci numbers, lattice paths.
\bigskip \hrule
\bigskip
\noindent (Concerned with sequences \seqnum{A000045},
\seqnum{A001835},
\seqnum{A030267},
\seqnum{A038731},
\seqnum{A052530},
\seqnum{A105309}, and
\seqnum{A119749}.)
\bigskip \hrule
\bigskip
\vspace*{+.1in} \noindent Received May 3 2007; revised version
received July 26 2007. Published in {\it Journal of
Integer Sequences}, August 2 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}