%animal.tex: ``Symbol-Crunching  the Transfer-Matrix Method...
%a Plain TeX file by Doron Zeilberger (29 pages)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=15pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\lheading#1{\bigbreak \noindent {\bf#1} 
}
\parindent=0pt
\overfullrule=0in

\voffset=30pt
\hoffset=10pt
\parindent=0pt
\hsize=6.25 true in
\vsize=8.75 true in
\font\smallit=cmti9
\font\smalltt=cmtt9
\font\smallrm=cmr8

\headline={\ifnum\pageno<2 \hfil \else
\smalltt INTEGERS:  \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL
NUMBER THEORY \smalltt 0 (2000), \#A09 \hfil \folio \fi}

\footline={\hfil}

%end macros
 
\centerline
{ \bf SYMBOL-CRUNCHING WITH THE TRANSFER-MATRIX METHOD}

\centerline{\bf IN ORDER TO COUNT
SKINNY PHYSICAL CREATURES}
\vskip30pt
\centerline{{\bf
Doron Zeilberger}
\footnote{$^1$}{{\eighttt http://www.math.temple.edu/\Tilde zeilberg/.}
{\smallrm Supported in part by the NSF.
This article is accompanied by seven Maple packages,
downloadable from  
{\eighttt http://www.math.temple.edu/\Tilde zeilberg/tm.html} 
where sample input and output files can also be found.}}}

\centerline{\smallit
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA.}

\centerline{\tt zeilberg@math.temple.edu} 
\vskip 40pt
\centerline{\smallit Received: 3/30/00, Revised: 7/17/00,
Accepted: 8/3/00, Published: 8/4/00}
\vskip30pt

\qquad\qquad {\it  The transfer-matrix method, like the
Principle of Inclusion-Exclusion and the M\"obius inversion formula,
has simple theoretical underpinnings but a very wide range of
applicability.}
\smallskip
\hfill
-- Richard  P. Stanley ([S], p. 241)
\vskip30pt
\baselineskip=12pt
\centerline{\bf Abstract} 
We describe Maple packages for
the automatic generation of generating functions
(and series expansions) for three 
notoriously hard-to-count combinatorial objects that
arise in statistical physics: lattice animals (alias
polyominoes), self-avoiding polygons, and self-avoiding
walks, in the two-dimensional square lattice, of bounded,
but {\it arbitrary} width. The novelty of
this work is in its {\it generality}, 
{\it reproducibility}, {\it explicitness of details},
and {\it availability}. Our Maple packages 
(complete with {\it source code}) are easy-to-use
and downloadable free of charge.
But perhaps, most
important, it is hoped that this work will 
{\it illustrate by example}
an admittedly crude and semi-amateurish, 
yet honest, attempt at a foundation for
a {\it work ethics} and  {\it research methodology},
of what will soon be a major part of 3rd millennium
mathematical research, and that for lack of a better
name we call {\it mathematical engineering}.

\baselineskip=15pt
\parindent=15pt
\vskip30pt
 
 
\line{\bf 1. From Number-Crunching to Symbol-Crunching in 
Computational \hfill} 
\line{\bf \hskip 14pt Combinatorial Statistical Physics \hfil}
 
Combinatorial Statistical Physics has several {\it impossible} problems
that define it. For example, the Ising model in a magnetic field,
percolation, and the enumeration of lattice animals,
self-avoiding walks and self-avoiding polygons. Even though they are
(probably) impossible, or at least intractable, there is
a vast literature on them. One tries to find, both
rigorously and non-rigorously, both exactly and approximately,
important numbers associated with these problems, like
connective constants, and more interestingly {\it critical
exponents}. One also uses {\it number-crunching} to find
{\it series expansions} that enable estimates of these important
numbers. Another cottage industry is that of 
tractable {\it toy models},
that are subsets or supersets of the `impossible-to-count' sets.
 
Even today there is a sharp dichotomy between `theoretical research'
that tries to find analytical solutions by pencil-and-paper
human reasoning, and `computational research' that uses the
computer to crank-out important numbers. The advent of computer-algebra
has enabled (e.g. the remarkable work of the Bordeux school [DV][B])
to use it as a {\it tool} for {\it solving} human-derived equations.
In this research mode the {\it human} uses {\it human reasoning}
(possibly aided by computers, but still with human guidance)
to {\it derive} the {\it equations} for the desired quantities.
Once the equations are obtained, they are fed into the
computer-algebra system (like Maple, Mathematica, etc.), that
solves them.
 
But even {\it deriving} the set of equations whose solution
would produce the desired generating function could be a very
difficult, and often impossible, task for a mere human.
The next natural step is to `teach' (i.e. program) the computer
to {\it find the equations}, {\it all by itself}.
 
Indeed, in order to take full advantage of the computer revolution,
WE MUST TEACH THE COMPUTER HOW TO DO RESEARCH ON ITS OWN.
The difficulty of this `idea crunching' is that at present,
Maple, Mathematica, and their likes are really only one
notch above Fortran, C, and their like. In principle
we can do symbolic computation in C and even in Fortran
(or for that matter, even in machine language), after all,
everything reduces to a Turing Machine, and in fact
the core of Maple is actually written in C! However, from
the user's interface point of view this is very awkward.
 
The same difficulty faces us right now, when we try to
do, essentially, `meta-symbolic computation',
or, more accurately, `idea-crunching' (idea-ics, for short).
Doing `idea-ics' in Maple is the
higher-level analog of doing symbolics in Fortran.
I am sure that in a few years we would have a Meta-Maple
that would make the task of the present undertaking much easier.
Conversely, it is hoped that this effort, and efforts like it,
would stimulate and guide future system-developers.
 
Once this higher-level Maple (or Mathematica, etc.) will become
available, it would be possible to state, for example,
the following command (in the appropriate formal language,
and perhaps even in English):
 
{\it Write a Maple program that inputs an integer $k$ and
a variable $s$ and outputs the rational function
$\sum_{n=0}^{\infty} a_k(n)s^n$, where
$a_k(n):=$ the number of self-avoiding walks of length n that is
confined to the strip $0 \leq y \leq k$}.
 
We would also need to tell the computer what is a {\it self avoiding
walk} but this can be done in one line in any formal language.
 
 
Since this Meta-Maple is not yet available, I had
to spend a month of my precious time to {\it write the program by hand},
(which, incidentally, turned out to be more complicated than I anticipated).
Even though this is very crude compared to the future, it is
definitely progress compared to the previous efforts discussed below.
 
With the exception of Mikovsky's remarkable thesis[M],
in past work, both for number- and symbol
crunching,
for example of the Australian (e.g. [BY], [CG]) and Bordelaise
(e.g. [DV],[B]) schools, one had to find the `alphabet' and
`grammar' (or equivalently the `transfer matrix') by hand,
for one $k$ at a time (where $k$ denotes the width of the counted
creatures).  Also, the source-code was normally not
published, nor made available upon request. 
With the Maple packages accompanying this article,
{\it anybody} with access to the web, and access to
Maple (that can be purchased for less than \$100),
can download, for example, my Maple program {\tt SAW}, go into
Maple, and type, {\tt read SAW:}, followed by
say, {\tt GFW(5,s);}, and after a few minutes he or she would get
the {\it exact answer} for the generating function for
the sequence: the number of $n$-step self-avoiding walks,
on the two-dimensional square lattice such that the largest $y$
coordinates minus the smallest $y$ coordinates is $\leq 5$.
He or she, can of course type {\tt GFW(k,s)}, for any desired $k$.
Even though, with current computers, it would be hopeless to get
{\tt GFW(100,s)} or even {\tt GFW(12,s)}, it is very gratifying
that {\it in principle} the program can do it. Also he or
she can read and enjoy the source-code, and later modify it
for different problems.
 
There is very little `conceptual originality' in this article.
The transfer-matrix method is a standard {\it tool of the trade}
in this area, used in computational and theoretical work alike.
So the ``traditionalist'' (who is usually computer-illiterate
and hence unable, and very often also unwilling,
to appreciate the effort that went into such an endeavor) might
dismiss it as `trivial', something to be published
in ``lowly'' ``software-engineering journals''.
To him I retort: don't be a theoretical snob! Don't you know that:
THE IMPLEMENTATION IS THE MESSAGE.
 
And believe me, it
was not easy! Especially for the Self-Avoiding Walks program
({\tt SAW}), I had to {\it think} much harder than I did
for my previous `human' stuff! So here is another point I am trying
to make (already made in my Opinion 37 [Z1]): Programming
to do a specific task is difficult and important research!
Much more important than proving, humanly, yet another theorem.
True, the programs of this project will be superseded and made obsolete
by future developments, (since, as I argued above,
it would be enough to {\it state} the general problem to the computer,
and it would {\it write the program} for you).
But the proof of Fermat's Last
Theorem will enjoy the same fate of obsolescence and `triviality'
as the present project.
All {\it current} math proofs 
(and computer programs) would be completely computer-generated in less
than fifty years. So, although Wiles's proof and my Maple programs 
are both destined to
become obsolete in the not-too-distant future, I hold that,
from a `future-history' point of view, this article,
and articles like it, constitute a more significant
contribution to mathematics than the proof
of Fermat's Last Theorem (I conceded that from a `past-history'
viewpoint, Wiles's proof wins).
 
Indeed, Wiles's proof does not contribute a iota to the really important
problem that faces 21st-century mathematics: TEACH THE COMPUTER
HOW TO DO RESEARCH. By contrast, my present effort is an
admittedly modest, yet strictly positive, step in the
right direction. It teaches the computer how `to do research', 
albeit very narrowly-focused, in the
sense that it does `theoretical research' that goes beyond
routine numeric and even symbolic computation. 
As I have already mentioned above, the computer
is used not just to {\it solve} the humanly-generated or
computer-aided {\it set of equations}, but it is used to
{\it generate the equations} for an {\it infinite} family
of problems, {\it ab initio}. 
 
I know that this is a tiny advance,
but Rome was not built in a day, and as we know from our experience
of teaching human students, we have to teach, {\it step-by-step},
{\it very gradually} delegating more responsibility and independence to them.
One of the reasons the original efforts at AI were such a flop was
that we tried to teach the computer too much too soon,
and also, in a true species-centric way, we tried to make 
`artificial' intelligence in our own image. As we get to know
the computer better, we would learn how to teach it better, and
take advantage of its strengths.
 
But enough of prophecy. Let me now describe the 
specific contents of this paper. A substantial part of 
it is an enhancement, correction, and {\it extension}
of a large part of
Anthony Mikovsky's thesis[M], so I'll have to explain first why
his work had to be redone.
 
\vskip 30pt

\line {\bf 2. A Critique of Anthony Mikovsky's 1997 Ph.D. Thesis \hfil}
 
In a very impressive Penn 1997 Ph.D. thesis [M], under the
direction of Herb Wilf, Mikovsky used Maple to derive generating
functions for the enumeration
of lattice animals and self-avoiding
walks, confined to a finite strip, as well as convex polyominoes
(that we do not consider here). The thesis is beautifully
written, and the algorithms are described clearly both
in English and in Maple. It is indeed a pioneering
effort in computer-generated research in 
combinatorial statistical physics, but it has some weaknesses.
 
The major weakness is `trivial' but nevertheless VERY IMPORTANT.
The source code, while printed-out in full, is not
available for download from the web! Much good does it do me!
Typing is not my idea of fun! I much rather write my own program.
Even worse, Mikovsky's thesis was never published in a journal,
and the only way to get it is by paying (like I did)
more than \$40 to University Microfilms.
 
A second weakness is long-winded human rambling. After describing
the ideas behind the algorithms, he actually goes on to write down,
in full detail, 
for each of the cases $k=1,2,3$,
the `grammar' and set of equations, thereby wasting
many pages.  I agree that for pedagogical reasons it is a good idea
to have the grammar and set of equations listed for the smallest and
second-smallest cases, but the rest should be reproducible by the
reader (or rather by her computer), if desired. 
We humans should learn not to micro-manage
the computer too much, in particular, 
not ask to see intermediate results,
and trust it. Of course, only after the
program has been completely debugged.
 
A third weakness is the style of the Maple code. It does not use
modularity, and has no procedures (subroutines). It starts
out with the line : {\tt rownum=?;},
where the user is supposed to
fill-in the question-mark, 
rather than defining a procedure {\tt SAW:=proc(rownum) local ...},
and using smaller procedures. Mikovsky gives very few comments,
and the code is very hard to follow and verify.
 
Finally, at least for his Maple program on self-avoiding walks,
Mikovsky failed to test the output against independently
generated, or readily available, data. While his output and mine
agree for lattice-animals, they disagree in the case of
self-avoiding walks. According to his corollary
5.5 (p. 163), half the number of self-avoiding walks
with $4$ steps and width $\leq 3$ equals 57, while it is well-known,
(and easy to find by direct counting) that there are only
$100$ such walks altogether, and two of them have width $4$,
hence the true number is $(100-2)/2=49$ rather than $57$.
So his program must be flawed. By contrast, I know that my version
({\tt SAW}), is correctly implemented, since the output was
compared to published tables, and independently generated output
from `empirical' programs.

\vskip 30pt
 
\line{\bf 3. The Specific Goals and Results of This Work \hfil}
 
In addition to the rather pompous `justification'
presented in the abstract, there
are more down-to-earth reasons for taking the trouble.
Thanks to the Maple package {\tt ANIMALS} one can now
compute the generating function for lattice-animals of
width $\leq k$, for {\it arbitrary} $k$
(at present it is feasible to go up to $k=6$, but as computers
get faster and bigger one should be able to go beyond).
If one is content with {\it series expansions}, i.e.
the first $200$ (or whatever) terms of the generating functions,
then one can go much further. Of course, in principle our programs
can handle any integer $k$.
 
Thanks to the Maple package {\tt SAP} one can now
find generating functions, and series expansions, for
{\it self-avoiding polygons} of width $\leq k$ for {\it any} $k$.
 
Thanks to the Maple package {\tt SAW}, one can do the same
for {\it self-avoiding walks} of bounded width.

\vskip 30pt
 
\line {\bf 4. Counting  More Inclusive Classes of Creatures:
Only Restricting the Width \hfil}
\line{\bf \hskip 14pt of Individual `Letters' \hfil}
 
Of course, the holy grail is the enumeration of the original
`impossible-to-count' objects, and the purpose of the
studied `toy models' is to approximate, both numerically
and conceptually, the `real-thing'. I noticed that once
the transfer-matrix method 
for counting creatures confined to a strip is
implemented correctly, then a slight modification of
the `Transfer Matrix' enables us to count the much wider class
of creatures in which we do not insist that the whole creature
should fit in a finite, fixed, strip, but only that
each {\it individual vertical cross-section} has bounded
width. The matrices get smaller (since there are fewer
letters), and the `connective constants' for these subclasses
(which imply lower bound for the `real' connective constant)
are higher than their counterparts. In particular,
we were able to improve the previous record of [WS] (see [F])
for the lower bound for 'Klarner's constant' (the connective
constant for lattice-animals) from $3.791$ (and its
updated value using the extended series expansion,
$3.8228$, see [F]) to $3.8499$.
 
The Maple packages enumerating these extended sets of creatures are
{\tt freeANIMALS \hskip -8pt, \hskip -5pt freeSAP}
and {\tt freeSAW}.

\vskip 30pt
 
\line{\bf 5. Coming Up Soon: The Umbral Transfer Matrix Method \hfil}
 
But the {\it main} reason for spending so much time developing
Maple packages and implementing 
seemingly minor enhancements of largely known algorithms is that we
need it as a starting point for the `Umbral Transfer Matrix Method' [Z2].
Now, we no longer have a `finite alphabet' but an `infinite alphabet',
and the `approximation' both conceptually and computationally to the
`real things' is much better. Hence 
the Maple packages presented in this article are not the shortest possible,
for the specified task.
Rather they are written in a form that would facilitate climbing from the
(finite) Transfer-Matrix method to the 
(infinite) Umbral Transfer-Matrix method.
 
In the present case we had a generalization in mind, but any project should
be considered as a link in an infinite chain of consecutive generalizations,
hence it should be written as clearly and modularly, as possible,
and carefully documented, so that future researchers can use it
both as a `black box', or as a starting point for tweaking and
modifying. Of course these precepts are part of the 
{\it practice of programming}, (see e.g. the classic [KP]), 
the trite-but-true dos and donts of the professional software
engineer and developer.
But even we, professional mathematicians but as yet
amateur programmers, would do well to adhere to them.
Within reason,
of course, after all, we can't spend {\it all} our time programming
and documenting.
 
\vskip 30pt
 
\line{\bf 6.1. The Transfer-Matrix Method \hfil}
 
There are several equivalent
formulations of the Transfer-Matrix Method. 
One  can talk about `finite-automata', a `Markov-Process' , or
a `type-3 grammar in normal form', but the most straightforward
way is in terms of weighted counting of paths in a directed graph.
 
We will follow Stanley[S], but things will be even simpler 
for us, since
we don't have to know any linear algebra, because Maple does. All we have
to do is know how to set up the system of equations.

\noindent 
{\bf Definition}: A directed graph $(V,E,init,fin)$, consists of a finite set
of "vertices", $V$, a finite set of "directed edges", $E$, 
and two functions
$init:E \rightarrow V$ and $fin:E \rightarrow V$.
 
For $e \in E$ we say that $e$ goes from vertex $init(e)$ to 
vertex $fin(e)$.

\noindent 
{\bf Definition}: A path in a directed graph $(V,E,init,fin)$ is
a sequence
$$
v_1,e_1,v_2, \dots, v_i,e_i,v_{i+1}, \dots, e_{k},v_{k+1}
$$
with $v_i \in V, (1 \leq i \leq k+1)$,
$e_i \in E, (1 \leq i \leq k)$, and
$init(e_i)=v_i, fin(e_i)=v_{i+1}, (1 \leq i \leq k)$.
 
\noindent  
{\bf Definition:} A  Combinatorial
Markov Process is a 6-tuple, $(V,E,init,fin,Start,Finish)$, where
$(V,E,init,fin)$ is a directed graph defined above, 
and $Start$ and $Finish$ are subsets of $V$.

\noindent  
{\bf Definition:} A Vertex-Weighted (resp. Edge-Weighted)
Combinatorial Markov Process is a seven-tuple $(V,E,init,fin,Start,Finish,wt)$,
where $(V,E,init,fin,Start,Finish)$ is a Combinatorial Markov Process and $wt$
is a function from $V$ (respectively $E$) to the positive
integers.

\noindent  
{\bf Definition:} The {\it weight} $Wt(P)$ of a path
$P=v_1,e_1,v_2,e_2, \dots, v_i,e_i,v_{i+1}, \dots , v_k, e_k, v_{k+1}$,
in a Vertex-Weighted Markov Process is:
$Wt(P):=wt(v_1)+wt(v_2)+ \dots +wt(v_k)+wt(v_{k+1})$.
 
\noindent  
{\bf Definition:} The {\it weight} of a path
$P=v_1,e_1,v_2,e_2, \dots, v_i,e_i,v_{i+1}, \dots , v_k, e_k, v_{k+1}$,
in an Edge-Weighted Markov Process is:
$wt(e_1)+wt(e_2)+ \dots +wt(e_k)$.
 
Note that we could combine the two notions and put weight both
on vertices and edges, but this is unnecessary, since the weights
of the vertices can always be incorporated by modifying the
weights of the edges. Please be warned that, unlike [S], weights of
paths are additive, not multiplicative.

\noindent  
{\bf Example}: If $V=\{1,2,3\}$,
$E=\{[1,2]^{1},[1,2]^{2},[2,3],[3,1]^{1},[3,2]^{2}\}$, 
$Start=\{1,2\}$, $Finish=\{2,3\}$,
where
an edge $[i,j]^k$ goes from $i$ to $j$, and if,
$wt(1)=2$, $wt(2)=5$, $wt(3)=1$, then the
weight of the path 
$P=1,[1,2]^2,2,[2,3],3,[3,1]^2,1,[1,2]^1,2$
in this Vertex-Weighted Markov-Process is
$Wt(P)=wt(1)+wt(2)+wt(3)+wt(1)+wt(2)=2+5+1+2+5=15$.

\noindent  
{\bf Another Example:} Let $V$, $E$, $Start$, and $Finish$,
be as above, but let's make it into an Edge-Weighted Markov-Process
with the weight function defined by
$wt([1,2]^{1})=3,wt([1,2]^{2})=4,wt([2,3])=1,wt([3,1]^{1})=4,$
$wt([3,2]^{2})=2$, then the weight of the above path $P$ is
$Wt(P)=wt([1,2]^2)+wt([2,3])+wt([3,1]^2)+wt([1,2]^1)=4+1+2+3=10$.
 
Our goal is to compute the weight-enumerator (generating function)
$$
F(t) = \sum_P t^{Wt(P)} \,, 
$$
where the sum extends over the (usually infinite) set of
paths in the directed graph that start with a vertex of
$Start$ and ends with a vertex of $Finish$.
 
For any statement, [statement] equals $1$ if it is true,
$0$ if it is false.
 
Let's first consider the Vertex-Weighted Markov Process, and
assume that there are no multiple edges, i.e. there is at most
one edge between any two vertices. 
For any $v \in V$, 
let $F_v(t)$ be the sum of $t^{Wt(P)}$, over all
path $P$
that start with $v$ (even if $v$ is not a member of $Start$),
and that end with a vertex in $Finish$.
Let $Followers(v)$ be the set of vertices $v'$ 
connected to $v$ by a single edge.
We have
$$
F_v(t)= [v \in Finish] \cdot t^{wt(v)} + t^{wt(v)} \sum_{v' \in Followers(v)}
F_{v'}(t) \, .
\eqno(Eq1)
$$
 
This gives us a system of $\vert V \vert$ equations
for the $\vert V \vert $ unknowns $\{F_v(t) \, \vert \, v \in V\}$.
We are guaranteed that it has a solution since we know that
$F_v(t)$ exists as a formal power series.
Once we (or rather Maple, or rather the computer) solves this
system, we discard the $F_v(t)$ for which $v \not\in Start$, and
get the final result
$$
F(t)=\sum_{v \in Start} F_v(t) \,.
$$
 
If we have multiple edges then the system of equations $(Eq1)$
should be modified to read
$$
F_v(t)=  [v \in Finish] \cdot t^{wt(v)}+ t^{wt(v)} \sum_{v' \in Followers(v)}
a(v,v') F_{v'}(t) \quad ,
\eqno(Eq2)
$$
where $a(v,v')$ is the number of edges between $v$ and
$v'$.
 
For the Edge-Weighted Markov Process, we have the equation
$$
F_v(t)=  [v \in Finish ]+  \sum_{e, init(e)=v}
t^{wt(e)} F_{fin(e)}(t) \, .
\eqno(Eq3)
$$
\vskip 30pt
\line{\bf 6.2. Finding Series Expansions \hfil}
 
Even though the system of equations $(Eq1)$ can always be solved,
it often happens that the system is too big to be solved
by Maple. It is then still possible to find what physicists
call "series expansion" of the generating function $F(t)$,
i.e. the first $L$ terms of its power-series expansion:
$F(t)=a(0)+a(1)t+a(2)t^2+ \dots +a(L) t^L+ \dots $, where
$a(i)$ is the number of paths in the 
Combinatorial Markov Process 
whose weight equals $i$. Let $a_v(i)$ be the number of paths of
weight $i$ that start with the vertex $v$. Then
$$
a(i)=\sum_{v \in Start} a_v(i) \,.
$$
The system of linear 
equations $(Eq1)$, for Vertex-Weighted simple Markov Processes is
equivalent to the recurrences:
$$
a_v(i)= [wt(v)=i] \cdot [v \in Finish] + \sum_{v' \in Followers(v)}
a_v'(i-wt(v)) \, , \quad i \geq 0 , \quad
\eqno(Eq1')
$$
with the initial conditions $a_v(i)=0$, when $i<0$.
The  recurrence counterparts of $(Eq2)$ and $(Eq3)$ are similar.
 
\vskip 30pt 
\line{\bf 6.3. Maple Representation of Combinatorial Markov Processes \hfil}
 
In order to solve the system of equations $(Eq1)$, $(Eq2)$,
or $(Eq3)$ we really don't
need to know the `nature' of the edges, only how many they
are of any given weight. This leads to the notion of
{\it profile} of a Weighted Combinatorial Markov Process.
 
Let's call a vertex-weighted Combinatorial Markov Process,
with no multiple edges, 
a Markov Process of type I. Its {\it profile} is
a list of length four: 
$$[Start, Finish, ListOfOutgoingNeighbors, ListOfWeights].$$
The length of $ListOfOutgoingNeighbors$ is the number of
vertices, let's call it $N$. We assume that the vertices
are labelled $\{1,2, \dots, N \}$. $Start$ and $Finsih$ are
subsets of $\{1,2, \dots, N \}$. The $i^{th}$ component of
$ListOfOutgoingNeighbors$  ($i=1, \dots, N$) is the set
of vertices $j$ such that there is an edge between $i$ and $j$
(recall that right now we assume that there is at most one edge
between vertex $i$ and $j$, for $1 \leq i,j \leq N$).
Finally, $ListOfWeights$ is a list of length $N$ whose
$i^{th}$ component ($i=1, \dots , N$) is the weight of the vertex
labelled $i$.
 
For example
$$
MC1:=[\{1\},\{1\},[\{ 1 \} ],[1]] \, ,
$$
is a very simple example of the profile of a type I Markov Process.
It has one vertex, of weight $1$, and a single edge, 
going from that vertex to itself.
 
Let's call a vertex-weighted Combinatorial Markov Process,
{\it with} multiple edges, 
a Markov Process of type II. Its {\it profile} is
a list of length $4$,  
$$[Start, Finish, ListOfOutgoingNeighbors, ListOfWeights]$$.
The length of $ListOfOutgoingNeighbors$ is the number of
vertices, let's call it $N$. We assume that the vertices
are labelled $\{1,2, \dots, N \}$. $Start$ and $Finsih$ are
subsets of $\{1,2, \dots, N \}$. The $i^{th}$ entry of
$ListOfOutgoingNeighbors$  ($i=1, \dots, N$) is a {\it multiset}
$j_1^{m_1} j_2^{m_2} \dots  j_k^{m_k}$ represented in the form
$\{ [j_1,m_1], \dots , [j_k,m_k] \}$, which means that
out of the vertex labelled $i$ there are $m_1$ edges going to $j_1$,
$m_2$ edges going to $j_2$, etc.
Finally, $ListOfWeights$ is a list of length $N$ whose
$i^{th}$ component ($i=1, \dots , N$) is the weight of the vertex
labelled $i$.
 
For example the Markov Process represented by $MC1$ can also be
viewed as a type II Markov Process with profile:
$$
MC2:=[\{1\},\{1\},[\{ [1,1] \} ],[1]] \, .
$$
 
Let's call a simple edge-weighted Combinatorial Markov Process,
(i.e. without multiple edges),
a Markov Process of type III. Its {\it profile}, 
is a list of length 3,
$$[Start, Finish, WeightedListOfOutgoingNeighbors].$$
The length of the list $WeightedListOfOutgoingNeighbors$ is the number of
vertices, let's call it $N$. We assume that the vertices
are labelled $\{1,2, \dots, N \}$. $Start$ and $Finsih$ are
subsets of $\{1,2, \dots, N \}$. The $i^{th}$ component of
$WeightedListOfOutgoingNeighbors$  ($i=1, \dots, N$) is the set
of pairs $[j,wt_{i,j}]$ such that there is an edge between $i$ and
$j$ and $wt_{i,j}$ is the weight of the edge connecting
vertex $i$ to vertex $j$.
 
For example the Markov Process
$$
MC3:=[\{1\},\{1\},[\{ [1,1] \} ]] \, ,
$$
is a very simple example of the profile of a type III Markov Process.
It has one vertex and a single edge, 
of weight $1$, going from vertex $1$ to itself.
 
 
For a slightly bigger example consider:
$$
MC3a:=[\{1\},\{1,2\},[\{ [1,3],[2,4] \},
\{ [1,2],[2,8] \} ]] \, ,
$$
Here the underlying digraph has two vertices
labelled $1$ and $2$. A path
must start at the vertex $1$, but may end at either $1$ or $2$.
Out of $1$ there is one edge, of weight $3$ going into itself,
and an edge, of weights $4$ going into $2$.
Out of $2$ there an edge, of weight $2$, going to $1$, and
an edge, of weight $8$, going back to $2$.
 
Let's call an edge-weighted Combinatorial Markov Process,
with possibly multiple edges,
a Markov Process of type IV. Its {\it profile}, w.r.t. the variable
$t$, is a list of length three, \hfill\break
$[Start, Finish, WeightedListOfOutgoingNeighbors]$.
 
The length of $WeightedListOfOutgoingNeighbors$ is the number of
vertices, let's call it $N$. We assume that the vertices
are labelled $\{1,2, \dots, N \}$. $Start$ and $Finsih$ are
subsets of $\{1,2, \dots, N \}$. The $i^{th}$ component of
$WeightedListOfOutgoingNeighbors$  ($i=1, \dots, N$) is the set
of pairs $[j,poly_{i,j} (t)]$ such that there is at least one
edge between $i$ and $j$, and $poly_{i,j}(t)$ is the weight-enumerator of
the set of edges that go from $i$ to $j$, i.e. the coeff. of $t^k$
in $poly_{i,j}(t)$ is the number of edges from $i$ to $j$ that
have weight $k$.
 
For example the Markov Process
$$
MC4:=[\{1\},\{1\},[\{ [1,t] \} ]] \,,
$$
is a very simple example of the profile of a type IV Markov Process.
It has one vertex and a single edge, 
of weight $1$, going from that vertex to itself.
 
 
For a slightly bigger example consider:
$$
MC4a:=[\{1\},\{1,2\},[\{ [1,t],[2,t^2+t^3] \},
\{ [1,t^2],[2,3t^5+2t^7] \} ]] \, ,
$$
Here the underlying digraph has two vertices
labelled $1$ and $2$. A path
must start at the vertex $1$, but may end at either $1$ or $2$.
Out of $1$ there is one edge, of weight $1$ going into itself,
and two edges, of weights $2$ and $3$ going into $2$.
Out of $2$ there is one edge, of weight $2$, going to $1$, and
five edges, three of weight $5$ and two of weight $7$, going back
to $2$.
 
The Maple package {\tt MARKOV} computers the generating functions
that weight-enumerate paths in Combinatorial Markov Processes of
types I-IV.
\eject
\vskip 30pt 
\line{\bf 6.4. A User's Manual for MARKOV \hfil}
 
First you should go to my website, and download {\tt MARKOV}.
Assuming that you are still in the same directory, go into
Maple by typing: {\tt maple} (or {\tt xmaple}), 
followed by {\tt Enter}, or click on the Maple icon.
 
Once in Maple, type: {\tt read MARKOV;} ,
and follow
the instructions given there. The main procedures are
{\tt SolveMC1}, {\tt SolveMC2}, {\tt SolveMC3}, {\tt SolveMC4}, that
find the generating functions weight-enumerating paths
in Combinatorial Markov Processes of type I, II, III, and IV
respectively.
 
For example, for the Markov Processes above, do 
{\tt SolveMC1(MC1,t);}, {\tt SolveMC2(MC2,t);},
{\tt SolveMC3(MC3,t);}, {\tt SolveMC4(MC4,t);}, 
to get, in all cases, $-t/(t-1)$.
 
If the input Markov Processes are too big for {\tt SolveMC1} and
its siblings to handle, try 
{\tt SolveMC1series}, etc. to
find the first $L$ (for a specified $L$) terms of the power-series
expansion of the corresponding generating function. For example
{\tt SolveMC1series(MC1,10);}
should output $[1,1,1,1,1,1,1,1,1,1]$.

\vskip 30pt 
\line{{\bf 6.5. A Brief Explanation of the Nuts and Bolts of } {\tt MARKOV}
\hfil}
 
We will only describe {\tt SolveMC1}, since the other procedures
are straightforward modifications. Please refer to the
source code of the package {\tt Markov}.
 
{\tt SolveMC1(MC,s)} inputs MC, the profile of a type I Markov Process,
and a variable {\tt s}. First the program checks that {\tt s} is indeed
a variable, and {\tt MC} is indeed a legal type I Markov Process,
using the procedure {\tt KosherMC1}.
 
The line
``{\tt LL:=MC[1]:RL:=MC[2]:Nei:=MC[3]:Wts:=MC[4]:} "
unpacks, MC. {\tt LL} is the set vertices that we call $Start$,
{\tt RL} is the set of vertices $Finish$, $Nei$ is the list of neighbor-sets
and {\tt Wts} is the list of weights. The line ``{\tt N:=nops(Wts):}''
finds the number of vertices. {\tt eq} and {\tt var} are the
set of equations and variables, respectively, that are initialized
to the empty set. We use the indexed variable {\tt A[i]} for
what we called above $F_v$, i.e. for the weight-enumerator of paths
that start at the vertex labelled {\tt i}.
 
The program now do-loops over {\tt i} from {\tt 1} to {\tt N},
adding, one at a time, {\tt A[i]} to {\tt var} and constructing
{\tt eq1} the equation representing paths that start at the vertex
labelled {\tt i}. If {\tt i} is a member of {\tt RL} (i.e. it belongs
to $Finish$, i.e. the length-$0$ path that starts and ends at $i$ and
has no edges, is to be counted), then {\tt eq1} is initialized to be
{\tt s**(Wt[i]) }, the weight of this trivial path.
{\tt Sakh} is {\tt Nei[i]}, the set of neighbors of the vertex {\tt i}.
The inner do-loop, w.r.t {\tt j}, sums {\tt A[Sakh[j]]}, over all
outgoing neighbors , {\tt Sakh[j]} of {\tt i}. We call the result
{\tt lu}. Then the current equation, {\tt eq1}, is updated
in the next line: {\tt eq1:=eq1-s**Wts[i]*lu:}, and the new equation,
{\tt eq1}, that considers all paths that start at vertex {\tt i},
is added to the set of equations, {\tt eq} with the command:
``{\tt eq:=eq union $\{$eq1$\}$:}''. Exiting the {\tt i} do-loop, equipped
with the set of linear equations, {\tt eq}, and the set of unknowns,
{\tt var}, we ask Maple to solve the system with the line:
``{\tt var:=solve(eq,var):}". The last do-loop, w.r.t. {\tt i},
sums the solved values for the weight-enumerators of paths that
start at one of the allowed starting points, the members of $Start$,
that is called {\tt LL} in this program. The very last line
normalizes the answer.

\vskip 30pt 
\line{\bf 7.1.  Counting Lattice Animals Confined to a Strip \hfil}
 
A (2D site) {\it lattice-animal} (alias fixed polyomino,
henceforth animal) is a connected set 
of lattice points in the square lattice $Z^2$. 

Two animals are equivalent if they are translations of each other.
The problem is to find $a(n)$, the number of equivalence classes
(under translation) of animals with $n$ cells. 
For example $a(1)=1$, $a(2)=2$, $a(3)=6$, $a(4)=19$ etc.
To date (see Steve Finch's superb website [F]) $a(n)$ is known
for $n\leq 28$. It is probably hopeless to look for
a `closed-form' formula, or even for a polynomial-time
algorithm for computing $a(n)$, so, one should be content,
at present, with counting interesting subsets and supersets,
that yield as a bonus,  lower and upper bounds, for
the so-called {\it Klarner} constant:
$\mu:=\lim_{n \rightarrow \infty} a(n)^{1/n}$. 
Klarner ([K1], see also [K2])  proved the existence of his constant
and that $\mu>3.72$. With Rivest ([KR]) he proved that
$\mu<4.65$.
 
It was Read [R] who first proposed to use the transfer-matrix
method to enumerate animals confined to a strip of width $k$.
This was nicely implemented by Mikovsky [M]. Here we
will use a different data structure, which logically is
equivalent, but that would be amenable to the generalization
that I hope to present in [Z2]. 
 
For a given integer $k$,
consider all animals $S=\{(x,y)\}$, with the restriction that
for each $(x,y) \in S$, $x \geq 0$, $0 \leq y < k$, and
$\min \{x \, \vert \, (x,y) \in S \}=0$.
We can look, for $x=0,1, \dots $,
at the set of corresponding $y$ coordinates with the specified
$x$ for which $(x,y) \in S$. 
This yields  a word in the alphabet consisting of the
non-empty subsets of $\{0,1, \dots , k-1\}$. For example
the animal 
$$
\{(0,1),(0,2),(0,4),
(1,0),(1,2),(1,4),(1,5),
(2,0),(2,2),(2,3),(2,4),
(3,0),(3,1),(3,2)
\}
$$
can be coded as the word
$$
\{1,2,4\},
\{0,2,4,5\},
\{0,2,3,4\},
\{0,1,2\} \,.
$$
While this is an injection into the set of words in the
alphabet  whose letters are the $2^{k}-1$ non-empty
subsets of $\{0,\dots,k-1\}$, it is impossible to construct
a reasonable (type-3) `grammar' describing this language. 
Following Read[R], we need a larger alphabet.
 
For an animal $S$, and for
an integer $i=0,1,2, \dots$, consider the subset of $S$,
$S_i$, obtained by only retaining the points of $S$ with
$x \leq i$:
$$
S_i :=\{(x,y) \in S \,\, \vert \,\,  x\leq i \} 
$$
For example, for the animal above,
$$
S_0=\{(0,1),(0,2),(0,4)\} \, ,\quad
S_1=\{(0,1),(0,2),(0,4),(1,0),(1,2),(1,4),(1,5)\} \, ,
$$
$$
S_2=\{(0,1),(0,2),(0,4),(1,0),(1,2),(1,4),(1,5),(2,0),(2,2),(2,3),(2,4)
\} \, , {\rm and}
$$

\line{$S_3=$ \hfil}

\noindent
$S \, \;  = 
\{(0,1),(0,2),(0,4),(1,0),(1,2),(1,4),(1,5),(2,0),(2,2),(2,3),(2,4),(3,0),(3,1),(3,2)
\} \, .
$

Note that the $S_i$ do not have to be animals, since removing the
points with $x>i$ may disconnect the animal $S$.
For each vertical cross section $x=i$, the points
of $S$ for which $x=i$ can be partitioned into
equivalence classes according to whether or not
they belong to the same component of $S_i$.
So the natural alphabet is not just subsets of
$\{0,1, \dots, k-1 \}$ but certain set-partitions.
According to this coding, the animal $S$ is coded as
the `word':
$$
\{ \{1,2\}, \{4\}\},
\{\{0\},\{2\},\{4,5\} \},
\{\{0\},\{2,3,4\} \},
\{\{0,1,2\} \} \,.
$$
It is easy to see that not all set-partitions show up.
First, if $(i,j)$ and $(i,j+1)$ both belong to $S$ then
they must belong to the same component. Hence it is more
beneficial, both conceptually and computationally, to
abbreviate the set 
of $j-i+1$ consecutive integers $\{i, i+1, i+2 , \dots , j-1 , j \}$,
by the "interval-notation": $[i,j]$. So from now on
we will denote sets of integers as unions of such closed intervals.
For example the set $\{1,2,3,5,7,8,9,11,12,13,17,19,20,22\}$
will be denoted by $\{[1,3],[5,5],[7,9],[11,13],[17,17],[19,20],[22,22]\}$.
Because of the observation above, the kind of set-partitions that
arise from lattice animals (in which all the members of a closed interval
must belong to the same component), can be written as set-partitions
of intervals. For example, in the new notation the animal $S$ above
is coded as the word:
$$
\{ \{[1,2]\}, \{[4,4]\}\},
\{\{[0,0]\},\{[2,2]\},\{[4,5]\} \},
\{\{[0,0]\},\{[2,4]\} \},
\{\{[0,2]\} \} \,.
$$
 
It is easy to see that the set-partitions that show up as letters
coding lattice animals by the above process are all {\it non-crossing},
but this fact is not needed, since the computer can always find the
complete alphabet, once it knows the "left-alphabet", i.e. the
letters that may be starters, and how to compute the {\it followers} of
a letter. So the next task is to decide who is eligible to
be a first (i.e. leftmost) letter, in an animal word.
Two intervals $[a,b]$ and $[c,d]$ belong to 
the same block in the set-partition that constitutes the $(i+1)^{th}$ letter
of an animal-word,
if and only in the animal it came from,
the set of lattice points $\{(i,a), (i,a+1), \dots, (i,b)\}$
is "connected from the left" to the set of latticed points
$\{(i,c), (i,c+1), \dots, (i,d)\}$.
In other words,
belong to the same component in the set obtained from the original
animal by only retaining the points with $x \leq i$.
When $i=0$, then there is nothing to the left, and hence
the left-letters must be set-partitions of intervals each of whose
blocks are singletons. For example
when $k=1$ there is only one left-letter,
$\{\{[0,0]\}\}$ . When $k=2$ then we have the three
letters$\{\{[0,0]\}\},\{\{[1,1]\}\},\{\{[0,1]\}\}$.
When $k=3$ then we have the seven
letters $\{\{[0,0]\}\},\{\{[1,1]\}\},\{\{[0,1]\}\},
\{\{[0,2]\}\},\{\{[1,2]\}\},\{\{[2,2]\}\},
\{\{[0,0]\}, \{[2,2]\}\}$.
 
In general there are $2^{k}-1$ left-letters corresponding to all
non-empty subsets of $\{0, \dots, k-1 \}$, written
in interval notation, in which each participating
interval forms its own singleton block in the set-partition.
 
What animal-letters can be the last (rightmost) letter?
Obviously, all the intervals in the rightmost cross-section
must belong to the same component, since there are no points
to the right to help them out. Hence the rightmost letters
consist of set-partitions 
consisting of one block. Their number again is $2^k-1$.
For example
when $k=1$ there is only one right-letter,
$\{\{[0,0]\}\}$ . When $k=2$ then we have the three
letters$\{\{[0,0]\}\},\{\{[1,1]\}\},\{\{[0,1]\}\}$.
When $k=3$ then we have the seven
letters $\{\{[0,0]\}\},\{\{[1,1]\}\},\{\{[0,1]\}\},
\{\{[0,2]\}\},\{\{[1,2]\}\},\{\{[2,2]\}\},$ $
\{\{[0,0],[2,2]\}\}.$
 
Given a letter in the animal-alphabet, who can follow it?
Let's call a {\it pre-letter} any non-empty subset of $\{0,1, \dots, k-1 \}$,
written in interval notation. Of course there are $2^k-1$ pre-letters.
As we saw above, the set-partitions all of whose blocks are
singletons correspond to leftmost letters,
and the set-partitions having exactly one block
correspond to rightmost letters.
So we must now answer the question: What pre-letters can follow
a given letter?
 
Since the partial animals (obtained by only retaining the points to
the left of the considered vertical-cross section) must be all
"connected from the right", we must make sure that each of
the components of the letter has non-empty intersection with
the pre-letter that comes right after it.
For example, after the letter
$$
\{ \{[0,1],[3,3]\},  
\{[5,8], [15,18], [21,24] \},
\{ [10,13] \} \},
$$
the pre-letter $\{ [4,8], [10,26] \}$ may {\it not} follow since
the component $\{[0,1],[3,3]\}$ has nothing to hang on to.
Also the pre-letter $\{ [0,4], [11,14],[19,20] \}$ may {\it not}
follow, since now the component $\{[5,8], [15,18], [21,24] \}$
does not intersect this pre-letter. On the other hand the pre-letter
$\{[1,1], [12,12], [22,22]\}$ may follow, since each of the three components
gets touched.
 
Once we have a letter, and a legitimate pre-letter follower,
the pre-letter becomes a letter in a unique way. Indeed,
given a letter, and a pre-letter following it, define
an (undirected) graph whose vertices are the intervals
of the pre-letter and where there is an edge between
two such intervals if they both touch the same component.
The set-partition induced from the connected components
of this graph is the desired follow-up letter.
For example, the pre-letter
$\{[2,6],[12,16],[24,24]\} $
following the letter 
$
\{ \{[0,1],[3,3]\},  
\{[5,8], [15,18], [21,24] \},
\{ [10,13] \} \},
$
becomes $\{\{[2,6],[12,16],[24,24]\}\}$.
 
Now that we know how to find all the followers of any letter,
we can dynamically construct the table of followers of each
letter that shows up, and at the same time keep track of our
current set of letters, and keep going until there are no
new letters encountered. This is accomplished by our Maple
package {\tt ANIMALS} described below.
 
\vskip 30pt
\line{\bf 7.2. A User's Manual for ANIMALS \hfil}
 
First download {\tt ANIMALS} to your directory
(either directly from INTEGERS or from my website).
Then go into Maple by typing: {\tt maple} 
(or, if you prefer, {\tt xmaple})
followed by
{\tt Enter},  or click on
the Maple icon. Then, once in Maple, type:
{\tt read ANIMALS;}, assuming you are still in the
same directory, or, e.g.  {\tt read `research/animals/ANIMALS` ;}
(i.e. the full path-name of the file {\tt ANIMAL})
if you are not.)
Then follow the on-line help.
To see the names of the main procedures type: {\tt ezra();} .
To get help on a specific procedure type {\tt ezra(ProcName); }.
For example, to get help on {\tt GF} type {\tt ezra(GF); }.
 
To find the generating function that enumerates
animals of width $\leq 3$, type {\tt GF(3,s);} .
To get 
the number of animals with $n$ cells, for $1 \leq n \leq L$,
type $Khaya(L)$. I was able to get $Khaya(18)$, but
$Khaya(20)$ took too long.
 
\vskip 30pt
\line{{\bf 7.3. A Brief Explanation of the Nuts and Bolts of} {\tt ANIMALS}
\hfil}
 
The procedure {\tt LeftLetters(a,b)} outputs all
set-partitions of $\{a,a+1, \dots, b \}$ (written in interval
notation, see above) with one interval per block.
The procedure {\tt Followers(n,LETTER)} finds all the possible followers
of the letter {\tt LETTER}, in 
the alphabet of animals confined to the strip $0 \leq y \leq n-1$.
It does that by testing each of the preletters (obtained
from procedure {\tt PreLeftLetters} by calling
{\tt PreLeftLetters(0,n-1)}). If every component of {\tt LETTER}
is touched by the tested pre-letter, {\tt mu1}, it is approved, and
it is made into a letter by procedure {\tt PreLetToLet},
by the call {\tt PreLetToLet(Let1,mu1)}.
 
Procedure {\tt PreLetToLet(Letter,PreLetter)} inputs 
a letter {\tt Letter} (a set-partition of intervals)
and a pre-letter {\tt PreLetter} (a set of intervals) and
decides how to turn {\tt PreLetter} into a letter.
It defines two tables {\tt T} and {\tt S}, defined
on the blocks of the set-partition {\tt Letter} and the
members of the set {\tt PreLetter} respectively.
At the end of the do-loop {\tt T[block] }
is the set of members of {\tt PreLetter} touching the block {\tt block},
and {\tt S[member] } is the set of blocks of
{\tt Letter} touching the given {\tt member} of {\tt PreLetter}.
 
If any of the {\tt T[component]} is empty then
{\tt PreLetter} is rejected by returning {\tt 0}.
Otherwise, we construct a graph {\tt G} whose vertex-set
is the set of members of {\tt PreLetter}. The graph
is given in terms of an adjacency table and the last
double do-loop constructs the graph where {\tt interval1}
is adjacent to {\tt interval2} if they both touch
at least one of the components of {\tt Letter}, i.e. if
{\tt S[interval1] intersect S[interval2]} is non-empty.
Finally a call to the procedure {\tt Comp},
{\tt Comp(G,PreLetter)}, gives the induced set-partition
of the set of intervals {\tt PreLetter}, by partitioning
it according to the connected components of the graph {\tt G}.
The procedure {\tt Support} simply finds the support of
a letter, for example {\tt Support}($\{ \{[0,2], [4,5]\},\{ [7,7] \} \}$)
should yield  $\{ 0,1,2,4,5,7\}$.
 
Procedure {\tt FollowersS} takes as input a set of letters,
and outputs the union of all the followers. Procedure
{\tt Alphabet(n)}, starting with {\tt LeftLetters(0,n-1)},
applies {\tt FollowersS} iteratively
until we get all letters. Since {\tt Followers} is with
{\tt option remember}, by the time {\tt Alphabet(n)} is
finished, Maple already knows all the followers of all the letters.
 
Procedure {\tt MarCha(n)} constructs the profile of the
type I Markov Process describing 
the animals confined to the strip $0 \leq y \leq n-1$,
in canonical, compact form. First a call to {\tt Alphabet},
{\tt gu:=Alphabet(n); } , gets the alphabet. By this
time Maple already knows all the followers, but in terms of
their long-winded set-partition names. To compactify it,
the letters are given integer names from {\tt 1} to
{\tt N:=nops(gu)}, and the table {\tt T} remembers the
new names. Then the set of left-letters, {\tt Left0}
is found, and {\tt Left1} and {\tt Right1} become the
set of left-letters and right-letters using the new,
abbreviated names. The list {\tt mu} is the list of lists
where the $i^{th}$ term is the set of followers,
using their new, abbreviated names, of
the letter whose abbreviated name is $i$.
Finally {\tt Wts} is the table of weights of the letters.
The output is the type I Markov Process profile
{\tt [Left1,Right1,mu,Wts]}.
 
Procedure {\tt gf(n,s)} uses {\tt SolveMC1} to
find the generating function for all animals that live
in the strip $0 \leq y \leq n-1$, but what we are really
interested in is the generating function for all animals
of width $\leq n$, since, {\tt gf} counts, for example both 
the animal $\{ (0,0) \}$ and the animal $\{ (0,1) \}$
as distinct entities, even though they are equivalent.
This is achieved by {\tt GF(n,s)} which is simply
{\tt gf(n,s)-gf(n-1,s)}.
 
If you are interested in the generating function
for animals with width {\it exactly } $n$, then
use {\tt Gf(n,s);}, which is {\tt GF(n,s)-GF(n-1,s)}.
 
Once $n\geq 6$, it takes too long, at least for Shalosh,
to compute {\tt GF(n,s)} exactly, but one can go much
further with {\tt GFseries(n,L)}  which uses
{\tt SolveMC1series} to find the series expansion
up to $L$ terms.
{\tt GfseriesS(n,L,s)} uses {\tt SolveMC1seriesS} to find
the series-expansion where we also keep track of
the length of the animal (alias the number of letters
in the animal word). In particular the
coefficient of $x^i$ in the $L^{th}$
entry of {\tt GfseriesS(n,L,x)}, let's call it
$A(L,n,i)$, is the
number of animals with $L$ cells, 
of width {\it exactly} $n$, and
length {\it exactly } $i$. 
Since width+length$\leq L$, by symmetry the total number
of animals with $L$ cells equals 
$A(L,L/2,L/2) [ k \equiv 0 \,\, mod \,\, 2]$ 
plus twice the sum of $A(L,n,i)$ with $n<i\leq L/2$.
This is how {\tt Khaya(L)}
computes the first $L$ terms of
the notorious animal-series. {\tt Khaya(18)} is fairly
fast, but {\tt Khaya(20)} already takes too long.
 
\vskip 30pt
\line{\bf 8.1. More Animals For Less Money: Counting 
Locally-Skinny Animals \hfil}
 
The Maple package {\tt ANIMALS} counted animals that are
{\it globally} skinny, i.e. the whole animal can be
fitted in a {\it fixed} strip.
Let's define, for $x=0,1, \dots$
$$
M(x):=max \{ y \vert (x,y) \in S\} \, , \quad
m(x):=min \{ y \vert (x,y) \in S\} \, .
$$
 
The package {\tt ANIMALS} described above counts, for a given
$n$, the number of
animals such that $max_x (M(x)) - min_x m(x) \leq n-1$.
 
By contrast, the Maple package
{\tt FreeANIMALS}, to be described in this
section, counts the much larger subset of animals
such that $M(x)-m(x) \leq n-1$ for {\it each} $x$.
For example the `staircase' animal:
$\{ (0,0),(0,1),(1,1),(1,2),(2,2),(2,3),(3,3),(3,4) , (n-1,n-1),(n-1,n) 
\dots \}$ is not counted by {\tt GF(n,s)} of {\tt ANIMALS},
but is already counted by {\tt GF(2,s)} of {\tt FreeANIMALS},
since each vertical cross-section, individually, had width $\leq 2$.
 
The modification is straightforward. Now we have a normalized
alphabet, where the lowest member must be $0$. So we have
half as many left-letters for a given $n$. 
Unlike the previous case, however, given a letter
of width $a$, say, and a pre-letter of width $b$
following it, the bottom of the pre-letter is placed, in turn
at $y=-(b-1),-(b-2), \dots, 0, \dots , a-1$, and for each
of these vertical translates we determine whether it is
a legal interface, and if yes, what is the corresponding letter.
For each of these resulting letters, we normalize them
so that the bottom is $0$. So now, in general, every letter
has a {\it multi-set} of followers, and we have to use
the Type II Markov Process Model.
 
\noindent
{\bf Example}: Consider the letter $\{\{ [0,0] \}, \{ [2,2] \} \}$,
and the pre-letter $\{[0,3]\}$. The translates
$\{[-3,0]\}$,$\{[-2,1]\}$,
$\{[1,4]\}$,$\{[2,5]\}$,
do not produce bona-fide followers,
while $\{[-1,2]\}$, $\{[0,3]\}$ do both give rise to the
letter $\{\{[0,3]\}\}$. Hence in the digraph of this Markov
Process, we have two edges between
$\{\{ [0,0] \}, \{ [2,2] \} \}$ and
$\{\{[0,3]\}\}$.  On the other hand there are six edges between
$\{\{ [0,0] , [2,2] \} \}$
and $\{\{[0,3]\}\}$, since all the translates
$\{[-3,0]\}$,$\{[-2,1]\}$,$\{[-1,2]\}$,$\{[0,3]\}$, $\{[1,4]\}$,
$\{[2,5]\}$, are legal followings and all of them normalize to
$\{\{[0,3]\}\}$. In general the followers that result from
all the vertical translates of a pre-letter do not have to be the same.
 
\vskip 30pt
\line{\bf 8.2. A User's Manual for the Maple Package {\tt FreeANIMALS} \hfil}
 
The main procedures are: {\tt gf, gfSeries, gfList, gfSeriesList }.
 
For a positive integer $n$, and a variable $s$, typing {\tt gf(n,s);}
would give
the generating function
$$
f_n(s):=\sum_{i=1}^{\infty} a_n(i) s^i \, ,
$$
where $a_n(i)$ is the number of (2D site) animals such that
for each vertical cross-section $x=x_0$ the difference between
the biggest $y$ such that $(x_0,y)$ belongs to the
animal and the smallest such $y$ is $\leq n-1$.
 
{\tt gf(n,s)} works, on my computer, up to $n=6$.
Beyond that, you may wish to use 
{\tt gfSeries(n,L)}, where $L$ is also a positive integer,
in order to get the first $L$ coefficients of $f_n(s)$.
 
Both {\tt gf(n,s)} and {\tt gfSeries(n,L)} enumerate
animals where each vertical cross-section has width $\leq n$.
But we may want to consider more general sets of animals.
Suppose that whenever the "letter" (i.e. vertical cross-section)
has $i$ boards, then it is allowed to have width $\leq R_i$,
for a list $[R_1,R_2, \dots, R_m]$, say. The corresponding
generating functions are given by typing
{\tt gfList(List,s);} and {\tt gfSeriesList(List,s);}.
For example {\tt gfList([5,3],s);} would give
the generating function for animals whose vertical cross-sections
with one interval (board) have width $\leq 5$ and vertical cross-sections
with two intervals have width $\leq 3$, or equivalently, the
"free animal-language" that only uses the letters
$\{\{[0,1]\}\},\{\{[0,2]\}\},\{\{[0,3]\}\},\{\{[0,4]\}\},$
$\{\{[0,0],[2,2]\}\},\{\{[0,0]\},\{[2,2]\}\}$.
 

\vskip 30pt 
\line{{\bf 8.3. A Brief Explanation of the Nuts and Bolts of} {\tt
FreeANIMALS} \hfil}
 
Now {\tt Alphabet(n);} gives the smaller set of
normalized letters, where the smallest integer is always $0$.
{\tt MarCha(n) } gives the Markov Process for the language of
the kind of animals considered here, but unlike
{\tt ANIMALS} it is what we called a Markov Process of type II,
i.e. the underlying graph is still vertex-weighted, but
multiple edges are allowed. Consequently, 
{\tt Followers(n,Letter)} does not return a set but a list
(that allows duplication).
Procedure {\tt ListToMultiSet} simply converts from list to
a mutliset. For example {\tt ListToMultiSet([1,2,2,1,2,1,1]);}
yields $\{[1,4],[2,3] \}$, since $1$ shows up $4$ times and
$2$ shows up $3$ times.
 
\vskip 30pt 
\line{\bf 9.1. Counting Skinny Self-Avoiding Polygons \hfil}
 
We will only consider the two-dimensional square-lattice,
but the approach can be adapted to other plane lattices,
and somewhat less obviously, to higher dimensions.
 
In the sequel we will use lower-case: {\it vertices} and {\it edges},
to talk about vertices and edges that live in the two-dimensional
square-lattice, i.e. the natural habitat where self avoiding polygons
roam. We will use Capitals: {\it Vertices} and {\it Edges} to talk
about vertices and edges in the type III Markov Process describing the
structure of these self-avoiding-polygons.
 
A (vertex)
lattice point will be denoted by an (ordered) pair of integers, $[m,n]$,
and, somewhat cumbersomely, but convenient for the computer implementation,
an edge will be denoted by the (unordered) pair consisting of its end-points.
For example the horizontal edge that joins $[4,5]$ and $[5,5]$
will be denoted by $\{ [4,5], [5,5] \}$.
 
A {\it self-avoiding polygon} ( henceforth sap) in a lattice, is a simple 
closed "curve" in the lattice.  Equivalently,
a sap is a set of edges of the square-lattice such that, in the
induced graph, every vertex had degree exactly two, i.e. every
vertex is adjacent to exactly two edges. We are interested in
the sequence $a(n):=$ the number of saps with $2n$ edges, up
to translation equivalence. For example 
$$
\{ \{[0,0],[1,0]\}, \{[1,0],[1,1]\}, \{[1,1],[0,1]\}, \{[0,1],[0,0]\} \}
$$
is the only (up to trivial translation-equivalence) sap with
$4$ edges, while
$$
\{ \{[0,0],[1,0]\}, \{[1,0],[2,0]\}, \{[2,0],[2,1]\}, \{[2,1],[1,1]\} ,
\{[1,1],[1,0]\} ,\{[1,0],[0,0]\} \}
$$
and
$$
\{ \{[0,0],[1,0]\}, \{[1,0],[1,1]\}, \{[1,1],[1,2]\}, \{[1,2],[0,2]\} ,
\{[0,2],[0,1]\} ,\{[0,1],[0,0]\} \}
$$
are the only saps with $6$ edges.
 
Let $vert(S)$ denote the set of vertices (lattice-points) that
participate in a the sap $S$. For example
$$
vert(
\{ \{[0,0],[1,0]\}, \{[1,0],[1,1]\}, \{[1,1],[0,1]\}, \{[0,1],[0,0]\} \})=
\{[0,0],[1,0],[0,1],[1,1]\}
$$
 
Let's standardize, and take, from each translation-equivalence class,
the unique sap $S$, such that $\min_x \{ (x,y) \in S\}=0$  and
$\min_y \{ (x,y) \in S\}=0$. In other words we place it such that
its "left-most walls" lie on the $y$-axis and its "bottom floors"
lie on the $x$-axis.
 
For any integer $K$, we would like to find the generating function
$$
f_K(s):=\sum_{n=0}^{\infty} a_K(n) s^{2n} \,,
$$
where $a_K(n)$ is the number of "skinny" saps with $2n$ edges,
i.e. standardized saps such that
$\max_y \{ (x,y) \in vert(S) \}\leq K$.
 
It is possible to code any (standardized) sap $S$, as a "word" in its
vertical cross-sections, i.e. for $k=1,2, \dots$, write it
as $A_0 A_1 A_2 \dots$, where the $k^{th}$ letter is the subset of
the horizontal edges of the sap that form $\{[k-1,y],[k,y]\}$.
Since $k$ is predetermined, it is enough to list it as a word
in the alphabet consisting  of the non-empty subsets of
$\{ 0,1, \dots , K \}$. Also the vertical edges are implied,
even though the "letters" only list the horizontal edges.
However, it is impossible to describe
a reasonable "grammar", definitely not a type-3, Markovian one,
on the language obtained from all skinny saps.
Hence, just as with animals, we have to extend the alphabet to
contain more information.
 
Looking at the vertical cross-section obtained by intersecting the sap
with $\{ k-1 \leq x \leq k \}$, i.e. at the above set of horizontal
edges, lets's call it $H_k$,
$H_k:=\{\{[k-1,y],[k,y]\}\}$, we see that every member of $H_k$
has a unique "mate", within $H_k$, such that it is possible
to walk counter-clockwise, from the lower one to the upper one,
along the sap, such that all the intermediate vertices are to
the left of the vertical line $y=k-1$. It is also obvious, on
geometrical grounds (the discrete Jordan Curve Theorem), that
these pairings form a {\it legal bracketing}. Thus the size
of the alphabet is
$$
\sum_{i=1}^{[(K+1)/2]}  {{K+1} \choose {2i} } C_i \,,
$$
where $C_i:={{2i} \choose {i} }/(i+1)$ are the Catalan numbers.
 
We will describe legal bracketings by using the letters $L$ and $R$,
to denote ``left bracket'' and ``right bracket'' respectively.
The only legal bracketing of length
$2$ is $[L,R]$. The two legal bracketings of length $4$ are
$[L,R,L,R]$ and $[L,L,R,R]$, etc. 
Recall that the set of legal bracketing
consists of
the empty word and all words in the alphabet $\{L,R\}$,
that may be written as $Lw_1Rw_2$, where $w_1$, $w_2$ are shorter
legal bracketings.
 
A typical, say, $k^{th}$ "letter", in the sap-alphabet consists of
a pair of lists of the same length, that length being
an even integer. The second list is the increasing sequence
of integers $[i_1, \dots, i_{2r}]$ indicating which horizontal
edges join the vertical lines $x=k-1$ and $x=k$, i.e. the edges
$\{[k-1,i_1],[k,i_1]\},\{[k-1,i_2],[k,i_2]\}, \dots ,$ 
$\{[k-1,i_{2r}],[k,i_{2r}]\}$.
The first list is the corresponding legal-bracketing, indicating
the pairing according to "accessibility from the left".
So if $i_n$ is an "L", and its $R$-mate is $i_m$, then it is possible
to walk along the sap, between  edge $\{[k-1,i_n],[k,i_n]\}$
and $\{[k-1,i_m],[k,i_m]\}$, without ever venturing to the right of
the vertical line $x=k-1$.
 
For example, the alphabet for saps confined to the horizontal strip
$0 \leq y \leq 4$, (i.e. $K=4$ above), consists of the following
${ {5} \choose {2}} C_1 + { {5} \choose {4}} C_2=20$ letters:
$$
   \{[[L, R], [0, 1]], [[L, R], [0, 2]], [[L, R], [1, 2]], [[L, R], [0, 3]],
       [[L, R], [2, 3]], [[L, R], [1, 3]], 
$$
$$
[[L, R, L, R], [0, 1, 2, 3]],
       [[L, L, R, R], [0, 1, 2, 3]], [[L, R, L, R], [0, 1, 2, 4]],
$$
$$
       [[L, R, L, R], [0, 1, 3, 4]], [[L, R, L, R], [0, 2, 3, 4]],
       [[L, R, L, R], [1, 2, 3, 4]], [[L, L, R, R], [0, 1, 2, 4]],
$$
$$
       [[L, L, R, R], [0, 1, 3, 4]], [[L, L, R, R], [0, 2, 3, 4]],
       [[L, L, R, R], [1, 2, 3, 4]], [[L, R], [0, 4]], 
$$
$$
       [[L, R], [2, 4]], [[L, R], [3, 4]], [[L, R], [1, 4]]\} \,.
$$
 
 
The leftmost letters, in a sap-word are not arbitrary, but necessarily
must have its first list be of the form $[(L,R)^r]$, for 
$r=1, \dots, [{(K+1)/2]}$. Hence there are exactly
$$
\sum_{i=1}^{[(K+1)/2]}  {{K+1} \choose {2i} } \,,
$$
letters that may be starters.
 
For example amongst the $20$ letters above
only the following
${ {5} \choose {2}} \cdot 1 + { {5} \choose {4}} \cdot 1 =15$ 
may start a sap word:
$$
   \{[[L, R], [0, 1]], [[L, R], [0, 2]], [[L, R], [1, 2]], [[L, R], [0, 3]],
       [[L, R], [2, 3]], [[L, R], [1, 3]], 
$$
$$
[[L, R, L, R], [0, 1, 2, 3]],
[[L, R, L, R], [0, 1, 2, 4]],
$$
$$
       [[L, R, L, R], [0, 1, 3, 4]], [[L, R, L, R], [0, 2, 3, 4]],
       [[L, R, L, R], [1, 2, 3, 4]], 
$$
$$
       [[L, R], [0, 4]], [[L, R], [2, 4]],
       [[L, R], [3, 4]], [[L, R], [1, 4]]\} \,.
$$
 
 
The rightmost letters, in a sap-word are not arbitrary either, but necessarily
must have its first list, irreducible,
i.e. of the form $[L,\phi,R]$, where $\phi$ is legal. In other words
the mate of the first $L$ must be the last $R$.
 
Hence there are exactly
$$
\sum_{i=1}^{[(K+1)/2]}  {{K+1} \choose {2i} } C_{i-1} \,,
$$
letters that may be finishers.
For example amongst the $20$ letters above
only the following
${ {5} \choose {2}} \cdot C_0 + { {5} \choose {4}} \cdot C_1 =15$ 
may end a sap word:
$$
   \{[[L, R], [0, 1]], [[L, R], [0, 2]], [[L, R], [1, 2]], [[L, R], [0, 3]],
       [[L, R], [2, 3]], [[L, R], [1, 3]], 
$$
$$
       [[L, L, R, R], [0, 1, 2, 3]], [[L, L, R, R], [0, 1, 2, 4]],
$$
$$
       [[L, L, R, R], [0, 1, 3, 4]], [[L, L, R, R], [0, 2, 3, 4]],
       [[L, L, R, R], [1, 2, 3, 4]], [[L, R], [0, 4]], 
$$
$$
       [[L, R], [2, 4]], [[L, R], [3, 4]], [[L, R], [1, 4]]\} \,.
$$
 
The next item on the agenda is: "Which letters can follow a given
letter?". This will be accomplished in three stages. First
we have to find the {\it pre-pre-followers} of the given letter,
then the {\it pre-followers} and finally the {\it followers}.
The pre-pre-followers indicate the possible ways of continuing
our sap (viewed globally) from $x<k$ into $ x \leq k$, by adding
vertical edges joining the ``loose ends'', thereby possibly
tying some of them to each other, which results in their
disappearance. The pre-followers are obtained by
deciding what to do with the surviving open ends. Going
from pre-pre-followers to pre-followers does not change the
first component of the pre-pre-letter. Finally the followers
are obtained from the pre-followers by inserting new  adjacent
$L,R$'s in the underlying legal bracketing, using the
free space that is left. In every phase, we also keep track of
the number of edges (of the sap, not of the Markov Process!) that are used,
that contribute to the weight of the Edge (of the Markov Process, not 
of the original sap!).
 
Let's first describe the first phase, of determining the
pre-pre-followers.
Let's consider a typical sap, and cut it
at the vertical line $x=k$. As we saw above, the horizontal
edges between $x=k-1$ and $x=k$ define a certain letter, 
the first part describing the induced legal bracketing, and the
second part listing the $y$ coordinates. So let's look only at the
part of the sap that lies to the left of $x=k$. Suppose that the
second part of $k^{th}$ letter is $[i_1, \dots, i_{2r}]$. This means
that there are $2r$ "open ends" waiting to be extended beyond
the "longitude" $x=k$. First note that we are allowed to
add  vertical edges on $x=k$, and in the process change the
underlying legal bracketing. For a very simple example,
suppose the letter
is  of the form $[[L,R],[i1,i2]]$. Then we can close the partial sap
by adding the $i2-i1$ edges joining $[k,i1]$ and $[k,i2]$ on
$x=k$, and finish up, adding a final letter "Period", to indicate that
we are finished. Another example is $[[L,L,R,R],[i1,i2,i3,i4]]$.
We can add the $i2-i1$ vertical edges joining $[k,i1]$ and $[k,i2]$, thereby
making the $i3$ an "L", turning it effectively into $[[L,R],[i3,i4]]$.
Another option is to add the $i4-i3$ edges joining $[k,i3]$ and $[k,i4]$, 
thereby making the $i2$ an "R", turning it effectively into $[[L,R],[i1,i2]]$.
We could also do both, eliminating the bracketing altogether, which
signals that we are done, so we only add the last letter, the Period.
 
In general, we can iterate this process of "shrinking the bracketing",
but every time we create new vertical edges, we lose territory, so
that we have to keep track of the "open space" left. In addition,
since we want to determine the type III Combinatorial Markov Process
(in which the edges are assigned weights), we also have to have another
variable, $extw$, that describes the length of the portion of the
underlying sap corresponding to the transition from the region
$x<k$ to $x\leq k$, in the first phase, and
from $x \leq k$ to $x < k+1$ in the second and third phases.
 
So we are now ready to formally define the set of {\it pre-pre-followers}
of a letter $LET=[[w_1, \dots, w_{2r}],[i_1, \dots, i_{2r}]]$,
where $[w_1, \dots, w_{2r}]$ is a legal bracketing, and 
$0 \leq i_1 < \dots < i_{2r} \leq K$. To this end,
we need to define the notion of {\it pre-pre-letter}.
 
A {\it pre-pre-letter} is a triple $[LET,FS,extw]$,
where $LET$ is a letter, $FS$ is a subset of $\{0, 1, 2, \dots , K\}$,
and $exwt$ is an integer denoting 
the extra-weight acquired so far in the transition from
$x <k$ to $x<k+1$. At the beginning 
$FS=FS_0:=\{0, 1, 2, \dots , K\} \backslash \{i_1, \dots , i_{2r} \}$,
and $extw=0$.
 
Initially the set of pre-pre-followers 
only has one element: the triple $[LET,FS_0,0]$. We keep
enlarging it by iteratively applying three "legal moves"
to the present members of this set of pre-pre-followers
of $LET$, until no new members can be inducted.
 
The three possible legal moves are $RR$, $LL$, and $RL$.
We will now describe them in turn.
 \vskip 30pt
\line{\bf 9.2 RR move \hfil}
 
An "$RR$ move"  is
obtained by joining two adjacent $R$s, erasing them both
and making the widow of the lower deceased $R$, formerly
an $L$, into an $R$. More precisely, an $RR$ move can be performed
whenever
there is a $b$ between $1$ and $2r-1$ such that
$w_b=w_{b+1}=R$. Letting the $L$-mate of $w_{b+1}$ be  $w_{a1}(=L)$ and
that of $w_{b}$ be $w_{a2} (=L)$, (of course we must have $a1<a2$),
we erase the two $R$'s, $w_b$ and $w_{b+1}$, from the first component of
$LET$, changing $w_{a2}$ from $L$ to $R$. We also erase $i_b$ and
$i_{b+1}$. The new $extw$, of the derived pre-pre-letter, is
the old $extw$ plus $i_{b+1}-i_{b}$ (the extra length of the sap, corresponding
to performing this particular $RR$ move), and the new set of
free-space, $FS$, is the old $FS$ minus 
$\{ i_b+1, i_b+2, \dots, i_{b+1}-1 \}$, corresponding to the set
of lattice points 
$\{ [k,i_b+1], [k,i_b+2], \dots, [k,i_{b+1}-1] \}$
taken-up by this particular $RR$ move.
 
In short, given a pre-pre-letter $[LET,FS,extw]$, where
$LET=[[w_1, \dots, w_{2r}],[i_1, \dots, i_{2r}]]$, 
then whenever there are two consecutive $R$s in 
$w_1 \dots w_{2r}$, say, $w_b=w_{b+1}=R$, applying the
$RR$-move at $b$, consists of the following operation,
where $a1$ is the location of the $L$-mate of $w_{b+1}(=R)$ and
$a2$ is the location of the $L$-mate of $w_b (=R)$.
$$
[[[w_1, \dots, w_{a1-1},L,w_{a1+1}, \dots, w_{a2-1},L,w_{a2+1},
\dots, w_{b-1},R,R,w_{b+2}, \dots, w_{2r}]
,[i_1, \dots, i_{2r}]],
$$
$$
FS,extw]
\rightarrow
$$
$$
[[[w_1, w_{a1-1},L,w_{a1+1}, \dots, w_{a2-1},R,w_{a2+1},
\dots, w_{b-1},w_{b+2}, \dots, w_{2r}],
[i_1, \dots, i_{b-1},i_{b+2}, \dots i_{2r}]],
$$
$$
FS \backslash \{i_{b}+1, \dots, i_{b+1}-1 \},extw+i_{b+1}-i_b]
$$
 
 \vskip 30pt
\line{\bf 9.3 LL move \hfil}
 
An "$LL$ move"  is
obtained by joining two adjacent $L$s, erasing them both
and making the widower of the upper deceased $L$, formerly
an $R$, into an $L$. More precisely, an $LL$ move can be performed
whenever
there is an $a$ between $1$ and $2r-1$ such that
$w_a=w_{a+1}=L$. Letting the $R$-mate of $w_{a+1}$ be  $w_{b1}(=R)$ and
that of $w_{a}$ be $w_{b2} (=R)$, (of course we must have $b1<b2$),
we erase the $2$ L's $w_a$ and $w_{a+1}$, from the first component of
$LET$, and change $w_{b1}$ from $R$ to $L$. We also erase $i_a$ and
$i_{a+1}$. The new $extw$, of the derived pre-pre-letter, is
the old $extw$ plus $i_{a+1}-i_{a}$ (the extra length of the sap, corresponding
to performing this particular $RR$ move), and the new set of
free-space, $FS$, is the old $FS$ minus 
$\{ i_a+1, i_a+2, \dots, i_{a+1}-1 \}$, corresponding to the set
of lattice points 
$\{ [k,i_a+1], [k,i_a+2], \dots, [k,i_{a+1}-1] \}$
taken-up by this particular $RR$ move.
 
In short, given a pre-pre-letter $[LET,FS,extw]$, where
$LET=[[w_1, \dots, w_{2r}],[i_1, \dots, i_{2r}]]$, 
then whenever there are two consecutive $L$'s in 
$w_1 \dots w_{2r}$, $w_a=w_{a+1}=L$, applying the
$LL$-move at $a$, consists of the following operation,
where $b1$ is the location of the $R$-mate of $w_{a+1}(=L)$ and
$b2$ is the location of the $R$-mate of $w_a (=L)$.
$$
[[[w_1, \dots, w_{a-1},L,L,w_{a+2}, \dots, 
w_{b1-1},R,w_{b1+1}, \dots, w_{b2-1},R,w_{b2+1}, \dots
w_{2r}],
[i_1, \dots, i_{2r}]] ,
$$
$$
FS,extw]
\rightarrow
$$
$$
[[[w_1, \dots, w_{a-1},w_{a+2}, \dots, 
w_{b1-1},L,w_{b1+1}, \dots, w_{b2-1},R,w_{b2+1}, \dots
w_{2r}],
$$
$$
[i_1, \dots, i_{a-1},i_{a+2}, \dots i_{2r}]], FS \backslash \{i_{a}+1, \dots,
i_{a+1}-1 \},extw+i_{a+1}-i_a]
$$
 
 \vskip 30pt
\line{\bf 9.4 RL move \hfil}
 
An "$RL$ move"  may be
obtained whenever an $L$ immediately follows an $R$, 
and erasing them both, and leaving the widowers unchanged,
thereby making them marry each other (luckily they are of the same
sex now, so that the "sex-change operation" required 
for one of the survivors of the $RR$ and $LL$ moves,
so that they can marry each other,
is no longer necessary).
More precisely, an $RL$ move can be performed
whenever
there is an $a$ between $1$ and $2r-1$ such that
$w_a=R$ and $w_{a+1}=L$. 
The new $extw$, of the derived pre-pre-letter, is
the old $extw$ plus $i_{a+1}-i_{a}$ (the extra length of the sap, corresponding
to performing this particular $RR$ move), and the new set of
free-space, $FS$, is the old $FS$ minus 
$\{ i_a+1, i_a+2, \dots, i_{a+1}-1 \}$, corresponding to the set
of lattice points 
$\{ [k,i_a+1], [k,i_a+2], \dots, [k,i_{a+1}-1] \}$
taken-up by this particular $RR$ move.
 
In short, given a pre-pre-letter $[LET,FS,extw]$, where
$LET=[[w_1, \dots, w_{2r}],[i_1, \dots, i_{2r}]]$, 
then whenever there is an $L$ immediately following an $R$ in
$w_1 \dots w_{2r}$, say: $w_a=R,w_{a+1}=L$; applying the
$RL$-move at $a$, consists of the following operation,
$$
[[[w_1, \dots, w_{a-1},R,L,w_{a+2}, \dots, 
w_{2r}],[i_1, \dots, i_{2r}]] ,FS,extw]
\rightarrow
$$
$$
[[[w_1, \dots, w_{a-1},w_{a+2}, \dots, w_{2r}],
[i_1, \dots, i_{a-1},i_{a+2}, \dots i_{2r}]],
$$
$$
FS \backslash \{i_{a}+1, \dots, i_{a+1}-1 \},extw+i_{a+1}-i_a]
$$

\vskip 30pt 
\line{\bf 9.5. From Pre-Pre-Followers to Pre-Followers \hfil}
 
The set of pre-pre-followers of any given letter $LET$ might contain
a pre-letter that has the form $[[[],[]],FS,extw]$, i.e. where the underlying
letter shrunk to nothing, which means that the sap has been closed,
and can't be continued. This means that there is an Edge
between $LET$ to the final letter "FINISH".
So the set of followers of $LET$, Followers(LET), starts out
with $[FINISH, extw]$. If the pre-pre-follower is not
empty, then, if it is $[LET1,FS,extw]$, where
$LET1=[[w_1, \dots, w_{2s}],[i_1, \dots, i_{2s}]]$, 
then we have $2s$ open ends, and we have to decide how to
continue them along the vertical line $x=k$, before they 
venture into a horizontal edge connecting the 
vertical lines $x=k$ and $x=k+1$.
Of course, for the vertical edges, we can
only use vertices on $x=k$  whose $y$ coordinates belong to $FS$.
Also, for each of these decisions where to extend the $2s$ free ends,
we keep track of the extra weight, and modify the free-space set,
$FS$.  For example, in the language for saps confined
to $[0,11]$ (i.e. $K=11$), consider the letter
$[[L,R,L,R],[1,5,7,10]]$. Its only pre-pre-follower is
obtained by performing an $RL$-move at the second and third places,
resulting in the pre-letter
$[[[L,R],[1,10]],\{0,2,3,4,7,8,9,11,12\},2]$.
Now we have two free ends to worry about. The one at
$[k,1]$ corresponding to the $L$ has the option either
to go down one unit, to $[k,0]$ before going to $[k+1,0]$,
or to "cross the river" right way, straight to $[k+1,1]$,
or to go up one unit, to $[k,2]$ (and then to $[k+1,2]$), or
go up two units, to $[k,3]$ (and then to $[k+1,3]$),
or go up three units, to $[k,4]$ (and then to $[k+1,4]$).
Of course it may not go up four units, since $[k,5]$ is
not free. Similarly the free end that is now at $[k,10]$
may go one or two units up, to $[k,11]$, or 
$[k,12]$, respectively, before crossing the river to $[k+1,11]$,
$[k+1,12]$ respectively, or it may decide to go to $[k+1,10]$
straight away, or it may decide to go down to $[k,9]$, or
$[k,8]$, or $[k,7]$, before crossing horizontally to
$[k+1,9]$,$[k+1,8]$, $[k+1,7]$, respectively. So
the open end at $[k,1]$ has $4$ options, while the
open end at $[k,10]$ has $6$ options. These are independent
(in this case, sometimes the options of each of the individual
free ends conflict with each other), so in this case there
are $4 \times 6 =24$ pre-followers that follow the
pre-pre-follower $[[[L,R],[1,10]],\{0,2,3,4,7,8,9,11,12\},3]$
considered here. For example one of them, obtained when
we decide to make the $L$ go down one unit and the $R$ go up
two units, results in the following pre-follower
$[[[L,R],[0,11]],\{2,3,4,7,8,9,12\},7]$.
 
\vskip 30pt
\line{\bf 9.6. From Pre-Followers to Followers \hfil}
 
Each pre-follower is automatically a follower, but in addition,
there are many other kinds of followers. These are obtained
by inserting pairs $LR$ in the free-space set $FS$, just like
we did for the Left-Letters above, individually for each consecutive
stretch of free-space. For example, the pre-letter above
$[[[L,R],[0,11]],\{2,3,4,8,9,12\},7]$, may be followed, by itself,
of course (i.e. do nothing extra), or by 
$[[[L,L,R,R],[0,2,3,11]],\{4,8,9,12\},10]$, or
$[[[L,L,R,R],[0,8,9,11]],$
$\{2,3,4,12\},10]$. 
Every time we insert a pair $L,R$ in a stretch of free space,
say that we place $L$ at location $a$ and $R$ at location
$b$, the resulting new pre-letter has its $extw$ increased by
$b-a+2$.
 
\vskip 30pt
\line {\bf 9.7. Constructing the type III Combinatorial Markov-Process for
SAPS \hfil}
 
Recall that
in order not to confuse edges of the original sap, that live on
the 2D square-lattice, with edges of the combinatorial Markov Process
describing them, we are calling the latter kind Edges.
 
To create the Type III (i.e. Edge-weighted) Combinatorial
Markov Process describing saps
confined to $0 \leq y \leq K$,
we create two extra letters, let's call them $START$, and $FINISH$.
The followers of the letter $START$ are all the left-letters described
above, i.e. all letters of the form
$[[L,R,L,R, \dots, L,R], [i_1, \dots, i_{2r} ]]$, for
$r=1,2, \dots, [(K+1)/2]$, and 
$0 \leq i_1 < i_2 < \dots < i_{2r} \leq K$. So we have
one Edge between $START$ and each one of these left-letters,
and we assign the weight
$$
\sum_{a=1}^{r} (i_{2a}-i_{2a-1}+2) \, ,
$$
to that Edge,
because these are the number of edges that live in $0 \leq x <1$.
 
For each letter, we find its followers, as described above, getting
followers that are pre-letters
of the form $[LET1,FS,extw]$. $FS$ is no longer needed,
but $extw$ is the weight of the Edge connecting $LET$ and $LET1$.
Also, if one of the pre-pre-followers is of the
form $[[],[]],FS,extw]$, then we make $FINISH$ one of
the followers of $LET$, and the weight of the Edge connecting
$LET$ and $FINISH$ is $extw$, and $FS$ is discarded.
 
In the resulting type III Combinatorial Markov Process,
$[Start,Finish,ListOfNeighbors]$,
the set $Start$ consists of the singleton $\{ START \}$,
the set $Finish$ consists of the singleton $\{ FINISH \}$,
and the list of outgoing neighbors is constructed as above.

\vskip 30pt 
\line{\bf 9.8. A User's Manual for the Maple Package SAP \hfil}
 
You must first download the package {\tt SAP}, saving it as SAP, either from
my website, or directly from INTEGERS.
To use it, stay in the same directory, get into Maple, and
type: { \tt read SAP;} Then follow the on-line help.
In particular, to get a list of the main procedures, type:
{\tt ezra(); }.
 
The main procedures are: {\tt    GF, GFSeries , SAPseries , gfBatchelorYung }.
 
For a positive integer $n$, and a variable $s$, typing {\tt GF(n,s);}
would give the generating function
$$
f_n(s):=\sum_{i=1}^{\infty} a_n(i) s^{2i} \, ,
$$
where $a_n(i)$ is the number of self-avoiding polygons in the
two-dimensional square lattice whose perimeter has $2i$ edges,
and whose width (the difference between the largest and smallest
$y$ coordinates) is $\leq n$.
 
{\tt GF(n,s)} works, on my computer, up to $n=6$.
Beyond that, you may wish to use 
{\tt GFSeries(n,L)}, where $L$ is also a positive integer,
in order to get the first $L$ coefficients of $f_n(s)$.
 
In order to get the first $L$ terms in the sequence enumerating
{\it all} self-avoiding polygons (with unrestricted width),
type {\tt SAPseries(L); }. 
 
Finally {\tt gfBatchelorYung(n,t);} 
gives the generating function for enumerating
self-avoiding {\it walks}
immersed in the strip $[0,n]$ and such that the leftmost wall touches
the $x$-axis (i.e. contains the origin).
It gives the quantity described in
M.T. Batchelor, and C.M. Yung's paper [BY]
(the denominators on p. 4059 and 4066 and the 
numerators on p. 4064).

\vskip 30pt
\line{{\bf 9.9. A Brief Explanation of the Nuts and Bolts of } {\tt SAP}
\hfil}
 
{\tt gf(n,t)} is the generating function for SAPS immersed in
$[0,n]$, and it is obtained by calling procedure {\tt SolveMC3},
borrowed from the package {\tt MARKOV}, that solves the
type III Markov Process obtained via {\tt MarCha(n)}.
{\tt MarCha(n)} follows the outline given above for constructing
the Markov Process describing saps confined to $[0,n]$.
Since {\tt gf(n,t)} counts all saps immersed in $[0,n]$, not
only those that lie on the $x$-axis, and what we really want
are only those that do lie (in other words we only want every sap
to be counted once up to translation), we  have to find
$gf(n,t)-gf(n-1,t)$. This is done by {\tt GF(n,t)}, the main
procedure.
 
{\tt SAPseries} is designed in an analogous way to {\tt KHAYA}.
 
{\tt gfBatchelorYung(n,t)} uses a slight modification of the 
Markov Process, obtained from {\tt MarChaBY(n)}, so that to count
the set of self-avoiding walks counted by [BY].
 
\vskip 30pt 
\line{\bf 10.1. More SAPs For Less Money: Counting 
Locally-Skinny SAPs \hfil}
 
The Maple package SAP counts {\it globally} skinny saps, i.e.,
for any given positive integer $n$, it counts
the saps for which the difference between the
largest $y$ coordinate of any of the vertices, and the
smallest $y$ coordinate, is less than $n$. The package 
{\tt FreeSAP} counts the larger set of saps in which we only demand
that the difference between the largest and smallest $y$ coordinate,
{\it for each specific} vertical slice $x=k$, is smaller than $ \leq n$.
 
To go from SAP to FreeSAP, we use the same methodology that
was employed in going from ANIMALS to FreeANIMALS. 
For the details, see the source code of the Maple package FreeSAP.
 
\vskip 30pt
\line{{\bf 10.2.  A User's Manual for the Maple Package }{\tt FreeSAP}\hfil}
 
You must first download the package {\tt FreeSAP}, saving it as 
FreeSAP, either from
my website, or directly from INTEGERS.
To use it, stay in the same directory, get into Maple, and
type: { \tt read FreeSAP;} Then follow the on-line help.
In particular, to get a list of the main procedures, type:
{\tt ezra(); }.
 
The main procedures are {\tt gff} and {\tt gffSeries}.
 
For a positive integer $n$, and a variable $s$, typing {\tt gff(n,s);}
would give the generating function
$$
g_n(s):=\sum_{i=1}^{\infty} b_n(i) s^{2i} \, ,
$$
where $b_n(i)$ is the number of self-avoiding polygons in the
two-dimensional square lattice whose perimeter has $2i$ edges,
and such that for any vertical cross-section, $x=k$, the difference
between the largest $y$ such that $(k,y)$ belong to the sap,
and the smallest such $y$, is $\leq n$.
 
{\tt gff(n,s)} works, on my computer, up to $n=6$.
Beyond that, you may wish to use 
{\tt gffSeries(n,L)}, where $L$ is also a positive integer,
in order to get the first $L$ coefficients of $g_n(s)$.

\vskip 30pt 
\line{{\bf 10.3. A Brief Explanation of the Nuts and Bolts of} {\tt FreeSAP}
\hfil}
 
The underlying Combinatorial Markov Process is of type IV.
{\tt MarChaf(n,t);} constructs it, using the machinery of
{\tt SAP}, but introducing multiple edges as necessary
(corresponding to various interfaces). Then {\tt SolveMC4},
borrowed from the package {\tt MARKOV}, described above,
finds the weight-enumerator, in procedure {\tt gff(n,t) }.
{\tt SolveMC4series}, also borrowed
from {\tt MARKOV}, is used to find the series expansion in
{\tt gffSeries(n,L)}.
\vskip 30pt
\line{\bf 11.1.  Counting Skinny Self-Avoiding Walks \hfil}
 
The methodology is the same as for counting self-avoiding polygons,
but the details are more complicated. The reader is invited to study
the source-code of the Maple package {\tt SAW} in detail. Here
we will only briefly sketch how to adapt the algorithm for counting skinny
self-avoiding polygons to that of counting 
skinny self-avoiding walks.
 
The vertical cross-sections look a little different, since in addition
to $L-R$ pairs, we may have zero, one, or two "loners" that 
do not connect, from the left, to any other horizontal edge.
Let's denote these loners by the letter $A$. So now the alphabet
still contains the same letters as in the SAP alphabet, but
each of these letters give rise to several more letters, obtained
by inserting either one or two $A$'s in any available slot.
 
For example, if the strip is $0 \leq y \leq 5$, then the
letter $[[L,R],[0,3]]$ also gives rise to the letters
$[[L,A,R],[0,1,3]]$, $[L,A,R,A],[0,1,3,5]]$ and eight others
(altogether ${{4} \choose {1}}+{{4} \choose {2}}=10$).
 
The pre-left-letters are obtained from those of the SAP case by sticking
$0$, $1$, or $2$ $A$'s.
To get the pre-pre-followers of a letter, we have, in addition to
$RR$, $LL$, and $RL$ moves, also the following four moves.
 
\noindent
{\bf AL move}: in which the
lonely $A$ connects to an $L$ residing right above it,
making $L$'s ex-R-mate into a lonely $A$.
 
\noindent 
{\bf LA move}: in which the
lonely $A$ connects to an $L$ residing right under it,
making $L$'s ex-R-mate into a lonely $A$.
 
\noindent 
{\bf AR move}: in which the
lonely $A$ connects to an $R$ residing right above it,
making $R$'s ex-L-mate into a lonely $A$.
 
\noindent 
{\bf RA move}: in which the
lonely $A$ connects to an $R$ residing right under it,
making $R$'s ex-L-mate into a lonely $A$.
 
The phase of going from pre-pre-followers to pre-followers is
similar, it preserves the $L-R-A$ part, i.e. the first
component of the letter, but changes the second part, as well
as the available free space.
 
Finally, the phase between pre-followers to followers is also similar,
except that in addition we may stick-in one or two $A$'s up to a total
of two $A$'s. 
 
We also have two special letters $START$ and $FINISH$, to denote the
beginning and end. Every time it is possible to end the walk,
i.e. there are only (one or two) $A$s left (possibly after doing
AbortL or AbortR, which means that an $L$ or $R$, formerly paired,
decides to "commit suicide", thereby
leaving its mate a lonely $A$.
 
To fully understand what's going on, you {\it must} study 
{\tt SAW} carefully. 
 
\vskip 30pt
\line{\bf 11.2. A User's Manual for the Maple Package SAW \hfil}
 
The main functions are {\tt GFW, GFSeriesW}, and {\tt SAWseries}.
 
{\tt GFW(n,t);} would give the (ordinary) generating function, in the
variable $t$,  that enumerates (undirected) saws whose (global) width is
$\leq n$. In other words, the rational function
$$
W_n(t)=\sum_{i=0}^{\infty} a_n(i) t^i \,,
$$
where $a_n(i)$ is the number of 
$i$-step self-avoiding walks (divided by 2), whose width is $\leq n$.
 
{\tt GFW(n,t)} works, on my computer, up to $n=4$.
Beyond that, you may wish to use 
{\tt GFSeriesW(n,M)}, where $M$ is also a positive integer,
in order to get the first $M$ coefficients of $W_n(t)$.
 
Finally, if you want to find the first $L$ terms in the
notorious enumerating sequence for (all, unrestricted)
saws (in the 2D square-lattice), type {\tt SAWseries(L)}.
Of course, it can't compete with the very efficient computations
of Conway and Guttmann [CG], but its agreement, up to $L=24$,
with the published data, is the best {\it proof}
for us, of the validity of our approach. If Mikowsky[M] would have done
it, he would have found his mistake right away (his output
starts to disagree at $L=4$).
 
\vskip 30pt
\line{{\bf 11.3 A Very Brief Explanation of the Nuts and Bolts of} {\tt SAW}
\hfil}
 
{\tt MarChaW} finds the type IV Combinatorial Markov Process that
describes the language of saws of bounded width. Please note that
we use a slightly different representation than the one used
in {\tt MARKOV}, using lists rather sets and generating
polynomials. Likewise, {\tt SolveMarCha} is a version of
{\tt MARKOV}'s {\tt SolveMC4} that handles the present representation.
{\tt gf(n,t);} gives the generating function for all saws confined
to the strip $0 \leq y \leq n$, which over-counts saws of width
$<n$. In order to get the right count, we use {\tt GF(n,t);}, which
is simply $gf(n,t)-gf(n-1,t)$.
 
\vskip 30pt
 
\line{\bf 12.1. More SAWs For Less Money: Counting 
Locally-Skinny SAWs \hfil}
 
The Maple package SAW counted {\it globally} skinny saws, i.e.,
for the given positive integer $n$, it counted
saps for which the difference between the
largest $y$ coordinate of any of the vertices, and the
smallest $y$ coordinate, is $\leq n$. The package 
{\tt FreeSAW} counts the larger set of saws in which we only demand
that the difference between the largest and smallest $y$ coordinate,
{\it for each specific} vertical slice $x=k$, is $\leq n$.
 
To go from SAW to FreeSAW, we use the same methodology that
was employed in going from ANIMALS to FreeANIMALS, and from
SAP to FreeSAP. 
We refer the reader is to the source code of the Maple package FreeSAW.
 
\vskip 30pt
\line{\bf 12.2. A User's Manual for the Maple Package FreeSAW \hfil}
 
You must first download the package {\tt FreeSAW}, saving it as 
FreeSAW, either from
my website, or directly from INTEGERS.
To use it, stay in the same directory, get into Maple, and
type: { \tt read FreeSAW;} . Then follow the on-line help.
In particular, to get a list of the main procedures, type:
{\tt ezra(); } . The main procedures are {\tt gfWf} and {\tt gfSeriesWf}.
 
For a positive integer $n$, and a variable $s$, typing {\tt gfWf(n,s);}
would give the generating function
$$
f_n(s):=\sum_{i=1}^{\infty} b_n(i) s^{i} \, ,
$$
where $b_n(i)$ is the number of $i$-step self-avoiding walks in the
two-dimensional square lattice 
such that for any vertical cross-section, $x=k$, the difference
between the largest $y$ such that $(k,y)$ belong to the saw,
and the smallest such $y$, is $\leq n$.
 
{\tt gfWf(n,s)} works, on my computer, up to $n=5$.
Beyond that, you may want to use 
{\tt gfSeriesWf(n,L)}, where $L$ is also a positive integer,
in order to get the first $L$ coefficients of $f_n(s)$.
 \eject
\vskip 30pt
\line{{\bf 12.3. A Very Brief Explanation of the Nuts and Bolts of} {\tt
FreeSAW}\hfil}
 
The underlying Combinatorial Markov Process is of type IV.
{\tt MarChaWf(n,t);} constructs it, using the machinery of
{\tt SAW}, but introducing even more multiple edges as necessary
(corresponding to various interfaces). Then 
{\tt SolveMarCha} solves it to give {\tt gfWf(n,t)}.
 
\vskip 30pt
\line{\bf 13. Conclusion \hfil}
 
We have described seven  Maple packages: 
{\tt MARKOV, ANIMALS, FreeANIMALS, SAP, FreeSAP, SAW} and {\tt FreeSAW}.
The first of these, {\tt MARKOV} is of very general scope, and should
be useful
in many other situations where the Transfer-Matrix method is
employable. The other packages enumerate
"skinny"
lattice-animals, self-avoiding polygons and self-avoiding walks,
with two definitions of skinniness: {\it global}, where the object
has to fit completely within a prescribed horizontal strip,
and {\it local}, where the whole object has unbounded width, but
each vertical cross-section has bounded width.
 
We hope that in the future, similar treatment would be given for
other venerable models of statistical physics, like
the Ising model (in two and three dimensions, with magnetic field),
Percolation, and the Monomer-Dimer problem.
This methodology should also be useful in the study of plane and solid
partitions.
 
Most important, the systematic, careful and lucid ``software engineering"
of this project should make it easier for me to implement the
{\it Umbral Transfer-Matrix Method} [Z2].
 
\vskip 30pt
\line{\bf References \hfil}


\parindent=0pt
 
[BY] M.T. Batchelor, and C.M. Yung,
{\it Exact transfer-matrix enumeration and critical behaviour of
self-avoiding walks across finite strips},
J. Physics A: Math. Gen. {\bf 27} (1994) 4055-4067.
\parskip=5pt
 
[B] Mireille Bousquet-M\'elou, {\it Convex polyominoes
and Algebraic Languages}, 
J. Physics A: Math. Gen. {\bf 25} (1992), 1935-1944.
 
[CG] A.R. Conway and Anthony J. Guttmann,
{\it Square lattice self-avoiding walks and corrections-to-scaling},
Phys. Rev. Letts. {\bf 77} (1996), 5284-5287.
 
[DV] Maylis Delest and Xavier G. Viennot, ``{\it Algebraic
Languages and Polyominoes Enumeration}", Theor. Comp. Sci.
{\bf 34}, 169-206.
 
[F] Steven Finch, {\it Mathematical Constants Website},
\hfill\break
{\tt http://www.mathsoft.com/asolve/constant/constant.html}.
 
[KP] Brian W. Kernighan and Bob Pike,
``{\it The Practice of Programming}", Addison-Wesley,
Reading, Mass, 1999.
 
[K1] David A. Klarner, {\it Cell Growth Problems},
Canad. J. Math. {\bf 19} (1967), 851-863. 
 
[K2] David A. Klarner, {\it My Life Among the Polyominoes},
in  ``The Mathematical Gardener", D. A. Klarner, ed., 
Wadsworth, 1981, 243-262.
 
[KR] David A. Klarner and Ronald L. Rivest,
{\it A procedure for improving the upper bound for the number
of n-ominoes}, Canad. J. Math. {\bf 25} (1973), 585-602.
 
[M] Anthony A. Mikovsky, ``{\it Convex Polyominoes, 
General Polyominoes, and Self-Avoiding Walks using
algebraic languages}", Ph.D. dissertation, University
of Pennsylvania Mathematics Department, 1997.
Available from UMI Dissertation Services,
{\tt http://www.umi.com}.
 
[R] Ronald C. Read, {\it Contributions to the Cell Growth Problem},
Canad. J. Math. {\bf 14} (1962), 1-20.
 
[S] Richard P. Stanley, ``{\it Enumerative Combinatorics}",
volume 1, Wadsworth, Monterey, California, 1986.
Reprinted by Cambridge University Press.
 
[WS] S.G. Whittington and C.E. Soteros, {\it Lattice Animals:
Rigorous results and wild guesses}, in:
``Disorder in Physical Systems: A Volume in Honour of J.M. Hammersley,
ed. G.R. Grimmet and D.J.A. Welsh, Oxford, 1990. 
 
[Z1] Doron Zeilberger,
{\it 
Opinion 37: Guess What? Programming is Even More Fun Than Proving, and, More
 Importantly It Gives As Much, If Not More, Insight and Understanding},
\hfill\break
{\tt http://www.math.temple.edu/\Tilde zeilberg/Opinion37.html}.
 
[Z2] Doron Zeilberger, {\it The Umbral Transfer-Matrix Method},
in preparation.
 
\bye