\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{diagbox,circledsteps}

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

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

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

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

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

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

\begin{document}

\begin{center}
\includegraphics[width=4in]{logo129.eps}
\end{center}

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

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

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


\begin{center}
\vskip 1cm{\LARGE\bf On Reduced Unicellular Hypermonopoles
}
\vskip 1cm
\large
Robert Cori\\
Labri, Universit\'e Bordeaux 1\\
33405 Talence Cedex\\
France\\
\href{mailto:cori@labri.fr}{\tt cori@labri.fr} \\
\ \\
G\'abor Hetyei\\
Department of Mathematics and Statistics\\
UNC Charlotte\\
Charlotte NC 28223-0001\\
USA\\
\href{mailto:ghetyei@charlotte.edu}{\tt ghetyei@charlotte.edu} \\
\end{center}

\vskip .2 in

\begin{abstract}
The problem of counting unicellular hypermonopoles by the number of their
hyperedges is equivalent to
describing the cycle length distribution of a product of two cyclic
permutations, first solved by Zagier. The solution of this problem has
also been used in the study of the cycle graph model of Bafna and
Pevzner, and of related models in mathematical biology. In this paper we
develop a method to compute the finite number of reduced unicellular
hypermonopoles of a given genus. The problem of 
representing any hypermap as a drawing is known to be simplifiable to
solving the same problem for reduced unicellular hypermonopoles. We also
outline a correspondence between our hypermap model, the cycle graph model of
Bafna and Pevzner, and the polygon gluing model of Alexeev and
Zograf. Reduced unicellular hypermonopoles correspond to reduced
objects in the other models as well, and the notion of genus is the
same.  
\end{abstract}


\section{Introduction}

In the study of the combinatorics of the  symmetric group many authors
have been interested in the statistics of cycle lengths of products
of pairs of permutations. In this note we revisit the particular case of
counting the cycles of the product of two cyclic permutations, or
dually finding the number of decompositions of a given permutation as a
product of two cyclic permutations.   
  
Our renewed interest in this topic comes from the study of {\em hypermaps}.
In a recent paper~\cite{Cori-Hetyei-hypertrees} we showed that the
problem of drawing a hypermap may be reduced to considering the same
problem for a {\em unicellular hypermonopole} of the same genus. A hypermap
$H=(\sigma,\alpha)$ is a pair of permutations generating a transitive
permutation group. A hypermonopole  is a hypermap with a single
vertex; that is, $\sigma$ is a cyclic permutation. It is called {\em
  unicellular} if it has only one face, meaning  that $\alpha^{-1}
\sigma$  is  also a  cyclic permutation.   
The main result of this short paper concerns the enumeration of
unicellular hypermonopoles without {\em buds}, meaning  that $\alpha$ has no
fixed point,  we call such a unicellular hypermonopole {\em reduced}. 

Our  main tool is the enumeration formula obtained by
Zagier~\cite{Zagier} for the number of unicellular  hypermonopoles
having a given number of cycles. Notice that the number of cycles $k$
and the genus $g$ of a unicellular hypermonopole  of $S_n$ satisfy $k=
n-2g$. A combinatorial bijective proof of Zagier's formula was given
by Cori, Marcus, and Schaeffer~\cite{Cori-Marcus-Schaeffer}.
In  the field of genome rearrangements,  Bafna and
Pevzner~\cite{Bafna-Pevzner} introduced a cycle graph model that is
essentially equivalent to studying the product of a pair of cyclic 
permutations. Their aim  was  to determine the minimum number of
``transpositions''\footnote{The transpositions in biology are
different from those considered in algebra; they displace an interval of
the word representing the permutation.} needed to reduce a permutation
(considered as a word) to the identity permutation. This allows to
model the evolution of the DNA of some  viruses.
These questions have motivated several researchers to focus on the
products of cyclic permutations. This is the case of the work of
A.\ Hultman in his thesis~\cite{Hultman}, and more recently  that of
Alexeev and Zograf~\cite{Alexeev-Zograf} who introduced gluings  of
polygons to represent these products.  

Our paper is organized as follows. In the Preliminaries
we recall the notions of the theory of hypermaps and state Zagier's
formula and some of its reformulations. Section~\ref{sec:basic} is devoted to
the description of the relationship between Zagier's factorization problem, 
counting unicellular hypermonopoles, and the models of Bafna and
Pevzner~\cite{Bafna-Pevzner} and of Alexeev and
Zograf~\cite{Alexeev-Zograf}. In Section~\ref{sec:counting} we give
our main result expressing the number of reduced unicellular
hypermonopoles on $n$ points with a given number of hyperedges. We
already observed in~\cite{Cori-Hetyei-hypertrees} that the number of all
reduced unicellular hypermonopoles of a given genus is finite. Our main
result allows to count these finite numbers explicitly, and
we give the first values of these numbers.

It is worth noting that reduced unicellular hypermonopoles correspond to
cycle graphs having breakpoints everywhere in the model of Bafna and
Pevzner~\cite{Bafna-Pevzner}. Furthermore, the genus of the corresponding
polygon gluing diagram in the work of  Alexeev and
Zograf~\cite{Alexeev-Zograf} is the same as the genus of the
corresponding unicellular hypermonopole. The three models are intimately
related, hence the counting problem we solved has also some significance
in the related models in mathematical biology. 


 
\section{Preliminaries}
\label{sec:prelim}

\subsection{Hypermaps and their two disk diagrams}

A {\em hypermap} $(\sigma,\alpha)$ is a pair of permutations of a set
$\{1,2,\ldots,n\}$ generating a transitive permutation group. It is used
to represent a (connected) hypergraph on an oriented
surface.
\begin{figure}[ht]
\centering
\input{hypermap.pdf_t}    
\caption{Three hypermaps drawn on the torus.}
\label{fig:hypermaps} 
\end{figure}
The cycles of $\sigma$ are the vertices, the cycles of
$\alpha$ are the hyperedges, and the cycles of
$\alpha^{-1}\sigma$ are the faces. The {\em points} 
$1,2,\ldots, n$ are the points of incidence between the vertices and
the hyperedges. 
Three hypermaps drawn on the torus are shown in
Figure~\ref{fig:hypermaps}. 
The leftmost drawing represents the hypermap $(\sigma,\alpha)$ with
$\sigma=(1,4,5)(2,6,3)$ and $\alpha=(1,2,3,4)(5,6)$. The description of
the other two drawings will follow below. To obtain three
tori, the parallel sides of the rectangles shown in bold should be identified. 
In our drawings, points follow in counterclockwise order along the
vertices and in the clockwise order along the hyperedges. The {\em
  genus $g(\sigma,\alpha)$} of the oriented surface on which a hypermap may
be drawn with noncrossing lines is given by the following formula due to Jacques~\cite{Jacques}: 
\begin{equation} 
\label{eq:genusdef}
n + 2 -2g(\sigma,\alpha) = z(\sigma) + z(\alpha) + z(\alpha^{-1}
\sigma),
\end{equation}
where $z(\pi)$ denotes the number of cycles of the permutation $\pi$.
A detailed introduction to the theory of hypermaps may be found in the
survey papers of Cori and Mach\`\i \cite{Cori-Machi}.

This paper is motivated by the following observation 
in~\cite{Cori-Hetyei-hypertrees}: using a sequence of {\em topological
  hyperdeletions $(\sigma,\alpha)\mapsto (\sigma,\alpha\delta)$}  and of
{\em topological hypercontractions $(\sigma,\alpha)\mapsto
  (\gamma\sigma,\gamma\alpha)$}, each hypermap may be reduced to a
  hypermap $(\sigma',\alpha')$ of the same genus, such that
  $z(\sigma')=1$; that is, $(\sigma',\alpha')$ is a {\em hypermonopole},
  and $z(\alpha'^{-1}\sigma')=1$; that is, $(\sigma',\alpha')$ is {\em
    unicellular}. By definition $(\sigma,\alpha)\mapsto
  (\sigma,\alpha\delta)$ is a topological hyperdeletion when 
  $\delta=(i,j)$ is a transposition such that $i$ and $j$ belong to the
  same cycle of $\alpha$ but to different cycles of $\alpha^{-1}\sigma$. 
Similarly  $(\sigma,\alpha)\mapsto
  (\gamma\sigma,\gamma\alpha)$ is a topological hypercontraction when 
  $\gamma=(i,j)$ is a transposition such that $i$ and $j$ belong to the
  same cycle of $\alpha$ and to different cycles of $\sigma$.
We refer the interested reader for the detailed
  description of the process to~\cite{Cori-Hetyei-hypertrees}. Here we
  illustrate it in Figure~\ref{fig:hypermaps}. First we apply
  the topological hypercontraction $(\sigma,\alpha)\mapsto
  (\gamma\sigma,\gamma\alpha)$ with $\gamma=(5,6)$ thus obtaining the
  hypermap $(\gamma\sigma,\gamma\alpha)$ with
  $\gamma\sigma=(1,4,6,3,2,5)$ and $\gamma\alpha=(1,2,3,4)(5)(6)$, drawn
  in the center of Figure~\ref{fig:hypermaps}. Finally we apply the
  topological hyperdeletion $(\gamma\sigma,\gamma\alpha)\mapsto
  (\gamma\sigma,\gamma\alpha\delta)$ with $\delta=(2,3)$ and we obtain
  the unicellular hypermonopole $(\sigma',\alpha')$ with
  $\sigma'=\gamma\sigma=(1,4,6,3,2,5)$ and
  $\alpha'=\gamma\alpha\delta=(1,2,4)(3)(5)(6)$, shown on the right hand
  side of Figure~\ref{fig:hypermaps}. 


  A process of reducing the original hypermap $(\sigma,\alpha)$
  to a unicellular hypermonopole $(\sigma',\alpha')$ via hyperdeletions
  and hypercontractions may be found without drawings: as long as there
  is more than one face, we can always find a hyperdeletion reducing the
  number of faces; and as long as there is more than one vertex, we can
  always reduce the number of vertices using a hypercontraction. If
  $(\sigma,\alpha)$ is drawn on an oriented surface, hyperdeletions and
  hypercontractions may be visualized as in
  Figure~\ref{fig:hypermaps}. Conversely, if we are able to draw the unicellular
  hypermonopole $(\sigma',\alpha')$ by some means on an oriented 
  surface then we may easily extend this drawing to a drawing of
  $(\sigma,\alpha)$ as follows.    
\begin{figure}[ht]
\centering
\input{2disk.pdf_t}    
\caption{A $2$-disk diagram of $(\sigma,\alpha)$.}
\label{fig:2disk} 
\end{figure}
Consider the representation of
  $(\sigma',\alpha')$ on the torus shown in Figure~\ref{fig:2disk}. The
dashed circle in the center represents
$$\sigma'=(1,4,6,3,2,5),$$
and the
  dashed square whose sides are in the corners represents
  $$\alpha'^{-1}(\sigma')=(1,2,5,4,6,3).$$
  We may complete the drawing of
  $(\sigma',\alpha')$ by  replacing the only cycle $\sigma'$ with a
  noncrossing partition having $z(\sigma)$ parts and the face
  $\alpha'^{-1}(\sigma')$ with a noncrossing partition having
  $z(\alpha^{-1}\sigma)$ parts.   
Noncrossing  partitions, introduced by Kreweras~\cite{Kreweras}, are
partitions of the set $\{1,2,\ldots,n\}$ such that the polygons representing the
  parts do not cross if we place the points in the cyclic order of
  $(1,2,\ldots,n)$ on a circle. The cycles of $\sigma$ and $\alpha^{-1}(\sigma)$
  are shown as shaded polygons in Figure~\ref{fig:2disk}, together with
  the line segments connecting the corresponding points of $\sigma'$ and
  $\alpha'^{-1}(\sigma')$ they divide the rest of the torus into two
  parts, which naturally correspond to the cycles of $\alpha$. The
  resulting representation is called a {\em two-disk representation of
    $(\sigma,\alpha)$} in~\cite{Cori-Hetyei-hypertrees}. Hence the
  problem of drawing an arbitrary hypermap on some oriented surface is reduced
  to the same question for unicellular hypermonopoles only.  

There are infinitely many unicellular hypermonopoles of a fixed genus:
trivially, for each $n$ the hypermap $(\sigma,\alpha)$ with
$\sigma=(1,2,\ldots,n)$ and $\alpha=(1)(2)\cdots (n)$ is a unicellular
hypermonopole of genus zero. Fortunately, in the case of unicellular
hypermonopoles it is easy to remove or
reinsert {\em buds}: a bud is a fixed point $i$ of $\alpha$. For $n\geq
2$, the removal of $i$ from the cycles representing $\sigma$ and
$\alpha$ results in a hypermap $(\sigma',\alpha')$ on the set of points
$\{1,2,\ldots,n\}- \{i\}$, which is still a
hypermonopole (as $z(\sigma')=z(\sigma)=1$), and it is also still
unicellular: the action of $\alpha'^{-1}\sigma'$ on a
$j\not\in\{i,\sigma^{-1}(i)\}$ is the same as that of
$\alpha^{-1}\sigma$, whereas 
$\alpha'^{-1}\sigma'$ takes $\sigma^{-1}(i)$ into    
$\alpha'^{-1}(\sigma(i))$. (Note that neither $\sigma^{-1}(i)$ nor
$\sigma(i)$ is equal to $i$, as $\sigma$ is cyclic and has at least
$2$ points.) Hence the cycle representing $\alpha'^{-1}\sigma'$ is
obtained from the cycle representing $\alpha^{-1}\sigma$ by simply
removing the point $i$ from the cyclic list. It is also worth
noting that the numbering of the set of points $\{1,2,\ldots,n\}- \{i\}$
may be made consecutive by decreasing each $j>i$ in the point set by
$1$. Clearly if we are able to
draw $(\sigma',\alpha')$ on an oriented surface with noncrossing lines, adding a
bud to the figure amounts to adding a single point. 
\begin{definition}
We call a unicellular hypermonopole {\em reduced} if it contains no bud.
\end{definition}  
It has been first observed in~\cite{Cori-Hetyei-hypertrees} that there
are only finitely many reduced unicellular hypermonopoles of a fixed
genus.
\begin{lemma}
\label{lem:genusbound}
If $(\sigma,\alpha)$ is a genus $g$ reduced unicellular hypermonopole on $n$
points then
$$2g+1\leq n\leq 4g\quad\text{holds.} $$
\end{lemma}  
\begin{proof}
Substituting $z(\sigma)=1$ and $z(\alpha^{-1}\sigma)=1$ into (\ref{eq:genusdef})
we obtain 
\begin{equation}
\label{eq:genusdefr}  
n = z(\alpha)+2g(\sigma,\alpha). 
\end{equation}
Since each cycle of $\alpha$ has at least $2$ elements, we get
$z(\alpha)\leq n/2$, yielding the upper bound for $n$. The lower bound
is a direct consequence of $z(\alpha)\geq 1$. 
\end{proof}

\begin{example}
By the end of this paper we will see that there are two reduced
unicellular hypermonopoles $(\sigma,\alpha)$ of genus $1$. Assuming that
the points are numbered in such a way that $\sigma=(1,2,\ldots,n)$
holds, it is not difficult to verify that one of them satisfies
$\sigma=(1,2,3)$ and $\alpha=(1,3,2)$, and the other one satisfies
$\sigma=(1,2,3,4)$ and $\alpha=(1,3)(2,4)$. The unicellular
hypermonopole $(\sigma',\alpha')$ shown in Figure~\ref{fig:2disk}
has three buds: $3$, $5$ and $6$. After removing these and renumbering
the points in such a way that the unique vertex becomes the cycle
$(1,2,3)$, we obtain the reduced unicellular hypermonopole
$(\sigma'',\alpha'')$ with $\sigma''=(1,2,3)$ and $\alpha''=(1,3,2)$. 
\end{example}   

  

\subsection{Products of two cyclic permutations}

A permutation is {\em cyclic} if it has exactly one cycle. In his
paper we will need the number of pairs of cyclic permutations of
$\{1,2,\ldots,n\}$ whose product has exactly $k$ cycles. The answer to
this question was first given by Zagier~\cite[application 3 of Theorem
  1]{Zagier}.
\begin{theorem}[Zagier]
The probability that the product of two cyclic permutations of the set 
$\{1,2,\ldots,n\}$ has $k$ cycles is
$$
P(n,k)=\frac{1+(-1)^{n-k}}{(n+1)!} c(n+1,k).
$$
Here $c(n+1,k)=|s(n+1,k)|$ is the number of permutations
of $\{1,2,\ldots,n+1\}$ with $k$ cycles, and $s(n+1,k)$ is a Stirling
number of the first kind.  
\end{theorem}
The first purely combinatorial proof of this result was provided by
Cori, Marcus, and Schaeffer~\cite[Corollary
  1]{Cori-Marcus-Schaeffer}. 
Note that $P(n,k)=0$ if $n-k$ is odd. This is obvious: all cyclic
permutations have the same parity, hence the product of two cyclic
permutations must be an even permutation. The parity of a
permutation is the parity of the number of its cycles of even length in
its cycle decomposition. This number cannot be even if $n-k$ is
odd. After noting that one of the two cyclic permutations may be fixed
to be $(1,2,\ldots,n)$, Zagier's result may be restated in combinatorial
terms as follows.  
\begin{theorem}
\label{thm:circperms}
The number of cyclic permutations $\psi$ of $\{1,\ldots,n\}$ such that
the product $(1,\ldots,n)\psi$ has exactly $k$ cycles is
\begin{align}
  \label{eq:Hn}
  H(n,k)&=
  \begin{cases}
    c(n+1,k)/\binom{n+1}{2}, & \text{if $n-k$ is even;}\\
    0, & \text{if $n-k$ is odd.} 
  \end{cases}  
\end{align}  
\end{theorem}
\begin{table}[h]
\centering
\begin{tabular}{l||c|c|c|c|c|c|c|c|c|c|}
\diagbox{$n$}{$k$}& $1$&$ 2$ & $ 3$ & $ 4$ & $ 5$ & $ 6$ & $ 7$ & $ 8$ & $ 9$ & $ 10 $\\
\hline
0& 1& & & & & & & & & \\
1& 0& 1& & & & & & & & \\
2& 1& 0& 1& & & & & & & \\
3& 0& 5& 0& 1& & & & & & \\
4& 8 &0 & 15 & 0 & 1& & & & & \\
5& 0 & 84 &  0 & 35 &  0 & 1  & & & & \\
6& 180& 0& 469& 0& 70& 0&  1 & & &  \\
7& 0& 3\, 044& 0& 1\, 869& 0& 126& 0& 1  & & \\
8& 8\, 064& 0& 26\, 060& 0& 5\, 985& 0& 210& 0& 1 & \\
9& 0& 193\, 248& 0& 152\, 900& 0& 16\, 401& 0& 330& 0& 1\\
\end{tabular}
\caption{The values of $H(n,k)$ for $n\leq 9$.}
\label{tab:Hnk}
\end{table}  


Table~\ref{tab:Hnk} shows the values of $H(n,k)$ for $n\leq 9$. It is
worth noting that when  
$n-k$ is even, the sign of $s(n+1,k)$ is negative, hence we may also
replace $c(n+1,k)$ with $-s(n+1,k)$ in~(\ref{eq:Hn}) above. 
The numbers $H(n,k)$ were later rediscovered by
A.\ Hultman in his MS Thesis~\cite{Hultman} who
defined them in terms of counting alternating cycles in the cycle graph
of a permutation. The numbers $H(n+1,k)$ were named {\em Hultman
  numbers} in the work of Doignon and Labarre~\cite{Doignon-Labarre},
and they are listed as \seqnum{A164652} in the
On-Line Encyclopedia of Integer Sequences~\cite{OEIS}.   
The equivalence of the two definitions is made
apparent in~\cite[Corollary 1]{Bona-Flynn}, which is based on a result
of Doignon and Labarre~\cite{Doignon-Labarre}.  Citing
Stanley~\cite{Stanley-EC2}, B\'ona and
Flynn~\cite[p.\ 931]{Bona-Flynn} also published (\ref{eq:Hn}) for these
numbers. A simple proof of~(\ref{eq:Hn}) (relying on Hultman's
definition) was also  found by Grusea and Labarre~\cite[Section
  7]{Grusea-Labarre}.  We will use the following lemma of Grusea and
Labarre~\cite[Lemma 8.1]{Grusea-Labarre}. 
\begin{lemma}[Grusea-Labarre]
\label{lem:GL}
The numbers $H(n,k)$ satisfy
$$  
\sum_{k=0}^n H(n,k) x^k=\frac{(x)^{(n+1)}-(x)_{n+1}}{(n+1)n}.
$$
Here $(x)^{(n+1)}=x\cdot(x+1)\cdots (x+n)$ and
$(x)_{n+1}=x\cdot(x-1)\cdots (x-n)$ are falling, respectively rising
factorials (Pochhammer symbols). 
\end{lemma}  




 
\section{Basic facts about unicellular hypermonopoles}
\label{sec:basic}

As a direct consequence of the definitions we may observe the following.

\begin{remark}
\label{rem:2cycles}
For a unicellular hypermonopole $(\sigma,\alpha)$ the permutations $\sigma$
and $\pi=\alpha^{-1}\sigma$, representing the unique vertex,
respectively, the unique face of the hypermap, are cyclic
permutations. Conversely, given a pair $(\sigma,\pi)$ of cyclic
permutations of the same set, there is a unique unicellular
hypermonopole $(\sigma,\alpha)$ satisfying $\pi=\alpha^{-1}\sigma$.   
\end{remark}
Indeed, the unique $\alpha$ satisfying $\pi=\alpha^{-1}\sigma$ is
\begin{align}
\label{eq:hf}
\alpha&=\sigma\pi^{-1}.
\end{align}  
Regardless of $\alpha$, the pair $(\sigma,\alpha)$ is always a hypermap
because $\sigma$ is a cyclic permutation, and any permutation group
containing a cyclic permutation is transitive. Theorem~\ref{thm:circperms} and
Remark~\ref{rem:2cycles} have the following consequence. 
\begin{corollary}
\label{cor:Hn}
The number of unicellular hypermonopoles $(\sigma,\alpha)$ satisfying
$\sigma=(1,\ldots,n)$ and $z(\alpha)=k$ is the number
$H(n,k)$ given in~(\ref{eq:Hn}). 
\end{corollary}  

In the rest of this section we show that unicellular hypermonopoles are
bijectively equivalent to two other combinatorial models for the
Hultman numbers $H(n+1,k)$. 

The first model we consider is the {\em cycle graph model} introduced by
Bafna and Pevzner~\cite{Bafna-Pevzner}. We present it using the same
simplification that was introduced by Doignon and Labarre
in~\cite{Doignon-Labarre} where the vertex $n+1$ is identified with $0$,
and we adjust that model even further, by replacing each permutation
$$
\left(
\begin{array}{cccc}
0 & 1& \cdots & n\\ 
0 & \pi_1 & \cdots & \pi_n
\end{array}  
\right)
$$
of $\{0,1,\ldots,n\}$, taking $0$ into $0$,   
with the cyclic permutation $\pi=(0,\pi_1,\ldots,\pi_n)$. This
correspondence is a bijection between all permutations of
$\{0,1,\ldots,n\}$ that have $0$ as a fixed point and all cyclic
permutations of $\{0,1,\ldots,n\}$. Let us fix the cyclic
permutation $\sigma=(0,1,\ldots,n)$, and let $\pi$ be any cyclic permutation of
the set $\{0,1,\ldots,n\}$. The {\em cycle graph} $G(\pi)$ of the cyclic
permutation $\pi$ is a digraph on the vertex set $\{0,1,\ldots,n\}$
whose edges are colored with two colors: 
\begin{enumerate}
\item the black edges go from $i$ to $\pi^{-1}(i)$ (mod $n+1$) for
  $0\leq i\leq n$;
\item the gray edges go from $i$ to $\sigma(i)$; in other words they go
  from $i$ to $i+1$ (mod $n+1$) for $0\leq i\leq n$.    
\end{enumerate}
Note that in the work of Doignon and Labarre~\cite{Doignon-Labarre} the black
edges go from $\pi_i$ to $\pi_{i-1}$ for $1\leq i\leq n$ and from $\pi_0$
to $\pi_n$. Our rule~(1) is the same if we read the array
$(0,\pi_1,\cdots,\pi_n)$ as the code for a cyclic permutation.


Each vertex is the head, respectively the tail of one edge of each color,
hence the cycle graph may be uniquely decomposed into disjoint
color-alternating cycles. Note that even though edges do not repeat in
such cycles, vertices may occur twice. To remedy this slight confusion,
we introduce two copies of each vertex $i$: a negative copy $i^-$ and a
positive copy $i^+$. Each negative vertex $i^-$ will be
the head of a black edge whose tail is $\pi(i)^+$, and it will be the
tail of a gray edge whose head is $(i+1)^+$. Equivalently,
each positive vertex $i^+$ will be  the head of a gray edge whose tail
is $(i-1)^-$, and it will be the tail of a black edge whose head is
$\pi^{-1}(i)^+$. Instead of using colors we will label the black edges
with $\pi^{-1}$ and the gray edges with $\sigma$. For example, for $n=7$
and $\pi=(0,4,1,6,2,5,7,3)$ (the same array, read as a permutation word,
gives rise to~\cite[Figure 1]{Doignon-Labarre}) we obtain the following
two cycles: 
$$
0^- \xrightarrow{\sigma} 1^+ \xrightarrow{\pi^{-1}} 4^-
\xrightarrow{\sigma} 5^+ \xrightarrow{\pi^{-1}} 2^- \xrightarrow{\sigma}
3^+ \xrightarrow{\pi^{-1}} 7^- \xrightarrow{\sigma} 0^+
\xrightarrow{\pi^{-1}} 3^- \xrightarrow{\sigma} 4^+
\xrightarrow{\pi^{-1}} 0^- \quad\text{and} 
$$
$$
6^-\xrightarrow{\sigma} 7^+ \xrightarrow{\pi^{-1}} 5^-
\xrightarrow{\sigma} 6^+ \xrightarrow{\pi^{-1}} 1^-
\xrightarrow{\sigma} 2^+ \xrightarrow{\pi^{-1}} 6^-
$$
Using this notation one may notice immediately that these cycles may be
uniquely reconstructed from the positive vertices only: we may identify
the first cycle with $(1,5,3,0,4)$ and the second cycle with
$(7,6,2)$. Observe next that
$$\alpha=(1,5,3,0,4)(7,6,2)=\sigma\pi^{-1};$$
that is, $\pi=\alpha^{-1}\sigma$. The cycle graph of $\pi$ may be
identified with the unicellular hypermonopole $(\sigma,\alpha)$ whose
only vertex is $\sigma$ and only face is $\pi=\alpha^{-1}\sigma$. The
number of alternating cycles in $G(\pi)$ is $z(\alpha)$, the number of
hyperedges. 
 
Bafna and Pevzner~\cite{Bafna-Pevzner} call a pair $(i,\pi(i))$ a {\em
  breakpoint} if $\pi(i)\neq \sigma(i)$. In our setting $(i,\pi(i))$ is a
breakpoint if and only if $\alpha^{-1}\sigma(i)\neq \sigma(i)$,
equivalently $\sigma(i)$ is not a bud of $(\sigma,\alpha)$. Reduced
unicellular hypermonopoles bijectively correspond to cyclic
permutations for which every pair $(i,\pi(i))$ is a breakpoint, see
Lemma~\ref{lem:breakpoint} in the next section. A ``transposition''
operation, as
defined by Bafna and Pevzner~\cite{Bafna-Pevzner} replaces the
permutation word $\pi_1\cdots\pi_n$ with the word
$\pi_1\cdots\pi_{i-1} \pi_j \pi_{j+1}\cdots\pi_{k-1}\pi_i\pi_{i+1}\cdots
\pi_{j-1}\pi_{k}\cdots\pi_n$ for some $i<j<k$. After rewriting the word
$\pi_1\cdots\pi_n$ as the cyclic permutation
$\pi=(0,\pi_1,\ldots,\pi_n)$, the same rearrangement of indices
corresponds to sending $\pi$ into
$(\pi_i,\pi_k)(\pi_{i},\pi_{j})\pi=(\pi_i,\pi_j,\pi_k)\pi$, that is,
multiplying $\pi$ with two transpositions. In our language, Bafna and
Pevzner~\cite{Bafna-Pevzner} study the question, how many such
operations are needed to transform $\pi$ into
$\sigma=(1,2\ldots,n)$. There seems no point in ``breaking'' up $\pi$
between $\pi(i)$ and $\pi(i+1)$ if $\pi(i+1)=\sigma(\pi(i))$ holds. For
example, when $n=4$ and $\pi=(0,3,1,2,4)$, the numbers $1$ and $2$ are
already cyclically consecutive, it makes sense to rearrange the entries
using only operations that keep $1$ and $2$ consecutive. In the
corresponding unicellular hypermonopole we have
$\alpha=\sigma\pi^{-1}=(0)(1,4,3)(2)$, i.e., $2$ is a bud. Note that
$0$ is also a bud, because the largest numbered point is already at the
end of our array. Removing the buds $0$ and $2$, and renumbering the
points consecutively corresponds to replacing $\sigma$ with
$\sigma'=(0,1,2)$ and $\pi$ with $\pi'=(1,0,2)$. We arrived at a
reduced unicellular hypermonopole, this always happens after removing
all buds. To summarize, if we accept as a rule that we only use the
interval ``transposition'' operations of Bafna and
Pevzner~\cite{Bafna-Pevzner} to break the words at their breakpoints
then (after removing the buds in the associated unicellular
hypermonopoles) the process is essentially running on a cyclic
permutation encoding the unique face of a reduced unicellular
hypermonopole.   
\begin{remark}
The careful reader may notice that the smallest numbered point $0$ is
not listed at the beginning of the cyclic permutation $\pi'$
above. Furthermore, 
Bafna and Pevzner only defined transpositions of intervals in
permutations written as words, not in cyclic permutations. That said,
allowing their 
operations to be performed on cyclically consecutive blocks of a 
cyclic permutation does not lead to the introduction of new operations
because of the following observation. Consider an array
$$\underline{u}=(a_1,\ldots,a_{i}, b_1,\ldots, b_j, c_1,\ldots, c_k, d_1,\ldots,
d_\ell, a'_1,\ldots, a'_m)$$
where all coordinates are pairwise different numbers. On the one hand,
we may think of the above  array as a code of a cyclic permutation,
which can be decomposed into four intervals of cyclically consecutive
entries: $(a'_1,\ldots, a'_m, a_1,\ldots,a_{i})$, $(b_1,\ldots, b_j)$,
$(c_1,\ldots, c_k)$ and $(d_1,\ldots,d_\ell)$. A move not explicitly
considered in~\cite{Bafna-Pevzner} is to exchange the ``cyclic''
interval $(a'_1,\ldots, a'_m, a_1,\ldots,a_{i})$ with the adjacent
interval $(d_1,\ldots,d_\ell)$. This yields the cyclic
permutation encoded by the array
$$\underline{v}=(a_1,\ldots,a_{i}, d_1,\ldots,
d_\ell, b_1,\ldots, b_j, c_1,\ldots, c_k, a'_1,\ldots, a'_m).$$
On the other hand, we can also read $\underline{u}$ as an array
representing a permutation as a word that has the following four
intervals: $(a_1,\ldots,a_{i})$,
$(b_1,\ldots, b_j, c_1,\ldots, c_k)$, $(d_1,\ldots,d_\ell)$, and
$(a'_1,\ldots, a'_m)$. The array $\underline{v}$ can also be
obtained by exchanging $(b_1,\ldots, b_j, c_1,\ldots, c_k)$
and $(d_1,\ldots,d_\ell)$: this is a transposition of intervals allowed
by the definition in~\cite{Bafna-Pevzner}. The case when we exchange
the cyclic interval $(a'_1,\ldots, a'_m, a_1,\ldots,a_{i})$ with
$(b_1,\ldots, b_j)$ can be dealt with in a completely similar fashion. 
\end{remark}  


The other model is the one introduced by Alexeev and
Zograf~\cite{Alexeev-Zograf}. Consider a $2n$ sided polygon whose
boundary consists of $n$ black sides followed by $n$ gray sides
(represented by dashed lines). The black sides are oriented in the
counterclockwise direction and the gray sides are oriented in the
clockwise direction, as shown in 
Fig.~\ref{fig:gluing}.    
\begin{figure}[h]
\centering
  \input{gluing.pdf_t}
  \caption{A polygon gluing diagram for $\pi=(0,2,3,1,4)$.}
  \label{fig:gluing}
\end{figure}  
Pairwise gluing of black sides with gray sides (respecting orientation)
gives an orientable topological surface without boundary of topological
genus $g\geq 0$. The genus $g$ depends on the gluing. We cut the polygon
along the diagonal connecting the vertex $n$ and the vertex $0$, and we
add a directed edge of each color from $n$ to $0$. By assuming that
these added edges will be glued together we don't change the genus.  
We number all edges by their tail end, and we use the gluing pattern to
define the cyclic permutation $\pi=(\pi_0,\pi_1,\ldots,\pi_n)$: we
define $\pi_i$ as the gray edge that is glued with the black edge
$i$. As in the previous model, we define $\sigma$ as the cyclic
permutation $(0,1,\ldots,n)$. For the gluing pattern shown in
Fig.~\ref{fig:gluing} we obtain 
$\pi=(0,2,3,1,4)$.  As before, let us define
$\alpha=\sigma\pi^{-1}$. In our example we obtain
$\alpha=(0)(1,4,2)(3)$. According to Alexeev and
Zograf~\cite{Alexeev-Zograf} it is easy to see that the alternating
cycles of $G(\pi)$ are in bijection with the vertices of the glued
polygon. We can make it easier to see this by adding the signed labels
$i^-$ and $i^+$ along each gray edge labeled $i$ as shown in
Fig.~\ref{fig:gluing}. For example, the alternating cycle
$$
0^- \xrightarrow{\sigma} 1^+ \xrightarrow{\pi^{-1}} 3^-
\xrightarrow{\sigma} 4^+ \xrightarrow{\pi^{-1}} 1^- \xrightarrow{\sigma}
2^+ \xrightarrow{\pi^{-1}} 0^-$$
corresponds to the identification $\Circled{0}=
\fbox{2}=\Circled{3}=\fbox{3}=\Circled{1}=\Circled{0}$.
The verification of the details is left to the reader. 


\section{Counting reduced unicellular hypermonopoles}
\label{sec:counting}

In this section we express the number of reduced unicellular hypermonopoles in
terms of the number $H(n,k)$.
In doing so, the following lemma will be
useful. 
\begin{lemma}
\label{lem:breakpoint}  
A unicellular hypermonopole $(\sigma,\alpha)$ satisfying $\sigma=(1,\ldots,n)$
is reduced if and only if the cyclic permutation $\pi=\alpha^{-1}\sigma$
satisfies $\pi(i)\neq i+1$ for all $i\in\{1,\ldots,n\}$. Here addition
is performed mod $n$. 
\end{lemma}  
Indeed, $\alpha^{-1}\sigma(i)=i+1$ is equivalent to $\alpha(i+1)=i+1$. 
Let us also note the following consequence of the proof of
Lemma~\ref{lem:genusbound}. 
\begin{corollary}
\label{cor:kbound}  
If $(\sigma,\alpha)$ is a reduced unicellular hypermonopole on $n$
points then
$$1\leq z(\alpha)\leq n/2\quad\text{holds.}$$
\end{corollary}  
As a consequence, the number $r(n,k)$ of reduced unicellular
hypermonopoles $(\sigma,\alpha)$ satisfying $\sigma=(1,\ldots,n)$ and
$z(\alpha)=k$ can be only nonzero for $1\leq k\leq n/2$. 

\begin{proposition}
\label{prop:rnk}
  Given $n\geq 2$ and $1\leq k\leq n/2$, the number of
  reduced unicellular hypermonopoles 
  $(\sigma,\alpha)$ satisfying $\sigma=(1,\ldots,n)$ and $z(\alpha)=k$
  is given by
\begin{align}
\label{eq:rnk}
r(n,k)&=\sum_{i=0}^{k-1} (-1)^{i} \binom{n}{i} H(n-i,k-i). 
\end{align}  
\end{proposition}  
\begin{proof}
We compute $r(n,k)$ using inclusion-exclusion. Let  ${\mathcal H}_{n,k}$
be the set of all unicellular hypermonopoles $(\sigma,\alpha)$ satisfying
$\sigma=(1,\ldots,n)$ and 
$z(\alpha)=k$. For each $j\in\{1,\ldots,n\}$, let
${\mathcal H}_{n,k,j}$ be the subset of ${\mathcal H}_{n,k}$ also satisfying
$\alpha(j)=j$. Clearly we have
$$
r(n,k)=\left| {\mathcal H}_{n,k}-\bigcup_{j=1}^n {\mathcal H}_{n,k,j}\right|.
$$
Using the inclusion-exclusion formula we obtain
\begin{align}
\label{eq:r1}  
r(n,k)&=\sum_{i=0}^n (-1)^i \sum_{\{j_1,\ldots,j_i\}\subseteq \{1,\ldots,n\}}
\left| {\mathcal H}_{n,k,j_1} \cap \ldots \cap {\mathcal H}_{n,k,j_i}\right|.
\end{align}
First we show that it suffices to perform the summation on the right
hand side only up to $i=k-1$. All hypermaps $(\sigma,\alpha)\in
{\mathcal H}_{n,k,j_1} \cap \ldots  
\cap {\mathcal H}_{n,k,j_i}$ have the property that $j_1,\ldots,j_i$ are fixed
points of $\alpha$. Since $z(\alpha)=k$, we may restrict the summation
in~(\ref{eq:r1}) to $i\leq k$. Furthermore the case $i=k$ is possible
only if the cycles $(j_1),\ldots,(j_k)$ are all the cycles of $\alpha$ in
which case $k=n$ in contradiction with $k\leq n/2$.

From now on let us fix a subset $\{j_1,\ldots,j_i\}$ of
$\{1,\ldots,n\}$ for some $i\leq k-1$. Let $\sigma'$ be the cyclic
permutation of $\{1,\ldots,n\}-\{j_1,\ldots,j_i\}$ obtained from $(1,\ldots,n)$
by removing the elements $j_1,\ldots,j_i$.  Given any unicellular
hypermonopole $(\sigma,\alpha)\in {\mathcal H}_{n,k,j_1} \cap \ldots \cap
{\mathcal H}_{n,k,j_i}$, let us define the unicellular hypermonopole 
$(\sigma',\alpha')$ on the set of points
$\{1,\ldots,n\}-\{j_1,\ldots,j_i\}$ by the following procedure: 
\begin{enumerate}
\item We define $\pi=\alpha^{-1}\sigma$ as the unique face of
  $(\sigma,\alpha)$.  
\item We define the unique face $\pi'$ of $(\sigma',\alpha')$ as the
  cyclic permutation obtained by removing the elements
  $j_1,\ldots,j_i$ from $\pi$ . 
\item The permutation $\alpha'$ is given by $\alpha'=\sigma'\pi'^{-1}$.  
\end{enumerate}
The operation $(\sigma,\alpha)\mapsto (\sigma',\alpha')$ associates to
each element  of ${\mathcal H}_{n,k,j_1} \cap \ldots \cap {\mathcal H}_{n,k,j_i}$ a
unicellular hypermonopole $(\sigma',\alpha')$. The operation is
invertible: to obtain $\pi$ from $\pi'$ we must insert each $j\in
\{j_1,\ldots,j_i\}$ right before $j+1$. Hence we obtain a bijection
between the hypermaps in ${\mathcal H}_{n,k,j_1} \cap \ldots \cap {\mathcal H}_{n,k,j_i}$ and
the set of all unicellular hypermonopoles $(\sigma',\alpha')$ on  the
set of points $\{1,\ldots,n\}-\{j_1,\ldots,j_i\}$ satisfying
$z(\alpha)=k-i$. Therefore we have
$$
\left| {\mathcal H}_{n,k,j_1} \cap \ldots \cap {\mathcal
  H}_{n,k,j_i}\right|=H(n-i,k-i), 
$$
and the statement is a direct consequence of~(\ref{eq:r1}).
\end{proof}
\begin{corollary}
If $n-k$ is odd then $r(n,k)=0$. As a consequence the least value of $n$
for which $r(n,k)>0$ holds for some $k\leq \frac{n}{2}$ is $n=3$.
\end{corollary}
Indeed, if $n-k$ is odd then all terms $H(n-i,k-i)=0$ appearing on the
right hand side of \eqref{eq:rnk} are zero. 

The values of $r(n,k)$ for $3\leq n\leq 12$ are shown in
Table~\ref{tab:rnk}. They also listed them as \seqnum{A371665} in the
On-Line Encyclopedia of Integer Sequences~\cite{OEIS}. 
\begin{table}[h]
\centering  
\begin{tabular}{l||c|c|c|c|c|c|}
\diagbox{$n$}{$k$}& $1$&$ 2$ & $ 3$ & $ 4$ & $ 5$ & $ 6$\\
\hline
3& 1& & & & & \\
4& 0& 1& & & & \\
5& 8& 0& & & & \\
6& 0& 36& 0& & & \\
7& 180& 0& 49& & & \\
8& 0& 1\, 604& 0& 21 && \\
9& 8\, 064& 0& 5\, 144& 0 & & \\
10& 0& 112\, 608& 0& 7\, 680& 0 &\\
11& 604\, 800& 0& 604\, 428& 0& 5\, 445 & \\
12& 0& 11\, 799\, 360& 0& 1\, 669\, 052& 0& 1\, 485\\
\end{tabular}
\caption{The values of $r(n,k)$ for $3\leq n\leq 12$ and $1\leq k\leq
\lfloor n/2\rfloor$.}
\label{tab:rnk}
\end{table}  


Combining Lemma~\ref{lem:GL} and Equation~(\ref{eq:rnk}) we obtain the
following formula.

\begin{theorem}
  The numbers $r(n,k)$ satisfy
  $$
  \sum_{k=0}^{\lfloor n/2\rfloor} r(n,k)\cdot x^k =
  \sum_{i=0}^{n-1} \binom{n}{i} (-x)^{i} \cdot
  \frac{(x)^{n-i+1}-(x)_{n-i+1}}{(n-i)(n-i+1)}.  
  $$
\end{theorem}  
\begin{proof}
  By Lemma~\ref{lem:GL} the number $H(n-i,k-i)$ is given by
  $$
  H(n-i,k-i)=[x^{k-i}] \frac{(x)^{n-i+1}-(x)_{n-i+1}}{(n-i)(n-i+1)}=
[x^k]  x^i\frac{(x)^{n-i+1}-(x)_{n-i+1}}{(n-i)(n-i+1)}. 
  $$
The statement now follows from Equation~(\ref{eq:rnk}) after noticing
that we may extend the upper limit of the summation to $n$. The equation
$$
r(n,k)=\sum_{i=0}^{n} (-1)^{i} \binom{n}{i} H(n-i,k-i)
$$
also holds if we set $H(n,k)=0$ for $k\leq 0$. Lemma~\ref{lem:GL} is
still applicable: the expression $((x)^{(n+1)}-(x)_{n+1})/((n+1)n)$ is a
polynomial of $x$ with zero constant term, containing no negative powers
of $x$.  
\end{proof}
  
Lemma~\ref{lem:genusbound} and Proposition~\ref{prop:rnk} allow us to
compute the number of all reduced unicellular hypermonopoles of a fixed
genus, using the following result. 

\begin{proposition}
The number $u(g)$ of all reduced unicellular hypermonopoles of genus
$g$ is given by
$$
u(g)=\sum_{n=2g+1}^{4g} r(n,n-2g).
$$
\end{proposition}  
\begin{proof}
By~\eqref{eq:genusdefr} a unicellular hypermonopole with $k$ cycles has
genus $g$ if and only if $k=n-2g$ holds. As seen in
Lemma~\ref{lem:genusbound}, $n$ must be at least $2g+1$ and at most
$4g$.  
\end{proof}  

The first $10$ entries of the sequence $\{u(g)\}_{g=1}^{\infty}$ are the
following:

\begin{align*}
  &2, 114, 21538, 8698450, 6113735682, 6641411533106,\\
  &10323616703610338, 21755183272319116818,\\
&59718914489141881419202,
207083242485963591169089778. 
\end{align*}

\section{Acknowledgments}
The authors thank three anonymous referees for many helpful suggestions,
corrections and comments. 
The second author wishes to express his heartfelt thanks to Labri, Universit\'e
Bordeaux I, for hosting him as a visiting researcher in Summer 2023 and
in Spring 2024, where a great part of this research was performed. 
This work was partially supported by a
grant from the Simons Foundation (\#514648 to G\'abor Hetyei).
 

\begin{thebibliography}{99}

\bibitem{Alexeev-Zograf}
N. Alexeev and P. Zograf,
Random matrix approach to the distribution of genomic distance,
{\it J. of Comput. Biology} {\bf 21} (2014), 622--631. 

\bibitem{Bafna-Pevzner}
V. Bafna and P. A. Pevzner,
Sorting by transpositions, 
{\it SIAM J. Discrete Math.} {\bf 11} (1998), 224--240.
  
\bibitem{Boccara}
  G. Boccara,
Nombre de repr\'esentations d'une permutation comme produit de deux
cycles de longueurs donn\'ees,
{\it Discrete Math.} {\bf 29} (1980), 105--134. 

\bibitem{Bona-Flynn}
M. B\'ona and R. Flynn, 
The average number of block interchanges needed to sort a permutation
and a recent result of Stanley, 
{\it Inform. Process. Lett.} {\bf 109} (2009), 927--931.   

\bibitem{Cori}
R. Cori,
{\it Un Code pour les Graphes Planaires et ses Applications,}
Asterisque {\bf 27} (1975).

\bibitem{Cori-Machi}
R. Cori and A. Mach\`\i, 
Maps, hypermaps and their automorphisms: a survey, I, II, III,
{\it Exposition. Math.} {\bf 10} (1992), 403--427, 429--447, 449--467.
  
\bibitem{Cori-Hetyei-hypertrees}
  R. Cori and G. Hetyei,
  Spanning hypertrees, vertex tours and meanders,
  {\it European J. Combin.} {\bf 119} (2024), 103805. 

\bibitem{Cori-Marcus-Schaeffer}
R. Cori, M. Marcus, and G. Schaeffer, 
Odd permutations are nicer than even ones,
{\it European J. Combin.} {\bf 33} (2012), 1467--1478.   

\bibitem{Doignon-Labarre}
J.-P.  Doignon and A. Labarre, 
On Hultman numbers, 
{\it J. Integer Sequences} {\bf 10} (2007), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL10/Doignon/doignon77.html}{Article 07.6.2}. 

\bibitem{Grusea-Labarre}
S. Grusea and A. Labarre, 
The distribution of cycles in breakpoint graphs of signed permutations,
{\it Discrete Appl. Math.} {\bf 161} (2013), 1448--1466.   

\bibitem{Hultman}
A. Hultman, Toric Permutations, Master's thesis, Department of Mathematics,
KTH, Stockholm, Sweden, 1999.   

\bibitem{Jacques}
A. Jacques,
Sur le genre d'une paire de substitutions,
{\it C.  R. Acad. Sci. Paris} {\bf 267} (1968), 625--627.

\bibitem{Kreweras} 
G. Kreweras, 
Sur les partitions non crois\'ees d'un cycle,
{\it Discrete Math.} {\bf 1} (1972), 333--350.

\bibitem{Machi}
A. Mach\`\i, 
On the complexity of a hypermap,
{\it Discrete Math.} {\bf 42} (1982), 221--226.   

\bibitem{OEIS}
OEIS Foundation Inc. (2024), The On-Line Encyclopedia of Integer
Sequences, Published electronically at \url{https://oeis.org}. 

\bibitem{Stanley-EC2}
  R. P. Stanley,
  {\it Enumerative Combinatorics, Vol. II,}
  Cambridge University Press, 1999.
  (Supplementary Exercises (without solutions) for
Ch. 7 (Symmetric functions)); Internet resource available at
\url{https://math.mit.edu/~rstan/ec/ch7supp.pdf}.  

\bibitem{Stanley-cycles}
R. P. Stanley, 
Two enumerative results on cycles of permutations, 
{\it European J. Combin.} {\bf 32} (2011), 937--943. 
  
\bibitem{Zagier}
D. Zagier, 
On the distribution of the number of cycles of elements in symmetric
groups,
{\it Nieuw Arch. Wisk.} {\bf 13} (1995), 489--495. 
  
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 05C30; Secondary 05C10, 05C15.

\noindent \emph{Keywords: } set partition, noncrossing partition,
genus of a hypermap. 

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A164652} and 
\seqnum{A371665}.) 

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 24 2024;
revised versions received  December 14 2024; April 1 2025; April 2 2025.
Published in {\it Journal of Integer Sequences}, April 15 2025.

\bigskip
\hrule
\bigskip

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



\end{document}

