Classifying ECOSystems and Random Walks
Cyril Banderier
Algorithms Project, INRIA Rocquencourt
Algorithms Seminar
September 27, 1999
[summary by Pierre Nicodème]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
This talk presents a classification by rationality, algebraicity or
transcendence of ECOsystems (Enumerating Combinatorial Objects) and
of more general random walks. It is based on an article by Cyril
Banderier, Mireille BousquetMélou, Alain Denise, Philippe Flajolet,
Danièle Gardy and Dominique GouyouBeauchamps [1].
1 Introduction
A generating tree is defined by a system (an axiom and a
family of rewriting rules)

æ è 
(s_{0}),

{ 
(k)®(e_{1}(k))(e_{2}(k))...(e_{k}(k)) 
} 

ö ø 
.
(1) 
Here, the axiom (s_{0}) specifies the degree of the root, while the
productions e_{i}(k) (with e_{i}(k)>0) list the degrees of the
k descendants of a node labelled k (note the constraint on the
number of descendants of a node). Such a system constitutes an
ECOSystem.
Example 1 123avoiding permutations.
Consider the set S_{n}(123) of permutations of length n that
avoid the pattern
123: there exist no integers i<j<k
such that s(i)<s(j)<s(k). For instance,
s=4213 belongs to S_{4}(123) but s=1324 does not,
since s(1)<s(3)<s(4).
Observe that if tÎS_{n+1}(123), then the permutation s
obtained by erasing the entry n+1 from t belongs to
S_{n}(123). Conversely, for every sÎS_{n}(123), insert
the value n+1 in each place where this is compatible with the
avoiding rule; this gives an element of S_{n+1}(123). For
example, the permutation s=213 gives 4213, 2413 and 2143,
by insertion of 4 in first, second and third place respectively. The
permutation 2134, resulting of the insertion of 4 in the last
place, does not belong to S_{4}(123). This process can be described
by a tree whose nodes are the permutations avoiding 123: the root is
1, and the children of any node s are the permutations
derived as above (see Figure 1(a)).
Let us now label the nodes by their number of children: we obtain the
tree of Figure 1(b). It can be proved
that the k children of any node labelled k are labelled
respectively k+1,2,3,...,k. Thus the tree we have constructed is
the generating tree obtained from the following system:

æ è 
(2),

{ 
(k)®(2)(3)...(k1)(k)(k+1) 
} 

ö ø 
.
(2) 
Figure 1: The generating tree of 123avoiding permutations:
(a) nodes labelled by the permutations;
(b) nodes labelled by the numbers of children.
Notations.
We assume that all the values appearing in the generating tree are
positive.
In the generating tree, let f_{n} be the number of nodes at level n
and s_{n} the sum of the labels of these nodes. By convention, the
root is at level 0, so that f_{0}=1. In terms of walks, f_{n} is the
number of walks of length n.
The generating function associated to the system is
F(z) =å_{n³ 0} f_{n} z^{n}.
Note that s_{n}=f_{n+1}, and that the sequence (f_{n})_{n} is
nondecreasing.
Now let f_{n,k} be the number of nodes at level n having
label k (or the number of walks of length n ending at position
k). The following generating functions will be of interest:
F_{k}(z) = 

f_{n,k} z^{n}
and 
F(z,u) = 

f_{n,k} z^{n} u^{k}.

We have F(z)=F(z,1)=å_{k³ 1}F_{k}(z).
Furthermore, the F_{k}'s satisfy the relation

F_{k}(z) = [k=s_{0}] + z 

p_{j,k} F_{j}(z),
(3) 
where [k=s_{0}] is 1 if k=s_{0} and 0 elsewhere and
p_{j,k} denotes the number { i£ j  e_{i}(j)=k } of onestep
transitions from j to k. This is equivalent to the
recurrence f_{n+1,k}=å_{j³ 1}p_{j,k} f_{n,j} for the
numbers f_{n,k} (with f_{0,s}_{0} = 1),
that results from tracing all the paths that lead to k in n+1
steps.
We refer to [1] for random generation using counting and
generating trees.
2 Rational Systems
ECOsystems satisfying strong
regularity conditions
lead to rational generating functions.
This covers systems that
have a finite number of allowed degrees, as well as
systems where the sum of the labels at level k depends linearly on k.
Proposition 1
If finitely many labels
appear in the tree, then F(z)=F(z,1) is rational.
Proof.
Only a finite number of F_{k}'s are nonzero; they are related by
linear equations like Equation (3) above and therefore
rational. F(z) is a finite sum of these, and is also rational.
Example 2
Fibonacci numbers are generated by the system
((1),{(k)®(k)^{k1}((kmod2)+1)})
that can also be written as
((1),{(1)®(2),(2)®(1)(2)}).
Proposition 2
Let s(k)=e_{1}(k)+e_{2}(k)+...+e_{k}(k). If s is an
affine function of k, say s(k)=a k+b, then the
series F(z) is rational. More precisely:
F(z)= 
1+(s_{0}a)z 

1a zb z^{2} 

. 
Proof.
Let n³ 0 and let k_{1}, k_{2},..., k_{f}_{n} denote the labels of
the f_{n} nodes at level n. Then
f_{n+2}=s_{n+1} 
=(a k_{1}+b)+(a k_{2}+b)
+...+(a k 

+b) 


=a s_{n}+b f_{n}=a f_{n+1}+b f_{n}. 
We know that f_{0}=1 and f_{1}=s_{0}. The result follows.
Example 3
The system ((2),{(k)®(2)^{k1}(k+1)})
produces the Fibonacci numbers of even index.
Proposition 2 can be adapted to apply to systems that
``almost'' satisfy its criterion (see [1]).
3 Algebraic Systems
Systems where a finite modification of the set {1,...,k} is
reachable from k lead to algebraic generating functions.
The possible moves from k are given by the rule:
(
k)
®{(0),...,(
k1)}\{(
k
i)
iÎ B}
È
{{(
k+
j)
jÎ A}},
(4)
where AÌN and BÌN^{+} are a finite multiset (denoted
{{...}}) and a finite set specifying respectively the
allowed forward jumps (possibly coloured) and the
forbidden backwards jumps.
Observe that these walk models are not necessarily ECOsystems, first
because we allow labels to be zerobut a simple translation can
take us back to a model with positive labels, and second because we
do not require (k) to have exactly k successors.
In this section f_{n,k} is the number of walks of length n ending
at point k and f_{n}(u)=å_{k³ 0}f_{n,k}u^{k} is the coefficient
of z^{n} in F(z,u).
We continue this section with the example A={4,15} and B={2},
axiom (0) and the corresponding family of rules
{ 
(k)®(0)(1)...(k3)(k1)(k+4)(k+15) 
} 
. 
This corresponds in generating functions to substituting u^{k} in
u^{0}+...+u^{k1}u^{k2}+u^{k+4}+u^{k+15}
= 

u^{k2}+u^{k+4}+u^{k+15} 
for k³ 2. This gives the recurrence
f_{n+1}(u)=f_{n}(1)f_{n}(u)/1u+(u^{4}+u^{15}u^{2})f_{n}(u), and
yields the functional equation
F(z,u)=1+z 
æ ç ç è 

+P(u)F(z,u){u^{<0}} 

z^{n} L[f_{n}](u) 
ö ÷ ÷ ø 
.
(5) 
Here
P(u)=å_{aÎ A}u^{a}å_{bÎ B}u^{b} and
L[g](u)=g(1)g(u)/1u+P(u)g(u).
Equation (5) may be rewritten as
F(z,u) 
æ ç ç è 
1+ 

zP(u) 
ö ÷ ÷ ø 
=1+ 

F(z,1)z 

c_{j}(u)¶_{u}^{j}
F(z,0), 
where the c_{j}(u) are Laurent polynomials.
The kernel K(z,u) of Equation (5) is the coefficient of
F(z,u) in the
lefthand side of this equation.
F(z,u)K(z,u) is a linear combination of b+1 unknown
functions. Solving K(z,u)=0 in u gives b+1 convergent branches u_{i}(z)
which, in turn, give the ¶_{u}^{j} F(z,0) through a
(b+1)×(b+1) linear system, and from there
F(z,1), which is algebraic.
Proposition 3
The generating function F(z,1) counting the number of walks,
starting from zero and irrespective of their endpoint is algebraic and
F(z,1)=1/zÕ_{i=0}^{b}(1u_{i}),
where b=max B and u_{i}(z) are the finite solutions
at z=0 of the equation K(z,u)=0.
Examples of algebraic systems are the Catalan numbers
{(k)®(0)(1)...(k)(k+1)}, the Motzkin numbers
{(k)®(0)...(k1)(k+1)}, the Schröder numbers
{(k)®(0)...(k1)(k)(k+1)} or the mary trees
((m),{(k)®(m)...(k)(k+1)(k+2)...(k+m1)}).
4 Transcendental Systems
4.1 Transcendence
If the coefficients of a series grow too fast, its radius of
convergence is zero.
Proposition 4
Let b be a nonnegative integer. For k³1, let
m_{k}={ i e_{i}(k)³ kb }. Assume that:

for all k, there exists a forward jump from k (i.e.,
e_{i}(k)>k for some i),
 the sequence (m_{k})_{k} is nondecreasing and tends to infinity.
Then the generating function of the system has radius of
convergence 0.
Proof.
See [1].
However, there are ECOsystems or walks that are transcendental with
positive radius of convergence such as
{(k)®(2)(4)...(2k)} or
{(k)®(é k/2ù)^{k1}(k+1)}.
4.2 Holonomy
A subclass of transcendental functions is the class of holonomic
functions. A series is said to be
holonomic or Dfinite if it satisfies
a linear differential equation with polynomial coefficients in
z. Equivalently, its coefficients f_{n} satisfy a linear recurrence
relation with polynomial coefficients in n. Given a sequence f_{n},
the OGF (ordinary generating function) å f_{n} z^{n} is holonomic if
and only if the EGF (exponential generating function) å f_{n}z^{n}/n!
is holonomic.
The following table gives examples of holonomic and nonholonomic
transcendental systems with references to the Encyclopedia of Integer
Sequences (EIS) by Sloane and Plouffe [2, 3].
Axiom 
Rewriting rules 
Name 
EIS Id. 
Generating Function 

Holonomic OGF 


EGF 
(1) 
(k)® (k+1)^{k} 
Permutations 
M1675 
1/(1z) 
(2) 
(k)® (k)(k+1)^{k1} 
Arrangements 
M1497 
e^{z}/(1z) 
(1) 
(k)® (k1)^{k1} (k+1) 
Involutions 
M1221 
e^{z+z}^{2}^{/2} 
(2) 
(k)® (k+1)^{k1} (k+2) 
Partial permutations 
M1795 
e^{z/(1z)}/(1z) 






Nonholonomic OGF 


EGF 
(1) 
(k)® (k)^{k1} (k+1) 
Bell numbers 
M1484 
e^{e}^{z}^{1} 
(2) 
(k)® (k1)(k)^{k2}(k+1) 
Bessel numbers 
M1462 
 
References
 [1]

Banderier (C.), BousquetMélou (M.), Denise (A.), Flajolet (P.), Gardy
(D.), and GouyouBeauchamps (D.). 
Generating functions for generating trees. Discrete
Mathematics. 
25 pages. To appear.
 [2]

Encyclopedia of integer sequences. 
Available from
http://www.research.att.com/~njas/sequences/
.
 [3]

Sloane (N. J. A.) and Plouffe (Simon). 
The encyclopedia of integer sequences. 
Academic Press Inc., San Diego, CA, 1995, xiv+587p.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.