zbMATH — the first resource for mathematics

Generating functions of embedded trees and lattice paths. (English) Zbl 1244.05060
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.
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
Full Text: DOI arXiv