Counting isomorphism classes of $β$-normal linear lambda terms

Unanticipated connections between different fragments of lambda calculus and different families of embedded graphs (a.k.a. "maps") motivate the problem of enumerating $β$-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 $β$-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).

No reviews yet.

No comments yet.