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

  • Input and Output for LatticePathStory3
    • To get the pure recurrences for the number of ways of walking from (0,0,0) to (m,n,k) using steps (1,0,0),(0,1,0), and (0,0,1),
      the input yields the output.
    • To get the pure recurrences for the number of ways of walking from (0,0,0) to (m,n,k) using steps (1,0,0),(0,1,0), (0,0,1) and (1,1,1),
      the input yields the output.
    • To get the pure recurrences for the number of ways of walking from (0,0,0) to (m,n,k) using steps (1,0,0),(0,1,0), (0,0,1) and (1,1,0),(1,0,1), and (0,1,1)
      the input yields the output.
  • Input and Output for DiagonalStory3
    • To get the ordinary recurrences for a(n), the number of ways of walking from (0,0,0) to (n,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,0,1), (0,1,0), and (0,0,1)
      the input yields the output.
    • To get the ordinary recurrences for a(n), the number of ways of walking from (0,0,0) to (n,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,0,1), (0,1,0), (0,0,1), and (1,1,1)
      the input yields the output.
    • Input and Output for ReciPolStory3
      • To get pure recurrences for F(m,n,k), the coefficient of x**m*y**n*z**k in the Maclaurin expansion of
        1/(1-x-y-z),
        the input yields the output.
      • To get pure recurrences for F(m,n,k), the coefficient of x**m*y**n*z**k in the Maclaurin expansion of
        1/(1-x-y-z+4xyz),
        the input yields the output.

    Doron Zeilberger's List of Papers

    Doron Zeilberger's Home Page