Séminaire Lotharingien de Combinatoire, 93B.49 (2025), 11 pp.
Enrica Duchi and Gilles Schaeffer
From Order One Catalytic Decompositions to Context-Free Specifications, Bijectively
Abstract.
A celebrated result of Bousquet-Mélou and Jehanne (2006) states
that the bivariate power series solutions of so-called
combinatorial polynomial equations with one catalytic
variable (or 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 60's to enumerate planar maps.
Received: November 15, 2024.
Accepted: February 15, 2025.
Final version: April 1, 2025.
The following versions are available: