\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\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{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

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

\DeclareMathOperator{\Gr}{Gr}
\DeclareMathOperator{\Stab}{Stab.Prod}
\DeclareMathOperator{\Spec}{Spec}
\DeclareMathOperator{\cyc}{cyc}
\DeclareMathOperator{\Part}{Part}

\newcommand\comment[1]{{\textcolor{red}{\bf [[ #1 ]]}}}

\begin{document}

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

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

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

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


\begin{center}
\vskip 1cm{\LARGE\bf Hultman Numbers and Generalized \\
\vskip .12in
Commuting Probability in Finite Groups}
\vskip 1cm
\begin{minipage}[t]{0.5\textwidth}
\begin{center}
Yonah Cherniavsky\\
Department of Mathematics\\
Ariel University\\
Israel\\
\href{mailto:yonah@ariel.ac.il}{\tt yonah@ariel.ac.il}  \\
\ \\
Avraham Goldstein\\
Borough of Manhattan Community College\\
The City University of New York\\
USA \\
\href{mailto:avraham.goldstein.nyc@gmail.com}{\tt avraham.goldstein.nyc@gmail.com }\\[1ex]
\end{center}
\end{minipage}
\begin{minipage}[t]{0.45\textwidth}
\begin{center}
Vadim E. Levit\\
Department of Computer Sciences\\
Ariel University\\
Israel\\
\href{mailto:levitv@ariel.ac.il}{\tt levitv@ariel.ac.il}\\
\ \\
Robert Shwartz\\
Department of Mathematics\\
Ariel University\\
Israel\\
\href{mailto:robertsh@ariel.ac.il}{\tt robertsh@ariel.ac.il} \\
\end{center}
\end{minipage}
\end{center}

\vskip .2in

\begin{abstract}
Let $G$ be a finite group. We investigate the distribution of the
probabilities of the permutation equality
\[
a_{1}a_{2}\cdots a_{n-1}a_{n}=a_{\pi_{1}}a_{\pi_{2}}\cdots a_{\pi_{n-1}}
a_{\pi_{n}}
\]
as $\pi$ varies over all the permutations in $S_{n}$. The probability
\[
{\Pr}_{\pi}(G)=\Pr(a_{1}a_{2}\cdots a_{n-1}a_{n}=a_{\pi_{1}}a_{\pi_{2}}\cdots
a_{\pi_{n-1}}a_{\pi_{n}})
\]
is identical to $\Pr_{1}^{\omega}(G)$, with
\[
\omega=a_{1}a_{2} \cdots a_{n-1}a_{n}a_{\pi_{n}}^{-1}a_{\pi_{n-1}}^{-1}\cdots
a_{\pi_{2}}^{-1}a_{\pi_{1}}^{-1},
\]
which was defined and studied by Das and Nath. The notion of commutativity
degree, or the probability of a permutation equality $a_{1}a_{2}=a_{2}a_{1}$,
for which $n=2$ and $\pi=\langle2\;\;1\rangle$, was introduced and assessed by
Erd\H{o}s and Turan in 1968 and by Gustafson in 1973. Gustafson established a
relation between the probability of $a_{1},a_{2}\in G$ commuting and the
number of conjugacy classes in $G$. In this work we define several other
parameters, which depend only on a certain interplay between the conjugacy
classes of $G$, and compute probabilities of permutation equalities in terms
of these parameters. It turns out that for a permutation $\pi$, the
probability of its permutation equality depends only on the number
$c(\Gr(\pi))$ of alternating cycles in the cycle graph $\Gr(\pi)$ of $\pi
$. The cycle graph of a permutation was introduced by Bafna and Pevzner, and
the number of alternating cycles in it was introduced by Hultman. Hultman
numbers are the numbers of different permutations with the same number of
alternating cycles in their cycle graphs. We show that the spectrum of
probabilities of permutation equalities in a generic finite group, as $\pi$
varies over all the permutations in $S_{n}$, corresponds to partitioning $n!$
as the sum of the corresponding Hultman numbers.


\end{abstract}

\section{Introduction}

Study of the (\textit{commuting probability}), i.e., the probability that two
random elements in a finite group $G$ commute, is very natural. In 1968
Erd\H{o}s and Turan \cite{ET} proved that
\[
\Pr(a_{1}a_{2}=a_{2}a_{1})>\frac{\log(\log|G|)}{|G|}.
\]
In the early 1970s, Dixon observed that the commuting probability is $\leq
\frac{1}{12}$ for every finite non-Abelian simple group. 
(This inequality was
submitted as an open problem in the Canadian Mathematical Bulletin \textbf{13}
(1970), with a solution appearing in 1973.) In 1973, Gustafson \cite{G} proved
that the commuting probability is equal to $\frac{k(G)}{|G|}$, where $k(G)$ is
the number of conjugacy classes in $G$. Based on that result, Gustafson
further obtained the upper bound of the commuting probability in a finite
non-Abelian group to be $\frac{5}{8}$. Commuting probability actually attains
the upper bound of $\frac{5}{8}$ in many finite groups, including $D_{8}$ and
$Q_{8}$. A significant amount of work has been done in assessing the commuting
probability for various special cases of finite groups. For example, Lescot
\cite{L} studied the case of dihedral groups. Clifton, Guichard, and Keef
\cite{CGK} studied the case of direct product of dihedral groups. Erovenko and
Surg \cite{ErSu} studied the case of wreath products of two Abelian groups.
Guralnick and Robinson \cite{GerRob} studied the case of non-solvable groups.
Additional information on development of the subject and its applications is
found in Dixon \cite{Dixon}, Jezernik and Moravec \cite{JM}, and Lescot,
Nguyen, and Yang \cite{LNY2014}.

Much research concerning probabilistic aspects of finite groups has been done
since the introduction of commuting probability. Many of these studies can be
regarded as variations of the commuting probability problem. For instance,
Erd\H{o}s and Straus \cite{ES} computed the number of ordered $k$-tuples of
elements of a group $G$ that have pairwise commuting elements. Another example
is due to Pournakia and Sobhani \cite{PS}, who determined the probability of
the commutator of two random group elements of $G$ being equal to a given
element of $G$. In another example Blackburn, Britnell, and Wildon \cite{BBW}
obtained the probability that two random elements of $G$ are conjugate.

A variation of the commuting probability problem, leading to its
generalization, is how to compute the number of balanced $G$-valued labelings
on various finite graphs. Cherniavsky, Goldstein, and Levit \cite{CGL,CGL2017}
computed the number of balanced $G$-valued labelings on both directed and
undirected graphs, when the group $G$ is Abelian. Cherniavsky, Goldstein,
Levit, and Shwartz \cite{CGLS2016} considered a non non-Abelian case.

A different direction in generalization of commuting probability appears in
Das and Nath \cite{DasNath1, NathDash1}. They studied the probability $\Pr
_{g}^{\omega}(G)$ of the equality
\[
a_{1}a_{2} \cdots a_{n-1}a_{n}a_{\pi_{n}}^{-1}a_{\pi_{n-1}}^{-1}\cdots a_{\pi_{2}
}^{-1}a_{\pi_{1}}^{-1}=g
\]
for a fixed element $g$ in a finite group $G$. The word
\[
a_{1}a_{2}\cdots a_{n-1}a_{n}a_{\pi_{n}}^{-1}a_{\pi_{n-1}}^{-1}\cdots
a_{\pi_{2}}^{-1}a_{\pi_{1}}^{-1},
\]
where $\omega$ denotes the product $a_{1}a_{2}\cdots a_{n-1}a_{n}$ vary over
all the elements of $G$. Nath \cite{Nath2011} generalized the classical study
of the commuting probability for which $\omega=a_{1}a_{2}a_{1}^{-1}a_{2}^{-1}$
and $g=1$.

In this paper we take a slightly different approach in generalizing the
commuting probability. Let
\[
\pi=\langle\pi_{1}\;\;\pi_{2}\;\;\ldots\;\;\pi_{n}\rangle
\]
be a permutation in $S_{n}$, written in a shortened form of the two-row
notation. We define $\Pr_{\pi}(G)$ as the \textit{permutation probability} of
the equality
\[
a_{1}a_{2}\cdots a_{n}=a_{\pi_{1}}a_{\pi_{2}}\cdots a_{\pi_{n-1}}a_{\pi_{n}}
\]
in $G$. Notice that $\Pr_{\langle2\;\;1\rangle}(G)$ is just the commuting
probability in $G$.

Notice also, that the probability
\[
{\Pr}_{\pi}(G)=\Pr(a_{1}a_{2}\cdots a_{n-1}a_{n}=a_{\pi_{1}}a_{\pi_{2}}\cdots
a_{\pi_{n-1}}a_{\pi_{n}})
\]
is identical to $\Pr_{1}^{\omega}(G)$, with
\[
\omega=a_{1}a_{2}\cdots a_{n-1}a_{n}a_{\pi_{n}}^{-1}a_{\pi_{n-1}}^{-1}\cdots
a_{\pi_{2}}^{-1}a_{\pi_{1}}^{-1},
\]
as Das and Nath \cite{DasNath1, NathDash1} have defined it.

In this work we

\begin{itemize}
\item obtain a new description of $\Pr_{\pi}(G)$ in terms of non-negative
integers $c_{i_{1},\ldots,i_{n};j}(G)$. Integer $c_{i_{1},\ldots,i_{n};j}(G)$
is the number of different ways in which an element from a conjugacy class
$\Omega_{j}\subset G$ can be broken into a product of elements from the
conjugacy classes $\Omega_{1_{1}},\ldots,\Omega_{i_{n}}\subset G$.

\item prove that $\Pr_{\pi}(G)$, for a fixed finite group $G$, depends only on
the number of alternating cycles in the cycle graph $\Gr(\pi)$ of the
permutation $\pi$.

\item show that the spectrum of permutation probabilities in a finite
non-Abelian group, as $\pi$ varies over all the elements of $S_{n}$, is the
partition of $n!$ into a sum of the Hultman numbers \seqnum{A164652}.
\end{itemize}

The following three theorems constitute the main finding of this paper

\begin{itemize}
\item Theorem \ref{main.theorem.1}: Let $G$ be a finite group. Let $\phi\in
S_{n}$ be a permutation whose cycle graph $\Gr(\phi)$ contains $k$ alternating
cycles. Then
\[
{\Pr}_{\phi}(G)={\Pr}^{n+1-k}(G)=\Pr(a_{1}a_{2}\cdots a_{n-k}a_{n+1-k}
=a_{n+1-k}a_{n-k}\cdots a_{2}a_{1}).
\]


\item Theorem \ref{main.theorem.2}: Let $G$ be a finite non-Abelian group. Let
$\phi$ and $\theta$ be two permutations in $S_{n}$. Then, $\Pr_{\phi}
(G)=\Pr_{\theta}(G)$ if and only if the number of alternating cycles in the
cycle graph $\Gr(\theta)$ equals the number of alternating cycles in the cycle
graph of $\Gr(\phi)$. This implies that the spectrum of permutation
probabilities in a non-Abelian group $G$ consists of exactly $\left\lfloor
\frac{n}{2}\right\rfloor +1$ different numbers, each number corresponding to
its unique Hultman class of permutations in $S_{n}$.

\item Theorem \ref{main.result.3}: Let $G$ be a finite group. Then
\begin{align*}
{\Pr}^{2t}(G) & =\Pr(a_{1}a_{2}\cdots a_{2t}=a_{2t}a_{2t-1}\cdots a_{1})\\
& =\Pr(a_{1}a_{2}a_{3}a_{4}\cdots a_{2t-1}a_{2t}=a_{2}a_{1}a_{4}a_{3}\cdots
a_{2t}a_{2t-1})\\
& =\frac{\sum\limits_{x_{1},x_{2},\ldots,x_{t}\in G}|{\Stab}_{n}(x_{1}
,x_{2},\ldots,x_{t}))|}{|G|^{2t}}\\
& =\frac{1}{|G|^{t}}\cdot\sum\limits_{i_{1},i_{2},\ldots,i_{t},j=1}
^{c(G)}\frac{\left\vert \Omega_{j}\right\vert \cdot c_{i_{1},i_{2}
,\ldots,i_{t};j}^{2}(G)}{\left\vert \Omega_{i_{1}}\right\vert \cdot\left\vert
\Omega_{i_{2}}\right\vert \cdot\cdots\cdot\left\vert \Omega_{i_{t}}\right\vert
}
\end{align*}

\end{itemize}

\subsection{Basic definitions and notation}

For a natural number $n$, $S_{n}$ denotes the group of all permutations of
$n$. We usually write a permutation $\pi\in S_{n}$ as
\[
\pi=\langle\pi_{1}\;\;\pi_{2}\;\;\ldots\;\;\pi_{n}\rangle,
\]
which is commonly known as ``the shortened way of the two row notation".
Sometimes, we also use the cyclic notation for a permutation $\pi\in S_{n}$,
in which case we use parentheses and commas. Thus, for example, $(\theta
_{1},\theta_{2},\theta_{3})$ represents the cycle permutation 
\newline
$\theta_{1}\mapsto\theta_{2}\mapsto\theta_{3}\mapsto\theta_{1}$. We refer to
such cycle permutations as ``cycles".

We use $G$ to denote a finite group. For a finite set $S$, we denote the size
of $S$ by $\left\vert S\right\vert $. Two elements $g_{1}, g_{2}\in G$ are
called conjugate if there exists $h\in G$ such that $g_{2}=h^{-1}g_{1}h$.
Conjugacy is an equivalence relation in $G$. As such, it breaks $G$ into
conjugacy classes. Let $c(G)$ denotes The number of conjugacy classes in $G$.
Let $\Omega_{1},\ldots,\Omega_{c(G)}$ denotes the conjugacy classes.
Let$\Omega(g)$ denotes the conjugacy class of $g$ for $g\in G$. The
centralizer $C_{G}(g)$ of an element $g\in G$ is the set of all elements of
$G$ that commute with $g$. Recall that for every all $g\in G$,
\[
\left\vert G\right\vert =\left\vert \Omega(g)\right\vert \cdot\left\vert
C_{G}(g)\right\vert .
\]


Let $C(G)$ denotes the set $\{\Omega_{1},\ldots,\Omega_{c(G)}\}$ of all
conjugacy classes in $G$. Let $G^{\prime}$ denotes the commutator subgroup of
$G$, which is the minimal subgroup of $G$ containing all elements of $G$ of
the form $ghg^{-1}h^{-1}$, where $g,h\in G$. We use the notation $h^{g}$ to
denote $g^{-1}hg$. To indicate that that $g,h\in G$ are conjugate in $G$ we
write $g\sim h$. The center $Z(G)\subseteq G$ is the subgroup of $G$,
consisting of all elements $h\in G$ for which $h^{g}=h$ for all $g\in G$.

Let $D_{2n}$ denotes the dihedral group with $2n$ elements, let $Q_{8}$
denotes the multiplicative group of unit quaternions, which has $8$ elements.

\begin{definition}
\label{Stab.prod.def} For a sequence $(g_{1},g_{2},\ldots,g_{n})$ of $n$
elements of $G$, let \newline${\Stab}_{n}(g_{1},g_{2},\ldots,g_{n})$ denotes
the set of all the sequences $(a_{1},a_{2},\ldots,a_{n})$ of $n$ elements of
$G$ such that
\[
a_{1}^{-1}g_{1}a_{1}\cdot a_{2}^{-1}g_{2}a_{2}\cdot\cdots\cdot a_{n}^{-1}
g_{n}a_{n}=g_{1}\cdot g_{2}\cdot\cdots\cdot g_{n}.
\]

\end{definition}

Notice that ${\Stab}_{n}(g_{1},g_{2},\ldots,g_{n})$ is a generalization of the
notion of the centralizer of an element $g\in G$. Indeed, ${\Stab}_{1}(g) $ is
just $C_{G}(g)$.

\begin{definition}
The nonnegative integer $c_{i_{1},\ldots,i_{n};j}(G)$ denotes the number of
different ways of breaking a fixed element $y\in\Omega_{j}(G)$ into a product
$y=x_{1}x_{2}\cdots x_{n}$ of elements $x_{1}\in\Omega_{i_{1}}(G),x_{2}
\in\Omega_{i_{2}}(G),\ldots,x_{n}\in\Omega_{i_{n}}(G)$.
\end{definition}

The number $c_{i_{1},\ldots,i_{n};j}(G)$ does not depend on the choice of the
element $y\in\Omega_{j}(G)$. Indeed, if we take some other $y^{\prime}
\in\Omega_{j}(G)$, then there exists some $g\in G$ such that $y^{\prime
}=gyg^{-1}$ and $y=g^{-1}y^{\prime}g$. Then each product $y=x_{1}x_{2}\cdots
x_{n}$ corresponds to the product
\[
y^{\prime}=gyg^{-1}=(gx_{1}g^{-1})\cdot(gx_{2}g^{-1})\cdot\cdots\cdot
(gx_{n}g^{-1}),
\]
in which each $x_{t}^{\prime}=(gx_{t}g^{-1})$ belongs to the same conjugacy
class $\Omega_{i_{t}}(G)$ as $x_{t}$. Vice versa, each product $y^{\prime
}=x_{1}^{\prime}x_{2}^{\prime}\cdots x_{n}^{\prime}$ corresponds back to the
product
\[
y=g^{-1}y^{\prime}g=(g^{-1}x_{1}^{\prime}g)\cdot(g^{-1}x_{2}^{\prime}
g)\cdot\cdots\cdot(g^{-1}x_{n}^{\prime}g).
\]
Thus, we see that the number of such different products is the same for any
$y$ and $y^{\prime}$ in $\Omega_{j}(G)$.

Notice that $c_{i_{1},\ldots,i_{n};j}(G)$ can be zero, and that $c_{i;j}(G)=1
$ if $i=j$, and $c_{i;j}(G)=0$ if $i\ne j$.

\begin{definition}
Let $L_{\pi}(G)$ denotes the number of different solutions of the equation
\[
a_{1}a_{2}\cdots a_{n-1}a_{n}=a_{\pi_{1}}a_{\pi_{2}}\cdots a_{\pi_{n-1}}
a_{\pi_{n}}
\]
in $G$. Clearly, $\Pr_{\pi}(G)=\frac{L_{\pi}(G)}{|G|^{n}}$.
\end{definition}

\begin{definition}
We define $\Pr^{n}(G)$ as $\Pr_{\langle n\;\;n-1\;\;\ldots\;\;2\;\;1\rangle
}(G)$.
\end{definition}

For a permutation $\pi\in S_{n}$ define $\omega(\pi)$ as a formal expression
$a_{1}\cdots a_{n}\cdot a_{\pi_{n}}^{-1}\cdots a_{\pi_{1}}^{-1}$. Then
$\Pr_{\pi}(G)$ is identical to $\Pr_{1}^{\omega}(G)$, which was defined by Das
and Nath \cite{DasNath1, DasNath2, NathDash1}. Similarly, $\Pr^{n}(G)$ is
identical to $\Pr_{1}^{n}(G)$, as defined by Das and Nath \cite{DasNath1,
DasNath2, NathDash1}. For further information on calculations, properties, and
estimates of $\Pr_{1}^{\omega}(G)$ and $\Pr_{1}^{n}(G)$ we refer the reader to
the papers of Das and Nath \cite{DasNath1, DasNath2, NathDash1}.

\begin{definition}
Let ${\Spec}_{n}(G)$ denotes the set of all $\Pr_{\pi}(G)$, as $\pi$ runs over
all the permutations from $S_{n}$.
\end{definition}

\begin{definition}
A finite group $G$ is called generic if for two permutations $\pi,\theta\in
S_{n}$, $\Pr_{\pi}(G)=\Pr_{\theta}(G)$ only if $\Pr_{\pi}(H)=\Pr_{\theta}(H)$
for every finite non-Abelian group $H$.
\end{definition}

\begin{definition}
Let ${\Part}_{n}$ denotes the partition of $S_{n}$ into subsets of
permutations, for which the permutation equalities have the same probability
for every finite group.
\end{definition}

For a generic group $G$, there is a natural isomorphism between the sets
${\Spec}_{n}(G)$ and ${\Part}_{n}$. We refer to ${\Spec}_{n}(G)$, for a
generic group $G$, as the spectrum of permutation probabilities. Theorem
\ref{generic.group} makes use of \cite[Thm.~6.8]{DasNath3} in order to
show that every non-Abelian finite group is generic.

\begin{definition}
\label{def.isoclinic} Hall \cite{Hall1940} defined two groups $G_{1}$ and
$G_{2}$ to be isoclinic if the following three conditions hold

\begin{itemize}
\item There exists an isomorphism $\alpha$ from $G_{1}/Z(G_{1})$ onto
$G_{2}/Z(G_{2})$;

\item There exists an isomorphism $\beta$ from the commutator subgroup
$G_{1}^{\prime}$ to the commutator subgroup $G_{2}^{\prime}$;

\item If $\alpha(a_{1}Z(G_{1}))=a_{2}Z(G_{2})$ and $\alpha(b_{1}
Z(G_{1}))=b_{2}Z(G_{2})$, then
\[
\beta(a_{1}^{-1}b_{1}^{-1}a_{1}b_{1})=a_{2}^{-1}b_{2}^{-1}a_{2}b_{2}.
\]

\end{itemize}
\end{definition}

For example, every two Abelian groups are isoclinic. The dihedral group
$D_{8}$ and the quaternion group $Q_{8}$ are two non-Abelian groups, which are isoclinic.

\begin{definition}
Buckley \cite{Buckley2014} defined two groups $G_{1}$ and $G_{2}$ to be weakly
isoclinic if the first two conditions of Definition \ref{def.isoclinic} hold.
Namely, if

\begin{itemize}
\item There exists an isomorphism $\alpha$ from $G_{1}/Z(G_{1})$ onto
$G_{2}/Z(G_{2})$;

\item There exists an isomorphism $\beta$ from the commutator subgroup
$G_{1}^{\prime}$ to the commutator subgroup $G_{2}^{\prime}$.
\end{itemize}
\end{definition}

\section{Preliminaries}

In the Lemmas \ref{commute-conjug} and \ref{conjug-decomp} we reproduce
well-known group theory results, which are fundamental for our work.

\begin{lemma}
\label{commute-conjug} For any $a,b\in G$ we have $ab\sim ba$.
\end{lemma}

\begin{proof}
$b(ab)b^{-1}=babb^{-1}=ba.$
\end{proof}

\begin{lemma}
\label{conjug-decomp} For any $x$ and $y$ from the same conjugacy class
$\Omega_{i}\subset G$, there are exactly
\[
\frac{\left\vert G\right\vert }{\left\vert \Omega_{i}\right\vert }=\left\vert
C_{G}(x)\right\vert =\left\vert C_{G}(y)\right\vert
\]
different ways to break $x$ into a product $x=ab$ of two elements $a,b\in G$,
so that $ba=y$.
\end{lemma}

\begin{proof}
Since $x\sim y$, there exists some $b\in G$ such that $bxb^{-1}=y$. We define
$a=xb^{-1}$. Thus, $ab=xb^{-1}b=x$ and $ba=bxb^{-1}=y$. For each pair
$a^{\prime},b^{\prime}\in G$, such that $a^{\prime}b^{\prime}=x$, there exists
a unique element $g=b^{\prime}b^{-1}=\left(  a^{\prime}\right)  ^{-1}a$ in
$G$, such that $a^{\prime}=ag^{-1}$ and $b^{\prime}=gb$. Now,
\[
b^{\prime}a^{\prime}=gbag^{-1}=gyg^{-1}.
\]
Hence, the pairs $(a^{\prime},b^{\prime})$ of elements in $G$, such that
$a^{\prime}b^{\prime}=x$ and $b^{\prime}a^{\prime}=y$, are in one-to-one
correspondence with the elements $g$ from $C_{G}(Y)$. So, the number of pairs
of elements $a^{\prime},b^{\prime}\in G$, such that $a^{\prime}b^{\prime}=x$
and $b^{\prime}a^{\prime}=y$, is equal to $|C_{G}(y)| $. But
\[
\left\vert C_{G}(y)\right\vert =\frac{|G|}{|\Omega_{i}|}=|C_{G}(x)|.
\]

\end{proof}

The following classical result on commuting probability, which is due to
Gustafson \cite{G}, follows immediately from Lemmas \ref{commute-conjug} and
\ref{conjug-decomp}.

\begin{theorem}
[Gustafson]\label{commute} $\Pr^{2}(G)=\Pr(a_{1}a_{2}=a_{2}a_{1})=\frac
{c(G)}{|G|}$.
\end{theorem}

\begin{proof}
For each $x\in G$ there are exactly $\frac{|G|}{|\Omega(x)|}$ different ways
to write $ab=x=ba$ with $a,b\in G$. Thus, for each $\Omega_{i}$ there are
$|G|$ different equations $ab=x=ba$ with $a,b\in G$ and $x\in\Omega(i)$.
Indeed, there are $|\Omega(x)|$ different elements $x$ in $\Omega_{i}$, and
for each choice of $x$, there are $\frac{|G|}{|\Omega(x)|}$ different ways to
break that $x$ into a product of commuting elements $a,b\in G$. Thus,
$L_{\langle2\;\;1\rangle}(G)=\left\vert G\right\vert \cdot c(G)$ and
\[
{\Pr}^{2}(G)=\frac{\left\vert G\right\vert \cdot c(G)}{\left\vert G\right\vert
^{2}}=\frac{c(G)}{\left\vert G\right\vert }.
\]

\end{proof}

\section{Calculation of ${\Spec}_{3}(G)$ and ${\Spec}_{4}(G)$}

We address the general case of permutational equations in the following
sections. In this section we study permutational equations for permutations
 from $S_{3}$ and $S_{4}$, which is self-contained and will help to illustrate
the general case.

\begin{lemma}
\label{inverse.general} For any permutation $\pi\in S_{n}$, with its inverse
$\pi^{-1}\in S_{n}$, the probability $\Pr_{\pi}(G)=\Pr_{\pi^{-1}}(G)$.
\end{lemma}

\begin{proof}
By definition,
\[
{\Pr}_{\pi}(G)=\Pr(a_{1}a_{2}\cdots a_{n-1}a_{n}=a_{\pi_{1}}a_{\pi_{2}}\cdots
a_{\pi_{n-1}}a_{\pi_{n}})
\]
Let $b_{1}$ denotes $a_{\pi_{1}}$, $b_{2}$ denotes $a_{\pi_{2}}$, $\ldots$,
$b_{n}$ denotes $a_{\pi_{n}}$ . Then $a_{1}=b_{(\pi^{-1})_{1}}$,
$a_{2}=b_{(\pi^{-1})_{2}}$, $\ldots$, $a_{n}=b_{(\pi^{-1})_{n}}$. As
$a_{1},a_{2},\ldots,a_{n}$ run over all the elements of $G$, so do
$b_{1},b_{2},\ldots,b_{n}$. Thus,
\[
{\Pr}_{\pi^{-1}}(G)=\Pr(b_{({\pi}^{-1})_{1}}b_{({\pi}^{-1})_{2}}\cdots
b_{({\pi}^{-1})_{n-1}}b_{({\pi}^{-1})_{n}}=b_{1}b_{2}\cdots b_{n-1}b_{n}
)={\Pr}_{\pi}(G).
\]

\end{proof}

We continue with Lemma \ref{threecommute}, which is a particular case, in
which $n=1$, of a general fact observed by Das and Nath \cite{DasNath2} that
for
\[
\omega_{1}=a_{1}a_{2}\cdots a_{2n}a_{1}^{-1}a_{2}^{-1}\cdots a_{2n}^{-1},
\]
\[
\omega_{2}=a_{1}a_{2}\cdots a_{2n+1}a_{1}^{-1}a_{2}^{-1}\cdots a_{2n+1}^{-1},
\]
and for any $g\in G$, there is an equality $\Pr_{g}^{\omega_{1}}(G)=\Pr
_{g}^{\omega_{2}}(G)$.

\begin{lemma}
\label{threecommute} The probability $\Pr^{3}(G)=\Pr_{\langle
3\;\;2\;\;1\rangle}(G)=\Pr(a_{1}a_{2}a_{3}=a_{3}a_{2}a_{1})$ is equal to the
probability $\Pr^{2}(G)=\Pr_{\langle2\;\;1\rangle}(G)=\Pr(a_{1}a_{2}
=a_{2}a_{1})=\frac{|c(G)|}{|G|}$.
\end{lemma}

\begin{proof}
For convenience, we rename $a_{1}$ to $a$, $a_{2}$ to $b$, and $a_{3}$ to $c$.
Now, from $abc=cba$ we obtain $abcb=cbab$. Thus, the commutator $[cb,ab]=1$.
Therefore, if we choose and fix an element $b\in G$, then the other two
elements $a$ and $c$ should be chosen in a such way that $[ab,cb]=1$.

Hence, for every of choice of an element $a\in G$, we must choose an element
$c\in G$ in such a way that $cb\in C_{G}(ab)$.

Since $G$ is a group, the product $ab$, as $b\in G$ is fixed and $a$ runs over
all the elements of $G$, produces elements $x\in G$, and each $x\in G$ is
produced exactly one time. Similarly, the product $cb$, as $b\in G$ is fixed
and $c$ runs over all the elements of $C_{G}(ab)\cdot b^{-1}$, produces
elements $y\in C_{G}(ab)$, and each element $y\in C_{G}(ab)$ is produced
exactly one time. Since $b\in G$ runs over all the elements of $G$, we get
\[
\label{Pr3}L_{\langle3\;\;2\;\;1\rangle}(G)=|G|\cdot\sum\limits_{y\in
G}\left\vert C_{G}(y)\right\vert =|G|^{2}\cdot|C(G)|.
\]
Dividing Equation \ref{Pr3} by $|G|^{3}$ gives us
\[
{\Pr}_{\langle3\;\;2\;\;1\rangle}(G)=\frac{|C(G)|}{|G|}={\Pr}_{\langle
2\;\;1\rangle}(G).
\]

\end{proof}

We will now prove that for all five nontrivial permutations in $S_{3}$, their
probabilities are the same. Notice that these five permutations have two
alternating cycles in their cycle graphs, but the identity permutation in
$S_{3}$ has four alternating cycles in its cycle graph. A detailed explanation
of cycle graphs and alternating cycles, followed by a clarification of their
relevance to probabilities, will be made in Section 4.

\begin{theorem}
\label{specthree} For every nontrivial $\pi\in S_{3}$, the probability
\newline$\Pr(a_{1}a_{2}a_{3}=a_{\pi_{1}}a_{\pi_{2}}a_{\pi_{3}})=\frac
{c(G)}{|G|}$. Thus, the spectrum ${\Spec}_{3}(G)$ is $\{\frac{c(G)}{|G|},1\}$.
\end{theorem}

\begin{proof}
By Lemma \ref{threecommute}, $\Pr(a_{1}a_{2}a_{3}=a_{3}a_{2}a_{1})=\frac
{c(G)}{|G|}$. Clearly,
\[
\Pr(a_{1}a_{2}a_{3}=a_{2}a_{1}a_{3})=\Pr(a_{1}a_{2}=a_{2}a_{1})=\frac
{c(G)}{|G|}
\]
and
\[
\Pr(a_{1}a_{2}a_{3}=a_{1}a_{3}a_{2})=\Pr(a_{2}a_{3}=a_{3}a_{2})=\frac
{c(G)}{|G|}.
\]


To compute $\Pr(a_{1}a_{2}a_{3}=a_{3}a_{1}a_{2})$, notice that if $g$ denotes
the product $a_{1}a_{2}$. Then, as $a_{1}$ and $a_{2}$ run over all the
elements of $G$, their product $g$ will also run over all the elements of $G$,
becoming equal to every element of $G$ exactly $|G|$ times. Thus, the number
$L(a_{1}a_{2}a_{3}=a_{3}a_{1}a_{2})$ of different solutions of the equation
$a_{1}a_{2}a_{3}=a_{3}a_{1}a_{2}$ in $G$ is $|G|$ times the number of
different solutions of the equation $ga_{3}=a_{3}g$ in $G$. Hence,
\[
\Pr(a_{1}a_{2}a_{3}=a_{3}a_{1}a_{2})=\frac{\left\vert G\right\vert
\cdot\left\vert G\right\vert \cdot c(G)}{\left\vert G\right\vert ^{3}}
=\frac{c(G)}{\left\vert G\right\vert }.
\]


By Lemma \ref{inverse.general}, we get
\[
\Pr(a_{1}a_{2}a_{3}=a_{2}a_{3}a_{1})=\Pr(a_{1}a_{2}a_{3}=a_{3}a_{1}
a_{2})=\frac{c(G)}{\left\vert G\right\vert }.
\]
Obviously, $\Pr(a_{1}a_{2}a_{3}=a_{1}a_{2}a_{3})=1$.
\end{proof}

We now investigate permutation probabilities for $S_{4}$.

\begin{lemma}
\label{Case.4.1} For any nontrivial permutation $\pi\in S_{4}$, if $\pi_{1}=1
$ or $\pi_{4}=4$, then \newline$\Pr_{\pi}(G)=\frac{c(G)}{|G|}$.
\end{lemma}

\begin{proof}
If $\pi_{1}=1$, then the equation $a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}
}a_{\pi_{3}}a_{\pi_{4}}$ is equivalent to the equation $a_{2}a_{3}a_{4}
=a_{\pi_{2}}a_{\pi_{3}}a_{\pi_{4}}$. By Theorem \ref{specthree}, there are
$|G|^{2}\cdot c(G)$ different equations $a_{2}a_{3}a_{4}=a_{\pi_{2}}a_{\pi
_{3}}a_{\pi_{4}}$ in $G$. Each of these equations corresponds exactly to $|G|$
different equations of the form $a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}
}a_{\pi_{3}}a_{\pi_{4}}$ (since $a_{1}$ can be any element of $G$). Thus
$L_{\pi}(G)=|G|^{3}\cdot c(G)$ and ${\Pr}_{\pi}(G)=\frac{c(G)}{|G|}$. The same
argument, but with $a_{4}$ instead of $a_{1}$, is applied for $\pi_{4}=4$.
\end{proof}

\begin{lemma}
\label{Case.4.2} For all nontrivial permutations $\pi\in S_{4}$, such that
$\pi_{i+1}=\pi_{i}+1$ for some $1\leq i\leq3$, the probability ${\Pr}_{\pi
}(G)=\frac{c(G)}{|G|}$.
\end{lemma}

\begin{proof}
The condition $\pi_{i+1}=\pi_{i}+1$ implies that the permutation $\pi$ keeps
two consecutive numbers $\pi_{i}$ and $\pi_{i}+1$ in their consecutive order.
Such are, for example, the permutations $\langle4\;\;3\;\;1\;\;2\rangle$,
$\langle3\;\;4\;\;1\;\;2\rangle$, $\langle2\;\;3\;\;4\;\;1\rangle$, and
$\langle4\;\;2\;\;3\;\;1\rangle,\langle4\;\;1\;\;2\;\;3\rangle$. Let $g $
denotes the product $a_{\pi_{i}}a_{\pi_{i+1}}$. Then, as $a_{\pi_{i}}$ and
$a_{\pi_{i+1}}$ run over all the elements of $G$, their product $g$ also runs
over all the elements of $G$, becoming equal to each element of $G$ exactly
$|G|$ times. By Theorem \ref{threecommute}, the equation $a_{1}a_{2}a_{3}
a_{4}=a_{\pi_{1}}a_{\pi_{2}}a_{\pi_{3}}a_{\pi_{4}}$, in which we change
$a_{\pi_{i}}a_{\pi_{i+1}}$, on both sides, to $g$, has exactly $|G|^{2}\cdot
c(G)$ solutions. But these solutions naturally correspond to $|G|$ different
solutions of the equation $a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}}
a_{\pi_{3}}a_{\pi_{4}}$. Thus $L_{\pi}(G)=|G|^{3}\cdot c(G)$ and ${\Pr}_{\pi
}(G)=\frac{c(G)}{|G|}$.
\end{proof}

Lemmas \ref{Case.4.1} and \ref{Case.4.2} establish that for fifteen different
permutations $\pi$ in $S_{4}$, their probabilities equal ${\Pr}_{\pi}
(G)=\frac{c(G)}{|G|}$. Notice that these fifteen permutations have exactly
three alternating cycles in their cycle graphs $\Gr(\pi)$ (see
Bafna and Pevzner \cite{BP}; Doignon and Labarre \cite{DL}). For the identity permutation, which
has five alternating cycles in its cycle graph, the probability of the
corresponding trivial permutation equation is $1$.

The remaining eight permutations in $S_{4}$ have one alternating cycle in
their cycle graphs. We will now show that for these eight permutations, the
corresponding permutations have the same probability, which, in a generic
group, is different both from $1$ and from $\frac{c(G)}{|G|}$.

\begin{theorem}
\label{mainfour} For any finite group $G$ we have
\begin{align*}
{\Pr}^{4}(G) & =\Pr(a_{1}a_{2}a_{3}a_{4}=a_{4}a_{3}a_{2}a_{1})=\Pr(a_{1}
a_{2}a_{3}a_{4}=a_{2}a_{1}a_{4}a_{3})\\
& =\frac{\sum\limits_{x,y\in G}|{\Stab}_{2}(x,y)|}{\left\vert G\right\vert
^{4}}=\frac{1}{|G|^{2}}\cdot\sum\limits_{i,k,j=1}^{c(G)}\frac{\left\vert
\Omega_{j}\right\vert \cdot c_{i,k;j}^{2}(G)}{\left\vert \Omega_{i}\right\vert
\cdot\left\vert \Omega_{k}\right\vert }\\
& =\frac{1}{|G|^{2}}\cdot\sum\limits_{i,k,j=1}^{c(G)}\frac{\left\vert
\Omega_{j}\right\vert \cdot c_{i,k;j}(G)\cdot c_{k,i;j}(G)}{\left\vert
\Omega_{i}\right\vert \cdot\left\vert \Omega_{k}\right\vert }.
\end{align*}

\end{theorem}

\begin{proof}
Notice that for any $x,y\in G$, the set ${\Stab}_{2}(x,y)$ of all ordered
pairs $(g,h)$ of elements of $G$, such that $xy=g^{-1}xgh^{-1}yh$, has an
alternative description as the set of all the ordered pairs $(g\in G,f^{-1}\in
G)$, such that $gxyf=xgfy$. Indeed, by setting $f=h^{-1}$, the equation
$xy=g^{-1}xgh^{-1}yh$ becomes $xy=g^{-1}xgfyf^{-1}$. Multiplying the right by
$g$ and the left by $f$ gives us $gxyf=xgfy$.

Thus, for each fixed ordered pair $(x,y)$ of elements in $G$, there are
exactly \newline$|{\Stab}_{2}(x,y)|$ different equations $gxyf=xgfy$ with
$g,h\in G$. As $x$ and $y$ run over all the elements of $G$, we obtain that
the total number of different equations $gxyf=xgfy$ in $G$ is $\sum
\limits_{x,y\in G}|{\Stab}_{2}(x,y)|$.

Dividing the total number of different equations $gxyf=xgfy$ in $G$ by
$|G|^{4}$ gives us
\[
\Pr(a_{1}a_{2}a_{3}a_{4}=a_{2}a_{1}a_{4}a_{3})=\frac{\sum\limits_{x,y\in
G}|{\Stab}_{2}(x,y)|}{\left\vert G\right\vert ^{4}}.
\]


Next, consider the equation $a_{1}a_{2}a_{3}a_{4}=a_{4}a_{3}a_{2}a_{1}$. Let
$x$ denotes the product $a_{1}a_{2}$, $x^{\prime}$ denotes the product
$a_{2}a_{1}$, $y$ denotes the product $a_{3}a_{4}$, and $y^{\prime}$ denotes
the product $a_{4}a_{3}$. The equation $a_{1}a_{2}a_{3}a_{4}=a_{4}a_{3}
a_{2}a_{1}$ becomes $xy=y^{\prime}x^{\prime}$. By Lemma \ref{commute-conjug},
we have $x\sim x^{\prime}$ and $y\sim y^{\prime}$.

Now consider any $x,x^{\prime},y,y^{\prime}\in G$, such that $x\sim x\prime$,
$y\sim y^{\prime}$, and $xy=y^{\prime}x^{\prime}$. By Lemma
\ref{conjug-decomp}, there are $\frac{|G|}{|\Omega(x)|}=|C_{G}(x)|$ different
ways of breaking $x$ into a product $a_{1}a_{2}$ in such a way that
$x^{\prime}=a_{2}a_{1}$. Again, by Lemma \ref{conjug-decomp}, there are
$\frac{|G|}{|\Omega(y)|}=|C_{G}(y)|$ different ways of breaking $y$ into a
product $a_{3}a_{4}$ in such a way that $y^{\prime}=a_{4}a_{3}$. Thus, to each
fixed equation $xy=y^{\prime}x^{\prime}$ correspond $\left\vert C_{G}
(x)\right\vert \cdot\left\vert C_{G}(y)\right\vert $ different equations
$a_{1}a_{2}a_{3}a_{4}=a_{4}a_{3}a_{2}a_{1}$.

Next, for each fixed $x,y\in G$, we count the number of different equations
\newline$xy=y^{\prime}x^{\prime}$, where $x\sim x\prime$ and $y\sim y^{\prime
}$. Define $x^{\prime\prime}=(y^{-1}xy)$. Thus, we get an equation
$xy=y(y^{-1}xy)=yx^{\prime\prime}$. Now, for each equation $xy=y^{\prime
}x^{\prime}$, as above, there exist some $g,h\in G$ such that $y^{\prime
}=g^{-1}yg$ and $x^{\prime}=h^{-1}x^{\prime\prime}h$. But, for each fixed
$x,y\in G$ we have $|{\Stab}_{2}(y,x^{\prime\prime})|$ different elements
$g,h\in G$, such that $xy=yx^{\prime\prime}=g^{-1}ygh^{-1}x^{\prime\prime}h$.
For each fixed pair $g,h\in G$, such that $yx^{\prime\prime}=g^{-1}
ygh^{-1}x^{\prime\prime}h$, a pair $g^{\prime},h^{\prime}\in G$ satisfies
$(g^{\prime})^{-1}yg^{\prime}=g^{-1}yg$ and $(h^{\prime})^{-1}x^{\prime\prime
}h^{\prime}=h^{-1}x^{\prime\prime}h$, if, and only if, $g^{\prime}g^{-1}\in
C_{G}(y)$ and \newline$h^{\prime}h^{-1}\in C_{G}(x^{\prime\prime})$. Thus, for
each fixed $x,y\in G $, there are exactly
\[
\frac{|{\Stab}_{2}(y,x^{\prime\prime})|}{\left\vert C_{G}(y)\right\vert
\cdot\left\vert C_{G}(x^{\prime\prime})\right\vert }
\]
different equations $xy=y^{\prime}x^{\prime}$, in which $x^{\prime}\sim x$ and
$y^{\prime}\sim y$. But, $\left\vert C_{G}(x^{\prime\prime})\right\vert
=|C_{G}(x)|$. Thus, for each fixed ordered pair $(x,y)$ of elements of $G$, we
have
\[
\frac{|{\Stab}_{2}(y,(y^{-1}xy))|}{\left\vert C_{G}(y)\right\vert
\cdot\left\vert C_{G}(x)\right\vert }
\]
different equations $xy=y^{\prime}x^{\prime}$. As we showed above, to each of
these equations correspond $\left\vert C_{G}(x)\right\vert \cdot\left\vert
C_{G}(y)\right\vert $ different equations $a_{1}a_{2}a_{3}a_{4}=a_{4}
a_{3}a_{2}a_{1}$, in which $a_{1}a_{2}=x$, $a_{3}a_{4}=y$, $a_{2}
a_{1}=x^{\prime}$, and $a_{4}a_{3}=y^{\prime}$. Thus, to each ordered pair
$(x,y)$ of elements of $G$ correspond $|{\Stab}_{2}(y,(y^{-1}xy))|$ different
equations $a_{1}a_{2}a_{3}a_{4}=a_{4}a_{3}a_{2}a_{1}$, in which $a_{1}a_{2}=x$
and $a_{3}a_{4}=y$.

Thus, to find $\Pr(a_{1}a_{2}a_{3}a_{4}=a_{4}a_{3}a_{2}a_{1})$ we need to sum
$|{\Stab}_{2}(y,(y^{-1}xy))|$ over all $x,y\in G$, and then divide that sum by
$|G|^{4}$. For each fixed $y$, the product $v=y^{-1}xy$ runs over all the
elements of $G$ when $x$ runs over all the elements of $G$. Thus, summing
$|{\Stab}{2}(y,(y^{-1}xy))|$ over all $x,y\in G$ is the same as summing
$|{\Stab}_{2}(y,v)|$ over all $y,v\in G$. Thus, we obtain
\[
L_{\langle4\;\;3\;\;2\;\;1\rangle}(G)=\sum\limits_{y,v\in G}|{\Stab}
_{2}(x,y)|,
\]
and
\begin{align*}
{\Pr}^{4}(G) & =\Pr(a_{1}a_{2}a_{3}a_{4}=a_{4}a_{3}a_{2}a_{1})\\
& =\frac{\sum\limits_{x,y\in G}|{\Stab}_{2}(x,y)|}{|G|^{4}}=\Pr(a_{1}
a_{2}a_{3}a_{4}=a_{2}a_{1}a_{4}a_{3}).
\end{align*}


Now, fix an element $z$ in some equivalence class $\Omega_{j}$ in $G$. For
each equation $xy=z=x^{\prime}y^{\prime}$ we have exactly
\[
\left\vert C_{G}(x)\right\vert \cdot\left\vert C_{G}(y)\right\vert
=\frac{|G|^{2}}{\left\vert \Omega(x)\right\vert \cdot\left\vert \Omega
(y)\right\vert }
\]
different equations
\[
(a_{1}a_{2})(a_{3}a_{4})=xy=z=x^{\prime}y^{\prime}=(a_{2}a_{1})(a_{4}a_{3}).
\]
Indeed, there are $|C_{G}(x)|$ different ways to break $x$ into a product
$a_{1}a_{2}$ so that $a_{2}a_{1}=x^{\prime}$, and there are $|C_{G}(y)|$
different ways to break $y$ into a product $a_{3}a_{4}$ so that $a_{4}
a_{3}=y^{\prime}$.

Now, there are $c_{i,k;j}(G)$ different ways to break $z$ as a product $xy$ so
that $x\in\Omega_{i}$ and $y\in\Omega_{k}$. For each of these $c_{i,k;j}(G)$
different ways, there are $c_{i,k;j}(G)$ different ways to break $z$ as a
product $x^{\prime}y^{\prime}$. Thus, for each ordered pair $(\Omega
_{i},\Omega_{k})$ of conjugacy classes in $G$, there are $c_{i,k;j}^{2}(G)$
different equations $xy=z=x^{\prime}y^{\prime}$ with $x,x^{\prime}\in
\Omega_{i}$ and $y,y^{\prime}\in\Omega_{k}$. The number of different equations
$xy=z=x^{\prime}y^{\prime}$ with $x,x^{\prime}\in\Omega_{i}$ and $y,y^{\prime
}\in\Omega_{k}$ is the same for all $z\in\Omega_{j}$.

Taking the sum of the number of different equations $a_{1}a_{2}a_{3}
a_{4}=z=a_{2}a_{1}a_{4}a_{3}$, as $z$ runs over all the elements of $G$, and
dividing it by $|G|^{4}$, gives us
\[
\Pr(a_{1}a_{2}a_{3}a_{4}=a_{2}a_{1}a_{4}a_{3})=\frac{1}{|G|^{2}}\cdot
\sum\limits_{i,k,j=1}^{c(G)}\frac{\left\vert \Omega_{j}\right\vert \cdot
c_{i,k;j}^{2}(G)}{\left\vert \Omega_{i}\right\vert \cdot\left\vert \Omega
_{k}\right\vert }.
\]


Finally, fix an element $z$ in some equivalence class $\Omega_{j}$ in $G$. For
each equation $xy=z=y^{\prime}x^{\prime}$ we have exactly
\[
\left\vert C_{G}(x)\right\vert \cdot\left\vert C_{G}(y)\right\vert
=\frac{|G|^{2}}{\left\vert \Omega(x)\right\vert \cdot\left\vert \Omega
(y)\right\vert }
\]
different equations
\[
(a_{1}a_{2})(a_{3}a_{4})=xy=z=y^{\prime}x^{\prime}=(a_{4}a_{3})(a_{2}a_{1}).
\]


Now, there are $c_{i,k;j}(G)$ different ways to break $z$ as a product $xy$ so
that $x\in\Omega_{i}$ and $y\in\Omega_{k}$. For each of these $c_{k,i;j}(G)$
different ways, there are $c_{i,k;j}(G)$ different ways to break $z$ as a
product $x^{\prime}y^{\prime}$. Thus, for each ordered pair $(\Omega
_{i},\Omega_{k})$ of conjugacy classes in $G$, there are there are
$c_{i,k;j}(G)\cdot c_{k,i;j}(G)$ different equations $xy=z=y^{\prime}
x^{\prime}$ with $x,x^{\prime}\in\Omega_{i}$ and $y,y^{\prime}\in\Omega_{k}$.

Taking the sum of the number of different equations $a_{1}a_{2}a_{3}
a_{4}=z=a_{4}a_{3}a_{2}a_{1}$, as $z$ runs over all the elements of $G$, and
dividing it by $|G|^{4}$, gives us
\[
\Pr(a_{1}a_{2}a_{3}a_{4}=a_{4}a_{3}a_{2}a_{1})=\frac{1}{|G|^{2}}\cdot
\sum\limits_{i,k,j=1}^{c(G)}\frac{\left\vert \Omega_{j}\right\vert \cdot
c_{i,k;j}(G)\cdot c_{k,i;j}(G)}{\left\vert \Omega_{i}\right\vert
\cdot\left\vert \Omega_{k}\right\vert }.
\]

\end{proof}

To study the other four permutations in $S_{4}$, we first prove a lemma that
is a particular case of Theorem \ref{exchange.operation.keeps.prob}.

\begin{lemma}
\label{small.exchange} Let $\pi\in S_{4}$ be a permutation such that $\pi
_{4}+1=\pi_{3}=2$ or $\pi_{4}+1=\pi_{3}=3$. Then the equations
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}}a_{\pi_{3}}a_{\pi_{4}},
\]
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{3}}a_{\pi_{4}}a_{\pi_{2}}
\]
have the same number of solutions.
\end{lemma}

\begin{proof}
First, consider the case $\pi_{4}+1=\pi_{3}=2$.

Rewrite the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}}a_{2}a_{1}
\]
as
\[
a_{1}a_{\pi_{2}}^{-1}a_{\pi_{2}}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}}
a_{2}a_{1}.
\]
Let $a$ denotes $a_{\pi_{2}}a_{2}$. Then the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}}a_{2}a_{1}
\]
becomes
\begin{equation}
\label{small.ex.1}a_{1}a_{\pi_{2}}^{-1}aa_{3}a_{4}=a_{\pi_{1}}aa_{1},
\end{equation}
in which the variable $a_{\pi_{2}}^{-1}$ runs over all the elements of $G$,
and for each fixed value of $a_{\pi_{2}}^{-1}$, the variable $a$ runs over all
the elements of $G$.

Rewrite the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{2}a_{1}a_{\pi_{2}}
\]
as
\[
a_{1}a_{\pi_{2}}a_{\pi_{2}}^{-1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{2}a_{1}
a_{\pi_{2}}.
\]
Let $a$ denotes $a_{1}a_{\pi_{2}}$. Then the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{2}a_{1}a_{\pi_{2}}
\]
becomes
\begin{equation}
\label{small.ex.2}aa_{\pi_{2}}^{-1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{2}a,
\end{equation}
in which the variable $a_{\pi_{2}}^{-1}$ runs over all the elements of $G$,
and for each fixed value of $a_{\pi_{2}}^{-1}$, the variable $a$ runs over all
the elements of $G$.

Now, Equation \ref{small.ex.1} is obtained from Equation \ref{small.ex.2} by
renaming $a$ to $a_{1}$ and renaming $a_{2}$ to $a$. Thus, they have the same
number of solutions.

Finally, consider the case $\pi_{4}+1=\pi_{3}=3$.

Rewrite the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}}a_{3}a_{2}
\]
as
\[
a_{1}a_{2}a_{\pi_{2}}^{-1}a_{\pi_{2}}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}}
a_{3}a_{2}.
\]
Let $a$ denotes $a_{\pi_{2}}a_{3}$. Then the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}}a_{3}a_{2}
\]
becomes
\begin{equation}
\label{small.ex.3}a_{1}a_{2}a_{\pi_{2}}^{-1}aa_{4}=a_{\pi_{1}}aa_{2},
\end{equation}
in which the variable $a_{\pi_{2}}^{-1}$ runs over all the elements of $G$,
and for each fixed value of $a_{\pi_{2}}^{-1}$, the variable $a$ runs over all
the elements of $G$.

Rewrite the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{3}a_{2}a_{\pi_{2}}
\]
as
\[
a_{1}a_{2}a_{\pi_{2}}a_{\pi_{2}}^{-1}a_{3}a_{4}=a_{\pi_{1}}a_{3}a_{2}
a_{\pi_{2}}.
\]
Let $a$ denotes $a_{2}a_{\pi_{2}}$. Then the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{3}a_{2}a_{\pi_{2}}
\]
becomes
\begin{equation}
\label{small.ex.4}a_{1}aa_{\pi_{2}}^{-1}a_{3}a_{4}=a_{\pi_{1}}a_{3}a,
\end{equation}
in which the variable $a_{\pi_{2}}^{-1}$ runs over all the elements of $G$,
and for each fixed value of $a_{\pi_{2}}^{-1}$, the variable $a$ runs over all
the elements of $G$.

Now, Equation \ref{small.ex.3} is obtained from Equation \ref{small.ex.4} by
renaming $a$ into $a_{2}$ and renaming $a_{3}$ into $a$. Thus, they have the
same number of solutions.
\end{proof}

The following corollary of Lemma \ref{small.exchange} provides examples of the
$x--y$ exchange operation, which will be introduced in Definition
\ref{def.exchange}. It also illustrates the notion of the $x--y$ exchange
orbit, which will be introduced in Definition \ref{exchange.orbit.def}, and
demonstrates how the $3-cycle$ of Proposition \ref{exchange-product} works.

\begin{corollary}
\label{mainfour.2} The equations
\[
a_{1}a_{2}a_{3}a_{4}=a_{4}a_{3}a_{2}a_{1},
\]
\[
a_{1}a_{2}a_{3}a_{4}=a_{4}a_{2}a_{1}a_{3},
\]
\[
a_{1}a_{2}a_{3}a_{4}=a_{4}a_{1}a_{3}a_{2}
\]
have the same number of solutions.
\end{corollary}

\begin{proof}
For permutation $\pi=\langle4\;\;3\;\;2\;\;1\rangle$ we have $\pi_{4}
+1=\pi_{3}=2$. Thus, by Lemma \ref{small.exchange}, the permutation equation
of the permutation $\langle4\;\;2\;\;1\;\;3\rangle$ has the same number of
solutions as the permutation equation of $\pi$.

For permutation $\theta=\langle4\;\;1\;\;3\;\;2\rangle$ we have $\pi_{4}
+1=\pi_{3}=3$. Thus, by Lemma \ref{small.exchange}, the permutation equation
of the permutation $\langle4\;\;3\;\;2\;\;1\rangle$ has the same number of
solutions as the permutation equation of $\theta$.
\end{proof}

The following corollary is based on Lemma \ref{inverse.general}, since
$\langle4\;\;2\;\;1\;\;3\rangle^{-1}=\langle3\;\;2\;\;1\;\;4\rangle$ and
$\langle4\;\;1\;\;3\;\;2\rangle^{-1}=\langle2\;\;4\;\;3\;\;1\rangle$.

\begin{corollary}
\label{mainfour.3} \textrm{(i)} The equations
\[
a_{1}a_{2}a_{3}a_{4}=a_{4}a_{2}a_{1}a_{3},
\]
\[
a_{1}a_{2}a_{3}a_{4}=a_{3}a_{2}a_{1}a_{4}
\]
have the same number of solutions.

\textrm{(ii)} The equations
\[
a_{1}a_{2}a_{3}a_{4}=a_{4}a_{1}a_{3}a_{2},
\]
\[
a_{1}a_{2}a_{3}a_{4}=a_{2}a_{4}a_{3}a_{1}
\]
have the same number of solutions.
\end{corollary}

To study the remaining two permutation in $S_{4}$, we first prove the following.

\begin{lemma}
\label{small.cyclic} Let $\pi\in S_{4}$ be a permutation such that for some
$i\in\{1,2\}$, $\pi_{i}+1=\pi_{i+2}$ and $\pi_{i+1}=\pi_{i}-2$. Let
$j\in\{1,2,3,4\}$ be such an integer that $pi_{j}=\pi_{i}-1$. Let $\theta\in
S_{4}$ be obtained from $\pi$ by interchanging $\pi_{i}$ and $\pi_{j}$. Then
the equations
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}}a_{\pi_{3}}a_{\pi_{4}},
\]
\[
a_{1}a_{2}a_{3}a_{4}=a_{\theta_{1}}a_{\theta_{2}}a_{\theta_{3}}a_{\theta_{4}}
\]
have the same number of solutions.
\end{lemma}

\begin{proof}
First, for permutations in $S_{4}$, the only option for the integer $j$ is a
unique element in $\{1,2,3,4\}$, which is different from all three integers
$i,i+1,i+2$. Similarly, the only option for the value $p_{i}$, for $\pi\in
S_{4}$, is $3$, and for the value $p_{j}$ is $2$.

For simplicity of dealing with the indices, we will consider the cases $j=1,
i=2$, and $j=4,i=1$ separately. Even though the permutation $\pi\in S_{4}$ is
uniquely determined in each of these two cases, we will use the notation
$\pi_{i}=x$, $\pi_{i+1}=y$, $\pi_{i+2}=x+1$, and $\pi_{j}=y+1$. This is done
to illustrate both the $x--y$ cyclic operation, which will be introduced in
Definition \ref{cyclic-cdot}, and the proof of the Theorem
\ref{cyclic.operation.keeps.prob}. Additionally, this proof, in which the
$x,y,x+1,y+1$ notation is used, can be adopted for a more general case of
substrings in a longer string, which is the case for certain permutations in
$S_{n}$ with $n>4$. An example of a substring of that type in a longer string,
for which this proof works, will be provided at the end of the proof.

First, let $j=4,i=1$. Then the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}}a_{\pi_{3}}a_{\pi_{4}}
\]
can be written as
\begin{equation}
a_{y}a_{y+1}a_{x}a_{x+1}=a_{x}a_{y}a_{x+1}a_{y+1}\label{small.cyclic.1}
\end{equation}
Similarly, the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\theta_{1}}a_{\theta_{2}}a_{\theta_{3}}a_{\theta_{4}}
\]
can be written as
\begin{equation}
a_{y}a_{y+1}a_{x}a_{x+1}=a_{y+1}a_{y}a_{x+1}a_{x}\label{small.cyclic.2}
\end{equation}
Now, define $c=a_{x}a_{x+1}$ and $d=a_{y}a_{x}^{-1}$, and insert them into
Equation \ref{small.cyclic.1} as follows
\begin{equation}
da_{x}a_{y+1}c=a_{x}dca_{y+1}\label{small.cyclic.1.1}
\end{equation}
Notice that as random variables $a_{y},a_{x},a_{x+1}$ run over all the
elements of $G$, so do random variables $a_{x},c,d$. Similarly, as random
variables $a_{x},c,d$ run over all the elements of $G$, so do random variables
$a_{y},a_{x},a_{x+1}$. Thus, there is a one-to-one correspondence between the
solutions of Equation \ref{small.cyclic.1} and the solutions of Equation
\ref{small.cyclic.1.1}. But Equation \ref{small.cyclic.1.1} is obtained from
Equation \ref{small.cyclic.2} by renaming $a_{y}$ to $d$ and $a_{x+1}$ to $c$.
Thus, Equation \ref{small.cyclic.1.1} and Equation \ref{small.cyclic.2}, after
renaming the variables, have the same solutions.

Second, let $j=1,i=2$. Then the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\pi_{1}}a_{\pi_{2}}a_{\pi_{3}}a_{\pi_{4}}
\]
can be written as
\begin{equation}
a_{y}a_{y+1}a_{x}a_{x+1}=a_{y+1}a_{x}a_{y}a_{x+1}\label{small.cyclic.3}
\end{equation}
Similarly, the equation
\[
a_{1}a_{2}a_{3}a_{4}=a_{\theta_{1}}a_{\theta_{2}}a_{\theta_{3}}a_{\theta_{4}}
\]
can be written as
\begin{equation}
a_{y}a_{y+1}a_{x}a_{x+1}=a_{x}a_{y+1}a_{y}a_{x+1}\label{small.cyclic.4}
\end{equation}
Now, define $c=a_{x}a_{x+1}$ and $d=a_{y}a_{x}^{-1}$, and insert them into
Equation \ref{small.cyclic.3} as follows
\begin{equation}
da_{x}a_{y+1}c=a_{x}a_{y+1}dc\label{small.cyclic.3.1}
\end{equation}
Again, there is a one-to-one correspondence between the solutions of Equation
\ref{small.cyclic.3} and the solutions of Equation \ref{small.cyclic.3.1}, but
Equation \ref{small.cyclic.3.1} is obtained from Equation \ref{small.cyclic.4}
by renaming $a_{y}$ to $d$ and $a_{x+1}$ to $c$. Thus, Equation
\ref{small.cyclic.3.1} and Equation \ref{small.cyclic.4}, after renaming the
variables, have the same solutions.

Obviously, for our purpose in this section, the case $j=1, i=2$ is of no
interest, since multiplication of Equation \ref{small.cyclic.3} by
$a_{x+1}^{-1}$ on the right reduces it to a permutational equation for a
permutation in $S_{3}$. However, it illustrates how the $x--y$ cyclic
operation works, when $a_{y}a_{y+1}a_{x}a_{x+1}$ and $a_{y+1}a_{x}a_{y}
a_{x+1}$ are just substrings in a longer string, which is the case for certain
permutations in $S_{n}$ with $n>4$. For example, the proof we provided here
adapts to show that the equations $a_{1}(a_{2}a_{3}a_{4}a_{5})a_{6}
=a_{6}(a_{3}a_{4}a_{2}a_{5})a_{1}$ and $a_{1}(a_{2}a_{3}a_{4}a_{5})a_{6}
=a_{6}(a_{4}a_{3}a_{2}a_{5})a_{1}$ have the same number of solutions.
\end{proof}

\begin{corollary}
\label{mainfour.4} \textrm{(i)} The equations
\[
a_{1}a_{2}a_{3}a_{4}=a_{2}a_{1}a_{4}a_{3},
\]
\[
a_{1}a_{2}a_{3}a_{4}=a_{3}a_{1}a_{4}a_{2}
\]
have the same number of solutions.

\textrm{(ii)} The equations
\[
a_{1}a_{2}a_{3}a_{4}=a_{2}a_{1}a_{4}a_{3},
\]
\[
a_{1}a_{2}a_{3}a_{4}=a_{2}a_{4}a_{1}a_{3}
\]
have the same number of solutions.
\end{corollary}

\begin{proof}
The case of $j=4,i=1$ in Lemma \ref{small.cyclic} corresponds to
$y=1,y+1=2,\newline x=3,x+1=4$. Thus, the equations of the permutations
$\pi=\langle3\;\;1\;\;4\;\;2\rangle$ and $\theta=\langle
2\;\;1\;\;4\;\;3\rangle$ have the same number of solutions. Specifically,
Equation \ref{small.cyclic.1} is
\[
a_{1}a_{2}a_{3}a_{4}=a_{3}a_{1}a_{4}a_{2}
\]
and Equation \ref{small.cyclic.2} is
\[
a_{1}a_{2}a_{3}a_{4}=a_{2}a_{1}a_{4}a_{3}.
\]
By Lemma \ref{small.cyclic}, they have the same number of solutions.

Since $\langle2\;\;4\;\;1\;\;3\rangle=\langle3\;\;1\;\;4\;\;2\rangle^{-1}$,
the equations
\[
a_{1}a_{2}a_{3}a_{4}=a_{3}a_{1}a_{4}a_{2},
\]
\[
a_{1}a_{2}a_{3}a_{4}=a_{2}a_{4}a_{1}a_{3}
\]
have, by Lemma \ref{inverse.general}, the same number of solutions.
\end{proof}

Thus, we obtain the following.

\begin{theorem}
\label{mainfour.last} The permutations
\[
\langle4\;\;3\;\;2\;\;1\rangle,\langle2\;\;1\;\;4\;\;3\rangle,\langle
4\;\;2\;\;1\;\;3\rangle,\langle4\;\;1\;\;3\;\;2\rangle,\langle
3\;\;2\;\;1\;\;4\rangle,\langle2\;\;4\;\;3\;\;1\rangle,
\]
\[
\langle3\;\;1\;\;4\;\;2\rangle,\langle2\;\;4\;\;1\;\;3\rangle
\]
in $S_{4}$ have the same probabilities.
\end{theorem}

\begin{proof}
This theorem follows from Theorem \ref{mainfour} and Corollaries
\ref{mainfour.2}, \ref{mainfour.3}, and \ref{mainfour.4}.
\end{proof}

In Theorem \ref{generic.group} we will show that every finite non-Abelian
group is generic. Thus,
\begin{equation}
\Pr(a_{1}a_{2}a_{3}a_{4}=a_{2}a_{1}a_{3}a_{4})\neq\Pr(a_{1}a_{2}a_{3}
a_{4}=a_{4}a_{3}a_{2}a_{1})\label{spect.1}
\end{equation}
for every finite non-Abelian group $G$. Since both probabilities, appearing in
Equation \ref{spect.1}, cannot be equal to $1$ in a non-Abelian group, it will
Imply that the spectrum of probabilities, for permutations in $S_{4}$,
consists of three different values. But now, in the Example \ref{d4q8.four},
we explicitly compute $\Pr(a_{1}a_{2}a_{3}a_{4}=a_{2}a_{1}a_{3}a_{4})={\Pr
}^{2}(G)$ and $\Pr(a_{1}a_{2}a_{3}a_{4}=a_{2}a_{1}a_{4}a_{3})={\Pr}^{4}(G)$
for the groups $G=D_{8}$ and $G=Q_{8}$. These probabilities, for both
$G=D_{8}$ and $G=Q_{8}$, are different. This permits us to avoid using Theorem
\ref{generic.group} in establishing Lemma \ref{SPEC4}. In Example
\ref{d4q8.general} we will perform the same calculations for the general case
of ${\Pr}^{2n}(G)$. Results, similar to our calculations of ${\Pr}^{2}(G)$ and
${\Pr}^{4}(G)$ for $G=D_{8}$ and $G=Q_{8}$, but in a much more general form
and for a larger variety of groups, were obtained in \cite{DasNath1,
NathDash1}.

\begin{example}
\label{d4q8.four} Both $G=D_{8}$ and $G=Q_{8}$ have five conjugacy classes.
\newline Thus, ${\Pr}^{2}(G)=\frac{5}{8}$ for both of these groups. For both
$D_{8}$ and $Q_{8}$, the center consists of the identity $1$ and another
element $c$, such that $c^{2}=1$. For both of these groups, the factor of the
group by its center is the Abelian group $K_{4}=Z_{2}\times Z_{2}$. This means
that if for some $x,y\in G$, $xy\neq yx$, then $xy=cyx$. Hence, the equation
$a_{1}a_{2}a_{3}a_{4}=a_{2}a_{1}a_{4}a_{3}$ is satisfied either if $a_{1}
a_{2}=a_{2}a_{1}$ and $a_{3}a_{4}=a_{4}a_{3}$, or if $a_{1}a_{2}=ca_{2}a_{1}$
and $a_{3}a_{4}=ca_{4}a_{3}$. The first option has the probability $\frac
{5}{8}\cdot\frac{5}{8}=\frac{25}{64}$. The second option has the probability
$\frac{3}{8}\cdot\frac{3}{8}=\frac{9}{64}$. Thus, ${\Pr}^{4}(G)=\frac{25}
{64}+\frac{9}{64}=\frac{17}{32}$. Notice that ${\Pr}^{4}(G)<{\Pr}^{2}(G)$.
\end{example}

Now we may conclude with the following.

\begin{theorem}
\label{SPEC4} For a generic finite non-Abelian group $G$, the spectrum of
permutation probabilities over $S_{4}$ consists of only three probabilities
\[
{\Spec}_{4}(G)=\{1,{\Pr}^{2}(G)=\frac{|c(G)|}{|G|},{\Pr}^{4}(G)\}
\]

\end{theorem}

Notice that the calculations for $G=D_{8}$ and $G=Q_{8}$ show that the three
probabilities belonging to ${\Spec}_{4}(G)$ are pairwise different for these
two groups.

 From the results of this section it is evident that permutational equalities
of any two permutations from $S_{2}$, $S_{3}$, or $S_{4}$ have the same
probability if they have the same number of alternating cycles in their cycle
graphs. Consequently, the number of different permutations, corresponding to
each probability in ${\Spec}_{2}(G)$, ${\Spec}_{3}(G)$, or ${\Spec}_{4}(G)$,
is precisely the Hultman number $S_{H}(n,k)$, where $n=2,3,4 $ and $k$ is the
number of alternating cycles in the cycle graphs of these permutations. In the
following sections we extend the observations and calculations of this section
to $S_{n}$.

\section{Probabilities of permutation equations, number of alternating cycles,
and Hultman decomposition}

For the information on cycle graphs, decomposition to alternating cycles, and
Hultman numbers, as well as many other related definitions and notions, we
refer to Doignon and Labarre \cite{DL} and the On-Line Encyclopedia of Integer
Sequences \cite{Sloan}. Here we briefly review these notions.

\begin{definition}
\label{def.cycle.graph} The cycle graph $\Gr(\phi)$ of a permutation $\phi\in
S_{n}$ is the bi-colored directed graph with $n+1$ vertices $\phi_{0}
=0,\phi_{1},\ldots,\phi_{n}$, whose edge set consists of

\begin{itemize}
\item black edges $\phi_{n}\rightarrow\phi_{n-1}$, $\phi_{n-1}\rightarrow
\phi_{n-2}$, $\ldots$, $\phi_{1}\rightarrow\phi_{0}$, $\phi_{0}\rightarrow
\phi_{n}$, and

\item grey edges $0\dashrightarrow1$, $1\dashrightarrow2$, $\ldots$,
$(n-1)\dashrightarrow n$, $n\dashrightarrow0$.
\end{itemize}

The set of black and grey edges is decomposed in a unique way into
edge-disjoint alternating cycles in which the black and the grey edges
alternate. It is called the decomposition of $\Gr(\phi)$ into alternating cycles.
\end{definition}

\begin{definition}
\label{def.hult.num} The Hultman number $S_{H}(n,k)$ is a nonnegative integer
that counts the number of permutations in $S_{n}$, whose cycle graph
decomposes into $k$ alternating cycles.
\end{definition}

Let $S(1+n)$ denotes the group of all permutations of the set $\{0,1,2,\ldots
,n\}$.

\begin{definition}
Let $\phi^{\bullet}$ denotes the $n+1$-cycle in a permutation $\phi\in S_{n}
$.
\[
\phi_{n}\rightarrow\phi_{n-1}\rightarrow\phi_{n-2}\rightarrow\cdots
\rightarrow\phi_{1}\rightarrow\phi_{0}\rightarrow\phi_{n}
\]
in $S(1+n)$, which is the $n+1$-cycle, composed of the black arrows of
$\Gr(\phi)$.
\end{definition}

We will use the cyclic notation $(\phi_{0},\phi_{n},\phi_{n-1},\ldots,\phi
_{2},\phi_{1})$ for $\phi^{\bullet}$. Notice that there is a trivial
one-to-one correspondence between all the permutations of $S_{n}$ and all the
$n+1$-cycles in $S(1+n)$. Namely, the entries of a $n+1$-cycle, starting from
the one after $0$, are interpreted as the entries of the permutation, but read
backwards, written in the shortened way of the two-row notation. Thus, for any
$n+1$-cycle $C$ in $S(1+n)$, we can easily obtain the unique permutation
$\phi\in S_{n}$, for which the $n+1$-cycle $C$ is its black cycle
$\phi^{\bullet}$.

\begin{definition}
For a permutation $\phi\in S_{n}$ we define the corresponding permutation
$\phi^{\circ}\in S(1+n)$ to be $\phi^{\bullet}\cdot(0,1,\ldots,n)$.
\end{definition}

Notice that $\phi^{\circ}$ cannot contain $m\mapsto(m+1)$ for any
$m=0,1,\ldots,n$, since $m\mapsto(m+1)$ is $i\dashrightarrow(i+1)\rightarrow
(i+1)$, but an $(n+1)$-cycle $\phi^{\bullet}$ cannot contain $(i+1)\rightarrow
(i+1)$.

\begin{theorem}
[Doignon and Labarre's theorem 8]\label{Theorem.8} There is a natural
one-to-one correspondence between the cycles in the cycle decomposition of the
permutation $\phi^{\circ}$ and the alternating cycles in $\Gr(\phi)$.
\end{theorem}

Therefore, there is a unique way to decompose a permutation into alternating cycles.

\begin{definition}
We define $H(S_{n})$ as a partition of $S_{n}$ into pairwise disjoint sets
containing permutations with the same number of alternating cycles in their
cycle graph.
\end{definition}

Now we are going to introduce two operations, $x--y$ exchange operation in
Definition \ref{def.exchange} and $x--y$ cyclic operation in Definition
\ref{cyclic-cdot}, which transform permutations in $S_{n}$. Next, we show that
these two operations do not change the number of alternative cycles in the
cycle graph of a permutation. After that, we demonstrate that these two
operations do not change the probabilities of the permutation equations.
Finally, we prove that any two permutations that have the same number of
alternating cycles in their cycles graphs, can be connected to each-other by
performing a finite number of these operations. This establishes that any two
permutations with the same number of alternating cycles in their cycle graphs,
have the same probabilities of their permutation equalities.

\subsection{Exchange operation}

Let $\phi\in S_{n}$ be a permutation. We augment $\phi$ by defining $\phi
_{0}=0$.

\begin{definition}
\label{def.exchange} Let $0\leq x=\phi_{j}, y=\phi_{i},w,z\leq n$, for some
$0\leq i,j\leq n$, be four integers, such that
\[
z\rightarrow x\dashrightarrow x+1\rightarrow y
\]
and
\[
y\rightarrow w
\]
appear in some alternating cycles of $\Gr(\phi)$. The black arrow
$x+1\rightarrow y$ implies that $x+1=\phi_{i+1}$. The black arrow
$z\rightarrow x$ implies that $z=\phi_{j+1}$. The black arrow $y\rightarrow w$
implies that $w=\phi_{i-1}$. All the arithmetic is performed modulo $n+1$. The
$x--y$ exchange operation is defined as follows (compare it to Lemma
\ref{small.exchange})

\begin{itemize}
\item if $x=w$ or if $y=z$, then the $x--y$ exchange operation does not change
$\phi$;

\item if $y=\phi_{0}=0$, then the $x--y$ exchange operation changes
\[
\langle\phi_{1}=(x+1)\;\;\ldots\;\;\phi_{j-1}\;\;\phi_{j}=x\;\;\phi
_{j+1}=z\;\;\ldots\;\;\phi_{n}=w\rangle
\]
to
\[
\langle\phi_{j+1}=z\;\;\phi_{j+2}\;\;\ldots\phi_{n}=w\;\;\phi_{1}
=(x+1)\;\;\ldots\;\;\phi_{j-1}\;\;\phi_{j}=x\rangle;
\]


\item if $x=\phi_{0}=0$, then the $x--y$ exchange operation changes
\[
\langle\phi_{1}=z\;\;\ldots\;\;\phi_{i-1}=w\;\;\phi_{i}=y\;\;\phi
_{i+1}=1\;\;\ldots\;\;\phi_{n}\rangle
\]
to
\[
\langle\phi_{i}=y\;\;\phi_{1}=z\;\;\ldots\;\;\phi_{i-1}=w\;\;\phi
_{i+1}=1\;\;\ldots\;\;\phi_{n}\rangle;
\]


\item if $1<i+1<j$, then the $x--y$ exchange operation changes
\[
\langle\phi_{1}\;\;\ldots\;\;\phi_{i-1}=w\;\;\phi_{i}=y\;\;\phi_{i+1}
=(x+1)\;\;\ldots\;\;\phi_{j}=x\;\;\phi_{j+1}=z\;\;\ldots\;\;\phi_{n}\rangle
\]
to
\[
\langle\phi_{1}\;\;\ldots\;\;\phi_{i-1}=w\;\;\phi_{i+1}=(x+1)\;\;\ldots
\;\;\phi_{j}=x\;\;\phi_{i}=y\;\;\phi_{j+1}=z\;\;\ldots\;\;\phi_{n}\rangle;
\]


\item if $0<j<i$, then the $x--y$ exchange operation changes
\[
\langle\phi_{1}\;\;\ldots\;\;\phi_{j}=x\;\;\phi_{j+1}=z\;\;\ldots
\;\;\phi_{i-1}=w\;\;\phi_{i}=y\;\;\phi_{i+1}=(x+1)\;\;\ldots\;\;\phi
_{n}\rangle
\]
to
\[
\langle\phi_{1}\;\;\ldots\;\;\phi_{j}=x\;\;\phi_{i}=y\;\;\phi_{j+1}
=z\;\;\ldots\;\;\phi_{i-1}=w\;\;\phi_{i+1}=(x+1)\;\;\ldots\;\;\phi_{n}\rangle.
\]

\end{itemize}
\end{definition}

Let us consider several examples of the $x--y$ exchange operation.

\begin{example}
Let $\phi=\langle4\;\;1\;\;6\;\;2\;\;5\;\;7\;\;3\rangle$. We perform the
$5--1$ exchange operation on $\phi$. Here $x=5=\phi_{5}$ and $y=1=\phi_{2}$.
Hence, $z=\phi_{6}=7$ and $w=\phi_{1}=4$. The fact that $x+1=6=\phi_{3}$
causes the condition $x+1\rightarrow y$ to be satisfied. The condition
$x+1\rightarrow y$ is what makes the $x--y$ exchange operation possible. Now,
$i=2$ and $j=5$. Thus, $1<i+1<j$ and we get that the $5--1$ exchange operation
changes $\phi$ to $\langle4\;\;6\;\;2\;\;5\;\;1\;\;7\;\;3\rangle$.
\end{example}

\begin{example}
Let $\phi=\langle4\;\;1\;\;6\;\;2\;\;5\;\;7\;\;3\rangle$. We perform the
$4--2$ exchange operation on $\phi$. Here $x=4=\phi_{1}$ and $y=2=\phi_{4}$.
Hence, $z=\phi_{2}=1$ and $w=\phi_{3}=6$. The fact that $x+1=5=\phi_{5}$
causes the condition $x+1\rightarrow y$ to be satisfied. The condition
$x+1\rightarrow y$ is what makes the $x--y$ exchange operation possible. Now,
$i=4$ and $j=1$. Thus, $0<j<i$ and we get that the $4--2$ exchange operation
changes $\phi$ to $\langle4\;\;2\;\;1\;\;6\;\;5\;\;7\;\;3\rangle$.
\end{example}

\begin{example}
Let $\phi=\langle4\;\;6\;\;1\;\;2\;\;5\;\;7\;\;3\rangle$. We perform the
$0--6$ exchange operation on $\phi$. Here $x=0=\phi_{0}$ and $y=6=\phi_{2}$.
Hence, $z=\phi_{1}=4$ and $w=\phi_{5}=5$. The fact that $x+1=1=\phi_{3}$
causes the condition $x+1\rightarrow y$ to be satisfied. The condition
$x+1\rightarrow y$ is what makes the $x--y$ exchange operation possible. Now,
$i=2$ and $j=0$. Since $x=\phi_{0}=0$, we get that the $0--6$ exchange
operation changes $\phi$ to $\langle6\;\;4\;\;1\;\;2\;\;5\;\;7\;\;3\rangle$.
\end{example}

\begin{example}
Let $\phi=\langle4\;\;1\;\;6\;\;3\;\;5\;\;7\;\;2\rangle$. We perform the
$3--0$ exchange operation on $\phi$. Here $x=3=\phi_{4}$ and $y=0=\phi_{0}$.
Hence, $z=\phi_{5}=5$ and $w=\phi_{7}=2$. The fact that $x+1=4=\phi_{1}$
causes the condition $x+1\rightarrow y$ to be satisfied. The condition
$x+1\rightarrow y$ is what makes the $x--y$ exchange operation possible. Now,
$i=0$ and $j=4$. Since $y=\phi_{0}=0$, we get that the $3--0$ exchange
operation changes $\phi$ to $\langle5\;\;7\;\;2\;\;4\;\;1\;\;6\;\;3\rangle$.
\end{example}

Notice that after completing the $x--y$ exchange operation on $\phi$,
$y\rightarrow x\dashrightarrow x+1\rightarrow w$ and $z\rightarrow y$ will
appear in the alternating cycles of the cycle graph of the new permutation.

\begin{proposition}
\label{exchange-product} Let $\phi$ and $\theta$ be two different permutations
in $S_{n}$, such that $\theta$ is obtained from $\phi$ by an $x--y$ exchange
operation. Then $\theta^{\bullet}$ is obtained from $\phi^{\bullet}$ by
multiplying $\phi^{\bullet}$ on the left by the $3-$cycle $(x,y,w)\in S(1+n)$.
Namely,
\[
\theta^{\bullet}=(x,y,w)\cdot\phi^{\bullet}.
\]

\end{proposition}

\begin{proof}
Since the $x--y$ exchange operation was permissible on $\phi$, and since this
operation changed $\phi$, the cycle $\phi^{\bullet}$ must be of the form
$(x+1,y,w,\ldots,z,x,\ldots)$. Indeed, $(x+1)\rightarrow y\rightarrow w$ and
$z\rightarrow x$ cannot intersect, since $\theta\neq\phi$. Here we are using
the cyclic notation, in which the cycles can be written starting from any
entry. Now,
\[
(x,y,w)\cdot\phi^{\bullet}=(x+1,w,\ldots,z,y,x,\ldots).
\]
To construct $\theta$ we need to rewrite the cycle $(x+1,w,\ldots
,z,y,x,\ldots)$, starting from $0$. Then the cycle will become $(0,\theta
_{n},\ldots,\theta_{1})$, which permits us to obtain $\theta=\langle\theta
_{1}\;\;\ldots\;\;\theta_{n}\rangle$. When we rewrite the cycle $(x+1,w,\ldots
,z,y,x,\ldots)$, starting from $0$, we can have four different cases

\begin{itemize}
\item if $y=0$, then the cycle, after rewriting, becomes $(y=0,x,\ldots
,x+1,w,\ldots,z)$;

\item if $x=0$, then the cycle, after rewriting, becomes $(x=0,\ldots
,x+1=1,w,\ldots,z,y)$;

\item if $1<i+1<j$, then the cycle, after rewriting, becomes \newline
$(0,\ldots,z,y,x,\ldots,x+1,w,\ldots)$;

\item if $1<j<i$, then the cycle, after rewriting, becomes $(0,\ldots
,x+1,w,\ldots,z,y,x,\ldots)$.
\end{itemize}

In all these four cases we obtain the exact $\theta$, which is described in
Definition \ref{def.exchange} as the result of the $x--y$ exchange operation.
\end{proof}

Notice that the inverse of an $x--y$ exchange operation is not, in general, an
$x--y$ exchange operation. Indeed, $\theta^{\bullet}$ might not contain
$(w+1)\rightarrow y\rightarrow x$, which is required to perform a $w--x$
exchange operation on $\theta$ and obtain $\phi$.

\begin{proposition}
\label{exchange-circ} Let $\theta\ne\phi$ be a permutation obtained from
$\phi$ by some $x--y$ exchange operation. Then the cyclic presentation of
$\theta^{\circ}$ is obtained from the cyclic presentation of $\phi^{\circ}$ by
relocating $x$ from the place after $(z-1)$ and before $y$ to the place after
$(y-1)$ and before $w$; i.e., the cycle of $\phi^{\circ}$ of the form
$(\ldots,z-1,x,y,\ldots)$ becomes $(\ldots,z-1,y,\ldots)$, and the cycle of
$\phi^{\circ}$ of the form $(\ldots,y-1,w,\ldots)$ becomes $(\ldots
,y-1,x,w,\ldots)$. This, in particular, implies that $\theta^{\circ}$ and
$\phi^{\circ}$ have the same number of cycles in their cyclic decompositions.
\end{proposition}

\begin{proof}
By Proposition \ref{exchange-product}, $\theta^{\bullet}=(x,y,w)\cdot
\phi^{\bullet}$. This implies that
\[
\theta^{\circ}=\theta^{\bullet}\cdot(0,1,\ldots,n)=(x,y,w)\cdot\phi^{\bullet
}\cdot(0,1,\ldots,n)=(x,y,w)\cdot\phi^{\circ}
\]
Now, multiplication of $\phi^{\circ}$ on the left by $(x,y,w)$ removes $x$
 from the cycle \newline$(\ldots,z-1,x,y,\ldots)$ and places it in the cycle
$(\ldots,y-1,w,\ldots)$ between $y-1$ and $w$. Thus, $z-1$, instead of going
to $x$, now goes to $y$. And $x$, instead of going to $y$, now goes to $w$.
And $y-1$, instead of going to $w$, now goes to $x$. No other changes are done
by multiplication of $\phi^{\circ}$ from the left by $3-$cycle $(x,y,w)$.
\end{proof}

Recall that Bafna and Pevzner \cite{BP}, for $1\leq i<j<k\leq n+1$, defined
the permutation $\rho(i,j,k)$ to be
\begin{equation}
\rho(i,j,k)=\langle1\;\;\ldots\;\;(i-1)\;\;j\;\;\ldots\;\;(k-1)\;\;i\;\;\ldots
\;\;(j-1);\;k\;\;\ldots\;\;n\rangle.\label{rho.def}
\end{equation}
Next, for a permutation $\phi\in S_{n}$, Bafna and Pevzner defined a
block-transposition, which exchanges places of the blocks $i\;\;\ldots
\;\;(j-1)$ and $j\;\;\ldots\;\;(k-1)$ inside $\phi$, to be $\phi\cdot
\rho(i,j,k)$. For any three pairwise different integers $1\leq i,j,k\leq n$
one can define
\[
\rho(i,j,k)=\rho(i,k,j)=\rho(j,i,k)=\rho(j,k,i)=\rho(k,i,j)=\rho(k,j,i).
\]
Since in one of these six expressions, $i,j,k$ are placed in the increasing
order, which makes that expression well-defined by Equation \ref{rho.def}, all
six expressions are now well-defined and represent the same permutation
$\rho(i,j,k)$. Finally, if two or more of the three integers $1\leq i,j,k\leq
n+1$ are equal, $\rho(i,j,k)$ is defined as an identity permutation. Now
$\rho(i,j,k)$ is defined for any three integers $1\leq i,j,k\leq n+1$ and
represents an appropriate block-transposition. Clearly, if two or more of the
three integers $1\leq i,j,k\leq n$ are equal, at least one of the blocks is
empty, which corresponds to no change performed to $\phi$. Now we can relate
our $x--y$ exchange operation to the block-transpositions.

\begin{remark}
\label{exchange-block-trans} Let $\phi$ be a permutation in $S_{n}$, extended
by $\phi_{0}=0$, such that for some $0\leq\phi_{j}=x,\phi_{i}=y\leq n$,
$\phi_{i+1}=x+1$. Then performing the $x--y$ exchange operation is a
block-transposition, for which the permutation $\rho$ is selected as follows

\begin{itemize}
\item if $x=j=0$, then select $\rho(1,i,i+1)$;

\item if $y=i=0$, then select $\rho(1,j+1,n+1)$;

\item in all other cases select $\rho(i,i+1,j+1)$.
\end{itemize}
\end{remark}

Lemma 2.1 in Bafna and Pevzner's work \cite{BP} asserts that a
block-transformation can either increase by two, or decrease by two, or keep
unchanged the number of alternating cycles in the cycle graph of a
permutation. We now show that an $x--y$ exchange operation does not change the
number of alternating cycles in the cycle graph of a permutation.

\begin{lemma}
\label{exchange.same.num.cycles} Let a permutation $\theta\in S_{n}$ be
obtained from a permutation $\phi\in S_{n}$ by an $x--y$ exchange operation.
Then $\theta$ and $\phi$ have the same number of alternating cycles in their
cycle graphs $\Gr(\theta)$ and $\Gr(\phi)$.
\end{lemma}

\begin{proof}
The lemma directly follows from Proposition \ref{exchange-circ} and Theorem
\ref{Theorem.8}. However, we produce an alternative proof, based on Bafna and
Pevzner's analysis of block-\\transformations.

Notice that the edges, which appear in $\Gr(\phi)$ and which do not appear in
$\Gr(\theta)$, are precisely the three black edges $\phi_{i}=y\rightarrow
w=\phi_{i-1}$, $\phi_{i+1}=x+1\rightarrow y=\phi_{i}$, and $\phi
_{j+1}=z\rightarrow x=\phi_{j}$.

Similarly, the edges, which appear in $\Gr(\theta)$ and which do not appear in
$\Gr(\phi)$, are precisely the three black edges $\phi_{i+1}=x+1\rightarrow
w=\phi_{i-1}$, $\phi_{j+1}=z\rightarrow y=\phi_{i}$, and $\phi_{i}
=y\rightarrow x=\phi_{j}$.

Since the black edges $\phi_{i+1}=x+1\rightarrow y=\phi_{i}$ and $\phi
_{j+1}=z\rightarrow x=\phi_{j}$ belong to the same alternating cycle in
$\Gr(\phi)$, the above-mentioned three black edges $y\rightarrow w$,
$x+1\rightarrow y$, and $z\rightarrow x$ belong to, at most, two alternating
cycles in $\Gr(\phi)$. Similarly, since the black edges $\phi_{i+1}
=x+1\rightarrow w=\phi_{i-1}$ and $\phi_{i}=y\rightarrow x=\phi_{j}$ belong to
the same alternating cycle in $\Gr(\theta)$, the above-mentioned three black
edges $x+1\rightarrow w$, $z\rightarrow y$, and $y\rightarrow x$ belong to, at
most, two alternating cycles in $\Gr(\phi)$.

In the proof of Lemma 2.1 in Bafna and Pevzner's work \cite{BP},it is shown
that if $\Gr(\phi)$ and $\Gr(\theta)$ differ by exactly three black edges,
which in both graphs $\Gr(\phi)$ and $\Gr(\theta)$ belong to one or two
alternating cycles, then $\Gr(\phi)$ and $\Gr(\theta)$ have the same number of
alternating cycles.
\end{proof}

\begin{definition}
\label{exchange.orbit.def} We say that the permutations $\phi,\theta\in S_{n}
$ are in the same ``$x--y$ exchange orbit" if there exist some permutations
$\tau_{1},\ldots,\tau_{k}\in S_{n}$ such that $\tau_{1}=\phi$, $\tau
_{k}=\theta$, and, for each $i=1,\ldots,k-1$, either $\tau_{i}$ can be
obtained from $\tau_{i+1}$ by an $x--y$ exchange operation, or $\tau_{i+1}$
can be obtained from $\tau_{i}$ by an $x--y$ exchange operation.
\end{definition}

Notice that according to Definition \ref{exchange.orbit.def}, $\phi,\theta\in
S_{n}$ can be in the same $x--y$ exchange orbit, while neither of them can be
obtained from the other by performing $x--y$ exchange operations.

\begin{theorem}
\label{exchange.operation.keeps.prob} Let $\phi,\theta\in S_{n}$ be two
permutations such that $\theta$ is obtained from $\phi$ by an $x--y$ exchange
operation. Then
\[
\Pr(a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
)=\Pr(a_{1}a_{2}\cdots a_{n}=a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}
}).
\]

\end{theorem}

\begin{proof}
Compare this proof with the proof of Lemma \ref{small.exchange} above. If
$x=y$ then $\theta=\phi$ and the theorem follows. Hence, we assume that $x\neq
y$.

First, we consider the case when $x,x+1,w,y,z$ are all different than $0$. In
that case, the requirement that $z\rightarrow x\dashrightarrow x+1\rightarrow
y$ and $y\rightarrow w$ are present in $\Gr(\phi)$ implies that the product
$a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}$ contains sub-products
$a_{w}a_{y}a_{x+1}$ and $a_{x}a_{z}$. These two sub-products $a_{w}
a_{y}a_{x+1}$ and $a_{x}a_{z}$ can ``overlap" if and only if $z=w$. By
overlapping we mean that they have a common piece. For example, if $z=w$ then
$a_{z}=a_{w}$ is the overlap of these two products.

If the sub-product $a_{w}a_{y}a_{x+1}$ appears in the product $a_{\phi_{1}
}a_{\phi_{2}}\cdots a_{\phi_{n}}$ before the sub-product $a_{x}a_{z}$, then
$z\ne w$. In that case, we rewrite the equation
\[
a_{1}\cdots a_{x}a_{x+1}a_{x+2}\cdots a_{n}=a_{\phi_{1}}\cdots a_{\phi_{i-2}
}a_{w}a_{y}a_{x+1}a_{\phi_{i+2}}\cdots a_{\phi_{j-1}}a_{x}a_{z}a_{\phi_{j+2}
}\cdots a_{\phi_{n}}
\]
as
\begin{equation}
\label{Case1a.Eq1}a_{1}\cdot\cdot\cdot a_{x}a_{y}^{-1}(a_{y}a_{x+1}
)a_{x+2}\cdot\cdot\cdot a_{n}=a_{\phi_{1}}\cdot\cdot\cdot a_{\phi_{i-2}}
a_{w}(a_{y}a_{x+1})a_{\phi_{i+2}}\cdot\cdot\cdot a_{\phi_{j-1}}a_{x}
a_{z}a_{\phi_{j+2}}\cdot\cdot\cdot\, a_{\phi_{n}}
\end{equation}


Similarly, the fact that $y\rightarrow x\dashrightarrow x+1\rightarrow w$ and
$z\rightarrow y$ are present in $\Gr(\theta)$, implies that the product
$a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}}$ contains sub-products
$a_{x}a_{y}a_{z}$ and $a_{w}a_{x+1}$. These two sub-products can ``overlap" if
and only if either $x=w$ or $z=x+1$. But $\phi_{j+1}=z=x+1=\phi_{i+1}$ would
imply $i=j$ and $\phi_{j}=x=y=\phi_{i}$. Thus, $\theta=\phi$. If $x=w$, then
$\theta=\phi$ by Definition \ref{def.exchange}. So, we can assume that
$a_{w}a_{y}a_{x+1}$ and $a_{x}a_{z}$ do not overlap. Again, we rewrite the
equation
\[
a_{1}\cdots a_{x-1}a_{x}a_{x+1}a_{x+2}\cdots a_{n}=a_{\theta_{1}}\cdots
a_{\theta_{i-2}}a_{w}a_{x+1}a_{\theta_{i+1}}\cdots a_{\theta_{j-2}}a_{x}
a_{y}a_{z}a_{\theta_{j+2}}\cdots a_{\theta_{n}}
\]
as
\begin{equation}
\label{Case1a.Eq2}a_{1}\cdot\cdot\cdot a_{x-1}(a_{x}a_{y})a_{y}^{-1}
a_{x+1}\cdot\cdot\cdot a_{n} =a_{\theta_{1}}\cdot\cdot\cdot a_{\theta_{i-2}
}a_{w}a_{x+1}a_{\theta_{i+1}}\cdot\cdot\cdot a_{\theta_{j-2}}(a_{x}a_{y}
)a_{z}a_{\theta_{j+2}}\cdot\cdot\cdot a_{\theta_{n}}\,.
\end{equation}
Notice that as the random variable $a_{y}$ runs over all the elements of $G$,
so does its inverse $a_{y}^{-1}$. Also, for each choice of $a_{y}$, as the
random variable $a_{x}$ runs over all the elements of $G$, so does the random
variable $b=(a_{x}a_{y})$. Similarly, for each choice of $a=a_{y}^{-1} $, as
the random variable $a_{x+1}$ runs over all the elements of $G$, so does the
random variable $c=(a_{y}a_{x+1})$.

We show now that Equations \ref{Case1a.Eq1} and \ref{Case1a.Eq2}, up to
renaming variables, are identical. We regard $b=(a_{x}a_{y})$ as one variable.
Similarly, we regard $c=(a_{y}a_{x+1})$ as one variable. Notice that the left
sides of Equations \ref{Case1a.Eq1} and \ref{Case1a.Eq2} have $n+1$ variables
in each, and their right sides have $n-1$ variables in each. Both left sides
have the variables $a_{1},\ldots,a_{x-1}$ in place of $1,\ldots,x-1$,
respectively, and the variables $a_{x+2},\ldots,a_{n}$ in place of
\newline$x+3,\ldots,n+1$, respectively.

Notice that for all $1\leq r\leq i-1$, $\phi_{r}=\theta_{r}$ and $a_{\phi_{r}
}=a_{\theta_{r}}$. Similarly, for all $j+1\leq r\leq n$, $\phi_{r}=\theta_{r}$
and $a_{\phi_{r}}=a_{\theta_{r}}$. For $i+1\leq r\leq j-2$, $\phi_{r+1}
=\theta_{r}$ and $a_{\phi_{r+1}}=a_{\theta_{r}}$. Thus, the right sides of
Equations \ref{Case1a.Eq1} and \ref{Case1a.Eq2} carry the same variables in
place of $1,\ldots,i-1$ and $i+1,\ldots,j-2$ and $j,\ldots,n-1$.

The random variable $a_{x}$ appears in the $x$-th place on the left side of
Equation \ref{Case1a.Eq1} and in the $(j-1)$-th place on its right side.
Similarly, the random variable $b=(a_{x}a_{y})$ appears in the $x$-th place on
the left side of Equation \ref{Case1a.Eq2} and in the $(j-1)$-th place on its
right side.

The inverse $a_{y}^{-1}$ of the random variable $a_{y}$ appears in the $(x+1)
$-th place on the left side of Equation \ref{Case1a.Eq1} and does not appear
on its right side. Similarly, the inverse $a_{y}^{-1}$ of the random variable
$a_{y}$ appears in the $(x+1)$-th place on the left side of Equation
\ref{Case1a.Eq2} and does not appear its right side. The random variable
$a_{y}$ cannot appear in the $x$-th, $(x+1)$-th, or $(x+2)$-th place on the
left side of Equation \ref{Case1a.Eq1} or of Equation \ref{Case1a.Eq2}. Since
the rest of the places of the left sides of Equations \ref{Case1a.Eq1} and
\ref{Case1a.Eq2} carry the same variables, $a_{y}$ must appear in the same
place in both left sides. The right sides of Equations \ref{Case1a.Eq1} and
\ref{Case1a.Eq2} do not contain $a_{y}$.

The random variable $c=(a_{y}a_{x+1})$ appears in the $(x+2)$-th place on the
left side of Equation \ref{Case1a.Eq1} and on the $i$-th place on its right
side. Similarly, the random variable $a_{x+1}$ appears in the $(x+2)$-th place
on the left side of Equation \ref{Case1a.Eq2} and in the $i$-th place on its
right side.

Thus, Equations \ref{Case1a.Eq1} and \ref{Case1a.Eq2}, up to renaming
variables, are identical. This implies that they have the same number of
solutions. This, in its turn, implies that
\[
\Pr(a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
)=\Pr(a_{1}a_{2}\cdots a_{n}=a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}
}).
\]


Now, assume that the sub-product $a_{x}a_{z}$ appears in the product
$a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}$ before the sub-product
$a_{w}a_{y}a_{x+1}$. Then, if $z=w$, then $a_{z}$ is the same as $a_{w}$, and
we have the sub-product $a_{x}a_{w}a_{y}a_{x+1}$ inside the product
$a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}$. In that case, the $x--y$
exchange operation only exchanges the places of $a_{w}$ and $a_{y}$. We
rewrite the equation
\[
a_{1}\cdots a_{x-1}a_{x}a_{x+1}a_{x+2}\cdots a_{n}=a_{\phi_{1}}\cdots
a_{\phi_{i-3}}a_{x}a_{w}a_{y}a_{x+1}a_{\phi_{i+2}}\cdots a_{\phi_{n}}
\]
as
\begin{equation}
a_{1}\cdots a_{x-1}a_{x}a_{y}^{-1}(a_{y}a_{x+1})a_{x+2}\cdots a_{n}
=a_{\phi_{1}}\cdots a_{\phi_{i-3}}a_{x}a_{w}(a_{y}a_{x+1})a_{\phi_{i+2}}\cdots
a_{\phi_{n}}.\label{special.case.eq.1}
\end{equation}
The equation
\[
a_{1}\cdots a_{x-1}a_{x}a_{x+1}a_{x+2}\cdots a_{n}=a_{\theta_{1}}\cdots
a_{\theta_{i-3}}a_{x}a_{y}a_{w}a_{x+1}a_{\theta_{i+2}}\cdots a_{\theta_{n}}
\]
is identical to the equation
\[
a_{1}\cdots a_{x-1}a_{x}a_{x+1}a_{x+2}\cdots a_{n}=a_{\phi_{1}}\cdots
a_{\phi_{i-3}}a_{x}a_{y}a_{w}a_{x+1}a_{\phi_{i+2}}\cdots a_{\phi_{n}},
\]
which we rewrite as
\begin{equation}
a_{1}\cdots a_{x-1}(a_{x}a_{y})a_{y}^{-1}a_{x+1}a_{x+2}\cdots a_{n}
=a_{\phi_{1}}\cdots a_{\phi_{i-3}}(a_{x}a_{y})a_{w}a_{x+1}a_{\phi_{i+2}}\cdots
a_{\phi_{n}}.\label{special.case.eq.2}
\end{equation}
Again, the random variable $a_{y}$ and its inverse $a_{y}^{-1}$ appear in the
same places in both Equations \ref{special.case.eq.1} and
\ref{special.case.eq.2}. The random variable $c=(a_{x}a_{y})$ in Equation
\ref{special.case.eq.2} plays the role of the random variable $a_{x}$ in the
Equation \ref{special.case.eq.1}. The random variable $a_{x+1}$ in Equation
\ref{special.case.eq.2} plays the role of the random variable $b=(a_{y}
a_{x+1})$ in Equation \ref{special.case.eq.1}. Thus, Equations
\ref{special.case.eq.1} and \ref{special.case.eq.2}, up to renaming variables,
are identical. This implies that they have the same number of solutions. This,
in its turn, implies that
\[
\Pr(a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
)=\Pr(a_{1}a_{2}\cdots a_{n}=a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}
}).
\]


If $z\ne w$, then we rewrite the equation
\[
a_{1}\cdots a_{x-1}a_{x}a_{x+1}a_{x+2}\cdots a_{n}=a_{\phi_{1}}\cdots
a_{\phi_{j-1}}a_{x}a_{z}a_{\phi_{j+2}}\cdots a_{w}a_{y}a_{x+1}a_{\phi_{i+2}
}\cdots a_{\phi_{n}}
\]
as
\begin{equation}
\label{Case2a.Eq1}a_{1}\cdot\cdot\cdot a_{x-1}a_{x}a_{y}^{-1}(a_{y}
a_{x+1})a_{x+2}\cdot\cdot\cdot a_{n}=a_{\phi_{1}}\cdot\cdot\cdot a_{\phi
_{j-1}}a_{x}a_{z}a_{\phi_{j+2}}\cdot\cdot\cdot a_{w}(a_{y}a_{x+1}
)a_{\phi_{i+2}}\cdot\cdot\cdot a_{\phi_{n}}\,.
\end{equation}


Similarly, we rewrite the equation
\[
a_{1}\cdots a_{x-1}a_{x}a_{x+1}a_{x+2}\cdots a_{n}=a_{\theta_{1}}\cdots
a_{\theta_{j-1}}a_{x}a_{y}a_{z}a_{\theta_{j+3}}\cdots a_{w}a_{x+1}
a_{\theta_{i+2}}\cdots a_{\theta_{n}}
\]
as
\begin{equation}
\label{Case2a.Eq2}a_{1}\cdot\cdot\cdot a_{x-1}(a_{x}a_{y})a_{y}^{-1}
a_{x+1}a_{x+2}\cdot\cdot\cdot a_{n}=a_{\theta_{1}}\cdot\cdot\cdot
a_{\theta_{j-1}}(a_{x}a_{y})a_{z}a_{\theta_{j+3}}\cdot\cdot\cdot a_{w}
a_{x+1}a_{\theta_{i+2}}\cdot\cdot\cdot a_{\theta_{n}}\,.
\end{equation}
Comparison of Equations \ref{Case2a.Eq1} and \ref{Case2a.Eq2}, shows that,
similarly to Equations \ref{Case1a.Eq1} and \ref{Case1a.Eq2}, and Equations
\ref{special.case.eq.1} and \ref{special.case.eq.2}, which we compared in
detail above, a certain renaming of variables in Equation \ref{Case2a.Eq2}
transforms it into Equation \ref{Case2a.Eq1}. Thus, again
\[
\Pr(a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
)=\Pr(a_{1}a_{2}\cdots a_{n}=a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}
}).
\]


Now, we consider the case when $x=\phi_{0}=\theta_{0}=0$. In this case
$y=\phi_{i}=\theta_{1}$, \newline$z=\phi_{1}=\theta_{2}$, $\phi_{2}=\theta
_{3},\ldots,\phi_{i-1}=\theta_{i}=w $, $x+1=\phi_{i+1}=\theta_{i+1}=1$, and
\newline$\phi_{i+2}=\theta_{i+2},\ldots,\phi_{n}=\theta_{n}$. We rewrite the
equation
\[
a_{1}a_{2}\cdots a_{n}=a_{z}a_{\phi_{2}}\cdots a_{\phi_{i-2}}a_{w}a_{y}
a_{1}a_{\phi_{i+2}}\cdots a_{\phi_{n}}
\]
as
\begin{equation}
\label{Case2.Eq1}(a_{y}a_{1})a_{2}\cdots a_{n}=a_{y}a_{z}a_{\phi_{2}}\cdots
a_{\phi_{i-2}}a_{w}(a_{y}a_{1})a_{\phi_{i+2}}\cdots a_{\phi_{n}},
\end{equation}
in which the random variable $a_{1}$ is omitted, and for each fixed value of
$a_{y}$, as $a_{1}$ runs over all the elements of $G$, so does the random
variable $b=(a_{y}a_{1})$.

Now, compare Equation \ref{Case2.Eq1} with the equation
\begin{equation}
\label{Case2.Eq2}a_{1}a_{2}\cdots a_{n}=a_{y}a_{z}a_{\theta_{3}}\cdots
a_{\theta_{i-1}}a_{w}a_{1}a_{\theta_{i+2}}\cdots a_{\theta_{n}}.
\end{equation}
Clearly, renaming $b=(a_{y}a_{1})$ to $a_{1}$ turns Equation \ref{Case2.Eq1}
to Equation \ref{Case2.Eq2}. Thus, again
\[
\Pr(a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
)=\Pr(a_{1}a_{2}\cdots a_{n}=a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}
}).
\]


Now we consider the case when $x=n$. In that case $x+1=0=\phi_{0}=\theta_{0}$,
\newline$y=\phi_{n}$ and $w=\phi_{n-1}=\theta_{n}$. Observe, that in that case
the equation
\[
a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
\]
is
\begin{equation}
\label{Case3.Eq1}a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}\cdots a_{\phi_{j-1}}
a_{n}a_{z}a_{\phi_{j+2}}\cdots a_{\phi_{n-2}}a_{w}a_{y}.
\end{equation}
Similarly, the equation
\[
a_{1}a_{2}\cdots a_{n}=a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}}
\]
in that case becomes
\[
a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}\cdots a_{\phi_{j-1}}a_{n}a_{y}a_{z}
a_{\phi_{j+2}}\cdots a_{\phi_{n-2}}a_{w},
\]
which we rewrite as
\begin{equation}
a_{1}a_{2}\cdots(a_{n}a_{y})=a_{\phi_{1}}\cdots a_{\phi_{j-1}}(a_{n}
a_{y})a_{z}a_{\phi_{j+2}}\cdots a_{\phi_{n-2}}a_{w}a_{y}.\label{Case3.Eq2}
\end{equation}
Again, the random variable $b=(a_{n}a_{y})$ in Equation \ref{Case3.Eq2} plays
the role of the random variable $a_{n}$ in Equation \ref{Case3.Eq1}. Thus,
again
\[
\Pr(a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
)=\Pr(a_{1}a_{2}\cdots a_{n}=a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}
}).
\]


Finally, we consider the case when $y=0=\phi_{0}=\theta_{0}$. In this case
$x+1=\phi_{1}$ and $w=\phi_{n}$. Thus, the equation
\[
a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
\]
becomes
\[
a_{1}a_{2}\cdots a_{n}=a_{x+1}a_{\phi_{2}}\cdots a_{\phi_{j-1}}a_{x}
a_{z}a_{\phi_{j+2}}\cdots a_{\phi_{n-1}}a_{w}.
\]
On the other hand, the equation
\[
a_{1}a_{2}\cdots a_{n}=a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}}
\]
becomes
\[
a_{1}a_{2}\cdots a_{n}=a_{z}a_{\phi_{j+2}}\cdots a_{\phi_{n-1}}a_{w}
a_{x+1}a_{\phi_{2}}\cdots a_{\phi_{j-1}}a_{x}.
\]
Let
\[
r=a_{x},s=a_{x+1},A=a_{1}\cdots a_{x-1},B=a_{x+2}a_{x+3}\cdots a_{n}
,P=a_{\phi_{2}}\cdots a_{\phi_{j-1}},
\]
and $Q=a_{z}a_{\phi_{j+2}}\cdots a_{\phi_{n-1}}a_{w}$. Then
\[
a_{1}a_{2}\cdots a_{n}=a_{x+1}a_{\phi_{2}}\cdots a_{\phi_{j-1}}a_{x}
a_{z}a_{\phi_{j+2}}\cdots a_{\phi_{n-1}}a_{w}
\]
becomes
\[
ArsB=sPrQ,
\]
and
\[
a_{1}a_{2}\cdots a_{n}=a_{z}a_{\phi_{j+2}}\cdots a_{\phi_{n-1}}a_{w}
a_{x+1}a_{\phi_{2}}\cdots a_{\phi_{j-1}}a_{x}
\]
becomes
\[
ArsB=QsPr.
\]
But $\Pr(ArsB=sPrQ)$ is the same as $\Pr(rArsB=rsPrQ)$, which is the same as
$\Pr(\gamma A\theta B=\theta P\gamma Q)$, where $\gamma=r,\theta=rs$, which,
in its turn, is the same as \newline$\Pr(\gamma A\theta BQ^{-1}\gamma
^{-1}=\theta P)$. Notice that since the random element $s$ does not appear in
the last equation, we regard $\theta=rs $ as a random element from $G$. And
$\gamma A\theta BQ^{-1}\gamma^{-1}=\theta P$ is equivalent to saying that
$A\theta BQ^{-1}$ is conjugate to $\theta P$.

Similarly, $\Pr(ArsB=QsPr)$ is the same as $\Pr(ArsBs=QsPrs)$, which is the
same as $\Pr(A\theta B\gamma=Q\gamma P\theta)$, where $\gamma=s,\theta=rs$,
which, in turn, is the same as $\Pr(\gamma^{-1}Q^{-1}A\theta B\gamma=P\theta)
$. Again, we regard $\theta=rs$ as a random element from $G$. And $\gamma
^{-1}Q^{-1}A\theta B\gamma=P\theta$ is equivalent to saying that
$Q^{-1}A\theta B$ is conjugate to $P\theta$.

Finally, notice that $\theta P=\theta(P\theta)\theta^{-1}$ is conjugate to
$P\theta$, and \newline$A\theta BQ^{-1}=Q(Q^{-1}A\theta B)Q{-1}$ is conjugate
to $Q^{-1}A\theta B$. Thus, $A\theta BQ^{-1}$ is conjugate to $\theta P$ if
and only if $Q^{-1}A\theta B$ is conjugate to $P\theta$. Thus,
\[
\Pr(a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
)=\Pr(a_{1}a_{2}\cdots a_{n}=a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}
}).
\]

\end{proof}

\subsection{Cyclic operation}

Now we define and discuss $x--y$ cyclic operation. This material is
illustrated by Lemma \ref{small.cyclic} above. Let $\phi\in S_{n}$ be a
permutation such that $\phi^{\bullet}\in S(1+n)$ contains some
$(x+1)\rightarrow y\rightarrow x$. In other words, for some $0\leq i\leq n$,
we have $\phi_{i}=x$, $\phi_{i+1}=y$, and $\phi_{i+2}=y$. Notice that if $x=n
$, the condition $(x+1)\rightarrow y\rightarrow x$ becomes \newline$0=\phi
_{0}\rightarrow y=\phi_{n}\rightarrow n=\phi_{n-1}$.

\begin{definition}
\label{cyclic-cdot} The $x--y$ cyclic operation on the permutation $\phi$ is
defined as follows

\begin{itemize}
\item If $y=x+2$, then the $x--y$ cyclic operation does not do anything to
$\phi$;

\item If $y>x+2$, then in the long cycle $\phi^{\bullet}$ we replace $x+1$ by
$y-1$ and replace each $t=x+2,\ldots,y-1$ by $t-1$. In other words, the $x--y$
cyclic operation changes $\phi^{\bullet}$ to
\begin{align*}
(y-1, y-2,\ldots, x+2, x+1)^{-1}\cdot\phi^{\bullet}\cdot(y-1, y-2,\ldots, x+2,
x+1)\\={\phi^{\bullet}}^{(y-1, y-2,\ldots, x+2, x+1)};
\end{align*}


\item If $y=x-1$, then the $x--y$ cyclic operation does not do anything to
$\phi$;

\item If $y<x-1$, then in the long cycle $\phi^{\bullet}$ we replace $x$ by
$y+1$ and replace each $t=y+1,\ldots,x-1$ by $t+1$. In other words, the $x--y$
cyclic operation changes $\phi^{\bullet}$ to
\[
(y+1, y+2,\ldots, x-1, x)^{-1}\cdot\phi^{\bullet}\cdot(y+1, y+2,\ldots, x-1,
x)={\phi^{\bullet}}^{(y+1, y+2,\ldots, x-1, x)}.
\]

\end{itemize}
\end{definition}

Since we can easily restore any permutation $\theta\in S_{n}$ from its
corresponding long cycle $\theta^{\bullet}\in S(1+n)$, Definition
\ref{cyclic-cdot} unambiguously describes what an $x--y$ cyclic operation does
to a permutation $\phi\in S_{n}$. The fact that an $x--y$ cyclic operation
always produces a long cycle in $S(1+n)$, is straightforward from the definition.

The requirement that $\phi^{\bullet}\in S(1+n)$ must contain $(x+1)\rightarrow
y\rightarrow x$, implies that the permutation $\phi^{\circ}=\phi^{\bullet
}\cdot(0,1,\ldots,n)$ has a cycle that contains \newline$(x\mapsto
y)=(x\dashrightarrow x+1 \rightarrow y)$, and a cycle that contains
$(y-1\mapsto x)=(y-1\dashrightarrow y\rightarrow x)$. Thus, $\phi^{\circ}$ has
a cycle, which contains $y-1\mapsto x\mapsto y$.

Let us consider several examples of $x--y$ cyclic operations.

\begin{example}
Let $\phi=\langle6\;\;5\;\;3\;\;1\;\;4\;\;2\rangle$. Then $\phi^{\bullet
}=(0,2,4,1,3,5,6)$. We can perform a $1--4$ cyclic operation on $\phi$ to
obtain a new permutation $\theta$. Since $y=4>x+1=2$, we get $\theta^{\bullet
}=(0,3,4,1,2,5,6)$. Hence, $\theta=\langle6\;\;5\;\;2\;\;1\;\;4\;\;3\rangle$.
\end{example}

\begin{example}
Let $\phi=\langle4\;\;1\;\;5\;\;2\;\;6\;\;3\rangle$. Then $\phi^{\bullet
}=(0,3,6,2,5,1,4)$. We can perform a $5--2$ cyclic operation on $\phi$ to
obtain a new permutation $\theta$. Since $y=2<x=5$, we get $\theta^{\bullet
}=(0,4,6,2,3,1,5)$. Hence, $\theta=\langle5\;\;1\;\;3\;\;2\;\;6\;\;4\rangle$.
\end{example}

\begin{example}
Let $\phi=\langle4\;\;1\;\;5\;\;2\;\;6\;\;3\rangle$. Then $\phi^{\bullet
}=(0,3,6,2,5,1,4)$. We can perform a $0--4$ cyclic operation on $\phi$ to
obtain a new permutation $\theta$. Since $y=4>x+1=1$, we get $\theta^{\bullet
}=(0,2,6,1,5,3,4)$. Hence, $\theta=\langle4\;\;3\;\;5\;\;1\;\;6\;\;2\rangle$.
\end{example}

\begin{example}
Let $\phi=\langle4\;\;1\;\;5\;\;2\;\;6\;\;3\rangle$. Then $\phi^{\bullet
}=(0,3,6,2,5,1,4)$. We can perform a $6--3$ cyclic operation on $\phi$ to
obtain a new permutation $\theta$. Since $y=3<x=6$, we get $\theta^{\bullet
}=(0,3,4,2,6,1,5)$. Hence, $\theta=\langle4\;\;3\;\;5\;\;1\;\;6\;\;2\rangle$.
\end{example}

\begin{example}
Let $\phi=\langle4\;\;1\;\;5\;\;2\;\;6\;\;3\rangle$. Then $\phi^{\bullet
}=(0,3,6,2,5,1,4)$. We can perform a $3--0$ cyclic operation on $\phi$ to
obtain a new permutation $\theta$. Since $y=0<x=3$, we get $\theta^{\bullet
}=(0,1,6,3,5,2,4)$. Hence, $\theta=\langle4\;\;2\;\;5\;\;3\;\;6\;\;1\rangle$.
\end{example}

We now describe the transformation of $\phi^{\circ}$ under an $x--y$ cyclic
operation. First, write $\phi^{\circ}$ in the cyclic notation. Let
$\phi^{\circ}$ consist of $k$ cycles $C_{1},\ldots,C_{k}$ of lengths
$h_{1},\ldots,h_{k}$, respectively. We think of these cycles as consisting of
boxes
\[
C_{1}=B_{1,1}\mapsto B_{1,2}\mapsto\cdots B_{1,h_{1}}\mapsto B_{1,1}
,\ldots,C_{k}=B_{k,1}\mapsto B_{k,2}\mapsto\cdots B_{k,h_{k}}\mapsto B_{k,1}.
\]
Each box in each cycle contains inside it one element of $\phi^{\circ}$. Let
$B_{k(z),h(z)}$ denotes the box that contains it for every element $z\in
\phi^{\circ}$. The requirement that $\phi^{\bullet}$ contains
$(x+1)\rightarrow y\rightarrow x$, asserts that $k(y-1)=k(x)=k(y)$ and
$h(y-1)+2=h(x)+1=h(y)$. Let $|B_{i,j}|$ denote its content for each box
$B_{i,j}$. We now fix the labeling of the boxes and start transforming their
contents. At any stage of the transformation, we permit the boxes to contain a
single element, two elements $z_{1}\mapsto z_{2}$ with an arrow between them,
or no elements. The last case, namely that of a box with no elements in it, we
permit only in a cycle in which at least one of its remaining boxes is not
empty. When we read a cycle, we treat an empty box as if it, together with the
arrow following it, are deleted. Thus, we regard a cycle containing an empty
box as if the arrow $\mapsto$ goes directly from the content of the first
nonempty box before the empty one, to the content of the first nonempty box
following the empty one.

\begin{lemma}
\label{howcyclicworks} Let $\theta\in S_{n}$ be obtained from $\phi\in S_{n}$
by an $x--y$ cyclic operation. Then the $x--y$ cyclic operation transforms
$\phi^{\circ}$ to $\theta^{\circ}$ as follows

\begin{itemize}
\item If $y=x+2$ or $y=x-1$, then $\theta^{\circ}=\phi^{\circ}$;

\item If $y>x+2$, then perform the following steps

\begin{enumerate}
\item Inside the box $B_{k(x+1),h(x+1)}$ replace $x+1$ by $y-1\mapsto x$. In
other words, in the cycle $C_{k(x+1)}$, the piece $|B_{k(x+1),h(x+1)-1}
|\mapsto x+1 \mapsto|B_{k(x+1),h(x+1)+1}|$ becomes $|B_{k(x+1),h(x+1)-1}
|\mapsto y-1\mapsto x \mapsto|B_{k(x+1),h(x+1)+1}|$;

\item Inside each box $B_{k(t),h(t)}$, for all $t=x+2,\ldots,y-1$, replace $t
$ by $t-1$;

\item Delete the element $x$ from the box $B_{k(x),h(x)}$. The box
$B_{k(x),h(x)}$ is now empty. Notice that the box before $B_{k(x),h(x)}$ is
$B_{k(y-1),h(y-1)}$, and it now contains $y-2$. The box after $B_{k(x),h(x)}$
is $B_{k(y),h(y)}$, and it still contains $y$. Thus, we obtain $y-2\mapsto y$
in the cycle $C_{k(x)}$.
\end{enumerate}

\item If $y<x-1$, then perform the following steps

\begin{enumerate}
\item Inside the box $B_{k(x-1),h(x-1)}$ replace $x-1$ by $x\mapsto y$. In
other words, in the cycle $C_{k(x-1)}$, the piece $|B_{k(x-1),h(x-1)-1}
|\mapsto x-1 \mapsto|B_{k(x-1),h(x-1)+1}|$ becomes $|B_{k(x-1),h(x-1)-1}
|\mapsto x\mapsto y \mapsto|B_{k(x-1),h(x-1)+1}|$;

\item Inside each box $B_{k(t),h(t)}$, for all $t=y,\ldots,x-2$, replace $t$
by $t+1$;

\item Delete the element $x$ from the box $B_{k(x),h(x)}$. The box
$B_{k(x),h(x)}$ is now empty. Notice that the box before $B_{k(x),h(x)}$ is
$B_{k(y-1),h(y-1)}$, and it still contains $y-1$. The box after $B_{k(x),h(x)}
$ is $B_{k(y),h(y)}$, and it now contains $y+1$. Thus, we obtain $y-1\mapsto
y+1$ in the cycle $C_{k(x)}$.
\end{enumerate}
\end{itemize}

In particular, the number of cycles in the cyclic decompositions of
$\theta^{\circ}$ and of $\phi^{\circ}$ is the same.
\end{lemma}

\begin{proof}
We start by investigating the effect of replacements of elements in
$\phi^{\bullet}$ on $\phi^{\circ}$. First, notice that when in a piece
$c\rightarrow a\rightarrow d$ we replace an element $a$ by an element $b$, $b$
replaces $a$ in two black arrows $-$ in the beginning of the black arrow
$a\rightarrow d$, and also the end of the black arrow $c\rightarrow a$. We
study these two replacements separately.

\begin{itemize}
\item The replacement of $a$ by $b$ in the end of the black arrow $\rightarrow
a$ transforms $(c-1)\dashrightarrow c\rightarrow a$, which, in $\phi^{\circ}$,
is the arrow $(c-1)\mapsto a$, to $(c-1)\dashrightarrow c\rightarrow b$, which
is $(c-1)\mapsto b$. To indicate that $b$ element of $\phi^{\circ}$ is post
the replacement of $a$ by $b$ in $\rightarrow a$, we mark it as $\acute{b}$.
Thus, we say that the replacement of $c\rightarrow a$ by $c\rightarrow
\acute{b}$ transforms $(c-1)\dashrightarrow c\rightarrow a$, which is
$(c-1)\mapsto a$ to $(c-1)\dashrightarrow c\rightarrow\acute{b}$, which is
$(c-1)\mapsto\acute{b}$. From $\acute{b}$ we draw a grey arrow $\acute
{b}\dashrightarrow(b+1)$. If, at this point, the original element $b$ of
$\phi^{\bullet}$ is still not replaced in $\rightarrow b$, we regard that
original $b$ as deleted, and do not use it in any further replacements,
marking, or arrow-drawing, except the future replacement of $b$ in
$\rightarrow b$, which eliminates that original $b$;

\item The replacement of $a$ by $b$ in the beginning of the black arrow
$a\rightarrow$ transforms $(a-1)\dashrightarrow a\rightarrow d$, which, in
$\phi^{\circ}$, is the arrow $(a-1)\mapsto d$, to $(b-1)\dashrightarrow
b\rightarrow d$, which is $(b-1)\mapsto d$. To indicate that $b$ element of
$\phi^{\circ}$ is post the replacement of $a$ by $b$ in $a\rightarrow$, we
mark it as $\ddot{b}$. Since this replacement replaces $(a-1)$ in
$(a-1)\mapsto$ of $\phi^{\circ}$ by $(b-1)$, we also mark $(b-1)$ as
$\grave{(b-1)}$. Thus, we say that the replacement of $a\rightarrow d$ by
$\ddot{b}\rightarrow d$ transforms $(a-1)\dashrightarrow a\rightarrow d$,
which is $(a-1)\mapsto d$, to $\grave{(b-1)}\dashrightarrow\ddot{b}\rightarrow
d$, which is $\grave{(b-1)}\mapsto d$. If, at this point, the original element
$b $ of $\phi^{\bullet}$ is still not replaced in $b\rightarrow$, we regard
that original $b$ as deleted, and do not use it in any further replacements,
marking, or arrow-drawing, except the future replacement of $b$ in
$b\rightarrow$, which eliminates that original $b$;

\item If we need to mark $b$ as both $\acute{b}$ and $\grave{b}$, we write
$\hat{b}$;

\item If we need to mark $b$ as both $\acute{b}$ and $\ddot{b}$, we write
$\vec{b}$;

\item If we need to mark $b$ as both $\grave{b}$ and $\ddot{b}$, we write
$\tilde{b}$;

\item If we need to mark $b$ as $\acute{b}$ and $\grave{b}$ and $\ddot{b}$, we
write $\check{b}$.
\end{itemize}

Notice that our notation permits us to study the effect of replacements of
elements in $\phi^{\bullet}$ on $\phi^{\circ}$ in several steps. Namely, if we
have to replace elements $a_{1},\ldots,a_{m}$ by elements $b_{1},\ldots,b_{m}
$, we do not have to perform all the $2m$ replacements in the black arrows at
once. Instead, we can perform these $2m$ replacements in several steps, each
time marking the elements as described above. The final $\phi^{\circ}$, after
we perform all the $2m$ replacements, will be the same, regardless of the
selection of intermediate steps. Now we are ready to start our investigation

If $y>x+2$, then the $x--y$ cyclic operation, applied to $\phi^{\bullet}$,
replaces $x+1$ by $y-1$, and replaces each $t$, for $t=x+2,\ldots,y-1$, by
$t-1$. Thus, $y\rightarrow x$ remains untouched by the $x--y$ cyclic
operation. This implies that $\theta^{\circ}$ contains $y-1\mapsto x$. Notice
that our marking notation implies that after all the replacements in
$\phi^{\bullet}$, $\phi^{\bullet}$ will contain $\grave{x}$ instead of $x$ and
$\check{t}$ instead of $t$, for all $t=x+1,\ldots,y-2$, and $\vec{(y-1)}$
instead of $(y-1)$. Altogether, we need to perform $2(y-x-1)$ replacements in
the black arrows of $\phi^{\bullet}$.

\textbf{At the first step}, we perform the following four replacements

\begin{enumerate}
\item Replacement of $(x+2)$ by $\ddot{(x+1)}$ in the black arrow
$(x+2)\rightarrow$. This changes $x$ to $\grave{x}$;

\item Replacement of $(x+1)$ by $\vec{(y-1)}$ in the black arrows
$\rightarrow(x+1)$ and $(x+1)\rightarrow$. This changes $(y-2)$ to
$\grave{(y-2)}$;

\item Replacement of $(y-1)$ by $\hat{(y-2)}$ in the arrow $\rightarrow(y-1)$.
\end{enumerate}

If $\phi^{\circ}$ contains $(x+1)\mapsto(y-1)$, then, according to our
notation, the original $\phi^{\bullet}$ takes $u=|B_{k(x+1),h(x+1)-1}|+1$ to
$x+1$. Indeed, in the original $\phi^{\circ}$ we must have an alternating
path
\begin{equation}
\label{HCW.case1}(u-1)\dashrightarrow u\rightarrow(x+1)\dashrightarrow
(x+2)\rightarrow(y-1)\dashrightarrow y\rightarrow x\dashrightarrow
(x+1)\rightarrow y,
\end{equation}
which is
\[
(u-1)\mapsto(x+1)\mapsto(y-1)\mapsto x\mapsto y.
\]


The four replacements of our first step transform Equation \ref{HCW.case1} to
\begin{equation}
(u-1)\dashrightarrow u\rightarrow\vec{(y-1)}\dashrightarrow y\rightarrow
\grave{x}\dashrightarrow\ddot{(x+1)}\rightarrow\hat{(y-2)}\dashrightarrow
\vec{(y-1)}\rightarrow y,\label{HCW.case1.new}
\end{equation}
which is
\[
(u-1)\mapsto\vec{(y-1)}\mapsto\grave{x}\mapsto\hat{(y-2)}\mapsto y.
\]
Notice that all four replacements in the black arrows appear in path
\ref{HCW.case1.new}. Thus, these four replacements correspond to the
replacement of $x+1$ by $\vec{(y-1)}\mapsto\grave{x}$ inside the box
$B_{k(x+1),h(x+1)}$, deletion of $x$ from the box $B_{k(x),h(x)}$, and
replacement of $y-1$ by $\hat{(y-2)}$ in the box $B_{k(y-1),h(y-1)}$.

If $\phi^{\circ}$ does not contain $(x+1)\mapsto(y-1)$ then, according to our
notation, the original $\phi^{\bullet}$ takes $u=\left\vert
B_{k(x+1),h(x+1)-1}\right\vert +1$ to $x+1$, takes $x+2$ to
$v=|B_{k(x+1),h(x+1)+1}|$, and takes $p=\left\vert B_{k(y-1),h(y-1)-1}
+1\right\vert $ to $(y-1)$. Indeed, in the original $\phi^{\circ}$ we must
have an alternating path
\begin{equation}
(u-1)\dashrightarrow u\rightarrow(x+1)\dashrightarrow(x+2)\rightarrow
v,\label{HCW.case1.1}
\end{equation}
which is
\[
(u-1)\mapsto(x+1)\mapsto v,
\]
and an alternative path
\begin{equation}
(p-1)\dashrightarrow p\rightarrow\rightarrow(y-1)\dashrightarrow y\rightarrow
x\dashrightarrow(x+1)\rightarrow y,\label{HCW.case1.2}
\end{equation}
which is
\[
(p-1)\mapsto(y-1)\mapsto x\mapsto y.
\]


The four replacements of the first step transform path \ref{HCW.case1.1} to
\begin{equation}
(u-1)\dashrightarrow u\rightarrow\vec{(y-1)}\dashrightarrow y\rightarrow
\grave{x}\dashrightarrow\ddot{(x+1)}\rightarrow v,\label{HCW.case1.1.new}
\end{equation}
which is
\[
(u-1)\mapsto\vec{(y-1)}\mapsto\grave{x}\mapsto v,
\]
and transforms path \ref{HCW.case1.2} to
\begin{equation}
(p-1)\dashrightarrow p\rightarrow\hat{(y-2)}\dashrightarrow\vec{(y-1)}
\rightarrow y,\label{HCW.case1.2.new}
\end{equation}
which is
\[
(p-1)\mapsto\hat{(y-2)}\mapsto y.
\]
Notice that all four replacements in the black arrows appear in paths
\ref{HCW.case1.1.new} and \ref{HCW.case1.2.new}. Thus, these four replacements
correspond to the replacement of $x+1$ by $\vec{y-1}\mapsto\grave{x}$ inside
the box $B_{k(x+1),h(x+1)}$, deletion of $x$ from the box $B_{k(x),h(x)}$, and
replacement of $y-1$ by $\hat{(y-2)}$ in the box $B_{k(y-1),h(y-1)}$.

\textbf{At the second step}, we perform the following two replacements

\begin{enumerate}
\item Replacement of $(x+2)$ by $\vec{(x+1)}$ in the black arrow
$\rightarrow(x+2)$;

\item Replacement of $(x+3)$ by $\ddot{(x+2)}$ in the black arrow
$(x+3)\rightarrow$. This changes $\vec{(x+1)}$ to $\check{(x+1)}$;
\end{enumerate}

According to our notation, $\phi^{\bullet}$, modified by the first step, takes
\newline$u=|B_{k(x+2),h(x+2)-1}|+1$ to $x+2$ and takes $x+2$ to
$v=|B_{k(x+2),h(x+2)+1}|$.\newline Indeed, after the first step, in
$\phi^{\circ}$ we must have an alternating path
\begin{equation}
\label{HCW.case2}(u-1)\dashrightarrow u\rightarrow(x+2)\dashrightarrow
(x+3)\rightarrow v,
\end{equation}
which is
\[
(u-1)\mapsto(x+2)\mapsto v.
\]


The two replacements of the second step transform path \ref{HCW.case2} to
\begin{equation}
(u-1)\dashrightarrow u\rightarrow\check{(x+1)}\dashrightarrow\ddot
{(x+2)}\rightarrow v,\label{HCW.case2.new}
\end{equation}
which is
\[
(u-1)\mapsto\check{(x+1)}\mapsto v.
\]
Notice that both replacements in the black arrows appear in path
\ref{HCW.case2.new}. Thus, these two replacements correspond to the
replacement of $x+2$ by $\check{(x+1)}$ inside the box $B_{k(x+2),h(x+2)}$.

\textbf{At the third step}, we perform the following two replacements

\begin{enumerate}
\item Replacement of $(x+3)$ by $\vec{(x+2)}$ in the black arrow
$\rightarrow(x+3)$;

\item Replacement of $(x+4)$ by $\ddot{(x+3)}$ in the black arrow
$(x+4)\rightarrow$. This changes $\vec{(x+2)}$ to $\check{(x+2)}$;
\end{enumerate}

According to our notation, $\phi^{\bullet}$, modified by the first and second
steps, takes \\ $u=|B_{k(x+3),h(x+3)-1}|+1$ to $x+3$ and takes $x+3$ to
$v=|B_{k(x+3),h(x+3)+1}|$. Indeed, after the second step, in $\phi^{\circ}$ we
must have an alternating path
\begin{equation}
\label{HCW.case3}(u-1)\dashrightarrow u\rightarrow(x+3)\dashrightarrow
(x+4)\rightarrow v,
\end{equation}
which is
\[
(u-1)\mapsto(x+3)\mapsto v.
\]


The two replacements of the third step transform path \ref{HCW.case3} to
\begin{equation}
(u-1)\dashrightarrow u\rightarrow\check{(x+2)}\dashrightarrow\ddot
{(x+3)}\rightarrow v,\label{HCW.case3.new}
\end{equation}
which is
\[
(u-1)\mapsto\check{(x+2)}\mapsto v.
\]
Notice that both replacements in the black arrows appear in path
\ref{HCW.case3.new}. Thus, these two replacements correspond to the
replacement of $x+3$ by $\check{(x+2)}$ inside the box $B_{k(x+3),h(x+3)}$.

We continue that way until \textbf{at the last step} we perform the following
two replacements

\begin{enumerate}
\item Replacement of $\grave{(y-2)}$ by $\vec{(y-3)}$ in the black arrow
$\rightarrow(y-2)$;

\item Replacement of $(y-1)$ by $\check{(y-2)}$ in the black arrow
$(y-1)\rightarrow$. This changes $\vec{(y-3)}$ to $\check{y-3)}$;
\end{enumerate}

According to our notation, $\phi^{\bullet}$, modified by all the previous
steps, takes \newline$u=|B_{k(y-2),h(y-2)-1}|+1$ to $\grave{(y-2)}$ and takes
$y-1$ to $v=|B_{k(y-2),h(y-2)+1}|$. Indeed, after the previous step, in
$\phi^{\circ}$ we must have an alternating path
\begin{equation}
\label{HCW.case.last}(u-1)\dashrightarrow u\rightarrow\grave{(y-2)}
\dashrightarrow(y-1)\rightarrow v,
\end{equation}
which is
\[
(u-1)\mapsto\grave{(y-2)}\mapsto v.
\]


The two replacements of the last step transform path \ref{HCW.case.last} to
\begin{equation}
(u-1)\dashrightarrow u\rightarrow\check{(y-3)}\dashrightarrow\check
{(y-2)}\rightarrow v,\label{HCW.case.last.new}
\end{equation}
which is
\[
(u-1)\mapsto\check{(y-3)}\mapsto v.
\]
Notice that both replacements in the black arrows appear in path
\ref{HCW.case.last.new}. Thus, these two replacements correspond to the
replacement of $\grave{y-2}$ by $\check{y-3}$ inside the box \newline
$B_{k(y-2),h(y-2)}$, and to change of $\hat{(y-2)}$ in the box
$B_{k(y-1),h(y-1)}$ to $\check{(y-2)}$.

At this point, we performed all the $2(y-x-1)$ replacements in the black
arrows of $\phi^{\bullet}$. Our marking notation makes it easy to verify that
all the required replacements in $\phi^{\bullet}$ were performed correctly.
Thus the lemma is proved for $y>x+2$. The proof for $y<x-1$ is done in a
similar way, by using the same marking notation and performing the
replacements in steps.
\end{proof}

\begin{definition}
\label{cyclic.orbit.def} We say that the permutations $\phi,\theta\in S_{n}$
are in the same ``$x--y$ cyclic orbit" if there exist some permutations
$\tau_{1},\ldots,\tau_{k}\in S_{n}$ such that $\tau_{1}=\phi$, $\tau
_{k}=\theta$, and, for each $i=1,\ldots,k-1$, either $\tau_{i}$ can be
obtained from $\tau_{i+1}$ by an $x--y$ cyclic operation or $\tau_{i+1}$ can
be obtained from $\tau_{i}$ by an $x--y$ cyclic operation.
\end{definition}

Notice that according to Definition \ref{cyclic.orbit.def}, $\phi,\theta\in
S_{n}$ can be in the same $x--y$ exchange orbit, while neither of them can be
obtained from the other one by performing $x--y$ cyclic operations.

\begin{theorem}
\label{cyclic.operation.keeps.prob} Let $\phi,\theta\in S_{n}$ be two
permutations such that $\theta$ is obtained from $\phi$ by an $x--y$ cyclic
operation. Then
\[
\Pr(a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
)=\Pr(a_{1}a_{2}\cdots a_{n}=a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}
}).
\]

\end{theorem}

\begin{proof}
We consider four different possible cases, and prove the theorem for each of them

\textbf{Case 1} is when $x\neq0,n$ and $y\neq0$. In this case, there exists
some $k$, $1\leq k\leq n-2$, such that $\phi_{k}=x$, $\phi_{k+1}=y$, and
$\phi_{k+2}=x+1$. Hence, the equation
\[
a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
\]
is of the form
\begin{equation}
a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{k-1}}a_{x}
a_{y}a_{x+1}a_{\phi_{k+3}}\cdots a_{\phi_{n}}\label{cyclic.first}
\end{equation}


If $y>x$, then Equation \ref{cyclic.first} is equivalent to
\begin{equation}
a_{1}\cdots(a_{x}a_{x+1})\cdots a_{y}\cdots a_{n}=a_{\phi_{1}}\cdots
a_{\phi_{k-1}}(a_{x}a_{x+1})(a_{x+1}^{-1}a_{y}a_{x+1})a_{\phi_{k+3}}\cdots
a_{\phi_{n}}.\label{cyclic.first.case1}
\end{equation}
We define

\begin{itemize}
\item $b_{t}=a_{t}$ for all $t<x$ and $t>y$;

\item $b_{x}=a_{x}a_{x+1}$;

\item $b_{t}=a_{t+1}$ for all $x+1<t<y-1$;

\item $b_{y-1}=a_{x+1}$;

\item $b_{y}=a_{x+1}^{-1}a_{y}$.
\end{itemize}

Next, $b_{y-1}=a_{x+1}$ and $b_{y}=a_{x+1}^{-1}a_{y}$ imply

\begin{itemize}
\item $b_{y-1}b_{y}=a_{y}$;

\item $b_{y}b_{y-1}=a_{x+1}^{-1}a_{y}a_{x+1}$.
\end{itemize}

As random variables $a_{1},\ldots,a_{n}$ run over all elements of $G$, so do
random elements $b_{1},\ldots,b_{n}$. Now, the Equation
\ref{cyclic.first.case1} is equivalent to the equation
\begin{equation}
\label{cyclic.first.case1.2}b_{1}b_{2}\cdots b_{n}=b_{\theta_{1}}b_{\theta
_{2}}\cdots b_{\theta_{k-1}}b_{x}b_{y}b_{y-1}b_{\theta_{k+3}}\cdots
b_{\theta_{n}},
\end{equation}
where

\begin{itemize}
\item $\theta_{t}=\phi_{t}$ for all such $t$, for which $1\leq\phi_{t}\leq x$ or
$y\leq\phi_{t}\leq n$;

\item $\theta_{t}=y-1$ for the $t$, for which $\phi_{t}=x+1$;

\item $\theta_{t}=\phi_{t}-1$ for all such $t$, for which $x+1<\phi_{t}<y$.
\end{itemize}

This proves the theorem for the subcase $y>x$ of the first case.

If $y<x$, then Equation \ref{cyclic.first} is equivalent to
\begin{equation}
a_{1}\cdots a_{y}\cdots(a_{x}a_{x+1})\cdots a_{n}=a_{\phi_{1}}\cdots
a_{\phi_{k-1}}(a_{x}a_{y}a_{x}^{-1})(a_{x}a_{x+1})a_{\phi_{k+3}}\cdots
a_{\phi_{n}}.\label{cyclic.first.case2}
\end{equation}
We define

\begin{itemize}
\item $b_{t}=a_{t}$ for all $t<y$ and $t>x+1$;

\item $b_{x+1}=a_{x}a_{x+1}$;

\item $b_{t}=a_{t-1}$ for all $y+1<t<x$;

\item $b_{y+1}=a_{x}$;

\item $b_{y}=a_{y}a_{x+1}^{-1}$.
\end{itemize}

Next, $b_{y+1}=a_{x}$ and $b_{y}=a_{y}a_{x+1}^{-1}$ imply

\begin{itemize}
\item $b_{y}b_{y+1}=a_{y}$;

\item $b_{y+1}b_{y}=a_{x}a_{y}a_{x}^{-1}$.
\end{itemize}

As random variables $a_{1},\ldots,a_{n}$ run over all elements of $G$, so do
random elements $b_{1},\ldots,b_{n}$. Now, Equation \ref{cyclic.first.case2}
is equivalent to the equation
\begin{equation}
b_{1}b_{2}\cdots b_{n}=b_{\theta_{1}}b_{\theta_{2}}\cdots b_{\theta_{k-1}
}b_{y+1}b_{y}b_{x+1}b_{\theta_{k+3}}\cdots b_{\theta_{n}}
,\label{cyclic.first.case2.2}
\end{equation}
where

\begin{itemize}
\item $\theta_{t}=\phi_{t}$ for all such $t$, for which $1\leq\phi_{t}\leq x$ or
$x+1\leq\phi_{t}\leq n$;

\item $\theta_{t}=y+1$ for the $t$, for which $\phi_{t}=x$;

\item $\theta_{t}=\phi_{t}+1$ for all such $t$, for which $y<\phi_{t}<x$.
\end{itemize}

This proves the theorem for the subcase $y<x$ of the first case.

\textbf{Case 2} is when $x=0=\phi_{0}$. In this case, $\phi_{1}=y$ and
$\phi_{2}=1$. Hence, the equation
\[
a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
\]
is of the form
\begin{equation}
a_{1}a_{2}\cdots a_{n}=a_{y}a_{1}a_{\phi_{3}}\cdots a_{\phi_{n}}
\label{cyclic.second}
\end{equation}
Multiplying Equation \ref{cyclic.second} from the left by $a_{1}^{-1}$ gives
us
\begin{equation}
a_{2}\cdots a_{n}=(a_{1}^{-1}a_{y}a_{1})a_{\phi_{3}}\cdots a_{\phi_{n}
}\label{cyclic.second1}
\end{equation}
We define

\begin{itemize}
\item $b_{t}=a_{t}$ for all $t>y$;

\item $b_{t}=a_{t+1}$ for all $1\leq t<y-1$;

\item $b_{y-1}=a_{1}$;

\item $b_{y}=a_{1}^{-1}a_{y}$.
\end{itemize}

Next, $b_{y-1}=a_{1}$ and $b_{y}=a_{1}^{-1}a_{y}$ imply

\begin{itemize}
\item $b_{y-1}b_{y}=a_{y}$;

\item $b_{y}b_{y-1}=a_{1}^{-1}a_{y}a_{1}$.
\end{itemize}

As random variables $a_{1},\ldots,a_{n}$ run over all elements of $G$, so do
random elements $b_{1},\ldots,b_{n}$.

Now, Equation \ref{cyclic.second1} is equivalent to the equation
\begin{equation}
b_{1}\cdots b_{n}=b_{y}b_{y-1}b_{\theta_{3}}\cdots b_{\theta_{n}
},\label{cyclic.second2}
\end{equation}
where

\begin{itemize}
\item $\theta_{t}=\phi_{t}$ for all such $t$, for which $\phi_{t}\geq y$;

\item $\theta_{t}=y-1$ for the $t$, for which $\phi_{t}=1$;

\item $\theta_{t}=\phi_{t}-1$ for all such $t$, for which $2\leq\phi_{t}\leq
y-1$.
\end{itemize}

This proves the theorem for the second case.

\textbf{Case 3} is when $x=n$. In this case, $x+1=0=\phi_{0}$, $\phi_{n}=y$
and $\phi_{n-1}=x=n$. Hence, the equation
\[
a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
\]
is of the form
\begin{equation}
a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}\cdots a_{\phi_{n-2}}a_{n}a_{y}
\label{cyclic.third}
\end{equation}
We apply the inverse map $inv(g)=g^{-1}$ to both sides of Equation
\ref{cyclic.third} and obtain
\begin{equation}
a_{n}^{-1}a_{n-1}^{-1}\cdots a_{1}^{-1}=a_{y}^{-1}a_{n}^{-1}a_{\phi_{n-2}
}^{-1}\cdots a_{\phi_{1}}^{-1}\label{cyclic.third.inv1}
\end{equation}
Define $c_{n+1-i}=a_{i}^{-1}$ and $\phi_{i}^{\prime}=n+1-\phi_{n+1-i}$, for
all $i=1,\ldots,n$. Define $x^{\prime}=0$ and $y^{\prime}=n+1-y$. Then
Equation \ref{cyclic.third.inv1} becomes
\begin{equation}
c_{1}c_{2}\cdots c_{n}=c_{\phi_{1}^{\prime}}c_{\phi_{2}^{\prime}}\cdots
c_{\phi_{n}^{\prime}},\label{cyclic.third.inv2}
\end{equation}
in which $\phi_{1}^{\prime}=y^{\prime}$ and $\phi_{2}^{\prime}=1$. We apply
$x^{\prime}--y^{\prime}$ cyclic operation to $\phi^{\prime}$. In the study of
Case 2, above, we showed that Equation \ref{cyclic.third.inv2} is equivalent
to the equation
\begin{equation}
b_{1}\cdots b_{n}=b_{y^{\prime}}b_{y^{\prime}-1}b_{\theta_{3}^{\prime}}\cdots
b_{\theta_{n}^{\prime}},\label{cyclic.third.inv3}
\end{equation}
where

\begin{itemize}
\item $\theta^{\prime}_{t}=\phi^{\prime}_{t}=n+1-\phi_{n+1-t}$ for all such
$t$, for which $n+1-\phi_{n+1-t}=\phi^{\prime}_{t}\geq y^{\prime}=n+1-y$;

\item $\theta^{\prime}_{t}=y^{\prime}-1=n-y$ for the $t$, for which
$n+1-\phi_{n+1-t}=\phi^{\prime}_{t}=1$;

\item $\theta^{\prime}_{t}=\phi^{\prime}_{t}-1=n-\phi_{n+1-t}$ for all such
$t$, for which $2\leq n+1-\phi_{n+1-t}=\phi^{\prime}_{t}\leq y^{\prime}-1=n-y$.
\end{itemize}

Next, we apply the inverse map $inv(g)=g^{-1}$ to both sides of the Equation
\ref{cyclic.third.inv3} and obtain
\begin{equation}
\label{cyclic.third.inv4}b_{n}^{-1}\cdots b_{1}^{-1}=b_{\theta^{\prime}_{n}
}^{-1}\cdots\theta^{\prime}_{3}{-1}b_{y^{\prime}-1}^{-1}b_{y^{\prime}}^{-1}.
\end{equation}
Define $d_{n+1-i}=b_{i}^{-1}$ and $\theta_{i}=n+1-\theta^{\prime}_{n+1-i}$,
for all $i=1,\ldots,n$. Then the Equation \ref{cyclic.third.inv4} becomes
\begin{equation}
\label{cyclic.third.final}d_{1}\cdots d_{n}=d_{\theta_{1}}b_{\theta_{2}}\cdots
d_{\theta_{n-2}},d_{y-1}d_{y}.
\end{equation}
Here

\begin{itemize}
\item $\theta_{t}=n+1-\theta^{\prime}_{n+1-t}=n+1-\phi^{\prime}_{n+1-t}
=\phi_{t}$ for all such $t$, for which $\phi_{t}=n+1-\phi^{\prime}_{n+1-t}\leq
n+1-y^{\prime}=y$;

\item $\theta_{t}=n+1-\theta^{\prime}_{n+1-t}=n+1-(n-y)=y+1$ the $t$, for
which $\phi_{t}=n+1-\phi^{\prime}_{n+1-t}=n+1-1=n$;

\item $\theta_{t}=n+1-\theta^{\prime}_{n+1-t}=n+1-(\phi^{\prime}
_{n+1-t}-1)=\phi_{t}+1$ for $y+1=n+1-(n-y)\leq\phi_{t}=n+1-\phi^{\prime
}_{n+1-t}\leq n+1-2=n-1$.
\end{itemize}

This proves the theorem for Case 3.

\textbf{Case 4} is when $y=0=\phi_{0}$. In this case, $\phi_{1}=x+1$ and
$\phi_{n}=x$. Hence, the equation
\[
a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
\]
is of the form
\begin{equation}
a_{1}a_{2}\cdots a_{n}=a_{x+1}a_{\phi_{2}}\cdots a_{\phi_{n-1}}a_{x}
\label{cyclic.fourth}
\end{equation}
Multiplying Equation \ref{cyclic.fourth} on the left by $a_{x}$ gives us
\begin{equation}
a_{x}a_{1}a_{2}\cdots a_{x-1}(a_{x}a_{x+1})\cdots a_{n}=(a_{x}a_{x+1}
)a_{\phi_{2}}\cdots a_{\phi_{n-1}}a_{x}\label{cyclic.fourth1}
\end{equation}
We define

\begin{itemize}
\item $b_{t}=a_{t}$ for all $t>x+1$;

\item $b_{x+1}=a_{x}a_{x+1}$

\item $b_{t}=a_{t-1}$ for all $1<t\leq x$;

\item $b_{1}=a_{x}$.
\end{itemize}

As random variables $a_{1},\ldots,a_{n}$ run over all elements of $G$, so do
random elements $b_{1},\ldots,b_{n}$. Finally, the Equation
\ref{cyclic.fourth1} is equivalent to the equation
\begin{equation}
\label{cyclic.fourth2}b_{1}\cdots b_{n}=b_{x+1}b_{\theta_{2}}\cdots
b_{\theta_{n-1}}b_{1},
\end{equation}
where

\begin{itemize}
\item $\theta_{t}=\phi_{t}$ for all such $t$, for which $\phi_{t}>x$;

\item $\theta_{t}=1$ for the $t$, for which $\phi_{t}=x$;

\item $\theta_{t}=\phi_{t}+1$ for all such $t$, for which $1\leq\phi_{t}<x$.
\end{itemize}

This proves our theorem for Case 4.
\end{proof}

\subsection{Main results}

\begin{definition}
\label{xy.equiv.def} Two permutations $\phi,\theta\in S_{n}$ are called
\textquotedblleft$x--y$ equivalent" if there exist some permutations
$\phi=\tau_{1},\ldots,\theta=\tau_{k}\in S_{n}$ such that $\tau_{i}$ and
$\tau_{i+1}$, for each \newline$i=1,\ldots,k-1$, are in the same $x--y$
exchange orbit or in the same $x--y$ cyclic orbit.
\end{definition}

\begin{theorem}
\label{equiv-alternating} If $\theta$ and $\phi$ are $x--y$ equivalent, then
$\Gr(\phi)$ and $\Gr(\theta)$ have the same number of alternating cycles.
\end{theorem}

\begin{proof}
Since $\theta$ and $\phi$ are $x--y$ equivalent, there exist some permutations
$\phi=\tau_{1},\ldots,\theta=\tau_{k}\in S_{n}$ such that $\tau_{i}$ and
$\tau_{i+1}$, for each $i=1,\ldots,k-1$, are in the same $x--y$ exchange orbit
or in the same $x--y$ cyclic orbit. For each $t=1,\ldots,k-1$, if $\tau_{i}$
and $\tau_{i+1}$ are in the same $x--y$ exchange orbit, then, by Lemma
\ref{exchange.same.num.cycles}, $\Gr(\tau_{i})$ and $\Gr(\tau_{i+1})$ have the
same number of alternating cycles. Else, if $\tau_{i}$ and $\tau_{i+1}$ are in
the same $x--y$ cyclic orbit, then, by Lemma \ref{exchange.same.num.cycles},
$\tau_{i}^{\circ}$ and $\tau_{i+1}^{\circ}$ have the same number of cycles in
their cyclic decompositions. Now, Theorem \ref{Theorem.8} asserts, that
$\Gr(\tau_{i})$ and $\Gr(\tau_{i+1})$ have the same number of alternating
cycles. Hence, $\Gr(\phi)$ and $\Gr(\theta)$ have the same number of
alternating cycles.
\end{proof}

\begin{theorem}
\label{equivalent.keeps.prob} If $\theta$ and $\phi$ are $x--y$ equivalent,
then
\[
\Pr(a_{1}a_{2}\cdots a_{n}=a_{\phi_{1}}a_{\phi_{2}}\cdots a_{\phi_{n}}
)=\Pr(a_{1}a_{2}\cdots a_{n}=a_{\theta_{1}}a_{\theta_{2}}\cdots a_{\theta_{n}
}).
\]

\end{theorem}

\begin{proof}
Since $\theta$ and $\phi$ are $x--y$ equivalent, there exist some permutations
$\phi=\tau_{1},\ldots,\theta=\tau_{k}\in S_{n}$ such that $\tau_{i}$ and
$\tau_{i+1}$, for each $i=1,\ldots,k-1$, are in the same $x--y$ exchange orbit
or in the same $x--y$ cyclic orbit. For each $t=1,\ldots,k-1$, if $\tau_{i}$
and $\tau_{i+1}$ are in the same $x--y$ exchange orbit, then, by Theorem
\ref{exchange.operation.keeps.prob},\newline$\Pr_{\tau_{i}}(G)=\Pr_{\tau
_{i+1}}(G)$. Else, if $\tau_{i}$ and $\tau_{i+1}$ are in the same $x--y$
cyclic orbit, then, by Theorem \ref{cyclic.operation.keeps.prob}, $\Pr
_{\tau_{i}}(G)=\Pr_{\tau_{i+1}}(G)$.
\end{proof}

At this point, we proceed to show that in a finite non-Abelian group $G$ two
permutation equalities have the same probability if, and only if, their
permutations have the same number of alternating cycles. The \textquotedblleft
only if" part implies that every finite non-Abelian group $G$ is generic. This
part immediately follows from a stronger result, stated in Theorem 6.8 due to
Das and Nath \cite{DasNath3}.

\begin{theorem}
[Theorem 6.8 of Das and Nath]\label{DasNash}For any finite non-Abelian group
$G$, \\ $\Pr^{2n+2}(G)<\Pr^{2n}(G)$.
\end{theorem}

\begin{theorem}
\label{generic.group} Every finite non-Abelian group is generic.
\end{theorem}

\begin{proof}
Let $\phi\in S_{n}$ have $k$ alternating cycles in its cycle graph $\Gr(\phi
)$, and $\theta\in S_{n}$ have $t$ alternating cycles in its cycle graph
$\Gr(\theta)$. Then, by Theorem \ref{main.theorem.1}, $\Pr_{\phi}(G)=\Pr
^{2k}(G) $ and $\Pr_{\theta}(G)=\Pr^{2t}(G)$. Thus, by Theorem \ref{DasNash},
$\Pr_{\phi}(G)=\Pr_{\theta}(G)$ only if $k=t$.
\end{proof}

We illustrate Theorem \ref{generic.group} by the following example, which is a
generalization of Example \ref{d4q8.four}.

\begin{example}
\label{d4q8.general} Let the group $G$ be $D_{8}$ or $Q_{8}$. Then
\[
\Pr(a_{1}a_{2}a_{3}a_{4}\cdots a_{2k-1}a_{2k}a_{2k+1}a_{2k+2}\cdots
a_{2n}=a_{2}a_{1}a_{4}a_{3}\cdots a_{2k}a_{2k-1}a_{2k+1}a_{2k+2}\cdots a_{n})
\]
is equal to
\begin{equation}
\left( \frac{5}{8}\right) ^{k}+\frac{k!}{2!(k-2)!}\left( \frac{5}{8}\right)
^{k-2}\left( \frac{3}{8}\right) ^{2}+\frac{k!}{4!(k-4)!}\left( \frac{5}
{8}\right) ^{k-4}\left( \frac{3}{8}\right) ^{4}+\ldots.\label{d4q8.formula}
\end{equation}
The last summand in the sum \ref{d4q8.formula} is $\left( \frac{3}{8}\right)
^{k}$, for even $k$, or $\left( \frac{5}{8}\right) k\left( \frac{3}{8}\right)
^{k-1}$, for odd $k$. Indeed, in order for the equation
\[
a_{1}a_{2}a_{3}a_{4}\cdots a_{2k-1}a_{2k}a_{2k+1}a_{2k+2}\cdots a_{n}
=a_{2}a_{1}a_{4}a_{3}\cdots a_{2k}a_{2k-1}a_{2k+1}a_{2k+2}\cdots a_{n}
\]
to hold, an even number of the inverted pairs $a_{j+1}a_{j}$ must be equal to
$ca_{j}a_{j+1}$, where $c$ is the nontrivial element from the center of $G $.
All the other inverted pairs $a_{j+1}a_{j}$ must be equal to $a_{j}a_{j+1} $.
But, for each $2t$ where $0\leq 2t\leq k$, there are $\frac{k!}{(2t)!(k-2t)!}$
different choices of $2t$ inverted pairs, for which $a_{j+1}a_{j}
=ca_{j}a_{j+1}$. Now, $\Pr(a_{j+1}a_{j}=a_{j}a_{j+1})=\frac{5}{8} $ and
$\Pr(a_{j+1}a_{j}=ca_{j}a_{j+1})=1-\frac{5}{8}=\frac{3}{8}$. This justifies
the sum \ref{d4q8.formula}. A direct computation now shows that for different
values of $k$ we get different probabilities for the corresponding permutation equalities.
\end{example}

Next, we prove Theorem \ref{hultman-exchange-cyclic}, which, for even $n$,
asserts the opposite direction of the statement of Theorem
\ref{equiv-alternating}. This, in turn, permits us to prove Theorem
\ref{main.theorem.1}, in which the ``if" part of the above statement is
asserted. In order to prove Theorem \ref{hultman-exchange-cyclic}, we need the
following several technical lemmas.

\begin{definition}
\label{permutation.augment} Let $\phi$ be a permutation in $S_{n}$. Let $i$ be
any nonnegative integer smaller than $n+1$. We define the permutation
$\phi+_{i}2\in S_{n+2}$ as follows

\begin{itemize}
\item $\mu_{t}=\phi_{t}$ for $t=1,\ldots,i$;

\item $\mu_{i+1}=n+2$;

\item $\mu_{i+2}=n+1$;

\item $\mu_{t}=\phi_{t-2}$ for $t=i+3,\ldots,n+2$.
\end{itemize}
\end{definition}

Notice that for $i=n$, our definition implies $\phi+_{i}2=\langle\phi
_{1}\;\ldots\;\phi_{n}\;n+2\;n+1\rangle$, and, for $i=0$, it implies
$\phi+_{i}2=\langle n+2\;n+1\;\phi_{1}\;\ldots\;\phi_{n}\rangle$. Observe that
for all $0\leq i\leq n$,
\[
(\phi+_{i}2)^{\bullet}=(\phi_{i},n+1,n+2)\cdot\phi^{\bullet}=(\phi_{i}
,\phi_{i-1},\ldots,\phi_{0},\phi_{n},\ldots,\phi_{i+1},n+1,n+2).
\]


\begin{lemma}
\label{tech.lem.0} Let $\phi$ be a permutation in $S_{n}$, $i\leq n$ be a
nonnegative integer, and \newline$\mu=\phi+_{i}2\in S_{n+2}$. Then $\Gr(\phi)$
and $\Gr(\mu)$ have the same number of alternating cycles.
\end{lemma}

\begin{proof}
 From $\mu^{\bullet}=(\phi_{i},n+1,n+2)\cdot\phi^{\bullet}$ we obtain
\[
\mu^{\circ}=\mu^{\bullet}\cdot(0,1,\ldots,n,n+1,n+2)=(\phi_{i},n+1,n+2)\cdot
\phi^{\bullet}\cdot(0,n+1,n+2)\cdot(0,1,\ldots,n)
\]
Now, $\phi^{\circ}$ always contains $(\phi_{i+1}-1)\mapsto\phi_{i}$ and
$n\mapsto\phi_{n}$. When $\phi_{i+1}=0=\phi_{0}$, $i=n$ and $\phi_{i+1}-1=n$.
Thus, $(\phi_{i+1}-1)\mapsto\phi_{i}$ is identical to $n\mapsto\phi_{n}$. With
regard to $\mu^{\circ}$, the following holds

\begin{itemize}
\item If $\phi_{i+1}\neq0$ then $\mu^{\circ}$ contains $(\phi_{i+1}
-1)\mapsto(n+1)\mapsto\phi_{i}$ and $n\mapsto(n+2)\mapsto\phi_{n}$. For all
$j\ne\phi_{i+1}-1, n, n+1, and n+2$, the piece $\mu_{j}\mapsto\mu_{k}$ of
$\mu^{\circ}$ is identical to the piece $\phi_{j}\mapsto\phi_{k}$ of
$\phi^{\circ}$;

\item If $\phi_{i+1}=0$ then $\mu^{\circ}$ contains $(\phi_{i+1}
-1)=n\mapsto(n+2)\mapsto(n+1)\mapsto\phi_{i}=\phi_{n}$. For all $j\ne n, n+1,
and n+2$, the piece $\mu_{j}\mapsto\mu_{k}$ of $\mu^{\circ}$ is identical to
the piece $\phi_{j}\mapsto\phi_{k}$ of $\phi^{\circ}$.
\end{itemize}

This shows that $\mu^{\circ}$ and $\phi^{\circ}$ have the same number of
cycles in their cyclic decomposition. Hence, by Theorem \ref{Theorem.8},
$\Gr(\mu)$ and $\Gr(\phi)$ have the same number of alternating cycles.
\end{proof}

\begin{lemma}
\label{tech.lem.0a} Let $\phi$ be a permutation in $S_{n}$. Let $i\leq n$ and
$j\leq n$ be two nonnegative integers. Let $\mu=\phi+_{i}2\in S_{n+2}$ and
$\tau=\phi+_{j}2\in S_{n+2}$. Then the permutations $\tau$ and $\mu$ in
$S_{n+2}$ are $x--y$ equivalent.
\end{lemma}

\begin{proof}
If $i=j$ then $\tau=\mu$ and our lemma trivially follows. If $i\neq j$, we can
assume that $i>j$. Since $\mu^{\bullet}=(\phi_{i},n+1,n+2)\cdot\phi^{\bullet}
$, the $x--y$ exchange operation, where $x=n+1$ and $y=\phi_{i}$, by
Proposition \ref{exchange-product}, produces a permutation $\theta\in S_{n+2}
$, for which
\begin{align*}
\theta^{\bullet} & =(n+1,\phi_{i},\phi_{i-1})\cdot(\phi_{i},n+1,n+2)\cdot
\phi^{\bullet}\\
& =(\phi_{i-1},n+1,n+2)\cdot\phi^{\bullet}=(\phi_{i-1},\phi_{i-2},\ldots
,\phi_{0},\phi_{n},\ldots,\phi_{i},n+1,n+2).
\end{align*}
Thus, consecutively performing on $\mu$ $i-j$ $x--y$ exchange operations, in
which $x=n+1$ and $y=\phi_{i},\phi_{i+1},\ldots,\phi_{j-1}$, produces the
permutation $\tau$.
\end{proof}

\begin{lemma}
\label{tech.lem.1} Let $\phi,\theta$ be $x--y$ equivalent permutations in
$S_{2t}$. Then any two permutations $\mu=\phi+_{i}2\in S_{2t+2}$ and
$\tau=\theta+_{j}2\in S_{2t+2}$ are $x--y$ equivalent in $S(2t+2)$.
\end{lemma}

\begin{proof}
It is sufficient to prove that for any permutation $\theta\in S_{2t}$, which
is obtained from $\phi\in S_{2t}$ by one $x--y$ exchange operation or one
$x--y$ cyclic operation, there exist some nonnegative integers $q$ and $k$,
such that the permutation $\mu=\phi+_{q}2\in S_{2t+2}$ is $x--y$ equivalent to
the permutation $\tau=\theta+_{k}2\in S_{2t+2}$. Indeed, our lemma then
follows, based on Definition \ref{xy.equiv.def} and Lemma \ref{tech.lem.0a}.

We start by considering the situation when $\theta$ was obtained from $\phi$
by one $x--y$ exchange operation. In this case, we set $q$ to be equal to $k$.
An $x--y$ exchange operation on $\phi$, by Proposition \ref{exchange-product},
produces $\theta$, such that $\theta^{\bullet}=(x,y,z)\cdot\phi^{\bullet}$.

If $t=1$ then $\phi=\theta$ and our lemma follows from Lemma \ref{tech.lem.0a}
. If $t\geq2$ we select any $k$ such that $\phi_{k}\notin\{x,y,z\}$. Then the
sets $\{x,y,z\}$ and $\{\phi_{k},2t+1,2t+2\}$ do not intersect. Then applying
the same $x--y$ exchange operation on $\mu$ produces a permutation $\tau$,
such that
\begin{align*}
\tau^{\bullet} & =(x,y,z)\cdot\mu^{\bullet}=(x,y,z)\cdot(\phi_{k},2t+1,2t+2)
\cdot\phi^{\bullet}\\
& =(\phi_{k},2t+1,2t+2)\cdot(x,y,z)\cdot\cdot\phi^{\bullet}=(\phi
_{k},2t+1,2t+2)\cdot\theta^{\bullet}.
\end{align*}
The cycles $(x,y,z)$ and $(\phi_{2t},2t+1,2t+2)$ in the equation commute,
because the sets $\{x,y,z\}$ and $\{\phi_{2t},2t+1,2t+2\}$ do not intersect.
Thus, $\tau$ is exactly $\theta+_{k}2\in S_{2t+2}$.

We conclude by considering the situation when $\theta$ was obtained from
$\phi$ by one $x--y$ cyclic operation. It is evident from Definition
\ref{cyclic-cdot}, that the $x--y$ cyclic operation, applied on $\theta$, does
not affect the $(2t+1)\rightarrow(2t+2)$ piece in the $(2t+3)$-cycle
$\mu^{\bullet}$, since both $2t+1$ and $2t+2$ are strictly greater than $x$
and greater than $y$. Thus, performing an $x--y$ cyclic operation on $\mu
=\phi+_{q}2\in S_{2t+2}$ produces a $(2t+3)$-cycle $\tau^{\bullet}$, which
contains some $\theta_{k+1}\rightarrow(2t+1)\rightarrow(2t+2)\rightarrow
\theta_{k}$. This Shows that $\tau=\theta+_{k}2\in S_{2t+2}$.
\end{proof}

Let $\phi$ be a permutation in $S_{2t}$, with $\phi_{2t}=2t-1$ and
$\phi_{2t-1}=2t$. Let $a$ be a nonnegative integer, smaller than $2t+1$. Let
$\theta\in S_{2t}$ be defined by $\theta_{\chi+i}=(\phi_{i}+a)\;\mod\;(2t+1)$,
where $\chi$ is such that $\phi_{\chi}=-a$. For $a=0$ we have $\theta=\phi$.
Notice that
\[
\phi^{\bullet}=(\phi_{2t-2},\phi_{2t-3},\ldots,\phi_{1},\phi_{0}=0,2t-1,2t)
\]
and
\[
\theta^{\bullet}=(\phi_{2t-2}+a,\phi_{2t-3}+a,\ldots,\phi_{1}+a,\phi
_{0}+a=a,2t-1+a=a-2,2t+a=a-1).
\]
Here all indices and all elements are modulo $2t+1$.

\begin{lemma}
\label{tech.lem.2} The permutations $\phi$ and $\theta$ are $x--y$ equivalent.
\end{lemma}

\begin{proof}
The lemma is trivial for $a=0$. Assume, by induction hypothesis, that the
lemma holds for $a$. We prove our lemma for $a+2$. This, by induction, implies
our lemma for all $a+2,a+4,a+6,\ldots$. Since $a+1=a+2t+2$ modulo $2t+1$, this
implies our lemma for $a+1$.

For all $q=1,\ldots,2t-2$, let $j_{q}$ be such that $\phi_{j_{q}}=2t-1-q$.
Since $\theta^{\bullet}$ contains $(a-2)\rightarrow(a-1)$, we can perform the
$(a-3)--(a-1)$ exchange operation on $\theta$. Recall that all the
calculations are carried modulo $2t+1$. Thus, for example, $-1=2t$, $-2=2t-1$,
and $-3=2t-2$. This $(a-3)--(a-1)$ exchange operation produces the permutation
$\rho\lbrack1]$ such that
\[
\rho\lbrack1]^{\bullet}=(\phi_{2t-2}+a,\phi_{2t-3}+a,\ldots,\phi_{j_{1}
-1}+a,2t+a=a-1,\phi_{j_{1}}+a=a-3,\ldots,
\]
\[
\ldots,\phi_{1}+a,\phi_{0}+a=a,2t-1+a=a-2).
\]
Since $\rho\lbrack1]^{\bullet}$ contains $(a-1)\rightarrow(a-3)$, we can
perform the $(a-2)--(a-3)$ exchange operation on $\rho\lbrack1]$. This
$(a-2)--(a-3)$ exchange operation produces the permutation $\varrho\lbrack1] $
such that
\[
\varrho\lbrack1]^{\bullet}=(\phi_{2t-2}+a,\phi_{2t-3}+a,\ldots,\phi_{j_{1}
-1}+a,2t+a=a-1,\phi_{j_{1}+1}+a,\ldots,
\]
\[
\ldots,\phi_{1}+a,\phi_{0}+a=a,\phi_{j_{1}}+a=a-3,2t-1+a=a-2).
\]
Since $\varrho\lbrack1]^{\bullet}$ contains $(a-3)\rightarrow(a-2)$, we can
perform the $(a-4)--(a-2)$ exchange operation on $\varrho\lbrack1]$. This
$(a-4)--(a-2)$ exchange operation produces the permutation $\rho\lbrack2]$
such that $\rho\lbrack2]^{\bullet}$ contains $(a-2)\rightarrow(a-4)$. Thus, we
perform an $(a-3)--(a-4)$ exchange operation on $\rho\lbrack2]$ and obtain
$\varrho\lbrack2]$. Notice that $\varrho\lbrack1]^{\bullet}$ is obtained from
\[
\theta^{\bullet}=(\phi_{2t-2}+a,\phi_{2t-3}+a,\ldots,\phi_{1}+a,\phi
_{0}+a=a,2t-1+a=a-2,2t+a=a-1)
\]
by adding $2$ to $\theta_{\chi+j_{1}}=\phi_{j_{1}}+a=a-3$ and to $\theta
_{\chi+j_{2}}=\phi_{j_{2}}+a=a-4$, and subtracting $2$ from $2t-1+a=a-2$ and
$2t+a=a-1$. Continuing this way, we produce permutations $\varrho
\lbrack3],\ldots,\varrho\lbrack2t-2]$. Now,
\begin{align*}
\varrho\lbrack2t-2\rbrack^{\bullet}&=(\phi_{2t-2}+a+2,\phi_{2t-3}+a+2,\ldots,\phi_{1}+a+2,\phi_{0}+a\\
&=a,2t-1+a-\lbrack 2t-2\rbrack\\
&=a+1,2t+a-\lbrack 2t-2\rbrack\\
&=a+2).
\end{align*}
Finally, we perform an $a--(a+2)$ exchange operation on $\varrho\lbrack2t-2\rbrack$
and obtain the permutation $\zeta$, for which
\begin{align*}
\zeta^{\bullet}&=(\phi_{2t-2}+a+2,\phi_{2t-3}+a+2,\ldots,\phi_{1}+a+2,\phi_{0}+a+2\\
&=a+2,2t-1+a+2\\
&=a,2t+a+2\\
&=a+1).
\end{align*}
Thus, we proved the lemma for $a+2$.
\end{proof}

\begin{lemma}
\label{tech.lem.3} Any permutation $\phi\in S_{2t}$, such that $\phi^{\bullet
}=(\ldots,a,b,a-1,\ldots)$, where $a$ and $b$ are between $0$ and $2t$, is
$x--y$ equivalent to some permutation $\theta\in S_{2t}$, such that
\[
\theta^{\bullet}=(\theta_{2t-2},\theta_{2t-3},\ldots,\theta_{1},\theta
_{0}=0,2t-1,2t).
\]

\end{lemma}

\begin{proof}
First, we show, that $\phi$ is $x--y$ equivalent to some $\rho\in S_{2t}$,
such that $\rho^{\bullet}$ contains some $k\rightarrow k+1$. Indeed, if
$b=a+1$, then we let $k=b$. Otherwise, if $b>a+1$, then an $(a-1)--b$ cyclic
operation on $\phi$ produces permutation $\rho$, such that $\rho^{\bullet
}=(\ldots,b-1,b,a-1,\ldots)$. Thus, we set $k=b-1$. And if $b<a-1$, then an
$(a-1)--b$ cyclic operation on $\phi$ produces permutation $\rho$, such that
$\rho^{\bullet}=(\ldots,a,b,b+1,\ldots)$. Thus, we set $k=b$.

Next, let $i,j$ be such that, in $\rho^{\bullet}$, $\rho_{i}\rightarrow k$ and
$\rho_{j}=k+2$. If $i=j$, then we set $\varrho=\rho$. Otherwise, a consecutive
performance of $k--\rho_{i}$, $k--\rho_{i+1}$, $\ldots$, $k--\rho_{j}$
exchange operations, just like in the proof of Lemma \ref{tech.lem.0a},
produces a permutation $\varrho=(\ldots,k+2,k,k+1,\ldots)$.

Lemma \ref{tech.lem.2} now establishes that $\varrho$, and, hence, $\phi$, is
$x--y$ equivalent to $\theta$.
\end{proof}

\begin{lemma}
\label{tech.lem.4} Let $\phi\in S_{2t}$ be a permutation, different than the
identity. Then $\phi$ is $x--y$ equivalent to some permutation $\theta\in
S_{2t}$, such that
\[
\theta^{\bullet}=(\theta_{2t-2},\theta_{2t-3},\ldots,\theta_{0},2t-1,2t).
\]

\end{lemma}

\begin{proof}
There exists some number $a$ between $0$ and $2t$, such that $\phi^{\bullet}$
does not contain $a\rightarrow(a-1)$. Otherwise, $\phi$ is the identity
permutation. Now, let $\phi^{\bullet}$ contain some path
\begin{equation}
a\rightarrow b_{1}\rightarrow b_{2}\rightarrow\dots\rightarrow b_{k}
\rightarrow(a-1),\label{last.lemma.eq.1}
\end{equation}
where $k\geq1$. First, assume that $k\geq2$. Then we look for $b(i)$,\newline
where $1\leq i\leq k-1$, such that $(b(i)-1)\notin\{b(1),\ldots,b(k)\}$. If we
find such a $b(i)$, we perform the $(b(i)-1)--b_{i+1}$ exchange operation on
$\phi$, which shortens the path \ref{last.lemma.eq.1} to
\[
a\rightarrow b_{1}\rightarrow\dots\rightarrow b_{i}\rightarrow b_{i+2}
\rightarrow\dots\rightarrow b_{k}\rightarrow(a-1).
\]
If we do not find such a $b(i)$, then $(b(k)-1)\notin\{b(1),\ldots,b(k)\}$. In
this case, we perform the $(a-1)--b(1)$ exchange operation on $\phi$, which
changes the path \ref{last.lemma.eq.1} to
\[
a\rightarrow b_{2}\rightarrow\dots\rightarrow b_{k}\rightarrow b_{1}
\rightarrow(a-1).
\]
Now we perform the $(b(k)-1)--b_{1}$ exchange operation, which shortens the
path \ref{last.lemma.eq.1} to
\[
a\rightarrow b_{2}\rightarrow\dots\rightarrow b_{k-1}\rightarrow
b_{1}\rightarrow(a-1).
\]


By repeating the argument of shortening the path \ref{last.lemma.eq.1}, we can
assume that $k=1$. The lemma now follows from Lemma \ref{tech.lem.3}.
\end{proof}

\begin{theorem}
\label{hultman-exchange-cyclic} If two permutations $\phi$ and $\theta$ in
$S_{2t}$ have the same number of alternating cycles in their cycle graphs
$\Gr(\phi)$ and $\Gr(\theta)$, then they are $x--y$ equivalent.
\end{theorem}

\begin{proof}
We prove the theorem by induction on $t$.

Basic step. For $t=1$ we only have one permutation $\langle2\;\;1\rangle\in
S_{2}$ with one alternating cycle in its cycle graph, and one permutation
$\langle1\;\;2\rangle\in S_{2}$ with two alternating cycles in its cycle
graph. Hence, the proof is completed for $t=1$.

Induction. Assume that the induction hypothesis is true for $t$. We will now
prove it for $t+1$.

If $\Gr(\phi)$ and $\Gr(\theta)$ have only one alternating cycle, then
$\phi=\theta$ is the identity permutation, and the proof is finished.

Otherwise, by Lemma \ref{tech.lem.4}, there exist permutations $\mu$ and
$\tau$ in $S_{2t+2}$ such that
\[
\mu^{\bullet}=(\mu_{2t},\mu_{2t-1},\ldots,\mu_{0},2t+1,2t+2),
\]
\[
\tau^{\bullet}=(\tau_{2t},\tau_{2t-1},\ldots,\tau_{0},2t+1,2t+2),
\]
and $\mu$ is $x--y$ equivalent to $\phi$, $\tau$ is $x--y$ equivalent to
$\theta$.

By Lemma \ref{tech.lem.0}, the permutations $\rho=\langle\mu_{1}\;\;\mu
_{2}\;\;\ldots\;\;\mu_{2t-1}\;\;\mu_{2t}\rangle$ and \newline$\varrho
=\langle\tau_{1}\;\;\tau_{2}\;\;\ldots\;\;\tau_{2t-1}\;\;\tau_{2t}\rangle$ in
$S_{2t}$ have the same number of alternating cycles in their cycle graphs as
the permutations $\mu$ and $\tau$, which, in turn, by Theorem
\ref{equiv-alternating}, have the same number of alternating cycles in their
cycle graphs as the permutations $\phi$ and $\theta$. Now we apply the
induction hypothesis to obtain that $\rho$ and $\varrho$ are $x--y$ equivalent
in $S_{2t}$. This, by Lemma \ref{tech.lem.1}, establishes that $\mu$ and
$\tau$ are $x--y$ equivalent in $S_{2t+2}$. Thus, $\phi$ and $\theta$ are
$x--y$ equivalent in $S_{2t+2}$, which completes the proof.
\end{proof}

At this point we are ready to state and prove the two main findings. They
generalize the observation, made at the end of the previous section, that the
probability of a permutation equality in a fixed finite group $G$ depends only
on the number of the alternating cycles in the cycle graph of the permutation.

\begin{theorem}
\label{main.theorem.1} Let $\phi\in S_{n}$ be a permutation such that
$\Gr(\phi)$ contains $k$ alternating cycles. Then, for all positive $k\leq
n$,
\[
{\Pr}_{\phi}(G)={\Pr}^{n+1-k}(G)=\Pr(a_{1}a_{2}\cdots a_{n-k}a_{n+1-k}
=a_{n+1-k}a_{n-k}\cdots a_{2}a_{1})
\]
Since, as shown in \cite{DL}, $n-k$ must be an odd number, $k\leq n$ implies
$k\leq n-1$. If $k>n$ then $k=n+1$ and $\phi$ is the identity permutation,
which implies $\Pr_{\phi}(G)=1$.
\end{theorem}

\begin{proof}
If $n$ is an even number then, by Theorem \ref{hultman-exchange-cyclic}, the
permutations $\phi$ and \newline$\langle a_{n+1-k}\;\;\ldots\;\;a_{1}
\;\;a_{n+2-k}\;\;\ldots\;\;a_{n}\rangle$, both having $k$ alternating cycles
in their cycle graphs, are $x--y$ equivalent in $S_{n}$. Next, Theorem
\ref{equivalent.keeps.prob} asserts that $\Pr_{\phi}(G)=\Pr^{n+1-k}(G)$.

If $n$ is odd then define $\rho\in S_{n+1}$ by $\rho=\langle\phi_{1}
\;\;\ldots\;\;\phi_{n}\;\;(n+1)\rangle$. Notice that $\Gr(\rho)$ contains the
same $k$ alternating cycles as $\Gr(\phi)$ plus one additional alternating
cycle $(n+1)\dashrightarrow0\rightarrow(n+1)$, which is $(n+1)\mapsto(n+1)$.
Since $n+1$ is even, $\Pr_{\phi}(G)=\Pr_{\rho}(G)=\Pr^{n+2-(k+1)}
(G)=\Pr^{n+1-k}(G)$.
\end{proof}

\begin{theorem}
\label{main.theorem.2} Let $G$ be a finite non-Abelian group. Let $\phi$ and
$\theta$ be two permutations in $S_{n}$. Then, $\Pr_{\phi}(G)=\Pr_{\theta}(G)
$ if, and only if, the number of the alternating cycles in the cycle graph
$\Gr(\phi)$ equals the number of alternating cycles in the cycle graph
$\Gr(\theta)$. Thus, the spectrum of probabilities of permutation equalities
for permutations from $S_{n}$ in a finite non-Abelian group $G$ consisting of
exactly $\left\lfloor \frac{n}{2}\right\rfloor +1$ different numbers, each
number corresponding to its unique Hultman class of permutations in $S_{n}$.
\end{theorem}

\begin{proof}
This theorem follows trivially from Theorem \ref{main.theorem.1} and Theorem
\ref{generic.group}.
\end{proof}

\section{Two explicit formulae for $\Pr^{2t}(G)$}

We provide two explicit formulae for $\Pr^{2t}(G)$. Our first formula
expresses $\Pr^{2t}(G)$ in terms of ${\Stab}_{t}(x_{1},x_{2},\ldots, x_{t})$.
Our second formula expresses $\Pr^{2t}(G)$ in terms of $c_{i_{1},\ldots
,i_{t};j}(G)$. These results constitute a generalization of what was shown in
Theorem \ref{mainfour} for permutations in $S_{4}$.

\begin{theorem}
\label{main.result.3} Let $G$ be a finite group. Then
\begin{equation}
\label{Eq.Stab.Prod}\Pr(a_{1}a_{2}\cdots a_{2t}=a_{2t}a_{2t-1}\cdots
a_{1})=\frac{\sum\limits_{x_{1},x_{2},\ldots,x_{t}\in G}|{\Stab}_{t}
(x_{1},x_{2},\ldots,x_{t})|}{|G|^{2t}}
\end{equation}
\begin{equation}
\label{Eq.weak.ring}\Pr(a_{1}a_{2}\cdots a_{2t}=a_{2t}a_{2t-1}\cdots
a_{1})=\frac{1}{|G|^{t}}\cdot\sum\limits_{i_{1},i_{2},\ldots,i_{t},j=1}
^{c(G)}\frac{|\Omega_{j}|\cdot c_{i_{1},i_{2},\ldots,i_{t};j}^{2}(G)}
{|\Omega_{i_{1}}|\cdot|\Omega_{i_{2}}|\cdot\cdots\cdot|\Omega_{i_{t}}|}
\end{equation}

\end{theorem}

\begin{proof}
Let us consider a generic equation
\[
a_{1}a_{2}\cdots a_{2t}=a_{2t}a_{2t-1}\cdots a_{1}.
\]
Let $x_{i}$ denotes the product $a_{2i-1}a_{2i}$ for all $i=1,\ldots,t$. Let
$x_{i}^{\prime}$ denotes the product $a_{2i}a_{2i-1}$. Notice that by Lemma
\ref{commute-conjug}, we have $x_{i}\sim x_{i}^{\prime}$.

The equation
\[
a_{1}a_{2}\cdots a_{2t}=a_{2t}a_{2t-1}\cdots a_{1}
\]
then becomes
\[
x_{1}x_{2}\cdots x_{t}=x_{t}^{\prime}x_{t-1}^{\prime}\cdots x_{1}^{\prime}.
\]


Now, consider any equation
\[
x_{1},\ldots,x_{n},x_{1}^{\prime},\ldots,x_{n}^{\prime}\in G,
\]
such that $x_{i}\sim x_{i}^{\prime}$ for all $i=1,\ldots,t$. Then, by Lemma
\ref{conjug-decomp}, there are exactly \newline$\frac{|G|}{|\Omega_{x_{i}}
|}=|C_{G}(x_{i})|$ different ways to break each $x_{i}$ into a product
$a_{2i-1}a_{2i}$ in such a way that $x_{i}^{\prime}=a_{2i}a_{2i-1}$. Thus, to
each fixed equation
\[
x_{1}x_{2}\cdots x_{t}=x_{t}^{\prime}x_{t-1}^{\prime}\cdots x_{1}^{\prime}
\]
corresponds to
\[
\left\vert C_{G}(x_{1})\right\vert \cdot\left\vert C_{G}(x_{2})\right\vert
\cdot\cdots\cdot\left\vert C_{G}(x_{t})\right\vert
\]
different equations
\[
a_{1}a_{2}\cdots a_{2t}=a_{2t}a_{2t-1}\cdots a_{1}.
\]


Notice that for any fixed elements $x_{1},x_{2},\ldots,x_{t}\in G$, we can
define an element
\[
x_{1}^{\prime\prime}=(x_{2}x_{3}\cdots x_{t})^{-1}x_{1}(x_{2}x_{3}\cdots
x_{t})=x_{t}^{-1}\cdots x_{3}^{-1}x_{2}^{-1}x_{1}x_{2}x_{3}\cdots x_{t}
\]
and obtain an equation
\[
x_{1}x_{2}\cdots x_{t}=x_{t}x_{t-1}\cdots x_{2}x_{1}^{\prime\prime}.
\]


Now, for any general equation
\[
x_{1}x_{2}\cdots x_{t}=x_{t}^{\prime}x_{t-1}^{\prime}\cdots x_{1}^{\prime},
\]
in which $x_{i}{}\sim x_{i}^{\prime}$ for all $i$, there exist some elements
$g_{1},g_{2},\ldots,g_{t}\in G$, such that \newline$x_{1}^{\prime}=g_{1}
x_{1}^{\prime\prime}g_{1}^{-1}$ and, for all $i=2,3,\ldots,t$, $x_{i}^{\prime
}=g_{i}x_{i}g_{i}^{-1}$.

Thus, if we select and fix elements $x_{1},x_{2},\ldots,x_{t}\in G$, we will
have
\[
\frac{|{\Stab}_{t}(x_{t},\ldots,x_{2},x_{1}^{\prime\prime})|}{\left\vert
C_{G}(x_{t})\right\vert \cdot\cdots\cdot\left\vert C_{G}(x_{2})\right\vert
\cdot\left\vert C_{G}(x_{1}^{\prime\prime})\right\vert }
\]
different equations
\[
x_{1}x_{2}\cdots x_{t}=x_{t}^{\prime}x_{t-1}^{\prime}\cdots x_{1}^{\prime},
\]
in which $x_{i}^{\prime}\sim x_{i}$ and for all $i$. Indeed, every ordered
$t$-tuple
\[
(g_{t},g_{t-1},\ldots,g_{2},g_{1}^{\prime\prime})\in{\Stab}_{t}(x_{t}
,\ldots,x_{2},x_{1}^{\prime\prime}),
\]
by setting $x_{i}^{\prime}=g_{i}x_{i}g_{i}^{-1}$, for all $i=t,\ldots,2$, and
$x\prime_{1}=g_{1}x_{1}^{\prime\prime}g_{1}^{-1}$, produces an equation
\[
x_{1}x_{2}\cdots x_{t}=x_{t}^{\prime}x_{t-1}^{\prime}\cdots x_{1}^{\prime}.
\]
And any two of these equations produced from the equation $x_{1}x_{2}\cdots
x_{t}=x_{t}x_{t-1}\cdots x_{2}x_{1}^{\prime\prime}$ are identical if, and only
if, $g_{i}\in C_{G}(x_{i})$, for all $i=t,\ldots,2$ and $g_{1}\in
C_{G}(x^{\prime\prime})$. Now, $\left\vert C_{G}(x_{1}^{\prime\prime
})\right\vert =\left\vert C_{G}(x_{1})\right\vert $. Thus, for each fixed
ordered $t$-tuple $(x_{1},x_{2},\ldots,x_{t})$ of elements of $G$ we have
\[
\frac{|{\Stab}_{t}(x_{t},\ldots,x_{2},x_{1}^{\prime\prime})|}{\left\vert
C_{G}(x_{t})\right\vert \cdot\cdots\cdot\left\vert C_{G}(x_{2})\right\vert
\cdot\left\vert C_{G}(x_{1})\right\vert }
\]
different equations
\[
x_{1}x_{2}\cdots x_{t}=x_{t}^{\prime}x_{t-1}^{\prime}\cdots x_{1}^{\prime}.
\]
As we showed above, to each of these equations correspond
\[
\left\vert C_{G}(x_{1})\right\vert \cdot\left\vert C_{G}(x_{2})\right\vert
\cdot\cdots\cdot\left\vert C_{G}(x_{t})\right\vert
\]
different equations
\[
a_{1}a_{2}\cdots a_{2t}=a_{2t}a_{2t-1}\cdots a_{1}.
\]
Thus to each ordered $t$-tuple $(x_{1},x_{2},\ldots,x_{t})$ of elements of $G$
correspond \newline$|{\Stab}_{t}(x_{t},\ldots,x_{2},x_{1}^{\prime\prime})|$
different equations
\[
a_{1}a_{2}\cdots a_{2t}=a_{2t}a_{2t-1}\cdots a_{1}.
\]


Hence, to find
\[
\Pr(a_{1}a_{2}\cdots a_{2t}=a_{2t}a_{2t-1}\cdots a_{1})
\]
we need to sum $|{\Stab}_{t}(x_{t},x_{t-1},\ldots x_{2},x_{1}^{\prime\prime
})|$, as $x_{1},x_{2},\ldots,x_{t}$ run over all elements of $G$.

Since $x_{1},x_{2},\ldots,x_{n}$ run over all the elements of $G$, and for
each fixed $x_{1},\ldots,x_{n-1}$ there is a one-to-one correspondence between
$x_{1}^{\prime\prime}$ and $x_{1}$, the sum remains the same if we sum
$|{\Stab}_{t}(x_{t},x_{t-1},\ldots, x_{2},x_{1})|$, as $x_{1},x_{2}
,\ldots,x_{t}$ run over all elements of $G$. That proves Equation
\ref{Eq.Stab.Prod}.

Now, select and fix an element $z$ in an equivalence class $\Omega_{j}$ of $G
$.\newline Let $x_{1},\ldots,x_{t},x_{1}^{\prime},\ldots,x_{t}^{\prime}\in G$
be such, that $x_{i}\sim x_{i}^{\prime}$ for all $i$, and
\begin{equation}
x_{1}x_{2}\cdots x_{t}=z=x_{1}^{\prime}x_{2}^{\prime}\cdots x_{t}^{\prime
}.\label{final.equation1}
\end{equation}
For each $i=1,\ldots,t$, there are $|C_{G}(x_{i})|$ different ways to break
$x_{i}$ into a product $a_{2i-1}a_{2i}$ so that $a_{2i}a_{2i-1}=x_{i}^{\prime}
$. Hence, for each (fixed) Equation \ref{final.equation1} we have exactly
$\left\vert C_{G}(x_{1})\right\vert \cdot\left\vert C_{G}(x_{2})\right\vert
\cdot\cdots\cdot\left\vert C_{G}(x_{t})\right\vert $ different equations
\begin{align*}
(a_{1}a_{2})(a_{3}a_{4})\cdots(a_{2t-1}a_{2t}) & =x_{1}x_{2}\cdots x_{t}\\
& =z=x_{1}^{\prime}x_{2}^{\prime}\cdots x_{t}^{\prime}=(a_{2}a_{1})(a_{4}
a_{3})\cdots(a_{2t}a_{2t-1}).
\end{align*}
But,
\[
\left\vert C_{G}(x_{1})\right\vert \cdot\left\vert C_{G}(x_{2})\right\vert
\cdot\cdots\cdot\left\vert C_{G}(x_{t})\right\vert =\frac{|G|^{t}}{\left\vert
\Omega(x_{1})\right\vert \cdot\left\vert \Omega(x_{2})\right\vert \cdot
\cdots\cdot\left\vert \Omega(x_{t})\right\vert }.
\]


Now, for $z\in\Omega_{j}$ there are $c_{i_{1},i_{2},\ldots,i_{t};j}(G)$
different ways to write $z$ as a product $x_{1}x_{2}\cdots x_{t}$, where
$x_{i}\in\Omega_{i}$ for all $i=1,\ldots,t$, and $c_{i_{1},i_{2},\ldots
,i_{t};j}(G)$ different ways to write $z$ as a product $x_{1}^{\prime}
x_{2}^{\prime}\cdots x_{t}^{\prime}$, where $x_{i}^{\prime}\in\Omega_{i}$ for
all $i=1,\ldots,t$. Thus, for each $z\in\Omega_{j}$ there are $c_{i_{1}
,i_{2},\ldots,i_{t};j}^{2}(G)$ different equations of the form
\[
x_{1}x_{2}\cdots x_{t}=z=x_{1}^{\prime}x_{2}^{\prime}\cdots x_{t}^{\prime},
\]
in which $x_{i},x_{i}^{\prime}\in\Omega_{i}$ for all $i=1,\ldots,t$. Thus, for
each $z\in\Omega_{j}$ there are
\[
|G|^{t}\cdot\sum\limits_{i_{1},i_{2},\ldots,i_{t}=1}^{c(G)}\frac
{c_{i_{1},i_{2},\ldots,i_{t};j}^{2}(G)}{\left\vert \Omega_{i_{1}}\right\vert
\cdot\left\vert \Omega_{i_{2}}\right\vert \cdot\cdots\cdot\left\vert
\Omega_{i_{t}}\right\vert }
\]
different equations of the form
\[
(a_{1}a_{2})(a_{3}a_{4})\cdots(a_{2t-1}a_{2t})=z=(a_{2}a_{1})(a_{4}
a_{3})\cdots(a_{2t}a_{2t-1}).
\]
We make $z$ run over all the elements of $G$ and obtain
\[
\Pr(a_{1}a_{2}\cdots a_{2t-1}a_{2t}=a_{2}a_{1}\cdots a_{2t}a_{2t-1})=\frac
{1}{|G|^{t}}\cdot\sum\limits_{i_{1},i_{2},\ldots,i_{t},j=1}^{c(G)}
\frac{\left\vert \Omega_{j}\right\vert \cdot c_{i_{1},i_{2},\ldots,i_{t}
;j}^{2}(G)}{\left\vert \Omega_{i_{1}}\right\vert \cdot\left\vert \Omega
_{i_{2}}\right\vert \cdot\cdots\cdot\left\vert \Omega_{i_{t}}\right\vert }.
\]
Since both permutations $\phi=\langle2t\;\;2t-1\;\;\ldots\;\;1\rangle$ and
$\theta=\langle2\;\;1\;\;4\;\;3\;\;\ldots\;\;2t\;\;2t-1\rangle$ have exactly
one alternating cycle in their cycle graphs $\Gr(\phi)$ and $\Gr(\theta)$,
Equation \ref{Eq.weak.ring} follows from Theorem \ref{main.theorem.2}.
\end{proof}

\section{Conclusion}

In conclusion, we recall two known results. The first result relates ${\Pr}^{2t}(G) $
to the commutator subgroup $G^{\prime}$ and the quotient group $G/Z(G)$, and
the second result relates ${\Pr}^{2t}(G)$ to the notion of isoclinism of groups. We
give a counter-example to the opposite direction of the second result. We
conjecture a weaker form of the opposite direction of the second result.
Finally, we give an example, demonstrating that the isoclinism in the second
result cannot be replaced by weak isoclinism. From that it follows that the
opposite direction of our conjecture is false.

\begin{theorem}
\label{Commutator} The first result, established by Das and Nath
\cite{DasNath2}, is
\[
\lim_{t\rightarrow\infty}{\Pr}^{2t}(G)=\frac{1}{|G^{\prime}|}.
\]

\end{theorem}

\begin{theorem}
\label{Thm_Isoclinic} The second result, established by Das and Nath
\cite{DasNath2} If two finite groups $G_{1}$ and $G_{2}$ are isoclinic,
then ${\Pr}^{2t}(G_{1})={\Pr}^{2t}(G_{2})$ for all $t=1,2,\ldots$.
\end{theorem}

For example, every two Abelian groups are isoclinic. Clearly, ${\Pr}
^{2t}(G)=1$ for all $t$, for every Abelian group. The dihedral group $D_{8}$
and the quaternion group $Q_{8}$, both of order $8$, are isoclinic. As we
showed in Example \ref{d4q8.general}, ${\Pr}^{2t}(D_{8})={\Pr}^{2t}(Q_{8})$
for every $t\geq1$.

Now, notice that the opposite direction of the second result is not true. Two
finite groups $G_{1}$ and $G_{2}$, for which ${\Pr}^{2t}(G_{1})={\Pr}
^{2t}(G_{2})$ for all $t=1,2,\ldots$, do not have to be isoclinic. For
example, the groups
\begin{align*}
G_{1}= & \langle a_{1},a_{2},a_{3},a_{4},a_{5},a_{6}\;:\;a_{1}^{2}=a_{4}
,a_{4}^{2}=a_{6},a_{2}^{2}=a_{3}^{2}=a_{5}^{2}=a_{6}^{2}=1,\\
& \lbrack a_{1},a_{2}\rbrack=a_{3},\lbrack a_{1},a_{3}\rbrack=\lbrack a_{2},a_{4}\rbrack=a_{5},\\
& \lbrack a_{1},a_{5}\rbrack=\lbrack a_{2},a_{5}\rbrack=\lbrack a_{3},a_{5}\rbrack=\lbrack a_{2},a_{3}\rbrack=\lbrack a_{3},a_{4}
\rbrack=\lbrack a_{2},a_{6}\rbrack=\lbrack a_{3},a_{6}\rbrack=1 \rangle
\end{align*}
and
\begin{align*}
G_{2}= & \langle a_{1},a_{2},a_{3},a_{4},a_{5},a_{6}\;:\;a_{1}^{2}=a_{2}
^{2}=a_{3}^{2}=a_{4}^{2}=a_{5}^{2}=a_{6}^{2}=1,\\
& \lbrack a_{1},a_{2}\rbrack=a_{6},\lbrack a_{1},a_{3}\rbrack=\lbrack a_{2},a_{4}\rbrack=a_{5},\\
& \lbrack a_{1},a_{4}\rbrack=\lbrack a_{1},a_{5}\rbrack=\lbrack a_{1},a_{6}\rbrack=\lbrack a_{2},a_{3}\rbrack=\lbrack a_{2},a_{5}
\rbrack=\lbrack a_{2},a_{6}\rbrack\\
& =\lbrack a_{3},a_{4}\rbrack=\lbrack a_{3},a_{5}\rbrack=\lbrack a_{3},a_{6}\rbrack=\lbrack a_{4},a_{5}\rbrack=\lbrack a_{4}
,a_{6}\rbrack=\lbrack a_{5},a_{6}\rbrack=1 \rangle,
\end{align*}
both of the order $64$, are not isoclinic, not even weakly isoclinic. Indeed,
$G_{1}/Z(G_{1})$ is a non-Abelian group of order $16$, while $G_{2}/Z(G_{2})$
is an Abelian group of order $16$. The fact that ${\Pr}^{2t}(G_{1})={\Pr}
^{2t}(G_{2})$, for every $t\geq1$, is verifiable by a direct calculation.

 From Theorem \ref{Commutator} it follows that, if for two finite groups
$G_{1}$ and $G_{2}$ we have \\ ${\Pr}^{2t}(G_{1})={\Pr}^{2t}(G_{2})$ for every
$t\geq1$, then $|G_{1}^{\prime}|=|G_{2}^{\prime}|$. That motivates the
following conjecture, which, together with $|G_{1}^{\prime}|=|G_{2}^{\prime}|
$, is a weaker form of the opposite direction of the second result.

\begin{conjecture}
\label{isoclinic} Let $G_{1}$ and $G_{2}$ are two finite groups, such that
${\Pr}^{2t}(G_{1})={\Pr}^{2t}(G_{2})$ for every $t\geq1$. Then $|G_{1}
/Z(G_{1})|=|G_{2}/Z(G_{2})|$.
\end{conjecture}

The groups $G_{2}$ and $G_{3}=D_{8}\times D_{8}$ give a counterexample to the
opposite direction of Conjecture \ref{isoclinic}. Moreover, $G_{2}^{\prime}$
is isomorphic to $G_{3}^{\prime}|$, and $G_{2}/Z(G_{2})$ is isomorphic to
$G_{3}/Z(G_{3})|$. Thus, $G_{2}$ and $G_{3}$ are weakly isoclinic.
However,\newline${\Pr}^{2}(G_{2})=\frac{22}{64}\neq\frac{25}{64}={\Pr}
^{2}(G_{3})$. Hence, by Theorem \ref{Thm_Isoclinic}, $G_{2}$ and $G_{3}$ are
not isoclinic.

\section{Acknowledgments}

We thank both referees for their helpful remarks that gave us an opportunity
to significantly improve the presentation of the paper. Our special gratitude
is to the referee that paid attention to fruitful connections between block
transpositions due to Bafna and Pevzner \cite{BP} and the $x--y $ exchange
operation defined in this paper.

\begin{thebibliography}{99}                                                                                               
\bibitem {BP}V. Bafna and P. A. Pevzner, Sorting by transpositions, \emph{SIAM
J. Discrete Math.} \textbf{11} (1998) 224--240.

\bibitem {BBW}S. R. Blackburn, J. R. Britnell, and M. Wildon, The probability
that a pair of elements of a finite group are conjugate, \emph{J. Lond. Math.
Soc.} \textbf{86} (2012) 755--778.

\bibitem {Buckley2014}S. M. Buckley, Isoclinism and weak isoclinism
invariants, preprint,  
\url{http://archive.maths.nuim.ie/staff/sbuckley/Papers/gp\_isoc.pdf},
2014.

\bibitem {CGL}Y. Cherniavsky, A. Goldstein, and V. E. Levit, Groups of
balanced labelings on graphs, \emph{Discrete Math.} \textbf{320} (2014) 15--25.

\bibitem {CGLS2016}Y. Cherniavsky, A. Goldstein, V. E. Levit, and R. Shwartz,
Enumeration of balanced finite group valued functions on directed graphs,
\emph{Inform. Process. Lett.} \textbf{116} (2016) 484--488.

\bibitem {CGL2017}Y. Cherniavsky, A. Goldstein, and V. E. Levit, Balanced
Abelian group-valued functions on directed graphs, \emph{Ars Math.
Contemporanea} \textbf{13} (2017) 307--315.

\bibitem {CGK}C. Clifton, D. Guichard, and P. Keef, How commutative are direct
products of dihedral groups?, \emph{Math. Mag.} \textbf{84} (2011) 137--140.

\bibitem {DasNath1}A. K. Das and R. K. Nath, A generalization of commutativity
degree of finite groups, \emph{Comm. Algebra} \textbf{40} (2012) 1974--1981.

\bibitem {DasNath2}A. K. Das and R. K. Nath, A survey on the estimation of
commutativity in finite groups, \emph{Southeast Asian Bull. Math.} \textbf{37}
(2013) 161--180.

\bibitem {DasNath3}A. K. Das and R. K. Nath, On generalized commutativity
degree of a finite group, \emph{Rocky Mountain J. Math.} \textbf{41} (2011) 1987--2000.

\bibitem {Dixon}J. Dixon, Probabilistic group theory, \emph{C. R. Math. Acad.
Sci. Soc. R. Can.} \textbf{24} (2002) 1--15.

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

\bibitem {ES}P. Erd\H{o}s and E. G. Straus, How abelian is a finite group?,
\emph{Linear Multilinear Algebra} \textbf{3} (1976) 307--312.

\bibitem {ET}P. Erd\H{o}s and P. Turan, On some problems of statistical group
theory, \emph{Acta Math. Acad. Sci. Hungar.} \textbf{19} (1968) 413--435.

\bibitem {ErSu}I. V. Erovenko and B. Surg, Commutativity degrees of wreath
products of finite abelian groups, \emph{Bull. Aust. Math. Soc.} \textbf{77}
(2008) 31--36.

\bibitem {G}W. H. Gustafson, What is the probability that two group elements
commute?, \emph{Amer. Math. Monthly} \textbf{80} (1973) 1031--1034.

\bibitem {GerRob}R. M. Guralnick and G. R. Robinson, On the commuting
probability in finite groups, \emph{J. Algebra} \textbf{300} (2006) 509--528.

\bibitem {Hall1940}P. Hall, The classification of prime-power groups, \emph{J.
Reine Angew. Math.} \textbf{182} (1940) 130--141.

\bibitem {JM}U. Jezernik and P. Moravec, Universal commutator relations,
Bogomolov multipliers, and commuting probability, \emph{J. Algebra}
\textbf{428} (2015) 1--25.

\bibitem {L}P. Lescot, Central extensions and commutativity degrees,
\emph{Comm. Algebra} \textbf{29} (2001) 4451--4460.

\bibitem {LNY2014}P. Lescot, H. N. Nguyen, and Y. Yang, On the commuting
probability and supersolvability of finite groups, \emph{Monatsh. Math.} 174
(2014) 567--576.

\bibitem {NathDash1}R. K. Nath and A. K. Das, On generalized commutativity
degree of a finite group, \emph{Rocky Mountain J. Math.} \textbf{41} (2011) 1987--2000.

\bibitem {Nath2011}R. K. Nath, 
{\it Some New Directions in Commutativity Degree of
Finite Groups: Recent Developments}, \emph{Lambert Academic Publishing},
2011.

\bibitem {PS}M. R. Pournakia and R. Sobhani, Probability that the commutator
of two group elements is equal to a given element, \emph{J. Pure Appl.
Algebra} \textbf{212} (2008) 727--734.

\bibitem {Sloan}N. J. A. Sloane, \emph{The On-line Encyclopedia of Integer Sequences},\\ \url{http://www.oeis.org}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 20P05; Secondary 20F12, 20B05, 05A05, 20D60.

\noindent \emph{Keywords: }
commuting probability, Hultman number, cycle graph of a permutation,
isoclinism, finite group.

\bigskip
\hrule
\bigskip

\noindent
(Concerned with the sequence
\seqnum{A164652}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 17 2015;
revised versions received March 29 2017; October 31 2017.
Published in {\it Journal of Integer Sequences}, November 22 2017.

\bigskip
\hrule
\bigskip

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


\end{document}