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/(1-d(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 non-crossing 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:
[zn]y(z)=
1
n
[yn-1]F n (y).

Example 2  
y=z(1+y2)   ¾®   y2n+1
=
1
2n+1
æ
è
2n+1
n
ö
ø
,
y=z+zy2+z2y3   ¾®   y2n-1
=
 
å
p
1
2n-1-p
æ
è
2n-1-p
n,n-1-2p,p
ö
ø
.

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 , Fy' (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
[zn]f(z)=
 
å
m³ 1
1
m
[znym-1]Fm (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 Valz(P)=g ³ 0 and Valz,y (Q)=a + b ³ 1. The expansion of the mth power of F is
Fm=
 
å
k
æ
è
m
k
ö
ø
zm-kykPm-kQk.
To avoid the cancellation of the quantity
[znym-1]Fm=[zn-m+kym-1-k]
 
å
k
æ
è
m
k
ö
ø
Pm-kQk,
we must have
n-m+k ³ (m-k)g+ka  and   m-1-k ³ kb.
This entails
m £ n
b+1
a+gb+b
+
a-g-1
a+g b+b
  whence   m £ 2n-1.

Example 3  

Dissections:
y=z+2y2-zy ¾® [zn]y=
 
å
r
1
n+r
æ
è
n+r
r+1,n-r-1,r
ö
ø
(-1)n-r-12r.

2-3 trees (edges and leaves):
y=z+z2y2+z3y3 ¾® [zn]y=
 
å
m
1
m
æ
è
m
n-m+1,5m-3n-2,2n-3m+1
ö
ø
.

2   Proof of Theorem 1

2.1   Formal Proof

Let y(z)=å an zn 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 an,mzn-mum.

From the Lagrange theorem we derive
[um]y(z,u)=
1
m
[ym-1]Qm(y,z).
Thus we obtain
[zn]y(z)=
 
å
m
1
m
[ym-1zn-m]Qm(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 y0 be the unique root of y (y) =0 inside a domain defined by a closed curve g.Then
y0=
1
2ip
ó
õ
 


g
y
y
'
 
(y)
y(y)
.
Since y(z) is a root of y-F(z,y)=0 and (0,0) is an ordinary point of y-F(z,y)=0, a formal application of the lemma gives:
y(z)=
1
2ip
ó
õ
 


g
y
1-F
'
 
y
(z,y)
y-F (z,y)
dy.
A formal application (justified later) of the formula (1-u)-1=1+u+u2+u3+··· entails:
y(z)=
 
å
m³ 0
1
2ip
ó
õ
 


g
'
 
(1-F
'
 
y
(z,y))Fm(z,y)
dy
ym
.     (1)
Using the Cauchy coefficient formula, we derive:
y(z)=
 
å
m³ 1
[ym-1](1-F
'
 
y
(z,y))Fm(z,y).
Still proceeding formally, we finally get the expressions stated in theorem 1:
y(z)
=
 
å
m³ 1
[ym-1]Fm(z,y)-
m
m+1
[ym]Fm+1 (z,y),
 
=
 
å
m³ 1
1
m
[ym-1]Fm(z,y).
Hence
yn=
 
å
m³ 1
1
m
[znym-1]Fm(z,y).

Let us explicit now the contours g and g' used in the computations above. Since the equation y-F(y,z)=0 has a unique solution f(z) tending to 0 with z, there exists r1>0 and r1>0 such that |z|£ r1 implies |f(z)|£ r1 and |fi(z)|> r1 for all other solutions. Consequently
g={y;|y|=r}  for any   0<r<r1.

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, r2 and r2 such that F(z,y)£ K(|z|+|zy|+|y2|) for |z|<r2 and |y|<r2. Since
|z|+|zy|+|y2|<|y| ÜÞ |z|<|y|
1-|y|
1+|y|
,
it follows that:
g
'
 
={(z,y);|y|<r
'
 
,|z|<r}  for any    r
'
 
<min(r1,r2),  with  r=min (r1,r2,r
'
 
1-r
'
 
1+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 square-free, 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 y1,..., yk 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; y1(j)(0)=yi(j)(0)  for all   j=0,..., a-1.
Now, to isolate a specific branch, we perform the change of variables
y=
~
y
 
+a
 
a
z
a
 
+a
 
b
z
b -1
 
Y,
where y~ is the common part of the expansions. The branch Y1=z+ån³ 1 an zn is the unique solution analytic at (0,0) of the equation Y=F (z,Y).

Example 4   Take the generating series of graphs in non-crossing configurations defined by the algebraic equation
y2+(-2-3z+2z2)y+1+3z=0
The expansions of the branches at the origin are:
y1(z) = 1+z+2z2+8z3+48z4+352z5+O(z6)
y2(z) = 1+2z-4z2-8z3-48z4-352z5+O(z6)
The change of variable
y=1+z+zY
results in
z2(-Y+Y2+2z+2zY)=0.
The algebraic function Y implicitly defined by -Y+Y2+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 LATEX by HEVEA.