A probabilistic method for lattice path enumeration (Q1081604): Difference between revisions

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.