Solving Discrete Initial- and Boundary-Value 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 constant-coefficient recurrence
always has a rational generating function, this is no longer true in
the multivariate case where this generating function can be
non-rational, non-algebraic, and even non-D-finite. Nevertheless,
there are important cases where the solution can be computed exactly
in terms of algebraic functions. Examples include many lattice-path
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 Bousquet-Mé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 well-known 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 an,k be the number of ways to reach (n,k).
Thus, one has the relation
an,0=a0,k=1 (for n,k³ 0) and the recurrence
an,k=an-1,k+an,k-1+an-1,k-1 (for
n,k³1). Then, the generating function is
Of course there is an explicit formula for the coefficients (often
referred to as Delannoy numbers1), namely an,k=åi=0n () ()
which translates all the possible choices to perform i moves of the
type (1,1), n-i moves of the type (1,0) and k-i 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 an,k's
are known for n£ 1 or k£ 1. Petkovsek proved that
F(x,y)=å an,kxn yk is irrational [10] and a
forthcoming article by Bousquet-Mélou and Petkovsek should show
that F is in fact non D-finite.
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
Zd or Cd, that is n=(n1,...,nd) and x=(x1,...,xd). Let H={h1,...,hk} 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ÜÞ(p-q Î 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 well-founded in Nd;
- 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
an,k=an-1,k+2+an+2,k-1 (for n,k³ 1),
where the an,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 an xn with an Î K and xn=x1n··· xdn. A function F(x) is called rational
if there exist two polynomials P and Q in K[x]\{0} such that QF-P=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 D-finite
if there exist polynomials Pi,j in K[x] such that
with Pi,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 finite-dimensional over K(x).
D-finite 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 Fs of the
recurrence (1),
which rewrites
Q(x) Fs(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 Fs for generic x:
Typically, the function U(x) is the sum of m unknown
multivariate functions Fi(x1,...,xd-1); thus cancelling the
kernel with m different values for xd (which then become
functions of (x1,...,xd-1)) yields a system which allows to
make explicit the Fi'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 Fs(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 Fs(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 ai,j of paths
from (0,0) to (i,j) satisfy the recurrence
ai,j=ai-1,j-1+ai-1,j+1 (for m,n³ 1), a0,0=1 and
ai,j=0 elsewhere. This leads to the functional equation
(y-x-xy2)Fs(x,y)=y-U(x). Applying the kernel method yields
A transcendental and D-finite 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·
An/(G(1-r)nr) 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-(d2-1)/2) is in Q((p)1/2 ) but not in Q(p(d-1)/2). Thus, the generating function of Young
tableaux of height at most d is transcendental (for d³ 3) and
D-finite. Due to well-known one-to-one correspondences, this result
extends from Young tableaux to ballot problems and involutions
avoiding long increasing subsequences.
A non-D-finite and hypertranscendental example
The numbers am,n defined by
am,n=am+1,n-2+am-2,n+1-am-1,n-1, if m,n³ 2,
a1,1=-1, and am,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 am,2 xm+1; one then has
This equation gives x3-G(x)-G(x2)=0 which leads by iteration
to G(x)=x3åi³ 0 (-i)i x2i.
This kind of lacunary series cannot be D-finite.
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?,
D-finite?, ...). 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 D-finite 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.uni-lj.si/~petkovsek/
.
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]
-
Bousquet-Mélou (Mireille). --
Multi-statistic enumeration of two-stack 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. 115--162.
- [4]
-
Fayolle (G.) and Iasnogorodski (R.). --
Solutions of functional equations arising in the analysis of
two-server queueing models. In Performance of computer systems (Proc.
Fourth Internat. Sympos. Modelling Performance Evaluation Comput. Systems,
Vienna, 1979), pp. 289--303. --
North-Holland, Amsterdam, 1979.
- [5]
-
Flajolet (Philippe). --
Analytic models and ambiguity of context-free languages. Theoretical Computer Science, vol. 49, n°2-3, 1987,
pp. 283--309. --
Twelfth international colloquium on automata, languages and
programming (Nafplion, 1985).
- [6]
-
Knuth (Donald E.). --
The art of computer programming. Vol. 1: Fundamental
algorithms. --
Addison-Wesley, 1968.
- [7]
-
Lipshitz (L.). --
D-finite power series. Journal of Algebra, vol. 122,
n°2, 1989, pp. 353--373.
- [8]
-
Loxton (J. H.) and Van der Poorten (A. J.). --
A class of hypertranscendental functions. Aequationes
Mathematicae, vol. 16, n°1-2, 1977, pp. 93--106.
- [9]
-
Merlini (Donatella) and Verri (M. Cecilia). --
Generating trees and proper Riordan arrays. Discrete
Mathematics, vol. 218, n°1-3, 2000, pp. 167--183.
- [10]
-
Petkovsek (M.). --
The irrational chess knight. In Formal Power Series and
Algebraic Combinatorics, pp. 513--522. --
1998. Proceedings of FPSAC'98, June 1998, Toronto.
- [11]
-
Petkovsek (Marko) and Bousquet-Mélou (Mireille). --
Linear recurrences with constant coefficients: the multivariate case.
Discrete Mathematics, vol. 225, n°1-3, 2000,
pp. 51--75.
- [12]
-
Stanley (R. P.). --
Differentiably finite power series. European Journal of
Combinatorics, vol. 1, n°2, 1980, pp. 175--188.
- 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
1898, 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 LATEX by
HEVEA.