Generating functions for generating trees.
Certain families of combinatorial objects admit recursive descriptions in terms of generating trees: each node of the tree corresponds to an object, and the branch leading to the node encodes the choices made in the construction of the object. Generating trees lead to a fast computation of enumeration sequences (sometimes, to explicit formulae as well) and provide efficient random generation algorithms. We investigate the links between the structural properties of the rewriting rules defining such trees and the rationality, algebraicity, or transcendence of the corresponding generating function.
Introduction
Only the simplest combinatorial structures - like binary strings, permutations, or pure involutions
(i.e., involutions with no fixed point) - admit product decompositions. In that case,
the
set\Omega n of objects of size n is isomorphic to a product
Two properties result from such a strong decomposability property: (i) enumeration is easy,
since the cardinality
of\Omega n is e 1 random generation is efficient since it reduces to a
sequence of random independent draws from intervals. A simple infinite tree, called a uniform
generating tree is determined by the e i : the root has degree e 1 , each of its e 1 descendents has
degree e 2 , and so on. This tree describes the sequence of all possible choices and the objects
of size n are then in natural correspondence with the branches of length n, or equivalently
with the nodes of generation n in the tree. The generating tree is thus fully described by its
root degree (e 1 ) and by rewriting rules, here of the special form,
where the power notation is used to express repetitions. For instance binary strings, permu-
tations, and pure involutions are determined by
Corresponding author.
A powerful generalization of this idea consists in considering unconstrained generating
trees where any set of rules
is allowed. Here, the axiom specifies the degree of the root, while the productions e i;k
list the degrees of the k descendents of a node labeled k. Following Barcucci, Del Lungo,
Pergola and Pinzani, we call \Sigma an ECO-system (ECO stands for "Enumerating Combinatorial
Objects"). Obviously, much more leeway is available and there is hope to describe a much
wider class of structures than those corresponding to product forms and uniform generating
trees.
The idea of generating trees has surfaced occasionally in the literature. West introduced it
in the context of enumeration of permutations with forbidden subsequences [27, 28]; this idea
has been further exploited in closely related problems [6, 5, 12, 13]. A major contribution in
this area is due to Barcucci, Del Lungo, Pergola, and Pinzani [4, 3] who showed that a fairly
large number of classical combinatorial structures can be described by generating trees.
A form equivalent to generating trees is well worth noting at this stage. Consider the walks
on the integer half-line that start at point (s 0 ) and such that the only allowable transitions are
those specified by \Sigma (the steps corresponding to transitions with multiplicities being labeled).
Then, the walks of length n are in bijective correspondence with the nodes of generation n in
the tree. These walks are constrained by the consistency requirement of trees, namely, that
the number of outgoing edges from point k on the half-line has to be exactly k.
Example 1. 123-avoiding permutations
The method of "local expansion" sometimes gives good results in the enumeration of permutations
avoiding specified patterns. Consider for example the set S n (123) of permutations
of length n that avoid the pattern 123: there exist no integers k such that
oe(k). For instance, belongs to S 4 (123) but does not, as
Observe that if - 2 S n+1 (123), then the permutation oe obtained by erasing the entry
n+ 1 from - belongs to S n (123). Conversely, for every oe 2 S n (123), insert the value n+ 1 in
each place that gives an element of S n+1 (123) (this is the local expansion). For example, the
permutation by insertion of 4 in first, second and third
place respectively. The permutation 2134, resulting from 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 oe are the permutations
derived as above. Figure 1(a) presents the first four levels of this tree.
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 labeled k are labeled respectively k
(see [27]). Thus the tree we have constructed is the generating tree obtained
from the following rewriting rules:
The interpretation of this system in terms of paths implies that 123-avoiding permutations
are equinumerous with "walks with returns" on the half-line, themselves isomorphic
to /
Lukasiewicz codes of plane trees (see, e.g., [26, p. 31-35]). We thus recover a classic
result [18]: 123-avoiding permutations are counted by Catalan numbers; more precisely,
(a) (b)

Figure

1: The generating tree of 123-avoiding permutations. (a) Nodes labeled by the per-
mutations. (b) Nodes labeled by the numbers of children.
We shall see below that (certain) generating trees correspond to enumeration sequences
of relatively low computational complexity and provide fast random generation algorithms.
Hence, there is an obvious interest in delineating as precisely as possible which combinatorial
classes admit a generating tree specification. Generating functions condense structural information
in a simple analytic entity. We can thus wonder what kind of generating function can
be obtained through generating trees. More precisely, we study in this paper the connections
between the structural properties of the rewriting rules and the algebraic properties of the
corresponding generating function.
We shall prove several conjectures that were presented to us by Pinzani and his coauthors
in March 1998. Our main results can be roughly described as follows.
Rational systems. Systems satisfying strong regularity conditions lead to rational generating
functions (Section 2). This covers systems that have a finite number of allowed
degrees, as well as systems like (2:a), (2:b), (2:c) and (2:d) below where the labels are
constant except for a fixed number of labels that depend linearly and uniformly on k.
Algebraic systems. Systems of a factorial form, i.e., where a finite modification of the
set is reachable from k, lead to algebraic generating functions (Section 3).
This includes in particular cases (2:f) and (2:g).
Transcendental systems. One possible reason for a system to give a transcendental series
is the fact that its coefficients grow too fast, so that its radius of convergence is zero.
This is the case for System (2:h) below. Transcendental generating functions are also
associated with systems that are too "irregular". An example is System (2:e). We shall
also discuss the holonomy of transcendental systems (Section 4).
Example 2. A zoo of rewriting systems
Here is a list of examples recurring throughout this paper.
(In (2:e), we make use of Iverson's brackets: [P
Notations. From now on, we adopt functional notations for rewriting rules: systems will
be of the form
where s 0 is a constant and each e i is a function of k. Moreover, we assume that all the values
appearing in the generating tree are positive: each node has at least one descendent.
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 In terms of walks,
f n is the number of walks of length n. The generating function associated with the system is
Remark that s 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 also of interest:
We have F
(z). Furthermore, the F k 's satisfy the relation
denotes the number of one-step transitions from j to k.
This is equivalent to the following recurrence for the numbers f n;k ,
that results from tracing all the paths that lead to k in n
Counting and random generation. The recurrence (3) gives rise to an algorithm that
computes the successive rows of the matrix (f n;k ) by "forward propagation": to compute
the (n propagate the contribution f n;j to f n+1;e i (j) for all pairs (i; j) such that
j. Assume the system is linearly bounded : this means that the labels of the nodes that
can be reached in m steps are bounded by a linear function of m. (All the systems given
in Example 2, except for (2:b), are linearly bounded; more generally, systems where forward
jumps are bounded by a constant are linearly bounded.) Clearly, the forward propagation
algorithm provides a counting algorithm of arithmetic complexity that is at most cubic.
For a linearly bounded system, uniform random generation can also be achieved in polynomial
time, as shown in [2]. We present here the general principle.
Let g n;k be the number of walks of length n that start from label k. These numbers are
determined by the recurrence g
that traces all the possible continuations
of a path given its initial step. Obviously, f the axiom of the system. As
above, the g n;k can be determined in time O(n 3 ) and O(n 2 ) storage. random generation
is then achieved as follows: In order to generate a walk of length n starting from state k,
pick up a transition i with probability g n\Gamma1;e i (k) =g n;k , and generate recursively a walk of
length starting from state e i (k). The cost of a single random generation is then O(n 2 ) if
a sequential search is used over the O(n) possibilities of each of the n random drawings; the
time complexity goes down to O(n log n) if binary search is used, but at the expense of an
increase in storage complexity of O(n 3 ) (arising from O(n 2 ) arrays of size O(n) that binary
search requires).
Rational systems
We give in this section three main criteria (and a variation on one of them) implying that the
generating function of a given ECO-system is rational.
Our first and simplest criterion applies to systems in which the functions e i are uniformly
bounded.
Proposition 1 If finitely many labels appear in the tree, then F (z) is rational.
Proof. Only a finite number of F k 's are nonzero, and they are related by linear equations
like Equation (2) above.
Example 3. The Fibonacci numbers
The system [(1); can be also written as
(1)(2)g]. Hence the only labels that occur in the tree are 1 and 2. Eq. (2) gives F 1
Finally,
the well-known Fibonacci generating function. 2
None of the systems of Example 2 satisfy the assumptions of Proposition 1. However, the
following criterion can be applied to systems (2:a) and (2:b).
Proposition 2 Let oe is an affine function of k, say
fi, then the series F (z) is rational. More precisely:
Proof. Let denote the labels of the f n nodes at level n. Then
We know that f . The result follows.
Example 4. Bisection of Fibonacci sequence
The system [(2);
\Delta, the
generating function for Fibonacci numbers of even index. (Changing the axiom to
leads to the other half of the Fibonacci sequence.) Some other systems, like
lead to the same function F (z) since 2. However, the generating trees
are different, as are the bivariate functions F (z; u). 2
Example 5. Prime numbers and rational generating functions
Amazingly, it is possible to construct a generating tree whose set of labels is the set of prime
numbers but that has a rational generating function F (z). This is a bit unexpected, as
prime numbers are usually thought "too irregular" to be associated with rational generating
functions. For n - 1, let p n denote the nth prime; hence (p
Assume for the moment that the Goldbach conjecture is true: every even number larger than
3 is the sum of two primes. Remember that, according to Bertrand's postulate,
for all n (see, e.g., [23, p. 140]).
For the number 2p is an even number larger than 3. Let q n and r n
be two primes such that 2p In particular, q 2. Consider the
system
It satisfies the criterion of Proposition 2, with 3. Hence, the generating function
of the associated generating tree is
Consequently, the number of nodes at level n is simply f )=2. This can be checked
on the first few levels of the tree drawn in Figure 2.
Now, one can object that the Goldbach conjecture is not proved; however, it is known
that every even number is the sum of at most six primes [22], and a similar example can be
constructed using this result.
Figure

2: A generating tree with prime labels and rational generating function.
Proposition 2 can be adapted to apply to systems that "almost" satisfy the criterion of
Proposition 2, like System (2:c) or (2:d). Let us consider a system of the form
Assume, moreover, that:
(i) the corresponding functions oe 0 and oe 1 are affine and have the same leading coefficient
ff, say oe
exactly m odd labels occur in the right-hand side of each rule, for some m - 0.
Proposition 3 If a system satisfies properties (i) and (ii) above, then
Of course, if fi we recover the generating function of Proposition 2.
Proof. The proof is similar to that of Proposition 2. The only new ingredient is the fact
that, for n - 1, the number of nodes of odd label at level n is mf
System (2:c) satisfies properties (i) and (ii) above with
5. Consequently, its generating function is F
. System (2:d),
although very close to (2:c), does not satisfy property (ii) above, so that Proposition 3 does
not apply. However, another minor variation on the argument of Proposition 2, based on the
fact that the number o n of odd labels at level n satisfies proves the
rationality of F (z).
Alternatively, rationality follows from the last criterion of this section, which is of a
different nature. We consider systems [(s 0 that can be
written as
am and the functions c i are uniformly bounded. Let
(k)g.
Proposition 4 Consider the system (4), and let - all the series
are rational, then so is the series F (z).
Proof. We form an infinite system of equations defining the series F k (z) by writing Eq. (2)
for all k - 1. In particular, for k ? C, we obtain
with F j This part of the system is easy to solve in terms of F
Indeed, for k 2 Z:
where the P i;k are polynomials in z defined by the following recurrence: for all
z
Using (5), we find
According to (6), for all i - C, the series
is a rational function of z and t, of
rational in z. Hence, to prove the rationality of F (z),
it suffices to prove the rationality of the F i (z), for i - C.
Let us go back to the C first equations of our system; using (5), we find, for k - C:
Again,
is a rational function of z and t (the Hadamard product of two
rational series is rational). Thus the series F k (z), for k - C, satisfy a linear system with
rational coefficients: they are rational themselves, as well as F (z).
Examples (2:a), (2:c), (2:d) and (2:e) have the form (4). The above proposition implies
that the first three have a rational generating function. System (2:e) will be discussed in
Section 4, and proved to have a transcendental generating function.
3 Factorial walks and algebraic systems
In this section, we consider systems that are of a factorial form. By this, we mean informally
that the set of successors of (k) is a finite modification of the integer interval
As was detailed in the introduction, ECO-systems can be rephrased in terms of walks over
the integer half-line. We thus consider the problem of enumerating walks over the integer
half-line such that the set of allowed moves from point k is a finite modification of the
integer interval [0; k]. We shall mostly study modifications around the point k (although
some examples where the interval is modified around 0 as well are given at the end of the
section). Precisely, a factorial walk is defined by a finite (multi)set A ae Z and a finite set
specifying respectively the allowed supplementary jumps
(possibly labeled) and the forbidden backward jumps. In other words, the possible moves from
k are given by the rule:
Observe that these walk models are not necessarily ECO-systems, first because we allow labels
to be zero - but 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.
We say that an ECO-system is factorial if a shift of indices transforms it into a factorial
walk. Hence the rules of a factorial ECO-system are of the form
that is,
The generating function F (z) for such an ECO-system, taken with axiom
generating function for the walk model (7), taken with axiom remember
that the rewriting rules defining a generating tree have to obey the additional condition that
a node labeled k has exactly k successors. Taking in (8), this implies that
Taking implies that r so that finally strictly
speaking, either one has a "fake" factorial ECO-system (that is some of its initial rules are
not of the factorial type), either one has a "real" factorial ECO-system and then it is given
by rules of the form
where A is a multiset of integers of cardinality r. For instance, Systems (2:f) and (2:g) are
factorial. We shall prove that all factorial walks have an algebraic generating function. The
result naturally applies to factorial ECO-systems.
We consider again the generating function F (z;
is the
number of walks of length n ending at point k. We also denote by F k (z) the coefficient of
k in this series, and by f n (u) the coefficient of z n . The first ingredient of the proof is a
linear operator M , acting on formal power series in u, that encodes the possible moves. More
precisely, for all n - 0, we will have:
The operator M is constructed step by step as follows.
- The set of moves from k to all the positions 0; described by the operator
L 0 that maps u k to u As L 0 is a linear operator,
we have, for any series g(u):
- The fact that transitions near k are modified, with those of type k
allowed and those of type expressed by a Laurent
polynomial
a
The degree of P is a := maxA, the largest forward jump and b := max(0; \GammaB; \GammaA)
is largest forbidden backward jump or the largest supplementary backward jumps (we
if the set B is empty).
The operator
describes the extension of a walk by one step.
- Finally, the operator M is given by
where fu !0 gh(u) is the sum of all the monomials in h(u) having a negative exponent.
Hence M is nothing but L stripped of the negative exponent monomials, which correspond
to walks ending on the nonpositive half-line. Observe that, for any series g(u),
the only part of L[g](u) that is likely to contain monomials with negative exponents is
Consequently,
and if
Assume for simplicity that the initial point of the walk is 0; other cases follow the same
argument. The linear relation f n+1
Thanks to (9), we can write
where r k (u) is a Laurent polynomials (defined by Equation whose exponents belong to
satisfies the following functional equation:
F (z; u)
z
Let us take an example. The moves
lead to
so that the functional equation defining F (z; u) is
F (z; u)
The second ingredient of the proof, sometimes called the kernel method , seems to belong
to the "mathematical folklore" since the 1970's. It has been used in various combinatorial
problems [10, 18, 20] and in probabilities [14]. See also [8, 9, 21] for more recent and systematic
applications. This method consists in cancelling the left-hand side of the fundamental
functional equation (10) by coupling z and u, so that the coefficient of the (unknown) quantity
F (z; u) is zero. This constraint defines u as one of the branches of an algebraic function of z.
Each branch that can be substituted analytically into the functional equation yields a linear
relation between the unknown series F (z; 1) and F k (z), b. If enough branches can be
substituted analytically, we obtain a system of linear equations, whose solution gives F (z; 1)
and the F k (z) as algebraic functions. From there, an expression for F (z; u) also results in the
form of a bivariate algebraic function.
Let us multiply Eq. (10) by u b (1 \Gamma u) to obtain an equation with polynomial coefficients
(remind that we take if the set B of forbidden backward steps is empty). The new
equation reads K(z; u)F (z; is the kernel of the equation:
This polynomial has degree a u, and hence, admits a are
algebraic functions of z. The classical theory of algebraic functions and the Newton polygon
construction enable us to expand the solutions near any point as Puiseux series (that is, series
involving fractional exponents; see [11]). The a expanded around 0, can be
classified as follows:
- the "unit" branch, denoted by u 0 , is a power series in z with constant term
branches, denoted by u are power series in z 1=b whose first nonzero
term is iz 1=b , with
- a "large" branches, denoted by v a , are Laurent series in z 1=a whose first nonzero
term is iz \Gamma1=a , with i a
In particular, all the roots are distinct. (It is not difficult to check "by hand" the existence
of these solutions: for instance, plugging confirms the
existence of the b small branches.) Note that there are exactly b branches: the unit
branch u 0 and the b small branches As F (z; u) is a series in z with polynomial
coefficients in u, these b having no negative exponents, can be substituted for
u in F (z; u). More specifically, let us replace u by u i in (10): the right-hand side of the
equation vanishes, giving a linear equation relating the b
b. Hence the b branches give a set of b relating
the series. One could solve directly this system, but the following argument is
more elegant.
The right-hand side of (10), once multiplied by u
By construction, it is a polynomial in u of degree b leading coefficient \Gamma1. Hence, it
admits which depend on z. Replacing u by the series u in Eq. (10)
shows that these series are exactly the b roots of R, so that
Y
Let p a := [u a ]P (u) be the multiplicity of the largest forward jump. Then the coefficient of
u a+b+1 in K(z; u) is p a z, and we can write
Y
a
Y
Finally, as K(z; u)F (z;
a z
We have thus proved the following result.
Proposition 5 The generating function F (z; u) for factorial walks defined by (7) and starting
from 0 is algebraic; it is given by (12), where u a ) are the finite (resp.
infinite) solutions at of the equation K(z; and the kernel K is defined by (11).
In particular, the generating function for all walks, irrespective of their endpoint, is
z
Y
and the generating function for excursions, i.e., walks ending at 0, is, for b ! 0:
z
Y
(for the relation becomes F (z;
These results could be derived by a detour via multivariate linear recurrences, and the present
treatment is closely related to [9, 21]; however, our results were obtained independently in
March 1998 [1].
The asymptotic behaviour of the number of n-step walks can be established via singularity
analysis or saddle point methods. The series u i have "in general" a square root singularity,
yielding an asymptotic behaviour of the form A- n n \Gamma3=2 : We plan to develop this study in a
forthcoming paper.
Example 6. Catalan numbers
This is the simplest factorial walk, which corresponds to the
ECO-system (2:f ). The operator M is given by
The kernel is K(z;
2z
, so
that
z
the generating function of the Catalan numbers (sequence M1459 1 ). This result could be
expected, given the obvious relation between these walks and / Lukasiewicz codes. 2
Example 7. Motzkin numbers
This example, due to Pinzani and his co-authors, is derived from the previous one by forbidding
"forward" jumps of length zero. The rule is then
The operator M is
The kernel is K(z; leading to
the generating function for Motzkin numbers (sequence M1184). 2
Example 8. Schr-oder numbers
This example is also due to the Florentine group. The rule is
From Proposition 5, we derive
The coefficients are the Schr-oder numbers (M2898: Schr-oder's second problem). We give
in

Table

1 at the end of the paper a generalization of Catalan and Schr-oder numbers, corresponding
to the rule . This generalized rule has recently been
shown to describe a set of permutations avoiding certain patterns [19]. 2
1 The numbers Mxxxx are identifiers of the sequences in The Encyclopedia of Integer Sequences [24].
The above examples were all quadratic. However, it is clear from our treatment that
algebraic functions of arbitrary degree can be obtained: it suffices that the set of "exceptions"
around k have a span greater than 1. Let us start with a family of ECO-systems where
supplementary forward jumps of length larger than one are allowed.
Example 9. Ternary trees, dissections of a polygon, and m-ary trees
The ECO-system with axiom
is equivalent to the walk
The kernel is K(z; and the generating function
3n
z
counts ternary trees (M2926).
More generally, the system with axiom (m) and rewriting rules
yields the m-Catalan numbers,
1), that count m-ary trees. The kernel
and the generating function F (z; 1) satisfies F (z; In
particular, the 4-Catalan numbers
in [24] (sequence M3587) and count
dissections of a polygon.In the above examples, all backward jumps are allowed. In other words, each of these
examples corresponds to an ECO-system. Let us now give an example where backward
jumps of length 1 are forbidden.
Example 10.
Consider the following modification of the Motzkin rule:
The kernel is now K(z; according to (12), the
series F
infinite at we find that the algebraic equation defining G is:
So far, we have only dealt with walks for which the set of allowed moves was obtained by
modifying the interval [0; k] around k. One can also modify this interval around 0: we shall
see - in examples - that the generating function remains algebraic. However, it is interesting
to note that in these examples, the kernel method does not immediately provide enough
equations between the "unknown functions" to solve the functional equation.
Let us first explain how we modify the interval [0; k] around 0. The walks we wish to count
are still specified by a multiset A of allowed supplementary jumps and a set B of forbidden
backward jumps. But, in addition, we forbid backward jumps to end up in C, where C is a
given finite subset of N . In other words, the possible moves from k are given by the rule
Again, we can write a functional equation defining F (z; u):
where, as above,
the new terms in the equations being
G
F fi+fl (z):
Observe that the first three terms are the same as in the case ;. The equation, once
multiplied by u by (11) and
The kernel is not modified by the introduction of C. As above, it has degree a+b+1 in u, and
admits roots
unknown functions, namely F (z; 1), the F k (z), and the G fl (z), fl 2 C. The degree
of R in u is no longer roots of K that
can be substituted for u in Eq. (13) provide b equations between the b
unknown functions. Additional equations will be obtained by extracting the coefficient of u j
from Eq. (13), for some values of j. In general, we have:
It is possible to construct a finite subset S ae N such that the combination of the b
equations obtained via the kernel method and the equations (14) written for j 2 S determines
all unknown functions as algebraic functions of z - more precisely, as rational functions of z
and the roots u of the kernel. However, this is a long development, and these classes
of walks play a marginal role in the context of ECO-systems. For these reasons, we shall
merely give two examples. The details on the general procedure for constructing the set S
can be found in [7].
Example 11.
This example is obtained by modifying the Motzkin rule of Example 7 around the point 0.
;. The rewriting rule is
The functional equation reads
with G 1 (z). The kernel has a unique finite root at z = 0:
whereas the right-hand side of Eq. (15) contains two unknown functions. Writing Eq. (14)
These two equations allow us to express F 0 and F 1 , and hence G 1 , in terms of F (z; 1):
This equation relates the two unknown functions of Eq. (15). We replace G 1 (z) by the above
expression in (15), so that only one unknown function, namely F (z; 1), is left. The kernel
method finally gives:
Let us choose f2g. The rewriting rule is now:
The functional equation reads
F (z; u)
with G 2 Only three roots, can be
substituted for u in the kernel, while the right-hand side of the equation contains four unknown
Writing (14) for
The second equation is not of much use but, by combining the first and third one, we find
Replacing F 0 (z) by this expression in (16) gives:
We are left with three unknown functions, related by three linear equations obtained by
cancelling the kernel. Solving these equations would give F (z; 1) as an enormous rational
function of z, u in the u i . This implies that F (z; 1) can also be
written as a rational function of z and v j v 1 , the fourth and last root of the kernel. In
particular, F (z; 1) is algebraic of degree at most 4.
In order to obtain directly an expression of F (z; 1) in terms of z and v, we can proceed
as follows. Let R 0 (z; u) denote the right-hand side of Eq. (17). Then R 0 (z; u) is a polynomial
in u of degree 5, and three of its roots are u Consequently, as a polynomial in u, the
kernel K(z; u) divides
Let us evaluate we obtain a polynomial of degree 3 in
u, whose coefficients depend on z; v; F (z; 1); F 1 (z) and G 2 (z). This polynomial has to be
zero: this gives a system of four (dependent) equations relating the three unknown functions
F (z; 1); F 1 (z) and G 2 (z). Solving the first three of these equations yields
Eliminating v between this expression and K(z; equation satisfied by
F (z; 1). 2
4 Transcendental systems
4.1 Transcendence
The radius of convergence of an algebraic series is always positive. Hence, one possible reason
for a system to give a transcendental series is the fact that its coefficients grow too fast, so
that its radius of convergence is zero. This is the case for System (2:h), as proved by the
following proposition.
Proposition 6 Let b be a nonnegative integer. For k - 1, let
Assume that:
1: for all k, there exists a forward jump from k (i.e., e i
2: the sequence (m(k)) k is nondecreasing and tends to infinity.
Then the (ordinary) generating function of the system has radius of convergence 0.
Proof. Let s 0 be the axiom of the system. Let us denote by h n the product m(s
us prove that the generating tree contains at least h n nodes at level
1). At level nb, take a node v labeled k, with nb. Such a node exists thanks to
the first assumption. By definition of m(k), this node v has m(k) sons whose label is at least
As m is non decreasing, v has at least m(s sons of label at least s
Iterating this procedure shows that, at level nb+ i, at least m(s 0
descendents of v have a label larger than or equal to s 0 In particular,
at level n(b + 1) at least h n descendents of v whose label is at least s 0 .
Hence f n(b+1) - h n . But as h n =h goes to infinity with n, the series
z n(b+1) has radius of convergence 0, and the same is true for F
In particular, this proposition implies that the generating function of any ECO-system in
which the length of backward jumps is bounded has radius of convergence 0. Many examples
of this type will be given in the next subsection, in which we shall study whether the corresponding
generating function is holonomic or not. The following example, in which backward
jumps are not bounded, was suggested by Nantel Bergeron.
Example 13. A fake factorial walk
Consider the system with axiom (1) and rewriting rules
applies with bk=2c. Note that the radius of convergence of F (z) is
zero although all the functions e i are bounded, and indeed constant: e i
The series F (z) is of course transcendental. Note, however, that F (z; u) satisfies a functional
equation that is at first sight reminiscent of the equations studied in Section 3:
:The following example shows that Proposition 6 is not far from optimal: an ECO-system
in which all functions e i grow linearly can have a finite radius of convergence.
Example 14.
The system with axiom (1) and rules leads to a generating function
with a positive radius of convergence.
Let us start from the recursion defining the numbers f n;k . We have f
The largest label occurring at level n in the tree is n + 1. Let us introduce the numbers
n. The above recursion can be rewritten as:
We have Hence Eq. (18) implies that for k - 0, the sequence (g n;k ) n is
nondecreasing and reaches a constant value g(k) as soon as n -
Going back to the number f n of nodes at level n, we have

Table

1: The numbers f n;k and g n;k . Observe the convergence of the coefficients.
z n
and hence it suffices to prove that the generating function for the numbers g(k) has a finite
radius of convergence, that is, that these numbers grow at most exponentially.
Writing (18) for
Iterating this formula for i between 1 and k yields
This inequality, together with the fact that implies that for all k - 0, g(k) - e
g(k),
where the sequence e
is defined by e
But the series
k e g(k)z k is rational, equal to (1 \Gamma z) 2 has a finite
radius of convergence. Consequently, the numbers e g(k) and g(k) grow at most exponentially.Algebraic generating functions are strongly constrained in their algebraic structure (by
a polynomial equation) as well as in their analytic structure (in terms of singularities and
asymptotic behaviour). In particular, they have a finite number of singularities, which are
algebraic numbers, and they admit local asymptotic expansions that involve only rational
exponents. A contrario, a generating function that has infinitely many singularities (e.g., a
natural boundary) or that involves a transcendental element (e.g., a logarithm) in a local
asymptotic expansion is by necessity transcendental; see [16] for a discussion of such transcendence
criteria. In the case of generating trees, this means that the presence of a condition
involving a transcendental element is expected to lead to a transcendental generating function.
This is the case in the following example.
Example 15. A Fredholm system
We examine System (2:e), in which the rules are irregular at powers of 2:
2:
This example will involve the Fredholm series h(z) :=
, which is well-known to admit
the unit circle as a natural boundary. (This can be seen by way of the functional equation
from which there results that h(z) is infinite at all iterated square-roots of
unity.) According to Eq. (2), we have, for k ? 3, F k so that
3:
writing Eq. (2) for
For
Solving for F 2 (z) and F 3 (z), then summing
The functions h(z) and F (z) are rationally related, so that F (z) is itself transcendental. The
series h has radius 1, but the denominator of F vanishes before z reaches 1 - actually, before
z reaches 1=2. Hence the radius of F is the smallest root of its denominator. Its value is
easily determined numerically and found to be about 0.360102. 2
4.2 Holonomy
In the transcendental case, one can also discuss the holonomic character of the generating
function F (z).
A series is said to be holonomic, or D-finite [25], 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. Consequently, given a sequence f n , the ordinary
generating function
z n is holonomic if and only if the exponential generating function
holonomic. The set of holonomic series has nice closure properties: the sum or
product of two of them is still holonomic, and the substitution of an algebraic series into an
holonomic one gives an holonomic series. Holonomic series include algebraic series, and have
a finite number of singularities. This implies that Example 15, for which F (z) has a natural
boundary, is not holonomic.
We study below five ECO-systems that, at first sight, do not look to be very different.
In particular, for each of them, forward and backward jumps are bounded. Consequently,
Proposition 6 implies that the corresponding ordinary generating function has radius of convergence
zero. However, we shall see that the first three systems have an holonomic generating
function, while the last two have not. We have no general criterion that would allow us to
distinguish between systems leading to holonomic generating functions and those leading to
nonholonomic generating functions.
Among the systems with bounded jumps, those for which e i belongs to f\Gamma1; 0; 1g
for all i - k have a nice property: the generating function for the corresponding excursions
(walks starting and ending at level 0) can be written as the following continued fraction
where the coefficients a k ; b k and c k are the multiplicities appearing in the rules, which read
Example 16. Arrangements
The system a sequence that starts with
It is not hard to see that the triangular array f n;k+2 is given by
the arrangement numbers k!
so that the exponential generating function (EGF) of the
sequence is
e
This system satisfies the conditions of Proposition 6 with Accordingly,
one has f n - e n!, so that the ordinary generating function F (z) has radius of convergence 0
and cannot be algebraic. However, e
is holonomic, and so is F (z). 2
Example 17. Involutions and Hermite polynomials
The system generates a sequence that starts
with These numbers count involutions: more precisely, one
easily derives from the recursion satisfied by the coefficients f n;k that f n;k is the number of
involutions on n points, of which are fixed. Proposition 6 applies with
The corresponding EGF is
e
and its value at
The polynomials f n
counting involutions on n points are in fact closely
related to the Hermite polynomials, defined by:
Indeed, comparing the above identity with (19) shows that f n
Example 18. Partial permutations and Laguerre polynomials
The rewriting rule a sequence that
starts with 1; 2; 7; 34; 209; ::: (M1795). From the recursion satisfied by the coefficients f n;k ,
we derive that f n;n+k is the number of partial injections of f1; ng into itself in which
are unmatched. From this, we obtain:
e
exp
where L n (u) is the nth Laguerre polynomial. Again, e
The next two systems, as announced, lead to nonholonomic generating functions.
Example 19. Set partitions and Stirling polynomials
Let us consider the system [(1); From the recursion satisfied by the
coefficients f n;k , we derive that f n;k+1 is equal to the Stirling number of the second kind
which counts partitions of n objects into k nonempty subsets. The corresponding EGF is
e
At generating function specializes to
e
z n
This is the exponential generating function of the Bell numbers (M1484). It is known that
log log log n+O(n) (see [20]), and this cannot be the asymptotic behaviour of
the logarithm of the coefficients of an holonomic series (see [29] for admissible types). Hence,
e
F (z; 1), as well as F (z; 1), is nonholonomic. 2
Example 20. Bessel numbers
We study the system with axiom (2) and rewriting rules
3: (20)
We shift the labels by 2 to obtain a walk model with axiom (0) and rules
The corresponding bivariate generating function F (z; u) satisfies the functional differential
equation
F (z; u)
which is certainly not obvious to solve. However, as observed in [15], it is easy to obtain a
continued fraction expansion of the excursion generating function:
is the generating
function of Bessel numbers (M1462) and counts non-overlapping partitions [17]. As F (z;
itself, the series B(z) has radius of convergence zero. The fast increase of B
From [17], we know that log B
prevents F (z;
from being holonomic.
In order to prove that F (z; 1) itself is nonholonomic, we are going to prove that its
coefficients f n have the same asymptotic behaviour as the coefficients of F (z; 0). Clearly,
To find an upper bound for f n , we compare the system (20) (denoted \Sigma 1 below) to the system
1). This system generates a tree with counting
sequence g n . The form of the rules implies that the (unlabeled) tree associated with \Sigma 1 is a
subtree of the tree associated with \Sigma 2 . Hence f n - g n . Comparing \Sigma 2 to the system studied
in the previous example shows that g n is the Bell number B n+1 , the logarithm of which is also
known to be n log log log n+O(n) (see [20]). Hence log f
and this prevents the series F (z; 1) from being holonomic. 2
Axiom System Name Id. Generating Function
Rational OGF OGF
3: Fibonacci M0692 1
even Fibonacci M1439 1\Gammaz
Algebraic OGF OGF
7: Motzkin numbers M1184 1\Gammaz\Gamma
Dissections of a polygon M3587
Holonomic EGF
transcendental OGF
Permutations M1675 1=(1 \Gamma z)
Involutions M1221 e z+ 1z 2
permutations M1795 e z=(1\Gammaz)
problem M1461 e 2z+ 1z 2
Bicolored involutions M1648 e 2z+z 2
Nonholonomic OGF EGF
Bicolored partitions M1662 e 2(e z \Gamma1)

Table

2: Some ECO-systems of combinatorial interest.
A small catalog of ECO-systems
To conclude, we present in Table 2 a small catalog of ECO-systems that lead to sequences
of combinatorial interest. Several examples are detailed in the paper; others are due to West
[27, 28] or Barcucci, Del Lungo, Pergola, Pinzani [4, 6, 5, 3], or are folklore. Each of them is
an instance of application of our criteria.

Acknowledgements

. We thank Elisa Pergola and Renzo Pinzani who presented us the
problem we deal with in this paper. We are also very grateful for helpful discussions with
Jean-Paul Allouche.



--R

Combinatoire analytique
random generation of trees and other combinatorial objects.
A methodology for plane tree enumeration.
ECO: a methodology for the enumeration of combinatorial objects.
From Motzkin to Catalan permutations.
Permutations avoiding an increasing number of length increasing forbidden subsequences.


Linear recurrences with constant coefficients: the multivariate case.
Enum'eration des graphes planaires
Infinitesimal calculus.
A. combinatorial proof of
Permutations with forbidden subsequences and nonseparable planar maps.
Solutions of functional equations arising in the analysis of two-server queueing models
Combinatorial aspects of continued fractions.
Analytic models and ambiguity of context-free languages

The Art of Computer Programming.
Permutations with forbidden subsequences and a generalized Schr-oder num- ber
Asymptotic enumeration methods.
The irrational chess knight.

The little book of big primes.
The Encyclopedia of Integer Sequences.
Differentiably finite power series.
Enumerative combinatorics
Generating trees and the Catalan and Schr-oder numbers
Generating trees and forbidden subsequences.
Resurrecting the asymptotics of linear recurrences.
--TR
Analytic models and ambiguity of context-free languages
Non-overlapping partitions, continued fractions, bessel functions and divergent series
The little book of big primes
Generating trees and the Catalan and SchroMYAMPERSANDuml;der numbers
Permutations with forbidden subsequences and nonseparable planar maps
Asymptotic enumeration methods
Generating trees and forbidden subsequences
The art of computer programming, volume 1 (3rd ed.)
A methodology for plane tree enumeration
A combinatorial proof of J. West''s conjecture
Random generation of trees and other combinatorial objects
From Motzkin to Catalan permutations
Permutations with forbidden subsequences and a generalized SchrMYAMPERSANDouml;der number
Solutions of Functional Equations Arising in the Analysis of Two Server Queueing Models

--CTR
Martin Klazar, Bell numbers, their relatives, and algebraic differential equations, Journal of Combinatorial Theory Series A, v.102 n.1, p.63-87, April
D. Merlini , R. Sprugnoli , M. C. Verri, Waiting patterns for a printer, Discrete Applied Mathematics, v.144 n.3, p.359-373, 15 December 2004
Anna de Mier , Marc Noy, A solution to the tennis ball problem, Theoretical Computer Science, v.346 n.2, p.254-264, 28 November 2005
M. Bousquet-Mlou , A. Rechnitzer, The site-perimeter of bargraphs, Advances in Applied Mathematics, v.31 n.1, p.86-112, 1 July
Mireille Bousquet-Mlou , Arnaud Jehanne, Polynomial equations with one catalytic variable, algebraic series and map enumeration, Journal of Combinatorial Theory Series B, v.96 n.5, p.623-672, September 2006
Enrica Duchi , Jean-Marc Fedou , Simone Rinaldi, From object grammars to ECO systems, Theoretical Computer Science, v.314 n.1, p.57-95, 25 February 2004
G. Castiglione , A. Frosini , A. Restivo , S. Rinaldi, Enumeration of L-convex polyominoes by rows and columns, Theoretical Computer Science, v.347 n.1-2, p.336-352, November 2005
Mireille Bousquet-Mlou , Marko Petkovek, Walks confined in a quadrant are not always D-finite, Theoretical Computer Science, v.307 n.2, p.257-276, 7 October
Petter Brndn , Toufik Mansour, Finite automata and pattern avoidance in words, Journal of Combinatorial Theory Series A, v.110 n.1, p.127-145, April 2005
walks on a half-line;algebraic generating functions;d-finite generating functions;generating trees