×

Walks on the slit plane: Other approaches. (English) Zbl 0992.05012

Summary: Let \({\mathfrak S}\) be a finite subset of \(\mathbb{Z}^2\). A walk on the slit plane with steps in \({\mathfrak S}\) is a sequence \((0,0)= w_0,w_1,\dots, w_n\) of points of \(\mathbb{Z}^2\) such that \(w_{i+ 1}- w_i\) belongs to \({\mathfrak S}\) for all \(i\), and none of the points \(w_i\), \(i\geq 1\), lie on the half-line \({\mathcal H}= \{(k, 0): k\leq 0\}\). In a recent paper [Walks on the slit plane, preprint 2000 arXiv: match.CO/0012230] G. Schaeffer and the author computed the length generating function \(S(t)\) of walks on the slit plane for several sets \({\mathfrak S}\). All the generating functions thus obtained turned out to be algebraic: for instance, on the ordinary square lattice, \(S(t)= ((1+ \sqrt{1+ 4t})^{1/2}(1+ \sqrt{1- 4t})^{1/2})/2(1- 4t)^{3/4}\). The combinatorial reasons for this algebraicity remain obscure. In this paper, we present two new approaches for solving slit plane models. One of them simplifies and extends the functional equation approach of the original paper. The other one is inspired by an argument of Lawler; it is more combinatorial, and explains the algebraicity of the produt of three series related to the model. It can also be seen as an extension of the classical cycle lemma. Both methods work for any set of steps \({\mathfrak S}\). We exhibit a large family of sets \({\mathfrak S}\) for which the generating function of walks on the slit plane is algebraic, and another family for which it is neither algebraic, nor even D-finite. These examples give a hint at where the border between algebraicity and transcendence lies, and call for a complete classification of the sets \({\mathfrak S}\).

MSC:

05A15 Exact enumeration problems, generating functions

Online Encyclopedia of Integer Sequences:

Apart from the leading term, a(n) = Catalan(n-1)*4^(n-1).

References:

[1] Barcucci, E.; Pergola, E.; Pinzani, R.; Rinaldi, S., A bijection for some paths on the slit plane, Adv. in Applied Math., 26, 89-96 (2001) · Zbl 0984.05004
[2] M. Bousquet-Mélou, and, G. Schaeffer, Walks on the slit plane, preprint, 2000, arXiv:math.CO/0012230.; M. Bousquet-Mélou, and, G. Schaeffer, Walks on the slit plane, preprint, 2000, arXiv:math.CO/0012230.
[3] Considine, D.; Redner, S., Repulsion of random and self-avoiding walks from excluded points and lines, J. Phys. A: Math. Gen., 22, 1621-1638 (1989)
[4] Dvoretzky, A.; Motzkin, Th., A problem of arrangements, Duke Math. J., 14, 305-313 (1947) · Zbl 0030.16701
[5] Flajolet, P., Analytic models and ambiguity of context-free languages, Theoret. Comput. Sci., 49, 283-309 (1987) · Zbl 0612.68069
[6] Flajolet, P.; Odlyzko, A., Singularity analysis of generating functions, SIAM J. Discrete Math., 3, 216-240 (1990) · Zbl 0712.05004
[7] Jungen, R., Sur les séries de Taylor n’ayant que des singularités algébrico-logarithmiques sur leur cercle de convergence, Comment. Math. Helv., 3, 266-306 (1931) · JFM 57.0373.03
[8] Kesten, H., Hitting probabilities of random walks on \(Z^d\), Stochastic Process Appl., 25, 165-184 (1987) · Zbl 0626.60067
[9] Lawler, G. F., Intersections of random walks, Probabilities and its Applications (1991), Birkhäuser: Birkhäuser Boston · Zbl 1228.60004
[10] Lipshitz, L., The diagonal of a D-finite power series is D-finite, J. Algebra, 113, 373-378 (1988) · Zbl 0657.13024
[11] Lipshitz, L., D-finite power series, J. Algebra, 122, 353-373 (1989) · Zbl 0695.12018
[12] Narayana, T. V., A partial order and its applications to probability theory, Sankhya, 21, 91-98 (1959) · Zbl 0168.39202
[13] Petkovs̆ek, M.; Wilf, H. S.; Zeilberger, D., \(A=B (1996)\), A. K. Peters: A. K. Peters Wellesley · Zbl 0848.05002
[14] Raney, G. N., Functional compositions patterns and power series reversion, Trans. Amer. Math. Soc., 94, 441-451 (1960) · Zbl 0131.01402
[15] G. Schaeffer, Conjugaison d’arbres et cartes combinatoires aléatoires, Ph.D. thesis, Université Bordeaux 1, 1998.; G. Schaeffer, Conjugaison d’arbres et cartes combinatoires aléatoires, Ph.D. thesis, Université Bordeaux 1, 1998.
[16] Singer, M. F., Algebraic relations among solutions of linear differential equations, Trans. Amer. Math. Soc., 295, 753-763 (1986) · Zbl 0593.12014
[17] Spitzer, F., Principles of random walk, The University Series in Higher Mathematics (1964), Van Nostrand Company: Van Nostrand Company Princeton · Zbl 0119.34304
[18] Stanley, R. P., Differentiably finite power series, European J. Combin., 1, 175-188 (1980) · Zbl 0445.05012
[19] Stanley, R. P., Enumerative Combinatorics (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0928.05001
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.