{'fraction_non_alphanumeric': 0.04774730656219393, 'fraction_numerical': 0.014131803553938716, 'mean_word_length': 3.737199668599834, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Pebble trees

A pebble tree is an ordered tree where each node receives some colored pebbles, in such a way that each unary node receives at least one pebble, and each subtree has either one more or as many leaves as pebbles of each color. We show that the contraction poset on pebble trees is isomorphic to the face poset of a convex polytope called pebble tree polytope. Beside providing intriguing generalizations of the classical permutahedra and associahedra, our motivation is that the faces of the pebble tree polytopes provide realizations as convex polytopes of all assocoipahedra constructed by K. Poirier and T. Tradler only as polytopal complexes.


Introduction
Permutahedra and associahedra are among the most classical polytopes in algebraic combinatorics. The (n−1)-dimensional permutahedron has a vertex for each permutation of [n] := {1, . . . , n} and an edge for each pair of permutations related by the transposition of two adjacent entries. The (n − 1)-dimensional associahedron has a vertex for each binary tree on n nodes and an edge for each pair of binary trees related by a rotation. These two families of polytopes admit common generalizations explaining their similar behavior, including the permutreehedra of [PP18], the quotientopes of [PS19], and the (m, n)-multiplihedra of [CP22]. All these polytopes are actually deformed permutahedra (defined as generalized permutahedra in [Pos09,PRW08]), meaning that their normal fans all coarsen the braid fan. This paper is devoted to another common generalization to the permutahedra and associahedra, which are not deformed permutahedra in general.
The combinatorics of this generalization is based on pebble trees. A pebble tree is an ordered tree where each node receives some colored pebbles in such a way that each unary node receives at least one pebble, and each subtree has either one more or as many leaves as pebbles of each color (see Figure 1). We consider the set of pebble trees with a fixed number of leaves and fixed sets of unbalanced and balanced colors (i.e. for which colors the whole pebble tree as one more or as many leaves as pebbles). It is immediate from the definition that these pebble trees are closed by arc contractions, and our main result is that the contraction poset is the face poset of a simple convex polytope, that we call the pebble tree polytope (see Figure 13). For this, we first construct the pebble tree fan, associating to each pebble tree a polyhedral cone in a very natural way, and then prove that this fan is the normal fan of a polytope by checking that its wall-crossing inequalities are satisfiable. Our construction recovers the combinatorics and geometry of the permutahedra and associahedra in two degenerate situations. On the one hand, pebble trees with a single leaf can be seen as ordered partitions of their balanced colors, and the pebble tree polytope is the permutahedron. On the other hand, pebble trees with no pebbles are Schröder trees, and the pebble tree polytope is the associahedron. But the special situation which motivated this paper is when there is exactly one color of pebbles. The pebble trees are then in bijection with some specific oriented planar trees considered by K. Poirier and T. Tradler in [PT18] for the combinatorics of algebraic structures endowed with a binary product and a co-inner product. These structures are closely connected to the V ∞ -algebras of T. Tradler and M. Zeinalian [TZ07] that arose in a temptative algebraic model for string topology operations defined by M. Chas and D. Sullivan [CS99]. It is proved in [PT18] that the contraction posets on these oriented planar trees are face lattices of the assocoipahedra, which are polytopal complexes refining the boundary complex of the Cartesian product of an associahedron with a simplex. We prove here that all assocoipahedra can actually be realized as convex polytopes using faces of pebble tree polytopes (see Figure 14).
The paper is organized as follows. Section 2 is devoted to the combinatorics of pebble trees. In Section 2.1, we provide more precise definitions and notations for pebble trees, we introduce some natural maps between families of pebble trees, and we give the precise bijection with the oriented planar trees of [PT18]. We introduce in Section 2.2 the pebble tree contraction poset, prove in Section 2.3 that it is the face poset of a pseudomanifold called the pebble tree complex, and discuss in Section 2.4 the adjacency graph of this complex called the pebble tree flip graph. Section 3 is devoted to the geometry of pebble trees. After quickly reminding some geometric preliminaries in Section 3.1, we construct the pebble tree fan in Section 3.2 and the pebble tree polytope in Section 3.3. Finally, Section 4 is devoted to the numerology of pebble trees. We compute the generating functions of the maximal pebble trees in Section 4.1 and of all the pebble trees in Section 4.2, and gather explicit expansions of these generating functions in Section 4.3. While the methods are standard computations based on generatingfunctionology [FS09], the results reveal a few surprises.

Pebble tree combinatorics
In this section, we define pebble trees (Section 2.1) and study the pebble tree contraction poset (Section 2.2), the pebble tree complex (Section 2.3), and the pebble tree flip graph (Section 2.4).
2.1. Pebble trees. Recall that an ordered tree is either a leaf or a node with an ordered list of subtrees. These subtrees are the children of the node, and this node is the parent of these subtrees. As we only consider ordered trees, we omit the adjective ordered and only say tree. For a node n in a tree T , we denote by T n the subtree of T rooted at n. For a subtree S, we denote by L(S) the set of leaves of S. Definition 1. For a finite set of colors Γ, a Γ-pebble tree is a tree with pebbles colored by Γ placed on its nodes such that (i) each leaf receives no pebble, each node with a single child receives at least one pebble, and each node with at least two children receives arbitrary many pebbles (possibly none), (ii) for each subtree S and each color γ ∈ Γ, the number of leaves minus the number of pebbles of color γ in S is either 0 or 1.
Example 2. Two classical combinatorial objects are extreme examples of pebble trees: • pebble trees with a single leaf can be seen as ordered partitions of their pebble colors, • pebble trees with no pebbles are Schröder trees (where each node has either none or at least two children). Some more generic examples of pebble trees are illustrated in Figure 1.
Notation 4. We denote by P Γ L the set of all pebble trees with leaves L and pebble colors Γ, and by P B,U L the subset of B-balanced and U -unbalanced pebble trees of P Γ L for any B ⊔ U = Γ. For ℓ, b, u ∈ N, we define P b,u ℓ as P . Note that P B,U L is isomorphic to P b,u ℓ for arbitrary L, B, U with |L| = ℓ, |B| = b and |U | = u. It is however convenient to keep the notation P B,U L to define certain operations on pebble trees (see Definitions 6 to 9) and for recursive decompositions of the pebble trees (see Section 4).
Remark 5. Some immediate consequences of Definition 1: • P Γ L is finite for any L and Γ, thus P b,u ℓ is finite for any ℓ, b, u ∈ N. • The number of γ-pebbles at a node p with children c 1 , . . . , c k is Hence, the number of γ-unbalanced children of p is the number of γ-pebbles at p, plus 1 if p is γ-unbalanced.
• Each unary node has at least one pebble, and at most one of each color. • There is no consecutive chain formed by |Γ| + 1 unary nodes We now define five natural maps between pebble trees (see Figures 2 and 3), that will induce isomorphisms in Propositions 17, 25 and 42. In Definitions 8 and 10, we call γ-leaf the only pebble tree of P {γ},∅ 1 , i.e. whose root has a single pebble of color γ and a single child which is a leaf. • if T is a node with pebbles P and children C 1 , . . . , C j , then µ(T ) is a node with pebbles P and children µ(C j ), . . . , µ(C 1 ). Definition 9. If x ∈ L and U = ∅, the x-rerooting map sends a pebble tree T of P B,∅ L to the pebble tree ρ x (T ) ∈ P B,∅ L obtained by hanging T from its leaf x, i.e. defined inductively by • if T is just the leaf x, then ρ x (T ) is just a leaf denoted r, • if T is a node with pebbles P and children C 1 , . . . , C j and i ∈ [j] is such that x ∈ L(C i ), then ρ x (T ) is obtained by replacing the leaf r of ρ x (C i ) by a node with pebbles P and children C i+1 , . . . , C j , r, C 1 , . . . , C i−1 .
Definition 10. If ℓ > 1, B = ∅ and γ / ∈ U , the γ-uprooting map sends a pebble tree T of P ∅,U [ℓ] to the pebble tree θ γ (T ) of P U∪{γ},∅ [ℓ−1] obtained from T by first hanging T from its rightmost leaf, then deleting the leftmost leaf and placing a γ-pebble at its parent, and finally replacing all remaining leaves except the first by a γ-leaf.
Finally, our next three remarks connect pebble trees with other relevant families of trees.
Remark 11. Consider a word α ∈ {i, o} ℓ+1 starting with o (here, i and o stand for incoming and outgoing). An α-tree is a rooted oriented planar tree such that • labeling the external arrows counterclockwise starting from the root, the ith arrow is incoming if α i = i and outgoing if α i = o, • each internal node has at least one outgoing arrow, • there is no node with precisely one incoming and one outgoing arrow. These trees arise in the combinatorics of algebras endowed with a binary product and a co-inner product. They are studied in details in [PT18]. It turns out that they can be understood from pebble trees.
First, as illustrated in Figure 4, there are simple bijections between the pebble trees of P 1,0 ℓ and the o ℓ+1 -trees: • Starting from a pebble tree T ∈ P 1,0 ℓ , orient each arc (p, c) of T from c to p if c is balanced, and from p to c if c is unbalanced, and forget all pebbles.
• Starting from a o ℓ+1 -tree, place at each node one less pebbles than its outdegree, and forget the orientations. In the present paper, we prefer our interpretation as pebble trees as it enables us to consider several pebble colors simultaneously.
Consider now an arbitrary signature α. Although not explicit in [PT18], there is a clear map from α-trees to o ℓ+1 -trees, which consists in replacing each incoming external arrow (like ↑) by a node with a pair of outgoing arrows (like ). This leads to a bijection between the α-trees and the pebble trees of P 1,0 ℓ where the parent of the ith leaf is a unary node marked with a pebble. Remark 12. The reader familiar with the bijective combinatorics of planar maps might also see some connections with the β-trees of [JS98,CS03]. Indeed, labeling each node p of a pebble tree by the pebble default ∆ γ (T p ), we obtain a β(1, 1)-tree. However, this map is clearly injective but not surjective, and the additional condition given by the pebble trees is unclear on β(1, 1)-trees.
Remark 13. There is also a natural map from the pebble trees of P 1,0 ℓ to the painted trees corresponding to the faces of the multiplihedron [Sta70,For08,CP22]. Namely, we can just forget all pebbles which have a pebble on the path to the root of the pebble tree to obtain a painted tree.
2.2. Pebble tree contraction poset. We now define the contraction poset on pebble trees, and will see that it is the face poset of a simplicial complex in Section 2.3 and of a polytope in Section 3.3. Remark 16. Observe that: • The set of pebble trees P b,u ℓ is clearly closed under contraction. Hence, the pebble tree contraction poset is a simplicial poset (a poset where each interval is a boolean algebra).
• The pebble tree contraction poset is ranked: the rank of a pebble tree is its number of nodes.
• The maximal pebble trees of PP b,u ℓ are the pebble trees with only unary nodes containing a single pebble and binary nodes containing no pebble (hence, they have ℓ(b + u) − u unary nodes and ℓ − 1 binary nodes, thus rank is the corolla with ℓ leaves and ℓ(b + u) − u pebbles at the root (hence it has rank 1).
Observe now that the mirroring, balancing, inserting, rerooting and uprooting maps of Definitions 6 to 10 obviously commute with contractions. This implies the following statement.   Remark 18. Following Remark 11, observe that for any signature α ∈ o · {i, o} ℓ , the α-tree contraction poset is isomorphic to the principal upper set of the pebble tree contraction poset PP 1,0 ℓ generated by the pebble tree whose root has ℓ − |α| i pebbles and ℓ children, and whose ith children is a leaf if α i = o and a unary node with one pebble and a leaf if α i = i.
Remark 19. The following observations are consequences of Remarks 11 and 18 and Proposition 17: • the o ℓ+1 -tree contraction poset is isomorphic to the pebble tree contraction poset PP 1,0 ℓ , • for any α ∈ o · {i, o} ℓ with a single occurrence of i, the α-tree contraction poset is isomorphic to the pebble tree contraction poset PP 0,1 ℓ , • for α = ooi ℓ−1 or α = oi ℓ−1 o, the α-tree contraction poset is isomorphic to the pebble tree contraction poset PP 0,0 ℓ+1 (i.e. the contraction poset on Schröder trees). 2.3. Pebble tree complex. As mentioned in Remark 16, the pebble tree contraction poset PP b,u ℓ is a simplicial poset. We now construct the corresponding simplicial complex. Recall that we denote by L(S) and B(S) the sets of leaves and of balanced colors in a subtree S. We will moreover need the following notations. Proposition 23. The pebble tree complex PC b,u ℓ is a pseudomanifold, whose face poset is isomorphic to the pebble tree poset PP b,u ℓ . Proof. Observe first that Λ(T /n) = Λ(T ) {λ(T n )} for any node n (not a leaf, nor the root) in a pebble tree T . Hence, the face poset of PC b,u ℓ is indeed isomorphic to PP b,u ℓ . We thus obtain that PC b,u ℓ is a pure simplicial complex since PP b,u ℓ is a ranked simplicial poset. It remains to prove that PC b,u ℓ is a pseudomanifold, meaning that any ridge (i.e. codimension 1 face) is contained in precisely two facets (i.e. maximal dimensional faces). Consider thus a pebble tree of corank 1, Figure 8. The pebble tree complex is a pseudomanifold. All possible corank 1 pebble trees are obtained by contracting precisely two maximal pebble trees. In the second (resp. third) picture, we mark Y (resp. X) with a • to indicate that it is •-balanced. Neither X nor Y are •-balanced in the fourth picture. and let p be the only node which is neither unary with a pebble, nor binary with no pebble. We distinguish two cases: • If p has three children and no pebble, then there are two ways to open p as usual (see Figure 8 (left)) and it does not matter whether p and its children are balanced or not for each pebble color.  Figure 9. The flip graph is the graph whose vertices are the maximal pebble trees of PP b,u ℓ and whose edges are the flips between them. Figure 9. All possible flips in a maximal pebble tree. In the second (resp. third) picture, we mark Y (resp. X) with a • to indicate that it is •-balanced. Neither X nor Y are •-balanced in the fourth picture.
Example 28. In the extreme situations of Example 2: • the flip graph on P b,u 1 is the graph of adjacent transpositions on permutations of [b], • the flip graph on P 0,0 ℓ is the rotation graph on binary trees with ℓ leaves. These extreme situations correspond to the right and left cases of Figure 9 respectively. Figure 10 illustrates a sequence of flips in maximal pebble trees of P 1,1 3 . Figures 11 and 12 illustrate the flip graphs on maximal pebble trees of P 0,1 3 and P 1,1 2 (which are isomorphic by Proposition 17 as already mentioned before).
As the dual graph of a pure simplicial pseudomanifold, the pebble tree flip graph is regular. Its degree is ℓ(1 + b + u)− u − 2. As we will see in Theorem 39 that it is the graph of a simple polytope, it has the connectivity of its degree. Among various further properties of this graph that would require more investigations, we mention the following problem in connection to [STT88,Pou14].
Problem 29. Evaluate the diameter of the flip graph on maximal pebble trees of P b,u ℓ . Finally, note that Proposition 17 and Remark 18 directly translate to morphisms between the flip graphs on the corresponding trees.

Pebble tree geometry
This section is devoted to the geometry of pebble trees. After quickly reminding some geometric preliminaries (Section 3.1), we construct the pebble tree fan (Section 3.2) and the pebble tree polytope (Section 3.3).
3.1. Geometric preliminaries. We refer to [Zie98] for a reference on polyhedral geometry, and only remind the basic notions needed later in the paper.
A (polyhedral) cone is the positive span R ≥0 R of a finite set R of vectors of R d or equivalently, the intersection of finitely many closed linear half-spaces of R d . The faces of a cone are its intersections with its supporting hyperplanes. The rays (resp. facets) are the faces of dimension 1 (resp. codimension 1). A cone is simplicial if its rays are linearly independent. A (polyhedral) fan F is a set of cones such that any face of a cone of F belongs to F, and any two cones of F intersect along a face of both. A fan is essential if the intersection of its cones is the origin, complete if the union of its cones covers R d , and simplicial if all its cones are simplicial.
Note that a simplicial fan defines a simplicial complex on its rays (the simplices of the simplicial complex are the subsets of rays which span a cone of the fan). Conversely, given a simplicial complex ∆ with ground set V , one can try to realize it geometrically by associating a ray r v of R d to each v ∈ V , and the cone R ≥0 R △ generated by the set R △ := {r v | v ∈ △} to each △ ∈ ∆. To show that the resulting cones indeed form a fan, we will need the following statement, which can be seen as a reformulation of [DRS10, Coro. 4.5.20]. • for any two adjacent facets △, denotes the unique (up to rescaling) linear dependence on R △∪△ ′ . A polytope is the convex hull of finitely many points of R d or equivalently, a bounded intersection of finitely many closed affine half-spaces of R d . The faces of a polytope are its intersections with its supporting hyperplanes. The vertices (resp. edges, resp. facets) are the faces of dimension 0 (resp. dimension 1, resp. codimension 1).
The normal cone of a face F of a polytope P is the cone generated by the normal vectors to the supporting hyperplanes of P containing F. Said differently, it is the cone of vectors c of R d such that the linear form x → c | x on P is maximized by all points of the face F. The normal fan of P is the set of normal cones of all its faces.
Consider now a complete simplicial fan F of R d with rays (r v ) v∈V and cones R ≥0 R △ for △ ∈ ∆, where R △ := {r v | v ∈ △} as in Proposition 30. To realize the fan F, one can try to pick a height vector h := (h v ) v∈V ∈ R V and consider the polytope The following classical statement characterizes the height vectors h for which the fan F is the normal fan of this polytope P h . We borrow the formulation from [CFZ02, Lem. 2.1].
Proposition 31. Let F be an essential complete simplicial fan in R n with rays (r v ) v∈V and cones R ≥0 R △ for △ ∈ ∆. Then the following are equivalent for any height vector h ∈ R V : • The fan F is the normal fan of the polytope denotes the unique linear dependence on R △∪△ ′ such that α v + α v ′ = 2.
3.2. Pebble tree fan. Fix ℓ, b, u ∈ N and consider the intervals whose union is the interval We work in the Euclidean space R I with canonical basis (e i ) i∈I . We denote by 1 J := j∈J e j the characteristic vector of a subset J ⊆ I. As our constructions actually live in the linear subspace we define the vector Example 33. In the extreme situations of Example 2: • the pebble tree fan PF b,u 1 is the braid fan, with a ray r J for each proper subset ∅ = J [b] and a maximal cone C(σ) for each permutation σ of [b], defined by the inequalities • the pebble tree fan PF 0,0 ℓ is the sylvester fan, with a ray r J for each proper interval J of [ℓ] and a maximal cone C(T ) for each binary tree T , defined by the inequalities x i ≤ x j whenever there is a path from i to j in the tree T labeled in inorder and oriented towards its root. Note that the sylvester fan coarsens the braid fan: the cone C(T ) of the sylvester fan can also be obtained by glueing the cones C(σ) of the braid fan corresponding to the linear extensions σ of T .
Theorem 34. The pebble tree fan PF b,u ℓ is an essential complete simplicial fan in H b,u ℓ , whose face lattice is the pebble tree contraction poset PP b,u ℓ . The proof of Theorem 34 relies on the description of the linear dependences among adjacent maximal cones described in Lemma 36. To obtain these dependences, we need the following preliminary statement, where we use the operation ⊗ defined in Notation 20. Proof. We analyse the five possible types of flips described in Figure 9. In all cases, we denote by R the parent of S and S ′ .
) is a linear combination of the rays r P for some subtrees P of S distinct from S (resp. of S ′ distinct from S ′ , resp. of Y ) by Lemma 35, this is indeed a linear dependence among the rays r Q associated to the subtrees Q of T and T ′ where the rays r S and r S ′ both have coefficient 1.
Again, we can develop r L(Y )⊗{•} using Lemma 35, so that we indeed obtained a linear dependence among the rays r Q for the subtrees Q of T and T ′ where the rays r S and r S ′ both have coefficient 1.
Case 4. Assume first that R has an ancestor with a •-pebble. Then we additionally denote • by U 0 the closest ancestor of R which has a •-pebble, • by U 1 , . . . , U k the closest descendants of U 0 but not descendants of R which have a •-pebble, • by V 0 , V 1 , . . . , V k the (unique) children of U 0 , U 1 , . . . , U k respectively. We have Now if R has no ancestor with a •-pebble, then using that r L(T )⊗{•} = 0, we obtain similarly • U 1 , . . . , U k are the closest descendants of the root of T but not descendants of R which have a •-pebble, • V 1 , . . . , V k are the (unique) children of U 1 , . . . , U k respectively.
and a pebble tree T such that v is contained in the interior of C(T ). As the last ℓ − 1 coordinates of v are strictly larger than all other coordinates, each of the last ℓ − 1 leaves of T is preceded by a unary node with pebble colored by b + u. Repeating the argument, we obtain that the first leaf of T is preceded by a chain of unary nodes with pebbles colored 1, . . . , b while each of the last ℓ − 1 leaves if T is preceded by a chain of unary nodes with pebbles colored 1, . . . , b + u. Finally, we obtain that the rest of the tree T is the left comb since it is the only Schröder tree whose cone in the sylvester fan contains the vector i∈[ℓ−2] r [i] . Finally, PF b,u ℓ is essential as the dimension of its cones matches the dimension of H b,u ℓ . Remark 37. A few observations on the pebble tree fan: • The simple descriptions of Example 33 for the braid fan and for the sylvester fan unfortunately fail for arbitrary b, u ≥ 0. Indeed, there is a natural way to label the nodes of a maximal pebble tree: label the binary nodes in inorder by [ℓ − 1] and the unary nodes by the only leaf first covered by this pebble. This labeling yields a cone C(T ) for each maximal pebble tree T , defined by x i ≤ x j whenever there is a directed path from i to j in the tree T oriented towards its root. However, the cones C(T ) for all maximal pebble trees T do not define a complete simplicial fan (check out the case ℓ = 2, b = 1 and u = 0). In fact, our pebble tree fan PF b,u ℓ is not refined by the braid fan in general • Our definition of the pebble tree fan PF b,u ℓ respects some symmetries of the pebble tree complex PC b,u ℓ but not all. See Proposition 42 for a precise statement directly on polytopes. • Lemma 36 actually proves that the pebble tree fan PF b,u ℓ is smooth, meaning that the principal vectors spanning the rays of any maximal cone of PF b,u ℓ form an integral basis of the space (in other words, the corresponding toric variety is smooth).
3.3. Pebble tree polytope. Our next step is to construct a polytope whose normal fan is the pebble tree fan, using the criterion of Proposition 31.
Definition 38. A submodular function on n is a map f from the subsets of [n] to R ≥0 such that f ∅ = 0 and for any subsets A and B of [n]. We then define where the minimum ranges over all subsets A and B of [n] such that A ⊆ B and A ⊇ B. Note that . . , A k are pairwise disjoint, • ∆λf = λ∆f for any scalar factor λ.
We say that f is strictly submodular when ∆f > 0.
Theorem 39. Pick three strictly submodular functions f on ℓ, g on ℓ, and h on b + u such that Observe that if V is the unique child of U , then and |B(U )| = |B(V )| + 1. We just need to prove that the function ϕ satisfies the wall-crossing inequalities of Proposition 31 for each of the linear dependences boxed in the proof of Lemma 36.
Case 1. By Lemmas 35 and 36, we have where the last inequality holds since U i = U j (resp. U ′ i = U ′ j , resp. V ′′ i = V ′′ j ) for i = j, and the pebble tree T has ℓb + ℓu − u unary subtrees. Since f, g, h take non-negative values and ϕ U − ϕ V = g U +h U −h V when V is the unique child of U , we obtain that ϕ satisfies the wall-crossing inequality Case 2. By Lemma 36, we have where the last inequality holds since S = U i = U j for i = j, and the subtree R has at most ℓb+ℓu−u unary subtrees. Since f, g, h take non-negative values and ϕ U − ϕ V = g U + h U − h V when V is the unique child of U , we obtain that ϕ satisfies the wall-crossing inequality Case 3. Symmetric to Case 2.
Case 4. Assume first that R has an ancestor with a •-pebble. Then by Lemma 36, we have where the last inequality holds since S = U i = U j = S ′ for i = j, and the subtree U 0 has at most ℓb+ℓu−u unary subtrees. Since f, g, h take non-negative values and ϕ U − ϕ V = g U + h U − h V when V is the unique child of U , we obtain that ϕ satisfies the wall-crossing inequality Assume now that R has no ancestor with a •-pebble. Then we have The wall-crossing inequality is thus even easier to satisfy since ϕ U0 − ϕ V0 does not appear.
Case 5. By Lemma 36, we have Remark 40. Note that the conditions of Theorem 39 are just sufficient conditions to ensure the wall-crossing inequalities. To find functions satisfying these conditions, pick three arbitrary strictly submodular functions f, g, h and rescale first g by a factor 4(ℓb + ℓu − u + 1) · max h/∆g, and then f by a factor (ℓb + ℓu − u) · (max g + max h)/∆f . We just write PTP b,u ℓ if we want to consider PTP b,u ℓ (f, g, h) for arbitrary f, g, h satisfying the conditions of Theorem 39. Figure 13. The pebble tree polytopes PTP 0,1 3 (left) and PTP 1,1 2 (right).

4.2.
Enumeration of all pebble trees. We now consider all pebble trees.
Definition 50. For ℓ, n, u, b ∈ N, we denote by p b,u ℓ,n the number of pebble tree with ℓ leaves, n nodes, b balanced and u unbalanced colors. We consider the generating function Proposition 51. The generating functions P b,u (x, y) satisfy the functional equations where δ is the Kronecker delta, where each X i ranges among arbitrary subsets of [d] while each Y j ranges among strict subsets of [d], and where b k : , • or a node with some pebbles and d ≥ 2 children in P B1,U1 [s1,t1] , . . . , The functional equations for P b,u (x) are immediate consequences of this structural decomposition by classical generatingfunctionology [FS09]. The algebraicity of P b,u (x) follows as it belongs to a system of finitely many polynomial equations (all equations for a given sum b + u).
The expansions of the generating functions P b,u (x, 1) and P b,u (x, y) for b + u ≤ 2 can be found in Section 4.3. Finally, we observe that the evaluations of P b,u (x, y) at y = 1 and y = −1 have a geometric meaning.
Proposition 53. For any b, u ∈ N, the evaluation P b,u (x, 1) is the generating function of the total number of faces of the pebble tree polytope PTP b,u ℓ , and P b,u (x, −1) = x (−1) b + (−1) u x .

Aknowledgements
I am grateful to Doriann Albertin for discussions around Problem 49 and for a very constructive proofreading, to Wenjie Fang for pointing out Remark 12 and for discussions on Propositions 45 and 51, to Guillaume Laplante-Anfossi for motivating me to find polytopal realizations of the assocoipahedra, and to Thibaut Mazuir for algebraic discussions on the assocoipahedra. This research benefited from computations and tests done using the open-source mathematical software Sage [Sd16] and its combinatorics features developed by the Sage-combinat community [SCc16], and from the Online Encyclopedia of Integer Sequences [OEI10].