Counting isomorphism classes of $\beta$-normal linear lambda terms

Abstract

Unanticipated connections between different fragments of lambda calculus and different families of embedded graphs (a.k.a. "maps") motivate the problem of enumerating $\beta$-normal linear lambda terms. In this brief note, it is shown (by appeal to a theorem of Arquès and Beraud) that the sequence counting isomorphism classes of $\beta$-normal linear lambda terms up to free exchange of adjacent lambda abstractions coincides with the sequence counting isomorphism classes of rooted maps on oriented surfaces (A000698).

5 pages

References in corpus (1)

• A correspondence between rooted planar maps and normal planar lambda terms

Cited by in corpus (1)

• Linear lambda terms as invariants of rooted trivalent maps