\documentclass[12pt,reqno]{article}

\usepackage
[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\usepackage{color}
\usepackage{fullpage}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage[all]{xy}
\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}
\makeatletter

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



\begin{center}
\vskip 1cm {\LARGE\bf A Note on Rational Succession Rules}
\vskip 1cm
\large 
Enrica Duchi\\
Dipartimento di Sistemi e Informatica, Via Lombroso 6/17\\
50134 Firenze, Italy\\
\href{mailto:duchi@dsi.unifi.it}{\tt duchi@dsi.unifi.it}\\
\ \\

Andrea Frosini \\
Dipartimento di Matematica, Via del Capitano, 15 \\
53100 Siena, Italy \\
\href{mailto:frosini@unisi.it}{\tt frosini@unisi.it}\\
\ \\

Renzo Pinzani \\
Dipartimento di Sistemi e Informatica, Via Lombroso 6/17\\
50134 Firenze, Italy\\
\href{mailto:pinzani@dsi.unifi.it}{\tt pinzani@dsi.unifi.it}\\
\ \\

Simone Rinaldi \\
Dipartimento di Matematica, Via del Capitano, 15 \\
53100 Siena, Italy \\
\href{mailto:rinaldi@unisi.it}{\tt rinaldi@unisi.it}\\

\vskip .5cm
\end{center}

\date{}

\pagestyle{myheadings}


\bibliographystyle{plain}
\newtheorem{definizione}{Definition}
\newtheorem{osservazione}{Osservazioni}
\newtheorem{proprieta}{Propriet\`a}
\newtheorem{teorema}{Theorem}
\newtheorem{proposizione}{Proposition}
\newtheorem{esempio}{Example}
\newtheorem{lemma}{Lemma}
\newcommand{\proof}{\bf Proof.}
\newtheorem{remark}{Remark}
\newtheorem{nota}{Note}
\newtheorem{corollario}{Corollary}
\newcommand{\QED}{\rule{1ex}{1ex} \par\medskip}

\begin{abstract}
Succession rules having a rational generating function are usually
called {\em rational succession rules}. In this note we discuss
some problems concerning rational succession rules, and determine
a simple method to pass from a rational generating function to a
rational succession rule, both defining the same number sequence.
\end{abstract}

\vfill\eject

\section{Introduction} \

A {\em succession rule} is a formal system  defined by an
\emph{axiom} $(a)$, $a\in \mathbb{N}^{+}$, and a set of
\emph{productions}
\begin{displaymath}
\{ (k_{t})\rightsquigarrow (e_{1}(k_{t}))(e_{2}(k_{t}))\cdots
(e_{k_{t}}(k_{t})): t\in \mathbb{N}\} ,
\end{displaymath}
where $e_{i}:\mathbb{N}^{+}\longrightarrow \mathbb{N}^{+}$, which
explains how to derive the \emph{successors} $(e_{1}(k)),
(e_{2}(k)), \ldots , (e_{k_{t}}(k))$ of any given label $(k)$,
$k\in \mathbb{N}^{+}$. In general, for a succession rule $\Omega$,
we use the more compact notation:
\begin{equation}\label{regola}
\Omega :\left\{ \begin{array}{l}
(a) \\
(k)\rightsquigarrow (e_{1}(k))\ (e_{2}(k))\, \cdots \, (e_{k}(k)) .
\end{array}\right.
\end{equation}

The {\em labels} $(a)$, $(k)$, $(e_i(k))$ of $\Omega$ are 
assumed to contain only positive integers. The rule $\Omega$ can
be represented by means of a {\em generating tree}, that is, a
rooted tree whose vertices are labelled with the labels of
$\Omega$: $(a)$ is the label of the root, and each node labelled
$(k)$ has $k$ children labelled by $e_1(k), \ldots , e_k(k)$
respectively, according to the production of $(k)$ defined in
(\ref{regola}). A succession rule $\Omega$ defines a sequence of
positive integers $(f_n)_{n\geq 0}$, where  $f_n$ is the number of
the nodes at level $n$ in the generating tree defined by $\Omega$.
By convention the root is at level $0$, so $f_0=1$. The function
$f_\Omega(x)=\sum _{n\geq 0} f_n x^n $ is the {\em generating
function} determined by $\Omega$.

Succession rules are closely related to a method for the
enumeration and generation of combinatorial structures, called
the {\em ECO method}. For further details and examples about
succession rules and the ECO method we refer to \cite{ECO}; in
\cite{FPPR} the authors study succession rules from an algebraic
point of view.

Two rules are {\em equivalent} if they have the same generating function.
A succession rule is {\em finite} if it has a finite number of labels and productions; for example, the rule

\begin{equation}
\left\{ \begin{array}{l}
(2) \\
(2)\rightsquigarrow (2)(3)\\
(3)\rightsquigarrow (2)(3)(3),
\end{array}\right.
\label{eq1}
\end{equation}

\noindent defining odd-index Fibonacci numbers $1,2,5,13,34,89,233, \ldots$
(sequence A001519 in \cite{Sl}) is finite and it is equivalent to

\begin{equation}
\left\{ \begin{array}{l}
(2) \\
(k)\rightsquigarrow (2)^{k-1} (k+2),
\end{array}\right.
\label{eq2}
\end{equation}

\noindent which is not finite.

\medskip

Figure \ref{array} depicts the first levels of the generating
trees associated with the rules in (\ref{eq1}) and (\ref{eq2}).

\medskip

\begin{figure}[htb]
\centerline{\hbox{\psfig{figure=array.eps,width=4in,clip=}}}
\caption{The first levels of two equivalent generating trees.}
\label{array}
\end{figure}

According to our definition, two labels containing the same
integer $k$ are allowed to have a different production. If this
happens we distinguish those labels using some indices (or {\em
colors}, see Example \ref{example}). A succession rule is called
{\em rational}, {\em algebraic} or {\em trascendental} according
to the generating function type. Rational succession rules are the
subject of this note (see also \cite{GFGT}, \cite{FPPR}).

\medskip

Below we list some classes of generating functions:

\begin{description}
\item[-]$\cal R$ is the set of rational generating functions of
integer sequences ($Z$-rational functions, using the notation in
\cite{SS}); \item[-]${\cal R}^+$ is the set of rational generating
functions of positive integer sequences; \item[-]$REG$ is the set
of generating functions of regular languages; \item[-]$\cal S$ is
the set of rational generating functions of succession rules;
\item[-]$\cal F$ is the set of generating functions of finite
succession rules.
\end{description}

Summarizing the results in \cite{SS}, \cite{FPPR} we obtain the
following scheme:

\bigskip

\makeatother
\centerline{
\xymatrix{ %
& {REG}\ar @{}[dr]|{\rotatebox{-45}{$\subset$}}\\
\mathcal{F} \ar@{}[ur]|-{\rotatebox{45}{$\subset$}}
\ar@{}[dr]|-{\rotatebox{-45}{$\subseteq$}}& \ar@{}[r]|-{ }
&\mathcal{R}^+ \ar@{}[r]|-{\subset}
&\mathcal{R}\\
& \mathcal{S} \ar@{}[ur]|-{\rotatebox{45}{$\subset$}} %
}}
\makeatletter

\bigskip

The classes $\cal R$, $REG$, and $\cal F$ are decidable, while
${\cal R}^+$ is not decidable. In \cite{FPPR} is conjectured that
${\cal F}={\cal S}$, i.e., every rational rule is equivalent to a
finite one.

This note proposes a simple tool to pass from a rational
generating function (i.e., a linear recurrence relation) defining a
non-decreasing sequence of positive integers to a succession rule
defining the same sequence. The results extend those in [GFGT].

Furthermore our technique provides interesting combinatorial
interpretations (in terms of generating trees) for sequences that
are defined by a linear recurrence relation, using an approach
different from that in \cite{BDFR} and \cite{BR}.

As an application of our method, we give a simple solution to a
problem proposed by Jim Propp on the mailing list ``domino''
(1999), where he asked for the combinatorial interpretation of the
sequence $1,1,1,2,3,7,11,26,\ldots $ (sequence A005246 in
\cite{Sl}) defined by the linear recurrence relation:

$$\left \{ \begin{array}{l}
f_0=1, \quad f_1=1, \quad f_2=1, \quad f_3=2 \\
f_n=4f_{n-2}-f_{n-4}.
\end{array}
\right.$$


\section {Two term linear recurrences.}\

We start by considering two-term linear recurrences:
$$ f_n= h_1 f_{n-1}+h_2f_{n-2}, \qquad h_1,h_2 \in \mathbb{Z}$$
with initial conditions $f_0 = 1$, $f_1=s_0\in\mathbb{N}^+$. The
positivity of the sequence is ensured by the additional conditions
$h_1 \in \mathbb{N}^+$, and $h_1 + h_2
>0$.

\begin{proposizione}\label{two}
The succession rule

\begin{displaymath}
\Omega = \left\{
\begin{array}{l}
(s_0) \\
(k) \leadsto (1)^{k-1} \left( \phi(k) \right),\\
\end{array}
\right.
\end{displaymath}

\medskip

\noindent with $\phi(k)=(h_1 -1)k + h_2 + 1$, defines the sequence
$(f_n)_{n\geq 0}$.
\end{proposizione}

\noindent{\bf Proof.}  We have  $f_0=1$ and $f_1=s_0$. Let $k_1, \, k_2,
\ldots, k_{f_{n-2}}$ be the  labels at level $n-2$ of the
generating tree of $\Omega$.  Then,  for $n \ge 2$,
$$
f_{n}=  k_1 + k_2+ \cdots + k_{f_{n-2}} - f_{n-2} + (h_1 -1)(k_1 +
k_2+ \cdots + k_{f_{n-2}})+ f_{n-2}(h_2 +1).
$$


Consequently we have
$$
f_{n}= f_{n-1} -f_{n-2} + (h_1 -1)f_{n-1} + f_{n-2}(h_2 +1)= h_1
f_{n-1}+h_2f_{n-2} \quad n \ge 2. \mbox{ \QED}
$$

\medskip

A succession rule defining the sequence $(f_n)_{n\geq 0}$ can
however have a more general form, such as:
\begin{displaymath}
\Omega_2 =
\left\{
\begin{array}{l}
(s_0) \\
(k) \leadsto (c)^{k-1} \left( \phi(k) \right)\\
\end{array}
\right.
\end{displaymath}
where $c, s_0 \in \mathbb{N}^+$, $\phi(k)= (h_1-c)k+h_2+c$, and
the positivity of the labels is ensured by the following
conditions:

\begin{itemize}
\item[\em{(i)}] if $c \le s_0$ then $1 \le c\le h_1$ and
$((h_1-c)c+h_2+c)>0$; \item[\em{(ii)}] if $c > s_0$ then $s_0 \le
c \le h_1$ and $((h_1-c)s_0+h_2+c)>0$.
\end{itemize}

\section {Linear recurrences with more than two terms.}

In this section we consider the general case of linear
recurrences defining non-decreasing sequences of positive
integers, and we give the explicit form of succession rules
defining such sequences.

For the sake of simplicity, let us start by studying the case of
three term recurrences of the form
$$f_n= h_1 f_{n-1}+h_2f_{n-2}+ h_3f_{n-3},$$
with $f_{-1}= 0$, $f_0 = 1$, $f_1=s_0\in \mathbb{N}^+$, where $h_1
\in \mathbb{N}^+$ and $h_2, h_3 \in \mathbb{Z}$.

\medskip

\noindent On the other hand, let us consider the rule

\begin{displaymath}
\Omega_3 =
\left\{
\begin{array}{ll}
(s_0) \\
(k) \leadsto \left( c \right) ^{k-1} \left( \phi^0(k) \right)&  k= {s_0}, {c}\\
(k) \leadsto \left(  {c} \right) ^{k-1} \left( \phi^1(k) \right)&  \\
\end{array}
\right.
\end{displaymath}

\noindent where $c \in \mathbb{N}^+$, and

$$
\begin{array}{l}
\phi^0(k)= (h_1-c)k+h_2+c, \\
\\
\phi^1(k)= (h_1-c)k+h_2+h_3+c.
\end{array}
$$

\medskip

\noindent The following conditions easily ensure that the labels
of $\Omega_3$ are positive and, as a consequence, the sequence
defined by $\Omega_3$ is positive and non-decreasing.

\begin{itemize}
\item[(i)] If $c \le s_0$ then $1 \le c\le h_1$, $\left(
\phi^0(c)\right)>0$ and $\phi^1 \left( \phi^0(c) \right) >0$.
\item[(ii)] If $c > s_0$ then $s_0 \le c\le h_1$, $\left(
\phi^0(s_0)\right)>0$ and $\phi^1 \left( \phi^0(s_0) \right) >0$.
\end{itemize}

\begin{proposizione}
The succession rule $\Omega_3$ defines the sequence $(f_n)_{n\geq
0}$.\label{three}
\end{proposizione}

\noindent{\bf Proof.} We can easily verify that $f_0=1$, $f_1=s_0$ and
$f_2=h_1s_0+h_2$. For $n \ge 3$  the number of occurrences of the
label $ {c}$ at level $n-3$ is equal to $f_{n-2}- f_{n-3}$, so we
obtain
$$f_n= {c}f_{n-1}- {c}f_{n-3}+(h_1- {c})f_{n-1}+
(h_2+h_3+ {c})f_{n-3}- {c}\;(f_{n-2}-f_{n-3})+(h_2+
{c})(f_{n-2}-f_{n-3}),
$$
which simplifies to $f_n=h_1f_{n-1}+h_2f_{n-2}+h_3f_{n-3}$ for $n
\ge 3$. \QED

\begin{esempio}\label{example}
{\em The sequence $(f_n)_{n\geq 0}$ satisfying the recurrence
relation
$$f_n= 3f_{n-1}-2f_{n-2}+f_{n-3},$$
with $f _1= 0, \, f_0=1, \, f_1= 2,$ is defined by the succession
rule
\begin{displaymath}
\left\{
\begin{array}{ll}
(2) \\
(1) \leadsto (1)&\\
(2) \leadsto (1)(3) &\\
(k) \leadsto (1)^{k-1} (2k) &k\geq 3. \\
\end{array}
\right.
\end{displaymath}
}

\end{esempio}

In the sequel we will extend the statement of Proposition
\ref{three} to the general case of linear recurrences.

\medskip

Let us consider the rule

\medskip

\begin{displaymath}
\Omega_j =
\left\{
\begin{array}{ll}
( {s_0}) \\
(k) \leadsto  (  {c})^{k-1} \left(  {\phi^0(k)} \right)&  k= {s_0},\;  {c} \\
(k) \leadsto  (  {c})^{k-1} \left(  {\phi^1(k)}
\right)&  k = {\phi^0(s_0)},\;  {\phi^0 (c)}  \\
(k) \leadsto  (  {c})^{k-1} \left(  {\phi^2(k)} \right)
&k = { \phi^1 \left( \phi^0 (s_0 \right))}, \;  {\phi^1 \left( \phi^0 (c) \right)}  \\
\vdots & \\
(k) \leadsto  (  {c})^{k-1} \left( {\phi^{j-3}(k)} \right) & k = \left\{ \;  {\phi^{j-4} (\phi^{j-5} ( \cdots \phi^1 (\phi^0(x))))}: \; x=s_0,c  \; \right\} \\
(k) \leadsto (  {c})^{k-1} \left(  {\phi^{j-2}(k)} \right), &
\end{array}
\right.
\end{displaymath}

\medskip

\noindent where $c, s_0, h_1 \in \mathbb{N}^+$, $h_2, h_3, \ldots, h_j \in
\mathbb{Z}$, and
$$ \phi^m(k)=
(h_1-c)k+\sum_{i=1}^{m+1}h_{i+1}+c, \qquad m= 0, \ldots, j-2. $$

The following conditions determine the positivity of the labels of
$\Omega_j$:
\begin{itemize}
\item[\em{(i)}] if $c \le s_0$ then $1 \le c\le h_1$, $\phi^{i-2}
\left( \phi^{i-1}(\cdots \phi^{0}(c)) \right) $, $i=2, \ldots, j$;
\item[\em{(ii)}] if $c > s_0$ then $s_0 \le c\le h_1$,
$\phi^{i-2}\left( \phi^{i-1}(\cdots \phi^{0}(s_0)) \right) $, $i=2,
\ldots, j$.
\end{itemize}

\begin{teorema}\label{tree}
The succession rule $\Omega_j$ defines the non-decreasing positive
sequence satisfying the recurrence relation:
$$f_n= h_1 f_{n-1}+h_2f_{n-2}+ \cdots +h_jf_{n-j},$$
\noindent with initial conditions $f_{i}= 0, \; i=-j+2, \ldots,
-1$, $f_0 = 1$, and $f_1=s_0$.
\end{teorema}

\noindent{\bf Proof.} Analogous to that of Proposition \ref{three}. \QED

\begin{esempio}
{\em

\begin{itemize}

\item[(i)] NSW numbers (sequence A002315 in \cite{Sl}) are defined
by the recurrence relation:

$$ f_n=6 f_{n-1} - f_{n-2}, \qquad f_0=1, \; f_1=7. $$

These numbers count the total area under elevated Schr\"oder paths
\cite{PP, BSS}. According to Theorem \ref{three}, the succession
rule defining these numbers is
$$
\left\{ \begin{array}{l}
(7) \\
(k)\rightsquigarrow (1)^{k-1}(5k)
\end{array}\right.
$$

\item[(ii)] Self-avoiding walks of length $n$, contained in the
strip $\{ 0,1 \} \times [- \infty , \infty ]$, are counted by the
sequence $\{ f_n \}$ that satisfies a linear recurrence relation
\cite{Z}:
\begin{equation}\label{self}
 \begin{array}{ll}
f_0=1, \; f_1=3, \; f_2=6, \; f_3=12, \; f_4=20, \; f_5=36, \; f_6=58, \; f_7=100,  & \\
f_n=f_{n-1}+3 f_{n-2}+ 2f_{n-3}-3f_{n-4}+ f_{n-5}+ f_{n-6} &n>7.
\end{array}
\end{equation}

For simplicity we change the initial conditions into the following:
$$
\begin{array}{ll}
f_{-i}=0, & i=1, \ldots, 5 \\
f_0=1. &
\end{array}$$

\noindent Then the succession rule obtained applying Theorem
\ref{tree} is

$$
\left\{ \begin{array}{l}
(1)\\
(1)\rightsquigarrow (4)\\
(3)\rightsquigarrow (1)^{2}(\overline{4})\\
(4)\rightsquigarrow (1)^{3}(6)\\
(\overline{4})\rightsquigarrow (1)^{3}(5)\\
(5)\rightsquigarrow (1)^{4}(5)\\
(6)\rightsquigarrow (1)^{5}(3).\\
\end{array}\right.
$$

\end{itemize}

For clarity's sake, we want to point out that the label $(4)$ is
produced by $\phi^0(c)$, and it is subject to the rule involving
$\phi^1$, while the label $(\overline{4})$ is subject to the rule
involving $\phi^4$.

Finally, we remark that a rule defining the original number
sequence can be simply obtained by adding some other productions,
in order to satisfy the initial conditions.}
\end{esempio}

\begin{esempio}
{\em Now we are able to give a succession rule for the number
sequence $1,1,1,2,3,7,11,26,\ldots $, defined in the first part of
the paper. Omitting for simplicity the initial constant terms we
have
\begin{displaymath}
\left\{
\begin{array}{ll}
(2) \\
(2) \leadsto (1)(2)\\
(1)\leadsto(4)\\
(4)\leadsto (1)^{3}(\overline{1})\\
(3)\leadsto (1)^{2}(\overline{1})\\
(\overline{1})\leadsto(3).\\
\end{array}
\right.
\end{displaymath}
}

\end{esempio}

\paragraph{Succession rules with negative labels.}
Theorem \ref{three} clearly does not involve the whole set $\cal
R$ of rational generating functions. Moreover, as we already
remarked, the problem of establishing if a rational generating
function defines a non-negative sequence of integers is
undecidable, and then if we want to treat the whole set of
rational generating functions we have to allow labels of the rules
to contain negative values. Under this hypothesis a succession
rule defines a sequence of integer numbers $(f_n)_{n\geq 0}$, not
necessarily positive, where the term $f_n$ is given by the number
of positive labels minus the number of negative labels at level
$n$ of the generating tree.

Recently we investigated the relationship between rational
generating functions and succession rules with negative labels
(briefly {\em generalized succession rules}) by applying the same
tools that we used in the first part of the paper. Furthermore we
determined an algorithm to pass from a rational generating
function to a generalized succession rule. However this algorithm
has a rather complex description, and moreover it does not give an
answer to the conjecture ${\cal F}={\cal S}$. Therefore, for the
sake of simplicity, we only present the following examples.

\begin{esempio}
{\em Let us consider the number sequence $1,2,-10,22,-26,-10,134,
\ldots $, defined by the recurrence relation
$$ \begin{array}{ll}
f_0=1, \; f_1=2,  & \\
f_n=-3 f_{n-1}-4 f_{n-2} &n>1.
\end{array}
$$

The succession rule defining this sequence is
\begin{displaymath}
\left\{
\begin{array}{ll}
(4) \\
(k) \leadsto (1)^{k-1}(-2k-1)\\
(-k) \leadsto (-1)^{k-1}(2k+1) .\\
\end{array}
\right. 
\end{displaymath}
}

\end{esempio}

\medskip

\begin{esempio}
{\em Odd-index Fibonacci numbers with alternating sign, $1,-2,5,
-13, 34, -89, \ldots $, are defined by the recurrence relation
$$ \begin{array}{ll}
f_0=1, \; f_1=-2,  & \\
f_n=-3 f_{n-1}- f_{n-2} &n>1.
\end{array}
$$

A succession rule defining this sequence is
\begin{displaymath}
\left\{
\begin{array}{ll}
(2) \\
(k) \leadsto (-1)^{k-1}(-2k)\\
(-k) \leadsto (1)^{k-1}(2k).\\
\end{array}
\right.  \label{eq3}
\end{displaymath}

We point out that the rule (\ref{eq3}) is very similar to
(\ref{eq2}), which defines the odd-indexed Fibonacci numbers. }
\end{esempio}


\begin{thebibliography}{8}

\bibitem[GFGT]{GFGT} C. Banderier, M. Bousquet-M\'elou,
A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps,\quad
Generating functions for generating trees, {\it Discrete\ Math.} {\bf 246} (2002), 29--55.

\bibitem[BDFR]{BDFR}
E. Barcucci, A. Del Lungo, A. Frosini, and S. Rinaldi, A technology
for reverse-engineering a combinatorial problem from
 a rational generating function,
{\it Adv.\ Appl.\ Math.} {\bf 26} (2001), 129--153.

\bibitem[BR]{BR}
E. Barcucci and S. Rinaldi,
\newblock Some linear recurrences and their combinatorial interpretation
by means of regular languages,
\newblock {\it Theor. Comp. Sci.} {\bf 255} (2001), 679--686.

\bibitem[BSS]{BSS}
J. Bonin, L. Shapiro, and R. Simion,
\newblock {\rm Some $q$-analogues of the Schr\"oder numbers arising from combinatorial statistics on
lattice paths,}
\newblock {\it J. Statistical Planning and Inference } {\bf 34} (1993) 35--55.

\bibitem[BDLPP]{ECO} E. Barcucci, A.
Del Lungo E. Pergola, and R. Pinzani, ECO: a methodology for
the enumeration of combinatorial objects, {\it J. Difference Eq. Appl.}
{\bf 5} (1999), 435--490.

\bibitem[FPPR]{FPPR} L. Ferrari, E. Pergola, R. Pinzani, and S. Rinaldi,
An algebraic characterization of the set of succession
rules, {\it Theor.\ Comp.\ Sci.} {\bf 281} (2002), 351--367.

\bibitem[PP]{PP}
E. Pergola and R. Pinzani,
\newblock {\rm A combinatorial interpretation of the Area of Schr\"oder paths,}
\newblock {\it Electronic J. Combinatorics} {\bf 6} (1999), \#R40.
\href{http://www.combinatorics.org/Volume_6/Abstracts/v6i1r40.html}{\tt http://www.combinatorics.org/Volume\_6/Abstracts/v6i1r40.html}

\bibitem[SL]{Sl} N. J. A. Sloane\quad \emph{The On-Line Encyclopedia of
Integer Sequences},
\href{http://www.research.att.com/~njas/sequences/index.html}{\tt http://www.research.att.com/\char'176njas/sequences/index.html}.

\bibitem[SS]{SS} A. Salomaa and M. Soittola,
\newblock {\em Automata-Theoretic Aspects of Formal Power Series},
\newblock Springer-Verlag, 1978.

\bibitem[Z]{Z}
D. Zeilberger,
\newblock Self-avoiding walks, the language of science, and Fibonacci numbers,
\newblock {\em J. Stat. Inference and Planning} {\bf 54} (1996) 135--138.

\end{thebibliography}


\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords:  succession rules, generating trees, rational generating
functions}



\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001519}
\seqnum{A005246}
\seqnum{A002315}.)



\vspace*{+.1in}
\noindent
Received December 23, 2002;
revised version received  April 22, 2003.
Published in {\it Journal of Integer Sequences} April 24, 2003.
\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.

\vskip .1in


\end{document}