# A bijection between shrubs and series-parallel posets

Frédéric Chapoton†

Université de Lyon; Université Lyon 1; Institut Camille Jordan CNRS UMR 5208; 43, boulevard du 11 novembre 1918, F-69622 Villeurbanne Cedex.

**Abstract.** Motivated by the theory of operads, we introduce new combinatorial objects, called shrubs, that generalize forests of rooted trees. We show that the species of shrubs is isomorphic to the species of series-parallel posets.

**Résumé.** Motivé par des considérations sur les opérades, on introduit de nouveaux objets combinatoires, appelés arbustes, qui généralisent les forêts d'arbres enracinés. On montre que l'espèce des arbustes est isomorphe à l'espèce des posets Série-Parallèle.

**Keywords:** tree, poset, species, bijection

## 1 Introduction

Series-parallel posets, also called *N*-free posets, are classical combinatorial objects (Sta74; Sta99). Informally, they are the posets that can be obtained from the one element poset by iterating disjoint union and concatenation of posets. They can also be described by exclusion of one forbidden pattern in the Hasse diagrams.

We introduce here new objects, called shrubs, and show that they share the same underlying species as series-parallel posets. The combinatorics is subtly different though. These objects are some kind of diagrams with levels, that are not trees in a topological sense but still have some kind of tree-flavor, hence the chosen name. They can be obtained from the one point diagram by iteration of disjoint union and another construction. We define them by exclusion of two forbidden patterns.

These objects were motivated by some constructions related to operads and themselves form an operad. More precisely, the species of shrubs can be endowed with the structure of an anticyclic operad. This operad is naturally contained in the Zinbiel operad, which is an anticyclic operad on the (vector-space valued) species of permutations. Shrubs form the smallest possible set of elements of Zinbiel containing permutations and closed under the structure of anticyclic operad.

From a combinatorial point of view, the inclusion in the Zinbiel operad implies the following interpretation. These diagrams should not be considered as Hasse diagrams of posets, but rather as describing

<footnote>†Support du programme ANR-06-BLAN-0380</footnote>
<figure><img src="image_1.png" /><figcaption>Fig. 1: One shrub.</figcaption></figure>

some boolean combination of inequalities: each vertex is greater than at least one of the vertices below it.

Details and proofs on these algebraic aspects will appear elsewhere. We concentrate here on the combinatorics.

We work in the context of species (BLL98) and the reader is assumed to be familiar with this language.

## 2 Definition of shrubs

Let $I$ be a finite set. A **shrub** on $I$ is the data of a simple graph on $I$ and a level function from $I$ to $\mathbb{N}$ satisfying the following conditions:

1. Each edge links two vertices whose level differ by 1.

2. Each vertex $i$ has at least one neighbor of level $\ell(i) - 1$, unless $\ell(i) = 0$.

3. The following patterns are excluded: and .

Here, the exclusion of a pattern means the following: there is no subset of vertices such that the induced graph (with induced level map) is isomorphic to the pattern (up to shift of the levels). This means that a shrub containing all the edges of a pattern does contains other edges between the chosen vertices.

One says that a shrub is connected if the underlying graph is. Each connected component of a shrub is itself a connected shrub.

**Remark:** one can truncate a shrub by removing vertices of level smaller than $k$ for some fixed $k \ge 0$. The result is still a shrub.

One can see a rooted tree (i.e. a connected and simply connected graph with a distinguished vertex called the root) as a shrub. The level is defined as the distance from the root. More generally, any forest (disjoint union of rooted trees) is a shrub.

Also, any complete bipartite graph is a shrub, if we define the level to be 0 on one part and 1 on the other part of the partition.

**Conventions and notations:**

Shrubs will be drawn with level increasing from bottom to top.

Edges will be oriented from top to bottom.

We will say that a vertex $i$ **covers** a vertex $j$ if there is an edge $i \to j$.

We will say that a vertex $i$ **is above** a vertex $j$ if there is a path

$$i \to \dots \to j. \tag{1}$$
<figure><img src="image_2.png" /><figcaption>Fig. 2: The 30 classes of connected shrubs on 5 vertices.</figcaption></figure>

A vertex $i$ of a shrub $P$ is called ramified if there at least two edges going down from $i$. Shrubs without ramified vertices are exactly forests of rooted trees.

Figure 2 shows the isomorphism classes of connected shrubs on 5 vertices. Ramified vertices are highlighted. In this figure, shrubs are gathered by orbits for an action that we will not define here.

## 3 Lemmas on shrubs

**Lemma 3.1** Let $P$ be a shrub. Let $a_0, a_1, \dots, a_s$ be vertices of the same height in $P$. If there exists a vertex $b$ above all $a_i$, then there exists a vertex $b'$ covering all $a_i$ and a path

$$b \to \dots \to b' \qquad (2)$$

**Proof:** By induction on the level of $b$. If $\ell(b) = \ell(a_0) + 1$, we can take $b' = b$. Assume this is not the case. There exist a vertex $d_0$, and for each $i \ge 1$, vertices $d_i, e_i$ and paths

$$a_0 \leftarrow \dots \leftarrow d_0 \leftarrow b \to d_i \to e_i \to \dots \to a_i, \qquad (3)$$

where $e_i$ can be the same as $a_i$. We use the excluded pattern $\mathcal{C}$ on vertices $\{b, d_0, d_i, e_i\}$ to show that there is an edge from $d_0 \to e_i$, hence a path from $d_0$ to $a_i$ for each $i \ge 1$. As the level of $d_0$ is smaller than that of $b$, the conclusion follows by induction. $\square$

**Lemma 3.2** Let $P$ be a shrub. Let $a$ and $a'$ be two vertices of level 0 in $P$. Assume that there exists vertices $a = a_0, \dots, a_s = a'$ of level 0 and vertices $b_i$ of level 1 for $0 \le i \le s-1$ and edges

$$a_i \leftarrow b_i \to a_{i+1}. \qquad (4)$$

Then there exists a vertex $c$ of level 1 and edges

$$a \leftarrow c \to a'. \qquad (5)$$
**Proof:** By induction on $s$. If $s = 1$, there is nothing to prove. Else, we can use the excluded pattern ⋀<sub>i=0</sub><sup>l</sup> ⋀<sub>j=0</sub><sup>l</sup> on vertices $a_0, a_1, a_2, b_0, b_1$. We deduce that there is an edge from $b_1$ to $a_0$ or an edge from $b_0$ to $a_2$.

In any case, one gets, by removing $a_1$ and $b_0$ or $b_1$, a shortest sequence satisfying the same hypothesis. Hence the Lemma follows by induction. □

**Lemma 3.3** Let $P$ be a connected shrub with at least 2 vertices. Let $a$ and $a'$ be vertices of level 0 in $P$. Then there exists a vertex $b$ and edges $a \leftarrow b \to a'$.

**Proof:** By connectedness, there exists a sequence of (unoriented) consecutive edges from $a$ to $a'$. As each vertex of positive level has at least one out-going edge, one can extend this sequence and find vertices $a = a_0, \dots, a_l = a'$ of level 0, vertices $b_i$ for $0 \le i \le l-1$ and paths

$$a_i \leftarrow \dots \leftarrow b_i \rightarrow \dots \rightarrow a_{i+1}. \qquad (6)$$

By Lemma 3.1, we can then find vertices $b'_i$ of level 1 and edges

$$a_i \leftarrow b'_i \rightarrow a_{i+1}. \qquad (7)$$

By Lemma 3.2, one can find a vertex $c$ and edges $a \leftarrow c \to a'$. □

**Proposition 3.4** Let $P$ be a connected shrub with at least 2 vertices. There exists in $P$ at least one vertex of level 1 covering all vertices of level 0.

**Proof:** Let $e$ be a vertex of level 1 covering the maximal number of vertices of level 0. Assume that there exists a vertex $a$ of level 0 not covered by $e$.

Let $b$ be a vertex covered by $e$. Let $d$ be a common cover of $a$ and $b$, which exists by the Lemma 3.3. Then $d$ is distinct from $e$ by hypothesis.

Let $c$ be a vertex covered by $e$ and distinct from $b$ if it exists. Let us consider the induced graph on $\{a, b, c, d, e\}$. By the excluded pattern ⋀<sub>i=0</sub><sup>l</sup> ⋀<sub>j=0</sub><sup>l</sup> ⋀<sub>k=0</sub><sup>l</sup>, either $e$ covers $a$, or $d$ covers $c$. As $e$ does not cover $a$ by hypothesis, one gets that $d$ covers $c$.

We have thus shown (both if there is a $c$ as above and if there is not) that $d$ covers all vertices covered by $e$ and also $a$. This contradicts the maximality of $e$. Hence the existence of $a$ is absurd and $e$ covers all vertices of level 0. □

**Proposition 3.5** Let $P$ be a connected shrub with at least 2 vertices. Let $S$ be the set of vertices of level 1 covering all vertices of level 0. In the graph $\tilde{P}$ obtained from $P$ by removing all edges between $S$ and vertices of level 0, no vertex of $S$ is in the same connected component as a vertex of level 0.

**Proof:** Assuming the contrary, there is a sequence of (unoriented) consecutive edges from a vertex of $S$ to a vertex of level 1 not in $S$.

One can then find $c$ and two paths $c = a_m \to a_{m-1} \to \dots \to a_1 = a$ et $c = a'_m \to a'_{m-1} \to \dots \to a'_1 = a'$ with $a \in S$ and $a' \notin S$.

By Lemma 3.1, one can assume that $c$ has level 2. By the excluded pattern ⋀<sub>i=0</sub><sup>l</sup> applied to vertices $a, c, a'$ and any vertex of level 0, one shows that $a'$ covers all vertices of level 0 and hence is in $S$. This is absurd. □
# 4 Operations on shrubs

Given two finite sets $I$ and $J$ and two shrubs $P$ and $Q$ on $I$ and $J$, one can form new shrubs on $I \sqcup J$ as follows.

Let us denote by $P \sqcup Q$ the disjoint union of $P$ and $Q$. This is an associative and commutative product on the set of shrubs.

**Proposition 4.1** Each shrub $P$ has a unique decomposition as the disjoint union of connected shrubs.

Let us now introduce a shrub $P \triangleleft Q$. As a graph, it is obtained from the disjoint union of the graph of $P$ and the graph of $Q$ by adding a complete bipartite graph joining the vertices of level 0 in $P$ and the vertices of level 0 in $Q$. The level function is unchanged on the vertices of $P$ and get shifted by +1 on the vertices of $Q$.

It is not hard to see that the result is a shrub $P \triangleleft Q$, the only point to check being the excluded patterns.

This operation $\triangleleft$ is not associative, but satisfies the relation

$$ (P \triangleleft Q) \triangleleft R = (P \triangleleft R) \triangleleft Q, \qquad (8) $$

which defines a NAP algebra (Liv06).

Let us call a shrub indecomposable if it is not-connected or has one vertex.

**Proposition 4.2** Each connected shrub $P$ with at least two vertices has a unique decomposition $P = Q \triangleleft R$ where $Q$ is indecomposable.

**Proof:** Let us first prove the existence of such a decomposition. Let $P$ be a shrub on the set $I$. Let $I_+$ be the set of vertices which are above all vertices of level 0 in $P$. Let $I_-$ be the complement of $I_+$ in $I$. Let $Q$ be the induced graph on $I_-$ with the restriction of the level function. Let $R$ be the induced graph on $I_+$, with level function shifted by -1.

Let us now show that $Q$ is a shrub. The exclusion of the forbidden patterns is obvious. There remains to check that for each vertex $i$ of positive level in $Q$, there is an edge $i \to j$ with $j$ in $Q$. Indeed, there is an edge $i \to j$ with $j$ in $P$. If the vertex $j$ is in $R$, then $i$ itself is in $R$. This is absurd, hence $j$ is in $Q$. Moreover, by proposition 3.4, the shrub $Q$ is indecomposable.

Let us show that $R$ is also a shrub. The exclusion of the patterns is obvious. There remains to check that for each vertex $i$ of positive level in $R$, there is an edge $i \to j$ with $j$ in $R$. By Lemma 3.1, there exists a path $i \to j \to \dots \to k$, with $k$ of level 1 and covering all vertices of level 0. Therefore $k$ is in $R$, hence $j$ also and $R$ is a shrub.

Then it is clear that $P$ can be recovered from $Q$ and $R$ as $Q \triangleleft R$. This proves the existence of a decomposition as wanted.

Let us now show that such a decomposition is unique. Let us write $P = Q' \triangleleft R'$ with $Q'$ indecomposable. Let $j$ be a vertex of $P$ above all vertices of level 0. As $Q'$ is indecomposable (i.e. not connected or with just one vertex), $j$ cannot be in $Q'$, hence $j$ is in $R'$. On the other hand, by definition of the $\triangleleft$ product, all vertices of $R'$ are above all vertices of level 0 in $P$. Hence $R'$ is the induced subgraph on vertices covering all vertices of level 0. Then $Q'$ is the induced subgraph on the complement. This proves uniqueness. $\square$
# 5 Series-parallel posets

Let us recall the notion of series-parallel poset and related results. Let $I$ be a finite set. A series-parallel poset is a partial order on $I$ whose Hasse diagram avoids the pattern $\text{88}$.

One can take the disjoint union $P \sqcup Q$ of series-parallel posets $P$ and $Q$ (or rather of their Hasse diagrams).

**Proposition 5.1** Each series-parallel poset $P$ has a unique decomposition as the disjoint union of connected series-parallel posets.

One can also concatenate the Hasse diagrams of $P$ and $Q$ (one above the other) by adding a complete bipartite graph between maximal elements of $P$ and minimal elements of $Q$. The result is a series-parallel poset $P * Q$. This defines an associative product $*$ on series-parallel posets.

Each series-parallel poset $P$ has a unique maximal decomposition as a concatenation of series-parallel posets. A series-parallel poset $P$ cannot be written $P = Q * R$ if and only if it is not connected or has only one vertex. Let us call such a poset indecomposable. In particular,

**Proposition 5.2** Each connected series-parallel poset $P$ with at least two vertices has a unique decomposition $P = Q * R$ where $Q$ is indecomposable.

**Theorem 5.3** The species of shrubs is isomorphic to the species of series-parallel posets.

**Proof:** Let us build a (natural) bijection $\psi$ from shrubs to series-parallel posets by induction on the number of vertices. One one vertex, there is only one shrub and one series-parallel poset, hence no choice. Assume then that the bijection $\psi$ has been defined for smaller sizes. If a shrub is not connected, it is mapped to the disjoint union of the images of its connected components. It follows that $\psi$ maps indecomposable shrubs to indecomposable series-parallel posets.

If a shrub is connected, it can be uniquely written $P \triangleleft Q$ with $P$ indecomposable and is mapped to $\psi(P) * \psi(Q)$. The inverse bijection is similar. $\square$

Note that this bijection is the identity on forests of rooted trees, which are both shrubs and series-parallel posets. In the recursive description above, this corresponds to the case where the indecomposable left factor for the $*$ or $\triangleleft$ product is always just one point.

# 6 Some symmetric functions

Let $F$ be the symmetric function associated to the species of shrubs, $F_c$ for the connected shrubs and $F_i$ for indecomposable shrubs.

As a shrub is either connected or indecomposable, one has

$$p_1 + F = F_c + F_i, \qquad (9)$$

where $p_1$ is the first power sum symmetric function, accounting here for the fact that a shrub with one vertex is both connected and indecomposable.

As a shrub is a union of connected shrubs, one has

$$F = \mathrm{Comm} \circ F_c, \qquad (10)$$
where Comm is the symmetric function associated to the species of non-empty sets (and to the Commutative operad).

As a shrub can be decomposed as a sequence of indecomposable shrubs, one has

$$F = \mathrm{Ass} \circ F_i, \qquad (11)$$

where Ass is the symmetric function associated to the species of non-empty lists (and to the Associative operad).

Recall that the suspension $\Sigma F$ of a symmetric function $F$ is defined by

$$(\Sigma F)(p_1, p_2, \dots, p_i, \dots) = -F(-p_1, -p_2, \dots, -p_i, \dots). \qquad (12)$$

Then one can use inversion for the plethysm to deduce that

$$F_c = \Sigma \mathrm{Lie} \circ F \qquad (13)$$

and

$$F_i = \Sigma \mathrm{Ass} \circ F, \qquad (14)$$

where Lie is the symmetric function associated to the Lie operad.

Using then (9), one gets

$$p_1 = \Sigma (\mathrm{Ass} + \mathrm{Lie} - p_1) \circ F. \qquad (15)$$

Hence $F$ is the inverse for plethysm of the symmetric function $\Sigma(\mathrm{Lie} + \mathrm{Ass} - p_1)$.

# 7 Appendix

Let us gather here the first terms of sequences enumerating both shrubs and series-parallel posets.

* labelled: (A053554) 1, 3, 19, 195, 2791, 51303, ...,

* labelled connected: (A058349) 1, 2, 12, 122, 1740, 31922, ...,

* labelled indecomposable: (A058350) 1, 1, 7, 73, 1051, ...,

* unlabelled: (A003430) 1, 2, 5, 15, 48, 167, ...,

* unlabelled connected: (A007453) 1, 1, 3, 9, 30, 103, ...,

* unlabelled indecomposable: (A007454) 1, 1, 2, 6, 18, 64, ...,

# References

[BLL98] F. Bergeron, G. Labelle, and P. Leroux. *Combinatorial species and tree-like structures*, volume 67 of *Encyclopedia of Mathematics and its Applications*. Cambridge University Press, Cambridge, 1998. Translated from the 1994 French original by Margaret Readdy, With a foreword by Gian-Carlo Rota.

[Liv06] Muriel Livernet. A rigidity theorem for pre-Lie algebras. *J. Pure Appl. Algebra*, 207(1):1–18, 2006.
[Sta74] Richard P. Stanley. Enumeration of posets generated by disjoint unions and ordinal sums. *Proc. Amer. Math. Soc.*, 45:295-299, 1974.

[Sta99] Richard P. Stanley. *Enumerative combinatorics. Vol. 2*, volume 62 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.