The HOLONOMIC ANSATZ I. Foundations and Applications to Lattice
Path Counting
By Doron Zeilberger
.pdf
.ps
.tex
Appeared in Annals of Combinatorics 11 (2007), 227-239.
First Written: Feb. 2, 2006.
Last update of this webpage (not article): Dec. 26, 2017
This paper is my love-song to my favorite pastime: guessing.
But even though I love to guess, I am really bad at it, so
I had to teach my beloved Shalosh how to guess,
and it loves it, and does a great job.
Important: This article is accompanied by Maple
package
GuessHolo2.txt
that automatically guesses holonomic representations to
discrete functions of two variables, with particular
emphasis on applications to counting the number of latttice
paths in the plane with an arbitrary set of steps, and
GuessHolo3 that does the above for functions of three
variables and walks in the 3D positive orthant.
Sample Input and Output for GuessHolo2
- Input and Output for LatticePathStory
-
To get the pure recurrences for the number of ways
of walking from (0,0) to (m,n) using steps
(1,0),(0,1), and (1,1) [the forward-going Chess King],
the example done in the body of the article,
the input
yields the
output.
-
To get the pure recurrences for the number of ways
of walking from (0,0) to (m,n) using steps
(1,0),(0,1), (2,0), and (0,2) [the number of possible basketball games
whose score was m:n, and there are no 3's],
the input
yields the
output.
-
To get the pure recurrences for the number of ways
of walking from (0,0) to (m,n) using steps
(1,0),(0,1), (1,1), and (2,2)
the input
yields the
output.
-
To get the pure recurrences for the number of ways
of walking from (0,0) to (m,n) using steps
(1,0),(0,1), (1,2), and (2,1)
the input
yields the
output.
- Input and Output for DiagonalStory
-
To get the ordinary recurrences for a(n), the number of ways of walking
from (0,0) to (n,n) without restriction, and for b(n),
number of such paths with the ballot restriction, as well
as their asymptotics and
the asymptotic expression for the probability that a lattice
path chosen uniformly at random stays in the "good" part,
using the steps
(0,1) and (1,0)
the input
yields the
output.
-
To get the ordinary recurrences for a(n), the number of ways of walking
from (0,0) to (n,n) without restriction, and for b(n),
number of such paths with the ballot restriction, as well
as their asymptotics and
the asymptotic expression for the probability that a lattice
path chosen uniformly at random stays in the "good" part,
using the steps
(0,1),(1,0) and (1,1),
the input
yields the
output.
-
To get the ordinary recurrences for a(n), the number of ways of walking
from (0,0) to (n,n) without restriction, and for b(n),
number of such paths with the ballot restriction, as well
as their asymptotics and
the asymptotic expression for the probability that a lattice
path chosen uniformly at random stays in the "good" part,
using the steps
(0,1),(1,0) and (2,0),(0,2)
the input
yields the
output.
[Note that the probability that in the basketball game whose score
was n:n the home team was never losing during the
game is asymptotically roughly 1.0481/n, slightly more the
corresponding figure for a soccer game, that is 1/n]
-
To get the ordinary recurrences for a(n), the number of ways of walking
from (0,0) to (n,n) without restriction, and for b(n),
number of such paths with the ballot restriction, as well
as their asymptotics and
the asymptotic expression for the probability that a lattice
path chosen uniformly at random stays in the "good" part,
using the steps
(0,1),(1,0) and (1,1),(2,2)
the input
yields the
output.
[Note that the probability of never being above the diagonal is now
roughly 1.53726/n]
-
To get the ordinary recurrences for a(n), the number of ways of walking
from (0,0) to (n,n) without restriction, and for b(n),
number of such paths with the ballot restriction, as well
as their asymptotics and
the asymptotic expression for the probability that a lattice
path chosen uniformly at random stays in the "good" part,
using the steps
(0,1),(1,0),(0,2),(2,0), and (1,1)
the input
yields the
output.
[Note that the probability of never being above the diagonal is now
roughly 1.251/n]
- Input and Output for ReciPolStory
-
To get pure recurrences for F(m,n), the coefficient of
x**m*y**n in the Maclaurin expansion of
1/(1-x-y+2xy),
the input
yields the
output.
-
To get pure recurrences for F(m,n), the coefficient of
x**m*y**n in the Maclaurin expansion of
1/(1-x-y+2x**2+3y**2),
the input
yields the
output.
-
To get pure recurrences for F(m,n), the coefficient of
x**m*y**n in the Maclaurin expansion of
1/(1-x-y+5*x*y+5x**2+2y**2),
the input
yields the
output.
Sample Input and Output for GuessHolo3