×

zbMATH — the first resource for mathematics

Walks confined in a quadrant are not always D-finite. (English) Zbl 1070.68112
Summary: We consider planar lattice walks that start from a prescribed position, take their steps in a given finite subset of \(\mathbb Z^2\) , and always stay in the quadrant \(x\geqslant 0\), \(y\geqslant 0\). We first give a criterion which guarantees that the length generating function of these walks is D-finite, that is, satisfies a linear differential equation with polynomial coefficients. This criterion applies, among others, to the ordinary square lattice walks. Then, we prove that walks that start from \((1,1)\), take their steps in \({(2,-1),(-1,2)}\) and stay in the first quadrant have a non-D-finite generating function. Our proof relies on a functional equation satisfied by this generating function, and on elementary complex analysis.

MSC:
68R05 Combinatorics in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] André, D., Solution directe du problème résolu par M. bertrand, C. R. acad. sci. Paris, 105, 436-437, (1887) · JFM 19.0200.05
[2] Banderier, C.; Bousquet-Mélou, M.; Denise, A.; Gardy, D.; Gouyou-Beauchamps, D.; Flajolet, P., Generating functions for generating trees, Discrete math., 246, 1-3, 29-55, (2002) · Zbl 0997.05007
[3] Banderier, C.; Flajolet, P., Basic analytic combinatorics of directed lattice paths, Theoret. comput. sci., 281, 1-2, 37-80, (2002) · Zbl 0996.68126
[4] Barcucci, E.; Pergola, E.; Pinzani, R.; Rinaldi, S., A bijection for some paths on the slit plane, Adv. appl. math., 26, 2, 89-96, (2001) · Zbl 0984.05004
[5] Bousquet-Mélou, M., Walks on the slit planeother approaches, Adv. appl. math., 27, 2-3, 243-288, (2001) · Zbl 0992.05012
[6] M. Bousquet-Mélou, Counting walks in the quarter plane, in: Mathematics and Computer Science II. Algorithms, Trees, Combinatorics and Probabilities, Trends in Mathematics, Birkhäuser, Basel, 2002. · Zbl 1026.05004
[7] M. Bousquet-Mélou, Walks in the quarter plane: Kreweras’ algebraic model, in preparation. · Zbl 1064.05010
[8] Bousquet-Mélou, M.; Petkovšek, M., Linear recurrences with constant coefficientsthe multivariate case, Discrete math., 225, 51-75, (2000) · Zbl 0963.05005
[9] Bousquet-Mélou, M.; Schaeffer, G., Walks on the slit plane, Probab. theory relat. fields, 124, 3, 305-344, (2002) · Zbl 1008.05006
[10] Cori, R.; Chottin, L., Une preuve combinatoire de la rationalité d’une série génératrice associée aux arbres, RAIRO inform. théor., 16, 2, 113-128, (1982) · Zbl 0509.05006
[11] Duchon, P., On the enumeration and generation of generalized Dyck words, Discrete math., 225, 121-135, (2000) · Zbl 0971.68090
[12] Dvoretzky, A.; Motzkin, Th., A problem of arrangements, Duke math. J., 14, 305-313, (1947) · Zbl 0030.16701
[13] W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, Wiley, New York, 1950. · Zbl 0039.13201
[14] Flajolet, P., Analytic models and ambiguity of context-free languages, Theoret. comput. sci., 49, 283-309, (1987) · Zbl 0612.68069
[15] Gessel, I.M., A factorization for formal Laurent series and lattice path enumeration, J. combin. theory ser. A, 28, 321-337, (1980)
[16] Gessel, I.M., A probabilistic method for lattice path enumeration, J. statist. plann. inference, 14, 49-58, (1986) · Zbl 0602.05006
[17] Gessel, I.M.; Zeilberger, D., Random walk in a Weyl chamber, Proc. amer. math. soc., 115, 27-31, (1992) · Zbl 0792.05148
[18] Grabiner, D.J., Random walk in an alcove of an affine Weyl group, and non-colliding random walks on an interval, J. combin. theory ser. A, 97, 2, 285-306, (2002) · Zbl 1005.05006
[19] Ishizaki, K., Hypertranscendency of meromorphic solutions of a linear functional equation, Aequationes math., 56, 271-283, (1998) · Zbl 0932.39020
[20] Kreweras, G., Sur une classe de problèmes liés au treillis des partitions d’entiers, Cahiers B.U.R.O., 6, 5-105, (1965)
[21] Labelle, J., Langages de Dyck généralisés, Ann. sci. math. Québec, 17, 53-64, (1993) · Zbl 0795.05004
[22] Labelle, J.; Yeh, Y.-N., Generalized Dyck paths, Discrete math., 82, 1-6, (1990) · Zbl 0723.05074
[23] Lawler, G.F., Intersections of random walks, probabilities and its applications, (1991), Birkhäuser Boston
[24] Lipshitz, L., The diagonal of a D-finite power series is D-finite, J. algebra, 113, 373-378, (1988) · Zbl 0657.13024
[25] Lipshitz, L., D-finite power series, J. algebra, 122, 353-373, (1989) · Zbl 0695.12018
[26] Lipshitz, L.; Rubel, L.A., A gap theorem for power series solutions of algebraic differential equations, Amer. J. math., 108, 2, 1193-1213, (1986) · Zbl 0605.12014
[27] Loxton, J.H.; van der Poorten, A.J., A class of hypertranscendental functions, Aequationes math., 16, 93-106, (1977) · Zbl 0384.10014
[28] Merlini, D.; Rogers, D.G.; Sprugnoli, R.; Verri, M.C., Underdiagonal lattice paths with unrestricted steps, Discrete appl. math., 91, 1-3, 197-213, (1999) · Zbl 0923.05003
[29] Mohanty, S.G., Lattice path counting and applications, (1979), Academic Press New York · Zbl 0455.60013
[30] Narayana, T.V., A partial order and its applications to probability theory, Sankhya, 21, 91-98, (1959) · Zbl 0168.39202
[31] Niederhausen, H., The ballot problem with three candidates, European J. combin., 4, 161-167, (1983) · Zbl 0528.05003
[32] Niederhausen, H., Lattice paths between diagonal boundaries, Electron. J. combin., 5, R30, (1998)
[33] Nishioka, K., Mahler functions and transcendence, Lecture notes in mathematics, Vol. 1631, (1996), Springer Berlin, Heidelberg · Zbl 0876.11034
[34] M. Petkovšek, The irrational chess knight, in: Proc. of the 10th Conf. Formal Power Series and Algebraic Combinatorics, Toronto, 1998, pp. 513-522.
[35] Spitzer, F., Principles of random walk, the university series in higher mathematics, (1964), Van Nostrand Company Princeton · Zbl 0119.34304
[36] Stanley, R.P., Differentiably finite power series, European J. combin., 1, 175-188, (1980) · Zbl 0445.05012
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.