×

zbMATH — the first resource for mathematics

Basic analytic combinatorics of directed lattice paths. (English) Zbl 0996.68126
Summary: This paper develops a unified enumerative and asymptotic theory of directed two-dimensional lattice paths in half-planes and quarter-planes. The lattice paths are specified by a finite set of rules that are both time and space homogeneous, and have a privileged direction of increase. (They are then essentially one-dimensional objects.) The theory relies on a specific “kernel method” that provides an important decomposition of the algebraic generating functions involved, as well as on a generic study of singularities of an associated algebraic curve. Consequences are precise computable estimates for the number of lattice paths of a given length under various constraints (bridges, excursions, meanders) as well as a characterization of the limit laws associated to several basic parameters of paths.

MSC:
68R05 Combinatorics in computer science
Software:
gfun; OEIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abhyankar, S.-S., Algebraic geometry for scientists and engineers, (1990), American Mathematical Society · Zbl 0709.14001
[2] C. Banderier, Combinatoire analytique: application aux marches aléatoires, D.E.A. memoir, Université Paris VII, July 1998.
[3] C. Banderier, Combinatoire analytique des chemins et des cartes, Ph.D. thesis, Université Paris VI, June 2001.
[4] C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, D. Gouyou-Beauchamps, Generating functions of generating trees, Tech. Report ALCOM FT-TR-01-17, Alcom-FT Project, February 2001, 26 pages, Accepted for publication in Discrete Mathematics. · Zbl 0997.05007
[5] Banderier, C.; Flajolet, P.; Schaeffer, G.; Soria, M., Random maps, coalescing saddles, singularity analysis, and Airy phenomena, Random structures & algorithms., 19, 194-246, (2001) · Zbl 1016.68179
[6] Barcucci, E.; Brunetti, S.; Del Lungo, A.; Nivat, M., Reconstruction of discrete sets from three or more X-rays, Discrete math., 241, 65-78, (2001) · Zbl 1001.68177
[7] Barcucci, E.; Del Lungo, A.; Nivat, M.; Pinzani, R., Reconstructing convex polyominoes from horizontal and vertical projections, Theoret. comput. sci., 155, 2, 321-347, (1996) · Zbl 0872.68134
[8] Barcucci, E.; Pinzani, R.; Sprugnoli, R., The random generation of directed animals, Theoret. comput. sci., 127, 2, 333-350, (1994) · Zbl 0938.68935
[9] Beauquier, D.; Nivat, M.; Rémila, É.; Robson, M., Tiling figures of the plane with two bars, Comput. geom. theory appl., 5, 1, 1-25, (1995) · Zbl 0815.05022
[10] J. Berstel (Ed.), Séries formelles, LITP, University of Paris, 1978. (Proceedings of a School, Vieux-Boucau, France, 1977.)
[11] M. Bousquet-Mélou, On (some) functional equations arising in enumerative combinatorics, Preprint, 2001.
[12] M. Bousquet-Mélou, A.J. Guttmann, Three-dimensional self-avoiding convex polygons, Physical Review E. Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics. Third Series 55(6) part A (1997), R6323-R6326.
[13] Bousquet-Mélou, M.; Petkovšek, M., Linear recurrences with constant coefficientsthe multivariate case, Discrete math., 225, 1-3, 51-75, (2000) · Zbl 0963.05005
[14] Comtet, L., Calcul pratique des coefficients de Taylor d’une fonction algébrique, Enseign. math., 10, 267-270, (1964) · Zbl 0166.41702
[15] Comtet, L., Advanced combinatorics, (1974), Reidel Dordrecht
[16] N.G. de Bruijn, Asymptotic methods in analysis, Dover, 1981, A reprint of the third North Holland edition, 1970 (1st Edition, 1958).
[17] A. Del Lungo, M. Nivat, R. Pinzani, The number of convex polyominoes reconstructible from their orthogonal projections, Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics, New Brunswick, NJ, 1994, Vol. 157, 1996, pp. 65-78. · Zbl 0856.05024
[18] Delest, M.; Viennot, G., Algebraic languages and polyominoes enumeration, Theoret. comput. sci., 34, 169-206, (1984) · Zbl 0985.68516
[19] G. Doyle, Peter; Laurie Snell, J., Random walks and electric networks, (1984), Mathematical Association of America Washington, DC · Zbl 0583.60065
[20] Drmota, M., Asymptotic distributions and a multivariate Darboux method in enumeration problems, J. combin. theory ser. A, 67, 169-184, (1994) · Zbl 0801.60016
[21] Drmota, M.; Soria, M., Images and preimages in random mappings, SIAM J. discrete math., 10, 2, 246-269, (1997) · Zbl 0867.05001
[22] P. Duchon, On the enumeration and generation of generalized Dyck words, Discrete Math. 225 (1-3) (2000) 121-135. (Formal power series and algebraic combinatorics, Toronto, Ont., 1998.) · Zbl 0971.68090
[23] M. Durand, Asymptotics of the “klam” recurrence, Preprint, 2001.
[24] Euler, L., Observationes analyticae, Novi commentarii acad. sci. imper. petropolitanae, 11, 124-143, (1765)
[25] Fayolle, G.; Iasnogorodski, R., Two coupled processorsthe reduction to a riemann – hilbert problem, Z. wahrsch. verw. gebiete, 47, 3, 325-351, (1979) · Zbl 0395.68032
[26] Fayolle, G.; Iasnogorodski, R.; Malyshev, V., Random walks in the quarter-plane, (1999), Springer Berlin · Zbl 0932.60002
[27] W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, 3rd Edition,Wiley, New York, 1968. · Zbl 0155.23101
[28] Feller, W., An introduction to probability theory and its applications, Vol. 2, (1971), Wiley New York · Zbl 0219.60003
[29] Flajolet, P., Combinatorial aspects of continued fractions, Discrete math., 32, 125-161, (1980) · Zbl 0445.05014
[30] P. Flajolet, The evolution of two stacks in bounded space and random walks in a triangle, in: J. Gruska, B. Rovan, J. Wiedermann (Eds.), Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 233, Springer, 1986, Proceedings of the 12th MFCS Symposium, Bratislava, August 1986, pp. 325-340. · Zbl 0602.68029
[31] Flajolet, P., Analytic models and ambiguity of context-free languages, Theoret. comput. sci., 49, 283-309, (1987) · Zbl 0612.68069
[32] Flajolet, P.; Françon, J.; Vuillemin, J., Sequence of operations analysis for dynamic data structures, J. algorithms, 1, 111-141, (1980) · Zbl 0445.68036
[33] Flajolet, P.; Guillemin, F., The formal theory of birth-and-death processes, lattice path combinatorics, and continued fractions, Adv. appl. probab., 32, 750-778, (2000) · Zbl 0966.60069
[34] Flajolet, P.; M. Odlyzko, Andrew, Singularity analysis of generating functions, SIAM J. algeb. discrete meth., 3, 2, 216-240, (1990) · Zbl 0712.05004
[35] D. Foata, La série génératrice exponentielle dans les problèmes d’énumération, S.M.S, Montreal University Press, 1974. · Zbl 0325.05007
[36] Françon, J., Histoires de fichiers, RAIRO informat. théor., 12, 1, 49-62, (1978) · Zbl 0377.68034
[37] Furstenberg, H., Algebraic functions over finite fields, J. algebra, 7, 271-277, (1967) · Zbl 0175.03903
[38] M. Gessel, Ira, A factorization for formal Laurent series and lattice path enumeration, J. combin. theory ser. A, 28, 3, 321-337, (1980)
[39] M. Gessel, Ira, A noncommutative generalization and q-analog of the Lagrange inversion formula, Trans. amer. math. soc., 257, 2, 455-482, (1980) · Zbl 0459.05014
[40] Gnedenko, B.V.; Kolmogorov, A.N., Limit distributions for sums of independent random variables, (1968), Addison-Wesley Reading, MA · Zbl 0056.36001
[41] H.W. Gould, Research bibliography on two number sequences, in: Mathematica Monongaliae, 1971. (A comprehensive bibliography on Bell and Catalan numbers.)
[42] P. Goulden, Ian; M. Jackson, David, Combinatorial enumeration, (1983), Wiley New York
[43] Henrici, P., Applied and computational complex analysis, Vol. 2, (1974), Wiley New York
[44] E. Hille, Analytic Function Theory, Blaisdell Publishing Company, Waltham, 1962, 2 Volumes. · Zbl 0102.29401
[45] Kirwan, F., Complex algebraic curves, London mathematical society student texts, no. 23, (1992), Cambridge University Press Cambridge
[46] Donald E. Knuth, The Art of Computer Programming, Vol. 1, 3rd Edition, Fundamental Algorithms, Addison-Wesley, Reading, MA, 1997. · Zbl 0895.68055
[47] Donald E. Knuth, The Art of Computer Programming, Vol. 2, 3rd Edition, Seminumerical Algorithms, Addison-Wesley, Reading, MA, 1998. · Zbl 0895.65001
[48] Donald E. Knuth, The Art of Computer Programming, Vol. 3, 2nd Edition, Sorting and Searching, Addison-Wesley, Reading, MA, 1998. · Zbl 0895.65001
[49] J. Labelle, Y. Nan Yeh, Dyck paths of knight moves, Discrete Appl. Math. 24(1-3) (1989) 213-221. (First Montreal Conference on Combinatorics and Computer Science, 1987.) · Zbl 0691.05004
[50] Labelle, J.; Nan Yeh, Y., Generalized Dyck paths, Discrete math., 82, 1-6, (1990) · Zbl 0723.05074
[51] P.-S. Laplace, Théorie analytique des probabilités, Vol. I, II, Éditions Jacques Gabay, Paris, 1995, Reprint of the 1819 and 1820 editions.
[52] Lothaire, M., Combinatorics on words, Encyclopedia of mathematics and its applications, Vol. 17, (1983), Addison-Wesley Reading, MA · Zbl 0514.20045
[53] Louchard, G., Asymptotic properties of some underdiagonal walks generation algorithms, Theoret. comput. sci., 218, 2, 249-262, (1999) · Zbl 0933.68153
[54] E. Lucas, Théorie des Nombres, Gauthier-Villard, Paris, 1891, Reprinted by A. Blanchard, Paris, 1961.
[55] Meir, A.; Moon, J.W., On the altitude of nodes in random trees, Canad. J. math., 30, 997-1015, (1978) · Zbl 0394.05015
[56] Merlini, D.; Rogers, D.G.; Sprugnoli, R.; Cecilia Verri, M., Underdiagonal lattice paths with unrestricted steps, Discrete appl. math. combin. algorithms, optimization and computer science, 91, 1-3, 197-213, (1999) · Zbl 0923.05003
[57] Sri G. Mohanty, Lattice Path Counting and Applications, Academic Press [Harcourt Brace Jovanovich Publishers], New York, 1979, Probability and Mathematical Statistics. · Zbl 0455.60013
[58] Sri G. Mohanty, Combinatorial aspects of some random walks, Random walks (Budapest, 1998), János Bolyai Math. Soc., Budapest, 1999, pp. 259-273. · Zbl 0954.60039
[59] Narayana, T.V., Lattice path combinatorics with statistical applications, (1979), University of Toronto Press Toronto, Ont., · Zbl 0437.05001
[60] Maurice Nivat, Langages algébriques sur le magma libre et sémantique des schémas de programme, Automata, languages and programming (Proc. Symp., Rocquencourt, 1972), North-Holland, Amsterdam, 1973, pp. 293-308.
[61] Odlyzko, A.M., Asymptotic enumeration methods, (), 1063-1229 · Zbl 0845.05005
[62] J. Pitman, Brownian motion, bridge, excursion, and meander characterized by sampling at independent uniform times, Electron. J. Probab. 4(11) (1999) 33 (electronic). · Zbl 0935.60068
[63] Pólya, G., Sur LES séries entières dont la somme est une fonction algébrique, Enseig. math., 1-2, 38-47, (1921-1922) · JFM 48.0368.02
[64] H. Prodinger, On a functional-difference equation of Runyon, Morrison, Carlitz, and Riordan, Sem. Lothar. Combin. 46 (2001), paper B46a, 4 pp. (electronic).
[65] Raney, G.N., Functional composition patterns and power series reversion, Trans. amer. math. soc., 94, 441-451, (1960) · Zbl 0131.01402
[66] P. Robert, Réseaux et files d’attente: méthodes probabilistes, Math. Appl., Vol. 35, sPRINGER, pARIS, 2000.
[67] Salvy, B.; Zimmermann, P., GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM trans. math. software, 20, 2, 163-167, (1994) · Zbl 0888.65010
[68] Sato, M., Generating funtions for the number of lattice paths between two parallel lines with a rational incline, Math. japonica, 34, 1, 123-137, (1989) · Zbl 0689.05005
[69] Sedgewick, R.; Flajolet, P., An introduction to the analysis of algorithms, (1996), Addison-Wesley Publishing Company Reading, MA
[70] N.J.A. Sloane, The on-line encyclopedia of integer sequences, 2000, Published electronically at http://www.research.att.com/njas/sequences/. · Zbl 1274.11001
[71] Sloane, N.J.A.; Plouffe, S., The encyclopedia of integer sequences, (1995), Academic Press New York · Zbl 0845.11001
[72] Stanley, R.P., Enumerative combinatorics, Vol. II, (1998), Cambridge University Press Cambridge
[73] J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science, vol. B: Formal Models and Semantics, North-Holland, Amsterdam, 1990.
[74] Chi Chih Yao, A., An analysis of \((h,k,1)\)-shellsort, J. algorithms, 1, 1, 14-50, (1980) · Zbl 0438.68023
[75] Chi Chih Yao, A., An analysis of a memory allocation scheme for implementing stacks, SIAM J. comput., 10, 2, 398-403, (1981) · Zbl 0457.68023
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.