Séminaire Philippe Flajolet

Gilles Schaeffer: From catalytic to algebraic decompositions, bijectively

par Gilles Schaeffer (LIX, Ecole Polytechnique)

Europe/Paris
IHP

IHP

Description

A celebrated result of Bousquet-Mélou and Jehanne states that under reasonable combinatorial hypotheses the solutions of polynomial equations with one catalytic variable are algebraic series. We give a combinatorial derivation of this result in the case of order one catalytic equations (those involving only one univariate unknown series), in the form of a recipe to derive systematically an algebraic decomposition or a bijection with a simply generated family of trees from an order one catalytic decomposition.

Joint work with Enrica Duchi.