\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{mathtools}
\usepackage{thmtools}
\usepackage{shuffle}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\usepackage{cleveref}
\crefformat{equation}{Eq.~(#2#1#3)}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Planted Brussels Sprouts (after Ji-Propp)
}
\vskip 1cm
\large
Nathan Williams \\ 
Department of Mathematical Sciences \\ 
University of Texas at Dallas \\ 
Richardson, Texas 75080 \\
USA\\
\href{mailto:nathan.f.williams@gmail.com}{\tt nathan.f.williams@gmail.com} \\
\end{center}

\vskip .2 in

\begin{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.
\end{abstract}

\section{Planted Brussels Sprouts and factorizations of the long cycle}

\subsection{Planted Brussels Sprouts}
Ji and Propp recently analyzed the number of ways to ``play'' a two-player game called {\it Planted Brussels Sprouts}~\cite{JiPropp}.  The game takes place in a disk whose boundary is regularly marked with $n{+}1 \geq 1$ distinct points, which we will label clockwise by distinct numbers $\mathbf{\ell}=(\ell_1,\ldots,\ell_{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~\Cref{fig:game} 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) \cdots (i_{n} j_{n})$ (where $i_k<j_k$ are the labels stripped on the $k$th move), and we write $\mathrm{Play}(\mathbf{\ell})$ 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 $\mathrm{Play}(\ell)=\emptyset$ when $n=0$ and $\ell=(\ell_1)$.

\begin{figure}[htbp]
\begin{center}
\includegraphics[height=1in]{pic1.eps}\includegraphics[height=1in]{pic2.eps}\includegraphics[height=1in]{pic3.eps}\includegraphics[height=1in]{pic4.eps}\includegraphics[height=1in]{pic5.eps}
\end{center}
\caption{A game of Planted Brussels Sprouts for $n+1=5$.  The corresponding sequence of stripped labels is $(13)(35)(12)(34)$.}
\label{fig:game}
\end{figure}

\subsection{Factorizations of the long cycle}
On the other hand, fix the symmetric group $\mathfrak{S}_{n+1}$ and write \[T = \{(i j) : 1 \leq i < j \leq n{+}1\}\] for the set of transpositions.  A {\it reduced factorization of the cycle $\mathbf{\ell}=(\ell_1,\ldots,\ell_{n+1})$ into transpositions} is an expression \[(\ell_1,\ldots,\ell_{n+1}) = (i_1 j_1) \cdots (i_{n} j_{n}),\] and we denote by $\mathrm{Red}(\mathbf{\ell})$ the set of all such factorizations.  There are no factorizations of a one-cycle into transpositions, so that $\mathrm{Red}(\ell)=\emptyset$ when $n=0$ and $\ell=(\ell_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~\Cref{fig:fact}.

\begin{figure}
	\begin{center}
	\includegraphics[height=1.5in]{fact2.eps}
	\end{center}
	\caption{Visualizing the factorization $(12345)=(13)(35)(12)(34)$.  In accordance with~\Cref{thm:gouldenyong}, reading the labels of the edges incident to the vertex 3 clockwise gives the decreasing sequence 4,2,1.}
\label{fig:fact}
\end{figure}

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

\begin{theorem}[{\cite[Theorem 2.2]{goulden2002tree}}]
	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 $(\ell_1,\ldots,\ell_{n+1})$ iff the labels of the edges when read clockwise around a vertex form a decreasing sequence.
	\label{thm:gouldenyong}
\end{theorem}

\section{Recursion, counting, and bijection}


For any sequence $(c_1,\ldots,c_k)$, denote concatenation by $(c_1,\ldots,c_k) \bullet c_{k+1} = (c_1,\ldots,c_k,c_{k+1})$ and  $c_0 \bullet (c_1,\ldots,c_k) = (c_0,c_1,\ldots,c_k)$.  The {\it shuffle} of two sequences of lengths $i$ and $j$ is the set of all $\frac{(i+j)!}{i!j!}$ interlacings defined inductively by 
\[(\mathbf{a}\bullet a_i) \shuffle (\mathbf{b}\bullet b_j) = \big(\left(\mathbf{a}\shuffle  (\mathbf{b}\bullet b_j)\right) \bullet a_i\big) \sqcup\big(\left((\mathbf{a}\bullet a_i)\shuffle  \mathbf{b}\right) \bullet b_j\big),\] where $\mathbf{a}=(a_1,\ldots,a_{i-1})$ and $\mathbf{b}=(b_1,\ldots,b_{j-1})$.  As a special case, $\mathbf{a} \shuffle \emptyset =   \emptyset  \shuffle \mathbf{a} = \mathbf{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):
\begin{align}
	\mathrm{Play}(\mathbf{\ell}) &= \bigsqcup_{(i j) \in T}  (i j) \bullet \left(\mathrm{Play}(\ell_{p(i)},\ldots,\ell_{p(j)-1}) \shuffle \mathrm{Play}(\ell_{p(j)},\ldots,\ell_{p(i)-1})\right), \\
	\mathrm{Red}(\mathbf{\ell}) &= \bigsqcup_{(i j) \in T} (i j) \bullet  \left(\mathrm{Red}(\ell_{p(i)},\ldots,\ell_{p(j)-1}) \shuffle \mathrm{Red}(\ell_{p(j)},\ldots,\ell_{p(i)-1})\right),
\label{eq:recurrencep}
\end{align}
where $p(i)=k$ if $\ell_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.

\begin{example}
We illustrate the recursion of~\Cref{eq:recurrencep} for games of Planted Brussels Sprouts with $n+1\leq 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. 
\begin{align*}
\mathrm{Play}(1) &= \emptyset, \text{ and } \\
\mathrm{Play}(1,2) &= \{(12)\}.
\end{align*}
The three games for $n+1=3$ are now computed as:
\[
\mathrm{Play}(1,2,3) =
\begin{array}{l}
 [(12) \bullet \big(\mathrm{Play}(1) \shuffle \mathrm{Play}(2,3)\big)] \sqcup \\ \null
 [(13) \bullet \big(\mathrm{Play}(1,2) \shuffle \mathrm{Play}(3)\big)] \sqcup \\ \null
 [(23) \bullet \big(\mathrm{Play}(2) \shuffle \mathrm{Play}(3,1)\big)]
\end{array}
= \{(12)(23),(13)(12),(23)(13)\}.
\]
Similarly, the sixteen games for $n+1=4$ are computed as $\mathrm{Play}(1,2,3,4) =$
\[
\begin{array}{l}
 [(12) \bullet \big(\mathrm{Play}(1) \shuffle \mathrm{Play}(2,3,4)\big)] \sqcup \\ \null
 [(13) \bullet \big(\mathrm{Play}(1,2) \shuffle \mathrm{Play}(3,4)\big)] \sqcup \\ \null
 [(14) \bullet \big(\mathrm{Play}(1,2,3) \shuffle \mathrm{Play}(4)\big)] \sqcup \\ \null
 [(23) \bullet \big(\mathrm{Play}(2) \shuffle \mathrm{Play}(3,4,1)\big)] \sqcup \\ \null
 [(24) \bullet \big(\mathrm{Play}(2,3) \shuffle \mathrm{Play}(4,1)\big)] \sqcup \\ \null
 [(34) \bullet \big(\mathrm{Play}(3) \shuffle \mathrm{Play}(4,1,2)\big)]
\end{array}
= 
\begin{array}{r}
 \big\{(12)(23)(34),(12)(24)(23),(12)(34)(24)\big\} \sqcup \\
 \big\{(13)(12)(34),(13)(34)(12)\big\} \sqcup \\
 \big\{(14)(12)(23),(14)(13)(12),(14)(23)(13)\big\} \sqcup \\
 \big\{(23)(13)(34),(23)(14)(13),(23)(34)(14)\big\} \sqcup \\
 \big\{(24)(23)(14),(24)(14)(23)\big\} \sqcup \\
 \big\{(34)(12)(24),(34)(14)(12),(34)(24)(14)\big\}.
\end{array}
\]

\end{example}

Solving the recurrence of~\Cref{eq:recurrencep} allows us to count the number of games of Planted Brussel Sprouts.

\begin{proposition}[{\cite[Theorem 3]{JiPropp}}]
	\label{prop:count}
Write $\mathcal{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\geq 1$, $\mathcal{R}_{n+1}=(n+1)^{n-1}$ (\seqnum{A000272}).
\end{proposition}

\begin{proof}
As explained in~\cite{deligne1974letter,reading2008chains} (independently), $\mathcal{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 \leq i \leq n$, when $n+1$ is odd or $n+1$ is even and $i \neq \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
\begin{equation}\mathcal{R}_{n+1}=\frac{n+1}{2} \sum_{i=1}^n \binom{n-1}{i-1} \mathcal{R}_i \mathcal{R}_{n+1-i},\label{eq:rec}
\end{equation}
As explained above, the factor $\frac{n+1}{2}$ keeps track of the initial arc $(i j)$ 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,~\cite[Example 3.5]{reading2008chains}) to obtain the famous formula $\mathcal{R}_{n+1}=(n+1)^{n-1}$.
\end{proof}


\Cref{thm:main} gives a direct statement of the bijection induced by~\Cref{eq:recurrencep}. 

\begin{proposition}[{\cite[Theorem 5]{JiPropp}}]
  Thinking of an ordered list of stripped labels as a product of transpositions gives a bijection $\mathrm{Play}(\mathbf{\ell})\simeq \mathrm{Red}(\mathbf{\ell})$.
	\label{thm:main}
\end{proposition}
\begin{proof}
	We describe the bijection from $\mathrm{Play}(\mathbf{\ell})$ to $\mathrm{Red}(\mathbf{\ell})$ geometrically, using the visualizations of both sets as in~\Cref{fig:game,fig:fact}.
	
	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 {\it 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~\Cref{fig:bij}).  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~\Cref{thm:gouldenyong} 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~\Cref{thm:gouldenyong}. 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.
\end{proof}

The bijection of~\Cref{thm:main} is illustrated in~\Cref{fig:bij}.

\begin{figure}[htbp]
	\begin{center}
		\raisebox{-0.5\height}{\includegraphics[width=.19\linewidth]{bijj1.eps} \includegraphics[width=.19\linewidth]{bij2a.eps} \includegraphics[width=.19\linewidth]{bij3a.eps}	\includegraphics[width=.19\linewidth]{bijj4a.eps}	\includegraphics[width=.19\linewidth]{bijj6.eps}}

\raisebox{-0.5\height}{  	\includegraphics[width=.19\linewidth]{bijj6.eps}
	\includegraphics[width=.19\linewidth]{bijback2.eps}
\includegraphics[width=.19\linewidth]{bijback3.eps}
\includegraphics[width=.19\linewidth]{bijback4.eps}
\includegraphics[width=.19\linewidth]{bijback5.eps}
}
\end{center}
\caption{An illustration of~\Cref{thm:main} (compare with~\Cref{fig:game}).  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.}
\label{fig:bij}
\end{figure}

\section{Corollaries}

\begin{corollary}[{\cite[Theorem 1]{JiPropp}}]
There is a bijection from $\mathrm{Play}(\mathbf{\ell})$ to labelled trees on $n+1$ vertices.
\end{corollary}
\begin{proof}
	A bijection between factorizations and labelled trees is given in~\cite{goulden2002tree}.
\end{proof}


\begin{corollary}[{\cite[Theorem 4]{JiPropp}}]
	\label{cor:park}
	There is a bijection from $\mathrm{Play}(\mathbf{\ell})$ to parking functions of length $n$.
\end{corollary}
\begin{proof}
	A bijection from factorizations to parking functions is given in~\cite{stanley1997parking}.  The bijection is given by sending a factorization $(i_1,j_1) \cdots (i_n,j_n)$ with $i_k<j_k$ to the word $i_1 \cdots i_n$.
\end{proof}


\begin{corollary}[{\cite[Theorem 2]{JiPropp}}]
	\label{cor:commute}
	 Ignoring the order arcs are drawn, there are $\frac{1}{2n+1}\binom{3n}{n}$ (\seqnum{A001764}) possible games of Planted Brussels Sprouts on $n+1$ vertices.
\end{corollary}
\begin{proof}
	The proof of~\Cref{thm:main} 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~\cite{eidswick1989short}.  See~\Cref{fig:commutation} for an example.
	
The unlabelled visualizations of the factorizations are known in the literature as {\it noncrossing trees}~\cite{deutsch2002diagonally,deutsch2002statistics,noy1998enumeration,panholzer2002bijections}.  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}$.
\end{proof}

\begin{figure}[htbp]	\begin{center}\raisebox{-0.5\height}{\includegraphics[width=.24\linewidth]{com1.eps} \includegraphics[width=.24\linewidth]{fact2.eps}  \includegraphics[width=.24\linewidth]{com2.eps} \includegraphics[width=.24\linewidth]{com3.eps}}\end{center}
\caption{Ignoring the labels in a visualization of a factorization of the long cycle gives factorizations \emph{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)$.}
\label{fig:commutation}
\end{figure}


\section{Factorizations of Coxeter elements}
\label{sec:history}
The symmetric group $\mathfrak{S}_{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  $\mathfrak{S}_{n+1}$ has a presentation using the $n$ simple transpositions $\{(i,i+1)\}_{1 \leq i \leq n}$, a Coxeter group $W$ has a presentation using an $n$ element set $S$ called simple reflections.  Similarly, a long cycle $\ell \in \mathfrak{S}_{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$).

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 $\mathrm{Red}(c)$ of factorizations of the Coxeter element $c$ into reflections~\cite{deligne1974letter}, which allows for a simple case-by-case proof of the uniform formula \begin{equation}\left|\mathrm{Red}(c)\right| = \frac{n!h^n}{|W|}.\label{eq:fact}\end{equation}  The same recurrence was independently rediscovered and refined by Reading in 2007~\cite{reading2008chains}, by analogy to methods he developed to model finite-type cluster algebras using sortable elements.  In the case of the symmetric group $\mathfrak{S}_{n+1}$, the recurrence is exactly~\Cref{eq:rec}.

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~\Cref{eq:fact} to all well-generated complex reflection groups in 2012~\cite{chapuy2014counting}.   Chapuy and Stump's work inspired Michel in 2014 to give the first \emph{uniform} proof of~\Cref{eq:fact} for Weyl groups using properties of Deligne-Lusztig representations~\cite{michel2014case}. 

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

\section{Centrally symmetric Brussels Sprouts}
As an illustration of the generality suggested by~\Cref{sec:history}, we give a brief account of the centrally symmetric version of Planted Brussels Sprouts.

\subsection{Centrally symmetric Brussels Sprouts}
The game is now played in a disk whose boundary is marked with $2n\geq 2$ distinct points labelled clockwise $(\ell_1,\ldots,\ell_n,\overline{\ell}_1,\ldots,\overline{\ell}_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~\Cref{fig:typebgame} for an example.

Again, the game is uniquely determined by its sequence of stripped labels---we abbreviate the central symmetry by writing $(\!(\ell_i,\ell_j)\!)$ for the pair $(\ell_i,\ell_j)(\overline{\ell}_i,\overline{\ell}_j)$, and $(\!(\ell_i,\overline{\ell}_j)\!)$ for the pair $(\ell_i,\overline{\ell}_j)(\overline{\ell}_i,\ell_j)$.  We write $\mathrm{Play}_B(\ell)$ for the set of all such sequences.


\begin{figure}[htbp]
	\begin{center}
\includegraphics[height=1.3in]{bgame1.eps}\includegraphics[height=1.3in]{bgame2.eps}\includegraphics[height=1.3in]{bgame3.eps}\includegraphics[height=1.3in]{bgame4.eps}
\end{center}
\caption{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})$.}
\label{fig:typebgame}
\end{figure}

\subsection{Factorizations of a Coxeter element}
\label{sec:typebfact}
The Coxeter group of type $B_n$ (which we shall simply denote as $B_n$) has a permutation representation on the set $\{1,2,\ldots,n,\overline{1},\overline{2},\ldots,\overline{n}\}$.  In this representation (continuing the notation from the previous section), the reflections of the group are \[T = \left\{(\!(i j)\!) : 1 \leq i < j \leq n \right\} \sqcup \left\{(\!(i \overline{j})\!) : 1 \leq i < j \leq n \right\} \sqcup \left\{(i \overline{i}) : 1 \leq i \leq n \right\}.\]  A type $B_n$ reduced factorization of the cycle $(\ell_1,\ldots,\ell_n,\overline{\ell}_1,\ldots,\overline{\ell}_n)$ is an expression for that element as a product of $n$ reflections.  We write $\mathrm{Red}_B(\ell)$ 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~\Cref{fig:typebfact}.


\begin{figure}[htbp]
	\begin{center}
		\includegraphics[height=1.5in]{typebfact.eps}
	\end{center}
\caption{Visualizing the factorization $(123\overline{123})=(\!(12)\!)(\!(2\overline{3})\!)(2\overline{2})$.}
\label{fig:typebfact}
\end{figure}

\subsection{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 its centrally symmetric move).  Similarly, there is an embedding of $B_n \hookrightarrow \mathfrak{S}_{2n}$ that sends $\overline{i} \mapsto n+i$.  By mapping the reflections of $B_n$ to the corresponding reflections or pairs of reflections in $\mathfrak{S}_{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 $\mathfrak{S}_{2n}$ (in which a transposition is immediately followed by its centrally symmetric transposition).

Let $\ell=(\ell_1,\ldots,\ell_n,\overline{\ell}_1,\ldots,\overline{\ell}_n)$.  Since we have the embeddings $\mathrm{Play}_B(\ell) \hookrightarrow \mathrm{Play}(\ell)$ and $\mathrm{Red}_B(\ell) \hookrightarrow \mathrm{Red}(\ell)$ as centrally symmetric subsets, and since the bijection from~\Cref{thm:main} between $\mathrm{Play}(\ell)$ and $\mathrm{Red}(\ell)$ preserves this symmetry, \Cref{thm:main} restricts to a bijection between $\mathrm{Play}_B(\ell)$ and $\mathrm{Red}_B(\ell)$.

\begin{corollary}
	Thinking of an ordered list of stripped labels as a product of reflections gives a bijection $\mathrm{Play}_B(\ell) \simeq \mathrm{Red}_B(\ell)$.
\end{corollary}

We now obtain the analogues of~\Cref{prop:count} and~\Cref{cor:park,cor:commute}.

\begin{proposition}[{\cite{deligne1974letter,reading2008chains}}]  For $n\geq 1$, $|\mathrm{Play}_B(\ell)| = n^n$ (\seqnum{A000312}).
\end{proposition}

\begin{proof}
	Let $\mathcal{R}_n^B = |\mathrm{Play}_B(\ell)|$.  As in~\Cref{prop:count}, we could write down a recurrence for $\mathcal{R}_n^B$; we prefer to give an elegant direct proof that $\mathcal{R}_n^B = n^2 \cdot \mathcal{R}_{n}$ (see, for example,~\cite{obaid2013number}).
	
	It is clear from the geometric interpretation given in~\Cref{sec:typebfact} that in any factorization of the cycle $(\ell_1,\ldots,\ell_n,\overline{\ell}_1,\ldots,\overline{\ell}_n)=t_1 \cdots t_n$, there is exactly one reflection of the form $(a \overline{a})$ for $1 \leq a \leq n$: two such arcs would cross, and a graph with only arcs of the form $(\!(a b)\!)$ and $(\!(a \overline{b})\!)$ couldn't be a tree.
	    
Recall that there is a braid group action on $\mathrm{Red}(\mathbf{\ell})$---a generator $\mathbf{s}_i$ of the braid group $\mathrm{Braid}_{n-1}$ acts on a factorization by
\begin{equation}\mathbf{s}_k\left( t_1 \cdots t_k t_{k+1} \cdots  t_n\right) = t_1 \cdots t_{k+1}^{t_k} t_k \cdots  t_n \label{eq:hurw}\end{equation} where $x^y = xyx^{-1}$.  The action of a generator is often called a {\it Hurwitz move}.  It is easy to check that they satisfy the braid group relations (that is, $\mathbf{s}_i \mathbf{s}_{i+1} \mathbf{s}_i = \mathbf{s}_{i+1} \mathbf{s}_i \mathbf{s}_{i+1}$):
\begin{align*}
	\mathbf{s}_i \mathbf{s}_{i+1} \mathbf{s}_i \left( t_1 \cdots t_i t_{i+1} t_{i+2} \cdots  t_n\right) &= \mathbf{s}_i \mathbf{s}_{i+1} \left( t_1 \cdots t_{i+1}^{t_i} t_i t_{i+2} \cdots  t_n\right) \\ &= \mathbf{s}_i \left( t_1 \cdots t_{i+1}^{t_i} t_{i+2}^{t_i} t_i \cdots t_n\right)\\ &= t_1 \cdots t_{i+2}^{t_i t_{i+1}} t_{i+1}^{t_i} t_i \cdots t_n
\end{align*} 
while also
\begin{align*}
	\mathbf{s}_{i+1} \mathbf{s}_{i} \mathbf{s}_{i+1} \left( t_1 \cdots t_i t_{i+1} t_{i+2} \cdots  t_n\right) &= \mathbf{s}_{i+1} \mathbf{s}_{i} \left( t_1 \cdots t_i t_{i+2}^{t_{i+1}} t_{i+1} \cdots  t_n\right) \\ &= \mathbf{s}_{i+1} \left( t_1 \cdots  t_{i+2}^{t_it_{i+1}} t_i t_{i+1} \cdots t_n\right)\\ &= t_1 \cdots t_{i+2}^{t_i t_{i+1}} t_{i+1}^{t_i} t_i \cdots t_n.
\end{align*} 
Since each Hurwitz move is invertible, the action of $\mathrm{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 $\mathcal{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 \leq a \leq 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 $\mathcal{R}_{n-1}$.  Hence, \[\mathcal{R}_n^B = n^2 \cdot \mathcal{R}_{n}= n^2 n^{n-2} = n^n.\]
\end{proof}

\begin{corollary}[{\cite[Theorem 3.2]{biane2002parking}}] There is a bijection from $\mathrm{Play}_B(\ell)$ to words on $\{1,2,\ldots,n\}$ of length $n$.
\end{corollary}

\begin{proof}
As explained in~\cite{biane2002parking}, the bijection is given by
sending a factorization $t_1 \cdots t_n$ to the word $w_1 \cdots w_n$
where \[w_k = 
\begin{cases}
i, & \text{ if } t_k = (\!(ij)\!) \text{ with }
1 \leq i < j \leq n; \\ 
j, & \text{ if } t_k = (\!(i\overline{j})\!) \text{
with } 1 \leq i < j \leq n; \\ 
i, & \text{ if } t_k = (i \overline{i}) .
\end{cases}
\]
\end{proof}

\begin{corollary}[{\cite[Theorem 1]{guo2011cyclic}}] Ignoring the order arcs are drawn, there are $\binom{3n-2}{n-1}$ (\seqnum{A045721}) possible games of centrally symmetric Planted Brussels Sprouts on $2n$ vertices.
\end{corollary}

\begin{proof}
We learned of this formula (without proof) from~\cite{chapoton}.  A proof can be given as follows.
	
As in~\Cref{cor:commute}, 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~\cite{guo2011cyclic} that the number of noncrossing graphs with $m$ vertices and $k$ edges fixed under rotation by $\frac{2\pi}{d}$ for any divisor $d$ of $m$ satisfies a cyclic sieving phenomenon with respect to the polynomial \[\frac{1}{[m-1]_q} \left[\!\begin{array}{c} 3m-3 \\ m+k \end{array}\!\right]_q \left[\!\begin{array}{c} k-1 \\ m-2 \end{array}\!\right]_q\] (see~\cite{reiner2004cyclic} 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}} \left[\!\begin{array}{c} 6n-3 \\ 4n-1 \end{array}\!\right]_q \Bigg|_{q=-1}.\]
\end{proof}


\begin{thebibliography}{10}

\bibitem{biane2002parking}
P.~Biane, {Parking functions of types $A$ and $B$}, {\em Electronic J. 
  Combinatorics} {\bf 9}(1) (2002), 
  \href{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v9i1n7}{Note \#N7}.

\bibitem{chapoton}
F.~Chapoton, Les alg\`ebres amass\'ees, preprint, 2018.  Available at
  \url{http://irma.math.unistra.fr/~chapoton/clusters.html}.

\bibitem{chapuy2014counting}
G.~Chapuy and C.~Stump, Counting factorizations of {C}oxeter elements into
  products of reflections, {\em J. London Math. Soc.}
  {\bf 90} (2014), 919--939.

\bibitem{deligne1974letter}
P.~Deligne, Letter to {E}. {L}ooijenga, 1974.

\bibitem{deutsch2002diagonally}
E.~Deutsch, S.~Fereti{\'c}, and M.~Noy, Diagonally convex directed polyominoes
  and even trees: a bijection and related issues, {\em Discrete Math.}
  {\bf 256} (2002), 645--654.

\bibitem{deutsch2002statistics}
E.~Deutsch and M.~Noy, Statistics on non-crossing trees, {\em Discrete
  Math.} {\bf 254} (2002), 75--87.

\bibitem{eidswick1989short}
J.~Eidswick, Short factorizations of permutations into transpositions, {\em
  Discrete Math.} {\bf 73} (1989), 239--243.

\bibitem{goulden2002tree}
I.~Goulden and A.~Yong, Tree-like properties of cycle factorizations, {\em
  J. Combin. Theory, Ser. A} {\bf 98} (2002), 106--117.

\bibitem{guo2011cyclic}
A.~Guo, Cyclic sieving phenomenon in non-crossing connected graphs, {\em 
  Electronic J. Combin.} {\bf 18}(1) (2011), \href{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p9}{Paper P9}.  

\bibitem{JiPropp}
C.~{Ji} and J.~{Propp}, Brussels sprouts, noncrossing trees, and parking
functions, preprint, May 2018.  Available at 
\url{https://arxiv.org/abs/1805.03608}.

\bibitem{michel2014case}
J.~Michel, ``{C}ase-free'' derivation for {W}eyl groups of the number of
  reflection factorisations of a {C}oxeter element, preprint, 2014.
  Available at \url{https://arxiv.org/abs/1408.0721}.

\bibitem{noy1998enumeration}
M.~Noy, Enumeration of noncrossing trees on a circle, {\em Discrete
  Math.} {\bf 180} (1998), 301--313.

\bibitem{obaid2013number}
M.~Obaid, K.~Nauman, W.~Al-Shammakh, W.~Fakieh, and C.~Ringel, The number of
complete exceptional sequences for a {D}ynkin algebra, In {\em Colloquium
Mathematicae}, Vol.~133,
Institute of Mathematics, Polish Academy of Sciences, 2013, pp.~197--210. 

\bibitem{panholzer2002bijections}
A.~Panholzer and H.~Prodinger, Bijections for ternary trees and non-crossing
  trees, {\em Discrete Math.} {\bf 250} (2002), 181--195.

\bibitem{reading2008chains}
N.~Reading, Chains in the noncrossing partition lattice, {\em SIAM J. 
  Discrete Math.} {\bf 22} (2008), 875--886.

\bibitem{reiner2004cyclic}
V.~Reiner, D.~Stanton, and D.~White, The cyclic sieving phenomenon, {\em
  J. Combin. Theory, Ser. A} {\bf 108} (2004), 17--50.

\bibitem{stanley1997parking}
R.~P. Stanley, Parking functions and noncrossing partitions, {\em Electron. J.
  Combin.} {\bf 4}(2) (1997), 
  \href{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v4i2r20}{Paper \#R20}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 20F55.

\noindent \emph{Keywords: } 
Planted Brussels Sprouts, reflection factorization, Coxeter element,
Coxeter group.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 11 2018;
revised versions received May 24 2018; August 31 2018; September 1 2018.
Published in {\it Journal of Integer Sequences}, November 25 2018.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}