Enumerative Combinatorics: Combinatorial Decompositions
and Functional Equations*

Mireille Bousquet-Mélou

Labri, Université Bordeaux 1 (France)

Algorithms Seminar

March 26 and 27, 2001

[summary by Mathias Vandenbogaert]

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
The primary purpose of this course is the elaboration of methods for providing answers to problems that arise in enumerative combinatorics. The main tool to be used in this respect are (ordinary) generating functions. The objects that will be dealt with are 2-dimensional walks (for which several convexity constraints will be taken into account) and trees. These objects are more generally described as ``decomposable'' objects. A description of the principal combinatorial decompositions by means of functional equations of generating functions will be presented as an equivalent but more synthetic approach to the use of recurrences. The modelling by generating functions of combinatorial structures like trees and walks will be discussed. The same principles hold for maps, animals, and polyominoes. The ``kernel method'' and ``quadratic method'' techniques will be presented. The course will be illustrated by numerous examples.



1  Enumeration Problems and the Way of Solving Them

The approach in solving an enumerative problem consists in a combinatorial step that examines the structure of the objects under consideration, and a step that resolves the recurrence relations or functional equations. By observing the structure of the objects, some (recursively definable) property can be translated into a mathematical, non-tautological information on an, the number of objects of size n. Instead of manipulating recurrence relations, generating functions describing the corresponding functional equations are used:
A(t) =
 
å
n ³ 0
an tn =
 
å
AÎ A
t|A|
is called the ordinary generating function of the combinatorial class A endowed with the size function |.|, where the number of objects an are to be finite. A power series with coefficients in A can be written ån ³ 0 an tn with an Î N. Using counting generating functions it can be noticed that paths of various sorts are invariably algebraic functions, which are defined as solutions of a polynomial equation [11].

There is a simple correspondence between operations on combinatorial classes of objects and combinations of the associated generating functions. This allows us to derive directly functional relations between generating functions starting from definitions of combinatorial objects.
  1. Union: A(z) + B(z) is the enumerative ordinary generating function of A È B. If an and bn are the numbers of objects of size n in A and B respectively, then an+bn is the number of objects of size n in A È B.

  2. Cartesian Product: A(z) B(z) is the enumerative ordinary generating function of A × B. The number of objects of size n in A × B equals the simple convolution å0 £ k £ n akbn-k. Alternatively:
     
    å
    g Î A×B
    		z|g| =
     
    å
    a Î A
     
    å
    b Î B
    		z|a|+|b| = A(z)B(z).


  3. Sequences: (1-A(z))-1 is the enumerative ordinary generating function of sets of objects of
    A = { (B1, B2,...,Bk)  |  B Î B, k ³ 0 } .
    The cardinality of A is |A| = åi=1k |Bi|, and the generating function of A(z) is
    A(t) =
     
    å
    k ³ 0
    		B(t)k= ( 1-B(t) ) -1
    according to the statements of union and cartesian product.
It can be proven that a strong algebraic decomposability prevails for directed lattice paths, which is obtained by a specific technique, the``kernel method'' [2, 6]. The decomposability enables us to determine the location and nature of dominant singularities.

2  Enumeration Example

Fix a finite set of vectors of Z × Z, S = {(a1,b1),...,(am,bm)}. A lattice path or walk relative to S is a sequence v = (v1,...,vn) such that each vj is in S. The geometric realization of a lattice path v = (v1,...,vn) is the sequence of points (P0, P1,...,Pn) such that P0 = (0,0) and Pj-1Pj = vj. The quantity n is referred to as the size of the path. The elements of S are called steps or jumps. For these paths, the solution F(t,u) (which is always an algebraic function of t and u), and combinatorial explanations for the simple formulae obtained from the recurrence relations can be found in [9].

2.1  Dyck paths

A classical example can be given with Dyck paths. A Dyck path of length 2n is a path in the plane from (0,0) to (2n,0) which uses only steps (1,1) (North-East), called rises, and (1,-1) (South-East), called falls. A Dyck path ends on the x-axis and does not go below the x-axis. A Dyck path therefore has even length, with the number of North-East steps equal to the number of South-East steps. A lattice point on the path is called a peak if it is immediately preceded by a North-East step and immediately followed by a South-East step [10]. A peak is at height k if its y-coordinate is k. By Dn we denote the set of all Dyck paths of half-length n. Obviously, D0 = {e}. Every nonempty Dyck path a can be decomposed uniquely in the following manner [7]:
a = ub1 dg1,
when writing u for a North-East step, and d for a South-East step, and where b1 and g1 are possibly empty Dyck paths. This relation implies that
Dn = u D0 d Dn-1 È u D1 d Dn-2 È ... È u Dn-2 d D1 È u Dn-1 d D0,    n ³ 1.

Alternatively, we can write a = b2 ug2 d in a unique manner, where b2 and g2 are possibly empty Dyck paths. This relation implies that
Dn = D0 u Dn-1 d È D1 u Dn-2 d È ... È Dn-2 u D1 d È Dn-1 u D0 d,   n ³ 1.

Both equations have disjoint unions. Thus we obtain
|Dn| = |D0| |Dn-1| + |D1| |Dn-2| + ... + |Dn-2| |D1| + |Dn-1| |D0|,    n ³ 1.

As |D0| = 1, this sequence with n ³ 0 satisfies the same recurrence relation as the sequence (cn)n ³ 0 of Catalan numbers.

2.2  Enumeration of Dyck paths

Let p be a fixed nonnegative integer-valued parameter of a Dyck path, i.e., a mapping from Èn ³ A Dn into {0, 1, 2, ...}. If D is a finite set of Dyck paths, then by D(t) we denote the enumerating polynomial of D relative to the parameter p given by
D(t) =
 
å
n ³ 0
dn tn   with    dn =
 
å
d Î D
tp(d).
D(t) is the generating function for the enumeration of Dyck paths according to semi-length (coded by t). Thus, dn is the enumerating polynomial of the set of all Dyck paths of length n.

The recurrence relation for Dyck paths satisfies
ì
ï
í
ï
î
d2n =
n-1
å
k=0
d2k d2n-2k-2,    n ³ 1,
d0 = 1.



This gives on summation:
D(t) =
 
å
n ³ 0
d2n t2n = 1 + æ
ç
ç
è
 
å
n ³ 1
t2n ö
÷
÷
ø		 æ
ç
ç
è
n-1
å
k=0
d2k d2n-2k-2 ö
÷
÷
ø		 = 1 + t2 D(t)2.
This quadratic equation is easily solved for D(t):
D(t) =
1 ± (1-4t2)1/2
2t2
.
The solution 1 - (1-4t2)1/2/2t2 is chosen in order to ascertain the existence of a Taylor series expansion at t=0. It is known [2, 7, 8, 10, 11] that the number of Dyck paths of length 2n is cn, the nth Catalan number, given by cn = 1/n+1(
2n
n
).

2.3  Enumeration of Dyck prefixes

Let bn,k be the number of prefixes of length n, with final height k. Then
bn,0 = dn    (Dyck paths)                  
F(t,u)
=
 
å
n,t ³ 0
bn,k tn uk Î Q [[t,u]] = æ
ç
ç
è
 
å
n ³ 0
tn ö
÷
÷
ø		 æ
ç
ç
è
n
å
k=0
bn,k uk ö
÷
÷
ø		 Î Q [u][[t]]
                 
which is a series in t whose coefficients are polynomials in u. The last equation is equivalent to:
F(t,u) = 1 + t(u + u-1) F(t,u) - tu-1 F(t,0),
which defines the generating function F(t,u) for these paths, counted by their length (variable t) and their height (variable u). This equation uniquely defines F(t,u) as a power series in t with polynomial coefficients in u.

More constraints can be imposed on such Dyck prefixes.

2.3.1  Dyck Paths with no peaks at height m

Let Gm(x) = ån ³ 0 g(m,n)xn be the generating function for Dyck paths of length 2n with no peaks at height m for some fixed m ³ 1. We proceed to show that
Gm(x) =
1
1-xGm-1(x)
for m ³ 2.
This can be illustrated by a path starting with a North-East step followed by a segment which represents any Dyck path of length 2k, 0 £ k £ n-1, with no peaks at height m-1. This segment is followed, after a South-East step, by a second segment which represents any Dyck path of length 2n-2-2k with no peaks at height m. Therefore
g(m,0) = 1
and
g(m,n) =
n-1
å
k=0
g(m-1,k)g(m,n-1-k) = [xn-1] ( Gm-1(x)Gm(x) ) .
Thus,
Gm(x) = 1+xGm-1(x)Gm(x),
or equivalently,
Gm(x) =
1
1-xGm-1(x)
.

This way, the number of Dyck paths of length 2n with no peaks at height 1 is the Fine number fn for n ³ 0. Obviously, g(1,0) = 1 and g(1,1) = 0. For n ³ 2, a Dyck path of length 2n with no peaks at height 1 has a segment representing any Dyck path of length 2k, 1 £ k £ n-1, and a second segment representing a Dyck path of length 2n-2k-2 with no peaks at height 1. Therefore, for n ³ 2, we have
g(w,n)
=
n-1
å
k=1
ck g(w,n-k-1)
                 
 
= [xn-1] ( C(x)G1(x) ) - g(1,n-1)
                 
 
= [xn] ( xC(x)G1(x) ) - g(1,n-1).
                 
Therefore,
G1(x)
= 1 +
 
å
n ³ 2
g(1,n)xn = 1+xC(x)G1(x) -x-xG1(x) +x
                 
 
= 1 + xG1(x) ( C(x) - 1 ) = 1 + xG1(x)xC2(x).
                 
That is,
G1(x) =
1
1-x2C2(x)
.

2.3.2  No peaks at height 2

Another extension establishes that the number of Dyck paths of length 2n with no peaks at height 2 is the Catalan number cn-1, for n ³ 1. This can be shown [10] using the first extension, so that
G2(x) =
1
1-xG1(x)
=
1
1 - x
C(x)
1+xC(x)
= 1+xC(x).

2.4  Bilateral paths or bridges

A bridge is a path whose end point Pn lies on the x-axis. Given a class C of paths, we let Cn denote the subclass of paths that have size n, and Cn,k Ì C those that have final altitude equal to k. We introduce the corresponding ordinary generating functions:
C(z) =
 
å
n
Cn zn,    uC(z,u) =
 
å
n,k
Cn,k uk zn.
By characterising these generating functions, that are algebraic in the case of bridges, a strong algebraic decomposition prevails, which renders the calculation of the generating function's effective. The decomposability of generating function's makes it possible to extract their singular structure, and to solve the corresponding asymptotic enumeration problems.

The equation corresponding to such a lattice path is:
B(t) = 1 + t2D(t)B(t)+t2B(t)D(t) =
1
1 - 2t2D(t)
.
For D(t) = 1 ± (1-4t2)1/2/2t2,
B(t) =
1
1 - 1 ± (1 - 4t2)1/2
=
1
(1 - 4t2)1/2
=
 
å
n ³ 0
t2n
æ
è
2n
n
ö
ø
.
Alternatively, since (1-4t2)1/2 = 1 - 2t2 - 2t4 + O(t6), we can find for Dyck paths:
D(t) =
1 +1-2t2 -2t4 + O(t6)
2t2
=
1
t2
+ 1 - t2 + O(t4)
or
D(t) =
1 - (1-4t2)1/2
2t2
,
which is the result we found before.

3  Lagrange Inversion Formula

Inherently to the symbolic method, the extraction of coefficients of generating functions defined by functional equations is a frequently occurring problem. For this purpose, the Lagrange Inversion Theorem provides a tool that is commonly used and especially dedicated to the enumeration of trees. This theorem states that given the generating function A(z) = ån ³ 0 an zn for which z = f(A(z)), if f(z) verifies the condition f(0) = 0 and f'(0) ¹ 0, then
an º [zn] A(z) =
1
n
[un-1] æ
ç
ç
è
u
f(u)
ö
÷
÷
ø		 n.
Additionally,
[zn] ( A(z) ) m =
m
n
[un-m] æ
ç
ç
è
u
f(u)
ö
÷
÷
ø		 n
and
[zn] g ( A(z) ) =
1
n
[un-1]g'(u) æ
ç
ç
è
u
f(u)
ö
÷
÷
ø		 n.
By application of the reciprocal function to both sides of the equation z = f(A(z)), it can be noticed that the function A(z) is the reciprocal of f(z). The surprising effect of the inversion theorem resides in the relation it establishes between the powers of a function and the coefficients of the reciprocal function.

3.1  Example: Catalan numbers

The language of Dyck words,
D ={e,x
_
x
 
,xx
_
x
 
_
x
 
,x
_
x
 
x
_
x
 
,...},
satisfies the defining recurrence D = e+xDx_D. This translates to the algebraic (non-commutative) equation
D(x,
_
x
 
) = 1 + x D(x,
_
x
 
)
_
x
 
D(x,
_
x
 
).
Since we have an algebraic and non-ambiguous grammar, we can rewrite the system with commutative variables:
D(x,
_
x
 
) = 1 + x
_
x
 
D(x,
_
x
 
)2.
As we know that the length of the words is always even, we will have n for a total length of 2n, when we only count x (or x_). Thus, we can substitute x_ for e, and x for t.
D(t) = 1 + t ( D(t) ) 2 ÜÞ tD(t)2-D(t)+1=0
By simply solving this second-order equation, we get D(t) = 1 - (1-4t)1/2/2t (the other root is negative, hence not applicable). This solution is to converted into the form D(t) = ån ³ 0 an tn, for which an gives us the number of Dyck words having n letters t (x), hence the number of Dyck words of length 2n. Using Taylor series expansion and applying the Lagrange Inversion Formula, we get Cn
1 - (1-4t)1/2
2t
=
 
å
n ³ 0
1
n+1
æ
è
2n
n
ö
ø
tn

[zn]C(t)=[zn]
1
n
zn-1 (1+z)2n=
1
n
æ
è
2n
n-1
ö
ø
.

4  Algebraic Structures and the Kernel Method

4.1  Algebraic equations

The equation describing sub-diagonal North-East paths,
F(t,u) = 1 + t(u + 1/u) F(t,u) - t/u F(t,0),
belongs to a class of equations that share two properties [3]:
  1. The equation uniquely defines F(t,u) as a power series in t with polynomial coefficients in u. There exist other, non-power-series solutions, for instance the rational function
    F(t,u) =
    2tu -1
    2t ( u - t(u2 + 1) )
    		.
    Hence, any method for solving the recurrence relation above must use the fact that F(t,u) is a power series.
  2. When trying to derive an equation in F(t,0) only from the recurrence relation, we end up with a tautologic expression. In other words, if we first multiply F(t,u) by u and directly set u = 0, this would give us 0 = tF(t,0) - tF(t,0).
It can be noticed that the recurrence relation is linear in F(t,u) and F(t,0), and we can strongly expect its solution to be algebraic and to satisfy
F(t,0) =
1 - (1-4t2)1/2
2t2
=
 
å
n ³ 0
1
n+1
æ
è
2n
n
ö
ø
,
since sub-diagonal walks ending on the main diagonal are well-known to be counted by Catalan numbers.

The generic form of equations that share the above properties, is
P ( F(t,u),F1(t),F2(t),...,Fk(t),t,u ) = 0,
where P is a polynomial in k + 3 variables with real coefficients. We assume that this equation defines uniquely all its unknowns as power series in t: the series Fi(t) have real coefficients, while F(t,u) has its coefficients in R [u]. Rewriting our equation according to this generic form of equations yields:
F(t,u) ( u - t(u2 + 1) ) - u + tF1(t) = 0,
with F1(t) = F(t,0), by setting u = 0.

In solving this instance, we propose to determine fn, the number of excursions of length n and type W, the set of jumps which is a finite subset of Z, via the corresponding bivariate generating function
F(z,u) =
 
å
n,k
fn,k uk zn,
where fn,k is the number of walks of length n and final altitude k. In particular, F(z) = F(z,0). Let -c denote the smallest (negative) value of a jump, and d denote the largest (positive) jump. A functional role is played by the ``characteristic polynomial'' of the walk [1, 2, 11],
S(y) =
 
å
w Î W
yw =
d
å
j = -c
Sj yj,
which is a Laurent polynomial. The bivariate generating function of generalised walks where intermediate values are allowed to be negative is rational:
G(z,u) =
1
1-zS(u)
.

The main result to be proven is the following: for each finite set W Ì Z, the generating function of excursions is an algebraic function that is explicitly computable from W. This problem is solved by an application of the kernel method [2].

4.2  Kernel method

[2]. Let fn(u) = [zn]F(z,u) be the generating function of walks of length n with u recording the final altitude. There is a simple recurrence relating fn+1(u) to fn(u), namely,
fn+1(u) = S(u) fn(u) - rn(u)
where rn(u) is a Laurent polynomial consisting of the sum of all the monomials of S(u)fn(u) that involve negative powers of u:
rn(u) =
-1
å
j=-c
( [uj] S(u)fn(u) ) uj = {u<0}S(u)fn(u),
where {u<0} denotes the singular part of a Laurent expansion:
{u<0}f(z) :=
 
å
j<0
( [uj]f(u) ) uj.

The idea behind the formula is to subtract the effect of those steps that would take the walk below the horizontal axis. Thus the generating function F(z,u) satisfies the fundamental functional equation
F(z,u) = 1 + zS(u)F(z,u) - z{u<0} ( S(u)F(z,u) ) .
Explicitly, we have
F(z,u) = 1 + zS(u)F(z,u) - z
c-1
å
j=0
lj (u) æ
ç
ç
è
dj
d uj
F(z,u) ö
÷
÷
ø		 u=0,
for Laurent polynomials lj(u) that depend on S(u) in an effective way by lj(u) = 1/j!{u<0}ujS(u) [2].

Both equations involve an unknown bivariate generating function F(z,u) and c univariate generating functions, the partial derivatives of F specialized at u=0. In particular, the latter functional equation determines fully the c+1 unknowns. The basic technique is known as ``cancelling the kernel'' and relies on strong analyticity properties.

The equation to be used by the basic kernel technique starts by grouping on one side the terms involving F(z,u). The main principle of the kernel method consists in coupling the values of z and u in such a way that 1-zS(u)=0, so that F(z,u) disappears. Consequently, the ``kernel equation'' 1-zS(u)=0, is rewritten as uc = z(ucS(u)). This kernel equation defines c+d branches of an algebraic function. Coupling z and u by u = ul(z) gives that (z,u) is close to (0,0) where F is bivariate analytic, so that substitution gives
1-z
c-1
å
j=0
lj ( ul(z) ) æ
ç
ç
è
dj
d uj
F(z,u) ö
÷
÷
ø		 u=0,      l=0,...,c-1,
which is a linear system of c equations in c unknowns with algebraic coefficients that determines F(z,0). Therefore, the generating function of excursions is expressible as
F(z) =
(-1)c-1
z S-c
c-1
Õ
l=0
ul(z), where S-c = [u-c]S(u)
is the multiplicity of the smallest element -c Î W.

More generally the bivariate generating function of nonnegative walks is bivariate algebraic and given by
F(z,u) =
1
uc - z ( uc S(u) )
c-1
Õ
l=0
( u - ul(z) ) .

In other words, to make explicit the solution Fs of the recurrence of the sub-diagonal North-East paths, written as F(t,u) (u - t(u2 + 1)) - u + tF1(t) = 0, we rewrite it as Q(x)F(x) = K(x)-U(x) [4], where K stands for the unknown initial conditions, and Q is the kernel:
F(t,u) ( u - t(u2 + 1) ) = u - U(t),
Fs(t) Q(t) = K(t) - U(t).
Again, the kernel method consists in cancelling the kernel Q(x), by handling a choice of algebraic values a of t, which yields a system of equations K(a) - U(a) = 0. Solving this system generally allows to make U explicit. This provides Fs for generic t:
Fs(t) =
K(t) - U(t)
Q(t)
.
The function U(t) is a sum of m unknown multivariate functions Fi(t1,...,td-1). Cancelling the kernel with m different values for td (which then become functions of (t1,...,td-1)) yields a system which allows to make explicit the Fi's.

Regrouping the terms in F(t,u) by the kernel method yields:
Fs(t,u) =
u -
1-(1-4t2)1/2
2t
u - t - tu2
.

4.3  The Quadratic Method

An analogous approach is referred to as the ``quadratic method,'' used to solve equations of the form
z(x,y)2 + P1 ( x,y,z(x,0) ) z(x,y) + P2 ( x,y,z(x,0) ) = 0
with Pi Î F[[x]][y,u], where F is an algebraically closed field of characteristic zero.

Rewrite the equation as
æ
ç
ç
è		 z+
1
2
P1 ö
÷
÷
ø		 2=
1
4
P12-P2=:DÎF[[x]][y,u].
If some y=y0ÎF[[x]] is known to kill z+1/2P1, then this y0 is a double root of D(x,y,u), viewed as a polynomial in (F[[x]][u])[y]. The resultant R(x,u) of D and D/ y with respect to y has to be zero. When we know by an external argument that the quadratic equation admits a series solutions z(x,y)ÎF[[x,y]], for example when it has a combinatorial interpretation, and therefore that z(x,0) is a series in F[[x]], the polynomial equation R(x,z(x,0))=0 delivers this value in F[[x]] for z(x,0).

After substitution, there only remains to solve an equation of the form z2 + P1z + P2 = 0 with Pi Î F[[x]][y]. In [5], necessary and sufficient conditions are derived in order that such an equation has a solution z in either of the rings F[[x]][y] or F[[x,y]]. In view of obtaining them, resume from the relation (z+1/2P1)2=D. Since P1ÎF[[x]][y]ÌF[[x,y]], we get that there is a solution in F[[x]][y] or F[[x,y]], respectively, if and only if D has a square root in the same ring. Again in [5], it is proved that UÎF[[x]][y] has a square root if and only if it factors under the form U=P2R for a polynomial PÎF[x,y] and a series RÎ1+yF[[x]][y]. Therefore, the equation has a solution in F[[x]][y] or F[[x,y]], respectively, if and only if D rewrites under the form P2R for some polynomial P and some series R of the form
R=1+yF[[x]][y]    or     R=1+xyF[[x]][y],     respectively.

References

[1]
Banderier (C.), Bousquet-Mélou (M.), Denise (A.), Flajolet (P.), Gardy (D.), and Gouyou-Beauchamps (D.). -- Generating functions for generating trees. Discrete Mathematics. -- 25 pages. To appear.

[2]
Banderier (Cyril) and Flajolet (Philippe). -- Basic analytic combinatorics of directed lattice paths. -- Available from http://algo.inria.fr/flajolet/Publications/BaFl01.ps.gz, August 2001. 39 pages. Accepted for publication in Theoretical Computer Science.

[3]
Bousquet-Mélou (Mireille). -- On (some) functional equations arising in enumerative combinatorics. -- In preparation. Extended abstract for FPSAC'2001 available from http://dept-info.labri.u-bordeaux.fr/~bousquet/.

[4]
Bousquet-Mélou (Mireille) and Petkovsek (Marko). -- Linear recurrences with constant coefficients: the multivariate case. Discrete Mathematics, vol. 225, n°1-3, 2000, pp. 51--75. -- Formal power series and algebraic combinatorics (Toronto, ON, 1998).

[5]
Brown (William G.). -- On the existence of square roots in certain rings of power series. Mathematische Annalen, vol. 158, 1965, pp. 82--89.

[6]
Cori (Robert) and Richard (Jean). -- Énumération des graphes planaires à l'aide des séries formelles en variables non commutatives. Discrete Mathematics, vol. 2, 1972, pp. 115--162.

[7]
Deutsch (Emeric). -- Dyck path enumeration. Discrete Mathematics, vol. 204, n°1-3, 1999, pp. 167--202.

[8]
Duchon (Philippe). -- On the enumeration and generation of generalized Dyck words. Discrete Mathematics, vol. 225, n°1-3, 2000, pp. 121--135. -- Formal power series and algebraic combinatorics (Toronto, ON, 1998).

[9]
Dvoretzky (A.) and Motzkin (Th.). -- A problem of arrangements. Duke Mathematical Journal, vol. 14, 1947, pp. 305--313.

[10]
Peart (Paul) and Woan (Wen-Jin). -- Dyck paths with no peaks at height k. Journal of Integer Sequences, vol. 4, n°1, 2001. -- Article 01.1.3. 6 pages.

[11]
Sedgewick (Robert) and Flajolet (Philippe). -- An introduction to the analysis of algorithms. -- Addison-Wesley Publishing Co., Reading, MA, 1996.
*
Lecture notes for a course given during the workshop ALÉA'01 in Luminy (France).
This document was translated from LATEX by HEVEA.