# From order one catalytic decompositions to context-free specifications, bijectively

Gilles Schaeffer, Enrica Duchi

► To cite this version:

Gilles Schaeffer, Enrica Duchi. From order one catalytic decompositions to context-free specifications, bijectively. 37th Conference on Formal Power Series and Algebraic Combinatorics (Sapporo), Jul 2025, Sapporo, Japan. pp.12. [hal-05385629](https://hal.science/hal-05385629v1)

HAL Id: hal-05385629

https://hal.science/hal-05385629v1

Submitted on 27 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# From order one catalytic decompositions to context-free specifications, bijectively

Enrica Duchi*<fnref n="1" /> and Gilles Schaeffer†<fnref n="2" />

**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.

**Keywords:** Bijective Combinatorics, Generating Functions

## 1 Introduction

An order one catalytic equation is an equation of the form

$$F(t, u) = t \cdot Q \left( F(t, u), \frac{1}{u} (F(t, u) - F(t, 0)), u \right), \quad (1.1)$$

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 in power series solutions $F(t, u)$ in the variables $t$ and $u$. We refer to [2, 10] for the relevance of these equations in the combinatorial literature, and examples of their many occurrences.

In [2], Bousquet-Mélou and Jehanne proved that a very general family of *polynomial equations with one catalytic variable* have algebraic power series solutions. More precisely,

<footnote n="1">¹IRIF, Université Paris Cité</footnote>

<footnote n="2">²LIX, CNRS, Ecole polytechnique, Institut Polytechnique de Paris</footnote>

<footnote>*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).</footnote>

<footnote>†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).</footnote>
as discussed in [18], in the case of a order one catalytic equation like (1.1) 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

$$f = C_{\square} - C_{\diamond} \cdot C_{\triangle} \quad \text{or} \quad \frac{d}{dt} f = (1 + C_{\bullet}) \cdot Q(C_{\square}, C_{\triangle}, C_{\diamond}), \qquad (1.2)$$

where $C_{\square} \equiv C_{\square}(t)$, $C_{\bullet} \equiv C_{\bullet}(t)$, $C_{\diamond} \equiv C_{\diamond}(t)$ and $C_{\triangle} \equiv C_{\triangle}(t)$ are the unique power series that satisfy the companion system

$$\left\{ \begin{aligned} C_{\square} &= t \cdot Q(C_{\square}, C_{\triangle}, C_{\diamond}), \\ C_{\bullet} &= t \cdot (1 + C_{\bullet}) \cdot Q'_{v}(C_{\square}, C_{\triangle}, C_{\diamond}), \\ C_{\diamond} &= t \cdot (1 + C_{\bullet}) \cdot Q'_{w}(C_{\square}, C_{\triangle}, C_{\diamond}), \\ C_{\triangle} &= t \cdot (1 + C_{\bullet}) \cdot Q'_{u}(C_{\square}, C_{\triangle}, C_{\diamond}). \end{aligned} \right. \qquad (1.3)$$

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 Equation (1.1) in terms of labeled trees with non-negativity conditions on labels. This was done for instance in [9] for a closely related family of equations, in terms of some *description trees*, or more recently in [5] for a special case of Equation (1.1) in terms of some *fully parked trees*. On the other hand, under the same hypotheses on $Q(v, w, u)$, System (1.3) is a so-called *N-algebraic system*, and the power series $C_{\square}$, $C_{\bullet}$, $C_{\diamond}$ and $C_{\triangle}$ admit natural interpretations as generating functions (gf) of simple varieties of multi-type trees, as discussed in [1], or [14, Chapter I, ex. I.53, p. 82]. However, by default there is no clear relations between the first and second types of interpretations.

Our contribution<fnref n="1" /> is to fill in this gap by providing a general interpretation of Equation (1.1) in terms of a family of *non-negative Q-trees* (Section 2) and a bijection (Theorem 3.1) between these trees and a related family of *Q-companion trees* (Section 3) that provide simple interpretations of Equation (1.2) and System (1.3) (Theorems 3.2 and 3.4).

# 2 Non-negative Q-trees

## 2.1 Necklaces and non-negative Q-trees

Let $Q$ denote a set of words on an alphabet $\{\bullet, \diamond, \triangle\}$ of *pearls*: we identify each element $w = w_1 \dots w_k$ of $Q$ with a clockwise oriented necklace carrying one $\square$-pearl followed by the pearls $w_1, \dots, w_k$. In the rest of the article the set $Q$ will be viewed as the set of allowed vertex types for various families of plane trees. Accordingly, to a set $Q$ of

<footnote n="1">¹In this extended abstract all proofs are omitted, see full text [11] for proofs.</footnote>
<figure><img src="image_2.png" /><figcaption>**Figure 1:** The graphical representation of the necklace $w = \bullet\blacklozenge\blacklozenge\blacklozenge\blacklozenge$, and the necklace sets $Q_{\text{all}} = \{\bullet, \blacklozenge, \blacklozenge\}^*$ and $Q_{\lambda} = \{\bullet\bullet, \blacklozenge, \blacklozenge\}$.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Figure 2:** Three rooted $Q_{\text{all}}$-trees with their excess labels, and with root indicated by a ○ around the root □-pearl. The third one is also a $Q_{\lambda}$-tree. The second and third ones are non-negative while the first one is not.</figcaption></figure>

necklaces we associate<fnref n="2" /> the vertex type generating function $Q(v, w, u)$ as

$$Q(v, w, u) = \sum_{s \in Q} v^{|s|} \bullet w^{|s|} \blacklozenge u^{|s|} \blacklozenge. \qquad (2.1)$$

The necklace associated to the word $w = \bullet\blacklozenge\blacklozenge\blacklozenge$ is represented on Figure 1, together with our two running examples of necklace sets: $Q_{\text{all}} = \{\bullet, \blacklozenge, \blacklozenge\}^*$, the set of all necklaces, and $Q_{\lambda} = \{\bullet\bullet, \blacklozenge, \blacklozenge\}$, with only three allowed necklaces, with respective vertex generating functions $Q_{\text{all}}(v, w, u) = 1/(1 - (v + w + u))$ and $Q_{\lambda}(v, w, u) = v^2 + w + u$.

As illustrated by Figure 2, a *rooted Q-tree* is a □-rooted plane tree with black and red edges such that

* each vertex is a copy of a necklace of $Q$,

* each black edge connects a ●-pearl to a □-pearl, i.e., takes the form ●□,

* each red edge connects a ♦-pearl to a □-pearl, i.e., takes the form ♦□,

* each pearl is incident to one edge except the □-root and the ▲-pearls which are *free*, that is, incident to no edge.

The size $|\tau|$ of a $Q$-tree $\tau$ is the number of its vertices. By construction it is also the number $|\tau|_{\square}$ of □-pearls, and the number of edges plus one: $|\tau| = |\tau|_{\square} = |\tau|_{\bullet} + |\tau|_{\blacklozenge} + 1$.

<footnote n="2">²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 Q_{\text{all}}} q_s v^{|s|} \bullet w^{|s|} \blacklozenge u^{|s|} \blacklozenge$.</footnote>
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 •- or ♦-pearls.

The subtree $\tau_x$ of a rooted $\mathcal{Q}$-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 excess of a pearl $x$ in the $\mathcal{Q}$-tree $\tau$ is the difference between the number of ▲- and ♦-pearls in the subtree planted at $x$, $x$ included: $\mathrm{exc}(x) = |\tau_x|_{▲} - |\tau_x|_{♦}$. The excess of a vertex $v$ is the excess of its local root (the only □-pearl on $v$), and the excess of $\tau$ is the excess of its root, that is $\mathrm{exc}(\tau) = |\tau|_{▲} - |\tau|_{♦}$. A non-negative $\mathcal{Q}$-tree is a $\mathcal{Q}$-tree whose excess is non-negative at each pearl. These definitions are illustrated by Figure 2. Observe that the non-negativity condition at each pearl in the definition of non-negative $\mathcal{Q}$-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 Figure 2 whereas it is not non-negative due to its ♦-pearl with excess $-1$.

**Proposition 2.1.** Let $\mathcal{Q}$ be as in (2.1) and $\mathcal{F}_k$ denote the set of non-negative $\mathcal{Q}$-trees with excess $k$ and $\mathcal{F} = \cup_{k \ge 0} \mathcal{F}_k$. Then the family $\mathcal{F}$ of non-negative $\mathcal{Q}$-trees admits a catalytic specification:

$$ \mathcal{F} \equiv \mathcal{Q}(\bullet\text{-}\mathcal{F}, \diamond\text{-}\mathcal{F}^+, \blacktriangle), \qquad (2.2) $$

meaning that each tree of $\mathcal{F}$ can be uniquely obtained from a necklace $s \in \mathcal{Q}$ upon attaching

* a black edge carrying a tree of $\mathcal{F}$ to each •-pearl of $s$,

* and a red edge carrying a tree of $\mathcal{F}^+ = \mathcal{F} \setminus \mathcal{F}_0$ to each ♦-pearl of $s$.

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 Equation (1.1), with $F(u) - F(0) = F^+(u) = \sum_{\tau \in \mathcal{F}^+} t^{|\tau|} u^{\mathrm{exc}(\tau)}$.

## 2.2 The closure and rewiring of a non-negative $\mathcal{Q}$-tree

A plane map (resp. 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 [17]. 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 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 $\mathcal{Q}$-tree $\tau$, as illustrated by Figures 3 and 4, let

* a left ♦-corner refer to the exterior angular sector following a red edge in counterclockwise direction around a ♦-pearl,
<figure><img src="image_4.png" /><figcaption>**Figure 3:** The left ♦-corners and ▲-corners of a non-negative Q-tree, and the matching of a left ♦-corner with the next available ▲-corner in clockwise direction.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 4:** The matchings after first iteration and final result of the ♦-to-▲ clockwise closure of the tree of Figure 3.</figcaption></figure>

• a ▲-corner refer to the exterior angular sector around a ▲-pearl, and define the (♦-to-▲ clockwise) closure $c(τ)$ of $τ$ as the plane map obtained by iteratively matching unmatched left ♦-corners that are followed by an unmatched ▲-corner in clockwise direction around the tree, to form a planar system of non-crossing ♦-to-▲ clockwise edges, hereafter called *blue edges* (♦▲). This construction is a standard ingredient of many bijections between plane maps and trees (see e.g. [17, Theorem 6]).

**Proposition 2.2.** The closure $c(τ)$ of a non-negative Q-tree $τ$ is a □-rooted plane maps with vertices in Q, and black edges (●□), red edges (♦□) and blue edges (▲♦) such that: (i) The black and red edges of the spanning tree $τ$ of $c(τ)$ are such that all blue edges are ♦-to-▲ clockwise around $τ$. (ii) The clockwise walk around each bounded face of $c(τ)$ visits exactly one blue edge in ♦-to-▲ direction and one red edge in □-to-♦ direction, and these two edges share their ♦-pearl. (iii) Each ♦-pearl $x$ of $τ$ is matched with a ▲-pearl in its subtree $τ_x$. (iv) All unmatched ▲-pearls in $c(τ)$ lie in the unbounded face. The closure is injective and its inverse is the opening that consists in deleting blue edges.

The *rewiring* $\phi(\tau)$ of a Q-tree $\tau$ consists in its closure followed by the removal of red edges, as illustrated by Figure 5.

**Proposition 2.3.** The rewiring $\phi(\tau)$ of a non-negative Q-tree $\tau$ is a tree with the same necklaces.
<figure><img src="image_6.png" /><figcaption>**Figure 5:** The tree $\tau$ of Figure 3 (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.</figcaption></figure>

# 3 Q-companion trees and their decomposition

## 3.1 Q-companion trees and the main bijection

By construction, rewiring replaces each red edge of the form $\Leftrightarrow$ by a blue edge of the form $\Leftrightarrow$ originating from the same $\blacklozenge$-pearl, as illustrated by Figure 5. Let us define *rooted Q-companion trees* as pearl rooted plane trees with black and blue edges such that

* each vertex is a copy of a necklace of $Q$,

* each black edge connects a $\bullet$-pearl to a $\square$-pearl, i.e., takes the form $\bullet$.

* each blue edge connects a $\blacklozenge$-pearl to a $\triangle$-pearl, i.e., takes the form $\Leftrightarrow$.

* each non-root $\bullet$- or $\blacklozenge$-pearl is incident to exactly one edge, the root pearl is free (i.e., incident to no edge) and each $\square$- or $\triangle$-pearl is incident to at most one edge.

The root pearl of a $Q$-companion tree can be of any type $\square$, $\bullet$, $\blacklozenge$, or $\triangle$. By convention an *unrooted Q-companion tree* is an equivalence class of $\square$-rooted (or $\triangle$-rooted) $Q$-companion trees up to rerooting: in other terms it is an unrooted plane tree satisfying the conditions above and without free $\bullet$- or $\blacklozenge$-pearl (as it arises from $\square$-rooted trees).

In any tree the number of vertices equals the number of edges plus one, so by definition, in a $\square$- or $\triangle$-rooted $Q$-companion tree $\tau'$, $|\tau'|_{\square} = |\tau'|_{\bullet} + |\tau'|_{\blacklozenge} + 1$. In particular this implies that the number of $\square$-pearls that are free is equal to the number of $\blacklozenge$-pearls plus one. Like in Section 2.2, we then define the inverse ($\blacklozenge$-to-$\square$ counterclockwise) closure $\bar{c}(\tau')$ of a $\square$-rooted, $\triangle$-rooted or unrooted $Q$-companion tree $\tau'$ as the plane map obtained by matching iteratively right $\blacklozenge$-corners that are followed by an unmatched $\square$-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 $\square$-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)$.
<figure><img src="image_7.png" /><figcaption>**Figure 6:** Three rooted Q-companion trees (root pearl indicated by ○) with their inverse closure edges (dashed red lines), and sharing the same underlying unrooted tree. The leftmost tree is □-rooted and unbalanced, the middle one is □-rooted and balanced, they both have one internal and one external defects. The rightmost one is ▲-rooted and unbalanced, without internal defects (root ▲-pearls do not count).</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>**Figure 7:** An unbalanced Q-companion tree without defect and the corresponding pair of ♦- and ▲-rooted Q-companion trees without defects.</figcaption></figure>

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

**Theorem 3.1.** *Rewiring and inverse rewiring are necklace-preserving bijections between*

* non-negative Q-trees with excess $k \ge 0$,

* and balanced □-rooted Q-companion trees with $k$ external defects and no internal defects.

## 3.2 Unrooted and rooted Q-companion trees without defects

Let $C$ denote the family of unrooted $Q$-companion trees without defects, and $C_{\square}$, $C_{\bullet}$, $C_{\diamond}$ and $C_{\triangle}$ denote respectively □-, •-, ♦- and ▲-rooted $Q$-companion trees without defects
(without the requirement of being balanced).

**Theorem 3.2.** There are necklace-preserving bijections between

* balanced □-rooted Q-companion trees without defects,

* and unrooted Q-companion trees without defects, and, as illustrated by Figure 7, between

* unbalanced □-rooted Q-companion trees without defects,

* and pairs made of a ♦-rooted Q-companion tree and a ▲-rooted Q-companion tree, both without defects.

Theorems 3.1 and 3.2 reduce the enumeration of non-negative Q-trees with excess 0 to that of rooted Q-companion trees without defects.

**Corollary 3.3.** There is a necklace-preserving bijection between $C_{\square}$ and $C \cup (C_{\diamond} \times C_{\triangle})$, or in other terms, between non-negative Q-trees with excess 0, and □-rooted Q-companion trees that are not unbalanced:

$$F_0 \equiv C \equiv C_{\square} \setminus (C_{\diamond} \times C_{\triangle}).$$

In particular this yields our combinatorial interpretation of the first equation in (1.2) with $f \equiv F(t, 0) = \sum_{\tau \in F_0} t^{|\tau|}$ the gf of non-negative Q-trees with excess 0, $C \equiv C(t) = \sum_{\tau \in C} t^{|\tau|}$ that of unrooted Q-companion trees, and $C_{\square}$, $C_{\bullet}$, $C_{\diamond}$, and $C_{\triangle}$ of □-rooted, •-rooted, ♦-rooted, and ▲-rooted Q-companion trees.

## 3.3 The decomposition of Q-companion trees without defects

The analysis of possible root necklaces in Q-companion trees is illustrated by Figure 8:

* the set of root vertex types of □-rooted Q-companion trees is Q, since each necklace $s \in Q$ has exactly one □-pearl,

* the set $Q'_{\bullet}$ of root vertex types of •-rooted Q-companion trees is the union for all necklaces $s \in Q$ of the $|s|_{\bullet}$ different rerootings of s on a •-pearl,

* the set $Q'_{\diamond}$ of ♦-rooted Q-companion trees and $Q'_{\triangle}$ of ▲-rooted Q-companion trees are obtained similarly.

Any □-rooted Q-companion tree without defects can thus be uniquely produced by selecting a necklace $s \in Q$ together with $|s|_{\bullet}$ subtrees from $Q_{\square}$, $|s|_{\diamond}$ subtrees from $Q_{\triangle}$ and $|s|_{\triangle}$ subtrees from $Q_{\diamond}$, and attaching these subtrees to the pearls of s. This operation is summarized as $C_{\square} \equiv Q(\bullet-C_{\square}, \diamond-C_{\triangle}, \triangle-C_{\diamond})$.

The same approach allows us to deal with •-rooted Q-companion trees without defects, upon taking $s \in Q'_{\bullet}$ and adding a possibly empty extra subtree in $Q_{\bullet}$ to attach to the □-pearl of s. The other classes $C_{\diamond}$ and $C_{\triangle}$ admit similar decompositions.

**Theorem 3.4.** The standard root vertex decomposition of multi-type rooted trees yields the following context-free specification of rooted Q-companion trees without defects:
<figure><img src="image_9.png" /><figcaption>**Figure 8:** On the left hand side, the decompositions of rooted $Q$-companion trees, illustrated in the case of a root vertex with necklace type ●▲●▲♦. On the right hand side, the corresponding derived necklaces types and contribution to the necklace gf.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>**Figure 9:** A closed planar $\lambda$-term (bottom left), the corresponding non-negative $Q_\lambda$-tree (blue closing edges) and its balanced $Q_\lambda$-companion tree (red closure edges). On the right the decomposition of □- and ●-rooted $Q_\lambda$-companion trees without excess.</figcaption></figure>
$$
\left\{
\begin{array}{l}
C_{\square} \equiv Q(\bullet-C_{\square}, \blacklozenge-C_{\triangle}, \blacktriangle-C_{\diamond}), \\
C_{\bullet} \equiv (\square+\boxdot-C_{\bullet}) \times Q'_{\bullet}(\bullet-C_{\square}, \blacklozenge-C_{\triangle}, \blacktriangle-C_{\diamond}), \\
C_{\diamond} \equiv (\square+\boxdot-C_{\bullet}) \times Q'_{\diamond}(\bullet-C_{\square}, \blacklozenge-C_{\triangle}, \blacktriangle-C_{\diamond}), \\
C_{\triangle} \equiv (\square+\boxdot-C_{\bullet}) \times Q'_{\triangle}(\bullet-C_{\square}, \blacklozenge-C_{\triangle}, \blacktriangle-C_{\diamond}), \\
C^{\circ} \equiv (\square+\boxdot-C_{\bullet}) \times Q(\bullet-C_{\square}, \blacklozenge-C_{\triangle}, \blacktriangle-C_{\diamond}),
\end{array}
\right.
\qquad (3.1)
$$

where $Q(\bullet-C_{\square}, \blacklozenge-C_{\triangle}, \bullet-C_{\diamond})$ denotes the set of trees obtained from a necklace of $Q$ by attaching to each $\bullet$-pearl a subtree of the form $\bullet-C_{\square}$, to each $\triangle$-pearl a subtree of the form $\blacktriangle-C_{\diamond}$, and to each $\diamond$-pearl a subtree of the form $\blacklozenge-C_{\triangle}$, and similarly for the other equations, and where $C^{\circ}$ denotes the set of unrooted $Q$-companion trees without defects with a marked necklace.

The first four equations yield our interpretation of System (1.3). Since marking a necklace in an unrooted $Q$-companion tree amounts to marking the same necklace in the corresponding non-negative $Q$-tree, the fifth equation yields our interpretation of the second equation in (1.2).

# 4 The example of $\lambda$-terms and parking functions

The planar $\lambda$-terms of [19] 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 closed if the matching leaves no unmached variables.

As illustrated by Figure 9, 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 Figure 1). In particular, their gf is governed by the corresponding catalytic equation: $F(u) = tQ_{\lambda}(F(u), \frac{1}{u}(F(u) - F(0)), u) = tu + tF(u)^2 + \frac{t}{u}(F(u) - F(0))$. Theorem 3.1 yields a direct bijection between closed planar $\lambda$-terms with $n$ abstractions (and $n$ variables and $n-1$ applications) and unrooted $Q_{\lambda}$-companion trees with $3n-1$ necklaces. According to Theorem 3.4, the corresponding $\square$-rooted $Q_{\lambda}$-companion trees are governed by the $\mathbb{N}$-algebraic system of Figure 9, with in particular $C_{\square} = tC_{\square}^2 + 2t^2(1+C_{\bullet})$, and $C_{\bullet} = 2tC_{\square}(1+C_{\bullet})$. This decomposition can be wrapped up in a single equation, i.e. $\square$-rooted $Q_{\lambda}$-companion trees form a simple variety of trees [14]: $C_{\square} = tC_{\square}^2 + 2t^2/(1-2tC_{\square})$. As far as we know this is the first direct bijection between $\lambda$-terms and simple trees.

Non-negative $Q$-trees also encompass the parking trees of [16], also studied in [5, 7, 6]. In this context, non-negative $Q$-trees can be viewed as a generalization of parking trees where the $\triangle$-pearls play the role of cars and the $\diamond$-pearls that of parking spots, and non-negative trees with excess 0 correspond to 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 [7] to relate the properties of a specific type of such random fully parked trees to random Galton-Watson trees.
# 5 Conclusion

In many instances, e.g. [4, 3, 5, 9, 12, 15, 19], Equation (1.1) arises from the translation for the gf $F(t,u)$ of a catalytic specification of the form (2.2) 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ützenberger methodology [1], the fact that $\frac{d}{dt}f$ can be expressed positively in terms of the solutions of System (1.3) raises the question of giving a context-free specification of the form (3.1) 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 *derivation trees* describing the way the recursion unfolds. Our model of non-negative $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 Equation (1.1) into a bijection between the associated derivation trees for $\mathcal{F}_0$ and simple varieties of multi-type trees governed by Equation (1.2)–(1.3). 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 [13], the only results of this type we are aware of are for planar maps: they go back to work of Cori prompted by Schützenberger [8], with a rich series of subsequent works [17] with ongoing offsprings. 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.

# References

[1] M. Bousquet-Mélou. "Rational and algebraic series in combinatorial enumeration". *International Congress of Mathematicians. Vol. III*. Eur. Math. Soc., Zürich, 2006, pp. 789–826.
[2] M. Bousquet-Mélou and A. Jehanne. "Polynomial equations with one catalytic variable, algebraic series and map enumeration". *J. Comb. Theory, Ser. B* **96.5** (2006), pp. 623–672. DOI.

[3] F. Chapoton. "Sur le nombre d'intervalle dans les treillis de Tamari". *Sém. Lothar. Combin.* **55** (2005/07), Art. B55f, 18 pp.

[4] F. Chapoton. "Some properties of a new partial order on Dyck paths". *Algebr. Comb.* **3.2** (2020), pp. 433–463. DOI.

[5] L. Chen. "Enumeration of fully parked trees". 2021. arXiv:2103.15770.

[6] A. Contat. "Last car decomposition of planar maps". *Ann. Inst. Henri Poincaré Comb. Phys. Interact.* (2024).

[7] A. Contat. "Parking on trees with a (random) given degree sequence and the frozen configuration model". *Electron. J. Probab.* **30** (2025), Paper No. 37, 25 pp. DOI.

[8] R. Cori. *Un code pour les graphes planaires et ses applications*. Vol. No. 27. Astérisque. Société Mathématique de France, Paris, 1975, pp. i+169. Link.

[9] R. Cori and G. Schaeffer. "Description trees and Tutte formulas". *Theoret. Comput. Sci.* **292.1** (2003). Selected Papers in honor of Jean Berstel, pp. 165–183. DOI.

[10] M. Drmota, M. Noy, and G.-R. Yu. "Universal singular exponents in catalytic variable equations". *J. Combin. Theory Ser. A* **185** (2022), Paper No. 105522, 33 pp. DOI.

[11] E. Duchi and G. Schaeffer. "From order one catalytic decompositions to context-free specifications, bijectively". Submitted. 2024. arXiv:2412.20628.

[12] W. Fang. "A partial order on Motzkin paths". *Discrete Math.* **343.5** (2020), 111802, 9 pp. DOI.

[13] W. Fang, É. Fusy, and P. Nadeau. "Tamari intervals and blossoming trees". 2024. arXiv:2312.13159.

[14] P. Flajolet and R. Sedgewick. *Analytic combinatorics*. Cambridge University Press, Cambridge, 2009, xiv+810 pp. DOI.

[15] I. P. Goulden and J. West. "Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations". *J. Combin. Theory Ser. A* **75.2** (1996), pp. 220–242. DOI.

[16] M.-L. Lackner and A. Panholzer. "Parking functions for mappings". *J. Combin. Theory Ser. A* **142** (2016), pp. 1–28. DOI.

[17] G. Schaeffer. "Planar maps". *Handbook of enumerative combinatorics*. Discrete Math. Appl. (Boca Raton). CRC Press, Boca Raton, FL, 2015, pp. 335–395.

[18] G. Schaeffer. "On universal singular exponents in equations with one catalytic parameter of order one". *EuroComb*. Prague, Czech Republic, 2023, pp. 806–811. DOI.

[19] N. Zeilberger and A. Giorgetti. "A correspondence between rooted planar maps and normal planar lambda terms". *Log. Methods Comput. Sci.* **11.3** (2015), 3:22, 39 pp. DOI.