\documentclass[finalversion]{FPSAC2025}
\articlenumber{49}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
%% \usepackage{amsmath,amssymb}
\usepackage{comment}
\usepackage{graphicx,hyperref}
%\usepackage{a4wide}
\usepackage{wasysym}

\usepackage{enumitem}
\setlist{nosep}
%% \usepackage{caption}
%% \setlength{\abovecaptionskip}{0ex}
%% \setlength{\belowcaptionskip}{0ex}
%% \setlength{\floatsep}{0ex}
%% \setlength{\textfloatsep}{0ex}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{pro}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{example}[thm]{Example}

\newcommand{\nin}{\not\in}
\newcommand{\tmem}[1]{{\em #1\/}}
\newcommand{\textdots}{...}
\newcommand{\tmop}[1]{\ensuremath{\operatorname{#1}}}
\newcommand{\tmcolor}[2]{{\color{#1}{#2}}}
\providecommand{\xequal}[2][]{\mathop{=}\limits_{#1}^{#2}}

\newcommand{\bt}{{\textcolor{blue}{\scriptstyle\blacktriangle}}}
\newcommand{\sbt}{{\textcolor{blue}{\scriptscriptstyle\blacktriangle}}}
\newcommand{\wt}{{\textcolor{blue}{\scriptstyle\triangle}}}
\newcommand{\mt}{{\textcolor{blue}{\scriptstyle\triangle}}\!\!\,\!\!\;\!\!\!\!\textcolor{black}\times}
\newcommand{\bl}{{\textcolor{red}{\scriptstyle\blacklozenge}}}
\newcommand{\sbl}{{\textcolor{red}{\scriptscriptstyle\blacklozenge}}}
\newcommand{\wl}{{\textcolor{red}{\scriptstyle\lozenge}}}
\newcommand{\ml}{{\textcolor{red}{\scriptstyle\lozenge}}\!\!\!\!\textcolor{black}\times}
\newcommand{\bs}{{\scriptstyle\blacksquare}}
\newcommand{\ws}{{\scriptstyle\square}}
\newcommand{\ms}{{\scriptstyle\square}\!\!\!\!\textcolor{red}\times}
\newcommand{\bc}{{\textstyle\bullet}}\newcommand{\sbc}{{\scriptstyle\bullet}}
\newcommand{\wc}{{\textstyle\circ}}
\newcommand{\mc}{{\textstyle\circ}\!\!\!\!\textcolor{black}\times}
\newcommand{\markedre}{\textcolor{red}{\bl\!\rule[1.5pt]{10pt}{1.7pt}}\!\!\!\!\!\!\!\textcolor{black}{\times}\!\ws}
\newcommand{\re}{\textcolor{red}{\bl\!\rule[1.5pt]{10pt}{1.7pt}}\!\ws}
\newcommand{\pe}{\bl\!\textcolor{blue}{\rule[1.5pt]{10pt}{1.7pt}}\!\bt}
\newcommand{\be}{\bc\!\textcolor{black}{\rule[1.5pt]{10pt}{1.7pt}}\!\ws}
\newcommand{\bcedge}{\bc\!\!\rule[2pt]{10pt}{1pt}}
\newcommand{\wsedge}{\ws\!\rule[2pt]{8pt}{1pt}}
\newcommand{\bledge}{\bl\!\!\textcolor{blue}{\rule[2pt]{10pt}{1pt}}}
\newcommand{\btedge}{\bt\!\!\textcolor{blue}{\rule[2pt]{10pt}{1pt}}}
\newcommand{\cQ}{\mathcal{Q}}

\newenvironment{descriptioncompact}{\begin{description} }{\end{description}}
%\usepackage{lipsum}
\title[Order One Catalytic Equations and context-free specifications]{From order one catalytic decompositions to context-free specifications, bijectively}
%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want

%% note the \printbibliography command at the end of the file which goes with these biblatex commands
\author{\texorpdfstring{Enrica Duchi\thanks{\href{mailto:Enrica.Duchi@irif.fr}{Enrica.Duchi@irif.fr}. ED was partially supported by ANR Projects IsOMa (Grant number ANR-21-CE48-0007) and CartesEtPlus (Grant number ANR-23-CE48-0018).}\addressmark{1} \and Gilles Schaeffer\thanks{\href{mailto:Gilles.Schaeffer@lix.polytechnique.fr}{Gilles.Schaeffer@lix.polytechnique.fr}. GS was partially supported by ANR Project 3DMaps (Grant number ANR-20-CE48-0018) and LambdaComb (Grant number ANR-21-CE48-0017) .}\addressmark{2}
\address{\addressmark{1}IRIF, Université Paris Cité\\
  \addressmark{2}LIX, CNRS, Ecole polytechnique, Institut Polytechnique de Paris}}{Enrica Duchi and Gilles Schaeffer}}
\received{\today}

\abstract{A celebrated result of Bousquet-Mélou and Jehanne (2006) states
  that the bivariate power series solutions of so-called
  \emph{combinatorial polynomial equations with one catalytic
  variable} (or \emph{catalytic equations}) are algebraic series.  We
  give a purely combinatorial derivation of this result in the case of
  \emph{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.}


% \resume{Un résultat célèbre de Bousquet-Mélou et Jehanne (2006) dit que les solutions séries formelles bivariées des équations dites \emph{polynomiales à une variable catalytique} sont des séries algébriques. Nous donnons une preuve purement combinatoire de ce résultat dans le cas des \emph{équations catalytiques d'ordre 1} (celles qui ne font intervenir que des dérivées discrètes d'ordre 1). En particulier notre approche fournit un outil pour produire des décompositions algébriques ou des bijections avec des familles simples d'arbres multi-types pour les arbres de dérivations associées aux objects combinatoires gouvernés par une décomposition catalytique d'ordre 1.

% Ceci donne un cadre unifié et simple pour traiter divers problèmes d'interprétation combinatoire soulevés ou traités durant ces dernières 50 années depuis que la première équation de ce type a été écrite par W.T. Tutte à la fin des années 60 pour compter des cartes planaires enracinées.}
\keywords{Bijective Combinatorics, Generating Functions}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{DuchiSchaeffer21.bib}

\begin{document}



\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
An \emph{order one catalytic equation} is an equation of the form
\begin{equation}\label{eqn:eq1}
F(t,u)=t\cdot Q\left(F(t,u),\frac1u(F(t,u)-F(t,0)),u\right),
\end{equation}
where $Q(v,w,u)$ is a given formal power series in the variables $v$,
$w$ and $u$ with non-negative coefficients, and we are interested power series solutions $F(t,u)$ in the variables $t$ and $u$.  We
refer to \cite{BMJ,DNY} for the relevance of these equations in
the combinatorial literature, and examples of their many occurrences.


In \cite{BMJ}, Bousquet-M\'elou and Jehanne proved that a very general
family of \emph{polynomial equations with one catalytic variable} have
algebraic power series solutions. More precisely, as discussed in
\cite{S23}, in the case of a order one catalytic equation
like~\eqref{eqn:eq1} above, the univariate part of the solution,
$f\equiv f(t)=F(t,0)$, is given, if it exists, in terms of the formal
power series $Q(v,w,u)$, by
\begin{align}
  f\;=\;C_\ws-C_\bl\cdot C_\bt \quad\textrm{ or } \quad
  {\textstyle \frac{d}{dt}}f&=(1+C_\bc)\cdot Q(C_\ws,C_\bt,C_\bl),
  \label{eq:fCFS}
\end{align}
where $C_\ws\equiv C_\ws(t)$, $C_\bc\equiv C_\bc(t)$, $C_\bl\equiv C_\bl(t)$ and $C_\bt\equiv C_\bt(t)$ are the unique power series that satisfy the companion system
\begin{align}
  \left\{
 \begin{array}{rclcl}
    {C}_\ws
    &=&t\cdot Q({C}_\ws,{C}_\bt,{C}_\bl),\\
    {C}_\bc
    &=&t\cdot (1+{C}_\bc)\cdot {Q}'_v ({C}_\ws,{C}_\bt,{C}_\bl),\\
    {C}_\bl
    &=&t\cdot (1+{C}_\bc)\cdot{Q}'_w ({C}_\ws,{C}_\bt,{C}_\bl),\\
    {C}_\bt
    &=&t\cdot (1+{C}_\bc)\cdot {Q}'_u ({C}_\ws,{C}_\bt,{C}_\bl).
   \end{array}
  \right.
  \label{eq:CFS}
\end{align}
%The purpose of this article is to give a combinatorial derivation of
%this result.

%\bigskip

On the one hand, when $Q(v,w,u)$ is a polynomial with non-negative
integer coefficients, it is not difficult to give a combinatorial
interpretation to \Cref{eqn:eq1} in terms of labeled trees
with non-negativity conditions on labels. This was done for instance
in \cite{cori-schaeffer} for a closely related family of equations, in
terms of some \emph{description trees}, or more recently in
\cite{Chen} for a special case of \Cref{eqn:eq1} in terms of
some \emph{fully parked trees}.
%
On the other hand, under the same hypotheses on $Q(v,w,u)$,
System~\eqref{eq:CFS} is a so-called \emph{$\mathbb{N}$-algebraic
system}, and the power series $C_\ws$, $C_\bc$, $C_\bl$ and $C_\bt$
admit natural interpretations as generating functions (gf) of simple
varieties of multi-type trees, as discussed in \cite{gs:BM-ICM}, or
\cite[Chapter I, ex. I.53, p. 82]{FS}.  However, by default there is no
clear relations between the first and second types of interpretations.  

Our  contribution\footnote{{In this extended abstract all proofs are omitted, see full text \cite{full} for proofs.}} is to fill in this gap by providing a general
interpretation of \Cref{eqn:eq1} in terms of a family of
\emph{non-negative $\cQ$-trees} (\Cref{sec:Qtrees}) and a bijection (\Cref{thm:main}) between these trees
and a related family of \emph{$\cQ$-companion trees} (\Cref{sec:Qcompanion}) that provide
simple interpretations of \Cref{eq:fCFS} and
System~\eqref{eq:CFS} (\Cref{thm:un-balanced,pro:CFS}).


\section{Non-negative \texorpdfstring{$\cQ$}{Q}-trees}\label{sec:Qtrees}\vspace{-0.5em}
\subsection{Necklaces and non-negative \texorpdfstring{$\cQ$}{Q}-trees}\label{sec:defQtrees}
Let $\cQ$ denote a set of words on an alphabet $\{\bc,\bl,\bt\}$ of
\emph{pearls}: we identify each element $w=w_1\ldots w_k$ of $\cQ$
with a clockwise oriented necklace carrying one $\ws$-pearl followed
by the pearls $w_1,\ldots,w_k$. In the rest of the article the set
$\cQ$ will be viewed as the set of allowed vertex types for various
families of plane trees. Accordingly, to a set $\cQ$ of necklaces we
associate\footnote{For simplicity we state our results in this extended abstract for the unweighted case, but all of them hold in fact unchanged in the weighted case
$Q(v,w,u)=\sum_{s\in \cQ_{\mathrm{all}}}q_s v^{|s|_\bc}w^{|s|_\bl}u^{|s|_\bt}$.}
the vertex type generating function $Q(v,w,u)$ as
\begin{equation}\label{eq:Q}
Q(v,w,u)=\sum_{s\in \cQ} v^{|s|_{\sbc}}w^{|s|_{\sbl}}u^{|s|_{\sbt}}.
\end{equation}
%
The necklace associated to the word $w=\bc\bl\bt\bc\bc\bl$ is
represented on \Cref{fig:Necklaces}, together with our two
running examples of necklace sets:
$\cQ_{\mathrm{all}}=\{\bc,\bl,\bt\}^*$, the set of all necklaces, and
$\cQ_\lambda=\{\bc\bc,\bt,\bl\}$, with only three allowed necklaces,
with respective vertex generating functions $Q_{\mathrm{all}}(v,w,u)=1/(1-(v+w+u))$ and
$Q_\lambda(v,w,u)=v^2+w+u$.


\begin{figure}[t]
  \begin{center}
    \begin{minipage}{.16\linewidth}
      $w=\raisebox{-1.3em}{\includegraphics[scale=.3]{Necklace-example}}$
    \end{minipage}
    \begin{minipage}{.8\linewidth}
      \begin{align*}
        \mathcal{Q}_{\mathrm{all}}&=\left\{\raisebox{-1.3em}{\includegraphics[scale=.3]{Q-all}}\right\}\\
        \mathcal{Q}_\lambda&=\left\{\raisebox{-.7em}{\includegraphics[scale=.3]{Q-lambda}}\right\}
      \end{align*}
    \end{minipage}
  \end{center}
  \caption{\label{fig:Necklaces}The graphical representation of the necklace $w=\bc\bl\bt\bc\bc\bl$, and the necklace sets $\cQ_{\mathrm{all}}=\{\bc,\bl,\bt\}^*$ and $\cQ_\lambda=\{\bc\bc,\bt,\bl\}$.}
\end{figure}
\begin{figure}[t]
  \begin{center}
      \includegraphics[scale=.3]{Q-all-tree-very-small}\quad
      \includegraphics[scale=.3]{Q-all-tree-small}\quad
      \includegraphics[scale=.3]{Q-tree-small}
  \end{center}
  \caption{\label{fig:Q-trees}Three rooted $\cQ_{\mathrm{all}}$-trees with their excess labels, and with root indicated by a $\fullmoon$ around the root $\ws$-pearl.  The third one is also a $\cQ_\lambda$-tree. The second and third ones  are non-negative while the first one is not.}
\end{figure}



As illustrated by \Cref{fig:Q-trees}, a \emph{rooted $\cQ$-tree} is a $\ws$-rooted plane tree with black and red edges such that
\begin{itemize}
\item each vertex is  a copy of a necklace of $\cQ$,
\item each black edge connects a $\bc$-pearl to a $\ws$-pearl, \emph{i.e.}, takes the form $\be$,
\item each red edge connects a $\bl$-pearl to a $\ws$-pearl, \emph{i.e.}, takes the form $\re$,
\item each pearl is incident to one edge except the
  $\ws$-root and the $\bt$-pearls which are \emph{free}, that is, incident to no edge.
\end{itemize}
The size $|\tau|$ of a $\cQ$-tree $\tau$ is the number of its
vertices. By construction it is also the number $|\tau|_\ws$ of
$\ws$-pearls, and the number of edges plus one:
$|\tau|=|\tau|_{\ws}=|\tau|_\bc+|\tau|_\bl+1$.  We are only interested
in finite trees, so we shall assume from
now on that $\mathcal{Q}$ contains at least one vertex with no child,
hence without $\bc$- or $\bl$-pearls.

The subtree $\tau_x$ of a rooted $\cQ$-tree $\tau$ at a pearl $x$
consists of $x$ and all the vertices, edges and pearls that are on the other side of
$x$ with respect to the root of $\tau$. The \emph{excess} of a pearl
$x$ in the $\cQ$-tree $\tau$ is the difference between the number
of $\bt$- and $\bl$-pearls in the subtree planted at $x$, $x$
included: $\mathrm{exc}(x)=|\tau_x|_\bt-|\tau_x|_\bl$. The excess of a
vertex $v$ is the excess of its local root (the only $\ws$-pearl on
$v$), and the excess of $\tau$ is the excess of its root, that
is $\mathrm{exc}(\tau)=|\tau|_\bt-|\tau|_\bl$.
%
A \emph{non-negative $\cQ$-tree} is a $Q$-tree whose excess
is non-negative at each pearl.
%A \emph{\L ukasiewicz $\cQ$-tree} is a non-negative $\cQ$-tree with excess 0.
These definitions are illustrated by \Cref{fig:Q-trees}.
Observe that the non-negativity condition at each pearl in the
definition of non-negative $\cQ$-trees is in general more restrictive than
just saying that the excess is non-negative at each vertex: for instance this latter
condition would be satisfied by the leftmost tree in
\Cref{fig:Q-trees} whereas it is not non-negative due to its $\bl$-pearl with excess $-1$.

%% The following alternative recursive characterization of non-negative
%% $\cQ$-trees follows immediately from the standard root vertex decomposition of ordered:
\begin{pro}\label{pro:cata}
  Let $\cQ$ be as in~\eqref{eq:Q} and $\mathcal{F}_{k}$ denote the
  set of non-negative $\cQ$-trees with excess $k$ and
  $\mathcal{F}=\bigcup_{k\geq0}\mathcal{F}_k$. Then the family
  $\mathcal{F}$ of non-negative $\cQ$-trees admits a
  catalytic specification:
  \begin{align}\label{eqn:cataspec}
  \mathcal{F}\equiv \cQ(\bc\!\!\rule[2pt]{10pt}{1pt}\mathcal{F},\bl\!\!\textcolor{red}{\rule[2pt]{10pt}{1pt}}\mathcal{F}^+,\bt),
  \end{align}
  meaning that each tree of $\mathcal{F}$ can be uniquely obtained from a necklace $s\in\cQ$ upon attaching
  \begin{itemize}
  \item a black edge carrying a tree of $\mathcal{F}$ to each $\bc$-pearl of $s$,
  \item and a red edge carrying a tree of $\mathcal{F}^+=\mathcal{F}\setminus\mathcal{F}_0$ to each $\bl$-pearl of $s$.
  \end{itemize}
  In particular the gf $F(u)\equiv F(t,u)=\sum_{\tau\in\mathcal{F}}t^{|\tau|} u^{\mathrm{exc}(\tau)}$ is the unique formal power series solution of \Cref{eqn:eq1}, with $F(u)-F(0)=F^+(u)=\sum_{\tau\in\mathcal{F}^+}t^{|\tau|} u^{\mathrm{exc}(\tau)}$.
\end{pro}

\subsection{The closure and rewiring of a non-negative \texorpdfstring{$\cQ$}{Q}-tree} \label{sec:closure}\label{sec:rewiring}

A \emph{plane map} (resp. \emph{planar map}) is an embedding of a
connected graph in the plane (resp. sphere), considered up to
orientation-preserving homeomorphisms of the plane
(resp. sphere). Observe that the choice of unbounded face yields a
bijection between planar maps with $n$ edges and a distinguished face and plane
maps with $n$ edges.
%
It proves convenient to describe our bijections graphically, in terms
of spanning trees of plane maps and non-crossing arc systems built
around plane trees.
%
These are very standard combinatorial concepts, the basic definitions
and results we rely upon can be found for instance in
\cite{chapterMaps}. From now on we view $\mathcal{Q}$-trees as plane
maps with one face and decorated edges, in which necklaces are viewed
as vertices and pearls as colored endpoints of edges, and we consider
more generally plane maps with such decorated vertices and edges. In
particular a plane map is \emph{rooted} if one of its pearl is
distinguished as the root pearl.  Observe that the root pearl is in
general not required to be incident to the unbounded face.
Around a non-negative $\cQ$-tree $\tau$, as illustrated by \Cref{fig:Corners,fig:closure}, let
\begin{itemize}
\item a \emph{left $\bl$-corner} refer to the exterior angular sector following
  %on the left hand side of
  a red edge in counterclockwise direction around a $\bl$-pearl,
\item a \emph{$\bt$-corner} refer to the exterior angular sector around a $\bt$-pearl,
\end{itemize}
and define the ($\bl$-to-$\bt$ clockwise) \emph{closure} $c(\tau)$ of
$\tau$ as the plane map obtained by iteratively matching unmatched
left $\bl$-corners that are followed by an unmatched $\bt$-corner in
clockwise direction around the tree, to form a planar system of
non-crossing $\bl$-to-$\bt$ clockwise edges, hereafter called
\emph{blue} edges ($\pe$). This construction is a standard ingredient
of many bijections between plane maps and trees (see \emph{e.g.}
\cite[Theorem 6]{chapterMaps}).

\begin{figure}[t]
  \centering
    \begin{minipage}{.5\linewidth}
      \centering
      \includegraphics[scale=.3,page=4]{Q-all-tree-bit-larger}
    \end{minipage}
    \begin{minipage}{.45\linewidth}
      \centering
      \includegraphics[scale=.3]{corners-figure}
    \end{minipage}
  \caption{The left $\bl$-corners and $\bt$-corners of a non-negative $\cQ$-tree, and the
    matching of a left $\bl$-corner with the next available $\bt$-corner in
    clockwise direction.}
  \label{fig:Corners}
\end{figure}


\begin{figure}[t]
  \begin{center}
      \includegraphics[scale=.3,page=5]{Q-all-tree-bit-larger}\quad
      \includegraphics[scale=.3,page=6]{Q-all-tree-bit-larger}
  \end{center}
  \caption{The matchings after first iteration and final result of the
    $\bl$-to-$\bt$ clockwise closure of the tree of
    \Cref{fig:Corners}.}
  \label{fig:closure}
\end{figure}

%The following proposition directly arises from the definition of the closure:
\begin{pro}\label{pro:lemma}
  The closure $c(\tau)$ of a non-negative $\cQ$-tree $\tau$ is a $\ws$-rooted plane maps with vertices in $\cQ$, and black edges ($\be$), red edges ($\re$) and blue edges ($\pe$) such that:
%  \begin{itemize}
  %\item[(i)]
  \emph{(i)} The black and red edges of the spanning tree $\tau$ of $c(\tau)$ are such that all blue edges are $\bl$-to-$\bt$ clockwise around $\tau$.
% \item[(ii)]
  \emph{(ii)} The clockwise walk around each bounded face of $c(\tau)$ visits exactly one blue edge in $\bl$-to-$\bt$ direction and one red edge in $\ws$-to-$\bl$ direction,
    and these two edges share their $\bl$-pearl.
%  \item[(iii)]
    \emph{(iii)} Each $\bl$-pearl $x$ of $\tau$ is matched with a $\bt$-pearl in its subtree $\tau_x$.
    %  \item[(iv)]
    \emph{(iv)} All unmatched $\bt$-pearls in $c(\tau)$ lie in the unbounded face.
%  \end{itemize}
  %%Moreover t
  The closure is injective and its inverse is the \emph{opening} that consists in deleting blue edges.
\end{pro}

\begin{figure}[ht]
  \begin{center}
    \begin{minipage}{.44\linewidth}
      \centerline{\includegraphics[scale=.3,page=8]{Q-all-tree-bit-larger}}
    \end{minipage}
    \begin{minipage}{.1\linewidth}
      \[
      \begin{array}{c}
        \phi\\
        \longrightarrow\\
        \longleftarrow\\
        \bar\phi
        \end{array}
      \]
    \end{minipage}
    \begin{minipage}{.44\linewidth}
      \centerline{\includegraphics[scale=.3,page=1]{Q-Comp-closure}}
    \end{minipage}
  \end{center}
  \caption{The tree $\tau$ of \Cref{fig:Corners} (red and black edges) with its closure edges (dashed blue lines), and its rewiring,  $\phi(\tau)$ (blue and black edges), with the inverse closure edges (dashed red lines). Observe that as plane maps, the two only differ by the dashing of blue versus red edges.}
  \label{fig:rewiring}
\end{figure}

The \emph{rewiring} $\phi(\tau)$ of a $\cQ$-tree $\tau$ consists in its closure followed by the removal of red edges, as illustrated by \Cref{fig:rewiring}. %Using Property (iii) above and induction:

\begin{pro}\label{pro:rewiringtree}
  The rewiring $\phi(\tau)$ of a non-negative $\cQ$-tree $\tau$ is a tree with the same necklaces.
\end{pro}

\section{\texorpdfstring{$\cQ$}{Q}-companion trees and their decomposition}\label{sec:Qcompanion}\vspace{-0.5em}
\subsection{\texorpdfstring{$\cQ$}{Q}-companion trees and the main bijection}\label{sec:defQcompanion}

By construction, rewiring replaces each red edge of the form $\re$ by a
blue edge of the form $\pe$ originating from the same $\bl$-pearl, as illustrated by
\Cref{fig:rewiring}. Let us define
\emph{rooted $\cQ$-companion trees} as pearl rooted plane trees with black and blue
edges such that
\begin{itemize}
\item each vertex is a copy of a necklace of $Q$,
\item each black edge connects a $\bc$-pearl to a $\ws$-pearl, \emph{i.e.}, takes the form $\be$.
\item each blue edge connects a $\bl$-pearl to a $\bt$-pearl, \emph{i.e.}, takes the form $\pe$.
\item each non-root $\bc$- or $\bl$-pearl is incident to exactly one edge, the
  root pearl is free (\emph{i.e.}, incident to no edge) and each $\ws$- or $\bt$-pearl is incident to at most
  one edge.
\end{itemize}
The root pearl of a $\cQ$-companion tree can be of any type $\ws$, $\bc$, $\bl$, or $\bt$. By convention an \emph{unrooted $\cQ$-companion tree} is an equivalence class of $\ws$-rooted (or $\bt$-rooted) $\cQ$-companion trees up to rerooting: in other terms it is an unrooted plane tree satisfying the conditions above and without free $\bc$- or $\bl$-pearl (as it arises from $\ws$-rooted trees).

In any tree the number of vertices equals the number of edges plus
one, so by definition, in a $\ws$- or $\bt$-rooted $\cQ$-companion
tree $\tau'$, $|\tau'|_\ws=|\tau'|_\bc+|\tau'|_\bl+1$. In particular
this implies that the number of $\ws$-pearls that are free is equal to
the number of $\bl$-pearls plus one. Like in
\Cref{sec:closure}, we then define the inverse
($\bl$-to-$\ws$ counterclockwise) closure $\bar c(\tau')$ of a
$\ws$-rooted, $\bt$-rooted or unrooted $\cQ$-companion tree $\tau'$ as
the plane map obtained by matching iteratively right $\bl$-corners
that are followed by an unmatched $\ws$-corner in counterclockwise
direction around the tree to form a planar system of red edges: in
particular $\bar c(\tau')$ is a plane map with exactly one unmatched
$\ws$-pearl, and $\bar c(\tau')$ is rooted if $\tau'$ is, by keeping
the same root pearl. If $\tau'=\phi(\tau)$ then $\bar
c(\tau')=c(\tau)$.


\begin{figure}[t]
  \begin{center}
    \includegraphics[scale=.3,page=2]{Q-Com-closure-details}\;
      \includegraphics[scale=.3,page=1]{Q-Com-closure-details}\;
      \includegraphics[scale=.3,page=3]{Q-Com-closure-details}
  \end{center}
  \caption{Three rooted $\cQ$-companion trees (root pearl indicated by
    $\fullmoon$) with their inverse closure edges (dashed red lines),
    and sharing the same underlying unrooted tree. The leftmost tree
    is $\ws$-rooted and unbalanced, the middle one is $\ws$-rooted and
    balanced, they both have one internal and one external
    defects. The rightmost one is $\bt$-rooted and unbalanced, 
    without internal defects (root $\bt$-pearls do not count).}  \label{fig:internaldefects}
\end{figure}
\begin{figure}[t]
\centerline{    \includegraphics[scale=.3,page=7]{Q-Com-closure-details}}
  \caption{An unbalanced $\cQ$-companion tree without defect and the corresponding pair of $\bl$- and $\bt$-rooted $\cQ$-companion trees without defects.\label{fig:unbalanced}}
\end{figure}

A $\ws$-rooted $\cQ$-companion tree is \emph{balanced} if it is
rooted on the unique $\ws$-pearl that remains free in its
closure, \emph{unbalanced} otherwise. Similarly a
$\bt$-rooted $\cQ$-companion tree is \emph{balanced} if its root
pearl remains in the outer face after its closure, \emph{unbalanced}
otherwise. 
These definitions are illustrated by \Cref{fig:internaldefects}.
The \emph{inverse rewiring} $\bar\phi(\tau')$ of a balanced
$\ws$-rooted $\cQ$-companion tree $\tau'$ is obtained from $\bar
c(\tau')$ by removing the blue edges. Finally the non-root free
$\bt$-pearls of a $\cQ$-companion tree are referred to as
\emph{defects}. A defect in a $\ws$-rooted $\cQ$-companion tree
$\tau'$ is said to be \emph{external} (resp. \emph{internal}) if it
lies in the outer face (resp. in an inner face) of the inverse closure
$\bar c(\tau')$ of $\tau'$. 

\begin{thm}\label{thm:main}
  Rewiring and inverse rewiring are necklace-preserving bijections between
  \begin{itemize}
  \item non-negative $\cQ$-trees with excess $k\geq 0$,
  \item and balanced $\ws$-rooted $\cQ$-companion trees with $k$ external defects and no internal defects.
  \end{itemize}
\end{thm}

\begin{comment}
This result immediately follows from Propositions~\ref{pro:rewiring} and~\ref{pro:inverserewiring} below, in the case $k=0$.

\begin{pro}\label{pro:rewiring}
The rewiring of a non-negative $\cQ$-tree $\tau$ with excess $k$ is a
balanced $\ws$-rooted $\cQ$-companion tree without internal defects with $k$ external defects,
and $\bar \phi(\phi(\tau))=\tau$.
\end{pro}

\begin{pro}\label{pro:inverserewiring}
The inverse rewiring $\bar \phi(\tau')$ of a balanced $\ws$-rooted $\cQ$-companion tree $\tau'$ with $k$ external defects and no internal defects is a non-negative $\cQ$-tree with excess $k$, and $\phi(\bar\phi(\tau'))=\tau'$.
\end{pro}
In view of the two latter propositions, Theorem~\ref{thm:main} extends to the following corollary:
\begin{cor}\label{cor:main}
  Rewiring and inverse rewiring are necklace-preserving bijections between
  \begin{itemize}
  \item non-negative $\cQ$-trees with excess $k\geq 0$, 
  \item and balanced $\ws$-rooted $\cQ$-companion trees with $k$ external defects and no internal defects.
  \end{itemize}
\end{cor}
However we prefer to emphasize the simpler statement with $k=0$
because we concentrate on this case in the rest of the text.
\end{comment}


\subsection{Unrooted and rooted \texorpdfstring{$\cQ$}{Q}-companion trees without defects}\label{sec:unrooted}
%% Let us now relate bijectively the family of balanced $\ws$-rooted
%% $\cQ$-companion trees without defects to the family
Let $\mathbf C$ denote the family of
unrooted $\cQ$-companion trees without defects, and $\mathbf{C}_\ws$, $\mathbf{C}_\bc$, $\mathbf{C}_\bl$ and
$\mathbf{C}_\bt$ denote respectively $\ws$-, $\bc$-, $\bl$- and $\bt$-rooted
$\cQ$-companion trees without defects (without the requirement of being
balanced).
\begin{thm}\label{thm:un-balanced}
  There are necklace-preserving bijections between
  \begin{itemize}
  \item balanced $\ws$-rooted $\cQ$-companion trees without defects, 
  \item and unrooted $\cQ$-companion trees without defects,
  \end{itemize}
  and, as illustrated by \Cref{fig:unbalanced}, between
  \begin{itemize}
  \item unbalanced $\ws$-rooted $\cQ$-companion trees without defects,
  \item and pairs made of a $\bl$-rooted $\cQ$-companion tree and a
    $\bt$-rooted $\cQ$-companion tree, both without defects.
  \end{itemize}
\end{thm}

\Cref{thm:main,thm:un-balanced} reduce the enumeration of non-negative $\cQ$-trees with excess 0 to
that of rooted $\cQ$-companion trees without defects.
\begin{cor}\label{cor:reroot}
There is a necklace-preserving bijection between $\mathbf{C}_\ws$ and
$\mathbf{C}\cup (\mathbf{C}_\bl\times\mathbf{C}_\bt)$, or in other
terms, between non-negative $\cQ$-trees with excess 0, and $\ws$-rooted $\cQ$-companion trees that are not unbalanced:
  \[
  \mathcal{F}_0\equiv\mathbf{C}\equiv \mathbf{C}_\ws\setminus (\mathbf{C}_\bl\times\mathbf{C}_\bt).
  \]
  In particular this yields our combinatorial interpretation of the first equation in~\eqref{eq:fCFS} with $f\equiv
  F(t,0)=\sum_{\tau\in\mathcal{F}_0}t^{|\tau|}$ the gf of non-negative
  $\cQ$-trees with excess 0,  $C\equiv
  C(t)=\sum_{\tau\in\mathbf{C}}t^{|\tau|}$ that of unrooted $\cQ$-companion
  trees, and $C_{\ws}$, $C_\bc$,
  $C_\bl$, and $C_\bt$ of $\ws$-rooted, $\bc$-rooted, $\bl$-rooted, and $\bt$-rooted
  $\cQ$-companion trees.
\end{cor}


\subsection{The decomposition of \texorpdfstring{$\cQ$}{Q}-companion trees without defects}\label{sec:decQcompanion}
The analysis of possible root necklaces in $\cQ$-companion trees is illustrated by \Cref{fig:QNodes}:
\begin{itemize}
\item the set of root vertex types of $\ws$-rooted $\cQ$-companion trees is $\cQ$, since each necklace $s\in\cQ$ has exactly one $\ws$-pearl,
\item the set $\cQ'_\bc$ of root vertex types of $\bc$-rooted $\cQ$-companion trees is the union for all necklaces $s\in\cQ$ of the $|s|_\bc$ different  rerootings of $s$ on a $\bc$-pearl,
\item the set $\cQ'_\bl$ of $\bl$-rooted $\cQ$-companion trees and $\cQ'_\bt$ of $\bt$-rooted $\cQ$-companion trees are obtained similarly.
\end{itemize}
Any $\ws$-rooted $\cQ$-companion tree without defects can thus be uniquely produced by selecting a necklace $s\in\cQ$ together with $|s|_\bc$ subtrees from $\cQ_\ws$, $|s|_\bl$ subtrees from $\cQ_\bt$ and $|s|_\bt$ subtrees from $\cQ_\bl$, and attaching these subtrees to the pearls of $s$. This operation is summarized as $\mathbf{C}_\ws\equiv{\cQ}(\bcedge\mathbf{C}_\ws,\bledge\mathbf{C}_\bt,\btedge\mathbf{C}_\bl)$.

The same approach allows us to deal with $\bc$-rooted $\cQ$-companion trees without defects, upon taking $s\in\cQ_\bullet'$ and adding a possibly empty extra subtree in $\cQ_\bullet$ to attach to the $\ws$-pearl of $s$. The other classes $\mathbf{C}_\bl$ and $\mathbf{C}_\bt$ admit similar decompositions. 

\begin{figure}[t]
\centering
\includegraphics[scale=.4]{Rooted-Companion-striped}
  \caption{\label{fig:QNodes} On the left hand side, the decompositions of rooted $\cQ$-companion trees, illustrated in the case of a root vertex with necklace type $\bc\bt\bt\bc\bt\bl\bl$. On the right hand side, the corresponding derived necklaces types and contribution to the necklace gf. }% Observe that if the set of allowed necklaces $\cQ$ is finite, this specification is $\mathbb{N}$-{algebraic} in the sense of \cite{gs:BM-ICM,FS}.}
%\end{figure}
%\begin{figure}[t]
  \begin{center}
    \includegraphics[scale=.3]{Lambda-companion-tree-another}\vspace{-1em}
  \end{center}
  \caption{\label{fig:lambda-companion}A closed planar $\lambda$-term (bottom left), the corresponding non-negative $\cQ_\lambda$-tree (blue closing edges) and its balanced $\cQ_\lambda$-companion tree (red closure edges). On the right the decomposition  of $\ws$- and $\bc$-rooted $\cQ_\lambda$-companion trees without excess.}
\end{figure}

\begin{thm}\label{pro:CFS}
  The standard root vertex decomposition of multi-type rooted trees yields the following context-free specification of rooted $\cQ$-companion trees without defects:
\clearpage
\begin{align}\label{eqn:combiCFS}
  \left\{
  \begin{array}{rclcl}
    \mathbf{C}_\ws
    &\equiv&{\cQ}(\bcedge\mathbf{C}_\ws,\bledge\mathbf{C}_\bt,\btedge\mathbf{C}_\bl),\\
    \mathbf{C}_\bc
    &\equiv&(\ws+\wsedge\mathbf{C}_\bc)\times {\cQ}'_\bc (\bcedge\mathbf{C}_\ws,\bledge\mathbf{C}_\bt,\btedge\mathbf{C}_\bl),\\
    \mathbf{C}_\bl
    &\equiv&(\ws+\wsedge\mathbf{C}_\bc)\times{\cQ}'_\bl (\bcedge\mathbf{C}_\ws,\bledge\mathbf{C}_\bt,\btedge\mathbf{C}_\bl),\\
    \mathbf{C}_\bt
    &\equiv&(\ws+\wsedge\mathbf{C}_\bc)\times{\cQ}'_\bt (\bcedge\mathbf{C}_\ws,\bledge\mathbf{C}_\bt,\btedge\mathbf{C}_\bl),\\
    \mathbf{C}^{\textcolor{black}{\fullmoon}}
    &\equiv&(\ws+\wsedge\mathbf{C}_\bc)\times{\cQ}(\bcedge\mathbf{C}_\ws,\bledge\mathbf{C}_\bt,\btedge\mathbf{C}_\bl),
  \end{array}
  \right.
\end{align}
where ${\cQ}(\bcedge\mathbf{C}_\ws,\bledge\mathbf{C}_\bt,\bcedge\mathbf{C}_\bl)$ denotes the set of trees obtained from a necklace of $\cQ$ by attaching to each $\bc$-pearl a subtree of the form $\bcedge\mathbf{C}_\ws$, to each $\bt$-pearl a subtree of the form $\btedge\mathbf{C}_\bl$, and to each $\bl$-pearl a subtree of the form $\bledge\mathbf{C}_\bt$, and similarly for the other equations, and where $\mathbf{C}^{\textcolor{black}{\fullmoon}}$ denotes the set of unrooted $\cQ$-companion trees without defects with a marked necklace. 

The first four equations yield our interpretation of System~\eqref{eq:CFS}. Since marking a necklace in an unrooted $\cQ$-companion tree amounts to marking the same necklace in the corresponding non-negative $\cQ$-tree, the fifth equation yields our interpretation of the second equation in~\eqref{eq:fCFS}.
\end{thm}


\section{The example of \texorpdfstring{$\lambda$}{lambda}-terms and parking functions}



The planar $\lambda$-terms of \cite{Zeilberger-Giorgetti}
can be described as unary-binary trees with three types of vertices
corresponding to variables (leaves), abstractions (unary nodes), and
applications (binary nodes), such that each abstraction can be matched
to a distinct variable in its subtree. A planar $\lambda$-term is
\emph{closed} if the matching leaves no unmached variables.

As illustrated by \Cref{fig:lambda-companion}, these structures
can immediately be interpreted as non-negative $Q_\lambda$-trees, with
vertex type generating function $Q_\lambda(v,w,u)=u+v^2+w$ (recall \Cref{fig:Necklaces}). In particular, their gf is governed by
the corresponding catalytic equation:
%\begin{align*}
$  {F}(u)=t{Q_\lambda}({F}(u),{\textstyle\frac1u}({F}(u)-F(0)),u)=tu+t{F}(u)^2+{\textstyle \frac tu}(F(u)-F(0)).$
%\end{align*}
\Cref{thm:main}  yields a direct bijection between closed planar
$\lambda$-terms with $n$ abstractions (and $n$ variables and $n-1$
applications) and unrooted $\cQ_\lambda$-companion trees
with $3n-1$ necklaces.
%
According to \Cref{pro:CFS}, the corresponding $\ws$-rooted
$\cQ_\lambda$-companion trees are governed by the $\mathbb{N}$-algebraic system of \Cref{fig:lambda-companion},
%with equations 
%\begin{align*}\left\{
%  \begin{array}{rcl}
%  C_\ws&=&tC_\ws^2+2t^2(1+C_\bc),\\
%  C_\bc&=&2tC_\ws(1+C_\bc).
%  \end{array}\right.
%\end{align*}
with in particular $ C_\ws=tC_\ws^2+2t^2(1+C_\bc)$, and $C_\bc=2tC_\ws(1+C_\bc)$.
This decomposition can be wrapped up in a single equation, \emph{i.e.} $\ws$-rooted  
$\cQ_\lambda$-companion trees form a simple variety of trees \cite{FS}:
%\begin{align*}
$  C_\ws=tC_\ws^2+{2t^2}/{(1-2tC_\ws)}$. %=\frac{2t^2}{(1-tC_\ws)(1-2tC_\ws)}.$
%\end{align*}
As far as we know this is the first direct bijection between $\lambda$-terms and simple trees.

Non-negative $\cQ$-trees also encompass the \emph{parking trees}
of \cite{Pan}, also studied in
\cite{Chen, contat23, contat24}. In this
context, non-negative $\cQ$-trees can be viewed as a generalization of
parking trees where the $\bt$-pearls play the role of cars and the
$\bl$-pearls that of parking spots, and non-negative trees
with excess 0 correspond to  \emph{fully parked trees}, in
which all cars are parked at the end of the process.
%
Our rewiring bijection can in particular be understood as a
combinatorial straightening of the coupling introduced independently
in \cite{contat23} to relate the properties of a specific type of
such random fully parked trees to random Galton-Watson trees. 


\section{Conclusion}
In many instances, \emph{e.g.}
\cite{ALCO_2020__3_2_433_0,chapoton,Chen,cori-schaeffer,FANG2020111802,GW,Zeilberger-Giorgetti},
\Cref{eqn:eq1} arises from the translation for the
gf $F(t,u)$ of a catalytic specification of the form \eqref{eqn:cataspec} for a bigraded
combinatorial class $\mathcal{F}$ with objects $\gamma$  equipped
with an additive size $|\gamma|$ with positive increments (marked by
$t$), and an additive catalytic parameter $c(\gamma)$ with signed
increments but a non-negativity constraint (marked by $u$): the series
$f=F(t,0)$ is the gf of 
$\mathcal{F}_0=\{\gamma\in\mathcal{F}\mid c(\gamma)=0\}$ and $\frac
d{dt}f$ is a gf for marked
$\mathcal{F}_0$-structures.

Following the Sch\"utzenberger methodology 
\cite{gs:BM-ICM}, the fact that  $\frac d{dt}f$ can be expressed positively in terms
of the solutions of System~\eqref{eq:CFS} raises the question of
giving a context-free specification of the form~\eqref{eqn:combiCFS} for marked
$\mathcal{F}_0$-structures.
%
To do this some knowledge of the actual recursive
decomposition of the $\mathcal{F}$-structures is needed, which is
typically encoded by a family of \emph{derivation trees} describing
the way the recursion unfolds.
%
Our model of non-negative
$\mathcal{Q}$-trees includes naturally many (most?) of the
derivation trees associated to first order catalytic decompositions in
the literature. Hence our result yields a generic recipe to
convert a catalytic specification governed by
\Cref{eqn:eq1} into a bijection between the associated
derivation trees for $\mathcal{F}_0$ and simple varieties of multi-type trees governed by
\Cref{eq:fCFS}--\eqref{eq:CFS}. Depending on the actual
relation between the underlying combinatorial structures and their
derivation trees, this can then also lead to a direct context-free specification
of the marked $\mathcal{F}_0$-structures counted by $\frac{d}{dt}f$.

A natural followup of this work is to make explicit the direct
context-free specifications that derives from our result for
the many known families of combinatorial structures governed by
order-one catalytic equations. With the exception of \cite{FFN24}, the
only results of this type we are aware of are for planar maps: they go
back to work of Cori prompted by Sch{\"u}tzenberger
{\cite{AST_1975__27__1_0}}, with a rich series of
subsequent works {\cite{chapterMaps}} with ongoing offsprings.
%{\cite{bouttier2021bijective}}.
Hopefully the present extension of these ideas
to arbitrary structures governed by order one catalytic equations can
lead to further interesting developments.

\acknowledgements{To W. Fang, Y. Kahane and C. Henriet for interesting discussions. To the referees for useful comments and suggestions of improvement of the text.}


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way

\printbibliography

\end{document}

