A probabilistic method for lattice path enumeration
type: Item
instance of: scholarly article
title: A probabilistic method for lattice path enumeration
zbMATH Open document ID: 0602.05006
DOI: 10.1016/0378-3758(86)90009-1
published in: Journal of Statistical Planning and Inference
publication date: 1986-01-01T00:00:00Z
review text: This paper presents a probabilistic method for obtaining functional equations for lattice path enumeration problems. A number of problems are handled in this manner (about half of these are listed below); for most of them, a combinatorial solution is either offered or cited, but usually the probabilistic solution involves less computation. 1. Given positive integers r and s, find \(d_ n\), the number of paths in the plane with unit steps up or right from (0,0) to \((n,r+sn)\) which never touch the line \(y=r+sx\) except at the endpoint (solved combinatorially in [\textit{S. G. Mohanty}, Lattice path counting and applications (1979; Zbl 0455.60013), p. 9]). 2. Given the boundary lines \(y=x+a\) and \(y=x-b\) for positive integers a, b, find \(f_ n\), the number of paths from (0,0) to \((m,a+m)\) which never touch any boundary points except at the end, and \(g_ n\), the number of analogous paths ending at \((b+n,n).\) 3. Problem 1 except that r and s are arbitrary non-negative rationals, and the path can neither touch or cross the boundary except at the end. The case where r and s are half-integers is treated here, and a special subcase was solved combinatorially in [ibid., p. 10]. 4. Find \(a_{m,n}\), the number of paths with steps (1,0,0), (0,1,0) and (0,0,1) from (0,0,1) to \((m,m+n+1,m+n+1)\) which never touch the planes \(x=z\) or \(y=z\) except at the end (solved combinatorially in [\textit{G. Kreweras}, Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers, Cahiers du B.U.R.O. 6, 5-105 (1965)]). The probabilistic method (which involves computing in two ways the probability that a random walk will touch the boundary somewhere) is illustrated for the first problem only; thenceforth the functional equations obtained by this method are stated immediately and then solved.
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 3970755
zbMATH Keywords: functional equations
zbMATH Keywords: lattice path enumeration problems
author: Ira M. Gessel
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
full work available at URL: 0378-3758(86)90009-1
OpenAlex ID: W2079699338
cites work: Random Walk and Distributions of Rank Order Statistics
cites work: Recurrence of a random walk on the halfline as the generating function for the Catalan numbers
cites work: Simple Random Walk and Rank Order Statistics
cites work: Q3669422
cites work: Q3939231
cites work: Q3880080
cites work: Solution of an enumerative problem connected with lattice paths
cites work: Q3283895
cites work: Q3903764
cites work: Q5647757
cites work: The ballot problem with three candidates
description: scientific article; zbMATH DE number 3970755