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