\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}
\OneNumberAllTheorems
%\usepackage{amsrefs}
\usepackage{tikz,pgf}
\pgfdeclarelayer{background}
\pgfsetlayers{background,main}
\usepackage{multirow}
\usepackage{scalerel,stackengine}
%\begin{DefTralics}
%\makeatletter
%\@ifundefined{amsrefs@xmlbibcite}{}{\let\bibcite\amsrefs@bibcite}
%\makeatother
%\xmlbibcite{adin14maximal}{{1}{}}
%\xmlbibcite{armstrong09generalized}{{2}{}}
%\xmlbibcite{athanasiadis08absolute}{{3}{}}
%\xmlbibcite{athanasiadis14absolute}{{4}{}}
%\xmlbibcite{baumeister17on}{{5}{}}
%\xmlbibcite{benitzhak03graph}{{6}{}}
%\xmlbibcite{bessis03dual}{{7}{}}
%\xmlbibcite{bessis15finite}{{8}{}}
%\xmlbibcite{biane96minimal}{{9}{}}
%\xmlbibcite{biane97some}{{10}{}}
%\xmlbibcite{bjorner80shellable}{{11}{}}
%\xmlbibcite{brady01partial}{{12}{}}
%\xmlbibcite{brenti08alternating}{{13}{}}
%\xmlbibcite{deligne74letter}{{14}{}}
%\xmlbibcite{deutsch02diagonally}{{15}{}}
%\xmlbibcite{garside69braid}{{16}{}}
%\xmlbibcite{gould56some}{{17}{}}
%\xmlbibcite{goulden92combinatorial}{{18}{}}
%\xmlbibcite{goulden00transitive}{{19}{}}
%\xmlbibcite{graham94concrete}{{20}{}}
%\xmlbibcite{heller18generalized}{{21}{}}
%\xmlbibcite{herzog76representation}{{22}{}}
%\xmlbibcite{hou08hurwitz}{{23}{}}
%\xmlbibcite{huang17absolute}{{24}{}}
%\xmlbibcite{hurwitz91ueber}{{25}{}}
%\xmlbibcite{krattenthaler10decomposition}{{26}{}}
%\xmlbibcite{kreweras72sur}{{27}{}}
%\xmlbibcite{lando04graphs}{{28}{}}
%\xmlbibcite{mitsuhashi01the}{{29}{}}
%\xmlbibcite{muehle19kindivisible}{{30}{}}
%\xmlbibcite{muehle17connectivity}{{31}{}}
%\xmlbibcite{regev04permutation}{{32}{}}
%\xmlbibcite{rotbart11generator}{{33}{}}
%\xmlbibcite{sia09hurwitz}{{34}{}}
%\xmlbibcite{simion00noncrossing}{{35}{}}
%\xmlbibcite{sloane}{{36}{}}
%\xmlbibcite{stanley01enumerative_vol2}{{37}{}}
%\xmlbibcite{stanley11enumerative_vol1}{{38}{}}
%\xmlbibcite{wegener17on}{{39}{}}
%\end{DefTralics}
\definecolor{Darkgreen}{rgb}{0.09,0.45,0.27}
\newcommand{\defn}[1]{{\color{Darkgreen}{\emph{#1}}}}
\DeclareMathOperator{\red}{Red}
\DeclareMathOperator{\oc}{ocyc}
\DeclareMathOperator{\cyc}{cyc}
\DeclareMathOperator{\Cay}{Cay}
%\newcommand{\Cay}{\operatorname{Cay}}
%\newcommand{\oc}{\operatorname{ocyc}}
%\newcommand{\cyc}{\operatorname{cyc}}
\newcommand{\st}{^{\text{st}}}
\newcommand{\Sym}{\mathfrak{S}}
\newcommand{\Alt}{\mathfrak{A}}
\newcommand{\Braid}{\mathfrak{B}}
\newcommand{\Alto}{\mathfrak{A}^{o}}
\newcommand{\nc}{N\!C}
\newcommand{\pnc}{\mathcal{N\!C}}
\newcommand{\enc}{O\!N\!C}
\newcommand{\penc}{\mathcal{O\!N\!C}}
\newcommand{\rk}{\operatorname{rk}}
\newcommand{\id}{e}
\newcommand{\Poset}{\mathcal{P}}
\newcommand{\Int}{\mathcal{I}}
\newcommand{\MaxChains}{\mathcal{M}}
\newcommand{\Rank}{\mathcal{R}}
\newcommand{\ZetaPol}{\mathcal{Z}}
\newcommand{\ww}{\mathbf{w}}
\newcommand{\xx}{\mathbf{x}}
\newcommand{\yy}{\mathbf{y}}
\newcommand{\zz}{\mathbf{z}}
\newcommand{\btw}{\mathbf{2}}
\newcommand{\bth}{\mathbf{3}}
%%Really wide hats
\stackMath
\newcommand\reallywidehat[1]{%
\savestack{\tmpbox}{\stretchto{%
\scaleto{%
\scalerel*[\widthof{\ensuremath{#1}}]{\kern-.6pt\bigwedge\kern-.6pt}%
{\rule[-\textheight/2]{1ex}{\textheight}}%WIDTH-LIMITED BIG WEDGE
}{\textheight}%
}{0.5ex}}%
\stackon[1pt]{#1}{\tmpbox}%
}
\newcommand{\la}{\ell_{\bth}}
\newcommand{\lt}{\ell_{\btw}}
\newcommand{\leqa}{\leq_{\bth}}
\newcommand{\leqt}{\leq_{\btw}}
\newcommand{\seq}{\mathbf{s}}
\newcommand{\Gen}{\mathcal{T}}
\newcommand{\GJbij}{\Phi}
%%
%%%%%%%%% a placer avant \begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
\author{\firstname{Henri} \lastname{M\"uhle}}
\address{Technische Universit{\"a}t Dresden\\
Institut f{\"u}r Algebra\\
Zellescher Weg 12--14\\
01069 Dresden\\
Germany.}
\email{henri.muehle@tu-dresden.de}
%%%%%%%%%%%%%%%%
\author{\firstname{Philippe} \lastname{Nadeau}}
\address{Univ. Lyon\\
CNRS\\
Université Claude Bernard Lyon 1\\
UMR5208\\
Institut Camille Jordan\\
F-69622 Villeurbanne\\
France.}
\email{nadeau@math.univ-lyon1.fr}
%%%%% Sujet
\keywords{Symmetric group, Alternating group, Noncrossing partitions, Hurwitz action, zeta polynomial}
\subjclass{06A07, 05A10, 05E15, 20B35}
%%%%% Gestion
%\DOI{10.5802/alco.83}
%\datereceived{2018-04-01}
%\daterevised{2019-01-21}
%\dateaccepted{2019-04-29}
%%%%% Titre et résumé
\title[The alternating group generated by 3-cycles]{A poset structure on the alternating group generated by 3-cycles}
\begin{abstract}
We investigate the poset structure on the alternating group that arises when the latter is generated by $3$-cycles. We study intervals in this poset and give several enumerative results, as well as a complete description of the orbits of the Hurwitz action on maximal chains. Our motivating example is the well-studied absolute order arising when the symmetric group is generated by transpositions, i.e. $2$-cycles, and we compare our results to this case along the way. In particular, noncrossing partitions arise naturally in both settings.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:introduction}
%%%%%%%%%%%%%%%%%%%%%%
Given a group $G$ generated by a finite set $\Gen$, the \defn{(right) Cayley graph} $\Cay(G,\Gen)$ is perhaps one of the most fundamental geometric objects attached to it. Recall that the vertex set of $\Cay(G,\Gen)$ is $G$, and that its edges are of the form $(g,gt)$ for $g\in G,t\in\Gen$. It comes with a natural graph distance which can be written as $d_{\Cay}(g,g')=\ell_{\Gen}(g^{-1}g')$. Here the \defn{length} $\ell_{\Gen}(g)$ is the minimum $k$ such that there exists a factorization $g=t_1t_2\cdots t_k$ where each $t_i$ is in $\Gen$. Such factorizations are \defn{$\Gen$-reduced} and $\red_{\Gen}(g)$ denotes the set of all $\Gen$-reduced factorizations of $g$.
The relation defined by $u\leq_{\Gen}v$ if and only if $\ell_{\Gen}(v)=\ell_{\Gen}(u)+\ell_{\Gen}(u^{-1}v)$ is a partial order on $G$, graded by $\ell_\Gen$. $\red_{\Gen}(g)$ is naturally identified with the set of maximal chains from $\id$ to $g$ in this poset. Geometrically, $u\leq_{\Gen}v$ holds if and only if $u$ occurs on a geodesic from the identity $\id$ to $v$ in $\Cay(G,\Gen)$.
If we require furthermore that $\Gen$ is closed under $G$-conjugation, then we can define a natural action of the braid group on $\ell_{\Gen}(g)$ strands on the set $\red_{\Gen}(g)$; the \defn{Hurwitz action}. Informally, this action can be described as follows: the $i\text{th}$ generator of the braid group shifts the $(i+1)\st$ letter of an element in $\red_{\Gen}(g)$ one step to the left, and conjugates as it goes. The Hurwitz action on closed intervals in $(G,\leq_{\Gen})$ was recently studied in \cite{muehle17connectivity}. For specific groups, the Hurwitz action was studied for instance in \cite{baumeister17on,benitzhak03graph,bessis15finite,deligne74letter,hou08hurwitz,sia09hurwitz,wegener17on}.
%\medskip
A well-studied example of this construction is the case where $G=\Sym_{N}$ is the symmetric group of all permutations of $[N]=\{1,2,\ldots,N\}$, and $\Gen$ is the set of all transpositions. Whenever we refer to this case we replace the subscript ``$\Gen$'' by ``$\btw$'' in all of the above definitions. It is a standard fact that $\lt(x)=N-\text{cyc}(x)$, where $\text{cyc}(x)$ denotes the number of cycles of $x$. The poset $(\Sym_{N},\leqt)$ was for instance studied in \cite{athanasiadis08absolute}. Moreover, it was observed in \cite{biane97some} that the \defn{lattice of noncrossing partitions} arises as the principal order ideal $\pnc_{N}=[e,c]_{\btw}$ where $c$ is the $N$-cycle $c=(1\;2\;\ldots\;N)$. See \cite{simion00noncrossing} for a survey on this lattice, and \cite{kreweras72sur} for some enumerative and structural properties.
It was in fact in this setting that the Hurwitz action was first considered~\cite{hurwitz91ueber}. One of the crucial properties, namely that for any $x\in\Sym_{N}$ the
action is transitive on $\red_{\btw}(x)$, is motivated by the enumeration of branched covers of the Riemann sphere with $N$ given branch points.
%\medskip
In this article, we set out to study the poset $(G,\leq_{\Gen})$ in the case where $G=\Alt_{N}$ is the alternating group and $\Gen$ is the set of all $3$-cycles. In that case we replace the subscript ``$\Gen$'' by ``$\bth$''. Note that several articles have been written about ordering the elements of $\Alt_{N}$ with respect to certain generating sets, mostly for the purpose of equipping $\Alt_{N}$ with a ``Coxeter-like'' structure; see~\cite{athanasiadis14absolute,brenti08alternating,mitsuhashi01the,regev04permutation,rotbart11generator}. However, none of these orders fits into the framework described in the first paragraph of this section.
We will show that the poset $(\Alt_{N},\la)$ has a rich combinatorial structure, which can be compared to the structure of $(\Sym_{N},\lt)$ mentioned before. Our first main combinatorial result computes the \defn{zeta polynomial} of the closed interval $[\id,c]_{\bth}$ in $(\Alt_{N},\leqa)$, where $c=(1\;2\;\ldots\;N)$ is a long cycle for $N$ odd. The evaluation of the zeta polynomial at an integer $q$ yields the number of multichains of length $q-1$ in $[\id,c]_{\bth}$.
\begin{theo}\label{thm:main_zeta_polynomial}
Let $N=2n+1$ be an odd positive integer, and let $c=(1\;2\;\ldots\;N)\in\Alt_{N}$. The zeta polynomial of the interval $[\id,c]_{\bth}$ of $(\Alt_{N},\leqa)$ is given by
\begin{displaymath}
\ZetaPol(q) = \frac{q}{q(2n+1)-n}\binom{q(2n+1)-n}{n}.
\end{displaymath}
\end{theo}
We note that the zeta polynomial of $[\id,c]_{\btw}$ in $(\Sym_{N},\lt)$, where $c=(1\;2\;\ldots\;N)$ for any $N$ has a well-known formula \cite[Theorem 5]{kreweras72sur} comparable to ours.
We further show that the Hurwitz action is no longer transitive on $\red_{\bth}(x)$ for all $x\in\Alt_{N}$. Our second main result computes the number of orbits depending on the number of even-length cycles of $x$.
\begin{theo}\label{thm:main_hurwitz_orbits}
Let $x\in\Alt_{N}$ for $N\geq 3$, and write $2k$ for its number of cycles of even length. The Hurwitz action on $\red_{\bth}(x)$ has $(2k)_{k}=(k+1)(k+2)\cdots(2k)$ orbits.
\end{theo}
We see in particular that the Hurwitz action is transitive on $\red_{\bth}(x)$ if and only if $x$ has only cycles of odd length.
%\medskip
This article is organized as follows. In Section~\ref{sec:preliminaries} we recall the necessary definitions and concepts. In Section~\ref{sec:alternating} we recall the definition of the alternating group and prove some basic properties of the poset $(\Alt_{N},\leqa)$. Subsequently, in Section~\ref{sec:alternating_noncrossing} we recall the definition of noncrossing partitions, and exhibit a subset of $\Alt_{N}$ whose combinatorial properties can be described with certain noncrossing partitions. We prove Theorem~\ref{thm:main_zeta_polynomial} in Section~\ref{sec:alternating_combinatorics}, and establish further combinatorial results of certain intervals of ${(\Alt_{N},\leqa)}$. In Section~\ref{sec:hurwitz} we prove Theorem~\ref{thm:main_hurwitz_orbits}, and we finish this article with Section~\ref{sec:extensions}, where we outline potential extensions of the work presented here.
%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries}
\label{sec:preliminaries}
%%%%%%%%%%%%%%%%%%%%%%
\subsection{Poset Terminology}
\label{sec:posets}
Let $\Poset=(P,\leq)$ be a partially ordered set, or \defn{poset} for short. If $x < y$ in $\Poset$ and there exist no $z\in P$ such that $x1\;\text{and}\\
& \;\sigma_{i}\sigma_{i+1}\sigma_{i}=\sigma_{i+1}\sigma_{i}\sigma_{i+1}\;\text{for}\;1\leq i0$, then there exists $y\in \enc_{2n+1}$ with $x\lessdot_{\bth} y \leqa c$, so $f(y)=f(x)-1$ and we can assume by induction that the cycles of $y$ satisfy \eqref{it:od}. By Proposition~\ref{prop:AAo_first_properties}, $x$ is obtained from $y$ by splitting an odd cycle $(u_{1}k+1$, then we need to show that $u_l-u_k$ is odd, which is equivalent to $l-k$ being odd. This is indeed the case since the two other cycles are odd and thus the set $\{u_{k+1},u_{k+2},\ldots,u_{l-1}\}$ has even cardinality.
% \smallskip
Conversely, assume that $x\in\nc_{2n+1}$ and its cycles satisfy \eqref{it:od}. If $x=c$ we are done. We now assume $x\neq c$. We will construct $y\in \Alt_{N}$ such that $x\lessdot_{\bth} y\leqt c$ and all cycles of $y$ satisfy \eqref{it:od}. Then $x\leqa c$ by induction on $f(x)$ as above.
Consider the cycle $\zeta_1=(u_11$. Let $\zeta_2$ be the cycle containing $u_t+1$, say $(v_1j$, and \eqref{it:p} implies that $x(j)-j$ is odd which is equivalent to $i-x'(i)$ being even as desired. If $i=2k+1$, then we have $x'(i)=x^{-1}(1)$, and $2k+1-x^{-1}(1)$ is even if and only if $x^{-1}(1)$ is odd. This is clearly satisfied if $x^{-1}(1)=1$. Otherwise, if $x^{-1}(1)>1$, then \eqref{it:p} applied to $x$ and $x^{-1}(1)$ yields that $x^{-1}(1)-1$ is even as desired.
We have thus shown the claim for $y=c_k$. If $y$ is a cycle $\zeta=(a_1\;a_2\;\ldots\;a_{2k+1})$ satisfying \eqref{it:od}, then by Proposition~\ref{prop:invariant_conjugation} the posets $[\id,y]_{\bth}$ and $(1\;2\;\ldots\;2k+1)$ are isomorphic via conjugation by $w\in\Sym_{2n+1}$ satisfying $w(i)=a_i$. Since $a_i-a_j$ has the same parity as $i-j$, the property \eqref{it:od} is preserved by this conjugation, and we can conclude the claim for $y=\zeta$ since $K_{c_k}=wK_\zeta w^{-1}$.
In the general case, one has a poset isomorphism $[\id,y]_{\bth}\cong [\id,\zeta_1]_{\bth}\times[\id,\zeta_{2}]_{\bth}\cdots\times [\id,\zeta_k]_{\bth}$ where the $\zeta_i$ are the odd cycles of $y$, thanks to Proposition~\ref{prop:interval_decomposition}, and each $\zeta_i$ satisfies \eqref{it:od} because $y$ does. This isomorphism sends $K_y$ to the product of the $K_{\zeta_i}$, and obviously $x\leqa y$ satisfies \eqref{it:od} if and only if each $x_i$ in its image $(x_1,x_2,\ldots,x_k)$ satisfies \eqref{it:od}, which concludes the proof.
\end{proof}
\begin{theo}\label{thm:enc_subposet}
For $N\geq 3$ the poset $\penc_{N}$ is an induced subposet of $\pnc_{N}$.
\end{theo}
\begin{proof}
We know that $\penc_{N}$ is a subposet of $\pnc_{N}$ by Proposition~\ref{prop:AAo_subposet}. Now let $x,y\in\enc_{N}$ with $x\leqt y$. By Proposition~\ref{prop:kreweras_invariance}, $K_y(x)=x^{-1}y$ is in $\enc_{N}\subset \Alto_{N}$, so we can use the relation between $\lt$ and $\la$ in Proposition~\ref{prop:AAo_first_properties} to deduce that $x\leqa y$, which concludes the proof.
\end{proof}
Now we can conclude the proof of Theorem~\ref{thm:AAo_embedding}.
\begin{proof}[Proof of Theorem~\ref{thm:AAo_embedding}]
Recall that any $y\in\Alto_{N}$ is $\Sym_{N}$-conjugate to some $x\in\enc_{N}$. Therefore, we can find $w\in\Sym_{N}$ with $y=w^{-1}xw$. Proposition~\ref{prop:invariant_conjugation} states that the posets $[\id,x]_{\bth}$ and $[\id,y]_{\bth}$ are isomorphic, and so are $[\id,x]_{\btw}$ and $[\id,y]_{\btw}$. Now Theorem~\ref{thm:enc_subposet} states that $[\id,x]_{\bth}$ is an induced subposet of $[\id,x]_{\btw}$, and this property is certainly preserved under the above isomorphism.
\end{proof}
\section{Enumerative Results}
\label{sec:alternating_combinatorics}
In this section we collect a few enumerative properties of the poset $(\Alt_{N},\leqa)$.
\subsection{The Rank Generating Function of \texorpdfstring{$(\mathfrak{A}_N, \ell_{\mathbf{3}})$}{(A N, l 3)}}
Let $F_N(q)=\sum_{x\in \Alt_N}q^{\oc(x)}$ be the polynomial enumerating $\Alt_{N}$ with respect to $\oc$. Then Proposition~\ref{prop:alternating_length} states that $q^{N/2}F_N(q^{-1/2})$ is the polynomial enumerating $\Alt_{N}$ with respect to $\la$.
\begin{prop}\label{prop:rankenumeration}
The generating function $F(t,q)=\displaystyle\sum_{N\geq 0}F_N(q)\frac{t^N}{N!}$ is given by
\begin{align}
F(t,q) & = \frac{1}{2}\left(\frac{1+t}{1-t}\right)^{q/2}\left(\vphantom{\frac{t+1}{t-1}}(1-t^2)^{-1/2}+(1-t^2)^{1/2}\right) \label{eq11}\\
& = \frac{1}{2}\left(\vphantom{\frac{t+1}{t-1}}(1+t)^{\frac{q-1}{2}}(1-t)^{-\frac{q+1}{2}}+ (1+t)^{\frac{q+1}{2}}(1-t)^{-\frac{q-1}{2}}\right).\label{eq12}
\end{align}
\end{prop}
\begin{proof}
We need to count collections of cycles with an even number of even cycles, with $q$ marking the number of odd cycles. Recall that the series enumerating cycles is $-\log(1-t)$, so that, by taking its odd and even part, the series for odd cycles is $1/2\log\bigl((1+t)/(1-t)\bigr)$ while the series for even cycles is $-1/2\log(1-t^2)$. By the exponential formula~\cite[Chapter~5]{stanley01enumerative_vol2}, using $q$ to mark odd cycles and $\bigl(\exp(x)+\exp(-x)\bigr)/2$ to ensure an even number of even cycles, we get
\begin{displaymath}
F(t,q) = \exp\left(\frac{q}{2}\log\left(\frac{1+t}{1-t}\right)\right)\cdot\frac{1}{2}\left(\exp\left(\frac{-\log(1-t^2)}{2}\right) + \exp\left(\frac{-\log(1-t^2)}{2}\right)\right)
\end{displaymath}
which gives the desired expression~\eqref{eq11}, and~\eqref{eq12} follows immediately.
\end{proof}
Notice that the case $q=1$ gives $F(t,1)=\bigl(1+t+1/(1-t)\bigr)/2$ which corresponds to the fact that $\lvert\Alt_{0}\rvert=\lvert\Alt_{1}\rvert=1$ and $\lvert\Alt_{N}\rvert=N!/2$ for $N\geq 2$. We obtain $F_N(q)$ by expanding \eqref{eq12} in powers of $t$ and picking the coefficient of $t^N/N!$. There does not seem to be a nice formula for $F_N(q)$ in general, however it is easy to use any mathematics software to obtain the polynomials for the first few values of $n$, see Table~\ref{tab:rank_generating_function}.
\begin{table}[htb] \centering
\renewcommand{\arraystretch}{1.2}
\begin{tabular}{c|c|c}
$n$ & $F_{n}(q)$ & $\displaystyle \sum_{x\in \Alt_{N}}q^{\la(x)}$\\
\hline
$0$ & $1$ & $1$ \\
$1$ & $q$ & $1$ \\
$2$ & $q^{2}$ & $q$ \\
$3$ & $q^{3}+2q$ & $1+2q$ \\
$4$ & $q^{4}+8q^{2}+3$ & $1+8q+3q^2$ \\
$5$ & $q^{5}+20q^{3}+39q$ & $1+20q+39q^2$ \\
$6$ & $q^{6}+40q^{4}+229q^{2}+90$ & $1+40q+229q^2+90q^3$ \\
$7$ & $q^{7}+70q^{5}+889q^{3}+1560q$ & $1+70q+889q^2+ 1560 q^3$
% $8$ & $q^{8}+112q^{6}+2674q^{4}+12648q^{2}+4725$ \\
% $9$ & $q^{9}+168q^{7}+6762q^{5}+67472q^{3}+107037q$ \\
% $10$ & $q^{10}+240q^{8}+15078q^{6}+273860q^{4}+1128321q^{2}+396900$ \\
\end{tabular}
\vspace*{2mm}
\caption{The rank generating function of $(\Alt_{N},\leqa)$ for $N\leq 7$.
\label{tab:rank_generating_function}}
\end{table}
\subsection{The Poset \texorpdfstring{$\mathcal{O\!N\!C}_{N}$}{ONCN}}
\label{sec:enumerative}
Recall from Proposition~\ref{prop:interval_decomposition} that any interval in $(\Alt_{N},\leqa)$ can be decomposed as a direct product of intervals induced by odd cycles times one interval induced by an element consisting of an even number of even cycles. In this section we study the intervals $\penc_{N}$ defined in Definition~\ref{def:even_nc}. In view of Propositions~\ref{prop:interval_decomposition} and~\ref{prop:AAo_first_properties} this knowledge is enough to understand all intervals in the poset $(\Alto_{N},\leqa)$.
Given a generated group $(G,\Gen)$, let $y\in G$ and $m\geq 1$. Then the multichains $y_{1}\leq_\Gen y_{2}\leq_\Gen\cdots \leq_\Gen y_{m}\leq_\Gen y$ are in bijection with the factorizations $x_1x_{2}\cdots x_{m+1}=y$ satisfying $\ell_{\Gen}(x_1)+\ell_{\Gen}(x_2)+\cdots +\ell_{\Gen}(x_{m+1})=\ell_{\Gen}(y)$ with $x_i\in G$. One simply defines $x_i=y^{-1}_{i-1}y_i$ for $i\in[m+1]$ with $y_0=e$ and $y_{m+1}=y$. The inverse bijection is given by setting $y_i=x_1x_2\cdots x_i$.
In particular, $m$-multichains of $\penc_{2n+1}$ correspond bijectively to factorizations $x_{1}x_{2}\cdots x_{m+1}=(1\;2\;\ldots\;2n+1)$ in $\Alt_{N}$ such that $\la(x_{1})+\la(x_{2})+\cdots+\la(x_{m+1})=n$. By Proposition~\ref{prop:kreweras_invariance}, all $x_i$ in this factorization belong to $\penc_{2n+1}$. Thus the $x_{i}$ have only odd cycles and therefore $\lt(x_i)=2\la(x_i)$ by Proposition~\ref{prop:AAo_first_properties}. We have the following lemma.
\begin{lemma}\label{lem:multichains_onc}
The set of $m$-multichains of $\penc_{2n+1}$ is in bijection with the set of factorizations $x_{1}x_{2}\cdots x_{m+1}=(1\;2\;\ldots\;2n+1)$ such that $\lt(x_{1})+\lt(x_{2})+\cdots+\lt(x_{m+1})=2n$, and all factors $x_{i}$ belong to $\Alto_{2n+1}$.
\end{lemma}
These multichains can thus be found inside $\pnc_{2n+1}$, which enables us to draw from results on the noncrossing partition lattice.
We start with a formula for the number of multichains of $\penc_{2n+1}$ with fixed rank jump vector, and then derive the zeta polynomial of $\penc_{2n+1}$, as well as some other enumerative properties, from this.
\begin{theo}\label{thm:enc_rs_chain_enumeration}
For $n,q\geq 1$, the number of $(q-1)$-multichains $C=(x_{1},x_{2},\ldots,x_{q-1})$ of $\penc_{2n+1}$ with rank jump vector $r(C)=(r_{1},r_{2},\ldots,r_{q})$ is
\begin{displaymath}
(2n+1)^{q-1}\prod_{i=1}^{q}{\frac{1}{2n+1-r_{i}}\binom{2n+1-r_{i}}{r_{i}}}.
\end{displaymath}
\end{theo}
\begin{proof}
By Lemma \ref{lem:multichains_onc} and the discussion preceding it, such a multichain is equivalent to a minimal factorization $y_{1}y_{2}\cdots y_{q}=(1\;2\;\ldots\;2n\!+\!1)$ where $y_i\in\Alto_{2n+1}$ for $i\in[q]$. Now~\cite[Theorem 3.2]{goulden92combinatorial} (see also~\cite[Theorem 5]{krattenthaler10decomposition}) gives a formula if the cycle type of each $y_i$ is fixed: in our case, if $y_i$ has $p_j^{(i)}$ cycles of length $2j+1$ for $j\geq 1$, then the number of these factorizations is given by
\begin{displaymath}
(2n+1)^{q-1}\prod_{i=1}^{q}{\frac{1}{2n-2r_{i}+1}\binom{2n-2r_{i}+1}{p_1^{(i)},p_2^{(i)},\ldots}},
\end{displaymath}
in which $r_i=\sum_{j}{jp_j^{(i)}}$. To obtain all factorizations, we sum over all sequences $(p_{1}^{(i)},p_{2}^{(i)},\ldots)$ by using~\cite[Lemma 4]{krattenthaler10decomposition}, and we obtain
\begin{displaymath}
(2n+1)^{q-1}\prod_{i=1}^{q}{\frac{1}{2n-2r_{i}+1}\binom{2n-r_{i}}{r_{i}}}
\end{displaymath}
for the number of such factorizations. This formula is equivalent to the formula in the statement.
\end{proof}
The cases $q=2,r(C)=(k,n-k)$ on the one hand, and $q=n+2,r(C)=(0,{1},{1},\ldots,{1},0)$ on the other give the following enumerations.
\begin{coro}\label{cor:enc_rk_and_chain_enumeration}
For $n\geq 1$ and $k\in\{0,1,\ldots,n\}$, we have the following formulas:
\begin{align*}
\Bigl\lvert\Rank_{\penc_{2n+1}}(k)\Bigr\rvert & = \frac{2n+1}{(2n+1-k)(n+1+k)}\binom{2n+1-k}{k}\binom{n+1+k}{n-k};\\
\Bigl\lvert\MaxChains\bigl(\penc_{2n+1}\bigr)\Bigr\rvert & = (2n+1)^{n-1}.
\end{align*}
\end{coro}
The second result is in fact a special case of~\cite[Theorem~1]{biane96minimal} and corresponds to sequence \cite[A052750]{sloane}. Table~\ref{tab:enc_rank_numbers} lists the rank numbers of $\penc_{2n+1}$ for $n\leq 5$.
\begin{table}[htb] \centering
\renewcommand{\arraystretch}{1.2}
\begin{tabular}{c|c}
$n$ & Rank numbers of $\penc_{2n+1}$ \\
\hline
$1$ & $(1,1)$ \\
$2$ & $(1,5,1)$ \\
$3$ & $(1,14,14,1)$ \\
$4$ & $(1,30,81,30,1)$ \\
$5$ & $(1,55,308,308,55,1)$ \\
\end{tabular}
\vspace*{3mm}
\caption{The sequences of rank numbers of $\penc_{2n+1}$ for $n\leq 5$.}
\label{tab:enc_rank_numbers}
\end{table}
Before we continue to prove Theorem~\ref{thm:main_zeta_polynomial}, we record the following auxiliary result, which is a multi-parameter version of the Rothe--Hagen identity.% Its proof follows essentially from the results noted in \cite{gould56some}.
\begin{lemm}\label{lem:multi_rothe_hagen}
Let $r$ be a positive integer, and fix integers $a_{1},a_{2},\ldots,a_{r},b,n$. Let $a=a_{1}+a_{2}+\cdots+a_{r}$. We have
\begin{displaymath}
\sum_{n_{1}+n_{2}+\cdots+n_{r}=n}{\prod_{i=1}^{r}{\frac{a_{i}}{a_{i}+bn_{i}}\binom{a_{i}+bn_{i}}{n_{i}}}} = \frac{a}{a+bn}\binom{a+bn}{n}.
\end{displaymath}
\end{lemm}
\begin{proof}
The key observation to this proof was already made in Equation~(7) of \cite{gould56some}. It was noted there that for integers $s,t$ we have the identity of power series in $z$:
\begin{equation}\label{eq:gould_equation}
x^{s}=\sum_{j=0}^{\infty}{\frac{s}{s+tj}\binom{s+tj}{j}z^{j}},
\end{equation}
%where $z=\tfrac{x-1}{x^{t}}$, and $\lvert z\rvert<\bigl\lvert\tfrac{(t-1)^{t-1}}{t^{t}}\bigr\rvert$.
where $x$ is defined as the power series solution of $x=1+zx^t$. Note that $x$ counts plane $t$-ary trees with respect to their number of internal vertices; also, \eqref{eq:gould_equation} is actually a direct application of the Lagrange Inversion Theorem. In the present setting we have $x^{a_{1}}x^{a_{2}}\cdots x^{a_{r}}=x^{a}$. If we apply \eqref{eq:gould_equation} on both sides, we obtain
\begin{align*}
\sum_{n=0}^{\infty}{\frac{a}{a+bn}\binom{a+bn}{n}z^{n}} & = x^{a} = x^{a_{1}}x^{a_{2}}\cdots x^{a_{r}} \\
& = \prod_{i=1}^{r}{\left(\sum_{n=0}^{\infty}{\frac{a_{i}}{a_{i}+bn}\binom{a_{i}+bn}{n}z^{n}}\right)}\\
& = \sum_{n=0}^{\infty}{\left(\sum_{n_{1}+n_{2}+\cdots+n_{r}=n}\prod_{i=1}^{r}{\frac{a_{i}}{a_{i}+bn_{i}}\binom{a_{i}+bn_{i}}{n_{i}}}\right)}z^{n}.
\end{align*}
The claim then follows by comparing coefficients.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:main_zeta_polynomial}]
By summing the number of $(q-1)$-multichains over all rank jump vectors given by Theorem~\ref{thm:enc_rs_chain_enumeration}, we get
\begin{align*}
\ZetaPol_{\penc_{2n+1}}(q) & = \sum_{r_{1}+r_{2}+\cdots+r_{q}=n}{(2n+1)^{q-1}\prod_{i=1}^{q}{\frac{1}{2n-r_{i}+1}\binom{2n-r_{i}+1}{r_{i}}}}\\
& = \frac{1}{2n+1}\left(\sum_{r_{1}+r_{2}+\cdots+r_{q}=n}{\prod_{i=1}^{q}{\frac{2n+1}{2n-r_{i}+1}\binom{2n-r_{i}+1}{r_{i}}}}\right)\\
& \overset{*}{=} \frac{1}{2n+1}\left(\frac{q(2n+1)}{q(2n+1)-n}\binom{q(2n+1)-n}{n}\right)\\
& = \frac{q}{q(2n+1)-n}\binom{q(2n+1)-n}{n}.
\end{align*}
as desired. The equality marked with a ``*'' is Lemma~\ref{lem:multi_rothe_hagen} with $r=q$, $a_{1}=a_{2}=\cdots=a_{q}=2n+1$ and $b=-1$.
\end{proof}
By evaluating the previous polynomial at $q=2,3$, and $-1$, respectively, we obtain the following corollary.
\begin{coro}\label{cor:enc_essentials}
For $n\geq 1$, we have the following formulas:
\begin{align}
\Bigl\lvert\enc_{2n+1}\Bigr\rvert & = \frac{1}{n+1}\binom{3n+1}{n}; \label{eq:enc_card}\\
\Bigl\lvert\Int\bigl(\penc_{2n+1}\bigr)\Bigr\rvert & = \frac{3}{5n+3}\binom{5n+3}{n};\label{eq:enc_intervals}\\
(-1)^{n}\mu\bigl(\penc_{2n+1}\bigr) & = \frac{1}{4n+1}\binom{4n+1}{n}.\label{eq:enc_moebius}
\end{align}
\end{coro}
The formulas appearing in Corollary~\ref{cor:enc_essentials} correspond to sequences \cite[A006013]{sloane}, \cite[A118970]{sloane}, and \cite[A002293]{sloane}, respectively.
\begin{rema}
Besides studying enumerative aspects of the poset $(\Alt_{N},\leqa)$ we may as well ask for structural or topological properties.
On the topological side, it is well known that the order complex of the poset $(\Sym_{N},\leqt)$ is Cohen--Macaulay and thus a wedge of spheres~\cite[Theorem~1]{athanasiadis08absolute}. Moreover, it follows from \cite[Example~2.9]{bjorner80shellable} that every interval in $(\Sym_{N},\leqt)$ is in fact (lexicographically) shellable.
We have verified by computer that every interval in the poset $(\Alt_{N},\leqa)$ is shellable for $N\leq 7$, which leads us to believe that this holds for all $N$.
\end{rema}
\subsection{Bijections}
\label{sec:bijective}
In this section we reprove \eqref{eq:enc_card} bijectively, and we use this bijection to determine the size of $\enc_{2n}$.
\begin{proof}[Bijective Proof of \eqref{eq:enc_card}]
Let $N>0$ be an integer. We first recall the bijection $\GJbij$ from $\nc_{N}$ to the set of edge-rooted bicolored plane trees with $N$ edges due to Goulden and Jackson~\cite[Theorem~2.1]{goulden92combinatorial}.
Consider $x\in\nc_{N}$, and let $y=x^{-1}(1\;2\;\ldots\;N)$. With each cycle of $x$ (respectively~$y$) we associate a white (respectively black) vertex in the tree $\GJbij(x)$. The vertex corresponding to a cycle $(a_1\;a_2\;\ldots\;a_p)$ is adjacent to $p$ edges labeled by $a_1,a_{2},\ldots,a_p$ clockwise. This creates a planar bicolored tree, and in order to obtain $\GJbij(x)$ we root the tree at the edge labeled by $1$, and delete all labels. To obtain the inverse bijection, we simply need to reconstruct the labels from the tree: this is done by walking around the tree clockwise, and labeling the edges by $1,2,\ldots,N$ starting from the marked edge in the direction from its white to its black vertex. Clearly this bijection sends the cycle type of $x$ (respectively $y$) to the degree distribution of white (respectively black) vertices in the tree $\GJbij(x)$.
By Lemma~\ref{lem:multichains_onc}, applied to the case $m=1$, it follows that $\GJbij$ restricts to a bijection between $\enc_{2n+1}$ and marked bicolored plane trees with $2n+1$ edges where all vertices have odd degree. By deleting the marked edge, we obtain a pair $(T_{1},T_{2})$ of planar \emph{rooted} trees where each node has an even number of children and the total number of edges in $T_{1}$ and $T_{2}$ is $2n$. In view of \cite{deutsch02diagonally} the set of such pairs of trees is in bijection with the set of pairs of ternary trees with a total of $n$ internal nodes. That the cardinality of this set is given by \eqref{eq:enc_card} follows for instance from \cite[p.~201, Equation~(5.60)]{graham94concrete}.
%
% bijection between $\enc_{2n+1}$ and the set of pairs $T_1,T_2\in \mathcal{T}^{e}$ where $\mathcal{T}^{e}$ is the set of planar \emph{rooted} trees where each node has an even number of children, and the total number of edges in $T_1$ and $T_2$ is $2n$. In view of \cite{deutsch02diagonally}, the latter set is in bijection with the set of pairs of ternary trees with a total of $n$ internal nodes. That the cardinality of this set is given by \eqref{eq:enc_card} follows for instance from \cite{graham94concretep.\;201, Equation~(5.60)}.
\end{proof}
We may use this bijection to prove the following result.
\begin{prop}\label{prop:onc_cardinality_even}
For $n\geq 1$, we have
\begin{align*}
\Bigl\lvert\enc_{2n}\Bigr\rvert = \frac{1}{2n+1}\binom{3n}{n}.
\end{align*}
\end{prop}
\begin{proof}
Let $x\in\enc_{2n}$. Since every cycle of $x$ has odd length, and $x$ lives in $\Alt_{2n}$, we conclude that $x$ has an even number of cycles. Moreover, the permutation $y=x^{-1}(1\;2\;\ldots\;2n)$ has a unique cycle with even length. (This is the cycle containing $2n$.) It follows that $\GJbij(x)$ is a marked bicolored plane tree with $2n$ edges, where all vertices have odd degree, except for a single black vertex.
If we make this black vertex the root, we obtain a planar rooted tree with $2n$ edges, where each node has an even number of children, and this process is clearly bijective. As before, the set of such trees is in bijection with the set of ternary trees with $n$ internal nodes~\cite{deutsch02diagonally}. The set of such trees is counted by \eqref{eq:gould_equation} with $s=1$ and $t=3$, and yields precisely the formula in the statement.
%
% Actually one can also work with $\enc_{2n}$. Here one shows easily that $\GJbij$ sends such elements to marked bicolored plane trees with $2n$ edges where all vertices have odd degree, except the black vertex adjacent to the marked edge. Indeed this vertex corresponds to the cycle of $y$ containing $1$, and this cycle has even length because $x$ has an even number of cycles. By making this black vertex the root, we obtain a bijection between $\enc_{2n}$ and trees in $\mathcal{T}^{e}$ with $2n$ edges. Their enumeration is well known (it is an application of~\eqref{eq:gould_equation} for $s=1$ and $t=3$) and we thus get the following proposition.
\end{proof}
\begin{exam}\label{ex:enc_8}
Let us illustrate the bijection with an example. Let us consider the permutation $x=(1\;14\;15)(3\;4\;7)(8\;9\;10\;11\;12)\in\Alt_{17}$. Its Kreweras complement is $y=(1\;2\;7\;12\;13)(4\;5\;6)(15\;16\;17)$. The corresponding labeled planar bicolored tree is shown in Figure~\ref{fig:enc_8_example_labeled_tree}; and the corresponding pair of ternary trees is shown in Figure~\ref{fig:enc_8_example_rooted_trees}.
\end{exam}
\begin{figure}[htb]\centering
\def\thefigure{{\upshape \alph{figure}}}\setcounter{figure}{0}\def\figurename#1{}
% \begin{minipage}[t]{0.46\textwidth}\centering
\begin{tikzpicture}
\def\x{1};
\def\y{1};
\def\s{.4};
%%
\draw(2*\x,2.2*\y) node[fill,circle,scale=\s](m1){};
\draw(2*\x,3.8*\y) node[fill,circle,scale=\s](m2){};
\draw(4*\x,3*\y) node[fill,circle,scale=\s](m3){};
\draw(5*\x,4.4*\y) node[fill,circle,scale=\s](m4){};
\draw(5.4*\x,3.6*\y) node[fill,circle,scale=\s](m5){};
\draw(5.8*\x,3.1*\y) node[fill,circle,scale=\s](m6){};
\draw(5.8*\x,2.5*\y) node[fill,circle,scale=\s](m7){};
\draw(5.6*\x,2.1*\y) node[fill,circle,scale=\s](m8){};
\draw(5*\x,2*\y) node[fill,circle,scale=\s](m9){};
\draw(3*\x,3*\y) node[draw,circle,scale=\s](n1){};
\draw(1*\x,4.2*\y) node[draw,circle,scale=\s](n2){};
\draw(2*\x,4.8*\y) node[draw,circle,scale=\s](n3){};
\draw(3.8*\x,4*\y) node[draw,circle,scale=\s](n4){};
\draw(4.6*\x,3.6*\y) node[draw,circle,scale=\s](n5){};
\draw(5*\x,2.8*\y) node[draw,circle,scale=\s](n6){};
\draw(3.8*\x,2*\y) node[draw,circle,scale=\s](n7){};
\draw(6.2*\x,3.9*\y) node[draw,circle,scale=\s](n8){};
\draw(6.2*\x,3.3*\y) node[draw,circle,scale=\s](n9){};
%%
\draw(m1) -- (n1) node[fill=white,inner sep=.9pt] at (2.5*\x,2.6*\y) {\tiny $14$};
\draw(m2) -- (n1) node[fill=white,inner sep=.9pt] at (2.5*\x,3.4*\y) {\tiny $15$};
\draw(m2) -- (n2) node[fill=white,inner sep=.9pt] at (1.5*\x,4*\y) {\tiny $16$};
\draw(m2) -- (n3) node[fill=white,inner sep=.9pt] at (2*\x,4.3*\y) {\tiny $17$};
\draw[very thick,red](m3) -- (n1) node[fill=white,inner sep=.9pt] at (3.5*\x,3*\y) {\tiny $1$};
\draw(m3) -- (n4) node[fill=white,inner sep=.9pt] at (3.9*\x,3.5*\y) {\tiny $2$};
\draw(m3) -- (n5) node[fill=white,inner sep=.9pt] at (4.3*\x,3.3*\y) {\tiny $7$};
\draw(m3) -- (n6) node[fill=white,inner sep=.9pt] at (4.5*\x,2.9*\y) {\tiny $12$};
\draw(m3) -- (n7) node[fill=white,inner sep=.9pt] at (3.9*\x,2.5*\y) {\tiny $13$};
\draw(m4) -- (n5) node[fill=white,inner sep=.9pt] at (4.8*\x,4*\y) {\tiny $3$};
\draw(m5) -- (n5) node[fill=white,inner sep=.9pt] at (5*\x,3.6*\y) {\tiny $4$};
\draw(m5) -- (n8) node[fill=white,inner sep=.9pt] at (5.8*\x,3.75*\y) {\tiny $5$};
\draw(m5) -- (n9) node[fill=white,inner sep=.9pt] at (5.8*\x,3.45*\y) {\tiny $6$};
\draw(m6) -- (n6) node[fill=white,inner sep=.9pt] at (5.4*\x,2.95*\y) {\tiny $8$};
\draw(m7) -- (n6) node[fill=white,inner sep=.9pt] at (5.4*\x,2.65*\y) {\tiny $9$};
\draw(m8) -- (n6) node[fill=white,inner sep=.9pt] at (5.3*\x,2.45*\y) {\tiny $10$};
\draw(m9) -- (n6) node[fill=white,inner sep=.9pt] at (5*\x,2.4*\y) {\tiny $11$};
\end{tikzpicture}
% \put(-148,-15){\begin{minipage}[t]{0.7\textwidth}\def\thefigure{\alph{figure}}
% \thefigure.
\caption{The labeled planar bicolored tree corresponding to $x=(1\;14\;15)(3\;4\;7)(8\;9\;10\;11\;12)$ and $y=(1\;2\;7\;12\;13)(4\;5\;6)(15\;16\;17)$.}\label{fig:enc_8_example_labeled_tree}
% \end{minipage}}%
% \put(33,-15){\begin{minipage}[t]{0.7\textwidth}%
% (b) The pair of planar rooted trees coming from the tree Figure~\ref{fig:enc_8_example_labeled_tree} by removing the marked edge.
% \end{minipage}}%
% \caption{The labeled planar bicolored tree corresponding to $x=(1\;14\;15)(3\;4\;7)(8\;9\;10\;11\;12)$ and $y=(1\;2\;7\;12\;13)(4\;5\;6)(15\;16\;17)$.}
% \end{minipage}
% \hspace*{.1cm}
\vspace*{5mm}
% \begin{minipage}[t]{0.46\textwidth} \centering
\begin{tikzpicture}
\def\x{1};
\def\y{1};
\def\s{.4};
%%
\draw(2*\x,4*\y) node[fill,circle,scale=\s](n1){};
\draw(1.5*\x,3*\y) node[fill,circle,scale=\s](n2){};
\draw(2.5*\x,3*\y) node[fill,circle,scale=\s](n3){};
\draw(1*\x,2*\y) node[fill,circle,scale=\s](n4){};
\draw(2*\x,2*\y) node[fill,circle,scale=\s](n5){};
\draw(4.75*\x,4*\y) node[fill,circle,scale=\s](m1){};
\draw(3.75*\x,3*\y) node[fill,circle,scale=\s](m2){};
\draw(4.25*\x,3*\y) node[fill,circle,scale=\s](m3){};
\draw(5.25*\x,3*\y) node[fill,circle,scale=\s](m4){};
\draw(5.75*\x,3*\y) node[fill,circle,scale=\s](m5){};
\draw(3.75*\x,2*\y) node[fill,circle,scale=\s](m6){};
\draw(4.08*\x,2*\y) node[fill,circle,scale=\s](m7){};
\draw(4.42*\x,2*\y) node[fill,circle,scale=\s](m8){};
\draw(4.75*\x,2*\y) node[fill,circle,scale=\s](m9){};
\draw(5.08*\x,2*\y) node[fill,circle,scale=\s](m10){};
\draw(5.42*\x,2*\y) node[fill,circle,scale=\s](m11){};
\draw(4.91*\x,1*\y) node[fill,circle,scale=\s](m12){};
\draw(5.25*\x,1*\y) node[fill,circle,scale=\s](m13){};
%%
\draw(n1) -- (n2);
\draw(n1) -- (n3);
\draw(n2) -- (n4);
\draw(n2) -- (n5);
\draw(m1) -- (m2);
\draw(m1) -- (m3);
\draw(m1) -- (m4);
\draw(m1) -- (m5);
\draw(m3) -- (m6);
\draw(m3) -- (m7);
\draw(m3) -- (m8);
\draw(m3) -- (m9);
\draw(m4) -- (m10);
\draw(m4) -- (m11);
\draw(m10) -- (m12);
\draw(m10) -- (m13);
\end{tikzpicture}
\caption{The pair of planar rooted trees coming from the tree Figure~\ref{fig:enc_8_example_labeled_tree} by removing the marked edge.}
\label{fig:enc_8_example_rooted_trees}
% \end{minipage}
\def\thefigure{\arabic{figure}}\setcounter{figure}{1}
\caption{An illustration of the bijection $\GJbij$.}
\label{fig:enc_8_example}
\end{figure}
\begin{rema}\label{rem:altproof}
We want to sketch how Goulden--Jackson's bijection gives an alternative way to prove certain key results of Section \ref{sec:alternating_noncrossing}.
We start with Proposition~\ref{prop:onc_characterization}, so let $c= (1\;2\;\ldots\;2n\!+\!1)$ and $x\in \nc_{2n+1}$. The proposition states that $x\in\enc_{2n+1}$ if and only if $x\leqa c$. By Lemma \ref{lem:multichains_onc}, one has $x\leqa c$ if and only if $xy=c$ is a minimal factorization and $x,y$ have only odd cycles, where $y=x^{-1}c=K_c(x)$. Via Goulden--Jackson's bijection, this means that all vertices of the marked bicolored planar tree $\Phi(x)$ have odd degree. It is then easily proved, by induction starting from the leaves of $\Phi(x)$, that all cycles of $x$ and $y$ necessarily satisfy Property~\eqref{it:od}, and thus $x$ belongs to $\enc_{2n+1}$.
To prove the reverse implication, consider $x\in\enc_{2n+1}$. It is enough to prove that $y=x^{-1}c$ has odd cycles. Equivalently, one must show that the white vertices in $\Phi(x)$ all have odd degree if the cycles of $x$ satisfy Property~\eqref{it:od}, which is also done by induction.
This approach has the additional advantage that it proves Proposition~\ref{prop:kreweras_invariance} for $y$ a long cycle $(1\;2\;\ldots\;2k\!+\!1)$, and thus bypasses the use of Lemma \ref{lem:value_characterization}.
\end{rema}
\subsection{The Case of Two Even Cycles}
\label{sec:enumeration_two_even_cycles}
In Section~\ref{sec:alternating_noncrossing} we have extensively studied the principal order ideals in $(\Alt_{N},\leqa)$ induced by permutations consisting of only odd cycles. In view of Proposition~\ref{prop:interval_decomposition} it remains to study those principal order ideals induced by even permutations consisting of only even cycles.
We restrict our attention to even permutations which have precisely two even cycles, say $x=x_{p,q}=(a_{1}\;a_{2}\;\ldots\;a_{2p})(b_{1}\;b_{2}\;\ldots\;b_{2q})$ for $p\geq q\geq 1$. Then, $x_{p,q}\in\Alt_{2(p+q)}$, and Proposition~\ref{prop:alternating_length} implies $\ell_{\bth}(x_{p,q})=p+q$. Let $N=2(p+q)$.
We are not able to describe a combinatorial model for the elements $y\in\Alt_{N}$ with $y\leqa x$, though there is reason to believe that noncrossing partitions on an annulus could be involved. We can however count the number of reduced decompositions of $x_{p,q}$.
\begin{prop}\label{prop:max_chains_two_even}
The number of maximal chains in $[\id,x_{p,q}]_{\bth}$ is
\begin{displaymath}
\frac{2(p+q-1)!(2p)^{p}(2q)^{q}}{(p-1)!(q-1)!}.
\end{displaymath}
\end{prop}
\begin{proof}
We have to count the minimal factorizations of $x_{p,q}$ in $3$-cycles; these factorizations are easily seen to be transitive. Therefore the number that we seek is precisely the coefficient $c_3(2p,2q)$ in \cite{goulden00transitive}, and can be computed via Theorem~1.4 in that paper.
\end{proof}
Let us call an element $y$ of $[\id,x_{p,q}]_{\bth}$ \defn{pure} if the support of any cycle of $y$ is included either in $\{a_{1},a_{2},\ldots,a_{2p}\}$ or $\{b_{1},b_{2},\ldots,b_{2q}\}$; such elements are called \defn{even} if they contain a cycle of even length, and \defn{odd} otherwise. Finally, $y$ is \defn{mixed} if it is not pure.
\begin{prop}
There is a bijection between even pure elements of $[\id,x_{p,q}]_{\bth}$ and odd ones. Their common cardinality is given by
\begin{displaymath}
\binom{3p-1}{p-1}\binom{3q-1}{q-1}.
\end{displaymath}
\end{prop}
\begin{proof}[Sketch of the Proof]
The Kreweras complement $K_{x_{p,q}}$ is the desired bijection: it is clear that it leaves stable the set of pure elements, and one checks easily that it exchanges the parity.
An even pure element can be decomposed uniquely as a product of a permutation with support in $\{a_1,a_2,\ldots,a_{2p}\}$ and a permutation with support in $\{b_1,b_2,\ldots,b_{2q}\}$; we only need to focus on the first permutation. In the same way as Proposition \ref{prop:onc_characterization}, one can show that this permutation is a noncrossing partition of $\{a_1,a_2,\ldots, a_{2p}\}$ with exactly one even cycle, and where all cycles $(x_10$ and that the claim holds for all elements of $\Alto_{N}$ with length smaller than $\la(x)$.
Suppose first that $x$ has more than one (non-trivial) cycle in its decomposition, say $x=\zeta_1\zeta_2\cdots\zeta_k$ with $k\geq 2$, so that $\la(\zeta_i)<\la(x)$ for all $i$. By construction, since $x\in\Alto_{N}$ so are its cycles. Let $\ww\in\red_{\bth}(x)$. By Proposition~\ref{prop:interval_decomposition}, $\ww$ is a shuffle of $k$ reduced words $\ww_i\in\red_{\bth}(\zeta_{i})$, and moreover the letters involved in distinct $\ww_i$ commute since the corresponding $3$-cycles have disjoint support. Therefore the Hurwitz action allows us to bring $\ww$ to the form $\ww_1\ww_2\cdots\ww_k$. Now by induction the Hurwitz action is transitive on $\red_{\bth}(\zeta_i)$ for all $i\in[k]$, and therefore also on $\red_{\bth}(x)$.
If $x$ is a single cycle, we can assume without loss of generality that $x=c=(1\;2\;\ldots\;2n\!+\!1)$ which has length $\la(c)=n$. Let us write $u_{i}=(i,i\!+\!1,i\!+\!2)$ for $i\in[N-2]$, and fix the reduced word $\ww_c=u_{1}u_{3}\cdots u_{2n-1}\in\red_{\bth}(c)$.
For any $k\in\{0,1,\ldots,n-1\}$ define $\ww_k:=\sigma^{-1}_1\sigma_2^{-1}\cdots\sigma_k^{-1} \ww_c$. A direct computation shows that
\begin{displaymath}
\ww_k=(1,2k\!+\!2,2k\!+\!3)u_{1}u_{3}\cdots
\reallywidehat
{u_{2k+1}}\cdots u_{2n-1},
% \ww_k=(1,2k\!+\!2,2k\!+\!3)(1,2,3)(3,4,5)\cdots \reallywidehat{(2k\!+\!1,2k\!+\!2,2k\!+\!3)}\cdots (2n\!-\!1,2n,2n\!+\!1).
\end{displaymath}
where the hat indicates omission. Now for $j\in\{0,1,\ldots,n-k-1\}$ define
\begin{displaymath}
\ww_{k,j}:=(1,2k\!+\!2,2k\!+\!2j\!+\!3)\;\xx\;\yy\;\zz,
\end{displaymath}
where the words $\xx,\yy,\zz$ are given by
\begin{align*}
\xx & = u_{2k+2j+2}u_{2k+2j}\cdots u_{2k+2}\\
\yy & = u_{1}u_{3}\cdots u_{2k-1}\\
\zz & = u_{2k+2j+3}u_{2k+2j+5}\cdots u_{2n-1}.
\end{align*}
In particular $\ww_{k,0}=\ww_k$. By induction on $j$ it is verified that
\begin{displaymath}
\sigma_1^2\sigma_2\cdots\sigma_{k+j}\ww_{k,j}=\ww_{k,j+1},
\end{displaymath}
which implies that all words $\ww_{k,j}$ are Hurwitz-equivalent to $\ww_c$.
Furthermore, it is easily shown that $(\sigma_1\sigma_2\cdots\sigma_{n-1})^n$ acts on a word of length $n$ consisting of $3$-cycles by conjugating each letter by $c$. The characterization in Proposition~\ref{prop:onc_characterization} implies that any $3$-cycle below $c$ is conjugate to a $3$-cycle of the form $(1,{2k\!+\!2j\!+\!2},{2k\!+\!2j\!+\!3})$. So we proved that for any $3$-cycle $a$ below $c$, there exists a word $\ww_a$ such that $a\ww_a$ is Hurwitz-equivalent to $\ww_c$.
Now pick any reduced word for $c$, and write it as $a\ww$ where $a\in A$ is its first letter, and let $x=a^{-1}c$ be the element represented by $\ww$. Then $x$ is in $\Alto_{N}$ by Proposition~\ref{prop:AAo_first_properties}, and so by induction the Hurwitz action is transitive on its reduced expressions. In particular $\ww$ is Hurwitz-equivalent to $\ww_{a}$, and so from the previous paragraph $a\ww$ is Hurwitz-equivalent to $\ww_c$, and the direct implication in Proposition~\ref{prop:hurwitz_transitive} is proved.
\end{proof}
\begin{rema}
The recursive structure of the proof is inspired by \cite[Proposition 1.6.1]{bessis03dual}. The result is also a special case of \cite[Theorem~5.4.11]{lando04graphs}. The proof there is of a geometric nature, using the dictionary between factorizations and ramified coverings of the Riemann sphere.
\end{rema}
We now deal with the case where $x\in\Alt_{N}$ has $2k$ even cycles for $k>0$. For $\ww\in\red_{\bth}(x)$ we define an equivalence relation $M_\ww$ on the set of even cycles of $x$ as follows: $M_\ww$ is the finest relation such that $\zeta\sim\zeta'$ whenever there exists a letter of $\ww$ whose support intersects the supports of both $\zeta$ and $\zeta'$.
Let us illustrate the relation $M_{\ww}$ with a concrete example. Consider
\begin{displaymath}
x = (1\;5\;4\;7)(2\;9)(3\;12\;8\;6\;10\;15)(11)(13\;18\;14)(16\;17)\in\Alt_{18},
\end{displaymath}
and the reduced factorization
\begin{displaymath}
\ww = (1\;2\;9)\cdot(1\;7\;9)\cdot(3\;6\;17)\cdot(1\;5\;4)\cdot(6\;17\;16)\cdot(3\;12\;8)\cdot(6\;10\;15)\cdot(13\;18\;14).
\end{displaymath}
The even cycles of $x$ are $\zeta_{1}=(1\;5\;4\;7)$, $\zeta_{2}=(2\;9)$, $\zeta_{3}=(3\;12\;8\;6\;10\;15)$, and $\zeta_{4}=(16\;17)$. The supports of the letters $(1\;2\;9)$ and $(1\;7\;9)$ of $\ww$ both intersect the supports of $\zeta_{1}$ and $\zeta_{2}$, so we have $\zeta_{1}\sim\zeta_{2}$. Moreover, the supports of the letters $(3\;6\;17)$ and $(6\;17\;16)$ of $\ww$ both intersect the supports of $\zeta_{3}$ and $\zeta_{4}$, so we have $\zeta_{3}\sim\zeta_{4}$. Therefore the equivalence classes of $M_{\ww}$ are given by $\{\zeta_{1},\zeta_{2}\}$ and $\{\zeta_{3},\zeta_{4}\}$.
\begin{lemm}\label{lem:matchings}
Let $x\in \Alt_{N}$ and $\ww\in\red_{\bth}(x)$. All equivalence classes of $M_\ww$ consist of two cycles, \ie $M_\ww$ is a (perfect) \emph{matching}. Moreover, $M_\ww$ is invariant under the Hurwitz action on $\red_{\bth}(x)$, \ie for any $i<\la(x)$, we have $M_{\sigma_i^{\pm 1}\ww}=M_\ww$.
\end{lemm}
\begin{proof}
Consider the maximal chain from the identity to $x$ in $(\Alt_{N},\leqa)$ corresponding to $\ww\in\red_{\bth}(x)$. By the description of covers in Corollary~\ref{cor:covers}, there must be $k$ occurrences of a cover of type \eqref{it:even}, and each creates a pair of even cycles (from a pair of odd cycles). If $x_{i}\lessdot_{\bth}x_{i+1}$ is such a cover, then the $3$-cycle $x_{i}^{-1}x_{i+1}$ implies that the newly created pair of even cycles in $x_{i+1}$ is contained in some block of $M_\ww$. Since the other possible covers of type \eqref{it:oddo} or \eqref{it:odde} merge three cycles (at most one of which is even), they are necessarily labeled by $3$-cycles whose support cannot involve elements from non-paired even cycles. This shows that all classes of $M_\ww$ have size $2$.
By the analysis from the previous paragraph, the support of each $3$-cycle occurring in $\ww$ is included in the support of $\zeta\zeta'$ for a well-defined pair $\{\zeta,\zeta'\}\in M_\ww$, or in the support of an odd cycle of $x$. So letters corresponding to distinct pairs of $M_\ww$ commute, which entails that the Hurwitz action does not modify $M_\ww$.
\end{proof}
Lemma~\ref{lem:matchings} effectively reduces the Hurwitz action to the case of two even cycles; we thus consider $x_{p,q}=(a_1\;a_2\;\ldots\;a_{2p})(b_1\;b_2\;\ldots\;b_{2q})\in\Alt_N$ as in Section~\ref{sec:enumeration_two_even_cycles}. % with $a_{1}