Dans cet exposé basé en partie sur des travaux avec Enrica Duchi, je reviendrai d'abord rapidement sur LA bijection entre cartes enracinées et arbres très bien étiquetés, et quelques unes de ses reformulations, pour motiver la question suivante : à quel point peut-on donner un relèvement combinatoire du théorème de Bousquet-Mélou--Jehanne qui assure l'algébricité des solutions de certaines équations polynomiales à une variable catalytique ?
Nous verrons que dans le cas simple où l'équation fait intervenir une seule fonction inconnue univariée, il est possible de comprendre le résultat de manière complètement combinatoire : si on sait donner une décomposition récursive d'une classe combinatoire $C$ à l'aide d'un paramètre catalytique, on peut en déduire une décomposition $\mathbb{N}$-algébrique des arbres de décomposition catalytique associés aux objets de la classe pointée $C^\bullet$.
Comme exemple d'application nous étudierons la séquence 1, 4, 48, 832, 17408, 408576... qui donne le nombre d'arbres binaires bicolores à $n$ noeuds bleus et $n+1$ noeuds rouges (et $2n+2$ feuilles non colorées) tels que dans chaque sous-arbre strict le nombre de noeuds bleus est au moins égal au nombre de noeuds rouges.
(Spoiler : on verra que la technique ne suffit pas (encore) à se passer complètement d'intuition combinatoire, et que je ne sais toujours pas dire comment Bernard et Robert ont eu l'idée de leur bijection !)