Solving Discrete Initial and BoundaryValue Problems
Marko Petkovsek
University of Ljubljana
Algorithms Seminar
October 4, 1999
[summary by Cyril Banderier]
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
Multivariate linear recurrences appear in such diverse fields of
mathematics as combinatorics, probability theory, and numerical
resolution of partial differential equations. Whereas in the
univariate case the solution of a constantcoefficient recurrence
always has a rational generating function, this is no longer true in
the multivariate case where this generating function can be
nonrational, nonalgebraic, and even nonDfinite. Nevertheless,
there are important cases where the solution can be computed exactly
in terms of algebraic functions. Examples include many latticepath
problems such as the enumerations of Dyck, Motzkin, and Schroeder
paths, determining the cardinality of various free algebras, and (in
some cases) the enumeration of permutations with a forbidden pattern.
This is joint work by Marko Petkovsek and Mireille BousquetMélou
(CNRS, Université de Bordeaux I).
1 Multivariate Linear Recurrences
Combinatorics are often synonymous of recurrences; whereas a quite
impressive apparatus is available for univariate recurrences,
multivariate recurrences are always a strange and mysterious world.
Whereas a linear recurrence with constant coefficients necessarily
leads to a rational generating function in one variable, this is no
longer true in several variables (even with very regular boundary
conditions). In fact, the set of multivariate generating functions
with such a recurrence intersects almost all of the wellknown classes
of functions. Here are two examples leading to two kinds of
generating functions.
A rational generating function: the chess king
recurrence
On the square lattice, one performs a walk, beginning at (0,0),
made of a sequence of jumps (1,0), (1,1) or (0,1).
Let a_{n,k} be the number of ways to reach (n,k).
Thus, one has the relation
a_{n,0}=a_{0,k}=1 (for n,k³ 0) and the recurrence
a_{n,k}=a_{n1,k}+a_{n,k1}+a_{n1,k1} (for
n,k³1). Then, the generating function is
F(x,y)= 

a_{n,k} x^{n} y^{k}= 

. 
Of course there is an explicit formula for the coefficients (often
referred to as Delannoy numbers^{1}), namely a_{n,k}=å_{i=0}^{n} () ()
which translates all the possible choices to perform i moves of the
type (1,1), ni moves of the type (1,0) and ki moves of the
type (0,1).
An irrational generating function: the chess knight
recurrence
This time, one performs jumps (1,2) or (2,1) and the a_{n,k}'s
are known for n£ 1 or k£ 1. Petkovsek proved that
F(x,y)=å a_{n,k}x^{n} y^{k} is irrational [10] and a
forthcoming article by BousquetMélou and Petkovsek should show
that F is in fact non Dfinite.
A first problem which can arise in several variables is that initial
conditions have to be correctly set in order to establish the
uniqueness of the solution to a linear recurrence with constant
coefficients. The second problem is what the nature of the solutions
is, and how to compute them.
2 Existence and Uniqueness of the Solution
Henceforth, we view all the indices (and variables) as tuples of
Z^{d} or C^{d}, that is n=(n_{1},...,n_{d}) and x=(x_{1},...,x_{d}). Let H={h_{1},...,h_{k}} be the set
of allowed jumps. Let s be the ``true'' starting
point of the walk, that is the point after which all jumps are
possible and where one does not care about the side conditions
anymore. The kind of recurrence under study is formalized by

a 

=

ì í î 
f(n) 
for n³0 and n¬ ³s, 

for n³s. 


(1) 
The first part of the recurrence stands for the ``initial'' conditions
(that is, the boundary values) and the second part reflects the
different shifts (or jumps) allowed.
Definition 1 [Dependency relation]
Define ® by
p®qÜÞ(pq Î H and q ³ s).
Note ®^{+} the transitive closure of ®.
Thus, p®q simply means that there is a ``step'' from p
to q, with q outside of the ``boundary value'' area,
and p®^{+}q means that there is a sequence of steps from p to q.
Theorem 1
The following are equivalent:

the transitive closure ®^{+} of the
dependency relation ® is wellfounded in N^{d};
 there exists u>0 such that u· h<0
for any ``jump vector'' hÎ H;
 the convex hull of H does not intersect R_{+}^{d}.
The last point is the most efficient for proving uniqueness of the
solution of recurrence (1) as it is easy to check.
For example, for the chess king problem, one has a recurrence
with starting point s=(1,1) and the set of allowed jumps is
H={(1,0),(1,1),(0,1)},
the intersection of
the convex hull of H (a triangle in the lower left quarter)
and of R_{+}^{2} is clearly the empty set; thus there is a unique
solution to the recurrence.
Considering now the recurrence
a_{n,k}=a_{n1,k+2}+a_{n+2,k1} (for n,k³ 1),
where the a_{n,k}'s are known (for n=0 or k=0),
where the starting point is s=(1,1) and where the set of allowed jumps
H={(1,2),(2,1)}, gives an example for which the convex hull
intersects R_{+}^{2}; thus uniqueness does not hold.
As a last example, one shows that
the chess knight problem has a unique solution:
the starting point is s=(2,2) and the set of allowed jumps is
H={(2,1),(1,2)},
whose convex hull does not intersect R_{+}^{2}.
3 Nature of the Solution
Let K be a field of characteristic zero. Consider F(x)=å_{n³ 0} a_{n} x^{n} with a_{n} Î K and x^{n}=x_{1}^{n}··· x_{d}^{n}. A function F(x) is called rational
if there exist two polynomials P and Q in K[x]\{0} such that QFP=0. The function F is called
algebraic if there exists PÎ K[x,t]\{0} such
that P(x,F(x))=0. The function F is called Dfinite
if there exist polynomials P_{i,j} in K[x] such that
P_{i,k}(x) 

+...+P_{i,0}(x)


=0

with P_{i,j}¹0 for at least one j for each i=1,2,...,d. An
equivalent definition states that the space spanned by all the
derivatives of F is finitedimensional over K(x).
Dfinite functions have nice closure properties and are related to a
lot of combinatorial problems (see Stanley's article [12]
and Lipshitz's article [7]).
Definition 2 [Apex] The apex of H is the componentwise maximum
of H È {0}.
For example, for the chess knight problem, one has
H={(2,1),(1,2)} so the apex is (1,1) (and the starting
point is (2,2)). If H={(2,1),(1,2)}, then the apex is (0,2).
An important ingredient in the proof of the two theorems stated
hereafter is the kernel method. Let us detail this point:
one wants to make explicit the solution F_{s} of the
recurrence (1),
which rewrites
Q(x) F_{s}(x)=K(x)U(x)
where K stands for the known initial conditions
and U stands for the unknown initial conditions.
Q is called the kernel.
The kernel method consists in cancelling the kernel
Q(x) by a choice of algebraic values a of x,
thus one gets a system of equations K(a)U(a)=0. Solving
this system generally allows to make U explicit.
This provides F_{s} for generic x:
Typically, the function U(x) is the sum of m unknown
multivariate functions F_{i}(x_{1},...,x_{d1}); thus cancelling the
kernel with m different values for x_{d} (which then become
functions of (x_{1},...,x_{d1})) yields a system which allows to
make explicit the F_{i}'s. The kernel method has belonged to
mathematical folklore since the 1970's; e.g., it has been used by
combinatorialists [3][6, Sec. 2.2.1, Ex. 4
and 11] and probabilists [4]. There is also some
recent work which makes a deep use of
it [1, 2, 10, 11].
Theorem 2
Assume the apex of H is 0. Then the generating function F_{s}(x)
of the unique solution of recurrence (1)
is rational if and only if the known initial function K(x) itself
is rational.
Theorem 3
Take K=C. Assume the apex of H has at most one positive
coordinate. Then the generating function F_{s}(x) of the unique
solution to the recurrence (1) is algebraic if and only if the
known initial function K(x) itself is algebraic.
An algebraic example: Dyck paths
One performs steps (1,1) or (1,1), the numbers a_{i,j} of paths
from (0,0) to (i,j) satisfy the recurrence
a_{i,j}=a_{i1,j1}+a_{i1,j+1} (for m,n³ 1), a_{0,0}=1 and
a_{i,j}=0 elsewhere. This leads to the functional equation
(yxxy^{2})F_{s}(x,y)=yU(x). Applying the kernel method yields
A transcendental and Dfinite example: Young tableaux
The generating function of
Young tableaux of height at most d
is related to the numbers
Algebraicity would imply asymptotics of the type C·
A^{n}/(G(1r)n^{r}) with C and A algebraic numbers and
r a rational number not in {1,2,3,...} (classical result from
singularity analysis [5]). In our case, for odd d>1,
r is an integer and for even d>2,
G(1(d^{2}1)/2) is in Q((p)^{1/2} ) but not in Q(p^{(d1)/2}). Thus, the generating function of Young
tableaux of height at most d is transcendental (for d³ 3) and
Dfinite. Due to wellknown onetoone correspondences, this result
extends from Young tableaux to ballot problems and involutions
avoiding long increasing subsequences.
A nonDfinite and hypertranscendental example
The numbers a_{m,n} defined by
a_{m,n}=a_{m+1,n2}+a_{m2,n+1}a_{m1,n1}, if m,n³ 2,
a_{1,1}=1, and a_{m,n}=0 elsewhere, actually belong
to {0,1,1} and correspond to a nice ``fractal'' lozenge pattern
(see the ``diamond figure'' in [11]). Let G(x)=å_{m³
2} a_{m,2} x^{m+1}; one then has
F_{s}(x,y)= 

a_{m,n}x^{m2}y^{n2}= 
xyG(x)G(y) 

(xy^{2})(yx^{2}) 

. 
This equation gives x^{3}G(x)G(x^{2})=0 which leads by iteration
to G(x)=x^{3}å_{i³ 0} (i)^{i} x^{2}^{i}.
This kind of lacunary series cannot be Dfinite.
A stronger result gives that G is in fact
hypertranscendental [8],
which means that there exists no algebraic differential equation
P(z,G,G',...,G^{(n)})=0.
4 Conclusion
This talk gave a bestiary of solutions for linear multivariate
recurrences with constant coefficients. In two dimensions, it covers
the theory of Riordan arrays [9] (objects related to the
Lagrange inversion formula). Even in two dimensions, it can be
difficult to get the status of the generating function (algebraic?,
Dfinite?, ...). The main possible proofs are: in the algebraic
case, the key point is the kernel method, note that this method also
appears in two other summaries in these proceedings (see Schaeffer's
and Banderier's talks); in the transcendental case, asymptotics allow
to detect the nonalgebraicity, and for non Dfinite functions, one
generally tries bootstrapping and then obtaining an infinite number of
singular points.
Marko Petkovsek has implemented some of the methods presented here
in a Mathematica package multivar, available, as several
author's articles, at http://www.fmf.unilj.si/~petkovsek/
.
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]

BousquetMélou (Mireille). 
Multistatistic enumeration of twostack sortable permutations. Electronic Journal of Combinatorics, vol. 5, n°1,
1998. 
Research Paper 21, 12 pp. (electronic).
 [3]

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. 115162.
 [4]

Fayolle (G.) and Iasnogorodski (R.). 
Solutions of functional equations arising in the analysis of
twoserver queueing models. In Performance of computer systems (Proc.
Fourth Internat. Sympos. Modelling Performance Evaluation Comput. Systems,
Vienna, 1979), pp. 289303. 
NorthHolland, Amsterdam, 1979.
 [5]

Flajolet (Philippe). 
Analytic models and ambiguity of contextfree languages. Theoretical Computer Science, vol. 49, n°23, 1987,
pp. 283309. 
Twelfth international colloquium on automata, languages and
programming (Nafplion, 1985).
 [6]

Knuth (Donald E.). 
The art of computer programming. Vol. 1: Fundamental
algorithms. 
AddisonWesley, 1968.
 [7]

Lipshitz (L.). 
Dfinite power series. Journal of Algebra, vol. 122,
n°2, 1989, pp. 353373.
 [8]

Loxton (J. H.) and Van der Poorten (A. J.). 
A class of hypertranscendental functions. Aequationes
Mathematicae, vol. 16, n°12, 1977, pp. 93106.
 [9]

Merlini (Donatella) and Verri (M. Cecilia). 
Generating trees and proper Riordan arrays. Discrete
Mathematics, vol. 218, n°13, 2000, pp. 167183.
 [10]

Petkovsek (M.). 
The irrational chess knight. In Formal Power Series and
Algebraic Combinatorics, pp. 513522. 
1998. Proceedings of FPSAC'98, June 1998, Toronto.
 [11]

Petkovsek (Marko) and BousquetMélou (Mireille). 
Linear recurrences with constant coefficients: the multivariate case.
Discrete Mathematics, vol. 225, n°13, 2000,
pp. 5175.
 [12]

Stanley (R. P.). 
Differentiably finite power series. European Journal of
Combinatorics, vol. 1, n°2, 1980, pp. 175188.
 1
 Henry Auguste Delannoy was
born in 1833, graduated from the École polytechnique in 1853 and
became a military intendant in the city of Orléans. He wrote a lot
of contributions in recreative mathematics and combinatorics until
1895, the most remarkable being How to use a chessboard in order
to solve some probability problems. After the death of his friend
Lucas, he took in charge the publication of Lucas's last unachieved
books.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.