×

Dénombrements de chemins dans \({\mathbb{R}}^ 2\)-soumis à contraintes. (Path enumeration in \({\mathbb{R}}^ 2\) obeying restrictions). (French) Zbl 0613.05008

The paths counted in this paper consist of unit-length horizontal and vertical lines in the plane. First, a formula is found for the number of length-n paths in the whole plane from the origin to a given point. Then, paths in certain regions of the plane are counted using Andre’s reflection principle (not referenced in the paper): the region is reflected until it covers the whole plane, reducing this problem to the previously-solved one of counting paths in the whole plane. The regions considered are the half-plane, the first quadrant (rederiving a result from W. T. Tutte [A census of Hamiltonian polygons, Can. J. Math. 14, 402-417 (1962; Zbl 0105.176)]), the 1/8-plane bounded by the \(+ve\) x-axis and the \(y=x\) (rederiving a result from D. Gouyou-Beauchamps [Produit de nombres de Catalan et chemins sous diagonaux, Manuscript, Bordeaux]), and the triangle whose vertices are (0,0), (0,m) and (m,0) (obtaining closed-form counting formula instead of the generating functions found in [P. Flajolet, The evolution of two stacks in bounded space and random walk in a triangle, I.N.R.I.A., Manuscript]). Finally, the formula for counting paths in the whole plane is generalized to higher-dimensional space.
Reviewer: T.Walsh

MSC:

05A15 Exact enumeration problems, generating functions
05C30 Enumeration in graph theory
05C38 Paths and cycles

Citations:

Zbl 0105.176
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. R. CORI, S. DULUCQ et G. VIENNOT, Shuffle of Parenthesis Systems and Baxter Permutations, Rapport C.N.R.S.-LA. n^\circ 226, Bordeaux, 1984. MR859292 · Zbl 0662.05004
[2] 2. P. FLAJOLET, The Evolution of two Stacks in Bounded Space and Random Walk in a Triangle, I.N.R.I.A., Manuscrit. · Zbl 0602.68029
[3] 3. J. FRANÇON, Sérialisabilité, commutation, mélange et tableaux de Young, Rapport U.H.A. n^\circ 27.
[4] 4. D. GOUYOU-BEAUCHAMPS, Produit de nombres de Catalan et chemins sous diagonaux, Manuscrit, Bordeaux.
[5] 5. D. GOUYOU-BEAUCHAMPS, Standard Young Tableaux of Height 4 and 5, Manuscrit, Bordeaux. · Zbl 0672.05012
[6] 6. W. T. TUTTE, A Census of Hamiltonian Polygons, Canad. J. Maths, vol. 14, 1962, p. 402-417. Zbl0105.17601 MR137657 · Zbl 0105.17601 · doi:10.4153/CJM-1962-032-x
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.