From order one catalytic decompositions to context-free specifications: the rewiring bijection

Overview & Synopsis

A celebrated result of Bousquet-Mélou and Jehanne states that the bivariate power series solutions of so-called discrete differential equations, also known as polynomial equations with one catalytic variable, or simply catalytic equations, are algebraic series. We give a purely combinatorial derivation of this result in the case of order one catalytic equations, involving only one univariate unknown series. In particular, our approach provides a tool to produce contextfree 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.