Combinatorial Theory

In this work, we study the limit distributions of various combinatorial parameters in trivalent maps, linear \(\lambda\)-terms, and other related families of objects. We focus on parameters in maps which naturally correspond to parameters in \(\lambda\)-terms and vice versa, allowing us to employ techniques from map theory and the \(\lambda\)-calculus in a combinatorial interplay. Some examples of the parameters we study are: the number of bridges in rooted trivalent maps and of subterms in closed linear \(\lambda\)-terms as well as the number of vertices of degree 1 in \((1,3)\)-valent maps and of free variables in open linear \(\lambda\)-terms. To analyse their distributions, we introduce appropriate tools: a moment-pumping schema for differential equations and a composition schema inspired by Bender's theorem.

Mathematics Subject Classifications: 05A16, 05A19, 03B40, 05C30

Keywords: Random maps on surfaces, lambda calculus, analytic combinatorics, limit laws