The enumeration of linear $\lambda$-terms has attracted quite some attention recently, partly due to their link to combinatorial maps. Zeilberger and Giorgetti (2015) gave a recursive bijection between planar linear normal $\lambda$-terms and planar maps, which, when restricted to 2-connected $\lambda$-terms (i.e., without closed sub-terms), leads to bridgeless planar maps. Inspired by this restriction, Zeilberger and Reed (2019) conjectured that 3-connected planar linear normal $\lambda$-terms have the same counting formula as bipartite planar maps. In this article, we settle this conjecture by giving a direct bijection between these two families. Furthermore, using a similar approach, we give a direct bijection between planar linear normal $\lambda$-terms and planar maps, whose restriction to 2-connected $\lambda$-terms leads to loopless planar maps. This bijection seems different from that of Zeilberger and Giorgetti, even after taking the map dual. We also explore enumerative consequences of our bijections.
翻译:-
平面映射与具有连通性条件的平面线性正规$λ$-项之间的双射
翻译后的摘要:
本文介绍了线性λ-项的枚举问题,这个问题近来引起了很多人的注意,部分原因是它们与组合图的联系。Zeilberger和Giorgetti(2015)给出了平面线性正规λ-项和平面地图之间的递归双射,当限制为2-连通的λ-项时(即没有闭合子项时),得到无桥平面图。
受此限制的启发,Zeilberger和Reed(2019)猜测3-连通的平面线性正规λ-项与二分平面图具有相同的计数公式。本文通过直接双射方法解决了这个猜想,给出了这两个族之间的直接双射。此外,利用类似的方法,我们还给出了平面线性正规λ-项和平面地图之间的直接双射,当限制为2-连通λ-项时,得到无环平面图。尽管采取了双重映射,这个双射似乎与Zeilberger和Giorgetti的不同。我们还探讨了双射的枚举后果。