Planted Brussels Sprouts (after Ji-Propp)

Nathan Williams Department of Mathematical Sciences University of Texas at Dallas Richardson, Texas 75080 USA

                  nathan.f.williams@gmail.com

Abstract We give an elementary argument to show that games of Planted Brussels Sprouts are in bijection with factorizations of the long cycle. This simplifies recent work of Ji and Propp. We also address a centrally symmetric version of the game.

1 Planted Brussels Sprouts and factorizations of the long cycle

1.1 Planted Brussels Sprouts

Ji and Propp recently analyzed the number of ways to “play” a two-player game called Planted Brussels Sprouts [10]. The game takes place in a disk whose boundary is regularly marked with n+1 ≥ 1 distinct points, which we will label clockwise by distinct numbers ℓ = (ℓ_{1}, …, ℓ_{n+1}). Players take turns drawing arcs in the disk that connect two labelled points without passing through any other arcs. These two points are then stripped of their labels, a short line segment is drawn transversely to the new arc, and the stripped labels are assigned to the end points of this short segment so that the new labels appear clockwise of the old labels. See Figure 1 for an example.

It is clear that a game of Planted Brussels Sprouts is uniquely determined by its sequence of stripped labels (i_{1}j_{1}) ⋯ (i_{n}j_{n}) (where i_{k} < j_{k} are the labels stripped on the kth move), and we write Play(ℓ) for the set of all such sequences. Since no player draws an arc for the disk marked with a single point, we take the convention that Play(ℓ) = ∅ when n = 0 and ℓ = (ℓ_{1}).

Figure 1: A game of Planted Brussels Sprouts for n + 1 = 5. The corresponding sequence of stripped labels is (13)(35)(12)(34).

Figure 2: Visualizing the factorization (12345) = (13)(35)(12)(34). In accordance with Theorem 1, reading the labels of the edges incident to the vertex 3 clockwise gives the decreasing sequence 4,2,1.

1.2 Factorizations of the long cycle

On the other hand, fix the symmetric group 𝔖_{n+1} and write

T = {(ij) : 1 ≤ i < j ≤ n+1}

for the set of transpositions. A reduced factorization of the cycle ℓ = (ℓ_{1}, …, ℓ_{n+1}) into transpositions is an expression

(ℓ_{1}, …, ℓ_{n+1}) = (i_{1}j_{1}) ⋯ (i_{n}j_{n}),

and we denote by Red(ℓ) the set of all such factorizations. There are no factorizations of a one-cycle into transpositions, so that Red(ℓ) = ∅ when n = 0 and ℓ = (ℓ_{1}). We can visualize a factorization by drawing arcs in the same initial disk we used in Planted Brussels Sprouts, where (i_{k}j_{k}) is drawn as an arc connecting i_{k} and j_{k}, and labeled with k. An example is given in Figure 2.

Goulden and Yong characterized this visualization of factorizations with the following theorem.

Theorem 1 ([8, Theorem 2.2]). A tree with vertex set the n+1 points on the boundary of a disk, whose n edges do not cross and are distinctly labelled from 1 to n, is a factorization of the cycle (ℓ_{1}, …, ℓ_{n+1}) iff the labels of the edges when read clockwise around a vertex form a decreasing sequence.

2 Recursion, counting, and bijection

For any sequence (c_{1}, …, c_{k}), denote concatenation by (c_{1}, …, c_{k}) • c_{k+1} = (c_{1}, …, c_{k}, c_{k+1}) and c_{0} • (c_{1}, …, c_{k}) = (c_{0}, c_{1}, …, c_{k}). The shuffle of two sequences of lengths i and j is the set of all \frac{(i+j)!}{i!j!} interlacings defined inductively by

(a • a_{i}) � (b • b_{j}) = ( (a � (b • b_{j})) • a_{i}) ⊔ ( ((a • a_{i}) � b) • b_{j}),

where a = (a_{1}, …, a_{i−1}) and b = (b_{1}, …, b_{j−1}). As a special case, a � ∅ = ∅ � a = a.

Since the first move of a game of Planted Brussels Sprouts divides the game into two disjoint smaller games, and since the product of a cycle by transposition breaks the cycle into two disjoint smaller cycles, there is a immediate recursion satisfied by both the stripped labels and the reduced factorizations (thinking of both as sequences):

Play(ℓ) = ⨆_{(ij)∈T}(ij) • (Play(ℓ_{p(i)}, …, ℓ_{p(j)−1}) � Play(ℓ_{p(j)}, …, ℓ_{p(i)−1})) ,  (1)
Red(ℓ) = ⨆_{(ij)∈T}(ij) • (Red(ℓ_{p(i)}, …, ℓ_{p(j)−1}) � Red(ℓ_{p(j)}, …, ℓ_{p(i)−1})) ,  (2)

where p(i) = k if ℓ_{k} = i and indices are taken modulo n + 1. Since the two sets have the same initial condition for n = 0 (recall that there is no Planted Brussels Sprouts game on a single vertex, and there are no factorizations of a one-cycle into transpositions), this recursion induces a bijection between the two sets.

Example 2. We illustrate the recursion of Eq. (2) for games of Planted Brussels Sprouts with n + 1 ≤ 4 initial points. The case n + 1 = 1 is the initial condition with no game, while the case n + 1 = 2 has the single game consisting of connecting the two points.

Play(1) = ∅, and
Play(1, 2) = {(12)}.

The three games for n + 1 = 3 are now computed as:

Play(1, 2, 3) = [(12) • (Play(1) � Play(2, 3))]⊔ [(13) • (Play(1, 2) � Play(3))]⊔ [(23) • (Play(2) � Play(3, 1))] = {(12)(23), (13)(12), (23)(13)}.

Similarly, the sixteen games for n + 1 = 4 are computed as Play(1, 2, 3, 4) =

[(12) • (Play(1) � Play(2, 3, 4))]⊔ [(13) • (Play(1, 2) � Play(3, 4))]⊔ [(14) • (Play(1, 2, 3) � Play(4))]⊔ [(23) • (Play(2) � Play(3, 4, 1))]⊔ [(24) • (Play(2, 3) � Play(4, 1))]⊔ [(34) • (Play(3) � Play(4, 1, 2))] = \begin{matrix}\{(12)(23)(34), (12)(24)(23), (12)(34)(24)\}⊔ \\ \{(13)(12)(34), (13)(34)(12)\}⊔ \\ \{(14)(12)(23), (14)(13)(12), (14)(23)(13)\}⊔ \\ \{(23)(13)(34), (23)(14)(13), (23)(34)(14)\}⊔ \\ \{(24)(23)(14), (24)(14)(23)\}⊔ \\ \{(34)(12)(24), (34)(14)(12), (34)(24)(14)\}. \end{matrix}

Solving the recurrence of Eq. (2) allows us to count the number of games of Planted Brussel Sprouts.

Proposition 3 ([10, Theorem 3]). Write R_{n+1} for the common number of reduced factorizations of an (n+1)-cycle into transpositions and games of Planted Brussel Sprouts on n+1 initial points. Then for n ≥ 1, R_{n+1} = (n + 1)^{n−1} (\underline{A000272}).

Proof. As explained in [4, 15] (independently), R_{n+1} satisfies a simple recurrence. To write down this recurrence, we group all initial arcs in a game of Planted Brussel Sprouts (or initial transposition in a factorization) according to how they partition the disk. Associate a boundary vertex lying on an initial arc with the region lying clockwise of that boundary vertex (any later arc connecting to that vertex must come from the corresponding region). For each 1 ≤ i ≤ n, when n + 1 is odd or n + 1 is even and i ≠ \frac{n+1}{2}, there are n + 1 arcs separating the disk with i vertices on one side and n + 1 − i vertices on the other (including the boundary vertices on the initial arc); when n + 1 is even and i = \frac{n+1}{2}, there are only \frac{n+1}{2} such arcs. By grouping i with n + 1 − i, we write these two cases uniformly as the recurrence

R_{n+1} = \frac{n + 1}{2} ∑_{i=1}^{n} \binom{n − 1}{i − 1}R_{i}R_{n+1−i},  (3)

As explained above, the factor \frac{n+1}{2} keeps track of the initial arc (ij) in a game of Planted Brussel Sprouts (or initial transposition in a factorization) up to rotation. The factor \binom{n−1}{i−1} counts the number of possible ways to interlace commuting moves (or transpositions). This recurrence is then easily solved (see, for example, [15, Example 3.5]) to obtain the famous formula R_{n+1} = (n + 1)^{n−1}.

Proposition 4 gives a direct statement of the bijection induced by Eq. (2).

Proposition 4 ([10, Theorem 5]). Thinking of an ordered list of stripped labels as a product of transpositions gives a bijection Play(ℓ) ≃ Red(ℓ).

Proof. We describe the bijection from Play(ℓ) to Red(ℓ) geometrically, using the visualizations of both sets as in Figures 1 and 2.

Consider the following modification of a game of Planted Brussels Sprouts. As with a visualization of a factorization, our modified game will eliminate the transverse short segments drawn during a game of Planted Brussels Sprouts and only draw arcs between the original n + 1 vertices on the boundary of the disk.

Define a boundary segment to be a line connecting a boundary vertex to a point nearby in the interior of the disk; the label of the boundary vertex is transferred to the interior point. Before the game starts, replace each labelled boundary vertex by a boundary segment (see Figure 3). Each arc in our modified game of Planted Brussels Sprouts will be drawn to connect two (labelled) interior vertices of boundary segments, which can be seen as an arc connecting the two original boundary vertices.

In this modified game, we no longer draw short segments transversely to new arcs. Each time an arc connects to a boundary segment, we duplicate that boundary segment so that its boundary vertex remains the same, but so that the new boundary segment lies counterclockwise of the old. Since replacing the transverse short segments by boundary segments does not change the topology (and, in particular, which arcs can be drawn later), our modified game is equivalent to Planted Brussels Sprouts.

Furthermore, since new boundary segments lie counterclockwise of the old, cycles are forbidden and the resulting graph is a tree. Moreover, the order in which the arcs are drawn satisfy the property that they decrease when read clockwise around a boundary vertex. We conclude from Theorem 1 that (discarding the remaining boundary segments not attached to arcs) we have produced a visualization of a factorization of the long cycle from a game of Planted Brussels Sprouts.

The inverse bijection is similar: we now work to replace the boundary segments with the transverse short segments of Planted Brussels Sprouts at each step. Start with a tree satisfying Theorem 1. For each boundary vertex, add a boundary segment that lies counterclockwise of all arcs emanating from that vertex. Now in the reverse order of the labels of the arcs, for each arc e, slide the ends of the arcs or boundary segments lying immediately counterclockwise of e so that they meet in the middle of e.

The bijection in the language of stripped labels is now immediate from the preceding geometric description.

The bijection of Proposition 4 is illustrated in Figure 3.

3 Corollaries

Corollary 5 ([10, Theorem 1]). There is a bijection from Play(ℓ) to labelled trees on n + 1 vertices.

Proof. A bijection between factorizations and labelled trees is given in [8].

Corollary 6 ([10, Theorem 4]). There is a bijection from Play(ℓ) to parking functions of length n.

Proof. A bijection from factorizations to parking functions is given in [17]. The bijection is given by sending a factorization (i_{1}, j_{1}) ⋯ (i_{n}, j_{n}) with i_{k} < j_{k} to the word i_{1} ⋯ i_{n}.

Figure 3: An illustration of Proposition 4 (compare with Figure 1). The top line is the modified game of Planted Brussels Sprouts, which replaces the transverse line segments with topologically equivalent boundary segments. The bottom line is the inverse bijection.

Corollary 7 ([10, Theorem 2]). Ignoring the order arcs are drawn, there are \frac{1}{2n+1} \binom{3n}{n} (\underline{A001764}) possible games of Planted Brussels Sprouts on n + 1 vertices.

Proof. The proof of Proposition 4 gives a bijection between the arcs in Planted Brussels Sprouts and the arcs in a visualization of a factorization of the long cycle. Ignoring the order arcs are drawn in a game of Planted Brussels Sprouts corresponds to ignoring the labels on the arcs in a visualization of a factorization. These correspond to factorizations of the long cycle up to commutations of transpositions, which are counted in [7]. See Figure 4 for an example.

The unlabelled visualizations of the factorizations are known in the literature as noncrossing trees [5, 6, 12, 14]. Note also that there is a simple bijection from noncrossing trees on n vertices to quadrangulations of a 2n-gon, which are well-known to be counted by the Fuss-Catalan number \frac{1}{2n+1} \binom{3n}{n}.

4 Factorizations of Coxeter elements

The symmetric group 𝔖_{n+1} is an example of a finite Coxeter group W, and many properties of the symmetric group carry over to these more general groups. Just as 𝔖_{n+1} has a presentation using the n simple transpositions {(i, i + 1)}_{1≤i≤n}, a Coxeter group W has a presentation using an n element set S called simple reflections. Similarly, a long cycle ℓ ∈ 𝔖_{n+1} is a (conjugate of a) product of the simple transpositions. A (conjugate of a) product of the simple reflections in a Coxeter group W is called a Coxeter element (written c), whose order is denoted h (so that c^{h} is the identity element of W).

Figure 4: Ignoring the labels in a visualization of a factorization of the long cycle gives factorizations up to commutation—for example, the unlabelled factorization on the left could have come from any of the three factorizations (13)(35)(12)(34), (13)(12)(35)(34), or (13)(35)(34)(12).

There is a long-studied generalization of this story of reduced factorizations to a finite Coxeter group W and a Coxeter element—a 1974 letter from Deligne to Looijenga (written after conversations with Tits and Zagier!) using properties of bipartite Coxeter elements to establish a beautiful recurrence on the set Red(c) of factorizations of the Coxeter element c into reflections [4], which allows for a simple case-by-case proof of the uniform formula

|Red(c)| = \frac{n!h^{n}}{|W |} .  (4)

The same recurrence was independently rediscovered and refined by Reading in 2007 [15], by analogy to methods he developed to model finite-type cluster algebras using sortable elements. In the case of the symmetric group 𝔖_{n+1}, the recurrence is exactly Eq. (3).

More recently, Chapuy and Stump used a standard representation-theoretic technique (the sum of all reflections is in the center of the group algebra) due to Frobenius to give a beautiful extension of Eq. (4) to all well-generated complex reflection groups in 2012 [3]. Chapuy and Stump’s work inspired Michel in 2014 to give the first uniform proof of Eq. (4) for Weyl groups using properties of Deligne-Lusztig representations [11].

Note also that representation theorists study factorizations of Coxeter elements under the name of exceptional sequences, associated to quivers of Dynkin type.

5 Centrally symmetric Brussels Sprouts

As an illustration of the generality suggested by Section 4, we give a brief account of the centrally symmetric version of Planted Brussels Sprouts.

5.1 Centrally symmetric Brussels Sprouts

The game is now played in a disk whose boundary is marked with 2n ≥ 2 distinct points labelled clockwise (ℓ_{1}, …, ℓ_{n}, \overline{ℓ}_{1}, …, \overline{ℓ}_{n}). A move now consists of drawing an arc connecting two labelled points without passing through any other arcs, while simultaneously drawing a second arc (if necessary) to maintain a half-turn rotational symmetry of the diagram. As before, the connected points are stripped of their labels, a short segment is drawn transversely to the new arc, and the stripped labels are assigned clockwise to the end points of the new short segments. See Figure 5 for an example.

Again, the game is uniquely determined by its sequence of stripped labels—we abbreviate the central symmetry by writing ((ℓ_{i}, ℓ_{j})) for the pair (ℓ_{i}, ℓ_{j})(\overline{ℓ}_{i}, \overline{ℓ}_{j}), and ((ℓ_{i}, \overline{ℓ}_{j})) for the pair (ℓ_{i}, \overline{ℓ}_{j})(\overline{ℓ}_{i}, ℓ_{j}). We write Play_{B}(ℓ) for the set of all such sequences.

Figure 5: A game of Centrally Symmetric Planted Brussels Sprouts for n = 3. The corresponding sequence of stripped labels is ((12))((2\overline{3}))(2\overline{2}).

5.2 Factorizations of a Coxeter element

The Coxeter group of type B_{n} (which we shall simply denote as B_{n}) has a permutation representation on the set \{1, 2, …, n, \overline{1}, \overline{2}, …, \overline{n}\}. In this representation (continuing the notation from the previous section), the reflections of the group are

T = \{((ij)) : 1 ≤ i < j ≤ n\} ⊔ \{((i\overline{j})) : 1 ≤ i < j ≤ n\} ⊔ \{(i\overline{i}) : 1 ≤ i ≤ n\} .

A type B_{n} reduced factorization of the cycle (ℓ_{1}, …, ℓ_{n}, \overline{ℓ}_{1}, …, \overline{ℓ}_{n}) is an expression for that element as a product of n reflections. We write Red_{B}(ℓ) for the set of all such factorizations. As in the symmetric group, we can visualize a factorization by drawing arcs in the same initial disk we used in centrally symmetric Planted Brussels Sprouts. An example is given in Figure 6.

5.3 Bijection and corollaries

Games of Centrally Symmetric Planted Brussels Sprouts can be thought of as a special subset of games of Planted Brussels Sprouts (in which a move is immediately followed by

Figure 6: Visualizing the factorization (123\overline{123}) = ((12))((2\overline{3}))(2\overline{2}).

its centrally symmetric move). Similarly, there is an embedding of B_{n} ↪ 𝔖_{2n} that sends \overline{i} ↦ n + i. By mapping the reflections of B_{n} to the corresponding reflections or pairs of reflections in 𝔖_{2n}, we have related the factorizations of the Coxeter element in type B_{n} to a special subset of factorizations of the long cycle in 𝔖_{2n} (in which a transposition is immediately followed by its centrally symmetric transposition).

Let ℓ = (ℓ_{1}, …, ℓ_{n}, \overline{ℓ}_{1}, …, \overline{ℓ}_{n}). Since we have the embeddings Play_{B}(ℓ) ↪ Play(ℓ) and Red_{B}(ℓ) ↪ Red(ℓ) as centrally symmetric subsets, and since the bijection from Proposition 4 between Play(ℓ) and Red(ℓ) preserves this symmetry, Proposition 4 restricts to a bijection between Play_{B}(ℓ) and Red_{B}(ℓ).

Corollary 8. Thinking of an ordered list of stripped labels as a product of reflections gives a bijection Play_{B}(ℓ) ≃ Red_{B}(ℓ).

We now obtain the analogues of Proposition 3 and Corollaries 6 and 7.

Proposition 9 ([4, 15]). For n ≥ 1, |Play_{B}(ℓ)| = n^{n} (\underline{A000312}).

Proof. Let R_{n}^{B} = |Play_{B}(ℓ)|. As in Proposition 3, we could write down a recurrence for R_{n}^{B}; we prefer to give an elegant direct proof that R_{n}^{B} = n^{2} · R_{n} (see, for example, [13]).

It is clear from the geometric interpretation given in Section 5.2 that in any factorization of the cycle (ℓ_{1}, …, ℓ_{n}, \overline{ℓ}_{1}, …, \overline{ℓ}_{n}) = t_{1} ⋯ t_{n}, there is exactly one reflection of the form (a\overline{a}) for 1 ≤ a ≤ n: two such arcs would cross, and a graph with only arcs of the form ((ab)) and ((a\overline{b})) couldn’t be a tree.

Recall that there is a braid group action on Red(ℓ)—a generator s_{i} of the braid group Braid_{n−1} acts on a factorization by

s_{k} (t_{1} ⋯ t_{k}t_{k+1} ⋯ t_{n}) = t_{1} ⋯ t_{k+1}^{t_{k}}t_{k} ⋯ t_{n}  (5)

where x^{y} = xyx^{−1}. The action of a generator is often called a Hurwitz move. It is easy to check that they satisfy the braid group relations (that is, s_{i}s_{i+1}s_{i} = s_{i+1}s_{i}s_{i+1}):

s_{i}s_{i+1}s_{i} (t_{1} ⋯ t_{i}t_{i+1}t_{i+2} ⋯ t_{n}) = s_{i}s_{i+1} (t_{1} ⋯ t_{i+1}^{t_{i}}t_{i}t_{i+2} ⋯ t_{n})

= s_{i} (t_{1} ⋯ t_{i+1}^{t_{i}}t_{i+2}^{t_{i}}t_{i} ⋯ t_{n})

= t_{1} ⋯ t_{i+2}^{t_{i}t_{i+1}}t_{i+1}^{t_{i}}t_{i} ⋯ t_{n} while also

s_{i+1}s_{i}s_{i+1} (t_{1} ⋯ t_{i}t_{i+1}t_{i+2} ⋯ t_{n}) = s_{i+1}s_{i} (t_{1} ⋯ t_{i}t_{i+2}^{t_{i+1}}t_{i+1} ⋯ t_{n})
= s_{i+1} (t_{1} ⋯ t_{i+2}^{t_{i}t_{i+1}}t_{i}t_{i+1} ⋯ t_{n})
= t_{1} ⋯ t_{i+2}^{t_{i}t_{i+1}}t_{i+1}^{t_{i}}t_{i} ⋯ t_{n}.

Since each Hurwitz move is invertible, the action of Braid_{n−1} gives a bijection between factorizations with (a\overline{a}) in position i and factorizations with (a\overline{a}) in position j. So R_{n}^{B} is equal to n times the number of factorizations with a reflection (a\overline{a}) occurring as the first reflection.

Since 1 ≤ a ≤ n, there are n choices of this first reflection (a\overline{a}). In the visualization of a factorization using the disk, each choice for a divides the disk into two halves, with n vertices associated to each half—by symmetry (an arc drawn in the one half is just mirrored in the other half) the number of ways to finish the factorization is now given by R_{n−1}. Hence,

R_{n}^{B} = n^{2} · R_{n} = n^{2}n^{n−2} = n^{n}.

Corollary 10 ([1, Theorem 3.2]). There is a bijection from Play_{B}(ℓ) to words on {1, 2, …, n} of length n.

Proof. As explained in [1], the bijection is given by sending a factorization t_{1} ⋯ t_{n} to the word w_{1} ⋯ w_{n} where

w_{k} = \begin{cases}i, & if t_{k} = ((ij)) with 1 ≤ i < j ≤ n; \\ j, & if t_{k} = ((i\overline{j})) with 1 ≤ i < j ≤ n; \\ i, & if t_{k} = (i\overline{i}). \end{cases}

Corollary 11 ([9, Theorem 1]). Ignoring the order arcs are drawn, there are \binom{3n−2}{n−1} (\underline{A045721}) possible games of centrally symmetric Planted Brussels Sprouts on 2n vertices.

Proof. We learned of this formula (without proof) from [2]. A proof can be given as follows.

As in Corollary 7, ignoring the order in which arcs are drawn corresponds to a factorization up to commutation. Such factorizations are represented visually as centrally symmetric noncrossing trees (with unlabelled edges). It was shown in [9] that the number of noncrossing graphs with m vertices and k edges fixed under rotation by \frac{2π}{d} for any divisor d of m satisfies a cyclic sieving phenomenon with respect to the polynomial

\frac{1}{[m − 1]_{q}} [ \begin{matrix}3m − 3 \\ m + k \end{matrix} ]_{q} [ \begin{matrix}k − 1 \\ m − 2 \end{matrix} ]_{q}

(see [16] for further details on q-analogues and the cyclic sieving phenomenon). Centrally symmetric noncrossing trees on 2n vertices are recovered by taking m = 2n (the number of vertices), k = 2n − 1 (the condition to be a tree), and d = 2 (the centrally symmetric condition). Finally, it is straightforward to check that

\binom{3n − 2}{n − 1} = \frac{1}{[2n − 1]_{q}} [ \begin{matrix}6n − 3 \\ 4n − 1 \end{matrix} ]_{q} |_{q=−1}.

References

[1] P. Biane, Parking functions of types A and B, Electronic J. Combinatorics 9(1) (2002), Note #N7.

[2] F. Chapoton, Les algèbres amassées, preprint, 2018. Available at http://irma.math.

unistra.fr/~chapoton/clusters.html.

[3] G. Chapuy and C. Stump, Counting factorizations of Coxeter elements into products of reflections, J. London Math. Soc. 90 (2014), 919–939.

[4] P. Deligne, Letter to E. Looijenga, 1974.

[5] E. Deutsch, S. Feretić, and M. Noy, Diagonally convex directed polyominoes and even trees: a bijection and related issues, Discrete Math. 256 (2002), 645–654.

[6] E. Deutsch and M. Noy, Statistics on non-crossing trees, Discrete Math. 254 (2002), 75–87.

[7] J. Eidswick, Short factorizations of permutations into transpositions, Discrete Math. 73 (1989), 239–243.

[8] I. Goulden and A. Yong, Tree-like properties of cycle factorizations, J. Combin. Theory, Ser. A 98 (2002), 106–117.

[9] A. Guo, Cyclic sieving phenomenon in non-crossing connected graphs, Electronic J. Combin. 18(1) (2011), Paper P9.

[10] C. Ji and J. Propp, Brussels sprouts, noncrossing trees, and parking functions, preprint,

May 2018. Available at https://arxiv.org/abs/1805.03608.

[11] J. Michel, “Case-free” derivation for Weyl groups of the number of reflection factorisations of a Coxeter element, preprint, 2014. Available at https://arxiv.org/abs/

1408.0721.

[12] M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math. 180 (1998), 301– 313.

[13] M. Obaid, K. Nauman, W. Al-Shammakh, W. Fakieh, and C. Ringel, The number of complete exceptional sequences for a Dynkin algebra, In Colloquium Mathematicae, Vol. 133, Institute of Mathematics, Polish Academy of Sciences, 2013, pp. 197–210.

[14] A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math. 250 (2002), 181–195.

[15] N. Reading, Chains in the noncrossing partition lattice, SIAM J. Discrete Math. 22 (2008), 875–886.

[16] V. Reiner, D. Stanton, and D. White, The cyclic sieving phenomenon, J. Combin. Theory, Ser. A 108 (2004), 17–50.

[17] R. P. Stanley, Parking functions and noncrossing partitions, Electron. J. Combin. 4(2) (1997), Paper #R20.

2010 Mathematics Subject Classification: Primary 20F55. Keywords: Planted Brussels Sprouts, reflection factorization, Coxeter element, Coxeter group.

(Concerned with sequences \underline{A000272}, \underline{A001764}, \underline{A000312}, and \underline{A045721}.)

Received May 11 2018; revised versions received May 24 2018; August 31 2018; September 1 2018. Published in Journal of Integer Sequences, November 25 2018.

Return to Journal of Integer Sequences home page.