%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[revision]{FPSAC2019}

\articlenumber{57}
\addbibresource{57.bib}


\usepackage{latexsym,verbatim,multirow,graphicx,epsfig,enumerate, paralist,xypic,hyperref}
\usepackage{xcolor}
\usepackage[utf8]{inputenc}
\usepackage[normalem]{ulem}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

 \newtheorem{theorem}{Theorem}[section]
   \newtheorem{proposition}[theorem]{Proposition}
   \newtheorem{prop}[theorem]{Proposition}
   \newtheorem{lemma}[theorem]{Lemma}
   \newtheorem{corollary}[theorem]{Corollary}
    \newtheorem{cor}[theorem]{Corollary}
   \newtheorem{conjecture}[theorem]{Conjecture}
   \newtheorem{problem}[theorem]{Problem}
   \newtheorem*{theorem*}{Theorem}
\theoremstyle{definition}
   \newtheorem{definition}[theorem]{Definition}
   \newtheorem{example}[theorem]{Example}
   \newtheorem{examples}[theorem]{Examples}
   \newtheorem{question}[theorem]{Question}
   \newtheorem{remark}[theorem]{Remark}
   \newtheorem{convention}[theorem]{Convention}
   \newtheorem*{main}{Main Question}

\numberwithin{equation}{section}

\newcommand\qbin[3]{\left[\begin{matrix} #1 \\ #2 \end{matrix} \right]_{#3}}
\newcommand\hook[2]{{\left( #2-#1, 1^{#1} \right)}}
\newcommand{\charhook}[3]{h(#1; #2, #3)}
%{{_{#3}\mathfrak{h}^{#1}_{#2}}}


\newcommand\Symm{\mathfrak{S}}

\newcommand\xx{{\mathbf{x}}}
\newcommand\yy{{\mathbf{y}}}

\newcommand\Nar{\operatorname{Nar}}
\newcommand{\boldt}{{\bf t}}
\newcommand{\boldalpha}{{\boldsymbol{\alpha}}}
\newcommand{\boldbeta}{{\boldsymbol{\beta}}}
\newcommand\abs{\operatorname{abs}}
\newcommand\mult{\operatorname{mult}}
\newcommand\defining{\operatorname{def}}
\newcommand\rad{\operatorname{rad}}
\newcommand\corad{\operatorname{corad}}
\newcommand\rank{\operatorname{rank}}
\newcommand\codim{\operatorname{codim}}
\newcommand\one{\mathbf{1}}
\newcommand\Sym{\operatorname{Sym}}
\newcommand\Hom{\operatorname{Hom}}
\newcommand\Cat{\operatorname{Cat}}
\newcommand\Hilb{\operatorname{Hilb}}
\newcommand\Conj{\operatorname{Conj}}
\newcommand\Ind{\operatorname{Ind}}
\newcommand\Par{\operatorname{Par}}
\newcommand\Frac{\operatorname{Frac}}
\newcommand\Irr{\operatorname{Irr}}
\newcommand\Aut{\operatorname{Aut}}
\newcommand\Tr{\operatorname{Tr}}
\newcommand\wt{\operatorname{wt}}
\newcommand\fix{\operatorname{fix}}
\newcommand\maj{\operatorname{maj}}
\newcommand\sgn{\operatorname{sgn}}
\newcommand\normchi{\widetilde{\chi}}
\newcommand\Class{\operatorname{Cl}}
\newcommand\Nref{\operatorname{N^{\operatorname{ref}}}}
\newcommand\Nhyp{\operatorname{N^{\operatorname{hyp}}}}
\newcommand\hcprod{{*}}
\newcommand\rk{\operatorname{rk}}
%\newcommand\hcprod{{\circ}}
\newcommand{\ibar}{\bar\imath}
\newcommand{\jbar}{\bar\jmath}
\newcommand\Span{\operatorname{span}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\occ}{\operatorname{occ}}

%\newcommand{\defn}[1]{\textbf{#1}}
\newcommand{\defn}[1]{{\it {#1}}}
\newcommand{\type}[1]{\mathrm{#1}}
%\newcommand{\B}{\mathcal{B}}

\newcommand\OOO{{\mathcal{O}}}
\newcommand\RRR{{\mathcal{R}}}

\newcommand\CCC{{\mathbf{C}}}
\newcommand\ccc{{\mathbf{c}}}

\newcommand\CC{{\mathbb{C}}}
\newcommand\ZZ{{\mathbb{Z}}}
\newcommand\NN{{\mathbb{N}}}
\newcommand\QQ{{\mathbb{Q}}}
\newcommand\RR{{\mathbb{R}}}
\newcommand\FF{{\mathbb{F}}}
\newcommand\Gr{{\mathbb{G}}}
\newcommand\GL{{\mathrm{GL}}}


\newcommand{\poly}[3]{P_{#1}^{(#2)}(#3)}


\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

\usepackage{lipsum}

%% define your title in the usual way
\title{Factorization problems in complex reflection groups}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Joel Brewster Lewis\thanks{\href{mailto:jblewis@gwu.edu}{jblewis@gwu.edu}}\addressmark{1}
\and 
Alejandro H. Morales\thanks{\href{mailto:ahmorales@math.umass.edu}{ahmorales@math.umass.edu}}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, George Washington
  University, Washington, DC 20052\\ \addressmark{2}Department of Mathematics
  and Statistics, University of Massachusetts, Amherst, MA 01003}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We enumerate factorizations of a Coxeter element into arbitrary factors in the complex reflection groups $G(d, 1, n)$ (the wreath product of the symmetric group with a cyclic group) and its subgroup $G(d, d, n)$, applying combinatorial and algebraic methods, respectively.  After a change of basis, the coefficients that appear are the same as those that appear in the corresponding enumeration in the symmetric group.}

\resumetitle{R\'esum\'e}
%% put your French abstract here, or comment this out if you don't have one
\resume{Nous comptons les factorisations d'un \'el\'ement de Coxeter en facteurs arbitraires dans les groupes de r\'eflexion complexes $ G(d, 1, n)$ (le produit en couronne du groupe sym\'etrique avec un groupe cyclique) et de son sous-groupe $ G (d, d, n) $, en appliquant des m\'ethodes combinatoires et alg\'ebriques, respectivement. Apr\`es un changement de base, les coefficients qui apparaissant sont le m\^eme que ceux figurant dans l'\'enum\'eration correspondante du groupe sym\'etrique.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{factorizations, complex reflection groups, wreath product, permutations}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{CRG.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% G(de, e, n) consists of monomial matrices whose
% nonzero entries are de-th roots of unity, having
% product a d-th root of unity.  In particular,
% type A is G(1, 1, n),
% type B is G(2, 1, n), and
% type D is G(2, 2, n).
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newcommand{\jbl}[1]{{\color{red} #1 }}

\newcommand{\ahm}[1]{{\bf \color{blue} \# #1 \# }}


\begin{document}

\maketitle




%
%\section{Background: colored permutations and the character approach}
%
%Group $G(d, 1, n)$  [decision: is this the name of the group, or a type label (like $B_n$)?]:  as a set, it is colored permutations.  As a group, it is the wreath product $(\ZZ/d\ZZ) \wr \Symm_n$.  Represent by matrices, in which case it is a complex reflection group; the name comes from the Shephard--Todd classification of those groups \cite{ShephardTodd}.  When $n = 1$, we get the cyclic group of $d$th roots of unity; when $d = 1$, we get the symmetric group, while for $d = 2$ we get the hyperoctahedral group of signed permutations, the Coxeter group of type $B_n$.
%
%Something about factorization problems in general.  In $\Symm_n$, one factors the long cycle.  As a permutation group acting on $[n]$, these are exactly the transitive elements; as a Coxeter group, these are exactly the Coxeter elements (a different notion of transitivity; define or gloss).  In $G(d, 1, n)$, the group acts on $[n] \times [d]$.  The Coxeter elements are the ones that act transitively; equivalently, blahblahblah\footnote{Mention the more restrictive definitions.  It should follow from \cite{RRS} that it doesn't matter, but this is a tiny bit subtle and we should be careful about it.  (This may also use Shi's result \cite[Remark 2.3(1)]{Shi} that reflection length is equal to fixed space codimension in $G(d, 1, n)$: the reflection automorphisms should preserve reflection length of every element.)  It is worth checking in $G(d, d, n)$ what's going on.}  Every such element is conjugate to something like 
%\[
%\begin{bmatrix}
%&&&&z\\
%1&&&&\\
%&1&&&\\
%&&\ddots&&\\
%&&&1&
%\end{bmatrix}
%\]
%where $z$ is a primitive $d$th root of unity in $\CC$.  [Possibly mention RRS again: different primitive roots give non-conjugate elements.]


\section{Introduction}

The motivation for this abstract is the following uniform formula of
Chapuy--Stump for the generating function for the number of factorizations of a fixed
Coxeter element by reflections in any complex reflection group.

\begin{theorem}[Chapuy--Stump \cite{CS}]
\label{thm:cs}
Let $W$ be an irreducible well-generated complex reflection group of
rank $n$. Let $c$ be a Coxeter element in $W$, let $\mathcal{R}$ and $\mathcal{R}^*$ be
the set of all reflections and all reflecting hyperplanes in $W$, and
for $\ell \geq 1$ let $N_{\ell}(W) := \#\{
(\tau_1,\ldots,\tau_{\ell}) \in \mathcal{R}^{\ell} \mid \tau_1\cdots
\tau_{\ell} =  c \bigr\}$ be the number of factorizations of $c$ as a
product of $\ell$ reflections in $\mathcal{R}$. Then
%\begin{equation}
\[
\sum_{\ell \geq 0} N_{\ell}(W)\frac{t^{\ell}}{\ell!}  \,=\, \frac{1}{|W|} \left( e^{t|\mathcal{R}|/n}
  - e^{-t |\mathcal{R}^*|/n} \right)^n.
\]
%\end{equation}
\end{theorem}

Near $t=0$, the generating function gives the well known result that the number of shortest factorizations of a Coxeter element is $n! h^n/|W|$, where $h$ is the Coxeter number of $W$. In addition, when $W$ is the symmetric group $\Symm_{n}$, the result above reduces
to a result of Jackson \cite{J} on the generating function for factorizations of
the $n$-cycle $(12\cdots n)$ into transpositions.  Chapuy and Stump prove their result
by an algebraic approach with irreducible
characters that dates back to Frobenius. 
(Recently, Michel \cite{JM} gave a uniform proof of this result when $W$ is a Weyl group using Deligne--Lusztig representations.)

A natural question is whether there are extensions to complex
reflection groups of other factorization results in the symmetric
group. In the same paper, Jackson \cite{J} gave formulas for the
generating polynomial of factorizations of a fixed $n$-cycle as a
product of a fixed number of factors, keeping track of the number of cycles of each factor. We state the result for two factors, as reformulated by Schaeffer and Vassilieva.

\begin{theorem}[{Jackson, Schaeffer--Vassilieva \cite{J,SV}}]
\label{S_n theorem}
Let $c$ be a fixed $n$-cycle in $\Symm_n$, and for integers $r, s$ let $a_{r, s}$ be the number of pairs $(u, v)$ of elements in $\Symm_n$ such that $u$ has $r$ cycles, $v$ has $s$ cycles, and $u \cdot v = c$.  Then
\[
\frac{1}{n!} \cdot \sum_{r, s \geq 1} a_{r, s} x^r y^s = \sum_{p,q \geq 1} \binom{n-1}{p-1; q-1; n - p - q + 1} \frac{(x)_{p}}{p!} \frac{(y)_{q}}{q!},
\]
where $(x)_p$ denotes the falling factorial $(x)_p := x(x - 1)\cdots (x - p + 1)$. In particular, the leading coefficient  $a_{r,n-1-r}$ is the Narayana number $\Nar_A(n,r):=\frac{1}{n} \binom{n}{r}\binom{n}{r-1}$.
\end{theorem}


  


In this abstract we give analogues of this result, and its generalizations to $k$ factors, for two infinite families of complex reflection groups:  the group $G(d,1,n)$ of $n \times n$ 
%monomial matrices whose nonzero entries are all $d$th roots of unity 
matrices having one nonzero entry in every row and column, each of which is a $d$th root of unity
({\em i.e.}, the wreath product $(\ZZ/d\ZZ)  \wr \mathfrak{S}_n$; at
$d = 2$, the Coxeter group of type $B_n$) and its subgroup $G(d,d,n)$  (at $d = 2$, the Coxeter group of type $D_n$).  
% Unlike in the real case, there is some ambiguity about the ``correct" definition of the Coxeter elements, with more and less general definitions appearing in the literature, and under the more general definitions it is not the case that all Coxeter elements are conjugate inside the group.  (See the discussion in [Reiner--Ripoll--Stump].)  However, thanks to the results of [Reiner--Ripoll--Stump], the enumerations we're interested in do not depend on the choice of Coxeter element, so we may take any Coxeter element we like.  The elements
% \[
% \begin{bmatrix}
% &&&&z\\
% 1&&&&\\
% &1&&&\\
% &&\ddots&&\\
% &&&1&
% \end{bmatrix}, \quad
% \begin{bmatrix}
% z &&&&\\
% &&&&z^{-1}\\
% &1&&&\\
% &&\ddots&&\\
% &&&1&
% \end{bmatrix}
% %\in G(\infty, 1, n)
% \]
% %is sent to a Coxeter element in the projection onto $G(d, 1, n)$
% are Coxeter elements in $G(d, 1, n)$ and $G(d,d,n)$ respectively, whenever $z$ is a primitive $d$th root of unity. 
The analogue of an $n$-cycle in a complex reflection group is a \emph{Coxeter element}.  In $G(d, 1, n)$, the Coxeter elements are the matrices whose underlying permutation is an $n$-cycle and in which the product of the nonzero elements is a primitive $n$th root of unity.  (The Coxeter elements in $G(d, d, n)$ are described in \cref{sec:ddn}.)  The analogue of the number of cycles of a group element is the \emph{fixed space dimension}.  Our results for $G(d, 1, n)$ are in terms of the polynomials
\[
    (x)_k^{(d)} := x(x-d)(x-2d)\cdots (x-(k-1)d) = \prod_{i = 1}^k (x - e^*_i).
\]
Here the roots $e^*_i$ are the \emph{coexponents} of this group, one of the fundamental sets of invariants associated to every complex reflection group.

\begin{theorem} \label{thm: main G(d1n)}
For $d > 1$, let $G = G(d, 1, n)$ and let $a^{(d)}_{r,s}$ be the number of factorizations of a fixed Coxeter element $c$ in $G$ as a product of two
elements of $G$ with fixed space dimensions $r$ and $s$,
respectively. Then
\begin{equation} \label{eq main G(d,1,n)}
\frac{1}{|G|} \sum_{r,s \geq 0} a^{(d)}_{r,s} x^r y^s  \,=\, \sum_{p,q \geq 0}
 \binom{n}{p; q; n - p - q} \frac{(x - 1)^{(d)}_{p}}{d^pp!} \frac{(y - 1)^{(d)}_{q}}{d^qq!}.
 \end{equation}
 In particular, the leading coefficient $a^{(d)}_{r,n-r}$ is the type $B$ Narayana number $\Nar_B(n,r):=\binom{n}{r}^2$.
 \end{theorem}

%\begin{theorem}
%\label{G(d1n) many factors theorem}
%Let $G = G(d, 1, n)$ and let
%\[
%F_d(x_1,x_2,\ldots,x_k) := \frac{1}{|G|^{k-1}} \sum_{r_1,\ldots,r_k}
%a_{r_1,\ldots,r_k} x_1^{r_1} \cdots x_k^{r_k},
%\]
%where $a_{r_1,\ldots,r_k}$ is the number of factorizations of a Coxeter element $c$ in $G$ as a product of $k$
%elements of $G$ with fixed space dimensions $r_1,\ldots,r_k$
%respectively.
%If $d>1$ then 
%\[
%\frac{1}{|G|^{k-1}} \sum_{r_1,\ldots,r_k}
%a_{r_1,\ldots,r_k} x_1^{r_1} \cdots x_k^{r_k} = \sum_{p_1,\ldots,p_k \geq 0}
%M^n_{p_1,\ldots,p_k} \frac{(x - 1)^{(d)}_{p_1}}{d^{p_1}p_1!} \cdots \frac{(x_k - 1)^{(d)}_{p_k}}{d^{p_k}p_k!},
% \]
%where $M^n_{p_1,\ldots,p_k}$ is defined in \eqref{definition M coeff}.
%\end{theorem}

In \cref{sec:d1n}, we give a combinatorial proof of this result and its generalization to $k$ factors. As a special case, we recover the Chapuy--Stump result for $G(d,1,n)$ (see \cref{sec:CS}). Our proof works directly with the group elements and permutations. However, the proof could also be written in terms of {\em maps} \cite{LZ,GS}, as in \cite{B,BM1,CFF,SV} (for example). 

Our results for the subgroup $G(d,d,n)$ involve a notion of
  \emph{transitive} factorization, defined  in \cref{sec:ddn}
  below, and are in terms of the polynomials
\[
\poly{x}{d}{k} := (x - (k - 1)(d - 1)) \cdot (x - 1)^{(d)}_{k - 1} = \prod_{i = 1}^k (x - e^*_i),
\]
where again the $e^*_i$ are the coexponents of the group. 
%\jbl{It involves a notion of \emph{transitive} factorization, defined}

\begin{theorem} \label{thm:mainG(ddn)}
For $d > 1$, let $G = G(d, d, n)$ and let $b^{(d)}_{r,s}$ be the number of \emph{transitive} factorizations of a Coxeter element $c$ in $G$ as a product of two
elements of $G$ with fixed space dimensions $r$ and $s$,
respectively. Then
\begin{equation} \label{eq main G(d,d,n)}
\frac{1}{d^{n-1} (n-1)(n-1)!} \sum_{r,s \geq 0} b^{(d)}_{r,s} x^r y^s \,=\, \sum_{p,q \geq 1}
 \binom{n-2}{p-1; q-1; n -p - q} \frac{\poly{p}{d}{x}}{d^{p-1} p!}
 \frac{\poly{q}{d}{x}}{d^{q-1} q!}.
 \end{equation}
 In particular, the leading term $b^{(d)}_{r,n-r}$ equals $dn \cdot \Nar_A(n-1,r)$.
 \end{theorem}

In \cref{sec:ddn}, we sketch a proof of this result and its generalization to $k$ factors using character theory. As a special case, we recover the Chapuy--Stump result for $G(d,d,n)$. 

In \cref{sec:rank 2}, we also include some suggestive evidence from factorization data of rank 2 complex reflection groups that indicates that the results above could be particular cases of a uniform statement like the Chapuy--Stump result.


\section{Known factorization results in $\mathfrak{S}_n$}

\cref{S_n theorem} is a special case of a more general result for factorizations of an $n$-cycle into $k$ factors. To state this theorem we need to define a number that counts certain tuples of sets.
Given a positive integer $k$ and nonnegative integers $n$ and $p_1,\ldots,p_k$, define
\begin{equation} \label{definition M coeff}
M^n_{p_1,\ldots,p_k} := \!\! \sum_{t=0}^{\min(p_i)} \!\! (-1)^t \binom{n}{t}
\prod_{i=1}^k \binom{n-t}{p_i-t} = [x_1^{p_1} \cdots x_k^{p_k}] \Bigl(
  (1+x_1)\cdots (1+x_k) - x_1\cdots x_k\Bigr)^n,
\end{equation}
which counts $n$-tuples $(S_1,\ldots,S_n)$ of proper subsets $S_i
\subsetneq [k]$ such that exactly $p_j$ of the sets  contain $j$. From this
interpretation, it is easy to see that $M^n_{p_1,p_2}$ is given by a
multinomial coefficient $\binom{n}{p_1; p_2; n-p_1-p_2}$ and that the
 $M^n_{\bf p}$  satisfy the following recurrence.

\begin{proposition} \label{prop:recurrence Ms}
One has
$ \displaystyle
M^n_{p_1,\ldots,p_k} \,=\, \sum_{\varnothing \neq S\subseteq [k]}
M^{n-1}_{{\bf p} - {\bf 1} +  {\bf e}_{S}}
$
where ${\bf 1}$ is the all-ones vector and ${\bf e}_{S}$
denotes the indicator vector for the set $S$. 
\end{proposition}

Let $c$ be a fixed $n$-cycle in $\Symm_n$, and for integers
$r_1,\ldots,r_k$ let $a_{r_1,\ldots,r_k}$ be the number of $k$-tuples
$(\pi_1,\ldots,\pi_k)$ of elements in $\Symm_n$ such that $\pi_i$ has $r_i$
cycles for $i=1,\ldots,k$, and $\pi_1 \cdots  \pi_k = c$. 

\begin{theorem}[{Jackson \cite{J}}]
\label{S_n theorem k factors}
One has
\begin{equation} \label{eqn S_n k factors}
\frac{1}{(n!)^{k-1}} \cdot \sum_{r_1,\ldots,r_k \geq 1} a_{r_1,
  \ldots, r_k} x_1^{r_1} \cdots x_k^{r_k} = \sum_{p_1,\ldots,p_k \geq
  1}  M^{n-1}_{p_1-1,\ldots,p_k-1} \frac{(x_1)_{p_1}}{p_1!} \cdots \frac{(x_k)_{p_k}}{p_k!}.
\end{equation}
\end{theorem}

Jackson's proof used the Frobenius approach with irreducible
characters. Bijective proofs of the case $k=2$ were given by
Schaeffer--Vassilieva \cite{SV}, Chapuy--F\'eray--Fusy \cite{CFF}, and
Bernardi \cite{B}. 
Bernardi--Morales \cite{BM1,BM2} extended Bernardi's approach to give a combinatorial proof of
Jackson's formula for all $k$ in terms of maps. These combinatorial proofs use an interpretation of the change of basis in \eqref{S_n theorem k factors} that we describe now. 

Let $\mathcal{C}_{p_1,\ldots,p_k}$ be the set of factorizations in
$\mathfrak{S}_n$ of the fixed $n$-cycle $c$ as a product $\pi_1\cdots
\pi_k$ such that for each $i$, the cycles of $\pi_i$ are colored
with the colors in $[p_i]$, and every color is used at least once. Let
  $c_{p_1,\ldots,p_k}$ be the number of such factorizations.

\begin{proposition}
With $a_{r_1, \ldots, r_k}$ and $c_{p_1, \ldots, p_k}$ as above, one has
\begin{equation} \label{eq change of basis}
\sum_{r_1,\ldots,r_k \geq 1} a_{r_1,
  \ldots, r_k} x_1^{r_1} \cdots x_k^{r_k} = \sum_{p_1,\ldots,p_k \geq 1} c_{p_1,\ldots,p_k} \binom{x_1}{p_1}\cdots \binom{x_k}{p_k}.
\end{equation}
\end{proposition}

\begin{proof}
Let each $x_i$ be a nonnegative integer. The LHS above counts  
%\begin{itemize}
%\item 
factorizations of the cycle $(12\cdots n)$ as a product
  $c = \pi_1\cdots \pi_k$, where
%\item 
for $i=1,\ldots,k$, each cycle of $\pi_i$ is colored with a
  color in $[x_i]$.
%\end{itemize}
These colored factorizations are also counted by the RHS above: for
$p_1,\ldots,p_k \in \ZZ_{> 0}$ and $i=1,\ldots,k$, choose $p_i$
colors from $x_i$ colors available and a colored factorization $\mathcal{C}_{p_1,\ldots,p_k}$ where exactly $p_i$ colors are used in
the factor $\pi_i$.
\end{proof}


\section{The group $G(d,1,n)$}\label{sec:d1n}

The conjugacy classes in $G(d, 1, n)$ are uniquely determined by the following combination of data: first, one needs to know the cycle type of the underlying permutation ({\it i.e.}, when we take the projection $G(d, 1, n) \twoheadrightarrow \Symm_n$ whose kernel is exactly the diagonal matrices), and then for each cycle one needs to know the product of the roots of unity that appear in it.  Equivalently, for each power $0, \ldots, d - 1$, which we call the \emph{weight}, we have a partition (possibly empty) recording the lengths of the cycles whose product of elements is that power of $\exp(2\pi i/d)$.  Thus, conjugacy classes in $G(d, 1, n)$ are unambiguously indexed by tuples $(\lambda^{(0)}, \ldots, \lambda^{(d - 1)})$ of partitions of total size $n$. The following proposition is straightforward.
\begin{prop}
\label{prop:reflection length}
The fixed space dimension of an element $w$ in $G$ whose conjugacy class is indexed by $(\lambda^{(0)}, \ldots, \lambda^{(d - 1)})$ is equal to $\ell(\lambda^{(0)})$, the number of cycles of weight $0$ in $w$.
\end{prop}

We are now prepared to state our main enumerative theorem  for $G(d, 1, n)$.

\begin{theorem}
\label{G(d1n) many factors theorem}
For $d > 1$, let $G = G(d, 1, n)$, so that $|G| = d^n n!$, let $c$ be a fixed Coxeter element in $G$, and let $a^{(d)}_{r_1,\ldots,r_k}$ be the number of factorizations of $c$ as a product of $k$ elements of $G$ with fixed space dimensions $r_1,\ldots,r_k$,
respectively.  Then
\[
\frac{1}{|G|^{k-1}} \sum_{0 \leq r_1,\ldots,r_k \leq n}
a^{(d)}_{r_1,\ldots,r_k} x_1^{r_1} \cdots x_k^{r_k} \,=\, \sum_{0 \leq p_1,\ldots,p_k \leq n}
M^n_{p_1,\ldots,p_k} \frac{(x_1 - 1)^{(d)}_{p_1}}{d^{p_1}p_1!} \cdots \frac{(x_k - 1)^{(d)}_{p_k}}{d^{p_k}p_k!},
 \]
where $M^n_{p_1,\ldots,p_k}$ is defined in \eqref{definition M coeff}.
\end{theorem}

The case of two factors $k=2$ follows immediately  as a corollary.

\begin{proof}[Proof of \cref{thm: main G(d1n)}]
Substitute $k = 2$ in \cref{G(d1n) many factors theorem} and use the fact that  $M^n_{p_1,p_2} = \linebreak \binom{n}{p_1,p_2,n-p_1-p_2}$.
\end{proof}



\begin{proof}[Combinatorial proof of \cref{G(d1n) many factors theorem}]
It is enough to show that if we define constants $C_{p_1, \ldots,p_k}$ by 
\[
\sum_{r_1,\ldots,r_k} a^{(d)}_{r_1,\ldots,r_k} (x_1d+1)^{r_1} \cdots
(x_kd+1)^{r_k} \,=\, \sum_{p_1,\ldots,p_k} C_{p_1,\ldots,p_k}
\binom{x_1}{p_1} \cdots \binom{x_k}{p_k},
\]
then $C_{p_1,\ldots,p_k} = (d^nn!)^{k-1} M^n_{p_1,\ldots,p_k}$.  
To prove this polynomial identity, it suffices to prove that it is valid when each of the $x_i$ is a nonnegative integer.  In this case, the LHS counts 
%\begin{compactitem}
%\item 
factorizations of $c$ as a product $c = u_1 \cdots u_k$, where
%\item 
for $i=1,\ldots,k$, each cycle of weight $0$ in $u_i$ is colored with a color in
  $X_i:=\{0_i, 1_i, 2_i, \ldots, (x_id)_i\}$, and 
%\item 
the cycles $u_i$ of weights other than $0$ are colored with the color $0_i$. 
%\end{compactitem}
(The subscripts $i$ on the colors are to emphasize that, for example, the allowable colors for cycles of $u_1$ are not the same as the allowable colors for cycles of $u_2$.)

Within the color set $X_i$, a \emph{$d$-strip} is any of the following collections of $d$ consecutive
colors: $\{1_i,\ldots,d_i\}$, $\{(d+1)_i,\ldots,(2d)_i\}$, \ldots, $\{((x_i-1)d+1)_i,\ldots,(x_id)_i\}$.  Thus, for each $i$, there are exactly $x_i$ $d$-strips in $X_i$ (and the color $0_i$ does not belong to any $d$-strip).
We use these $d$-strips to divide the set of colored factorizations counted by the LHS into disjoint subsets, as follows: for $p_1, \ldots, p_k \in \ZZ_{\geq 0}$, consider the colored factorizations in which colors from exactly $p_i$ of the $d$-strips in $X_i$ are used to color cycles of the factor $u_i$.  The number of ways to choose the $p_i$ $d$-strips is $\binom{x_i}{p_i}$; consequently, the coefficient $C_{p_1,\ldots,p_k}$ on the RHS counts 
%\begin{compactitem}
%\item 
factorizations of $c$ as a product $c = u_1 \cdots u_k$ where
%\item  
for $i=1,\ldots,k$, each cycle of weight $0$ in $u_i$ is colored with colors from a prescribed set of $p_i$ $d$-strips in $X_i$, or with the color $0_i$, in such a way that at least one color is used from each of the prescribed $d$-strips, and 
%\item 
the cycles $u_i$ of weights other than $0$ are colored with the color $0_i$. 
%\end{compactitem}
We now wish to relate this number to certain factorizations in the symmetric group.

We claim there is the following connection between the $C$s (the numbers of colored factorizations in $G(d,1,n)$) and the
$c$s (the numbers of colored factorizations in $\mathfrak{S}_n$), with proof given below.

\begin{lemma}
\label{lem:d1n}
For any ${\bf p} = (p_1, \ldots, p_k)$ in $(\ZZ_{\geq 0})^k$, we have
$\displaystyle
C_{\bf p} = d^{(k-1)n} \sum_{\varnothing \neq S\subseteq [k]}
c_{{\bf p} + {\bf e}_S}
$
where ${\bf e}_S$ is the indicator vector for $S$.
\end{lemma}

We have by Jackson's \cref{S_n theorem k factors} that $c_{{\bf p} + {\bf e_S}} =
(n!)^{k-1} \cdot M^{n-1}_{{\bf p} -{\bf 1} + {\bf e}_S}$ where $\bf 1$ is the all-ones vector.
Then \cref{G(d1n) many factors theorem} follows by \cref{lem:d1n} and \cref{prop:recurrence Ms}.
%
% \begin{lemma}
% \[
% \sum_{\varnothing \neq S\subseteq [k]}  M^{n-1}_{{\bf p-{\bf 1}} + {\bf
%     e_{S}}} = M^n_{p_1,\ldots,p_k}.
% \]
% \end{lemma} 
%
%
\end{proof}

\begin{proof}[Proof of \cref{lem:d1n}]
Given a colored factorization $c = u_1 \cdots u_k$ of the Coxeter
element $c$ for $G(d, 1, n)$ of the relevant kind, we associate to it
a colored factorization $(1 \cdots n) = \pi_1 \cdots \pi_k$ in $\Symm_n$, as follows: $\pi_i$ is the projection of $u_i$ in $\Symm_n$; if a cycle of $u_i$ is colored with a color in the $d$-strip $\{((a - 1)d + 1)_i, \ldots, (ad)_i\}$, then the corresponding cycle of $\pi_i$ is colored with color $a$; if a cycle of $u_i$ is colored with color $0_i$, then the corresponding cycle of $\pi_i$ is colored with color $0$.  Thus, in the resulting colored factorization of $(1 \cdots n)$, the $i$th factor is colored in either $p_i$ or $p_i + 1$ colors, with every color appearing.  Let $S \subseteq [k]$ denote the set of indices $i$ such that $\pi_i$ is colored in $p_i + 1$ colors (rather than $p_i$); equivalently, it is the set of indices $i$ such that some cycle of $u_i$ is colored with color $0_i$.

First, we observe that $S \neq \varnothing$: the product $c = u_1 \cdots u_k$ has total weight nonzero, so at least one of the factors $u_i$ has
a cycle with weight different from zero. Such a cycle is colored with
the special color $0_i$, and so at least for this value of $i$ we have $i \in S$. 
Thus the collection of underlying
factorizations is in the disjoint union of pieces
$\mathcal{C}_{{\bf p} + {\bf e}_S}$ for nonempty sets $S\subseteq [k]$. 

Second, we must consider how many preimages each factorization in
$\mathcal{C}_{{\bf p} + {\bf e}_S}$ has under this map.  To choose a
preimage, we must assign weights to the entries of each factor $\pi_i$
in such a way that the product of the resulting factors $u_i$ really
is the Coxeter element $c$, \emph{and} so that in each $u_i$, any
factor of nonzero weight was originally colored by the color $0_i$;
and we must choose one of $d$ colors from a $d$-strip for each of the
cycles in $u_i$ that corresponds to a cycle in $\pi_i$ of nonzero
color.

%\jbl{explaining the power of $d$ -- new version}
In order to do this, we consider a too-large set of factorizations in $G(d, 1, n)$: we choose a total order on all the entries of all the $\pi_i$, in such a way that the last entry chosen belongs to a cycle of color $0_j$ for some $j$.  (Note that such cycles must exist, since $S \neq \varnothing$.)  Then we weight the entries in order, choosing the weights arbitrarily except in two cases: if an element belongs to a cycle of nonzero color and is the last element in its cycle to be weighted, we assign it the unique weight so that the total weight of its cycle is $0$; and we choose the weight of the specially selected final element so that the total weight of all elements is $1$.  (These two exceptions never conflict because the special element was chosen in a cycle of color $0$.)  The number of ways to perform these choices is $d^{nk - 1 - \#(\textrm{cycles not colored } 0)}$.  Finally, for each cycle of $\pi_i$ that is colored some nonzero color, there are $d$ choices for the color in the associated $d$-strip of the corresponding cycle of the lift $u_i$ of $\pi_i$; this contributes a factor of $d^{\#(\textrm{cycles not colored } 0)}$, for a total of $d^{nk- 1}$ lifts.

Each lift is a colored factorization $u_1 \cdots u_k$ in $G(d, 1, n)$ of some element $c^*$ of weight $1$ whose underlying permutation is the $n$-cycle $(1 \cdots n)$.  The number of such elements is $d^{n - 1}$; they are all conjugate to $c$ by some diagonal matrix $a$ in $G(d, 1, n)$.  Moreover, since $a$ is a diagonal matrix, conjugating any $w \in G(d, 1, n)$ by $a$ preserves the weight of every cycle of $w$.  Consequently, conjugation by $a$ extends to a bijection between factorizations of $c$ and factorizations of $c^*$ that respects the underlying permutation of each factor and the weight of each cycle of each factor.  Thus, in particular it gives a bijection between the lifts of $\pi_1 \cdots \pi_k$ that factor $c$ and those that factor $c^*$.  Thus, of the total $d^{nk - 1}$ lifts, exactly $\frac{1}{d^{n - 1}} \cdot d^{nk - 1} = d^{n(k - 1)}$ of them are factorizations of $c$.  This completes the proof of the lemma.
\end{proof}


\subsection{Specializations and leading terms for factorizations of $G(d,1,n)$}

We first remark on two natural specializations of the factorization results
for $G(d,1,n)$. Let $F_d(x,y)$ denote the RHS of \eqref{eq main
  G(d,1,n)}. One can check from \cref{thm: main G(d1n)} that $F_d(1,1) = \binom{n}{0;0;n}\cdot 1 =1$ as expected: by the definition of $F_d$, we have $F_d(1,1)= \frac{1}{|G|} \cdot |G|=1$. The next specialization is more interesting.

\begin{proposition}
One has
$\displaystyle
F_d(x,1) = \frac{1}{|G|} \sum_{g \in G} x^{\dim \fix(g)} = \frac{1}{|G|} \prod_{i=1}^n (x+id-1).
$
\end{proposition}

\begin{proof}
By \cref{thm: main G(d1n)}, we have 
%\begin{align*}
\[
F_d(x, 1) = 
\sum_{p \geq 0} \binom{n}{p} \frac{(x - 1)_p^{(d)}}{d^p p!} = 
% \sum_{p = 0}^n \binom{n}{p} \binom{(x - 1)/d}{p} = 
\binom{n + (x - 1)/d}{n} = 
\frac{1}{|G|} \prod_{i=1}^n (x+id-1),
\]
%\end{align*}
where the %third 
second
equality is the Vandermonde identity.
On the other hand, by the definition of $F_d$ we have
\[
F_d(x,1) = \frac{1}{|G|} \sum_{g \in G} x^{\dim \fix(g)},
\]
so we recover in this case the general fact that the generating function for fixed space dimension in a finite complex reflection group splits into linear factors, with roots equal to $1 - d_i$ where $\{d_i\}$ are the \emph{degrees} of the group. 
\end{proof}

Lastly, we show that the leading term $a_{r,n-r}$ of $|G| \cdot F_d(x,y)$ is given by the type B Narayana number $\binom{n}{r}^2$
\href{https://oeis.org/A008459}{A008459} \cite[Table 12.3]{KP}.  In
particular, it is independent of $d$.

\begin{corollary}
For $d > 1$, let $G=G(d,1,n)$, and let $a_{r,n-r}$ be the number of factorizations of a
Coxeter element $c$ in $G$ as a product of two elements $u$ and $v$
with fixed space dimension $r$ and $n-r$ respectively, then $a_{r,n-r}
= \binom{n}{r}^2$.
\end{corollary}

\begin{proof}
The leading coefficients of \eqref{eq main G(d,1,n)} have total degree
$n$. Extracting such coefficients from the RHS gives $a_{r,n-r} = |G|
\binom{n}{r; n-r; 0}\frac{1}{r! (n-r)! d^n}$ which equals the desired formula.
\end{proof}





\section{The subgroup $G(d,d,n)$}
\label{sec:ddn}

The hyperoctahedral group of signed permutations (the Coxeter group of type $B_n$) has an index-$2$ subgroup of ``even-signed permutations'' (the Coxeter group of type $D_n$), consisting of matrices in which the total number of negative entries is even.  Similarly, for every $d$, the group $G(d, 1, n)$ has an irreducible rank-$n$ well generated reflection subgroup: the group $G(d, d, n)$ of $n \times n$ weighted permutation matrices in which the product of the nonzero entries is $1$ (equivalently, in which the total weight is $0$), of order $|G(d, d, n)| = \frac{|G(d, 1, n)|}{d} = d^{n - 1} n!$.  The Coxeter elements in $G(d, d, n)$ are the elements whose underlying permutation is an $(n - 1)$-cycle and the weight of the fixed point is $1$ (and so also the weight of the $(n - 1)$-cycle is $-1$).

Most of the results in this section rely on the Frobenius character approach, which is based on the following lemma.

\begin{lemma}[{{Frobenius, {\it e.g.} \cite[Ex.~7.67(b)]{EC2}}}]
\label{frobenius}
Let $W$ be a finite group, $g$ an element of $W$, and $A_1, \ldots, A_k$ subsets of $W$ that are each closed under conjugation by elements of $W$.  Then the number of factorizations of $g$ as a product $g = t_1 \cdots t_k$, such that for each $i$ the factor $t_i$ is required to lie in the set $A_i$, is equal to
\[
\frac{1}{|W|} \sum_{\lambda \in \Irr(W)} \dim(\lambda) \chi_\lambda(g^{-1}) \normchi_\lambda(z_1) \cdots \normchi_{\lambda}(z_k),
\]
where $\Irr(W)$ is the set of irreducible representations of $W$, $\dim(\lambda)$ is the dimension of the representation $\lambda$, $\chi_\lambda$ is the character associated to $\lambda$, $\normchi_\lambda = \frac{\chi_\lambda}{\dim(\lambda)}$ is the normalized character associated to $\lambda$, and for $i = 1, \ldots, k$, $z_i$ is the formal sum in the group algebra of elements in $A_i$.
\end{lemma}


\subsection{Results in $\mathfrak{S}_n$ for factorizations of an $(n - 1)$-cycle}


%\begin{conjecture}
%\label{unexplained identity}
%\begin{align*}
%\sum_{m=-1}^{n-3}(-1)^m  & (n-2-m)m\binom{n}{m+1}
%\binom{n-1-m}{r-1-m}\binom{n-1-m}{s-1-m} =
%\frac{(n)_{r+s-2}}{r!s!} \times \\
% & \times \left( {n}^{3}+ \left( rs-2\,s-2\,r+2 \right) {n}^{2}-
% \left( r{s}^{2}-{s}^{2}-3\,rs+s+{r}^{2}s+r+1-{r}^{2} \right) n+
% \left( rs+r+s-2 \right)  \left( r-1 \right)  \left( s-1 \right)
%  \right)\\
%&= (n-1)\binom{n}{r,s,n-r-s} + \binom{n}{r-1,s-1} \left(
%  (n+1)(n-r-s) + (s+1)(r+1)-2\right)
%\end{align*}
%\jbl{This is definitely false as written for $r = s = n > 2$, when the RHS here gives $0$ but the true answer is $(-1)^{n + 1} \cdot (n - 1)$.  Otherwise it looks right.}
%\end{conjecture}

%\begin{cor}
%Let $c$ be a fixed $(n-1)$-cycle in $\mathfrak{S}_n$, and for integers $r, s$ let $a_{r, s}$ be the number of pairs $(u, v)$ of elements in $\Symm_n$ such that $u$ has $r$ cycles, $v$ has $s$ cycles, and $u \cdot v = c$.  Then
%\[
%\widetilde{F}_n(x, y) := 
%\frac{1}{n!} \cdot \sum_{r, s} a_{r, s} x^r y^s = \sum_{r, s} \cdot \left(????\right) \cdot \frac{(x)_{r}}{r!} \frac{(y)_{s}}{s!}.
%\]
%\end{cor}
%\begin{proof}
%From Prop~\ref{n - 1 cycle prop}, for $1 \leq r, s \leq n$ we have that
%\[
%\left[ \frac{(x)_{r}}{r!} \frac{(y)_{s}}{s!} \right] \widetilde{F}_n(x, y)
%=
%\binom{n - 1}{r - 1} \binom{n - 1}{s - 1} + (-1)^n [r = s = n] + \frac{rs}{n^2(n - 1)} \sum_{m=1}^{n-3}(-1)^m (n-2-m)m \binom{n}{m+1} \binom{n-1-m}{r-1-m}\binom{n-1-m}{s-1-m}
%.\]

%{\bf In the case that $r = s = n$}, this becomes
%\begin{align*}
%\left[ \frac{(x)_{n}}{n!} \frac{(y)_{n}}{n!} \right] \widetilde{F}_n(x, y)
%& =
%1 + (-1)^n + \frac{1}{n - 1} \sum_{m=1}^{n-3}(-1)^m (n-2-m)m \binom{n}{m+1} \\
%& = 1 + (-1)^n + \frac{1}{n - 1} \cdot \begin{cases} 0 & n < 4 \textrm{ or } n \textrm{ odd} \\
%-2(n - 1) & \textrm{o.w.} \end{cases}\\
%& = \begin{cases}
%2 & n = 2 \\ 0 & \textrm{o.w.}\end{cases}.
%\end{align*}
%\jbl{This really should be $1$ for $n = 2$.  Missing and $n!$ somewhere, maybe?}

%{\bf In the case that $\min(r, s) < n$}, we apply Conjecture~\ref{unexplained identity} to get 
%\begin{align*}
%\left[ \frac{(x)_{r}}{r!} \frac{(y)_{s}}{s!} \right] \widetilde{F}_n(x, y)
%& = \binom{n - 1}{r - 1} \binom{n - 1}{s - 1} + \frac{rs}{n^2(n - 1)} \cdot \left(
%\underbrace{(n-1)\binom{n}{r,s,n-r-s} + \binom{n}{r-1,s-1} \left(
 % (n+1)(n-r-s) + (s+1)(r+1)-2\right)}_{\textrm{sum incl. } m = -1}
%-
%\underbrace{(n - 1) \binom{n}{r} \binom{n}{s}}_{m = -1}
%\right) \\
%& = \frac{rs}{n^2(n - 1)} \cdot \left((n-1)\binom{n}{r,s,n-r-s} + \binom{n}{r-1,s-1} \left(
%  (n+1)(n-r-s) + (s+1)(r+1)-2\right)\right) \\
%& = \frac{(n - 2)!}{n \cdot (r - 1)!(s - 1)!(n - r - s + 2)!} \left((n - 1)(n - r - s + 2)(n - r - s + 1) +  rs( (n+1)(n-r-s) + (s+1)(r+1)-2)\right)
%\end{align*}
%\jbl{and the question is, what is a nice way to write this???}
%\end{proof}

If one factors an $(n - 1)$-cycle $c$ in $\Symm_n$ as a product of other permutations, there are two possibilities: either every factor shares $c$'s fixed point, or some factor acts nontrivially on it.  The factorizations in the former case correspond to factorizations of an $(n-1)$-cycle in $\Symm_{n - 1}$.  The factorizations in the latter case have a more elegant description: they are exactly the factorizations in which the factors act transitively on the set $[n]$.  The study of transitive factorizations plays an important role in the field of permutation factorizations; it is present already in the late 19th century work of Hurwitz \cite{H}. 

% We could not find the following results in the literature but John Irving had an equivalent statement for the two factor case in his research notes (private communication). For brevity, we sketch their proofs.

% \begin{theorem}
% Let $c$ be a fixed $(n-1)$-cycle in $\mathfrak{S}_n$.  For integers
% $r, s$ let $b_{r, s}$ be the number of pairs of elements $(u,v)$ in $\mathfrak{S}_n$ such that $u$ has $r$ cycles, $v$ has $s$ cycles, $u\cdot v = c$, and $u$ and $v$ are a transitive factorization. Then
% \begin{align}
% %\label{n - 1 cycle all %factorizations}
% %\sum_{r, s} a_{r, s} x^r y^s %& = (n + xy - 1)\cdot (n - %1)! \cdot \sum_{p,q \geq 1}%       \binom{n-2}{p-1; q-1; n - p - q}
% %  \cdot \frac{(x)_{p}}{p!}
%                           %\frac{(y)_{q}}{q!} 
% %\\
% %
% %\intertext{and} 
% %
% \label{n - 1 cycle transitive factorizations}
% \sum_{r, s} b_{r, s} x^r y^s  & = (n - 1) \cdot (n - 1)! \cdot \sum_{p,q \geq 1}
% %                                           
%                                                   \binom{n-2}{p-1; q-1; n - p - q}
%   \cdot \frac{(x)_{p}}{p!}
%                                                   \frac{(y)_{q}}{q!}  
% \end{align}
% where the notation $(x)_k$ denotes the falling factorial $(x)_k = x(x - 1)\cdots (x - k + 1)$. 
% \end{theorem}



% \begin{proof}[Proof sketch]
% Given a factorization $u \cdot v = (1 \cdots (n - 1))$ of an $(n - 1)$-cycle as a product of two factors in $\Symm_{n - 1}$, there are exactly $n - 1$ locations into which $n$ can be inserted in the cycle notation for $u$ to create a permutation $u'$ in $\Symm_n$.  This insertion uniquely determines a second factor $v'$ in $\Symm_n$ such that $u' \cdot v' = (1 \cdots (n - 1))(n) = : c$.  One can show that $v'$ has the same number of cycles as $v$ and that this procedure produces every transitive factorization of $c$ exactly once.  Equation~\ref{n - 1 cycle transitive factorizations} follows immediately.
% %
% % Let $c = (1 \cdots n - 1)(n)$%.  The action of $c$ is transitive on $[n - 1]$.  Therefore, if $c = u \cdot v$, then $\langle u, v \rangle$ contains a subgroup that is transitive on $[n - 1]$ and fixes $n$.  The orbit structure of the larger group is a coarsening of the orbit structure of its subgroup, so either $\langle u, v \rangle$ fixes $n$ (in which case $n$ is a fixed point of both $u$ and $v$, and $(u, v)$ is a factorization of a long cycle in $\Symm_{n - 1}$) or it acts transitively on all of $[n]$.  
% % %
% % , and let $c = u \cdot v$ be a transitive factorization.
% % This means that $n$ appears in a cycle of $v$ with some other entries. Since $c = u\cdot v$, we have
% % \[
% % v = \cdots (\cdots a \; n \; b \cdots) \cdots \quad \text{and} \quad u = \cdots (\cdots b \; n \; a + 1 \cdots ) \cdots
% % \]
% % (where possibly $a=b$ or $b = a + 1$, and addition is understood modulo $n - 1$).  Deleting $n$ from the cycle notation of both $u$ and $v$ yields a factorization $u' \cdot v' = c'$ of the long cycle in $\Symm_{n - 1}$, in which $u'$ and $v'$ have respectively the same number of cycles as $u$ and $v$.  Going the other direction, given any factorization $u' \cdot v' = c'$ it is not hard to see that there are $n-1$ ways of inserting $n$ to produce a factorization of $c$ in $\mathfrak{S}_n$. 
% % %of the long cycle in $\Symm_{n - 1}$, choose any value $b \in [n - 1]$, and let $a = (v')^{-1}(b)$ (where possibly $a = b$).  Since $u' \cdot v' = c'$, we have $u'(b) = c'(a) = a + 1$ (again, understood cyclically), so that
% % %\[
% % %v' = \cdots (\cdots a \; b \cdots) %\cdots 
% % %\qquad
% % %\textrm{ and }
% % %\qquad
% % %u' = \cdots (\cdots b \; a + 1 \cdots %) \cdots
% % %\]
% % %(and again possibly these cycles could be $1$-cycles).  But then inserting $n$ into these two locations produces a factorization of $c$ in $\Symm_n$.  
% %
% % Taken together, these maps give a $1$-to-$(n - 1)$ correspondence between transitive factorizations of an $(n - 1)$-cycle in $\Symm_n$ and all factorizations of a long cycle in $\Symm_{n - 1}$ that preserves the number of cycles of the factors.  
% % %Consequently, $b_{r,s} = (n - 1) \cdot a_{r,s}(n-1)$,
% % %where $a_{r,s}(n-1)$ is the number of factorizations %of a long cycle in $\mathfrak{S}_{n-1}$ into two %factors with $r$ and $s$ cycles, respectively. 
% % Equation~\ref{n - 1 cycle transitive factorizations} follows immediately.
% \end{proof}

% More generally, we have the following counting theorem for transitive factorizations of an $(n - 1)$-cycle in $\Symm_n$ into more factors.

\begin{theorem}
\label{S_n (n-1) cycle theorem k factors}
Let $c$ be a fixed $(n-1)$-cycle in $\mathfrak{S}_n$. For integers
$r_1,\ldots,r_k$ let $b_{r_1,\ldots,r_k}$ be the number of $k$-tuples
$(u_1,\ldots,u_k)$ of elements in $\Symm_n$ such that $u_i$ has $r_i$
cycles for $i=1,\ldots,k$, $u_1 \cdots  u_k = c$, and $(u_1,\ldots,u_k)$ is a transitive factorization. Then 
\begin{align}
%\label{n - 1 cycle k factors all factorizations}
%\sum_{r_1,\ldots,r_k \geq 1} a_{r_1,
%  \ldots, r_k} x_1^{r_1} \cdots %x_k^{r_k} &= (n-1)!^{k-1}
%  \left(\frac{1}{n} + x_1\cdots x_k\right) \sum_{p_1,\ldots,p_k \geq
%  1} (p_1\cdots p_k M^n_{p_1,\ldots,p_k} + M^{n-2}_{p_1-1,\ldots,p_k-1}) \frac{(x_1)_{p_1}}{p_1!} \cdots
%  \frac{(x_k)_{p_k}}{p_k!},
%\\
\label{n - 1 cycle k factors transitive factorizations}
\sum_{r_1,\ldots,r_k \geq 1} b_{r_1,
  \ldots, r_k} x_1^{r_1} \cdots x_k^{r_k} &= \frac{(n-1)!^k}{n!}\sum_{p_1,\ldots,p_k \geq
  1}  M^{n}_{p_1,\ldots,p_k} \frac{(x_1)_{p_1}}{(p_1-1)!} \cdots
  \frac{(x_k)_{p_k}}{(p_k-1)!},
\end{align}
where $M^n_{p_1,\ldots,p_k}$ is as defined in \eqref{definition M coeff}.
\end{theorem}

We were surprised not to find this statement in the literature.  In the case of two factors, there is a simple combinatorial proof. We sketch here the algebraic proof for any number $k$ of factors.

\begin{proof}[Proof sketch]
By the Murnaghan--Nakayama rule, the character values on an $(n - 1)$-cycle in $\Symm_n$ are usually $0$, so the sum in \cref{frobenius} simplifies considerably.
%
%The character values on an $(n-1)$ cycle in $\mathfrak{S}_n$ are usually zero, except for hooks and {\em near hooks} $(n-m,2,1^{m-2})$ (this can be seen from the {\em Murnaghan--Nakayama rule}). So when applying Lemma~\ref{frobenius} the sum simplifies considerably. 
We first use this lemma on the generating polynomial of all factorizations of $c$ into $k$ factors (not necessarily transitive). We then subtract the generating polynomial of the non-transitive factorizations. It is not hard to see that this is just the product of $x_1\cdots x_k$ and the generating polynomial of factorizations of a long cycle in  $\mathfrak{S}_{n-1}$ into $k$ permutations. % We apply again Lemma~\ref{frobenius} to this generating polynomial. 
Unexpected cancellations occur when we subtract, %both expressions 
and we finally rewrite the expression in terms of the basis $(x_1)_{p_1}\cdots (x_k)_{p_k}$ to obtain the desired formula.
\end{proof}

\subsection{Results for transitive factorizations in $G(d,d,n)$}

As $G(d, 1, n)$ is a wreath product, it and its subgroups carry a natural permutation action: they act on $d$ copies of $[n]$ indexed by $d$th roots of unity.  (Equivalently, they act on $\{z^i e_j \colon 0 \leq i < d, 1 \leq j \leq n\}$ where $z$ is a primitive $d$th root of unity and $e_j$ are the standard basis vectors for $\CC^n$.)  The Coxeter elements for $G(d, 1, n)$ act transitively on this set, and consequently every factorization of a Coxeter element in $G(d, 1, n)$ is a transitive factorization.  However, the same is not true for the subgroup $G(d, d, n)$, where the underlying permutations of the Coxeter elements are $(n - 1)$-cycles.  In this abstract, we consider only the case of transitive factorizations of a Coxeter element in $G(d, d, n)$.  As mentioned in the introduction, our generating function in this case is in terms of the polynomials $\poly{k}{d}{x}$ defined by 
$\poly{0}{d}{x} = 1$, $\poly{1}{d}{x} = x$, and for $k > 1$ by
\begin{equation} \label{eq: equivalent expressions G(d,d,n) basis}
\poly{k}{d}{x} :=  \prod_{i = 1}^k (x - e^*_i) = (x - (k - 1)(d - 1)) \cdot (x - 1)^{(d)}_{k - 1}  = (x-1)^{(d)}_k + k(x-1)^{(d)}_{k-1},
\end{equation}
where the $e^*_i$ are the coexponents of the group $G(d, d, k)$.

\begin{theorem} \label{thm:mainG(ddn) k factors}
For $d > 1$, let $G = G(d, d, n)$ and let
 $b^{(d)}_{r_1,\ldots,r_k}$ be the number of transitive factorizations of a Coxeter element $c$ in $G$ as a product of $k$
elements of $G$ with fixed space dimensions $r_1,\ldots,r_k$, respectively. 
Then
\[
\sum_{r_1,\ldots,r_k
  \geq 0} b^{(d)}_{r_1,\ldots,r_k} x_1^{r_1}\cdots x_k^{r_k}
 \,=\, \frac{|G|^{k-1}}{n^k}\sum_{r_1,\ldots,r_k \geq 1}
 M^n_{r_1,\ldots,r_k} \frac{\poly{r_1}{d}{x_1}}{d^{r_1-1} (r_1-1)!} \cdots 
 \frac{\poly{r_k}{d}{x_k}}{d^{r_k-1} (r_k-1)!},
 \]
where $M^n_{r_1,\ldots,r_k}$ is as defined in \eqref{definition M coeff}.
 \end{theorem}

\begin{proof}[Proof sketch]
The character values on a Coxeter element are usually zero, so when applying \cref{frobenius} the sum simplifies considerably.  The relevant character values are provided in \cite{CS}.  It is technically but not conceptually challenging to use this to produce a formula for the generating function of all factorizations of the Coxeter element.  One then subtracts the generating function for non-transitive factorizations.  

As in the case of the $(n - 1)$-cycle in the symmetric group, the non-transitive factorizations are exactly those in which the underlying permutations of the factors all fix the element $1$, and so (ignoring the fixed point) these factorizations correspond to factorizations of a Coxeter element in $G(d, 1, n - 1)$.  However, there is a wrinkle: in the symmetric group, this correspondence increases the number of cycles (fixed space dimension) of each factor by exactly $1$ (the new fixed point); in $G(d, d, n)$, whether the extra cycle increases the fixed space dimension or not depends on whether it has weight $0$ ({\it i.e.}, whether the $(1, 1)$ entry of the matrix is $1$ or some other root of unity).  This requires a second set of technical gymnastics to handle.
In the end, there is massive unexpected cancellation between the non-transitive factors and the messier terms of the sum for all factorizations, leaving the claimed formula.
\end{proof}

The case of $k = 2$ factors follows immediately  as a corollary.

\begin{proof}[Proof of \cref{thm:mainG(ddn)}]
Take $k = 2$ in \cref{thm:mainG(ddn) k factors} and use the fact that $M^{n}_{p,q} = \binom{n}{p,q,n-p-q}$.
\end{proof}



% \begin{proof}[Combinatorial proof]
% Note that from \eqref{eq: equivalent expressions G(d,d,n) basis}
% \[
% \frac{\poly{r}{d}{xd+1}}{d^{r-1} r!} = \binom{x+1}{r} + (d-1)\binom{x}{r} =  d\binom{x}{r} + \binom{x}{r-1}.
% \]
% Then
% \[
% \sum_{r,s \geq 0} b_{r,s} (xd+1)^r (yd+1)^s \,=\, \sum_{r,s}  c_{r,s}
% \left(d^2\binom{x}{r}\binom{y}{s} + d\binom{x}{r} \binom{y}{s-1}
%   + d\binom{x}{r-1}\binom{y}{s} + \binom{x}{r-1}\binom{y}{s-1} \right).
% \]
% It suffices to show that 
% \[
% \sum_{r,s \geq 0} b_{r,s} (xd+1)^r (yd+1)^s = d^{n-1} \sum_{r,s}  c'_{r,s} \binom{x}{r}\binom{y}{s},
% \]
% where
% \[
% c'_{r,s} = d^2 \cdot c_{r,s} + d\cdot c_{r,s+1} + d\cdot c_{r+1,s} + c_{r+1,s+1}.
% \]
% where $c_{r,s}$ is the coefficient of the  \eqref{n - 1 cycle transitive factorizations}.
% \end{proof}


% \begin{theorem} \label{thm:mainG(ddn) k factors}
% For $d > 1$, let $G = G(d, d, n)$ and let
% \[
% G_d(x_1,\ldots, x_k) := \sum_{r_1,\ldots,r_k
%   \geq 0} b_{r_1,\ldots,r_k} x_1^{r_1}\cdots x_k^{r_k},
% \]
% where $b_{r_1,\ldots,r_k}$ is the number of transitive factorizations of a Coxeter element $c$ in $G$ as a product of $k$
% elements of $G$ with fixed space dimensions $r_1,\ldots,r_k$, respectively. 
% Then
% \[
% G_d(x_1,\ldots,x_k) \,=\, \frac{|G|^{k-1}}{n^k}\sum_{r_1,\ldots,r_k \geq 1}
%  M^n_{r_1,\ldots,r_k} \frac{\poly{r_1}{d}{x_1}}{d^{r_1-1} (r_1-1)!} \cdots 
%  \frac{\poly{r_k}{d}{x_k}}{d^{r_k-1} (r_k-1)!},
%  \]
% where $M^n_{p_1,\ldots,p_k}$ is as defined in \eqref{definition M coeff}.
%  \end{theorem}
 

% %We begin with a lemma about factorizations in the large group $G(d,1,n)$.  Let $c$ be the standard Coxeter element in $G(d, 1, n)$, let $a_{r_1, \ldots, r_k}^{c_1, \ldots, c_k}$ be the
% %number of factorizations $c = w_1 \cdots w_k$ such
% %that $\dim \fix w_i = r_i$ and $\wt(w_i) = c_i$, and define the generating function
% %\[
% %F_n^{c_1, \ldots, c_k}(x_1, \ldots, x_k) := \sum_{r_1, \ldots, r_k} a_{r_1, \ldots, r_k}^{c_1, \ldots, c_k} x_1^{r_1} \cdots x_k^{r_k} 
% %\]
% %for these numbers.  Let 
% %\[
% %{\bf F}_n := \sum_{\substack{c_1, \ldots c_k \\ c_1 + \ldots + c_k = 1}} x_1^{\delta_{0, c_1}} \cdots  x_k^{\delta_{0, c_k}} F_n^{c_1, \ldots, c_k}(x_1, \ldots, x_k).
% %\]
% %be a weighted sum of the $F_n^{c_1, \ldots, c_k}$.

% %\begin{lemma} \label{lemma:non transitive k factors}
% %We have
% %\begin{equation} \label{eq: non transitive k factors}
% %{\bf F}_n = \frac{1}{|G(d, 1, n)|}  \sum_{\substack{\chi \textrm{ irrep}\\ \textrm{for } G(d, 1, n)}} \deg(\chi) \cdot \chi(c^{-1})  \cdot \prod_{i = 1}^k \left((x_i - 1) f_\chi^0(x_i) + f_\chi(x_i)\right).
% %\end{equation}
% %\end{lemma}

% %\begin{proof}
% %Let $z_{r_i}^{(c_i)}$ be the sum in the group algebra of $G(d, 1, n)$ of all elements with fixed space dimension $r_i$ and weight $c_i$.  Then by Lemma~\ref{frobenius}, we have
% %\[
% %a_{r_1, \ldots, r_k}^{c_1, \ldots, c_k} = \frac{1}{|G(d, 1, n)|} \sum_{\chi \textrm{irrep}} \deg(\chi) \cdot \chi(c^{-1}) \cdot \normchi(z_{r_1}^{(c_1)}) \cdots \normchi(z_{r_k}^{(c_k)}).
% %\]
% %Let 
% %\[
% %f_\chi^{c}(x) = \sum_{k = 0}^n %\normchi(z_k^{(c)}) x^k.
% %\]
% %Then by rearranging the order of summation we get
% %\[
% %F_n^{c_1, \ldots, c_k}(x_1, \ldots, x_k)  = \frac{1}{|G(d, 1, n)|}
% %\sum_{\chi \textrm{ irrep}} \deg(\chi) \cdot \chi(c^{-1})  \cdot
% %f_\chi^{c_1}(x_1) \cdots f_\chi^{c_k}(x_k).
% %\]
% %Next, we compute ${\bf F}_n$.  A first observation is that we can drop the sum condition on the $c_i$ in the definition of ${\bf F}_n$, since the summands for other tuples $(c_i)$ are perfectly sensibly defined and are equal to $0$.  A second observation is that $\sum_{c} f_\chi^{c}(x) = f_\chi(x)$, and so $\sum_c x^{\delta_{0, c}} f_\chi^c(x) = (x - 1)f_\chi^0(x) + f_\chi(x)$.  Thus
% %\begin{align*}
% %{\bf F}_n & = \frac{1}{|G(d, 1, n)|}  \sum_{\chi \textrm{ irrep}} \deg(\chi) \cdot \chi(c^{-1})  \cdot \sum_{c_1, \ldots c_k} x_1^{\delta_{0, c_1}} f_\chi^{c_1}(x_1) \cdots x_k^{\delta_{0, c_k}} f_\chi^{c_k}(x_k) \\
% %& =  \frac{1}{|G(d, 1, n)|}  \sum_{\chi \textrm{ irrep}} \deg(\chi) \cdot \chi(c^{-1})  \cdot \prod_{i = 1}^k \left((x_i - 1) f_\chi^0(x_i) + f_\chi(x_i)\right),
% %\end{align*}
% %as claimed.
% %\end{proof}


% \begin{proof}[Proof of Theorem~\ref{thm:mainG(ddn) k factors}]
% Let $c$ be a Coxeter element in $G(d, d, n)$, let $a_{r_1,\ldots,r_k}$ be the number of factorizations of $c$ in $G(d, d, n)$ in which the $i$th factor has fixed space dimension $r_i$, and let $b_{r_1,\ldots,r_k}$ be defined as in the theorem statement.
% Then the difference $c_{r_1,\ldots,r_k} := a_{r_1,\ldots,r_k} - b_{r_1,\ldots,r_k}$ counts the number of \emph{non-transitive} factorizations of $c$ with prescribed dimensions of fixed spaces of the factors.
% Given such a factorization $c = u_1\cdots u_k$, we may write each factor $u_i$ in block-diagonal form as $u_i = \begin{bmatrix} z^{c_i} &  0 \\ 0 &
%   w_i\end{bmatrix}$ where $w_i$ is an element in $G(d,1,n-1)$ such
% that $w_1 \cdots w_k$ is a factorization of a Coxeter element in $G(d,1,n-1)$, and
% $c_1+\cdots+c_k=1$.  \jbl{Check conventions about what elements we want to take as standard Coxeter elements -- this choice disagrees with what we wrote is the standard Coxeter element in $G(d, d, n)$ above (the sum should be $d - 1$ in that case).  Of course it doesn't affect the results at all, but it may affect intermediate statements that depend (e.g.) on the choice of root of unity.}
% If $c_i=0$ then $\dim \fix u_i = \dim \fix w_i$, otherwise the two fixed space dimensions are the same.  It follows immediately that ${\bf F}_{n - 1}$ is the generating function for \emph{non-transitive} factorizations of $c$, and so that 
% \[
% G_d(x_1,\ldots,x_k) = F_d(x_1,\ldots,x_k) - {\bf F}_{n-1}.
% \]
% By Lemma~\ref{frobenius}, Proposition~\ref{character values on Coxeter elements case G(d,d,n)}, and the formulas for the
% degrees and character values from Proposition~\ref{character and degree values case G(d,d,n)}, we have \jbl{Should $f$ everywhere below $f^0$?}
% \begin{multline*}
% F_d(x_1, \ldots, x_k) = \frac{1}{|G|}\Bigg( \prod_{i = 1}^k f_{((n), \varnothing, \ldots)}(x_i)
%  + (-1)^n \prod_{i = 1}^k f_{((1^n), \varnothing, \ldots)}(x_i)  \\
%   + \sum_{m=1}^{n-3} \frac{(n-2-m)m}{n-1} \binom{n}{m+1} (-1)^m  \prod_{i = 1}^l f_{((n - m - 1, 2, 1^{m -1}), \varnothing, \ldots)}(x_i)  \\
%  + \sum_{j=1}^{d-1}\sum_{m=0}^{n-2} n\binom{n-2}{m}(-1)^m z^{-j} \prod_{i = 1}^k f_{(\hook{m}{n - 1}, \ldots, (1), \ldots)}(x_i) ) \Bigg).
% \end{multline*}
% In the last term of the right side, it follows from Proposition~\ref{character polynomials type G(d,d,n)} that the value of the character polynomial $f_{(\hook{m}{n - 1}, \ldots, (1), \ldots)}(x)$ does not depend on the position of the part $(1)$, and so
% \begin{multline*}
% F_d(x_1, \ldots, x_k) = \frac{1}{|G|}\Bigg( \prod_{i = 1}^k f_{((n), \varnothing, \ldots)}(x_i)
%  + (-1)^n \prod_{i = 1}^k f_{((1^n), \varnothing, \ldots)}(x_i)  \\
%   + \sum_{m=1}^{n-3} \frac{(n-2-m)m}{n-1} \binom{n}{m+1} (-1)^m  \prod_{i = 1}^l f_{((n - m - 1, 2, 1^{m -1}), \varnothing, \ldots)}(x_i)  \\
%  + \left(\sum_{j=1}^{d-1} z^{-j} \right) \cdot \sum_{m=0}^{n-2}
%   n\binom{n-2}{m}(-1)^m  \prod_{i = 1}^k f_{(\hook{m}{n - 1}, (1), \ldots)}(x_i) ) \Bigg).
% \end{multline*}
% Since $d > 1$, we have $\sum_{j=1}^{d-1} z^{-j} = -1$ and so
% \begin{multline*}
% F_d(x_1, \ldots, x_k) = \frac{1}{|G|}\Bigg( \prod_{i = 1}^k f_{((n), \varnothing, \ldots)}(x_i)
%  + (-1)^n \prod_{i = 1}^k f_{((1^n), \varnothing, \ldots)}(x_i)  \\
%   + \sum_{m=1}^{n-3} \frac{(n-2-m)m}{n-1} \binom{n}{m+1} (-1)^m  \prod_{i = 1}^l f_{((n - m - 1, 2, 1^{m -1}), \varnothing, \ldots)}(x_i)  \\
%  - \sum_{m=0}^{n-2}
%   n\binom{n-2}{m}(-1)^m  \prod_{i = 1}^k f_{(\hook{m}{n - 1}, (1), \ldots)}(x_i) ) \Bigg).
% \end{multline*}

% By Proposition~\ref{character polynomials type G(d,d,n)}, the final sum (involving the characters $(\hook{m}{n - 1}, (1), \ldots)$) is equal to
% \begin{align*}
% A & :=   \frac{n\binom{n-2}{m}(-1)^m}{|G(d,d,n)|} \prod_{i=1}^k f_{(\hook{m}{n - 1}, (1), \ldots)}(x_i) \\
% &=  \frac{n\binom{n-2}{m}(-1)^m}{|G(d,d,n)|} \prod_{i=1}^k \big( (x_i-1) g_1(x_i) +
%  (x_i(d-1) + 1) g_2(x_i) \big).
%  \end{align*}
% By Proposition~\ref{prop:f_lam_tilde} and
% Proposition~\ref{prop:f_lam}, the  $m$th term in the sum in \eqref{eq:
%   non transitive k factors} (the term with
% $\binom{n-2}{m}(-1)^m$) \jbl{what exactly does this mean?  Maybe we should write out \eqref{eq: non transitive k factors} more explicitly?  or name the characters here that we're pulling out.}  are
% \begin{align*}
% B & := \frac{1}{|G(d,1,n-1)|} \Bigl(  \prod_{i=1}^k
% \bigl[(x_i-1)(g_1(x_i)+(d-1)g_2(x_i))  + dg_1(x_i)\bigr] + \\
%   & \left(\sum_{r=1}^d z^{-r}\right) \prod_{i=1}^k
% \bigl[(x_i-1)(g_1(x_i)+(d-1)g_2(x_i))  + dg_2(x_i)\bigr]  \Bigr) \\
% & = \frac{1}{|G(d,1,n-1)|} \Bigl(  \prod_{i=1}^k
% \bigl[(x_i-1)(g_1(x_i)+(d-1)g_2(x_i))  + dg_1(x_i)\bigr] -  \\  
% & \prod_{i=1}^k
% \bigl[(x_i-1)(g_1(x_i)+(d-1)g_2(x_i))  + dg_2(x_i)\bigr]  \Bigr).  
% \end{align*}
% By simple arithmetic we have  
% \begin{align*}
% (x_i-1)(g_1(x_i)+(d-1)g_2(x_i))  +
%                           dg_2(x_i) &= (x_i-1) g_1(x_i) +
%  (x_i(d-1) + 1) g_2(x_i)\\
% (x_i-1)(g_1(x_i)+(d-1)g_2(x_i))  +
%                           dg_1(x_i) &= (d+x_i-1)g_1(x_i) + (d-1)(x_i-1)g_2(x_i).
% \end{align*}
% Then 
% \[
% A + B = \frac{n}{|G(d,d,n)|} \prod_{i=1}^k  \bigl[(d+x_i-1)g_1(x_i) + (d-1)(x_i-1)g_2(x_i)\bigr], 
% \]
% which by Proposition~\ref{character polynomials type G(d,d,n)}  is precisely the term  with $\frac{(n-2-m)m}{n-1} \binom{n}{m+1}
% (-1)^m$ in \eqref{eq:FrobG(d,d,n)}. We have shown
% \begin{multline*}
% {\bf F}_{n-1} + \frac{1}{|G(d,d,n)|} \sum_{m=0}^{n-2}
%   n\binom{n-2}{m}(-1)^m \prod_{i=1}^k f_{(\hook{m}{n - 1}, (1), \ldots)}(x_i)
%   = \\
%   \frac{1}{|G(d,d,n)|}\sum_{m=1}^{n-3}
% (-1)^mn\binom{n-2}{m} \prod_{i=1}^k f_{((n - m - 1, 2, 1^{m -
%   1}), \varnothing, \ldots)}(x_i).
% \end{multline*}
% Since 
% \[
% \frac {(n-2-m)m}{n-1} \binom{n}{m+1} - n \binom{n-2}{m} =
% \binom{n}{m+1},
% \]
% it follows that
% \begin{align*}
% F_d(x_1,\ldots,x_k) - {\bf F}_{n-1} = \frac{1}{|G|}\Bigg(
%   \prod_{i=1}^k f_{((n), \varnothing, \ldots)}(x_i)
%   + (-1)^n \prod_{i=1}^k f_{((1^n), \varnothing,
%   \ldots)}(x_i) \\
%   + \sum_{m=0}^{n-2} \binom{n}{m+1} (-1)^m \prod_{i=1}^k f_{((n - m - 1, 2, 1^{m -
%   1}), \varnothing, \ldots)}(x_i) \Bigg).
% \end{align*}
% Now we use Proposition~\ref{character polynomials type G(d,d,n)} to
% extract the coefficient of $\prod_{i=1}^k \poly{r_i}{d}{x_i}$ from this
% sum:
% \begin{multline*}
% \left[ \prod_{i=1}^k \frac{\poly{r_i}{d}{x_i}}{d^{r_i-1}r_i!}\right]
%   G_{d}(x_1,\ldots,x_k) =\\
%  |G|^{k-1}\Bigg(  \binom{n-1}{r_1-1}\cdots
%                           \binom{n-1}{r_k-1} +   \frac{r_1\cdots r_k}{n^k}
%                           \sum_{m=0}^{n-2} (-1)^{m+1}\binom{n}{m+1}
%                           \binom{n-1-m}{r_1-1-m}\cdots
%                           \binom{n-1-m}{r_k-1-m} \Bigg).
% \end{multline*}
% Note that the first term of the RHS corresponds to the term $m=-1$ in
% the sum \jbl{this is not true as written.  Also there must be something at this spot about whether $r_1 = \ldots r_k = n$, right?}. We absorb this term to the sum and reindex it using $t=m+1$
% to obtain
% \begin{align*}
% \left[ \prod_{i=1}^k \frac{\poly{r_i}{d}{x_i}}{d^{r_i-1}r_i!}\right]
%   G_{d}(x_1,\ldots,x_k) &= \frac{|G|^{k-1}r_1\cdots r_k}{n^k}  \sum_{t=0}^{n-1}
%                                         (-1)^{t}\binom{n}{t}
%                                         \binom{n-t}{r_1-t}\cdots
%                                         \binom{n-t}{r_k-t} \\
% & \,=\, \frac{|G|^{k-1}r_1\cdots r_k}{n^k} M^n_{r_1,\ldots,r_k}.
% \end{align*}
% This yields the desired result.
% \end{proof}




\section{Rank $2$ complex reflection groups}
\label{sec:rank 2}

In this section, we record some tantalizing data that suggests that \cref{G(d1n) many factors theorem,thm:mainG(ddn) k factors} could be particular cases of a more general, uniform statement, along the lines of the Chapuy--Stump result.  There are two infinite families of irreducible rank-$2$ well generated complex reflection groups, the wreath products $(\ZZ/r\ZZ) \wr \Symm_2$ (of type $G(r, 1, 2)$) and the dihedral groups (of type $G(r, 2, 2)$), as well as twelve exceptional groups (Shephard--Todd classes $G_4$, $G_5$, $G_6$, $G_8$, $G_9$, $G_{10}$, $G_{14}$, $G_{16}$, $G_{17}$, $G_{18}$, $G_{20}$, and $G_{21}$).  For any such group $G$, one may define $a_{r,s}$ to be the number of factorizations of a given Coxeter element $c$ as a product $c = u \cdot v$ where $u$ has fixed space dimension $r$ and $v$ has fixed space dimension $s$, and so also one may define the generating function 
\[
F_G(x, y) = \sum_{r, s} a_{r,s} x^r y^s.
\]
Since the matrices act on a space of dimension $2$ and the Coxeter elements have fixed space dimension $0$, every such generating function has the form
\[
F_G(x, y) = \sum_{0 \leq r, s \leq 2} a_{r,s} x^r y^s = x^2 + y^2 + a xy + \textrm{lower order terms}.
\]
Easy arguments in the two infinite families combined with exhaustive computation (performed in Sage \cite{sage}) for the exceptional groups reveal the following formula.
\begin{theorem}
Let $G$ be an irreducible well generated complex reflection group of rank $2$.  Let $e^*_1 = 1$ and $e^*_2$ be the coexponents of $G$, and let $h$ be the Coxeter number of $G$ (i.e., the multiplicative order of the Coxeter element; equivalently, the largest degree of $G$).  Then one has
\[
F_G(x, y) = (x - 1)(x - e^*_2) + k(x - 1)(y - 1) + (y - 1)(y - e^*_2) + 2h(x - 1) + 2h(y - 1) + |G|,
\]
where $k$ is the nontrivial $G$-Narayana number (i.e., the number of reflections that lie below each Coxeter element of $G$ in the absolute order).
\end{theorem}

So far, we have been unable to find a correspondingly attractive formula for the rank-$3$ complex reflection groups, where the correct choice of basis is less clear.  In particular, we have not found a natural basis in which the generating function for the group $G_{25}$ (a Shephard group, with abstract presentation $\langle a, b, c \mid a^3 = b^3 = c^3 = 1, aba = bab, bcb = cbc\rangle$) has coefficients that we understand.  This seems ripe for further investigation.


%
%
%Here is the fundamental data associated to each of the rank-$2$ groups.  
%\[
%\begin{array}{c|ccccccc}
%\textrm{gp} & d 	& e 		& d^*  	& e^* 	& h 	& |R| & |A| \\ \hline
%I_2(r)& 2, r 	& 1, r - 1	& 0, r - 2	& 1, r - 1	& r 	& & \\
%G(r,1,2)& 2, 2r	& 1, 2r - 1	& 0, r 	& 1, r + 1	& 2r	& & \\
%4 	&  4, 6	& 3, 5	& 0, 2	& 1, 3	& 6	& & \\
%5 	&  6, 12	& 5, 11	& 0, 6	& 1, 7	& 12	& & \\
%6 	&  4, 12	& 3, 11	& 0, 8	& 1, 9	& 12	& & \\
%8 	&  8, 12	& 7, 11	& 0, 4	& 1, 5	& 12	& & \\
%9 	&  8, 24	& 7, 23	& 0, 16	& 1, 17	& 24	& & \\
%10 	&  12, 24	& 11, 23	& 0, 12	& 1, 13	& 24	& & \\
%14 	& 6, 24	& 5, 23	& 0, 18	& 1, 19	& 24	& & \\
%16 	& 20, 30	& 19, 29	& 0, 10	& 1, 11	& 30	& & \\
%17 	& 20, 60	& 19, 59	& 0, 40	& 1, 41	& 60	& & \\
%18 	& 30, 60	& 29, 59	& 0, 30	& 1, 31	& 60	& & \\
%20 	& 12, 30	& 11, 29	& 0, 18	& 1, 19	& 30	& & \\
%21 	& 12, 60	& 11, 59	& 0, 48	& 1, 49	& 60	& & 
%\end{array}
%\]
%And here are their factorization polynomials:
%\[
%\begin{array}{c|cc}
%\textrm{gp} & F_G(x, y)	&  F_G(x, y) - (x - e^*_1)(x - e^*_2) - (y - e^*_1)(y - e^*_2) \\ \hline
%I_2(r) &
%x^2 + r\cdot x \cdot y + y^2 + (r - 2)  &
%r \cdot x \cdot y + r \cdot x + r \cdot y - r \\
%
%G(r,1,2)& 
%x^2 + 4 xy + y^2 + (3r - 6)(x + y) + (2r^2 - 6r + 6)& 
%4 x y + (4r - 4)(x + y) + (2r^2 - 8r + 4)\\
%
%4 &
%x^2 + 3 \cdot x \cdot y + y^2 + 5 \cdot x + 5 \cdot y + 9 &
%3 \cdot x \cdot y + 9 \cdot x + 9 \cdot y + 3 \\
%
%
%5 &
%x^2 + 4 \cdot x \cdot y + y^2 + 12 \cdot x + 12 \cdot y + 42 &
%4 \cdot x \cdot y + 20 \cdot x + 20 \cdot y + 28 \\
%
%
%6 &
%x^2 + 6 \cdot x \cdot y + y^2 + 8 \cdot x + 8 \cdot y + 24 &
%6 \cdot x \cdot y + 18 \cdot x + 18 \cdot y + 6 \\
%
%
%8 &
%x^2 + 3 \cdot x \cdot y + y^2 + 15 \cdot x + 15 \cdot y + 61 &
%3 \cdot x \cdot y + 21 \cdot x + 21 \cdot y + 51 \\
%
%
%9 &
%x^2 + 6 \cdot x \cdot y + y^2 + 24 \cdot x + 24 \cdot y + 136 &
%6 \cdot x \cdot y + 42 \cdot x + 42 \cdot y + 102 \\
%
%
%10 &
%x^2 + 4 \cdot x \cdot y + y^2 + 30 \cdot x + 30 \cdot y + 222 &
%4 \cdot x \cdot y + 44 \cdot x + 44 \cdot y + 196 \\
%
%
%14 &
%x^2 + 8 \cdot x \cdot y + y^2 + 20 \cdot x + 20 \cdot y + 94 &
%8 \cdot x \cdot y + 40 \cdot x + 40 \cdot y + 56 \\
%
%
%16 &
%x^2 + 3 \cdot x \cdot y + y^2 + 45 \cdot x + 45 \cdot y + 505 &
%3 \cdot x \cdot y + 57 \cdot x + 57 \cdot y + 483 \\
%
%
%17 &
%x^2 + 6 \cdot x \cdot y + y^2 + 72 \cdot x + 72 \cdot y + 1048 &
%6 \cdot x \cdot y + 114 \cdot x + 114 \cdot y + 966 \\
%
%
%18 &
%x^2 + 4 \cdot x \cdot y + y^2 + 84 \cdot x + 84 \cdot y + 1626 &
%4 \cdot x \cdot y + 116 \cdot x + 116 \cdot y + 1564 \\
%
%
%20 &
%x^2 + 5 \cdot x \cdot y + y^2 + 35 \cdot x + 35 \cdot y + 283 &
%5 \cdot x \cdot y + 55 \cdot x + 55 \cdot y + 245 \\
%
%
%21 &
%x^2 + 10 \cdot x \cdot y + y^2 + 60 \cdot x + 60 \cdot y + 588 &
%10 \cdot x \cdot y + 110 \cdot x + 110 \cdot y + 490
%\end{array}
%\]
%And let's do one more where we subtract out the $xy$ term, just guessing that it's $(x - 1)(y - 1)$.
%\[
%\begin{array}{c|c}
%\textrm{gp} & F_G(x, y) - (x - e^*_1)(x - e^*_2) - (y - e^*_1)(y - e^*_2) - k(x - 1)(y - 1)\\ \hline
%I_2(r) &
%2r \cdot x + 2r \cdot y - 2r \\
%
%G(r,1,2)& 
%4r x + 4r y + (2r^2 - 8r)\\
%
%4 &
%12x + 12y \\
%
%
%5 &
%24x + 24y + 24 \\
%
%
%6 &
%24x + 24y \\
%
%
%8 &
%24x + 24y + 48 \\
%
%
%9 &
%48x + 48y + 96 \\
%
%
%10 &
%48x + 48y + 192 \\
%
%
%14 &
%48x + 48y + 48 \\
%
%
%16 &
%60x + 60y + 480 \\
%
%
%17 &
%120x + 120y + 960 \\
%
%
%18 &
%120x + 120y + 1560 \\
%
%
%20 &
%60x + 60y + 240 \\
%
%
%21 &
%120x + 120y + 480
%\end{array}
%\]
%
%In all cases, the leading coefficient is exactly $2h$.  If we subtract off $2h(x - 1) + 2h(y - 1)$, we are left with $|G|$.  So for rank $2$ the answer is
%\[
%F_G(x, y) = (x - 1)(x - e^*_2) + k(x - 1)(y - 1) + (y - 1)(y - e^*_2) + 2h(x - 1) + 2h(y - 1) + |G|
%\]
%where $k$ is the $G$-Narayana number (the number of reflections below a Coxeter element in the $G$-noncrossing partition lattice).
%
%


\section{Rederiving Chapuy--Stump formulas for $G(d,1,n)$ and $G(d,d,n)$}
\label{sec:CS}
  
One can rederive the Chapuy--Stump formula (\cref{thm:cs}) for the groups $G(d, 1, n)$ and $G(d, d, n)$ from \cref{G(d1n) many factors theorem,thm:mainG(ddn) k factors}, respectively. In $G(d, d, n)$, we make use of the fact that every \emph{reflection} factorization of a Coxeter element is transitive in our sense. In both cases, this amounts to extracting the coefficient $x_1^{n - 1} \cdots x_{\ell}^{n - 1}$ from the generating function for all factorizations.  This involves contributions only from terms where the coefficient is $M^n_{n, \ldots, n, n - 1, \ldots, n - 1} = k! \cdot S(n, k)$ where $S(n, k)$ is a Stirling number of the second kind.  In the case of $G(d, 1, n)$, this gives an elementary proof of the Chapuy--Stump formula; it would be nice also to have an elementary proof (without characters) for $G(d, d, n)$.
  
\bigskip

\acknowledgements{We thank Gilles Schaeffer for suggesting we look at transitive factorizations for the case of the $(n-1)$-cycle and $G(d,d,n)$. We also thank Olivier Bernardi, John Irving, Vic Reiner, and the anonymous referees for helpful comments.}

\printbibliography
%\bibliography{CRG}

%\bibliographystyle{alpha}

\end{document}

\begin{itemize}
\item Populate bibliography (Alejandro)
\item Clean proof of main theorem in Section 3 
\item Summarize algebraic derivation for $G(d,d,n)$ (Alejandro+Joel) \jbl{Some version of this is done.}
\item outline the character approach, including references to CS and whoever they cite for known characters (Frobenius lemma stated in Section 4) \jbl{Maybe we have this under control?}
\item describe the proof strategy, we have a nice account of this in \cite[\S 2.2]{LM}
\item introduce transitivity in $G(d,d,n)$ (Joel) \jbl{done in part}
\item shorten proofs of the $n - 1$-cycle result (Alejandro) \ahm{shortened both, we could shorten the $k$-factor one to two sentences since the $G(d,d,n)$ follows the same approach with more technicalities.}
\item Write map questions last section (Alejandro) \ahm{no room, removed it}
\item assert that we can also count non-transitive factorizations, but don't actually state result (Joel one sentence) \jbl{Ok this turns out to be part of the proof sort of (?).}
\item Optional: derive power of $d$ in $G(d,1,n)$ using
  maps. (Alejandro)
\end{itemize}

\end{document}



\subsection{Connection with maps} \label{subsec: maps}

The main bijective results on factorizations of permutations are given in the language of maps, certain graphs embedded on surfaces, e.g. \cite{LZ,GS}. In \cite{B} Bernardi gave a "master bijection" using maps to prove the two factor case of Jackson's formula (\cref{S_n theorem}). This bijection was then used as the first step of an intricate combinatorial proof of the $k$ factor case of Jackson's formula (\cref{S_n theorem k factors}). 
In this section we explain how factorizations in $G(d,1,n)$ can be viewed as maps with extra decorations. For simplicity, we do the case of two factors. It would be then possible to recast the combinatorial proof of \cref{G(d1n) many factors theorem} in terms of maps. 

A (bipartite) {\em map} is a cellular (faces are simply connected) embedding of a connected (bipartite) graph on an orientable surface. 

A classical encoding (e.g. \cite{LZ}) shows that pairs of permutations $(\pi_1,\pi_2)$ in $\mathfrak{S}_n$ such that $\pi_1 \cdot \pi_2 = c$ are in bijection with edge labelled unicellular bipartite maps $G$ where the cycles of $\pi_1$ ($\pi_2$) correspond to the counter-clockwise order of the edge labels around black (white) vertices (see \cref{ex:maps}).   





We use the convention for multiplication
\[
((s_1,\ldots,s_n),\sigma) \cdot ((t_1,\ldots,t_n), \tau) =
((s_1t_{\sigma_1},\ldots,s_nt_{\sigma_n}), \tau \sigma)
\]


\begin{example} \label{ex:maps}
Let $u=((2,2,1,0,1),(2,3,5,4,1))$ and $\alpha=((2,2,1,0,2),(4,5,1,3,2))$ be the following elements in $G(3,1,5)$
\[
u = \begin{bmatrix}
 & z^2  &  &  & \\
 &  & z^2 &  &\\
& & & & z\\
& & & 1 & \\
z & & & & 
\end{bmatrix}, \quad 
v = \begin{bmatrix}
 & &  &z^2 & \\
& &  && z^2 \\
z &  & & & \\
& & 1  & & \\
& z^2 & & & 
\end{bmatrix}, \quad u\cdot v = \begin{bmatrix}
 &  &  & & z\\
1&  & &  & \\
& 1 &  & & \\
&  & 1 &  & \\
& & &  1&  
\end{bmatrix}
\] 
We have the following conventions
\begin{itemize}
\item The map has $n$ edges labelled $1,2,\ldots,n$,
\item The cycles of $v$ describe the order of the edges incident to a
  white vertex in counter-clockwise order, the weight of the edges
  from $v$ are by rows
\item The cycles of $u$ describe the order of the edges incident to a
  black vertex in counter-clockwise order, the weight of the edges
  from $v$ are by column.
\end{itemize}

The fact that $u\cdot v = c$ means that if we start at a white vertex
and traverse the map recording the labels on the right hand side of
the edges (when we go from white to black vertex) then we see the edges given by the long cycle of $c$ in
order (so $1,n,n-1,\ldots,1$). As we traverse the graph, if we add the
two weights of an edge (from black to white vertex) we obtain the corresponding weight of $c$ by row.


\begin{center}
\includegraphics[scale=0.9]{cmap_torus}
\end{center}



\end{example}




\ahm{For the case $k=2$ we can think of the objects as a bipartite
plane  rooted  tree with $(p+1,q)$, $(p,q+1)$, $(p+1,q+1)$ vertices with extra
 bipartite  edges glued to get to $n$ edges, with at most one vertex
 of each type labelled $0$, and in total at least one such
 vertex. Somehow there are $d^{n-p-q}$ ways of labelling the half
 edges.}



















\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{A section}

\lipsum[3]

\begin{equation}\label{eqn:eq1}
\int_0^\infty \exp(-x)dx = 1.
\end{equation}

\begin{lem}\label{lem:lem1}
\lipsum[11]
\end{lem}

\lipsum[10]

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{plot}
\caption{A plot of a function.}
\label{fig:plot}
\end{figure}

\subsection{A subsection}

\lipsum[5]

\begin{align*}
1 + 1 + 1 &= 2 + 1 \\ &= 3.
\end{align*}

\subsubsection{A subsubsection}

\lipsum[17]

Here is a citation~\cite{greenwade93} with URL. Here is another
citation~\cite{MR4}, which is the earliest-numbered Math Review with a
functioning DOI: MR0000004. Finally, a reference to
equation~\eqref{eqn:eq1}. And a reference to \cref{fig:plot}.

\acknowledgements{\lipsum[20]}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
