# PreLie-decorated hypertrees

## Bérénice Oger

Institut Camille Jordan, Université Claude Bernard Lyon 1, Villeurbanne, France

**Abstract.** Weighted hypertrees have been used by C. Jensen, J. McCammond, and J. Meier to compute some Euler characteristics in group theory. We link them to decorated hypertrees and 2-coloured rooted trees. After the enumeration of pointed and non-pointed types of decorated hypertrees, we compute the character for the action of the symmetric group on these hypertrees.

**Résumé.** Des hyperarbres pondérés ont été utilisés en théorie des groupes, par C. Jensen, J. McCammond et J. Meier pour calculer des caractéristiques d'Euler. Nous relions ces hyperarbres pondérés à des hyperarbres décorés, puis à des arbres enracinés 2-colorés. Après énumération des hyperarbres décorés pointés et non pointés, nous déterminons le caractère de l'action du groupe symétrique sur les hyperarbres.

**Keywords:** Enumerative combinatorics, Species, Hypertrees, Symmetric group action

## 1 Introduction

Hypergraphs are generalizations of graphs introduced by C. Berge in his book [Ber89] during the 1980's. Like graphs, they are defined by their vertices and edges, but the edges can contain more than two vertices. Hypertrees are hypergraphs in which there is one and only one walk between every pair of vertices. Several studies on hypertrees have been led such as the computation of the number of hypertrees on *n* vertices by L. Kalikow in [Kal99] and by W. D. Smith and D. Warme in [War98]. In the article [JMM07], C. Jensen, J. McCammond and J. Meier have used weighted hypertrees to compute the Euler characteristic of a subgroup of the automorphism group of a free product. The weight used was $(e-1)^{e-2}$ for an edge of cardinality *e*.

Thanks to operad theory, we also know a vector space of dimension $(n-1)^{n-2}$. This vector space is the component of arity *n* − 1 of the PreLie operad introduced by F. Chapoton and M. Livernet in their paper [CL01]. A basis of this vector space is the set of rooted trees on *n* − 1 vertices. These results lead to the following question: is there a combinatorial interpretation in terms of rooted trees of the weighted hypertrees used by C. Jensen, J. McCammond and J. Meier ?

In this paper, we present a combinatorial interpretation of weighted hypertrees used in [JMM07] in terms of hypertrees decorated by PreLie, which are hypertrees in which vertices in every edges form a rooted tree. To enumerate them, we establish a bijection of species between the species of decorated hollow hypertrees and the species of 2-coloured rooted trees. In Section 2, we enumerate pointed and non-pointed versions of decorated hypertrees, which give back the result of C. Jensen, J. McCammond and J. Meier in [JMM07]. We then compute the action of the symmetric group on decorated hypertrees in Section 3, which is remarkable because the associated cycle index series is quite simple.
<figure><img src="image_1.png" /><figcaption>**Figure 1:** An example of hypergraph on {1, 2, 3, 4, 5, 6, 7}.</figcaption></figure>

We use the language of species for which the book of F. Bergeron, G. Labelle and P. Leroux [BLL98] is a good reference. Note that we write *species* for *linear species*. This paper is an extended abstract of [Oge12]: we refer to the long version for a generalization of this construction and enumeration of decorated hypertrees to any species or linear species.

## 2 Description and relations of the decorated hypertrees

In this section, we introduce a type of *decorated hypertrees*, decorated by $\tilde{PreLie}$ and give functional equations satisfied by these.

### 2.1 From hypergraphs to rooted and pointed hypertrees

We first recall the definition of hypergraphs and hypertrees.

**Definition 2.1** A hypergraph (on a set $V$) is an *ordered pair* $(V, E)$ where $V$ is a *finite set* and $E$ is a collection of parts of $V$ of cardinality at least two. The elements of $V$ are called *vertices* and those of $E$ are called *edges*.

**Definition 2.2** Let $H = (V, E)$ be a hypergraph, $v$ and $w$ two vertices of $H$. A walk from $v$ to $w$ in $H$ is an alternating sequence of vertices and edges ($v = v_1, e_1, v_2, \dots, e_n, v_{n+1} = w$) where for all $i$ in $\{1, \dots, n+1\}$, $v_i \in V$, $e_i \in E$ and for all $i$ in $\{1, \dots, n\}$, $\{v_i, v_{i+1}\} \subseteq e_i$.

**Example 2.3** On the hypergraph of the example of Figure 1, there are several walks from 4 to 2: (4, A, 7, B, 6, C, 2) and (4, A, 7, B, 6, C, 1, D, 2).

In this article, we are interested in a special type of hypergraphs: hypertrees.

**Definition 2.4** A hypertree is a non empty hypergraph $H$ such that, given any vertices $v$ and $w$ in $H$,

* there exists a walk from $v$ to $w$ in $H$ with distinct edges $e_i$, i.e. $H$ is connected,

* and this walk is unique, i.e. $H$ has no cycles.

The pair $H = (V, E)$ is called hypertree on $V$. If $V$ is the set $\{1, \dots, n\}$, then $H$ is called a hypertree on $n$ vertices.

We now recall rooted and pointed variations of hypertrees.

**Definition 2.5** • A rooted hypertree is a hypertree $H$ together with a vertex $s$ of $H$. The hypertree $H$ is said to be rooted at $s$ and $s$ is called the root of $H$.
<figure><img src="image_2.png" /><figcaption>**Figure 2:** (Left) A hypertree on nine vertices, rooted at 1. (Middle) A hypertree on seven vertices, pointed at edge {1, 2, 3, 4} and rooted at 3. (Right) A hollow hypertree on eight vertices. The hollow edge is the edge {1, 2, 3, 4}.</figcaption></figure>

* An edge-pointed hypertree is a hypertree $H$ together with an edge $e$ of $H$. The hypertree $H$ is said to be pointed at $e$.

* An edge-pointed rooted hypertree is a hypertree $H$ on at least two vertices, together with an edge $a$ of $H$ and a vertex $v$ of $a$. The hypertree $H$ is said to be pointed at $a$ and rooted at $s$.

* A hollow hypertree on $n$ vertices is a hypertree on $n+1$ vertices on the set $\{\# , 1, \dots, n\}$, such that the vertex labelled by $\#$, called the gap, belongs to one and only one edge.

## 2.2 On the linear species $\widehat{\text{PreLie}}$ and the operad $\text{PreLie}$

An operad is a species with an operadic composition. It means that it is a functor $F$ from the category of finite sets and bijections to the category of vector spaces, with a family of composition $\circ_i : F([n]) \times F([m]) \to F([n+m-1])$, for all integers $n$ and $m$, satisfying some axioms that we will not describe here, as they will not be needed in this paper.

The basic definitions on species can be found in the book [BLL98]. We can define the following operations on species:

**Definition 2.6** Let $F$ and $G$ be two species. We define the following operations on species:

* $F'(I) = F(I \sqcup \{\bullet\})$, (differentiation)

* $(F + G)(I) = F(I) + G(I)$, (addition)

* $(F \times G)(I) = \sum_{I_1 \sqcup I_2 = I} F(I_1) \times G(I_2)$, (product)

* $(F \circ G)(I) = \bigoplus_{\pi \in \mathcal{P}(I)} F(\pi) \times \prod_{J \in \pi} G(J)$, (substitution) where $\mathcal{P}(I)$ runs on the set of partitions of $I$.

With each species $F$, we can associate a generating series of the dimension of $F([n])$ and a cycle index series, which gives the character for the action of the symmetric group $S_n$ on the set of vertices $[n]$ of the hypertree, such that operations on species can be translated in terms of operations on generating series and cycle index series.

The operad $\text{PreLie}$ associates to any finite sets $I$ the vector space whose basis is the set of rooted trees with vertex set $I$. This operad is described in the paper by F. Chapoton and M. Livernet [CL01]. In the article [Cha05], F. Chapoton proves that $\text{PreLie}$ is anticyclic. It means that the action of the symmetric group $S_n$ on the vector space $\text{PreLie}([n])$ obtained by permutations of vertices can be extended into an
action of $\mathfrak{S}_{n+1}$ on $\text{PreLie}([n])$. This implies the existence of a species $\widehat{\text{PreLie}}$ whose differential is the species $\text{PreLie}$.

## 2.3 Definitions of decorated hypertrees

From a hypertree, we can define what we call a *decorated hypertree*. It consists in decorating the edges of the hypertree by the linear species $\widehat{\text{PreLie}}$.

**Definition 2.7** *Given a species $S$, a decorated (edge-pointed) hypertree is obtained from a (edge-pointed) hypertree $H$ by choosing for every edge $e$ of $H$ an element of $\widehat{\text{PreLie}}(V_e)$, where $V_e$ is the set of vertices in the edge $e$.*

The map which associates to a finite set $I$ the set of decorated (resp. edge-pointed) hypertrees on $I$ is a species, denoted by $\mathcal{H}_{\widehat{\text{PreLie}}}$ (resp. $\mathcal{H}_{\widehat{\text{PreLie}}}^a$).

We now give definitions for rooted or hollow versions of decorated hypertrees.

**Definition 2.8** *A decorated rooted (resp. edge-pointed rooted, resp. hollow) hypertree is obtained from a rooted (resp. edge-pointed rooted, resp. hollow) hypertree $H$ by choosing for every edge $e$ of $H$ an element of $\widehat{\text{PreLie}}(V_e)$, where $V_e$ is the set of vertices in the edge $e$.*

In rooted or hollow hypertrees, there is one distinguished vertex in every edge. Therefore, using the definition of the differential of a species, we obtain the following equivalent definition:

**Definition 2.9** *Let us consider a rooted (resp. edge-pointed rooted, resp. hollow) hypertree $H$. Given an edge $e$ of $H$, there is one vertex of $e$ which is the nearest from the root (resp. the gap) of $H$ in $e$: let us call it the petiole $p_e$ of $e$. Then, a decorated rooted (resp. rooted edge-pointed, resp. hollow) hypertree is obtained from the hypertree $H$ by choosing for every edge $e$ of $H$ an element in the vector space $\text{PreLie}(V_e - \{p_e\})$, where the set $V_e$ is the set of vertices of $e$. It means that edges of decorated hypertrees contain a vertex (or a gap) and a rooted tree.*

The map which associates to a finite set $I$ the set of decorated rooted (resp. edge-pointed rooted, resp. hollow) hypertrees on $I$ is a species, called the decorated rooted (resp. edge-pointed rooted, resp. hollow) hypertree species and denoted by $\mathcal{H}_{\widehat{\text{PreLie}}}^p$ (resp. $\mathcal{H}_{\widehat{\text{PreLie}}}^{pa}$, resp. $\mathcal{H}_{\widehat{\text{PreLie}}}^c$).

## 2.4 Relations

### 2.4.1 Dissymmetry principle

The reader may consult the book [BLL98, Chapter 2.3] for a deeper explanation on the dissymmetry principle. In a general way, a *dissymmetry principle* is the use of a natural center to obtain the expression of a non pointed species in terms of pointed species. An example of this principle is the use of the center of a tree to express unrooted trees in terms of rooted trees.

We will consider the following weight on any hypertree (pointed or not, rooted or not, hollow or not):

**Definition 2.10** *The weight of a hypertree $H$ with edge set $E$ is given by:*

$$W_t(H) = t^{\#E-1}.$$

The expression of the hypertree species in terms of pointed and rooted hypertrees species is the following:
<figure><img src="image_3.png" /><figcaption>**Figure 3:** An example of an edge-pointed rooted hypertree with edges decorated by $\widehat{\text{PreLie}}$. The root of the hypertree is in a white square, the roots of trees from the decoration are in two circles whereas the other vertices are in one circle. The grey rectangles are the non-pointed edges of the hypertrees and the blue dotted rectangle is the pointed one.</figcaption></figure>

**Proposition 2.11 ([Oge13])** The species of hypertrees and the one of rooted hypertrees are related by:

$$ \mathcal{H} + \mathcal{H}^{pa} = \mathcal{H}^{p} + \mathcal{H}^{a}. \qquad (1) $$

This bijection links hypertrees with $k$ edges with hypertrees with $k$ edges, and therefore it preserves the weight on hypertrees. Pointing a vertex or an edge of a hypertree and then decorating its edges is just the same as decorating its edges and then pointing a vertex or an edge. Therefore, the decoration of edges is compatible with the previous Proposition 2.11 and we obtain:

**Proposition 2.12 (Dissymmetry principle for decorated hypertrees)** Given a species $S$, the following relation holds:

$$ \mathcal{H}_{\widehat{\text{PreLie}}} + \mathcal{H}^{pa}_{\widehat{\text{PreLie}}} = \mathcal{H}^{p}_{\widehat{\text{PreLie}}} + \mathcal{H}^{a}_{\widehat{\text{PreLie}}}. \qquad (2) $$

Thanks to this proposition, the study of decorated hypertrees is obtained with the study of pointed and rooted decorated hypertrees.

## 2.4.2 Functional equations

To study pointed and rooted decorated hypertrees, we decompose them into smaller pointed and rooted hypertrees to obtain relations between the different species. The previous species are related by the following proposition, where $X$ is the species of singleton, which associates to every singleton $s$ itself and the empty set otherwise, and $\text{Comm}$ is the species of non-empty sets, which associates to every non-empty set $S$ the set $\{S\}$ and the empty set otherwise:

**Theorem 2.13** The species $\mathcal{H}_{\widehat{\text{PreLie}}}$, $\mathcal{H}^{p}_{\widehat{\text{PreLie}}}$, $\mathcal{H}^{a}_{\widehat{\text{PreLie}}}$, $\mathcal{H}^{pa}_{\widehat{\text{PreLie}}}$ and $\mathcal{H}^{c}_{\widehat{\text{PreLie}}}$ satisfy:

$$ \mathcal{H}^{p}_{\widehat{\text{PreLie}}} = X \times \mathcal{H}'_{\widehat{\text{PreLie}}}, \qquad (3) $$

$$ t\mathcal{H}^{p}_{\widehat{\text{PreLie}}} = X + X \times \text{Comm} \circ (t \times \mathcal{H}^{c}_{\widehat{\text{PreLie}}}), \qquad (4) $$

$$ \mathcal{H}^{c}_{\widehat{\text{PreLie}}} = \text{PreLie} \circ t\mathcal{H}^{p}_{\widehat{\text{PreLie}}}, \qquad (5) $$
$$ \mathcal{H}_{\widehat{\text{PreLie}}}^{a} = \widehat{\text{PreLie}} \circ t \mathcal{H}_{\widehat{\text{PreLie}}}^{p}, \qquad (6) $$

$$ \mathcal{H}_{\widehat{\text{PreLie}}}^{pa} = \mathcal{H}_{\widehat{\text{PreLie}}}^{c} \times t \mathcal{H}_{\widehat{\text{PreLie}}}^{p} = \frac{X}{t} \times (X(1 + \text{Comm}) \circ t \mathcal{H}_{\widehat{\text{PreLie}}}^{c}). \qquad (7) $$

**Proof:** If we multiply the series by $t$, the power of $t$ corresponds to the number of edges in the associated hypertrees.

* The first relation is due to the general relation between a species and a pointed species.

* The second one is obtained from a decomposition of a rooted hypertree. If there is only one vertex, we keep the label of it and it gives $X$, the number of edges is 0. Otherwise, we separate the label of the root: it gives $X$. A hypertree with a gap contained in different edges remains. Separating these edges, we obtain a non-empty set of hollow hypertrees with edges decorated by $\widehat{\text{PreLie}}$. There is the same number of edges in the set of hollow hypertrees as in the rooted hypertree. This operation is a bijection of species because a vertex alone is a rooted decorated hypertree and taking a non-empty forest of hollow decorated hypertrees and linking them by their gap on which we put a label gives a rooted decorated hypertree.

* The third relation is obtained by pointing the vertices in the hollow edge and breaking the edge: we obtain a non-empty forest of rooted decorated hypertrees. As we break an edge, there is one edge less in the forest of rooted hypertrees than in the hollow hypertree: it corresponds to a division by $t$. The set of roots is a rooted tree and induces this structure on the set of hypertrees: we obtain a rooted tree whose vertices are rooted decorated hypertrees. As this operation is reversible and does not depend on the labels of the hollow hypertree, this is a bijection of species.

* The fourth relation is obtained by pointing the vertices in the pointed edge and breaking it: we obtain a non-empty forest of at least two rooted decorated hypertrees. As we break an edge, there is one edge less in the forest of rooted hypertrees than in the edge-pointed hypertree: it corresponds to a division by $t$. The set of roots is a $\widehat{\text{PreLie}}$-structure and induces this structure on the set of tree: we obtain a $\widehat{\text{PreLie}}$-structure in which all elements are rooted decorated hypertrees. As this operation is reversible and does not depend on the labels of the hollow hypertree, this is a bijection of species.

* The last relation is obtained by separating the pointed edge from the other edges containing the root and putting a gap in the pointed edge instead of the root: the connected component of the pointed edge gives a decorated hollow hypertree and the connected component containing the root gives a rooted decorated hypertree. There is the same number of edges in the edge-pointed rooted hypertree as in the union of the hollow and the rooted hypertree.

□

**Corollary 2.14** *Using the equations (4) and (5) of the previous proposition, we obtain:*

$$ t \mathcal{H}_{\widehat{\text{PreLie}}}^{p} = X + X \times \text{Comm} \circ (t \times \text{PreLie} \circ t \mathcal{H}_{\widehat{\text{PreLie}}}^{p}) \qquad (8) $$
<figure><img src="image_4.png" /><figcaption>**Figure 4:** (Left) An example of 2-coloured rooted tree. The edges of $E_1$ are dashed whereas the edges of $E_0$ are plain. (Right) The hollow hypertree with edges decorated by $\widehat{\text{PreLie}}$ associated to this 2-coloured rooted tree.</figcaption></figure>

and

$$ \mathcal{H}_{\widehat{\text{PreLie}}}^{c} = \text{PreLie} \circ (X + X \times \text{Comm} \circ (t \times \mathcal{H}_{\widehat{\text{PreLie}}}^{c})). \qquad (9) $$

These equations enables us to compute recursively the generating series and the cycle index series of all decorated hypertrees and rooted and pointed decorated hypertrees. Nevertheless, we can obtain closed formulas thanks to a bijection with 2-coloured rooted trees.

# 3 Computation of generating series and cycle index series of decorated hypertrees

## 3.1 Link with 2-coloured rooted trees and computation of generating series

We now draw the link between trees whose edges can be either plain (0) or dashed (1) and decorated hollow hypertrees.

**Definition 3.1** A 2-coloured rooted tree is a rooted tree $(V, E)$, where $V$ is the set of vertices and $E \subseteq V \times V$ is the set of edges, together with a map $\varphi$ from $E$ to $\{0, 1\}$. It is equivalent to the data of a tree $(V, E)$ and a decomposition $E_0 \cup E_1$ of $E$, with $E_0 \cap E_1 = \emptyset$. We consider the weight $t^{\#E_1}$ on this set.

**Theorem 3.2** 1. The species of hollow hypertrees decorated by $\widehat{\text{PreLie}}$ is isomorphic to the species of 2-coloured rooted trees.

2. The species of rooted hypertrees decorated by $\widehat{\text{PreLie}}$ is isomorphic to the species of 2-coloured rooted trees such that the edges adjacent to the root are all dashed, up to a coefficient $\frac{1}{t}$ to respect the weight.

3. The species of rooted edge-pointed hypertrees decorated by $\widehat{\text{PreLie}}$ is isomorphic to the species of 2-coloured rooted trees such that all the edges adjacent to the root but one are dashed.
This theorem enables us to compute explicitly the generating series and cycle index series for decorated
hypertrees. Hence this is the key point to establish the link between $\widehat{\text{PreLie}}$-decorated hypertrees and C.
Jensen, J. McCammond and J. Meier's weighted hypertrees.

**Proof:**

1. A hollow hypertree with edges decorated by $\widehat{\text{PreLie}}$ is a hollow hypertree in which, for all edges $e$, the vertices of $e$ different from the gap or the petiole form a rooted tree.

Let us consider a hollow hypertree $H$ decorated by $\widehat{\text{PreLie}}$ on vertex set $V$. We call $E_0$, the set of edges between elements of $V$ in the rooted trees obtained from the decoration by $\widehat{\text{PreLie}}$. The graph $(V, E_0)$ is then a forest of trees obtained by deleting the edges of the hypertree $H$ and forgetting the roots. For any edge $e$ of $H$, we write $r_e$ for the root of the rooted tree in $e$ and $p_e$ for the petiole of $e$. Let $E_1$ be the set of edges between $r_e$ and $p_e$ for all edges $e$ of $H$. By definition of the sets, the intersection of $E_0$ with $E_1$ is empty. Moreover, to every path in $H$ corresponds a path in $(V, E_0 \cup E_1)$. As $H$ is a hypertree, the graph $(V, E_0 \cup E_1)$ is a tree $T$. We root that tree in the root $r$ of the tree in the hollow edge of $H$: $T$ is then a 2-coloured tree rooted in $r$.

Conversely, let $T = (V, E_0 \cup E_1)$ be a 2-coloured rooted tree. The graph $(V, E_0)$ is a forest of trees: we can root these trees in their closest vertex from the root. Let us call $T_1, \dots, T_n$ this forest, where $T_1$ is the tree rooted in the root of $T$. For all $i$ between 2 and $n$, there is one vertex of $V$ linked with a vertex of $T_i$ in $T$ and closer than the root of $T_i$ from the root of $T$: we call this vertex $p_i$. Then, we consider the hypergraph whose set of vertices is $V$, with edges containing the vertices of $T_1$ or the vertices of a $T_i$ and $p_i$ for all $i$ between 2 and $n$. Adding the edges of every $T_i$, we obtain a hypergraph decorated by $\widehat{\text{PreLie}}$. Moreover, paths in $T$ and in the hypergraph are the same: the hypergraph is then a hypertree.

As there is a bijection between the elements of $E_1$ and the edges of the hypertree different from the
hollow one, the weight is preserved.

2. Let us consider a rooted hypertree $H$ decorated by $\widehat{\text{PreLie}}$ on vertex set $V$.

If the cardinality of $V$ is 1, then $H$ is a 2-coloured rooted tree on one vertex. Otherwise, putting a gap in the edges containing the root $r$, deleting the root and separating the edges linked by the root, we obtain a forest of hollow hypertrees decorated by $\widehat{\text{PreLie}}$. According to the first point, the species of hollow decorated hypertrees is in bijection with the species of 2-coloured rooted trees: the species of decorated rooted hypertrees is then in bijection with the species of a vertex $r$ and a forest of 2-coloured trees. Linking the vertex $r$ to the roots of the 2-coloured trees by dashed edges give the result. To preserve the weight, we must insert the factor $\frac{1}{t}$ in front of the species of 2-coloured trees.

3. A rooted edge-pointed hypertree is a rooted hypertree on at least two vertices with one edge adjacent to the root distinguished. We then distinguished one edge in the corresponding 2-coloured trees by changing it from dashed to plain. The weight is then preserved.

☐

Applying the results of Theorem 3.2, we obtain the following proposition, which establish the link between $\widehat{\text{PreLie}}$-decorated hypertrees and J. McCammond and J. Meier's weighted hypertrees:
**Corollary 3.3** The generating series of the species of hollow hypertrees decorated by $\widehat{\text{PreLie}}$ is given by:

$$S_{\widehat{\text{PreLie}}}^{c} = x + \sum_{n \ge 2} (tn + n)^{n-1} \frac{x^n}{n!}.$$

The generating series of the species of rooted hypertrees decorated by the linear species $\widehat{\text{PreLie}}$ is given by:

$$S_{\widehat{\text{PreLie}}}^{p} = \frac{x}{t} + \sum_{n \ge 2} n(tn + n - 1)^{n-2} \frac{x^n}{n!}.$$

The generating series of the species of hypertrees decorated by $\widehat{\text{PreLie}}$ is given by:

$$S_{\widehat{\text{PreLie}}} = x + \sum_{n \ge 2} (tn + n - 1)^{n-2} \frac{x^n}{n!}.$$

The generating series of the species of edge-pointed hypertrees decorated by $\widehat{\text{PreLie}}$ is given by:

$$S_{\widehat{\text{PreLie}}}^{pa} = x + \sum_{n \ge 2} n(n + tn - 1)^{n-3}(n-1)(1 + 2t) \frac{x^n}{n!}.$$

The generating series of the species of edge-pointed hypertrees decorated by $\widehat{\text{PreLie}}$ is given by:

$$S_{\widehat{\text{PreLie}}}^{a} = x + \sum_{n \ge 2} (n + tn - 1)^{n-3}(n-1)(1 + tn) \frac{x^n}{n!}.$$

We recover the result of C. Jensen, J. McCammond and J. Meier for weighted hypertrees and rooted weighted hypertrees in [JMM07, Theorem 3.9] and in [JMM07, Theorem 3.11]

**Proof:**

* According to Theorem 3.2, we have to count 2-coloured rooted trees on $n$ vertices. There are $n^{n-1}$ rooted trees on $n$ vertices. To obtain 2-coloured rooted trees from rooted trees, we establish a bijection between the set of edge, of cardinality $n-1$, and the set $\{0, 1\}$, according to the set $E_i$ to which the edge belongs.

* Let us count the number $N_n^p$ of 2-coloured rooted trees such that the edges adjacent to the root are all dashed. There are $n$ ways to choose the root. Cutting the root, we obtain a forest of $j$ trees on $n-1$ vertices. We use the classical formula for the number of forests of $j$ trees on $n-1$ vertices, which can be found in the book of M. Aigner and G. Ziegler [AZ04]. We obtain:

$$N_n^p = n \times \sum_{j=1}^{n-1} \binom{n-2}{j-1} \times ((n-1)(1+t))^{n-1-j} \times t^j.$$

Re-indexing, we obtain the result.

* We apply the first equation of Proposition 2.13.
* We count in the same way as for the second point 2-coloured rooted trees such that all the edges adjacent to the root but one are dashed:

$$N_n^{pa} = n \times \sum_{j=1}^{n-1} \binom{n-2}{j-1} \times ((n-1)(1+t))^{n-1-j} \times j \times t^{j-1}.$$

* We apply the dissymetry principle of Proposition 2.12.

□

## 3.2 Computation of cycle index series of hypertrees decorated by $\widehat{\text{PreLie}}$

We denote the cycle index series of usual species in the same way as the species itself. We compute the cycle index series of hypertrees decorated by $\widehat{\text{PreLie}}$. We do not write the argument of the cycle index series $(t, p_1, p_2, \dots)$ in this subsection.

We are now interested in the action of the symmetric group on the set of decorated hypertrees, which is given by cycle index series:

**Proposition 3.4** *The cycle index series of hollow hypertrees decorated by $\widehat{\text{PreLie}}$ is given by:*

$$Z_{\widehat{\text{PreLie}}}^{c} = \frac{1}{1+t} \widehat{\text{PreLie}} \circ (1+t)p_1. \qquad (10)$$

**Proof:** By Theorem 3.2, the cycle index series of hollow hypertrees decorated by $\widehat{\text{PreLie}}$ is given by the cycle index series of 2-coloured rooted trees. □

Let us define the following expressions, for $\lambda$ a partition of an integer $n$, written $\lambda \vdash n$:

$$f_k(\lambda) = \sum_{l|k} l\lambda_l$$

and

$$P_k(\lambda) = ((1+t^k)f_k(\lambda) - 1)^{\lambda_k} - k\lambda_k(t^k+1) \times ((1+t^k)f_k(\lambda) - 1)^{\lambda_k-1}.$$

We obtain the following expression for the cycle index series of hypertrees decorated by $\widehat{\text{PreLie}}$:

**Proposition 3.5** *The cycle index series of rooted hypertrees decorated by $\widehat{\text{PreLie}}$ is given by:*

$$Z_{\widehat{\text{PreLie}}}^{p} = \sum_{n \ge 1} \sum_{\lambda \vdash n, \lambda_1 \ne 0} \lambda_1 (\lambda_1 t + \lambda_1 - 1)^{\lambda_1 - 2} \prod_{k \ge 2} P_k(\lambda) \times \frac{p_\lambda}{z_\lambda}. \qquad (11)$$

The cycle index series of edge-pointed rooted hypertrees decorated by $\widehat{\text{PreLie}}$ is given by:

$$Z_{\widehat{\text{PreLie}}}^{pa} = \sum_{n \ge 1} \sum_{\lambda \vdash n, \lambda_1 \ne 0} \lambda_1 (\lambda_1 - 1)(2t + 1)(\lambda_1 + \lambda_1 t - 1)^{\lambda_1 - 3} \prod_{k \ge 2} P_k(\lambda) \times \frac{p_\lambda}{z_\lambda}. \qquad (12)$$
The cycle index series of edge-pointed hypertrees decorated by $\widehat{\text{PreLie}}$ is given by:

$$Z_{\widehat{\text{PreLie}}}^{a} = \sum_{n \ge 1} \sum_{\lambda \vdash n, \lambda_1 \neq 0} (\lambda_1 - 1)(1 + \lambda_1 t)(\lambda_1 + \lambda_1 t - 1)^{\lambda_1 - 3} \prod_{k \ge 2} P_k(\lambda) \times \frac{p_{\lambda}}{z_{\lambda}}. \quad (13)$$

The cycle index series of hypertrees decorated by $\widehat{\text{PreLie}}$ is given by:

$$Z_{\widehat{\text{PreLie}}} = \sum_{n \ge 1} \sum_{\lambda \vdash n, \lambda_1 \ne 0} (\lambda_1 t + \lambda_1 - 1)^{\lambda_1 - 2} \prod_{k \ge 2} P_k(\lambda) \times \frac{p_{\lambda}}{z_{\lambda}}. \quad (14)$$

This proposition is proven in the paper [Oge12].

## References

[AZ04] Martin Aigner and Günter M. Ziegler. *Proofs from The Book*. Springer-Verlag, Berlin, third edition, 2004. Including illustrations by Karl H. Hofmann.

[Ber89] Claude Berge. *Hypergraphs*, volume 45 of North-Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, 1989.

[BLL98] François Bergeron, Gilbert Labelle, and Pierre Leroux. *Combinatorial species and tree-like structures*, volume 67 of *Encyclopedia of Mathematics and its Applications*. Cambridge University Press, Cambridge, 1998.

[Cha05] Frédéric Chapoton. On some anticyclic operads. *Algebr. Geom. Topol.*, 5:53–69 (electronic), 2005.

[CL01] Frédéric Chapoton and Muriel Livernet. Pre-Lie algebras and the rooted trees operad. *Internat. Math. Res. Notices*, (8):395–408, 2001.

[JMM07] Craig Jensen, Jon McCammond, and John Meier. The Euler characteristic of the Whitehead automorphism group of a free product. *Trans. Amer. Math. Soc.*, 359(6):2577–2595 (electronic), 2007.

[Kal99] Louis H. Kalikow. *Enumeration of parking functions, allowable permutation pairs, and labeled trees*. ProQuest LLC, Ann Arbor, MI, 1999. Thesis (Ph.D.)–Brandeis University.

[Oge12] B. Oger. Decorated hypertrees. *Submitted*, 2012. http://arxiv.org/abs/1209.0941.

[Oge13] B. Oger. Action of the symmetric groups on the homology of the hypertree posets. *Journal of Algebraic Combinatorics*, 2013. DOI:10.1007/s10801-013-0432-2.

[War98] David Michael Warme. *Spanning trees in hypergraphs with applications to Steiner trees*. ProQuest LLC, Ann Arbor, MI, 1998. Thesis (Ph.D.)–University of Virginia.