Coefficients of Algebraic Series
Philippe Flajolet
LIP6 and INRIA
Algorithms Seminar
June 15, 1998
[summary by Cyril Chabaud]
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 aim of this talk is to provide closed form formulæ for the
coefficients of algebraic series using a general method involving
finite sums of multinomials.
We start by giving an example of an algebraic series encountered in
combinatorics.
Example 1
General planar trees without unary nodes can be described by
D = o + o( D D)+o( D
D D)+··· .
The generating series enumerating the external nodes is a branch of
the algebraic function defined by the following equation:
d(z)=z+d(z)^{2}/(1d(z))
and the coefficients of series d(z) are known to be the Schröder
numbers, for which we give a closed form expression in the third
example while treating dissections of noncrossing configurations.
1 Form of Coefficients
The coefficients of rational generating functions satisfy linear
recurrences with
constant coefficients and they can be easily given a closed form
expression in terms of exponential polynomials.
In general, algebraic generating functions satisfy linear differential
equations with polynomial coefficients leading to
linear recurrences with polynomial coefficients. One may wonder
whether it is possible to obtain a finite index formula for the coefficients of
algebraic generating series.
The answer is yes. The simplest case is when the series
y(z) satisfies an equation of the form y=zF (y) with F
analytic at 0. Typically,
the coefficients of such series can be given an explicit form using
the Lagrange inversion theorem:
[z^{n}]y(z)= 

[y^{n1}]F ^{n} (y). 
Example 2
y=z(1+y^{2}) 
¾® 
y_{2n+1} 

y=z+zy^{2}+z^{2}y^{3} 
¾® 
y_{2n1} 

The following theorem provides closed form formulæ for a larger class
of algebraic generating functions using a similar approach.
Theorem 1
Let F (z,y) be a bivariate polynomial such that F (0,0)=0 ,
F_{y}^{'} (0,0)=0 and Val(F (z,0))>0, where
Val denotes the valuation in y and z. Consider the
algebraic function implicitly defined by f(z)=F (z,f(z)).
Then the coefficients of f(z) are given by
[z^{n}]f(z)= 



[z^{n}y^{m1}]F^{m} (z,y). 
Note that, as we have seen in the examples, the powers of
F induce
multinomial expansions and the valuation condition on F gives rise to
finite sums of these expansions.
Indeed, F (z,y) can be expressed as F (z,y)=zP(z)+yQ(z,y)
where Val_{z}(P)=g ³ 0 and Val_{z,y}
(Q)=a + b ³ 1. The expansion of the mth
power of F is
F^{m}= 


z^{mk}y^{k}P^{mk}Q^{k}. 
To
avoid the cancellation of the quantity
[z^{n}y^{m1}]F^{m}=[z^{nm+k}y^{m1k}] 


P^{mk}Q^{k}, 
we must have
nm+k ³ (mk)g+ka and m1k ³ kb.
This entails
Example 3
Dissections:
y=z+2y^{2}zy ¾®
[z^{n}]y= 



(1)^{nr1}2^{r}.

23 trees (edges and leaves):
y=z+z^{2}y^{2}+z^{3}y^{3} ¾®
[z^{n}]y= 



.

2 Proof of Theorem 1
2.1 Formal Proof
Let y(z)=å a_{n} z^{n} be the generating series implicitly defined by
the functional equation y(z)=F(z,y)=zQ(z,y). We introduce a parameter u
such that y(z,u)=uQ(z,y(z,u)). The expression of y is now
y(z,u)=å_{n,m} a_{n,m}z^{nm}u^{m}.
From the Lagrange theorem we derive
[u^{m}]y(z,u)= 

[y^{m1}]Q^{m}(y,z). 
Thus we obtain
[z^{n}]y(z)= 



[y^{m1}z^{nm}]Q^{m}(y,z). 
2.2 Analytic Part of the Proof
The following lemma is a classical formula derived from residue computation.
Lemma 1
Let y (y) be analytic and y_{0} be the unique root of y (y) =0
inside a domain defined by a closed curve g.Then
Since y(z) is a root of yF(z,y)=0 and (0,0) is an ordinary
point of yF(z,y)=0, a formal application of the lemma gives:
A formal application (justified later) of the formula
(1u)^{1}=1+u+u^{2}+u^{3}+··· entails:

y(z)= 


ó õ 

(1F 

(z,y))F^{m}(z,y) 

.
(1) 
Using the Cauchy coefficient formula, we derive:
y(z)= 

[y^{m1}](1F 

(z,y))F^{m}(z,y). 
Still proceeding formally, we finally get the expressions stated in
theorem 1:
y(z) 
= 

[y^{m1}]F^{m}(z,y) 

[y^{m}]F^{m+1}
(z,y), 



Hence
y_{n}= 


[z^{n}y^{m1}]F^{m}(z,y). 
Let us explicit now the contours g and g^{'} used in the
computations above.
Since the equation yF(y,z)=0 has a unique solution f(z) tending
to 0 with z, there exists r_{1}>0 and r_{1}>0 such that
z£ r_{1} implies f(z)£ r_{1} and f_{i}(z)> r_{1} for all other
solutions. Consequently
g={y;y=r} for any 0<r<r_{1}.
The expansion that leads to formula (1) requires the
condition F(z,y)<y around y=0.
Consequently, the conditions on F(z,y) around the origin imply
that there exist constants K, r_{2} and r_{2} such that
F(z,y)£ K(z+zy+y^{2}) for z<r_{2} and y<r_{2}.
Since
z+zy+y^{2}<y ÜÞ z<y 

, 
it
follows that:
g 

={(z,y);y<r 

,z<r} for any 
r 

<min(r_{1},r_{2}), with r=min 
(r_{1},r_{2},r 


). 
3 General Case
Let y be the function implicitly defined by the algebraic equation
P(z,y)=0 where P is supposed to be squarefree, and assume this
equation has several analytic solutions at the
origin.
We present here an analytic technique designed to isolate
the appropriate branch by giving more information. Actually, it consists in
a change of variable that leads to an equation of the form
Y=F(z,Y) fulfilling the conditions of theorem 1.
Let y_{1},..., y_{k} be the solutions analytic at the origin of the
algebraic equation P(z,y)=0. To distinguish all these branches at the
origin, we specify a the maximum integer such that
$ i; y_{1}^{(j)}(0)=y_{i}^{(j)}(0) for all j=0,...,
a1.
Now, to isolate a specific branch, we perform the change of variables
where y^{~} is the common part of the expansions. The branch
Y_{1}=z+å_{n³ 1} a_{n} z^{n} is the unique solution analytic
at (0,0) of the equation Y=F (z,Y).
Example 4
Take the generating series of graphs in noncrossing configurations
defined by the algebraic equation
y^{2}+(23z+2z^{2})y+1+3z=0
The expansions of the branches at the origin
are:
y_{1}(z) 
= 1+z+2z^{2}+8z^{3}+48z^{4}+352z^{5}+O(z^{6}) 
y_{2}(z) 
= 1+2z4z^{2}8z^{3}48z^{4}352z^{5}+O(z^{6}) 
The change of variable
y=1+z+zY
results in
z^{2}(Y+Y^{2}+2z+2zY)=0.
The algebraic function Y implicitly defined by Y+Y^{2}+2z+2zY=0 has
only one branch tending to 0 at the origin and the general form of
this equation is
in the scope of theorem 1.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.