A probabilistic method for lattice path enumeration.

*(English)*Zbl 0602.05006This 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 [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 [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.

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 [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 [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.

Reviewer: T.Walsh

##### MSC:

05A15 | Exact enumeration problems, generating functions |

60G50 | Sums of independent random variables; random walks |

05C30 | Enumeration in graph theory |

05C38 | Paths and cycles |

PDF
BibTeX
XML
Cite

\textit{I. M. Gessel}, J. Stat. Plann. Inference 14, 49--58 (1986; Zbl 0602.05006)

Full Text:
DOI

##### References:

[1] | Aneja, K.G.; Sen, K., Random walk and distributions of rank order statistics, SIAM J. applied math., 23, 276-287, (1972) · Zbl 0226.62044 |

[2] | Cohen, D.I.A.; Katz, T.M., Recurrence of a random walk on the half-line as the generating function for the Catalan numbers, Discrete math., 29, 213-214, (1980) · Zbl 0444.60056 |

[3] | Dwass, M., Simple random walk and rank order statistics, Ann. math. statist., 38, 1042-1053, (1967) · Zbl 0162.50204 |

[4] | Goulden, I.P.; Jackson, D.M., Combinatorial enumeration, (1983), Wiley New York · Zbl 0519.05001 |

[5] | Greene, D.H.; Knuth, D.E., Mathematics for the analysis of algorithms, (1981), Birkhäuser Boston, MA · Zbl 0481.68042 |

[6] | Handa, B.R.; Mohanty, S.G., On dwass’ method for deriving the distribution of rank order statistics, Aplikace mat., 24, 458-468, (1979) · Zbl 0438.62011 |

[7] | Kreweras, G., 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) |

[8] | Kreweras, G.; Niederhausen, H., Solution of an enumeration problem connected with lattice paths, Europ. J. combinat., 2, 55-60, (1981) · Zbl 0471.05004 |

[9] | MacMahon, P.A., Combinatory analysis, (), 1915-1916, (1960), Chelsea New York, originally published by |

[10] | Mohanty, S.G., Lattice path counting and applications, (1979), Academic Press New York · Zbl 0455.60013 |

[11] | Mohanty, S.G.; Handa, B.R., Rank order statistics related to a generalized random walk, Studia sci. math. hungar., 5, 267-276, (1970) · Zbl 0237.62040 |

[12] | Niederhausen, H., The ballot problem with three candidates, Europ. J. combinat., 4, 161-167, (1983) · Zbl 0528.05003 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.