2024/12/30 by Enrica Duchi, Duchi, Enrica, Gilles Schaeffer +1 · 1 citation
Chemistry · Computer Science · #05A15 #05A19 #Combinatorics (math.CO) #FOS: Mathematics #Formal Methods in Verification #Model-Driven Software Engineering Techniques #Synthetic Organic Chemistry Methods
paper · pdf · doi:10.48550/arxiv.2412.20628
openalex publication_date 2024/12/30 · openalex created_date 2025/01/01 · openalex updated_date 2026/07/28
A celebrated result of Bousquet-Mélou and Jehanne states that the bivariate power series solutions of so-called combinatorial polynomial equations with one catalytic variable, also known as catalytic equations, are algebraic series. We give a purely combinatorial derivation of this result in the case of order one catalytic equations (those involving only one univariate unknown series). In particular our approach provides a tool to produce context-free specifications, or bijections with simple multi-type families of trees, for the derivation trees of combinatorial structures that are directly governed by an order one catalytic decomposition. This provides a simple unified framework to deal with various combinatorial interpretation problems that were solved or raised over the last 50 years since the first such catalytic equation was written by W. T. Tutte in the late 60's to enumerate rooted planar maps.