Generating functions of embedded trees and lattice paths. (English) Zbl 1244.05060

Kuba, Markus

Fundam. Inform. 117, No. 1-4, 215-227 (2012).

Summary: J. Bouttier, P. Di Francesco and E. Guitter [Nucl. Phys., B 663, No. 3, 535–567 (2003; Zbl 1022.05022)] 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.

MSC:

05C05	Trees
05C60	Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C30	Enumeration in graph theory
05C12	Distance in graphs

Keywords:

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