Generating Functions of Embedded Trees and Lattice Paths

• Autorzy: Kuba M.
• Języki publikacji: EN

Abstrakty

EN

Bouttier, Di Francesco and Guitter introduced a method for solving certain classes of algebraic recurrence relations arising the context of maps and embedded trees. The aim of this note is to apply their method, consisting of a suitable ansatz and (computer assisted) guessing, to three problems, all related to the enumeration of lattice paths. First, we derive the generating function of a family of embedded binary trees, unifying some earlier results in the literature. Second, we show that several enumeration problems concerning so-called simple families of lattice paths can be solved without using the kernel method. Third, we use their method to (re-)derive the length generating function of three vicious walkers and osculating walkers.

Słowa kluczowe

EN

embedded trees; binary trees; lattice paths; vicious walkers; osculating walkers

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 117, nr 1-4
• Strony: 215--227
• Opis fizyczny: Bibliogr. 13 poz., wykr.

Twórcy

autor

Kuba M.

• Institut für Diskrete Mathematik und Geometrie Technische Universität Wien Wiedner Hauptstr. 8-10/104, 1040 Wien, Austria,

Bibliografia

• [1] C. Banderier and P. Flajolet. Basic analytic combinatorics of directed lattice paths. Theoretical Computer Science 281, 37-80, 2002.
• [2] C. Banderier and P. Nicodéme, Bounded discrete walks, DMTCS, Proceedings of the AofA 2010, 2010.
• [3] M. Bousquet-Mélou and S. Janson, The density of the ISE and local limit laws for embedded trees. Annals of Applied Probability, 16, 3, 1597-1632, 2006.
• [4] M. Bousquet-Mélou, Limit laws for embedded trees. Applications to the integrated superBrownian excursion. Random Structures and Algorithms 29 , 4, 475-523, 2006.
• [5] M. Bousquet-Mélou, Rational and algebraic series in combinatorial enumeration, Proceedings of the ICM, Session lectures, pp.789-826, 2006.
• [6] M. Bousquet-Mélou, Three osculating walkers, Journal of Physics: Conference Series, 42, 35-46, 2006.
• [7] J. Bouttier, P. Di Francesco and E. Guitter, Geodesic distance in planar graphs, Nucl. Phys. B 663, 535-567, 2003.
• [8] J. Bouttier, P. Di Francesco and E. Guitter, Random trees between two walls: Exact partition function, J. Phys. A: Math. Gen. 36 , 12349-12366, 2003.
• [9] A. Del Lungo, F. Del Ristoro and J.-G. Penaud, Left ternary trees and non-separable rooted planar maps, Theoretical Computer Science 233, 1-2, 201-215, 2000.
• [10] P. Di Francesco, Geodesic Distance in Planar Graphs: An Integrable Approach. The Ramanujan Journal 10, No. 2, 2005.
• [11] M. Drmota, Embedded trees and the support of the ISE, LNCS 5874 - Proceedings of the IWOCA 2009,194-205, Springer, 2009.
• [12] B. Jacquard and G. Schaeffer, A Bijective Census of Nonseparable Planar Maps, Journal of Combinatorial Theory Series A 83, Issue 1, 1-20, 1998.
• [13] J.-F.Marckert, The rotation correspondence is asymptotically a dilatation. RandomStructures and Algorithms 24, 118-132, 2004.