\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, October 31, 2019 19:48:00}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\ihead{Math 4990 Fall 2017 (Darij Grinberg): homework set 7}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4990 Fall 2017 (Darij Grinberg): homework set 7 with solutions}
\end{center}

%

%TCIMACRO{\TeXButton{tableofcontents}{\tableofcontents}}%
%BeginExpansion
\tableofcontents
%EndExpansion


\subsection{A generalized principle of inclusion/exclusion}

\begin{exercise}
\label{exe.pie.dan}Let $n\in\mathbb{N}$. Let $S$ be a finite set. Let
$A_{1},A_{2},\ldots,A_{n}$ be finite subsets of $S$. Let $k\in\mathbb{N}$. Let
$S_{k}$ be the set of all elements of $S$ that belong to exactly $k$ of the
subsets $A_{1},A_{2},\ldots,A_{n}$. (In other words, let $S_{k}=\left\{  s\in
S\ \mid\ \text{the number of }i\in\left[  n\right]  \text{ satisfying }s\in
A_{i}\text{ equals }k\right\}  $.) Prove that%
\[
\left\vert S_{k}\right\vert =\sum_{I\subseteq\left[  n\right]  }\left(
-1\right)  ^{\left\vert I\right\vert -k}\dbinom{\left\vert I\right\vert }%
{k}\left\vert \bigcap_{i\in I}A_{i}\right\vert .
\]
Here, the intersection $\bigcap_{i\in\varnothing}A_{i}$ is understood to mean
the whole set $S$.
\end{exercise}

Note that the principle of inclusion and exclusion (see, e.g., \cite[\S 16]%
{Galvin}) is the particular case of Exercise \ref{exe.pie.dan} for $k=0$
(since $S_{0}=S\setminus\bigcup_{i=1}^{n}A_{i}$).

Exercise \ref{exe.pie.dan} is a result of Charles Jordan (see \cite[\S 4.8,
Theorem A]{Comtet74} and \cite{DanRot78} for fairly complicated proofs). I
further generalize it in \cite[Theorem 3.44]{detnotes}. Let me here give a
self-contained proof.

First, we recall two facts from the solutions to
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw5os.pdf}{homework set \#5}:

\begin{proposition}
\label{prop.binom.0}We have
\[
\dbinom{m}{n}=0
\]
for every $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfying $m<n$.
\end{proposition}

\begin{corollary}
\label{cor.binom.1-1cor2}Let $n\in\mathbb{N}$. Let $i\in\mathbb{N}$. Then,%
\[
\sum_{j=0}^{n}\left(  -1\right)  ^{j}\dbinom{n}{j}\dbinom{j}{i}=\left(
-1\right)  ^{i}\left[  n=i\right]  .
\]

\end{corollary}

Next, we recall the classical formula for the size of a subset using Iverson brackets:

\begin{lemma}
\label{lem.iverson.card}Let $S$ be a finite set. Let $T$ be a subset of $S$.
Then,%
\[
\left\vert T\right\vert =\sum_{s\in S}\left[  s\in T\right]  .
\]

\end{lemma}

Lemma \ref{lem.iverson.card} allows us to reduce a formula for $\left\vert
S_{k}\right\vert $ to a formula for $\left[  s\in S_{k}\right]  $ (for any
given $s\in S$). Here is the latter formula:

\begin{lemma}
\label{lem.pie.dan.1}Let $n\in\mathbb{N}$. Let $S$ be a finite set. Let
$A_{1},A_{2},\ldots,A_{n}$ be finite subsets of $S$. Let $k\in\mathbb{N}$. Let
$S_{k}$ be the set of all elements of $S$ that belong to exactly $k$ of the
subsets $A_{1},A_{2},\ldots,A_{n}$. (In other words, let $S_{k}=\left\{  s\in
S\ \mid\ \text{the number of }i\in\left[  n\right]  \text{ satisfying }s\in
A_{i}\text{ equals }k\right\}  $.) Let $s\in S$. Then,%
\[
\left[  s\in S_{k}\right]  =\sum_{I\subseteq\left[  n\right]  }\left(
-1\right)  ^{\left\vert I\right\vert -k}\dbinom{\left\vert I\right\vert }%
{k}\left[  s\in\bigcap_{i\in I}A_{i}\right]  .
\]
Here, the intersection $\bigcap_{i\in\varnothing}A_{i}$ is understood to mean
the whole set $S$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.pie.dan.1}.]Define a subset $C$ of $\left[  n\right]
$ by%
\[
C=\left\{  i\in\left[  n\right]  \ \mid\ s\in A_{i}\right\}  .
\]
Thus, for each $i\in\left[  n\right]  $, we have the following equivalence:%
\begin{equation}
\left(  i\in C\right)  \ \Longleftrightarrow\ \left(  s\in A_{i}\right)  .
\label{pf.lem.pie.dan.1.1}%
\end{equation}


But recall the definition of $S_{k}$. From this definition, we obtain the
following equivalence:%
\begin{align*}
\left(  s\in S_{k}\right)  \  &  \Longleftrightarrow\ \left(
\underbrace{\text{the number of }i\in\left[  n\right]  \text{ satisfying }s\in
A_{i}}_{=\left\vert \left\{  i\in\left[  n\right]  \ \mid\ s\in A_{i}\right\}
\right\vert }\text{ equals }k\right) \\
&  \Longleftrightarrow\ \left(  \left\vert \underbrace{\left\{  i\in\left[
n\right]  \ \mid\ s\in A_{i}\right\}  }_{=C}\right\vert \text{ equals
}k\right)  \ \Longleftrightarrow\ \left(  \left\vert C\right\vert \text{
equals }k\right) \\
&  \Longleftrightarrow\ \left(  \left\vert C\right\vert =k\right)  .
\end{align*}
Hence, we find the following equality between truth values:%
\begin{equation}
\left[  s\in S_{k}\right]  =\left[  \left\vert C\right\vert =k\right]  .
\label{pf.lem.pie.dan.1.2}%
\end{equation}


On the other hand, let $I$ be any subset of $\left[  n\right]  $. Then, we
have the following equivalence:%
\begin{align*}
\left(  s\in\bigcap_{i\in I}A_{i}\right)  \  &  \Longleftrightarrow\ \left(
\underbrace{s\in A_{i}}_{\substack{\Longleftrightarrow\ \left(  i\in C\right)
\\\text{(by (\ref{pf.lem.pie.dan.1.1}))}}}\text{ for each }i\in I\right)
\ \Longleftrightarrow\ \left(  i\in C\text{ for each }i\in I\right) \\
&  \Longleftrightarrow\ \left(  I\subseteq C\right)  .
\end{align*}
Thus,
\begin{equation}
\left[  s\in\bigcap_{i\in I}A_{i}\right]  =\left[  I\subseteq C\right]  .
\label{pf.lem.pie.dan.1.4}%
\end{equation}


Now, forget that we fixed $I$. We thus have proven (\ref{pf.lem.pie.dan.1.4})
for each subset $I$ of $\left[  n\right]  $. Thus,
\begin{align*}
&  \sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{\left\vert
I\right\vert -k}\dbinom{\left\vert I\right\vert }{k}\underbrace{\left[
s\in\bigcap_{i\in I}A_{i}\right]  }_{\substack{=\left[  I\subseteq C\right]
\\\text{(by (\ref{pf.lem.pie.dan.1.4}))}}}\\
&  =\sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{\left\vert
I\right\vert -k}\dbinom{\left\vert I\right\vert }{k}\left[  I\subseteq
C\right] \\
&  =\underbrace{\sum_{\substack{I\subseteq\left[  n\right]  ;\\I\subseteq C}%
}}_{\substack{=\sum_{I\subseteq C}\\\text{(since }C\subseteq\left[  n\right]
\text{)}}}\left(  -1\right)  ^{\left\vert I\right\vert -k}\dbinom{\left\vert
I\right\vert }{k}\underbrace{\left[  I\subseteq C\right]  }%
_{\substack{=1\\\text{(since }I\subseteq C\text{)}}}+\sum
_{\substack{I\subseteq\left[  n\right]  ;\\\text{not }I\subseteq C}}\left(
-1\right)  ^{\left\vert I\right\vert -k}\dbinom{\left\vert I\right\vert }%
{k}\underbrace{\left[  I\subseteq C\right]  }_{\substack{=0\\\text{(since we
don't have }I\subseteq C\text{)}}}\\
&  =\sum_{I\subseteq C}\left(  -1\right)  ^{\left\vert I\right\vert -k}%
\dbinom{\left\vert I\right\vert }{k}+\underbrace{\sum_{\substack{I\subseteq
\left[  n\right]  ;\\\text{not }I\subseteq C}}\left(  -1\right)  ^{\left\vert
I\right\vert -k}\dbinom{\left\vert I\right\vert }{k}0}_{=0}=\underbrace{\sum
_{I\subseteq C}}_{=\sum_{j\in\mathbb{N}}\sum_{\substack{I\subseteq
C;\\\left\vert I\right\vert =j}}}\left(  -1\right)  ^{\left\vert I\right\vert
-k}\dbinom{\left\vert I\right\vert }{k}\\
&  =\sum_{j\in\mathbb{N}}\sum_{\substack{I\subseteq C;\\\left\vert
I\right\vert =j}}\underbrace{\left(  -1\right)  ^{\left\vert I\right\vert
-k}\dbinom{\left\vert I\right\vert }{k}}_{\substack{=\left(  -1\right)
^{j-k}\dbinom{j}{k}\\\text{(since }\left\vert I\right\vert =j\text{)}}%
}=\sum_{j\in\mathbb{N}}\underbrace{\sum_{\substack{I\subseteq C;\\\left\vert
I\right\vert =j}}\left(  -1\right)  ^{j-k}\dbinom{j}{k}}_{=\left(  \text{the
number of all subsets }I\text{ of }C\text{ satisfying }\left\vert I\right\vert
=j\right)  \left(  -1\right)  ^{j-k}\dbinom{j}{k}}\\
&  =\sum_{j\in\mathbb{N}}\underbrace{\left(  \text{the number of all subsets
}I\text{ of }C\text{ satisfying }\left\vert I\right\vert =j\right)
}_{\substack{=\left(  \text{the number of all }j\text{-element subsets of
}C\right)  =\dbinom{\left\vert C\right\vert }{j}\\\text{(by the combinatorial
interpretation of the binomial coefficients)}}}\left(  -1\right)
^{j-k}\dbinom{j}{k}\\
&  =\sum_{j\in\mathbb{N}}\dbinom{\left\vert C\right\vert }{j}\left(
-1\right)  ^{j-k}\dbinom{j}{k}=\sum_{j\in\mathbb{N}}\left(  -1\right)
^{j-k}\dbinom{\left\vert C\right\vert }{j}\dbinom{j}{k}%
\end{align*}%
\begin{align*}
&  =\sum_{j=0}^{\left\vert C\right\vert }\underbrace{\left(  -1\right)
^{j-k}}_{=\left(  -1\right)  ^{j+k}=\left(  -1\right)  ^{j}\left(  -1\right)
^{k}}\dbinom{\left\vert C\right\vert }{j}\dbinom{j}{k}+\sum_{j=\left\vert
C\right\vert +1}^{\infty}\left(  -1\right)  ^{j-k}\underbrace{\dbinom
{\left\vert C\right\vert }{j}}_{\substack{=0\\\text{(by Proposition
\ref{prop.binom.0},}\\\text{applied to }\left\vert C\right\vert \text{ and
}j\\\text{instead of }m\text{ and }n\text{ (since }\left\vert C\right\vert
<j\\\text{(because }j\geq\left\vert C\right\vert +1>\left\vert C\right\vert
\text{)))}}}\dbinom{j}{k}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have split the summation at
}j=\left\vert C\right\vert \right) \\
&  =\sum_{j=0}^{\left\vert C\right\vert }\left(  -1\right)  ^{j}\left(
-1\right)  ^{k}\dbinom{\left\vert C\right\vert }{j}\dbinom{j}{k}%
+\underbrace{\sum_{j=\left\vert C\right\vert +1}^{\infty}\left(  -1\right)
^{j-k}0\dbinom{j}{k}}_{=0}\\
&  =\sum_{j=0}^{\left\vert C\right\vert }\left(  -1\right)  ^{j}\left(
-1\right)  ^{k}\dbinom{\left\vert C\right\vert }{j}\dbinom{j}{k}=\left(
-1\right)  ^{k}\underbrace{\sum_{j=0}^{\left\vert C\right\vert }\left(
-1\right)  ^{j}\dbinom{\left\vert C\right\vert }{j}\dbinom{j}{k}%
}_{\substack{=\left(  -1\right)  ^{k}\left[  \left\vert C\right\vert
=k\right]  \\\text{(by Corollary \ref{cor.binom.1-1cor2},}\\\text{applied to
}\left\vert C\right\vert \text{ and }k\text{ instead of }n\text{ and
}i\text{)}}}\\
&  =\underbrace{\left(  -1\right)  ^{k}\left(  -1\right)  ^{k}}_{=\left(
-1\right)  ^{2k}=1}\left[  \left\vert C\right\vert =k\right]  =\left[
\left\vert C\right\vert =k\right]  =\left[  s\in S_{k}\right]
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{pf.lem.pie.dan.1.2})}\right)  .
\end{align*}
This proves Lemma \ref{lem.pie.dan.1}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.pie.dan}.]For every subset $I$ of $\left[
n\right]  $, the intersection $\bigcap_{i\in I}A_{i}$ is a subset of
$S$\ \ \ \ \footnote{In fact, this is obvious when $I$ is nonempty (because
all the $A_{i}$ are subsets of $S$), but it also holds when $I$ is empty
(because in this case, the intersection $\bigcap_{i\in I}A_{i}=\bigcap
_{i\in\varnothing}A_{i}$ is defined to be $S$).}. Thus, for every subset $I$
of $\left[  n\right]  $, we have%
\[
\left\vert \bigcap_{i\in I}A_{i}\right\vert =\sum_{s\in S}\left[  s\in
\bigcap_{i\in I}A_{i}\right]
\]
(by Lemma \ref{lem.iverson.card}, applied to $T=\bigcap_{i\in I}A_{i}$).
Hence,%
\begin{align*}
&  \sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{\left\vert
I\right\vert -k}\dbinom{\left\vert I\right\vert }{k}\underbrace{\left\vert
\bigcap_{i\in I}A_{i}\right\vert }_{=\sum_{s\in S}\left[  s\in\bigcap_{i\in
I}A_{i}\right]  }\\
&  =\sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{\left\vert
I\right\vert -k}\dbinom{\left\vert I\right\vert }{k}\sum_{s\in S}\left[
s\in\bigcap_{i\in I}A_{i}\right]  =\underbrace{\sum_{I\subseteq\left[
n\right]  }\sum_{s\in S}}_{=\sum_{s\in S}\sum_{I\subseteq\left[  n\right]  }%
}\left(  -1\right)  ^{\left\vert I\right\vert -k}\dbinom{\left\vert
I\right\vert }{k}\left[  s\in\bigcap_{i\in I}A_{i}\right] \\
&  =\sum_{s\in S}\underbrace{\sum_{I\subseteq\left[  n\right]  }\left(
-1\right)  ^{\left\vert I\right\vert -k}\dbinom{\left\vert I\right\vert }%
{k}\left[  s\in\bigcap_{i\in I}A_{i}\right]  }_{\substack{=\left[  s\in
S_{k}\right]  \\\text{(by Lemma \ref{lem.pie.dan.1})}}}=\sum_{s\in S}\left[
s\in S_{k}\right]  .
\end{align*}
Comparing this with $\left\vert S_{k}\right\vert =\sum_{s\in S}\left[  s\in
S_{k}\right]  $ (which follows from Lemma \ref{lem.iverson.card}, applied to
$T=S_{k}$), we obtain
\[
\left\vert S_{k}\right\vert =\sum_{I\subseteq\left[  n\right]  }\left(
-1\right)  ^{\left\vert I\right\vert -k}\dbinom{\left\vert I\right\vert }%
{k}\left\vert \bigcap_{i\in I}A_{i}\right\vert .
\]
This solves Exercise \ref{exe.pie.dan}.
\end{proof}

\subsection{Summing fixed point numbers of permutations}

Recall that for any $n\in\mathbb{N}$, we let $S_{n}$ denote the set of all
permutations of $\left[  n\right]  $.

If $S$ is a finite set, and if $f:S\rightarrow S$ is a map, then we let
$\operatorname*{Fix}f$ denote the set of all fixed points of $f$. (That is,
$\operatorname*{Fix}f=\left\{  s\in S\ \mid\ f\left(  s\right)  =s\right\}  $.)

\begin{exercise}
\label{exe.perm.sumFix}Let $n$ be a positive integer. Prove that $\sum_{w\in
S_{n}}\left\vert \operatorname*{Fix}w\right\vert =n!$.

[\textbf{Hint:} Rewrite $\left\vert \operatorname*{Fix}w\right\vert $ as
$\sum_{i\in\left[  n\right]  }\left[  w\left(  i\right)  =i\right]  $.]
\end{exercise}

(In other words, this exercise states that the average number of fixed points
of a permutation of $\left[  n\right]  $ is $1$.)

Exercise \ref{exe.perm.sumFix} was Problem 1 at
\href{http://artofproblemsolving.com/wiki/index.php?title=1987_IMO_Problems/Problem_1}{the
International Mathematical Olympiad (IMO) 1987}.

Our solution to Exercise \ref{exe.perm.sumFix} relies on the following facts:

\begin{lemma}
\label{lem.perm.sumFix.m!}Let $m\in\mathbb{N}$. Let $G$ be an $m$-element set.
Then, the number of all permutations of $G$ is $m!$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.perm.sumFix.m!} (sketched).]There is a bijection
$\alpha:G\rightarrow\left[  m\right]  $ (since $G$ is an $m$-element set). Fix
such an $\alpha$. Then, the map%
\begin{align*}
\left\{  \text{permutations of }G\right\}   &  \rightarrow\left\{
\text{permutations of }\left[  m\right]  \right\}  ,\\
\sigma &  \mapsto\alpha\circ\sigma\circ\alpha^{-1}%
\end{align*}
is also a bijection\footnote{This is straightforward to verify.}. Hence,
\begin{align*}
\left\vert \left\{  \text{permutations of }G\right\}  \right\vert  &
=\left\vert \left\{  \text{permutations of }\left[  m\right]  \right\}
\right\vert \\
&  =\left(  \text{the number of all permutations of }\left[  m\right]
\right)  =m!.
\end{align*}
In other words, the number of all permutations of $G$ is $m!$. This proves
Lemma \ref{lem.perm.sumFix.m!}.
\end{proof}

\begin{lemma}
\label{lem.perm.sumFix.1}Let $n$ be a positive integer. Let $i\in\left[
n\right]  $. Then, the number of all permutations $w\in S_{n}$ satisfying
$w\left(  i\right)  =i$ is $\left(  n-1\right)  !$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.perm.sumFix.1} (sketched).]Roughly speaking, a
permutation $w\in S_{n}$ satisfying $w\left(  i\right)  =i$ is
\textquotedblleft nothing but\textquotedblright\ a permutation of the $\left(
n-1\right)  $-element set $\left[  n\right]  \setminus\left\{  i\right\}  $
(because it has to map $i$ to $i$, and therefore must map the remaining
elements of $\left[  n\right]  $ to elements other than $i$). This is not
rigorous, because strictly speaking a permutation of $\left[  n\right]  $
cannot be a permutation of $\left[  n\right]  \setminus\left\{  i\right\}  $
(after all, the former has domain $\left[  n\right]  $ while the latter only
has domain $\left[  n\right]  \setminus\left\{  i\right\}  $). Here is a
rigorous version of the above statement:

To each permutation $w\in S_{n}$ satisfying $w\left(  i\right)  =i$, we can
assign a permutation $\widetilde{w}$ of $\left[  n\right]  \setminus\left\{
i\right\}  $ by letting%
\[
\widetilde{w}\left(  p\right)  =w\left(  p\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }p\in\left[  n\right]  \setminus\left\{
i\right\}  .
\]
This defines a map%
\begin{align}
A:\left\{  w\in S_{n}\ \mid\ w\left(  i\right)  =i\right\}   &  \rightarrow
\left\{  \text{permutations of }\left[  n\right]  \setminus\left\{  i\right\}
\right\}  ,\nonumber\\
w  &  \mapsto\widetilde{w}. \label{pf.lem.perm.sumFix.1.1}%
\end{align}
Conversely, to each permutation $u$ of $\left[  n\right]  \setminus\left\{
i\right\}  $, we can assign a permutation $\widehat{u}\in S_{n}$ satisfying
$\widehat{u}\left(  i\right)  =i$ by setting%
\[
\widehat{u}\left(  p\right)  =%
\begin{cases}
u\left(  p\right)  , & \text{if }p\neq i;\\
i, & \text{if }p=i
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for each }p\in\left[  n\right]  .
\]
This defines a map%
\begin{align*}
B:\left\{  \text{permutations of }\left[  n\right]  \setminus\left\{
i\right\}  \right\}   &  \rightarrow\left\{  w\in S_{n}\ \mid\ w\left(
i\right)  =i\right\}  ,\\
u  &  \mapsto\widehat{u}.
\end{align*}
The maps $A$ and $B$ are well-defined and mutually inverse\footnote{This is
straightforward to check (just remember that permutations are bijective).}.
Thus, there is a bijection from the set $\left\{  w\in S_{n}\ \mid\ w\left(
i\right)  =i\right\}  $ to the set $\left\{  \text{permutations of }\left[
n\right]  \setminus\left\{  i\right\}  \right\}  $ (namely, $A$). Hence,%
\begin{align*}
\left\vert \left\{  w\in S_{n}\ \mid\ w\left(  i\right)  =i\right\}
\right\vert  &  =\left\vert \left\{  \text{permutations of }\left[  n\right]
\setminus\left\{  i\right\}  \right\}  \right\vert \\
&  =\left(  \text{the number of all permutations of }\left[  n\right]
\setminus\left\{  i\right\}  \right) \\
&  =\left(  n-1\right)  !
\end{align*}
(by Lemma \ref{lem.perm.sumFix.m!} (applied to $G=\left[  n\right]
\setminus\left\{  i\right\}  $ and $m=n-1$), because $\left[  n\right]
\setminus\left\{  i\right\}  $ is an $\left(  n-1\right)  $-element set). In
other words, the number of all permutations $w\in S_{n}$ satisfying $w\left(
i\right)  =i$ is $\left(  n-1\right)  !$. This proves Lemma
\ref{lem.perm.sumFix.1}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.perm.sumFix} (sketched).]If $w\in S_{n}$ and
$i\in\left[  n\right]  $, then%
\begin{equation}
\left[  i\in\operatorname*{Fix}w\right]  =\left[  w\left(  i\right)
=i\right]  \label{sol.exe.perm.sumFix.1}%
\end{equation}
\footnote{because of the equivalence $\left(  i\in\operatorname*{Fix}w\right)
\ \Longleftrightarrow\ \left(  i\text{ is a fixed point of }w\right)
\ \Longleftrightarrow\ \left(  w\left(  i\right)  =i\right)  $}.

If $w\in S_{n}$, then $\operatorname*{Fix}w$ is a subset of $\left[  n\right]
$, and therefore Lemma \ref{lem.iverson.card} (applied to $S=\left[  n\right]
$ and $T=\operatorname*{Fix}w$) yields%
\begin{align}
\left\vert \operatorname*{Fix}w\right\vert  &  =\sum_{s\in\left[  n\right]
}\left[  s\in\operatorname*{Fix}w\right]  =\sum_{i\in\left[  n\right]
}\underbrace{\left[  i\in\operatorname*{Fix}w\right]  }_{\substack{=\left[
w\left(  i\right)  =i\right]  \\\text{(by (\ref{sol.exe.perm.sumFix.1}))}%
}}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have renamed the}\\
\text{summation index }s\text{ as }i
\end{array}
\right) \nonumber\\
&  =\sum_{i\in\left[  n\right]  }\left[  w\left(  i\right)  =i\right]  .
\label{sol.exe.perm.sumFix.2}%
\end{align}


But if $i\in\left[  n\right]  $, then $\left\{  w\in S_{n}\ \mid\ w\left(
i\right)  =i\right\}  $ is a subset of $S_{n}$, and therefore Lemma
\ref{lem.iverson.card} (applied to $S=S_{n}$ and $T=\left\{  w\in S_{n}%
\ \mid\ w\left(  i\right)  =i\right\}  $) yields%
\begin{align}
\left\vert \left\{  w\in S_{n}\ \mid\ w\left(  i\right)  =i\right\}
\right\vert  &  =\sum_{s\in S_{n}}\left[  \underbrace{s\in\left\{  w\in
S_{n}\ \mid\ w\left(  i\right)  =i\right\}  }_{\Longleftrightarrow\ \left(
s\left(  i\right)  =i\right)  }\right] \nonumber\\
&  =\sum_{s\in S_{n}}\left[  s\left(  i\right)  =i\right]  =\sum_{w\in S_{n}%
}\left[  w\left(  i\right)  =i\right]  \label{sol.exe.perm.sumFix.3}%
\end{align}
(here, we have renamed the summation index $s$ as $w$).

Now,
\begin{align*}
\sum_{w\in S_{n}}\underbrace{\left\vert \operatorname*{Fix}w\right\vert
}_{\substack{=\sum_{i\in\left[  n\right]  }\left[  w\left(  i\right)
=i\right]  \\\text{(by (\ref{sol.exe.perm.sumFix.2}))}}}  &  =\underbrace{\sum
_{w\in S_{n}}\sum_{i\in\left[  n\right]  }}_{=\sum_{i\in\left[  n\right]
}\sum_{w\in S_{n}}}\left[  w\left(  i\right)  =i\right]  =\sum_{i\in\left[
n\right]  }\underbrace{\sum_{w\in S_{n}}\left[  w\left(  i\right)  =i\right]
}_{\substack{=\left\vert \left\{  w\in S_{n}\ \mid\ w\left(  i\right)
=i\right\}  \right\vert \\\text{(by (\ref{sol.exe.perm.sumFix.3}))}}}\\
&  =\sum_{i\in\left[  n\right]  }\underbrace{\left\vert \left\{  w\in
S_{n}\ \mid\ w\left(  i\right)  =i\right\}  \right\vert }_{\substack{=\left(
\text{the number of all permutations }w\in S_{n}\text{ satisfying }w\left(
i\right)  =i\right)  \\=\left(  n-1\right)  !\\\text{(by Lemma
\ref{lem.perm.sumFix.1})}}}\\
&  =\sum_{i\in\left[  n\right]  }\left(  n-1\right)  !=\underbrace{\left\vert
\left[  n\right]  \right\vert }_{=n} \cdot\left(  n-1\right)  !=n\cdot\left(
n-1\right)  !=n!.
\end{align*}
This solves Exercise \ref{exe.perm.sumFix}.
\end{proof}

\begin{remark}
Exercise \ref{exe.perm.sumFix} can be generalized: If $n\in\mathbb{N}$ and
$k\in\mathbb{N}$ satisfy $n\geq k$, then
\[
\sum_{w\in S_{n}}\dbinom{\left\vert \operatorname*{Fix}w\right\vert }%
{k}=\left(  n-k\right)  !\dbinom{n}{k}=\dfrac{n!}{k!}.
\]
Do you see how the above solution can be extended to cover this generalization?
\end{remark}

\subsection{Transpositions $t_{1,i}$ generate permutations}

Recall a basic notation regarding permutations:

\begin{definition}
\label{def.transpos}Let $n\in\mathbb{N}$. Let $i$ and $j$ be two distinct
elements of $\left[  n\right]  $. We let $t_{i,j}$ be the permutation in
$S_{n}$ which switches $i$ with $j$ while leaving all other elements of
$\left[  n\right]  $ unchanged. Such a permutation is called a
\textit{transposition}.
\end{definition}

\begin{exercise}
\label{exe.t1i-gen-Sn}Let $n\in\mathbb{N}$. Prove that each permutation in
$S_{n}$ can be written as a composition of some of the transpositions
$t_{1,2},t_{1,3},\ldots,t_{1,n}$.

(Note that this composition can be empty -- in which case it is understood to
be $\operatorname*{id}$ --, and it can contain any given transposition
multiple times.)
\end{exercise}

To solve this exercise, we recall another definition:

\begin{definition}
Let $n\in\mathbb{N}$. Let $i\in\left[  n-1\right]  $. Then, $s_{i}$ denotes
the permutation $t_{i,i+1}\in S_{n}$.
\end{definition}

We shall use the following well-known fact (\cite[Exercise 5.1 \textbf{(b)}%
]{detnotes}):

\begin{lemma}
\label{lem.si-gen-Sn}Let $n\in\mathbb{N}$. Each permutation in $S_{n}$ can be
written as a composition of some of the transpositions $s_{1},s_{2}%
,\ldots,s_{n-1}$.
\end{lemma}

The following is easy to check:

\begin{lemma}
\label{lem.t1i-gen-si}Let $n\in\mathbb{N}$. Let $i\in\left[  n-1\right]  $ be
such that $i>1$. Then, $s_{i}=t_{1,i+1}\circ t_{1,i}\circ t_{1,i+1}$.
\end{lemma}

Lemma \ref{lem.t1i-gen-si} can be proven by straightforward verification (just
check how $s_{i}$ and $t_{1,i+1}\circ t_{1,i}\circ t_{1,i+1}$ transform a
given element of $\left[  n\right]  $, depending on whether this element is
$1$, $i$ or $i+1$ or something else). Let us give a slightly more skillful
argument. The following fact is simple and well-known (\cite[Exercise 5.17
\textbf{(a)}]{detnotes}):

\begin{lemma}
\label{lem.perm.cycles.a}Let $n\in\mathbb{N}$. Let $k\in\left[  n\right]  $.
For every $\sigma\in S_{n}$ and every $k$ distinct elements $i_{1}%
,i_{2},\ldots,i_{k}$ of $\left[  n\right]  $, we have%
\[
\sigma\circ\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}\circ
\sigma^{-1}=\operatorname*{cyc}\nolimits_{\sigma\left(  i_{1}\right)
,\sigma\left(  i_{2}\right)  ,\ldots,\sigma\left(  i_{k}\right)  }.
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.t1i-gen-si} (sketched).]From $i\in\left[  n-1\right]
$, we obtain $i\leq n-1$. But $i>1$, so that $i\geq2$, and thus $2\leq i\leq
n-1$. Hence, $n\geq3$. Thus, $2\in\left[  n\right]  $.

Clearly,
\begin{equation}
t_{u,v}=\operatorname*{cyc}\nolimits_{u,v} \label{pf.lem.t1-gen-si.1}%
\end{equation}
for any two distinct elements $u$ and $v$ of $\left[  n\right]  $. Applying
this to $u=1$ and $v=i$, we obtain $t_{1,i}=\operatorname*{cyc}\nolimits_{1,i}%
$.

Now, let $\sigma=t_{1,i+1}$. Thus, $\sigma\left(  1\right)  =i+1$ and
$\sigma\left(  i\right)  =i$ (since $i$ equals neither $1$ nor $i+1$). But
Lemma \ref{lem.perm.cycles.a} (applied to $k=2$, $i_{1}=1$ and $i_{2}=i$)
yields
\begin{equation}
\sigma\circ\operatorname*{cyc}\nolimits_{1,i}\circ\sigma^{-1}%
=\operatorname*{cyc}\nolimits_{\sigma\left(  1\right)  ,\sigma\left(
i\right)  }=\operatorname*{cyc}\nolimits_{i+1,i} \label{pf.lem.t1i-gen-si.4}%
\end{equation}
(since $\sigma\left(  1\right)  =i+1$ and $\sigma\left(  i\right)  =i$).

The permutation $\sigma$ is a transposition (since $\sigma=t_{1,i+1}$), and
hence an involution. In other words, $\sigma^{-1}=\sigma$.

But the definition of $s_{i}$ yields%
\begin{align*}
s_{i}  &  =t_{i,i+1}=\operatorname*{cyc}\nolimits_{i,i+1}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{pf.lem.t1-gen-si.1})}\right) \\
&  =\operatorname*{cyc}\nolimits_{i+1,i}=\underbrace{\sigma}_{=t_{1,i+1}}%
\circ\underbrace{\operatorname*{cyc}\nolimits_{1,i}}_{=t_{1,i}}\circ
\underbrace{\sigma^{-1}}_{=\sigma=t_{1,i+1}}\ \ \ \ \ \ \ \ \ \ \left(
\text{by (\ref{pf.lem.t1i-gen-si.4})}\right) \\
&  =t_{1,i+1}\circ t_{1,i}\circ t_{1,i+1}.
\end{align*}
This proves Lemma \ref{lem.t1i-gen-si}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.t1i-gen-Sn} (sketched).]We first show the
following fact:

\begin{statement}
\textit{Observation 1:} Let $i\in\left[  n-1\right]  $. Then, $s_{i}$ can be
written as a composition of some of the transpositions $t_{1,2},t_{1,3}%
,\ldots,t_{1,n}$.
\end{statement}

[\textit{Proof of Observation 1:} If $i>1$, then this follows immediately from
Lemma \ref{lem.t1i-gen-si}. Thus, for the rest of this proof, we WLOG assume
that we don't have $i>1$. Hence, $i=1$. Thus, $s_{i}=s_{1}=t_{1,2}$ (by the
definition of $s_{1}$). Thus, again it is clear that $s_{i}$ can be written as
a composition of some of the transpositions $t_{1,2},t_{1,3},\ldots,t_{1,n}$.
This proves Observation 1.]

Now, let $\sigma\in S_{n}$ be a permutation. We want to write $\sigma$ as a
composition of some of the transpositions $t_{1,2},t_{1,3},\ldots,t_{1,n}$.

First write $\sigma$ as a composition of some of the transpositions
$s_{1},s_{2},\ldots,s_{n-1}$. (This is possible according to Lemma
\ref{lem.si-gen-Sn}.) Next, write each of these transpositions $s_{1}%
,s_{2},\ldots,s_{n-1}$ as a composition of some of the transpositions
$t_{1,2},t_{1,3},\ldots,t_{1,n}$. (This is possible according to Observation
1.) The resulting expression is now a representation of $\sigma$ as a
composition of some of the transpositions $t_{1,2},t_{1,3},\ldots,t_{1,n}$.

Now, forget that we fixed $\sigma$. We thus have shown that each $\sigma\in
S_{n}$ has a representation as a composition of some of the transpositions
$t_{1,2},t_{1,3},\ldots,t_{1,n}$. This solves Exercise \ref{exe.t1i-gen-Sn}.
\end{proof}

\subsection{V-permutations as products of cycles}

Recall the following notation:

\begin{definition}
\label{def.cyc}Let $X$ be a set. Let $k$ be a positive integer. Let
$i_{1},i_{2},\ldots,i_{k}$ be $k$ distinct elements of $X$. We define
$\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}$ to be the
permutation of $X$ that sends $i_{1},i_{2},\ldots,i_{k}$ to $i_{2}%
,i_{3},\ldots,i_{k},i_{1}$, respectively, while leaving all other elements of
$X$ fixed. In other words, we define $\operatorname*{cyc}\nolimits_{i_{1}%
,i_{2},\ldots,i_{k}}$ to be the permutation of $X$ given by%
\[
\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}\left(  p\right)  =%
\begin{cases}
i_{j+1}, & \text{if }p=i_{j}\text{ for some }j\in\left\{  1,2,\ldots
,k\right\}  ;\\
p, & \text{otherwise}%
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for every }p\in X,
\]
where $i_{k+1}$ means $i_{1}$.
\end{definition}

\begin{exercise}
\label{exe.V-perm-as-cyc}Let $n\in\mathbb{N}$. For each $r\in\left[  n\right]
$, let $c_{r}$ denote the permutation $\operatorname*{cyc}%
\nolimits_{r,r-1,\ldots,2,1}\in S_{n}$. (Thus, $c_{1}=\operatorname*{cyc}%
\nolimits_{1}=\operatorname*{id}$ and $c_{2}=\operatorname*{cyc}%
\nolimits_{2,1}=s_{1}$.)

Let $G=\left\{  g_{1}<g_{2}<\cdots<g_{p}\right\}  $ be a subset of $\left[
n\right]  $. (The notation \textquotedblleft$G=\left\{  g_{1}<g_{2}%
<\cdots<g_{p}\right\}  $\textquotedblright\ is simultaneously saying that
$G=\left\{  g_{1},g_{2},\ldots,g_{p}\right\}  $ and that $g_{1}<g_{2}%
<\cdots<g_{p}$.)

Let $\sigma\in S_{n}$ be the permutation $c_{g_{1}}\circ c_{g_{2}}\circ
\cdots\circ c_{g_{p}}$.

Prove the following:

\textbf{(a)} We have $\sigma\left(  1\right)  >\sigma\left(  2\right)
>\cdots>\sigma\left(  p\right)  $.

\textbf{(b)} We have $\sigma\left(  \left[  p\right]  \right)  =G$.

\textbf{(c)} We have $\sigma\left(  p+1\right)  <\sigma\left(  p+2\right)
<\cdots<\sigma\left(  n\right)  $.

(Note that a chain of inequalities that involves less than two numbers is
considered to be vacuously true. For example, Exercise \ref{exe.V-perm-as-cyc}
\textbf{(c)} is vacuously true when $p=n-1$ and also when $p=n$.)
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.V-perm-as-cyc} (sketched).]For each
$r\in\left[  n\right]  $ and $i\in\left[  n\right]  $, we have%
\begin{equation}
c_{r}\left(  i\right)  =%
\begin{cases}
r, & \text{if }i=1;\\
i-1, & \text{if }1<i\leq r;\\
i, & \text{if }i>r
\end{cases}
\label{sol.V-perm-as-cyc.cri=}%
\end{equation}
(by the definition of $c_{r}$). Thus, each $r\in\left[  n\right]  $ satisfies%
\begin{equation}
c_{r}\left(  2\right)  <c_{r}\left(  3\right)  <\cdots<c_{r}\left(  n\right)
\label{sol.V-perm-as-cyc.crinc}%
\end{equation}
(because the one-line notation of the permutation $c_{r}$ is $\left(
r,1,2,\ldots,r-1,r+1,r+2,\ldots,n\right)  $, which shows immediately that
$c_{r}$ is strictly increasing on the set $\left\{  2,3,\ldots,n\right\}  $).
Moreover, each $r\in\left[  n\right]  $ and $i\in\left[  n\right]  $ satisfy%
\begin{equation}
c_{r}\left(  i\right)  \geq i-1. \label{sol.V-perm-as-cyc.crigeq}%
\end{equation}
(This is easy to check using (\ref{sol.V-perm-as-cyc.cri=}).)

We have $g_{1}<g_{2}<\cdots<g_{p}$. Define a further integer $g_{0}$ by
$g_{0}=0$. Then, the chain of inequalities $g_{1}<g_{2}<\cdots<g_{p}$ can be
extended to $g_{0}<g_{1}<\cdots<g_{p}$ (since each of $g_{1},g_{2}%
,\ldots,g_{p}$ is $>0=g_{0}$).

For each $q\in\left\{  0,1,\ldots,p\right\}  $, we let $\sigma_{q}$ denote the
permutation $c_{g_{1}}\circ c_{g_{2}}\circ\cdots\circ c_{g_{q}}\in S_{n}$.
Thus,%
\[
\sigma_{0}=c_{g_{1}}\circ c_{g_{2}}\circ\cdots\circ c_{g_{0}}=\left(
\text{empty composition of permutations}\right)  =\operatorname*{id}%
\]
and%
\[
\sigma_{p}=c_{g_{1}}\circ c_{g_{2}}\circ\cdots\circ c_{g_{p}}=\sigma.
\]


Notice that%
\begin{equation}
\sigma_{q}=\sigma_{q-1}\circ c_{g_{q}}\ \ \ \ \ \ \ \ \ \ \text{for each }%
q\in\left[  p\right]  \label{sol.V-perm-as-cyc.sigmaq-rec}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.V-perm-as-cyc.sigmaq-rec}):} Let
$q\in\left[  p\right]  $. Then, the definition of $\sigma_{q-1}$ yields
$\sigma_{q-1}=c_{g_{1}}\circ c_{g_{2}}\circ\cdots\circ c_{g_{q-1}}$. But the
definition of $\sigma_{q}$ yields%
\[
\sigma_{q}=c_{g_{1}}\circ c_{g_{2}}\circ\cdots\circ c_{g_{q}}%
=\underbrace{\left(  c_{g_{1}}\circ c_{g_{2}}\circ\cdots\circ c_{g_{q-1}%
}\right)  }_{=\sigma_{q-1}}\circ c_{g_{q}}=\sigma_{q-1}\circ c_{g_{q}}.
\]
This proves (\ref{sol.V-perm-as-cyc.sigmaq-rec}).}.

\begin{noncompile}
Hence, for each $q\in\left[  p\right]  $ and $i\in\left[  n\right]  $, we have%
\begin{equation}
\sigma_{q}\left(  i\right)  =%
\begin{cases}
\sigma_{q-1}\left(  g_{q}\right)  , & \text{if }i=1;\\
\sigma_{q-1}\left(  i-1\right)  , & \text{if }1<i\leq g_{q};\\
\sigma_{q-1}\left(  i\right)  , & \text{if }i>g_{q}%
\end{cases}
\label{sol.V-perm-as-cyc.sigmaqi=}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.V-perm-as-cyc.sigmaqi=}):} Let
$q\in\left[  p\right]  $ and $i\in\left[  n\right]  $. Then,
(\ref{sol.V-perm-as-cyc.cri=}) (applied to $r=g_{q}$) yields $c_{g_{q}}\left(
i\right)  =%
\begin{cases}
g_{q}, & \text{if }i=1;\\
i-1, & \text{if }1<i\leq g_{q};\\
i, & \text{if }i>g_{q}%
\end{cases}
$. Applying the map $\sigma_{q-1}$ to both sides of this equality, we find%
\[
\sigma_{q-1}\left(  c_{g_{q}}\left(  i\right)  \right)  =\sigma_{q-1}\left(
\begin{cases}
g_{q}, & \text{if }i=1;\\
i-1, & \text{if }1<i\leq g_{q};\\
i, & \text{if }i>g_{q}%
\end{cases}
\right)  =%
\begin{cases}
\sigma_{q-1}\left(  g_{q}\right)  , & \text{if }i=1;\\
\sigma_{q-1}\left(  i-1\right)  , & \text{if }1<i\leq g_{q};\\
\sigma_{q-1}\left(  i\right)  , & \text{if }i>g_{q}%
\end{cases}
.
\]
Comparing this with%
\[
\sigma_{q-1}\left(  c_{g_{q}}\left(  i\right)  \right)  =\underbrace{\left(
\sigma_{q-1}\circ c_{g_{q}}\right)  }_{\substack{=\sigma_{q}\\\text{(by
(\ref{sol.V-perm-as-cyc.sigmaq-rec}))}}}\left(  i\right)  =\sigma_{q}\left(
i\right)  ,
\]
we obtain $\sigma_{q}\left(  i\right)  =%
\begin{cases}
\sigma_{q-1}\left(  g_{q}\right)  , & \text{if }i=1;\\
\sigma_{q-1}\left(  i-1\right)  , & \text{if }1<i\leq g_{q};\\
\sigma_{q-1}\left(  i\right)  , & \text{if }i>g_{q}%
\end{cases}
$. Thus, (\ref{sol.V-perm-as-cyc.sigmaqi=}) is proven.}.
\end{noncompile}

Now, we claim the following:

\begin{statement}
\textit{Observation 1:} For each $q\in\left\{  0,1,\ldots,p\right\}  $, the
following holds:

\textbf{(a)} We have $\sigma_{q}\left(  i\right)  =g_{q+1-i}$ for each
$i\in\left[  q\right]  $.

\textbf{(b)} We have $\sigma_{q}\left(  j\right)  =j$ for each $j\in\left[
n\right]  $ satisfying $j>g_{q}$.

\textbf{(c)} We have $\sigma_{q}\left(  q+1\right)  <\sigma_{q}\left(
q+2\right)  <\cdots<\sigma_{q}\left(  n\right)  $.

\textbf{(d)} We have $g_{q}\geq q$.
\end{statement}

[\textit{Proof of Observation 1:} We shall prove Observation 1 by
induction:\footnote{It is rather important to prove the four parts of
Observation 1 \textbf{together}, rather than trying to prove them separately.
This way, they can \textquotedblleft lend each other a hand\textquotedblright%
\ in the induction step (as we will see below).}

\textit{Induction base:} Let us prove Observation 1 for $q=0$. To do so, we
must prove the following four statements:

\begin{statement}
\textbf{(a}$_{\text{\textbf{0}}}$\textbf{)} We have $\sigma_{0}\left(
i\right)  =g_{0+1-i}$ for each $i\in\left[  0\right]  $.
\end{statement}

\begin{statement}
\textbf{(b}$_{\text{\textbf{0}}}$\textbf{)} We have $\sigma_{0}\left(
j\right)  =j$ for each $j\in\left[  n\right]  $ satisfying $j>g_{0}$.
\end{statement}

\begin{statement}
\textbf{(c}$_{\text{\textbf{0}}}$\textbf{)} We have $\sigma_{0}\left(
0+1\right)  <\sigma_{0}\left(  0+2\right)  <\cdots<\sigma_{0}\left(  n\right)
$.
\end{statement}

\begin{statement}
\textbf{(d}$_{\text{\textbf{0}}}$\textbf{)} We have $g_{0}\geq0$.
\end{statement}

But all of these four statements are obvious. Indeed, \textbf{(a}%
$_{\text{\textbf{0}}}$\textbf{)} is vacuously true (since there exist no
$i\in\left[  0\right]  $); furthermore, \textbf{(b}$_{\text{\textbf{0}}}%
$\textbf{)} and \textbf{(c}$_{\text{\textbf{0}}}$\textbf{)} are obvious (since
$\sigma_{0}=\operatorname*{id}$); finally, \textbf{(d}$_{\text{\textbf{0}}}%
$\textbf{)} follows from $g_{0}=0$. Thus, Observation 1 has been proven for
$q=0$. This completes the induction base.

\textit{Induction step:} Let $h\in\left[  p\right]  $. Assume that Observation
1 holds for $q=h-1$. We must now prove that Observation 1 holds for $q=h$.

We have assumed that Observation 1 holds for $q=h-1$. In other words, the
following four statements hold:

\begin{statement}
\textbf{(a}$_{\text{\textbf{1}}}$\textbf{)} We have $\sigma_{h-1}\left(
i\right)  =g_{\left(  h-1\right)  +1-i}$ for each $i\in\left[  h-1\right]  $.
\end{statement}

\begin{statement}
\textbf{(b}$_{\text{\textbf{1}}}$\textbf{)} We have $\sigma_{h-1}\left(
j\right)  =j$ for each $j\in\left[  n\right]  $ satisfying $j>g_{h-1}$.
\end{statement}

\begin{statement}
\textbf{(c}$_{\text{\textbf{1}}}$\textbf{)} We have $\sigma_{h-1}\left(
h\right)  <\sigma_{h-1}\left(  h+1\right)  <\cdots<\sigma_{h-1}\left(
n\right)  $.
\end{statement}

\begin{statement}
\textbf{(d}$_{\text{\textbf{1}}}$\textbf{)} We have $g_{h-1}\geq h-1$.
\end{statement}

We must prove that Observation 1 holds for $q=h$. In other words, we must
prove the following four statements:

\begin{statement}
\textbf{(a}$_{\text{\textbf{2}}}$\textbf{)} We have $\sigma_{h}\left(
i\right)  =g_{h+1-i}$ for each $i\in\left[  h\right]  $.
\end{statement}

\begin{statement}
\textbf{(b}$_{\text{\textbf{2}}}$\textbf{)} We have $\sigma_{h}\left(
j\right)  =j$ for each $j\in\left[  n\right]  $ satisfying $j>g_{h}$.
\end{statement}

\begin{statement}
\textbf{(c}$_{\text{\textbf{2}}}$\textbf{)} We have $\sigma_{h}\left(
h+1\right)  <\sigma_{h}\left(  h+2\right)  <\cdots<\sigma_{h}\left(  n\right)
$.
\end{statement}

\begin{statement}
\textbf{(d}$_{\text{\textbf{2}}}$\textbf{)} We have $g_{h}\geq h$.
\end{statement}

Recall that $g_{0}<g_{1}<\cdots<g_{p}$. Thus, $g_{h-1}<g_{h}$, so that
$g_{h}>g_{h-1}$. Thus, $g_{h}\geq g_{h-1}+1$ (since $g_{h}$ and $g_{h-1}$ are
integers). But \textbf{(d}$_{\text{\textbf{1}}}$\textbf{)} yields $g_{h-1}\geq
h-1$, so that $g_{h-1}+1\geq h$. Hence, $g_{h}\geq g_{h-1}+1\geq h$. This
proves statement \textbf{(d}$_{\text{\textbf{2}}}$\textbf{)}.

Let $r=g_{h}$. Thus, $r\in\left[  n\right]  $ (since $h\in\left[  p\right]  $
and thus $g_{h}\in\left[  n\right]  $). Applying
(\ref{sol.V-perm-as-cyc.sigmaq-rec}) to $q=h$, we obtain
\[
\sigma_{h}=\sigma_{h-1}\circ c_{g_{h}}=\sigma_{h-1}\circ c_{r}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }g_{h}=r\right)  .
\]


Statement \textbf{(c}$_{\text{\textbf{2}}}$\textbf{)} is easy to derive from
statement \textbf{(c}$_{\text{\textbf{1}}}$\textbf{)} with the help of
(\ref{sol.V-perm-as-cyc.crinc})\footnote{\textit{Proof.} We want to prove
statement \textbf{(c}$_{\text{\textbf{2}}}$\textbf{)}. In other words, we want
to prove that $\sigma_{h}\left(  h+1\right)  <\sigma_{h}\left(  h+2\right)
<\cdots<\sigma_{h}\left(  n\right)  $. In other words, we want to prove that
$\sigma_{h}\left(  k\right)  <\sigma_{h}\left(  k+1\right)  $ for each
$k\in\left\{  h+1,h+2,\ldots,n-1\right\}  $. So let us fix $k\in\left\{
h+1,h+2,\ldots,n-1\right\}  $. We must prove $\sigma_{h}\left(  k\right)
<\sigma_{h}\left(  k+1\right)  $.
\par
We have $k\in\left\{  h+1,h+2,\ldots,n-1\right\}  $. Thus, $k\geq h+1\geq2$
(since $h\geq1$). But (\ref{sol.V-perm-as-cyc.crinc}) yields $c_{r}\left(
2\right)  <c_{r}\left(  3\right)  <\cdots<c_{r}\left(  n\right)  $. Thus,
$c_{r}\left(  k\right)  <c_{r}\left(  k+1\right)  $ (since $k\geq2$).
\par
Also, (\ref{sol.V-perm-as-cyc.crigeq}) yields $c_{r}\left(  k\right)  \geq
k-1\geq h$ (since $k\geq h+1$). Thus, $c_{r}\left(  k\right)  \in\left\{
h,h+1,\ldots,n\right\}  $.
\par
Also, (\ref{sol.V-perm-as-cyc.crigeq}) yields $c_{r}\left(  k+1\right)
\geq\left(  k+1\right)  -1=k\geq k-1\geq h$. Thus, $c_{r}\left(  k+1\right)
\in\left\{  h,h+1,\ldots,n\right\}  $.
\par
Statement \textbf{(c}$_{\text{\textbf{1}}}$\textbf{)} says that the map
$\sigma_{h-1}$ is strictly increasing on the set $\left\{  h,h+1,\ldots
,n\right\}  $. In other words, if $u$ and $v$ are two elements of $\left\{
h,h+1,\ldots,n\right\}  $ satisfying $u<v$, then $\sigma_{h-1}\left(
u\right)  <\sigma_{h-1}\left(  v\right)  $. Applying this to $u=c_{r}\left(
k\right)  $ and $v=c_{r}\left(  k+1\right)  $, we obtain $\sigma_{h-1}\left(
c_{r}\left(  k\right)  \right)  <\sigma_{h-1}\left(  c_{r}\left(  k+1\right)
\right)  $ (since $c_{r}\left(  k\right)  <c_{r}\left(  k+1\right)  $, and
since both $c_{r}\left(  k\right)  $ and $c_{r}\left(  k+1\right)  $ are
elements of $\left\{  h,h+1,\ldots,n\right\}  $).
\par
But $\sigma_{h}=\sigma_{h-1}\circ c_{r}$, and thus
\[
\sigma_{h}\left(  k\right)  =\left(  \sigma_{h-1}\circ c_{r}\right)  \left(
k\right)  =\sigma_{h-1}\left(  c_{r}\left(  k\right)  \right)  <\sigma
_{h-1}\left(  c_{r}\left(  k+1\right)  \right)  =\underbrace{\left(
\sigma_{h-1}\circ c_{r}\right)  }_{=\sigma_{h}}\left(  k+1\right)  =\sigma
_{h}\left(  k+1\right)  .
\]
This completes our proof of statement \textbf{(c}$_{\text{\textbf{2}}}%
$\textbf{)}.}.

Statement \textbf{(b}$_{\text{\textbf{2}}}$\textbf{)} easily follows from
statement \textbf{(b}$_{\text{\textbf{1}}}$\textbf{)} with the help of
(\ref{sol.V-perm-as-cyc.cri=})\footnote{\textit{Proof.} Let $j\in\left[
n\right]  $ be such that $j>g_{h}$. We want to show that $\sigma_{h}\left(
j\right)  =j$.
\par
We have $j>g_{h}=r$. Thus, (\ref{sol.V-perm-as-cyc.cri=}) (applied to $i=j$)
simplifies to $c_{r}\left(  j\right)  =j$. But $j>g_{h}>g_{h-1}$; therefore,
statement \textbf{(b}$_{\text{\textbf{1}}}$\textbf{)} yields $\sigma
_{h-1}\left(  j\right)  =j$.
\par
Now, recall that $\sigma_{h}=\sigma_{h-1}\circ c_{r}$. Hence,%
\[
\sigma_{h}\left(  j\right)  =\left(  \sigma_{h-1}\circ c_{r}\right)  \left(
j\right)  =\sigma_{h-1}\left(  \underbrace{c_{r}\left(  j\right)  }%
_{=j}\right)  =\sigma_{h-1}\left(  j\right)  =j.
\]
This proves statement \textbf{(b}$_{\text{\textbf{2}}}$\textbf{)}.}.

Applying (\ref{sol.V-perm-as-cyc.cri=}) to $i=1$, we obtain $c_{r}\left(
1\right)  =r=g_{h}>g_{h-1}$. Hence, statement \textbf{(b}$_{\text{\textbf{1}}%
}$\textbf{)} (applied to $j=c_{r}\left(  1\right)  $) yields $\sigma
_{h-1}\left(  c_{r}\left(  1\right)  \right)  =c_{r}\left(  1\right)  =g_{h}$.
But from $\sigma_{h}=\sigma_{h-1}\circ c_{r}$, we obtain%
\begin{equation}
\sigma_{h}\left(  1\right)  =\left(  \sigma_{h-1}\circ c_{r}\right)  \left(
1\right)  =\sigma_{h-1}\left(  c_{r}\left(  1\right)  \right)  =g_{h}%
=g_{h+1-1}. \label{sol.V-perm-as-cyc.a2.pf.1}%
\end{equation}


Finally, statement \textbf{(a}$_{\text{\textbf{2}}}$\textbf{)} can be derived
from statement \textbf{(a}$_{\text{\textbf{1}}}$\textbf{)} using
(\ref{sol.V-perm-as-cyc.a2.pf.1})\footnote{\textit{Proof.} Let us prove
statement \textbf{(a}$_{\text{\textbf{2}}}$\textbf{)}. In other words, let us
prove that $\sigma_{h}\left(  i\right)  =g_{h+1-i}$ for each $i\in\left[
h\right]  $.
\par
Indeed, let $i\in\left[  h\right]  $. We must prove that $\sigma_{h}\left(
i\right)  =g_{h+1-i}$.
\par
If $i=1$, then this follows from (\ref{sol.V-perm-as-cyc.a2.pf.1}). Hence, for
the rest of this proof, we WLOG assume that $i\neq1$. Thus, $i>1$. Combined
with $i\in\left[  h\right]  $, this yields $i\in\left\{  2,3,\ldots,h\right\}
$, so that $i-1\in\left[  h-1\right]  $. Therefore, statement \textbf{(a}%
$_{\text{\textbf{1}}}$\textbf{)} (applied to $i-1$ instead of $i$) yields
$\sigma_{h-1}\left(  i-1\right)  =g_{\left(  h-1\right)  +1-\left(
i-1\right)  }=g_{h+1-i}$ (since $\left(  h-1\right)  +1-\left(  i-1\right)
=h+1-i$).
\par
But $i\in\left\{  2,3,\ldots,h\right\}  $, so that $1<i\leq h\leq r$ (because
$r=g_{h}\geq h$). The equality (\ref{sol.V-perm-as-cyc.cri=}) simplifies to
$c_{r}\left(  i\right)  =i-1$ (since $1<i\leq r$). Now, recall that
$\sigma_{h}=\sigma_{h-1}\circ c_{r}$. Thus,%
\[
\sigma_{h}\left(  i\right)  =\left(  \sigma_{h-1}\circ c_{r}\right)  \left(
i\right)  =\sigma_{h-1}\left(  \underbrace{c_{r}\left(  i\right)  }%
_{=i-1}\right)  =\sigma_{h-1}\left(  i-1\right)  =g_{h+1-i}.
\]
Thus, $\sigma_{h}\left(  i\right)  =g_{h+1-i}$ is proven, as we wanted. This
completes the proof of statement \textbf{(a}$_{\text{\textbf{2}}}$\textbf{)}.}.

We have now proven all four statements \textbf{(a}$_{\text{\textbf{2}}}%
$\textbf{)}, \textbf{(b}$_{\text{\textbf{2}}}$\textbf{)}, \textbf{(c}%
$_{\text{\textbf{2}}}$\textbf{)} and \textbf{(d}$_{\text{\textbf{2}}}%
$\textbf{)}. Thus, Observation 1 holds for $q=h$. This completes the induction
step; thus, Observation 1 is proven.]

Now, we can apply Observation 1 to $q=p$. As a result, we obtain the following
four statements:

\begin{statement}
\textbf{(a}$_{\text{\textbf{3}}}$\textbf{)} We have $\sigma_{p}\left(
i\right)  =g_{p+1-i}$ for each $i\in\left[  p\right]  $.
\end{statement}

\begin{statement}
\textbf{(b}$_{\text{\textbf{3}}}$\textbf{)} We have $\sigma_{p}\left(
j\right)  =j$ for each $j\in\left[  n\right]  $ satisfying $j>g_{p}$.
\end{statement}

\begin{statement}
\textbf{(c}$_{\text{\textbf{3}}}$\textbf{)} We have $\sigma_{p}\left(
p+1\right)  <\sigma_{p}\left(  p+2\right)  <\cdots<\sigma_{p}\left(  n\right)
$.
\end{statement}

\begin{statement}
\textbf{(d}$_{\text{\textbf{3}}}$\textbf{)} We have $g_{p}\geq p$.
\end{statement}

Statement \textbf{(c}$_{\text{\textbf{3}}}$\textbf{)} says that $\sigma
_{p}\left(  p+1\right)  <\sigma_{p}\left(  p+2\right)  <\cdots<\sigma
_{p}\left(  n\right)  $. In view of $\sigma_{p}=\sigma$, this rewrites as
$\sigma\left(  p+1\right)  <\sigma\left(  p+2\right)  <\cdots<\sigma\left(
n\right)  $. This solves Exercise \ref{exe.V-perm-as-cyc} \textbf{(c)}.

Statement \textbf{(a}$_{\text{\textbf{3}}}$\textbf{)} says that $\sigma
_{p}\left(  i\right)  =g_{p+1-i}$ for each $i\in\left[  p\right]  $. In view
of $\sigma_{p}=\sigma$, this rewrites as
\begin{equation}
\sigma\left(  i\right)  =g_{p+1-i}\ \ \ \ \ \ \ \ \ \ \text{for each }%
i\in\left[  p\right]  . \label{sol.V-perm-as-cyc.sigmai}%
\end{equation}
In other words,%
\begin{equation}
\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
p\right)  \right)  =\left(  g_{p},g_{p-1},\ldots,g_{1}\right)  .
\label{sol.V-perm-as-cyc.sigmais}%
\end{equation}
Hence,%
\[
\left\{  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots
,\sigma\left(  p\right)  \right\}  =\left\{  g_{p},g_{p-1},\ldots
,g_{1}\right\}  =\left\{  g_{1},g_{2},\ldots,g_{p}\right\}  =G
\]
(since $G=\left\{  g_{1}<g_{2}<\cdots<g_{p}\right\}  =\left\{  g_{1}%
,g_{2},\ldots,g_{p}\right\}  $). Hence%
\[
\sigma\left(  \underbrace{\left[  p\right]  }_{=\left\{  1,2,\ldots,p\right\}
}\right)  =\sigma\left(  \left\{  1,2,\ldots,p\right\}  \right)  =\left\{
\sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
p\right)  \right\}  =G.
\]
This solves Exercise \ref{exe.V-perm-as-cyc} \textbf{(b)}.

Finally, recall that $g_{1}<g_{2}<\cdots<g_{p}$. In other words,
$g_{p}>g_{p-1}>\cdots>g_{1}$. In view of (\ref{sol.V-perm-as-cyc.sigmai}),
this rewrites as follows: $\sigma\left(  1\right)  >\sigma\left(  2\right)
>\cdots>\sigma\left(  p\right)  $. This solves Exercise
\ref{exe.V-perm-as-cyc} \textbf{(a)}.
\end{proof}

Permutations $\sigma\in S_{n}$ satisfying the inequalities $\sigma\left(
1\right)  >\sigma\left(  2\right)  >\cdots>\sigma\left(  p\right)  $ and
$\sigma\left(  p+1\right)  <\sigma\left(  p+2\right)  <\cdots<\sigma\left(
n\right)  $ for some $p\in\left\{  0,1,\ldots,n\right\}  $ are known as
\textquotedblleft V-permutations\textquotedblright\ (as their plot looks
somewhat like the letter \textquotedblleft V\textquotedblright: first
decreasing for a while, then increasing). Can you guess how permutations
$\sigma\in S_{n}$ satisfying $\sigma\left(  1\right)  <\sigma\left(  2\right)
<\cdots<\sigma\left(  p\right)  $ and $\sigma\left(  p+1\right)
>\sigma\left(  p+2\right)  >\cdots>\sigma\left(  n\right)  $ are
called?\footnote{\textit{Answer:} They are called \textquotedblleft$\Lambda
$-permutations\textquotedblright. Both names \textquotedblleft
V-permutations\textquotedblright\ and \textquotedblleft$\Lambda$%
-permutations\textquotedblright\ are due to the shape of the plot when the
permutation is plotted in 2D.}

Exercise \ref{exe.V-perm-as-cyc} is a lemma in the theory of free Lie algebras
(see \cite[(10)]{BleLau92}).

TODO: Explain how Exercise \ref{exe.V-perm-as-cyc} can also be obtained as a
particular case of the formula for a permutation in terms of its Rothe
diagram. (See \url{https://sumidiot.blogspot.com/2008/05/rothe-diagram.html}
for now.)

\subsection{Lexicographic comparison of permutations}

\begin{definition}
Let $n\in\mathbb{N}$. Let $\sigma\in S_{n}$ be a permutation. For any
$i\in\left[  n\right]  $, we let $\ell_{i}\left(  \sigma\right)  $ denote the
number of $j\in\left\{  i+1,i+2,\ldots,n\right\}  $ such that $\sigma\left(
i\right)  >\sigma\left(  j\right)  $.
\end{definition}

For example, if $\sigma$ is the permutation of $\left[  5\right]  $ written in
one-line notation as $\left[  4,1,5,2,3\right]  $, then $\ell_{1}\left(
\sigma\right)  =3$, $\ell_{2}\left(  \sigma\right)  =0$, $\ell_{3}\left(
\sigma\right)  =2$, $\ell_{4}\left(  \sigma\right)  =0$ and $\ell_{5}\left(
\sigma\right)  =0$.

\begin{definition}
\label{def.lexico}Let $n\in\mathbb{N}$. Let $\left(  a_{1},a_{2},\ldots
,a_{n}\right)  $ and $\left(  b_{1},b_{2},\ldots,b_{n}\right)  $ be two
$n$-tuples of integers. We say that $\left(  a_{1},a_{2},\ldots,a_{n}\right)
<_{\operatorname*{lex}}\left(  b_{1},b_{2},\ldots,b_{n}\right)  $ if and only
if there exists some $k\in\left[  n\right]  $ such that $a_{k}\neq b_{k}$, and
the \textbf{smallest} such $k$ satisfies $a_{k}<b_{k}$.
\end{definition}

For example, $\left(  4,1,2,5\right)  <_{\operatorname*{lex}}\left(
4,1,3,0\right)  $ and $\left(  1,1,0,1\right)  <_{\operatorname*{lex}}\left(
2,0,0,0\right)  $. The relation $<_{\operatorname*{lex}}$ is usually
pronounced \textquotedblleft is lexicographically smaller
than\textquotedblright; the word \textquotedblleft
lexicographic\textquotedblright\ comes from the idea that if numbers were
letters, then a \textquotedblleft word\textquotedblright\ $a_{1}a_{2}\cdots
a_{n}$ would appear earlier in a dictionary than $b_{1}b_{2}\cdots b_{n}$ if
and only if $\left(  a_{1},a_{2},\ldots,a_{n}\right)  <_{\operatorname*{lex}%
}\left(  b_{1},b_{2},\ldots,b_{n}\right)  $.

\begin{exercise}
\label{exe.perm.lexico1}Let $n\in\mathbb{N}$. Let $\sigma\in S_{n}$ and
$\tau\in S_{n}$. Prove the following:

\textbf{(a)} If
\[
\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
n\right)  \right)  <_{\operatorname*{lex}}\left(  \tau\left(  1\right)
,\tau\left(  2\right)  ,\ldots,\tau\left(  n\right)  \right)  ,
\]
then
\[
\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(  \sigma\right)
,\ldots,\ell_{n}\left(  \sigma\right)  \right)  <_{\operatorname*{lex}}\left(
\ell_{1}\left(  \tau\right)  ,\ell_{2}\left(  \tau\right)  ,\ldots,\ell
_{n}\left(  \tau\right)  \right)  .
\]


\textbf{(b)} If $\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(
\sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)  \right)  =\left(
\ell_{1}\left(  \tau\right)  ,\ell_{2}\left(  \tau\right)  ,\ldots,\ell
_{n}\left(  \tau\right)  \right)  $, then $\sigma=\tau$.
\end{exercise}

The solution to Exercise \ref{exe.perm.lexico1} given below is one of those
cases where a simple argument becomes insufferably long and dreary as I try to
capture it in writing. Apologies for what you are about to see. The proof
relies on the following lemma:

\begin{lemma}
\label{lem.perm.lexico1.lis}Let $n\in\mathbb{N}$. Let $\sigma\in S_{n}$ and
$i\in\left[  n\right]  $. Then:

\textbf{(a)} We have $\ell_{i}\left(  \sigma\right)  =\left\vert \left[
\sigma\left(  i\right)  -1\right]  \setminus\sigma\left(  \left[  i\right]
\right)  \right\vert $.

\textbf{(b)} We have $\ell_{i}\left(  \sigma\right)  =\left\vert \left[
\sigma\left(  i\right)  -1\right]  \setminus\sigma\left(  \left[  i-1\right]
\right)  \right\vert $.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.perm.lexico1.lis}.]\textbf{(a)} We know that
$\ell_{i}\left(  \sigma\right)  $ is the number of $j\in\left\{
i+1,i+2,\ldots,n\right\}  $ such that $\sigma\left(  i\right)  >\sigma\left(
j\right)  $ (by the definition of $\ell_{i}\left(  \sigma\right)  $). Hence,%
\begin{align}
\ell_{i}\left(  \sigma\right)   &  =\left(  \text{the number of }j\in\left\{
i+1,i+2,\ldots,n\right\}  \text{ such that }\sigma\left(  i\right)
>\sigma\left(  j\right)  \right) \nonumber\\
&  =\left\vert \left\{  j\in\left\{  i+1,i+2,\ldots,n\right\}  \ \mid
\ \sigma\left(  i\right)  >\sigma\left(  j\right)  \right\}  \right\vert .
\label{pf.lem.perm.lexico1.lis.1}%
\end{align}
Define a set $A$ by
\begin{equation}
A=\left\{  j\in\left\{  i+1,i+2,\ldots,n\right\}  \ \mid\ \sigma\left(
i\right)  >\sigma\left(  j\right)  \right\}  .
\label{pf.lem.perm.lexico1.lis.A=}%
\end{equation}
Thus,%
\begin{equation}
\left\vert A\right\vert =\left\vert \left\{  j\in\left\{  i+1,i+2,\ldots
,n\right\}  \ \mid\ \sigma\left(  i\right)  >\sigma\left(  j\right)  \right\}
\right\vert =\ell_{i}\left(  \sigma\right)
\label{pf.lem.perm.lexico1.lis.sizeA=}%
\end{equation}
(by (\ref{pf.lem.perm.lexico1.lis.1})).

Let $B$ be the set $\left[  \sigma\left(  i\right)  -1\right]  \setminus
\sigma\left(  \left[  i\right]  \right)  $.

The map $\sigma$ is a permutation of $\left[  n\right]  $ (since $\sigma\in
S_{n}$), and thus is invertible, and therefore is injective.

For each $k\in A$, we have $\sigma\left(  k\right)  \in B$%
\ \ \ \ \footnote{\textit{Proof.} Let $k\in A$. Thus, $k\in A=\left\{
j\in\left\{  i+1,i+2,\ldots,n\right\}  \ \mid\ \sigma\left(  i\right)
>\sigma\left(  j\right)  \right\}  $. In other words, $k$ is an element of
$\left\{  i+1,i+2,\ldots,n\right\}  $ and satisfies $\sigma\left(  i\right)
>\sigma\left(  k\right)  $.
\par
From $k\in\left\{  i+1,i+2,\ldots,n\right\}  \subseteq\left[  n\right]  $, we
conclude that $\sigma\left(  k\right)  $ is well-defined. Also, $\sigma\left(
k\right)  <\sigma\left(  i\right)  $ (since $\sigma\left(  i\right)
>\sigma\left(  k\right)  $), so that $\sigma\left(  k\right)  \leq
\sigma\left(  i\right)  -1$ (since $\sigma\left(  k\right)  $ and
$\sigma\left(  i\right)  $ are integers). Thus, $\sigma\left(  k\right)
\in\left[  \sigma\left(  i\right)  -1\right]  $.
\par
Next, let us prove that $\sigma\left(  k\right)  \notin\sigma\left(  \left[
i\right]  \right)  $.
\par
Indeed, assume the contrary (for the sake of contradiction). Hence,
$\sigma\left(  k\right)  \in\sigma\left(  \left[  i\right]  \right)  $. In
other words, there exists some $j\in\left[  i\right]  $ such that
$\sigma\left(  k\right)  =\sigma\left(  j\right)  $. Consider this $j$. From
$\sigma\left(  k\right)  =\sigma\left(  j\right)  $, we obtain $k=j$ (since
the map $\sigma$ is injective). Hence, $k=j\in\left[  i\right]  $. But
$k\in\left\{  i+1,i+2,\ldots,n\right\}  =\left[  n\right]  \setminus\left[
i\right]  $, so that $k\notin\left[  i\right]  $. This contradicts
$k\in\left[  i\right]  $. This contradiction shows that our assumption was
false. Hence, $\sigma\left(  k\right)  \notin\sigma\left(  \left[  i\right]
\right)  $ is proven.
\par
Combining $\sigma\left(  k\right)  \in\left[  \sigma\left(  i\right)
-1\right]  $ with $\sigma\left(  k\right)  \notin\sigma\left(  \left[
i\right]  \right)  $, we obtain $\sigma\left(  k\right)  \in\left[
\sigma\left(  i\right)  -1\right]  \setminus\sigma\left(  \left[  i\right]
\right)  =B$. Qed.}. Hence, we can define a map $\alpha:A\rightarrow B$ by
\[
\left(  \alpha\left(  k\right)  =\sigma\left(  k\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }k\in A\right)  .
\]
Consider this $\alpha$.

On the other hand, for each $k\in B$, we have $\sigma^{-1}\left(  k\right)
\in A$\ \ \ \ \footnote{\textit{Proof.} Let $k\in B$. Thus, $k\in B=\left[
\sigma\left(  i\right)  -1\right]  \setminus\sigma\left(  \left[  i\right]
\right)  $. In other words, $k\in\left[  \sigma\left(  i\right)  -1\right]  $
and $k\notin\sigma\left(  \left[  i\right]  \right)  $.
\par
From $k\in\left[  \sigma\left(  i\right)  -1\right]  $, we obtain $1\leq
k\leq\sigma\left(  i\right)  -1$. Also, $k\in\left[  \sigma\left(  i\right)
-1\right]  \subseteq\left[  n\right]  $, so that $\sigma^{-1}\left(  k\right)
$ is a well-defined element of $\left[  n\right]  $.
\par
We have $\sigma\left(  \sigma^{-1}\left(  k\right)  \right)  =k\leq
\sigma\left(  i\right)  -1<\sigma\left(  i\right)  $. In other words,
$\sigma\left(  i\right)  >\sigma\left(  \sigma^{-1}\left(  k\right)  \right)
$.
\par
Next, we claim that $\sigma^{-1}\left(  k\right)  \in\left\{  i+1,i+2,\ldots
,n\right\}  $. Indeed, assume the contrary (for the sake of contradiction).
Thus, $\sigma^{-1}\left(  k\right)  \notin\left\{  i+1,i+2,\ldots,n\right\}
$. Combining this with $\sigma^{-1}\left(  k\right)  \in\left[  n\right]  $,
we obtain%
\[
\sigma^{-1}\left(  k\right)  \in\left[  n\right]  \setminus\left\{
i+1,i+2,\ldots,n\right\}  =\left[  i\right]  .
\]
Hence, $k=\sigma\left(  \underbrace{\sigma^{-1}\left(  k\right)  }_{\in\left[
i\right]  }\right)  \in\sigma\left(  \left[  i\right]  \right)  $, which
contradicts $k\notin\sigma\left(  \left[  i\right]  \right)  $. This
contradiction shows that our assumption was false. Thus, $\sigma^{-1}\left(
k\right)  \in\left\{  i+1,i+2,\ldots,n\right\}  $ is proven.
\par
Now, we know that $\sigma^{-1}\left(  k\right)  \in\left\{  i+1,i+2,\ldots
,n\right\}  $ and $\sigma\left(  i\right)  >\sigma\left(  \sigma^{-1}\left(
k\right)  \right)  $. In other words, $\sigma^{-1}\left(  k\right)  $ is a
$j\in\left\{  i+1,i+2,\ldots,n\right\}  $ satisfying $\sigma\left(  i\right)
>\sigma\left(  j\right)  $. In other words,%
\[
\sigma^{-1}\left(  k\right)  \in\left\{  j\in\left\{  i+1,i+2,\ldots
,n\right\}  \ \mid\ \sigma\left(  i\right)  >\sigma\left(  j\right)  \right\}
.
\]
In view of (\ref{pf.lem.perm.lexico1.lis.A=}), this rewrites as $\sigma
^{-1}\left(  k\right)  \in A$. Qed.}. Hence, we can define a map
$\beta:B\rightarrow A$ by%
\[
\left(  \beta\left(  k\right)  =\sigma^{-1}\left(  k\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }k\in B\right)  .
\]
Consider this $\beta$.

The maps $\alpha$ and $\beta$ are mutually inverse (since $\alpha$ is a
restriction of $\sigma$, whereas $\beta$ is a restriction of $\sigma^{-1}$),
and therefore are bijections. Hence, there is a bijection from $A$ to $B$
(namely, $\alpha$). Thus, $\left\vert A\right\vert =\left\vert B\right\vert $.

But (\ref{pf.lem.perm.lexico1.lis.sizeA=}) yields%
\[
\ell_{i}\left(  \sigma\right)  =\left\vert A\right\vert =\left\vert
B\right\vert =\left\vert \left[  \sigma\left(  i\right)  -1\right]
\setminus\sigma\left(  \left[  i\right]  \right)  \right\vert
\]
(since $B=\left[  \sigma\left(  i\right)  -1\right]  \setminus\sigma\left(
\left[  i\right]  \right)  $). This proves Lemma \ref{lem.perm.lexico1.lis}
\textbf{(a)}.

\textbf{(b)} If we had $\sigma\left(  i\right)  \in\left[  \sigma\left(
i\right)  -1\right]  $, then we would have $\sigma\left(  i\right)  \leq
\sigma\left(  i\right)  -1<\sigma\left(  i\right)  $, which would be absurd.
Hence, we have $\sigma\left(  i\right)  \notin\left[  \sigma\left(  i\right)
-1\right]  $.

But $\left[  i\right]  =\left\{  i\right\}  \cup\left[  i-1\right]  $. Hence,%
\[
\sigma\left(  \underbrace{\left[  i\right]  }_{=\left\{  i\right\}
\cup\left[  i-1\right]  }\right)  =\sigma\left(  \left\{  i\right\}
\cup\left[  i-1\right]  \right)  =\underbrace{\sigma\left(  \left\{
i\right\}  \right)  }_{=\left\{  \sigma\left(  i\right)  \right\}  }\cup
\sigma\left(  \left[  i-1\right]  \right)  =\left\{  \sigma\left(  i\right)
\right\}  \cup\sigma\left(  \left[  i-1\right]  \right)  .
\]
Thus,%
\begin{align*}
&  \left[  \sigma\left(  i\right)  -1\right]  \setminus\underbrace{\sigma
\left(  \left[  i\right]  \right)  }_{=\left\{  \sigma\left(  i\right)
\right\}  \cup\sigma\left(  \left[  i-1\right]  \right)  }\\
&  =\left[  \sigma\left(  i\right)  -1\right]  \setminus\left(  \left\{
\sigma\left(  i\right)  \right\}  \cup\sigma\left(  \left[  i-1\right]
\right)  \right) \\
&  =\underbrace{\left(  \left[  \sigma\left(  i\right)  -1\right]
\setminus\left\{  \sigma\left(  i\right)  \right\}  \right)  }%
_{\substack{=\left[  \sigma\left(  i\right)  -1\right]  \\\text{(since }%
\sigma\left(  i\right)  \notin\left[  \sigma\left(  i\right)  -1\right]
\text{)}}}\setminus\sigma\left(  \left[  i-1\right]  \right)  =\left[
\sigma\left(  i\right)  -1\right]  \setminus\sigma\left(  \left[  i-1\right]
\right)  .
\end{align*}


Now, Lemma \ref{lem.perm.lexico1.lis} \textbf{(a)} yields%
\[
\ell_{i}\left(  \sigma\right)  =\left\vert \underbrace{\left[  \sigma\left(
i\right)  -1\right]  \setminus\sigma\left(  \left[  i\right]  \right)
}_{=\left[  \sigma\left(  i\right)  -1\right]  \setminus\sigma\left(  \left[
i-1\right]  \right)  }\right\vert =\left\vert \left[  \sigma\left(  i\right)
-1\right]  \setminus\sigma\left(  \left[  i-1\right]  \right)  \right\vert .
\]
This proves Lemma \ref{lem.perm.lexico1.lis} \textbf{(b)}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.perm.lexico1} (sketched).]\textbf{(a)} Assume
that%
\[
\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
n\right)  \right)  <_{\operatorname*{lex}}\left(  \tau\left(  1\right)
,\tau\left(  2\right)  ,\ldots,\tau\left(  n\right)  \right)  .
\]
According to Definition \ref{def.lexico}, this means the following: There
exists some $k\in\left[  n\right]  $ such that $\sigma\left(  k\right)
\neq\tau\left(  k\right)  $, and the \textbf{smallest} such $k$ satisfies
$\sigma\left(  k\right)  <\tau\left(  k\right)  $.

Let $i$ be the smallest such $k$. Thus, $\sigma\left(  i\right)  <\tau\left(
i\right)  $, but
\begin{equation}
\text{each }k\in\left[  i-1\right]  \text{ satisfies }\sigma\left(  k\right)
=\tau\left(  k\right)  \label{sol.perm.lexico1.a.ak=bk}%
\end{equation}
(since $i$ is the \textbf{smallest} $k\in\left[  n\right]  $ such that
$\sigma\left(  k\right)  \neq\tau\left(  k\right)  $).

Thus,%
\begin{equation}
\text{each }k\in\left[  i\right]  \text{ satisfies }\sigma\left(  \left[
k-1\right]  \right)  =\tau\left(  \left[  k-1\right]  \right)
\label{sol.perm.lexico1.a.ak=bk2}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.perm.lexico1.a.ak=bk2}):} Let
$k\in\left[  i\right]  $. Thus, $k\leq i$.
\par
Let $j\in\left[  k-1\right]  $. Thus, $j\leq\underbrace{k}_{\leq i}-1\leq
i-1$, so that $j\in\left[  i-1\right]  $. Hence,
(\ref{sol.perm.lexico1.a.ak=bk}) (applied to $j$ instead of $k$) shows that
$\sigma\left(  j\right)  =\tau\left(  j\right)  $.
\par
Now, forget that we fixed $j$. We thus have shown that $\sigma\left(
j\right)  =\tau\left(  j\right)  $ for each $j\in\left[  k-1\right]  $. In
other words,%
\[
\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
k-1\right)  \right)  =\left(  \tau\left(  1\right)  ,\tau\left(  2\right)
,\ldots,\tau\left(  k-1\right)  \right)  .
\]
Thus,%
\[
\left\{  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots
,\sigma\left(  k-1\right)  \right\}  =\left\{  \tau\left(  1\right)
,\tau\left(  2\right)  ,\ldots,\tau\left(  k-1\right)  \right\}  .
\]
\par
Now,%
\begin{align*}
\sigma\left(  \underbrace{\left[  k-1\right]  }_{=\left\{  1,2,\ldots
,k-1\right\}  }\right)   &  =\sigma\left(  \left\{  1,2,\ldots,k-1\right\}
\right)  =\left\{  \sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  k-1\right)  \right\} \\
&  =\left\{  \tau\left(  1\right)  ,\tau\left(  2\right)  ,\ldots,\tau\left(
k-1\right)  \right\}  =\tau\left(  \underbrace{\left\{  1,2,\ldots
,k-1\right\}  }_{=\left[  k-1\right]  }\right)  =\tau\left(  \left[
k-1\right]  \right)  .
\end{align*}
This proves (\ref{sol.perm.lexico1.a.ak=bk2}).}. Hence,%
\begin{equation}
\text{each }k\in\left[  i-1\right]  \text{ satisfies }\ell_{k}\left(
\sigma\right)  =\ell_{k}\left(  \tau\right)  \label{sol.perm.lexico1.a.li=li}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.perm.lexico1.a.li=li}):} Let $k\in\left[
i-1\right]  $. Then, Lemma \ref{lem.perm.lexico1.lis} \textbf{(b)} (applied to
$k$ instead of $i$) yields $\ell_{k}\left(  \sigma\right)  =\left\vert \left[
\sigma\left(  k\right)  -1\right]  \setminus\sigma\left(  \left[  k-1\right]
\right)  \right\vert $. The same argument (applied to $\tau$ instead of
$\sigma$) yields $\ell_{k}\left(  \tau\right)  =\left\vert \left[  \tau\left(
k\right)  -1\right]  \setminus\tau\left(  \left[  k-1\right]  \right)
\right\vert $.
\par
But $k\in\left[  i-1\right]  \subseteq\left[  i\right]  $. Hence,
(\ref{sol.perm.lexico1.a.ak=bk2}) yields $\sigma\left(  \left[  k-1\right]
\right)  =\tau\left(  \left[  k-1\right]  \right)  $. Also,
(\ref{sol.perm.lexico1.a.ak=bk}) yields $\sigma\left(  k\right)  =\tau\left(
k\right)  $. Hence,%
\[
\ell_{k}\left(  \sigma\right)  =\left\vert \left[  \underbrace{\sigma\left(
k\right)  }_{=\tau\left(  k\right)  }-1\right]  \setminus\underbrace{\sigma
\left(  \left[  k-1\right]  \right)  }_{=\tau\left(  \left[  k-1\right]
\right)  }\right\vert =\left\vert \left[  \tau\left(  k\right)  -1\right]
\setminus\tau\left(  \left[  k-1\right]  \right)  \right\vert =\ell_{k}\left(
\tau\right)  .
\]
This proves (\ref{sol.perm.lexico1.a.li=li}).}. Furthermore,%
\begin{equation}
\ell_{i}\left(  \sigma\right)  <\ell_{i}\left(  \tau\right)
\label{sol.perm.lexico1.a.li2}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.perm.lexico1.a.li2}):} We have
$i\in\left[  i\right]  $. Hence, (\ref{sol.perm.lexico1.a.ak=bk2}) (applied to
$k=i$) yields $\sigma\left(  \left[  i-1\right]  \right)  =\tau\left(  \left[
i-1\right]  \right)  $.
\par
Also, $\sigma\left(  i\right)  <\tau\left(  i\right)  $, so that
$\sigma\left(  i\right)  -1<\tau\left(  i\right)  -1$ and therefore $\left[
\sigma\left(  i\right)  -1\right]  \subseteq\left[  \tau\left(  i\right)
-1\right]  $.
\par
From $\sigma\left(  i\right)  <\tau\left(  i\right)  $, we also obtain
$\sigma\left(  i\right)  \leq\tau\left(  i\right)  -1$ (since $\sigma\left(
i\right)  $ and $\tau\left(  i\right)  $ are integers), and thus
$\sigma\left(  i\right)  \in\left[  \tau\left(  i\right)  -1\right]  $.
\par
Also, $\sigma\left(  i\right)  \notin\sigma\left(  \left[  i-1\right]
\right)  $. [\textit{Proof:} Assume the contrary. Thus, $\sigma\left(
i\right)  \in\sigma\left(  \left[  i-1\right]  \right)  $. In other words,
$\sigma\left(  i\right)  =\sigma\left(  j\right)  $ for some $j\in\left[
i-1\right]  $. Consider this $j$. From $\sigma\left(  i\right)  =\sigma\left(
j\right)  $, we obtain $i=j$ (since $\sigma$ is injective), so that
$i=j\in\left[  i-1\right]  $ and thus $i\leq i-1<i$. But this is absurd.
Hence, we found a contradiction, so that $\sigma\left(  i\right)  \notin%
\sigma\left(  \left[  i-1\right]  \right)  $ is proven.]
\par
If we had $\sigma\left(  i\right)  \in\left[  \sigma\left(  i\right)
-1\right]  $, then we would have $\sigma\left(  i\right)  \leq\sigma\left(
i\right)  -1<\sigma\left(  i\right)  $, which is absurd. Hence, we have
$\sigma\left(  i\right)  \notin\left[  \sigma\left(  i\right)  -1\right]  $.
Thus, also $\sigma\left(  i\right)  \notin\left[  \sigma\left(  i\right)
-1\right]  \setminus\sigma\left(  \left[  i-1\right]  \right)  $.
\par
Combining $\sigma\left(  i\right)  \in\left[  \tau\left(  i\right)  -1\right]
$ with $\sigma\left(  i\right)  \notin\sigma\left(  \left[  i-1\right]
\right)  $, we obtain $\sigma\left(  i\right)  \in\left[  \tau\left(
i\right)  -1\right]  \setminus\sigma\left(  \left[  i-1\right]  \right)  $.
\par
Now,%
\begin{equation}
\underbrace{\left[  \sigma\left(  i\right)  -1\right]  }_{\subseteq\left[
\tau\left(  i\right)  -1\right]  }\setminus\sigma\left(  \left[  i-1\right]
\right)  \subseteq\left[  \tau\left(  i\right)  -1\right]  \setminus
\sigma\left(  \left[  i-1\right]  \right)  . \label{sol.perm.lexico1.a.li2.1}%
\end{equation}
\par
Moreover, the set $\left[  \tau\left(  i\right)  -1\right]  \setminus
\sigma\left(  \left[  i-1\right]  \right)  $ contains $\sigma\left(  i\right)
$ (since $\sigma\left(  i\right)  \in\left[  \tau\left(  i\right)  -1\right]
\setminus\sigma\left(  \left[  i-1\right]  \right)  $), but the set $\left[
\sigma\left(  i\right)  -1\right]  \setminus\sigma\left(  \left[  i-1\right]
\right)  $ does not (since $\sigma\left(  i\right)  \notin\left[
\sigma\left(  i\right)  -1\right]  \setminus\sigma\left(  \left[  i-1\right]
\right)  $). Thus, these two sets are distinct. In other words, $\left[
\sigma\left(  i\right)  -1\right]  \setminus\sigma\left(  \left[  i-1\right]
\right)  \neq\left[  \tau\left(  i\right)  -1\right]  \setminus\sigma\left(
\left[  i-1\right]  \right)  $. Combining this with
(\ref{sol.perm.lexico1.a.li2.1}), we conclude that $\left[  \sigma\left(
i\right)  -1\right]  \setminus\sigma\left(  \left[  i-1\right]  \right)  $ is
a \textbf{proper} subset of $\left[  \tau\left(  i\right)  -1\right]
\setminus\sigma\left(  \left[  i-1\right]  \right)  $. Thus,%
\[
\left\vert \left[  \sigma\left(  i\right)  -1\right]  \setminus\sigma\left(
\left[  i-1\right]  \right)  \right\vert <\left\vert \left[  \tau\left(
i\right)  -1\right]  \setminus\sigma\left(  \left[  i-1\right]  \right)
\right\vert
\]
(since a proper subset of any finite set must always have smaller size than
the latter).
\par
But Lemma \ref{lem.perm.lexico1.lis} \textbf{(b)} yields $\ell_{i}\left(
\sigma\right)  =\left\vert \left[  \sigma\left(  i\right)  -1\right]
\setminus\sigma\left(  \left[  i-1\right]  \right)  \right\vert $. The same
argument (applied to $\tau$ instead of $\sigma$) yields $\ell_{i}\left(
\tau\right)  =\left\vert \left[  \tau\left(  i\right)  -1\right]
\setminus\tau\left(  \left[  i-1\right]  \right)  \right\vert $. Hence,%
\begin{align*}
\ell_{i}\left(  \sigma\right)   &  =\left\vert \left[  \sigma\left(  i\right)
-1\right]  \setminus\sigma\left(  \left[  i-1\right]  \right)  \right\vert \\
&  <\left\vert \left[  \tau\left(  i\right)  -1\right]  \setminus
\underbrace{\sigma\left(  \left[  i-1\right]  \right)  }_{=\tau\left(  \left[
i-1\right]  \right)  }\right\vert =\left\vert \left[  \tau\left(  i\right)
-1\right]  \setminus\tau\left(  \left[  i-1\right]  \right)  \right\vert
=\ell_{i}\left(  \tau\right)  .
\end{align*}
This proves (\ref{sol.perm.lexico1.a.li2}).}. Thus, $\ell_{i}\left(
\sigma\right)  \neq\ell_{i}\left(  \tau\right)  $. In other words, $i$ is a
$k\in\left[  n\right]  $ such that $\ell_{k}\left(  \sigma\right)  \neq
\ell_{k}\left(  \tau\right)  $. Moreover, (\ref{sol.perm.lexico1.a.li=li})
shows that $i$ is the \textbf{smallest} such $k$. Thus, the smallest
$k\in\left[  n\right]  $ such that $\ell_{k}\left(  \sigma\right)  \neq
\ell_{k}\left(  \tau\right)  $ satisfies $\ell_{k}\left(  \sigma\right)
<\ell_{k}\left(  \tau\right)  $ (because this $k$ is $i$, and $i$ satisfies
(\ref{sol.perm.lexico1.a.li2})).

Thus, we have shown that there exists some $k\in\left[  n\right]  $ such that
$\ell_{k}\left(  \sigma\right)  \neq\ell_{k}\left(  \tau\right)  $, and the
\textbf{smallest} such $k$ satisfies $\ell_{k}\left(  \sigma\right)  <\ell
_{k}\left(  \tau\right)  $. But this means precisely that%
\[
\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(  \sigma\right)
,\ldots,\ell_{n}\left(  \sigma\right)  \right)  <_{\operatorname*{lex}}\left(
\ell_{1}\left(  \tau\right)  ,\ell_{2}\left(  \tau\right)  ,\ldots,\ell
_{n}\left(  \tau\right)  \right)
\]
(according to Definition \ref{def.lexico}). Hence, Exercise
\ref{exe.perm.lexico1} \textbf{(a)} is solved.

\textbf{(b)} Assume that
\begin{equation}
\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(  \sigma\right)
,\ldots,\ell_{n}\left(  \sigma\right)  \right)  =\left(  \ell_{1}\left(
\tau\right)  ,\ell_{2}\left(  \tau\right)  ,\ldots,\ell_{n}\left(
\tau\right)  \right)  . \label{sol.perm.lexico1.b.ass}%
\end{equation}
We must prove that $\sigma=\tau$.

Indeed, assume the contrary. Thus, $\sigma\neq\tau$. Hence, there exists some
$k\in\left[  n\right]  $ satisfying $\sigma\left(  k\right)  \neq\tau\left(
k\right)  $. Therefore, there exists the \textbf{smallest} such $k$. This
smallest $k$ must satisfy either $\sigma\left(  k\right)  <\tau\left(
k\right)  $ or $\sigma\left(  k\right)  >\tau\left(  k\right)  $ (because it
satisfies $\sigma\left(  k\right)  \neq\tau\left(  k\right)  $). We can WLOG
assume that it satisfies $\sigma\left(  k\right)  <\tau\left(  k\right)  $
(because otherwise, we can simply switch the roles of $\sigma$ and $\tau$).
Assume this. Thus, $\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  n\right)  \right)  <_{\operatorname*{lex}}\left(
\tau\left(  1\right)  ,\tau\left(  2\right)  ,\ldots,\tau\left(  n\right)
\right)  $ (because of Definition \ref{def.lexico}). Hence, Exercise
\ref{exe.perm.lexico1} \textbf{(a)} shows that $\left(  \ell_{1}\left(
\sigma\right)  ,\ell_{2}\left(  \sigma\right)  ,\ldots,\ell_{n}\left(
\sigma\right)  \right)  <_{\operatorname*{lex}}\left(  \ell_{1}\left(
\tau\right)  ,\ell_{2}\left(  \tau\right)  ,\ldots,\ell_{n}\left(
\tau\right)  \right)  $. In other words, there exists some $k\in\left[
n\right]  $ such that $\ell_{k}\left(  \sigma\right)  \neq\ell_{k}\left(
\tau\right)  $, and the \textbf{smallest} such $k$ satisfies $\ell_{k}\left(
\sigma\right)  <\ell_{k}\left(  \tau\right)  $ (according to Definition
\ref{def.lexico}).

In particular, there exists some $k\in\left[  n\right]  $ such that $\ell
_{k}\left(  \sigma\right)  \neq\ell_{k}\left(  \tau\right)  $. In other words,
$\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(  \sigma\right)
,\ldots,\ell_{n}\left(  \sigma\right)  \right)  \neq\left(  \ell_{1}\left(
\tau\right)  ,\ell_{2}\left(  \tau\right)  ,\ldots,\ell_{n}\left(
\tau\right)  \right)  $. But this contradicts (\ref{sol.perm.lexico1.b.ass}).
This contradiction shows that our assumption was false. Hence, $\sigma=\tau$
is proven. This solves Exercise \ref{exe.perm.lexico1} \textbf{(b)}.
\end{proof}

\begin{noncompile}
\textbf{(a)} An \textit{inversion} of $\sigma$ means a pair $\left(
i,j\right)  \in\left[  n\right]  ^{2}$ such that $i<j$ and $\sigma\left(
i\right)  >\sigma\left(  j\right)  $. (For example, the permutation of
$\left[  5\right]  $ written in one-line notation as $\left[
4,1,5,2,3\right]  $ has inversions $\left(  1,2\right)  ,\left(  1,4\right)
,\left(  1,5\right)  ,\left(  3,4\right)  ,\left(  3,5\right)  $.)
\end{noncompile}

\subsection{Comparing subsets of $\left[  n\right]  $}

If $I$ and $J$ are two finite sets of integers, then we write $I\leq_{\#}J$ if
and only if the following two properties hold:

\begin{itemize}
\item We have $\left\vert I\right\vert \geq\left\vert J\right\vert $.

\item For every $r\in\left\{  1,2,\ldots,\left\vert J\right\vert \right\}  $,
the $r$-th smallest element of $I$ is $\leq$ to the $r$-th smallest element of
$J$.
\end{itemize}

For example, $\left\{  2,4\right\}  \leq_{\#}\left\{  2,5\right\}  $ and
$\left\{  1,3\right\}  \leq_{\#}\left\{  2,4\right\}  $ and $\left\{
1,3,5\right\}  \leq_{\#}\left\{  2,4\right\}  $. (But not $\left\{
1,3\right\}  \leq_{\#}\left\{  2,4,5\right\}  $.)

The relation $\leq_{\#}$ is called the \textit{Gale order} on the powerset of
$\left[  n\right]  $.

\begin{exercise}
\label{exe.gale}Let $n\in\mathbb{N}$. Let $I$ and $J$ be two subsets of
$\left[  n\right]  $.

\textbf{(a)} For every subset $S$ of $\left[  n\right]  $ and every $\ell
\in\left[  n\right]  $, let $\alpha_{S}\left(  \ell\right)  $ denote the
number of all elements of $S$ that are $\leq\ell$. Prove that $I\leq_{\#}J$
holds if and only if every $\ell\in\left[  n\right]  $ satisfies $\alpha
_{I}\left(  \ell\right)  \geq\alpha_{J}\left(  \ell\right)  $.

\textbf{(b)} Prove that $I\leq_{\#}J$ if and only if $\left[  n\right]
\setminus J\leq_{\#}\left[  n\right]  \setminus I$.
\end{exercise}

The following solution is mostly copypasted from \cite[Proof of Proposition
12.75.2]{GriRei17}, where the exercise serves as a lemma for a combinatorial
proof of an identity between Schur polynomials.

\begin{proof}
[Solution to Exercise~\ref{exe.gale}.]\textbf{(a)} We must prove the
equivalence%
\begin{equation}
\left(  I\leq_{\#}J\right)  \ \Longleftrightarrow\ \left(  \text{every }%
\ell\in\left[  n\right]  \text{ satisfies }\alpha_{I}\left(  \ell\right)
\geq\alpha_{J}\left(  \ell\right)  \right)  . \label{sol.gale.a.goal}%
\end{equation}


$\Longrightarrow:$ Assume that $I\leq_{\#}J$. In other words, the following
two properties hold:

\begin{statement}
\textit{Property }$\alpha$\textit{:} We have $\left\vert I\right\vert
\geq\left\vert J\right\vert $.
\end{statement}

\begin{statement}
\textit{Property }$\beta$\textit{:} For every $r\in\left\{  1,2,\ldots
,\left\vert J\right\vert \right\}  $, the $r$-th smallest element of $I$ is
$\leq$ to the $r$-th smallest element of $J$.
\end{statement}

Now, let $\ell\in\left[  n\right]  $. Then, we need to show that $\alpha
_{I}\left(  \ell\right)  \geq\alpha_{J}\left(  \ell\right)  $. Since this is
obvious if $\alpha_{J}\left(  \ell\right)  =0$ (because $\alpha_{I}\left(
\ell\right)  \geq0$), we can WLOG assume that $\alpha_{J}\left(  \ell\right)
\neq0$. Assume this. Thus, $\alpha_{J}\left(  \ell\right)  \geq1$. Also,
$\alpha_{J}\left(  \ell\right)  =\left\vert \underbrace{\left\{  s\in
J\ \mid\ s\leq\ell\right\}  }_{\subseteq J}\right\vert \leq\left\vert
J\right\vert \leq\left\vert I\right\vert $ (since $\left\vert I\right\vert
\geq\left\vert J\right\vert $). Hence, both the $\alpha_{J}\left(
\ell\right)  $-th smallest element of $J$ and the $\alpha_{J}\left(
\ell\right)  $-th smallest element of $I$ are well-defined.

Since $\alpha_{J}\left(  \ell\right)  =\left\vert \left\{  s\in J\ \mid
\ s\leq\ell\right\}  \right\vert $, we know that the elements of $J$ which are
$\leq\ell$ are precisely the $\alpha_{J}\left(  \ell\right)  $ smallest
elements of $J$. Thus,%
\[
\left(  \text{the }\alpha_{J}\left(  \ell\right)  \text{-th smallest element
of }J\right)  =\left(  \text{the largest element of }J\text{ which is }%
\leq\ell\right)  .
\]
But by Property $\beta$ (applied to $r=\alpha_{J}\left(  \ell\right)  $), we
have%
\begin{align*}
\left(  \text{the }\alpha_{J}\left(  \ell\right)  \text{-th smallest element
of }I\right)   &  \leq\left(  \text{the }\alpha_{J}\left(  \ell\right)
\text{-th smallest element of }J\right) \\
&  =\left(  \text{the largest element of }J\text{ which is }\leq\ell\right)
\leq\ell.
\end{align*}
Hence, there are at least $\alpha_{J}\left(  \ell\right)  $ elements of $I$
which are $\leq\ell$ (namely, the $\alpha_{J}\left(  \ell\right)  $ smallest
ones). In other words, $\left\vert \left\{  s\in I\ \mid\ s\leq\ell\right\}
\right\vert \geq\alpha_{J}\left(  \ell\right)  $. Now, the definition of
$\alpha_{I}\left(  \ell\right)  $ yields $\alpha_{I}\left(  \ell\right)
=\left\vert \left\{  s\in I\ \mid\ s\leq\ell\right\}  \right\vert \geq
\alpha_{J}\left(  \ell\right)  $. We thus have proven the $\Longrightarrow$
direction of (\ref{sol.gale.a.goal}).

$\Longleftarrow:$ Assume that every $\ell\in\left[  n\right]  $ satisfies
$\alpha_{I}\left(  \ell\right)  \geq\alpha_{J}\left(  \ell\right)  $. We need
to prove that $I\leq_{\#}J$. In other words, we need to prove that the
following two properties hold:

\begin{statement}
\textit{Property }$\alpha$\textit{:} We have $\left\vert I\right\vert
\geq\left\vert J\right\vert $.
\end{statement}

\begin{statement}
\textit{Property }$\beta$\textit{:} For every $r\in\left\{  1,2,\ldots
,\left\vert J\right\vert \right\}  $, the $r$-th smallest element of $I$ is
$\leq$ to the $r$-th smallest element of $J$.
\end{statement}

First of all, $\left\{  s\in I\ \mid\ s\leq n\right\}  =I$ (since every $s\in
I$ satisfies $s\leq n$), and the definition of $\alpha_{I}\left(  n\right)  $
yields $\alpha_{I}\left(  n\right)  =\left\vert \underbrace{\left\{  s\in
I\ \mid\ s\leq n\right\}  }_{=I}\right\vert =\left\vert I\right\vert $.
Similarly, $\alpha_{J}\left(  n\right)  =\left\vert J\right\vert $. Applying
$\alpha_{I}\left(  \ell\right)  \geq\alpha_{J}\left(  \ell\right)  $ to
$\ell=n$, we obtain $\alpha_{I}\left(  n\right)  \geq\alpha_{J}\left(
n\right)  $, so that $\left\vert I\right\vert =\alpha_{I}\left(  n\right)
\geq\alpha_{J}\left(  n\right)  =\left\vert J\right\vert $, and thus Property
$\alpha$ is proven.

Now, let $r\in\left\{  1,2,\ldots,\left\vert J\right\vert \right\}  $. The
$r$-th smallest element of $I$ and the $r$-th smallest element of $J$ are then
well-defined (because of $r\leq\left\vert J\right\vert \leq\left\vert
I\right\vert $). Let $\ell$ be the $r$-th smallest element of $J$. Then,
$\left\{  s\in J\ \mid\ s\leq\ell\right\}  $ is the set consisting of the $r$
smallest elements of $J$, so that $\left\vert \left\{  s\in J\ \mid\ s\leq
\ell\right\}  \right\vert =r$. Now, the definition of $\alpha_{J}\left(
\ell\right)  $ yields $\alpha_{J}\left(  \ell\right)  =\left\vert \left\{
s\in J\ \mid\ s\leq\ell\right\}  \right\vert =r$.

But the definition of $\alpha_{I}\left(  \ell\right)  $ yields $\alpha
_{I}\left(  \ell\right)  =\left\vert \left\{  s\in I\ \mid\ s\leq\ell\right\}
\right\vert $, so that%
\[
\left\vert \left\{  s\in I\ \mid\ s\leq\ell\right\}  \right\vert =\alpha
_{I}\left(  \ell\right)  \geq\alpha_{J}\left(  \ell\right)  =r.
\]
In other words, there exist at least $r$ elements of $I$ which are $\leq\ell$.
Hence, the $r$-th smallest element of $I$ must be $\leq\ell$. Since $\ell$ is
the $r$-th smallest element of $J$, this rewrites as follows: The $r$-th
smallest element of $I$ is $\leq$ to the $r$-th smallest element of $J$. Thus,
Property $\beta$ holds. Now we know that both Properties $\alpha$ and $\beta$
hold. Hence, $I\leq_{\#}J$ holds (which, as we know, is equivalent to the
conjunction of said properties). This proves the $\Longleftarrow$ direction of
(\ref{sol.gale.a.goal}). Thus, (\ref{sol.gale.a.goal}) is proven. In other
words, Exercise \ref{exe.gale} \textbf{(a)} is solved.

\textbf{(b)} For every $\ell\in\left[  n\right]  $ and $S\subseteq\left[
n\right]  $, let $\alpha_{S}\left(  \ell\right)  $ denote the number
$\left\vert \left\{  s\in S\ \mid\ s\leq\ell\right\}  \right\vert $. Thus,
every $\ell\in\left[  n\right]  $ satisfies%
\begin{align*}
\alpha_{I}\left(  \ell\right)  +\alpha_{\left[  n\right]  \setminus I}\left(
\ell\right)   &  =\left\vert \left\{  s\in I\ \mid\ s\leq\ell\right\}
\right\vert +\left\vert \left\{  s\in\left[  n\right]  \setminus
I\ \mid\ s\leq\ell\right\}  \right\vert \\
&  =\left\vert \left\{  s\in\underbrace{I\cup\left(  \left[  n\right]
\setminus I\right)  }_{=\left[  n\right]  }\ \mid\ s\leq\ell\right\}
\right\vert \ \ \ \ \ \ \ \ \ \ \left(  \text{since }I\text{ and }\left[
n\right]  \setminus I\text{ are disjoint}\right) \\
&  =\left\vert \left\{  s\in\left[  n\right]  \ \mid\ s\leq\ell\right\}
\right\vert =\left\vert \left\{  1,2,\ldots,\ell\right\}  \right\vert =\ell,
\end{align*}
so that $\alpha_{\left[  n\right]  \setminus I}\left(  \ell\right)
=\ell-\alpha_{I}\left(  \ell\right)  $. Similarly, every $\ell\in\left[
n\right]  $ satisfies $\alpha_{\left[  n\right]  \setminus J}\left(
\ell\right)  =\ell-\alpha_{J}\left(  \ell\right)  $.

Applying (\ref{sol.gale.a.goal}) to $\left[  n\right]  \setminus J$ and
$\left[  n\right]  \setminus I$ in lieu of $I$ and $J$, we obtain the
equivalence%
\[
\left(  \left[  n\right]  \setminus J\leq_{\#}\left[  n\right]  \setminus
I\right)  \ \Longleftrightarrow\ \left(  \text{every }\ell\in\left[  n\right]
\text{ satisfies }\alpha_{\left[  n\right]  \setminus J}\left(  \ell\right)
\geq\alpha_{\left[  n\right]  \setminus I}\left(  \ell\right)  \right)  .
\]
Hence, we have the following chain of equivalences:%
\begin{align*}
&  \ \left(  \left[  n\right]  \setminus J\leq_{\#}\left[  n\right]  \setminus
I\right) \\
&  \Longleftrightarrow\ \left(  \text{every }\ell\in\left[  n\right]  \text{
satisfies }\underbrace{\alpha_{\left[  n\right]  \setminus J}\left(
\ell\right)  }_{=\ell-\alpha_{J}\left(  \ell\right)  }\geq\underbrace{\alpha
_{\left[  n\right]  \setminus I}\left(  \ell\right)  }_{=\ell-\alpha
_{I}\left(  \ell\right)  }\right) \\
&  \Longleftrightarrow\ \left(  \text{every }\ell\in\left[  n\right]  \text{
satisfies }\ell-\alpha_{J}\left(  \ell\right)  \geq\ell-\alpha_{I}\left(
\ell\right)  \right) \\
&  \Longleftrightarrow\ \left(  \text{every }\ell\in\left[  n\right]  \text{
satisfies }\alpha_{I}\left(  \ell\right)  \geq\alpha_{J}\left(  \ell\right)
\right) \\
&  \Longleftrightarrow\ \left(  I\leq_{\#}J\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.gale.a.goal})}\right)  .
\end{align*}
This solves Exercise \ref{exe.gale} \textbf{(b)}.
\end{proof}

\begin{remark}
Recall that we have defined a \textit{Dyck word} as a list $w$ of $2n$
numbers, exactly $n$ of which are $0$'s while the other $n$ are $1$'s, and
having the property that for each $k\in\left[  2n\right]  $, the number of
$0$'s among the first $k$ entries of $w$ is $\leq$ to the number of $1$'s
among the first $k$ entries of $w$.

It is not hard to see the connection between the relation $\leq_{\#}$ and Dyck
words: Let $w=\left(  w_{1},w_{2},\ldots,w_{2n}\right)  \in\left\{
0,1\right\}  ^{2n}$ be a list of $2n$ numbers, exactly $n$ of which are $0$'s
while the other $n$ are $1$'s. Then, $w$ is a Dyck word if and only if%
\[
\left\{  i\in\left[  2n\right]  \ \mid\ w_{i}=1\right\}  \leq_{\#}\left\{
i\in\left[  2n\right]  \ \mid\ w_{i}=0\right\}
\]
(in other words, for every $r\in\left[  n\right]  $, the $r$-th appearance of
$1$ in $w$ precedes the $r$-th appearance of $0$ in $w$).
\end{remark}

\subsection{A rigorous approach to the existence of a cycle decomposition}

The purpose of the following exercise is to give a rigorous proof of the fact
that any permutation can be decomposed into disjoint cycles.

\begin{exercise}
\label{exe.perm.rig-cyc.1}Let $X$ be a finite set. Let $\sigma$ be a
permutation of $X$.

Define a binary relation $\sim$ on the set $X$ as follows: For two elements
$x\in X$ and $y\in X$, we set $x\sim y$ if and only if there exists some
$k\in\mathbb{N}$ such that $y=\sigma^{k}\left(  x\right)  $.

\textbf{(a)} Prove that $\sim$ is an equivalence relation.

For any $x\in X$, we let $\left[  x\right]  _{\sim}$ denote the $\sim
$-equivalence class of $x$.

\textbf{(b)} For any $x\in X$, prove that $\left[  x\right]  _{\sim}=\left\{
\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma
^{k-1}\left(  x\right)  \right\}  $, where $k=\left\vert \left[  x\right]
_{\sim}\right\vert $.

\textbf{(c)} For any $\sim$-equivalence class $E$, let us define $c_{E}$ to be
the map
\[
X\rightarrow X,\ \ \ \ \ \ \ \ \ \ x\mapsto%
\begin{cases}
\sigma\left(  x\right)  , & \text{if }x\in E;\\
x, & \text{if }x\notin E
\end{cases}
.
\]
Prove that $c_{E}$ is a permutation of $X$.

\textbf{(d)} Prove that if $E=\left[  x\right]  _{\sim}$ for some $x\in X$,
then $c_{E}$ can be written as $\operatorname*{cyc}\nolimits_{\sigma
^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{k-1}\left(
x\right)  }$, where $k=\left\vert \left[  x\right]  _{\sim}\right\vert $.
(Don't forget to show that $\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(
x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)  $ are distinct, so that
$\operatorname*{cyc}\nolimits_{\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(
x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)  }$ is well-defined.)

\textbf{(e)} Let $E_{1},E_{2},\ldots,E_{m}$ be all $\sim$-equivalence classes
(listed without repetitions -- that is, $E_{i}\neq E_{j}$ whenever $i\neq j$).
Prove that%
\[
\sigma=c_{E_{1}}\circ c_{E_{2}}\circ\cdots\circ c_{E_{m}}.
\]

\end{exercise}

Exercise \ref{exe.perm.rig-cyc.1} is mostly an exercise in understanding the
definitions and writing up proofs. The first two parts of it are similar to
Exercise 6 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw3os.pdf}{homework set \#3};
thus, our solution below is partly copypasted from the latter (with the
necessary changes made).

Our solution relies on a few lemmas:

\begin{lemma}
\label{lem.perm.rig-cyc.1.semigr}Let $X$ be a set. Let $f:X\rightarrow X$ be
any map. Let $x\in X$. Let $i$ and $j$ be two nonnegative integers satisfying
$i<j$ and $f^{i}\left(  x\right)  =f^{j}\left(  x\right)  $. Then,
\[
\left\{  f^{h}\left(  x\right)  \ \mid\ h\in\mathbb{N}\right\}  =\left\{
f^{0}\left(  x\right)  ,f^{1}\left(  x\right)  ,\ldots,f^{j-1}\left(
x\right)  \right\}  .
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.perm.rig-cyc.1.semigr}.]We have%
\begin{align}
\left\{  f^{0}\left(  x\right)  ,f^{1}\left(  x\right)  ,\ldots,f^{j-1}\left(
x\right)  \right\}   &  =\left\{  f^{h}\left(  x\right)  \ \mid\ h\in
\underbrace{\left\{  0,1,\ldots,j-1\right\}  }_{\subseteq\mathbb{N}}\right\}
\nonumber\\
&  \subseteq\left\{  f^{h}\left(  x\right)  \ \mid\ h\in\mathbb{N}\right\}  .
\label{pf.lem.perm.rig-cyc.1.semigr.easy-dir}%
\end{align}


On the other hand, we have $i\in\left\{  0,1,\ldots,j-1\right\}  $ (since $i$
is a nonnegative integer satisfying $i<j$), and thus $f^{i}\left(  x\right)
\in\left\{  f^{0}\left(  x\right)  ,f^{1}\left(  x\right)  ,\ldots
,f^{j-1}\left(  x\right)  \right\}  $. Hence, $\left\{  f^{i}\left(  x\right)
\right\}  \subseteq\left\{  f^{0}\left(  x\right)  ,f^{1}\left(  x\right)
,\ldots,f^{j-1}\left(  x\right)  \right\}  $. Therefore,%
\begin{align}
\left\{  f^{0}\left(  x\right)  ,f^{1}\left(  x\right)  ,\ldots,f^{j-1}\left(
x\right)  \right\}   &  =\left\{  f^{0}\left(  x\right)  ,f^{1}\left(
x\right)  ,\ldots,f^{j-1}\left(  x\right)  \right\}  \cup\left\{
\underbrace{f^{i}\left(  x\right)  }_{=f^{j}\left(  x\right)  }\right\}
\nonumber\\
&  =\left\{  f^{0}\left(  x\right)  ,f^{1}\left(  x\right)  ,\ldots
,f^{j-1}\left(  x\right)  \right\}  \cup\left\{  f^{j}\left(  x\right)
\right\} \nonumber\\
&  =\left\{  f^{0}\left(  x\right)  ,f^{1}\left(  x\right)  ,\ldots
,f^{j}\left(  x\right)  \right\}  . \label{pf.lem.perm.rig-cyc.1.semigr.j=j-1}%
\end{align}


Now,%
\begin{equation}
f^{h}\left(  x\right)  \in\left\{  f^{0}\left(  x\right)  ,f^{1}\left(
x\right)  ,\ldots,f^{j-1}\left(  x\right)  \right\}
\ \ \ \ \ \ \ \ \ \ \text{for each }h\in\mathbb{N}.
\label{pf.lem.perm.rig-cyc.1.semigr.1}%
\end{equation}


\begin{fns}
[\textit{Proof of (\ref{pf.lem.perm.rig-cyc.1.semigr.1}):} We shall prove
(\ref{pf.lem.perm.rig-cyc.1.semigr.1}) by induction over $h$:

\textit{Induction base:} We have $i<j$, hence $j>i\geq0$ and thus $j\geq1$
(since $j$ is an integer). Hence, $0\in\left\{  0,1,\ldots,j-1\right\}  $, so
that $f^{0}\left(  x\right)  \in\left\{  f^{0}\left(  x\right)  ,f^{1}\left(
x\right)  ,\ldots,f^{j-1}\left(  x\right)  \right\}  $. In other words,
(\ref{pf.lem.perm.rig-cyc.1.semigr.1}) holds for $h=0$. This completes the
induction base.

\textit{Induction step:} Let $g\in\mathbb{N}$. Assume that
(\ref{pf.lem.perm.rig-cyc.1.semigr.1}) holds for $h=g$. We must now show that
(\ref{pf.lem.perm.rig-cyc.1.semigr.1}) holds for $h=g+1$ as well.

We have assumed that (\ref{pf.lem.perm.rig-cyc.1.semigr.1}) holds for $h=g$.
In other words, $f^{g}\left(  x\right)  \in\left\{  f^{0}\left(  x\right)
,f^{1}\left(  x\right)  ,\ldots,f^{j-1}\left(  x\right)  \right\}  $. In other
words, there exists some $k\in\left\{  0,1,\ldots,j-1\right\}  $ such that
$f^{g}\left(  x\right)  =f^{k}\left(  x\right)  $. Consider this $k$.

We have $k\in\left\{  0,1,\ldots,j-1\right\}  $, so that $k+1\in\left\{
1,2,\ldots,j\right\}  \subseteq\left\{  0,1,\ldots,j\right\}  $ and therefore
\[
f^{k+1}\left(  x\right)  \in\left\{  f^{0}\left(  x\right)  ,f^{1}\left(
x\right)  ,\ldots,f^{j}\left(  x\right)  \right\}  =\left\{  f^{0}\left(
x\right)  ,f^{1}\left(  x\right)  ,\ldots,f^{j-1}\left(  x\right)  \right\}
\]
(by (\ref{pf.lem.perm.rig-cyc.1.semigr.j=j-1})). But%
\[
f^{g+1}\left(  x\right)  =f\left(  \underbrace{f^{g}\left(  x\right)
}_{=f^{k}\left(  x\right)  }\right)  =f\left(  f^{k}\left(  x\right)  \right)
=f^{k+1}\left(  x\right)  \in\left\{  f^{0}\left(  x\right)  ,f^{1}\left(
x\right)  ,\ldots,f^{j-1}\left(  x\right)  \right\}
\]
(as we have just proven). In other words,
(\ref{pf.lem.perm.rig-cyc.1.semigr.1}) holds for $h=g+1$ as well. This
completes the induction step. Thus, (\ref{pf.lem.perm.rig-cyc.1.semigr.1}) is proven.]
\end{fns}

From (\ref{pf.lem.perm.rig-cyc.1.semigr.1}), we immediately obtain%
\[
\left\{  f^{h}\left(  x\right)  \ \mid\ h\in\mathbb{N}\right\}  \subseteq
\left\{  f^{0}\left(  x\right)  ,f^{1}\left(  x\right)  ,\ldots,f^{j-1}\left(
x\right)  \right\}  .
\]
Combining this with (\ref{pf.lem.perm.rig-cyc.1.semigr.easy-dir}), we obtain%
\[
\left\{  f^{h}\left(  x\right)  \ \mid\ h\in\mathbb{N}\right\}  =\left\{
f^{0}\left(  x\right)  ,f^{1}\left(  x\right)  ,\ldots,f^{j-1}\left(
x\right)  \right\}  .
\]
This proves Lemma \ref{lem.perm.rig-cyc.1.semigr}.
\end{proof}

\begin{lemma}
\label{lem.perm.rig-cyc.2} Let $X$ be a finite set. Let $\sigma$ be a
permutation of $X$. Let $x\in X$.

\textbf{(a)} There exists a $j\in\mathbb{N}$ such that $\sigma^{j}\left(
x\right)  \in\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{j-1}\left(  x\right)  \right\}  $.

Let $p$ be the smallest such $j$.

\textbf{(b)} The integer $p$ is positive and satisfies $\sigma^{p}\left(
x\right)  =x$.

\textbf{(c)} The elements $\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(
x\right)  ,\ldots,\sigma^{p-1}\left(  x\right)  $ are pairwise distinct.

\textbf{(d)} We have $\left\{  \sigma^{h}\left(  x\right)  \ \mid
\ h\in\mathbb{N}\right\}  =\left\{  \sigma^{0}\left(  x\right)  ,\sigma
^{1}\left(  x\right)  ,\ldots,\sigma^{p-1}\left(  x\right)  \right\}  $.
\end{lemma}

\begin{proof}
[Proof of Lemma~\ref{lem.perm.rig-cyc.2}.]The map $\sigma$ is a permutation of
$X$. In other words, $\sigma$ is a bijection $X\rightarrow X$. Hence, $\sigma$
is injective.

\textbf{(a)} Define an $n\in\mathbb{N}$ by $n=\left\vert X\right\vert $. (This
is well-defined, since $X$ is a finite set.)

The $n+1$ elements $\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{n}\left(  x\right)  $ cannot all be distinct, because they all
belong to the $n$-element set $X$. Hence, at least two of these $n+1$ elements
are equal. In other words, there exist two elements $u$ and $v$ of $\left\{
0,1,\ldots,n\right\}  $ such that $u<v$ and $\sigma^{u}\left(  x\right)
=\sigma^{v}\left(  x\right)  $. Consider these $u$ and $v$.

We have $u\in\left\{  0,1,\ldots,n\right\}  \subseteq\mathbb{N}$. Thus,
$u\in\left\{  0,1,\ldots,v-1\right\}  $ (since $u<v$). Hence, $\sigma
^{u}\left(  x\right)  \in\left\{  \sigma^{0}\left(  x\right)  ,\sigma
^{1}\left(  x\right)  ,\ldots,\sigma^{v-1}\left(  x\right)  \right\}  $. In
view of $\sigma^{u}\left(  x\right)  =\sigma^{v}\left(  x\right)  $, this
rewrites as $\sigma^{v}\left(  x\right)  \in\left\{  \sigma^{0}\left(
x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{v-1}\left(  x\right)
\right\}  $. Thus, there exists a $j\in\mathbb{N}$ such that $\sigma
^{j}\left(  x\right)  \in\left\{  \sigma^{0}\left(  x\right)  ,\sigma
^{1}\left(  x\right)  ,\ldots,\sigma^{j-1}\left(  x\right)  \right\}  $
(namely, $j=v$). This proves Lemma~\ref{lem.perm.rig-cyc.2} \textbf{(a)}.

Now, let us study the $p$ in Lemma~\ref{lem.perm.rig-cyc.2}. We have defined
$p$ as the smallest $j\in\mathbb{N}$ such that $\sigma^{j}\left(  x\right)
\in\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{j-1}\left(  x\right)  \right\}  $. Thus, $p$ is an element of
$\mathbb{N}$ and satisfies $\sigma^{p}\left(  x\right)  \in\left\{  \sigma
^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{p-1}\left(
x\right)  \right\}  $. Hence, the set $\left\{  \sigma^{0}\left(  x\right)
,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{p-1}\left(  x\right)  \right\}  $
is nonempty (since it contains the element $\sigma^{p}\left(  x\right)  $).
Thus, $p\neq0$ (because if we had $p=0$, then the set $\left\{  \sigma
^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{p-1}\left(
x\right)  \right\}  $ would be empty). Hence, $p$ is a positive integer (since
$p\in\mathbb{N}$).

\textbf{(b)} We already know that $p$ is positive. It thus remains to show
that $\sigma^{p}\left(  x\right)  =x$.

Indeed, we have $\sigma^{p}\left(  x\right)  \in\left\{  \sigma^{0}\left(
x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{p-1}\left(  x\right)
\right\}  $. In other words, there exists some $i\in\left\{  0,1,\ldots
,p-1\right\}  $ such that $\sigma^{p}\left(  x\right)  =\sigma^{i}\left(
x\right)  $. Consider this $i$.

Next, we claim that $i=0$. We shall prove this by contradiction. Indeed,
assume the contrary. Thus, $i\neq0$, so that $i>0$ (since $i\in\mathbb{N}$).
Hence, $\sigma^{i}\left(  x\right)  =\sigma\left(  \sigma^{i-1}\left(
x\right)  \right)  $. But the integer $p$ is also positive; hence,
$p-1\in\mathbb{N}$ and $\sigma^{p}\left(  x\right)  =\sigma\left(
\sigma^{p-1}\left(  x\right)  \right)  $. Hence, $\sigma\left(  \sigma
^{p-1}\left(  x\right)  \right)  =\sigma^{p}\left(  x\right)  =\sigma\left(
\sigma^{i-1}\left(  x\right)  \right)  $. Since $\sigma$ is injective, we thus
conclude that $\sigma^{p-1}\left(  x\right)  =\sigma^{i-1}\left(  x\right)  $.
But $i-1\in\mathbb{N}$ (since $i>0$). From $i\in\left\{  0,1,\ldots
,p-1\right\}  $, we obtain $i-1\in\left\{  -1,0,\ldots,\left(  p-1\right)
-1\right\}  $. Combined with $i-1\in\mathbb{N}$, this yields $i-1\in\left\{
-1,0,\ldots,\left(  p-1\right)  -1\right\}  \cap\mathbb{N}=\left\{
0,1,\ldots,\left(  p-1\right)  -1\right\}  $. Hence, $\sigma^{i-1}\left(
x\right)  \in\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{\left(  p-1\right)  -1}\left(  x\right)  \right\}  $. Hence,%
\[
\sigma^{p-1}\left(  x\right)  =\sigma^{i-1}\left(  x\right)  \in\left\{
\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots
,\sigma^{\left(  p-1\right)  -1}\left(  x\right)  \right\}  .
\]
Thus, $p-1$ is a $j\in\mathbb{N}$ such that $\sigma^{j}\left(  x\right)
\in\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{j-1}\left(  x\right)  \right\}  $ (because $p-1\in\mathbb{N}%
$). But we defined $p$ to be the \textbf{smallest} such $j$. Hence, $p\leq
p-1$. This contradicts $p>p-1$. This contradiction shows that our assumption
was false; hence, we have shown that $i=0$. Therefore, $\sigma^{i}\left(
x\right)  =\underbrace{\sigma^{0}}_{=\operatorname*{id}}\left(  x\right)
=\operatorname*{id}\left(  x\right)  =x$.

Now, $\sigma^{p}\left(  x\right)  =\sigma^{i}\left(  x\right)  =x$. This
completes the proof of Lemma~\ref{lem.perm.rig-cyc.2} \textbf{(b)}.

\textbf{(c)} Assume the contrary. Thus, two of the elements $\sigma^{0}\left(
x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{p-1}\left(  x\right)  $
are equal. In other words, there exist two elements $u$ and $v$ of $\left\{
0,1,\ldots,p-1\right\}  $ such that $u<v$ and $\sigma^{u}\left(  x\right)
=\sigma^{v}\left(  x\right)  $. Consider these $u$ and $v$. Notice that $v\leq
p-1$ (since $v\in\left\{  0,1,\ldots,p-1\right\}  $).

From $u\in\left\{  0,1,\ldots,p-1\right\}  $, we obtain $u\geq0$. From $u<v$,
we obtain $u\leq v-1$ (since $u$ and $v$ are integers), so that $u\in\left\{
0,1,\ldots,v-1\right\}  $ (since $u\geq0$). Hence, $\sigma^{u}\left(
x\right)  \in\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{v-1}\left(  x\right)  \right\}  $. From $\sigma^{u}\left(
x\right)  =\sigma^{v}\left(  x\right)  $, we obtain $\sigma^{v}\left(
x\right)  =\sigma^{u}\left(  x\right)  \in\left\{  \sigma^{0}\left(  x\right)
,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{v-1}\left(  x\right)  \right\}
$. Thus, $v$ is a $j\in\mathbb{N}$ such that $\sigma^{j}\left(  x\right)
\in\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{j-1}\left(  x\right)  \right\}  $ (because $v\in\mathbb{N}$).
But we defined $p$ to be the \textbf{smallest} such $j$. Hence, $p\leq v$.
This contradicts $v\leq p-1<p$. This contradiction shows that our assumption
was false. Thus, Lemma~\ref{lem.perm.rig-cyc.2} \textbf{(c)} is proven.

\textbf{(d)} We have $\sigma^{p}\left(  x\right)  \in\left\{  \sigma
^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{p-1}\left(
x\right)  \right\}  $. In other words, there exists some $i\in\left\{
0,1,\ldots,p-1\right\}  $ such that $\sigma^{p}\left(  x\right)  =\sigma
^{i}\left(  x\right)  $. Consider this $i$. Hence, $i<p$ (since $i\in\left\{
0,1,\ldots,p-1\right\}  $) and $\sigma^{i}\left(  x\right)  =\sigma^{p}\left(
x\right)  $. Thus, Lemma \ref{lem.perm.rig-cyc.1.semigr} (applied to
$f=\sigma$ and $j=p$) yields%
\[
\left\{  \sigma^{h}\left(  x\right)  \ \mid\ h\in\mathbb{N}\right\}  =\left\{
\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma
^{p-1}\left(  x\right)  \right\}  .
\]
This proves Lemma~\ref{lem.perm.rig-cyc.2} \textbf{(d)}.
\end{proof}

\begin{lemma}
\label{lem.perm.rig-cyc.o2}Let $X$ be a set. Let $f:X\rightarrow X$ be any
map. Let $x\in X$. Let $p\in\mathbb{N}$ be such that $f^{p}\left(  x\right)
=x$. Then, $f^{kp}\left(  x\right)  =x$ for each $k\in\mathbb{N}$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.perm.rig-cyc.o2}.]Lemma \ref{lem.perm.rig-cyc.o2} is
intuitively obvious: All it says is that if applying the map $f$ to $x$ a
total of $p$ times brings you back to $x$, then applying the map $f$ to $x$ a
total of $kp$ times brings you back to $x$ as well. This intuition can easily
be translated into a rigorous argument:

\begin{fns}
We shall prove Lemma \ref{lem.perm.rig-cyc.o2} by induction over $k$:

\textit{Induction base:} We have $f^{0p}=f^{0}=\operatorname*{id}%
\nolimits_{X}$, so that $f^{0p}\left(  x\right)  =\operatorname*{id}%
\nolimits_{X}\left(  x\right)  =x$. Thus, Lemma \ref{lem.perm.rig-cyc.o2}
holds for $k=0$. This completes the induction base.

\textit{Induction step:} Let $m\in\mathbb{N}$. Assume that Lemma
\ref{lem.perm.rig-cyc.o2} holds for $k=m$. We must prove that Lemma
\ref{lem.perm.rig-cyc.o2} holds for $k=m+1$.

Let $x\in X$. Let $p\in\mathbb{N}$ be such that $f^{p}\left(  x\right)  =x$.
Then, $f^{mp}\left(  x\right)  =x$ (since Lemma \ref{lem.perm.rig-cyc.o2}
holds for $k=m$). But $f^{mp}\circ f^{p}=f^{mp+p}=f^{\left(  m+1\right)  p}$.
Hence, $\left(  f^{mp}\circ f^{p}\right)  \left(  x\right)  =f^{\left(
m+1\right)  p}\left(  x\right)  $, and therefore%
\[
f^{\left(  m+1\right)  p}\left(  x\right)  =\left(  f^{mp}\circ f^{p}\right)
\left(  x\right)  =f^{mp}\left(  \underbrace{f^{p}\left(  x\right)  }%
_{=x}\right)  =f^{mp}\left(  x\right)  =x.
\]
In other words, Lemma \ref{lem.perm.rig-cyc.o2} holds for $k=m+1$. This
completes the induction step. Thus, Lemma \ref{lem.perm.rig-cyc.o2} is proven.
\end{fns}
\end{proof}

\begin{lemma}
\label{lem.compose-disjoint-maps}Let $X$ be a set. Let $m\in\mathbb{N}$. Let
$f_{1},f_{2},\ldots,f_{m}$ be $m$ maps from $X$ to $X$. Let $x$ and $y$ be two
elements of $X$.

Let $i\in\left[  m\right]  $. Assume that $f_{i}\left(  x\right)  =y$. Assume
further that%
\begin{equation}
f_{j}\left(  x\right)  =x\ \ \ \ \ \ \ \ \ \ \text{for each }j\in\left[
m\right]  \text{ satisfying }j<i. \label{eq.lem.compose-disjoint-maps.ass1}%
\end{equation}
Assume also that%
\begin{equation}
f_{j}\left(  y\right)  =y\ \ \ \ \ \ \ \ \ \ \text{for each }j\in\left[
m\right]  \text{ satisfying }j>i. \label{eq.lem.compose-disjoint-maps.ass2}%
\end{equation}
Then, $\left(  f_{m}\circ f_{m-1}\circ\cdots\circ f_{1}\right)  \left(
x\right)  =y$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.compose-disjoint-maps}.]The idea behind this proof is
very simple (if we don't insist on being rigorous): Imagine the element $x$
undergoing the maps $f_{1},f_{2},\ldots,f_{m}$ in this order; the result is,
of course, $\left(  f_{m}\circ f_{m-1}\circ\cdots\circ f_{1}\right)  \left(
x\right)  $. But let us look closer at the step-by-step procedure. The element
is initially $x$. Then, the maps $f_{1},f_{2},\ldots,f_{m}$ are being applied
to it in this order. Up until the map $f_{i}$ is applied, the element does not
change (because of (\ref{eq.lem.compose-disjoint-maps.ass1})). Then, the map
$f_{i}$ is applied, and the element becomes $y$ (since $f_{i}\left(  x\right)
=y$). From then on, the maps $f_{i+1},f_{i+2},\ldots,f_{m}$ again leave the
element unchanged (due to (\ref{eq.lem.compose-disjoint-maps.ass2})). Thus,
the final result is $y$. This shows that $\left(  f_{m}\circ f_{m-1}%
\circ\cdots\circ f_{1}\right)  \left(  x\right)  =y$.

\begin{fns}
Let us now rewrite the above argument in rigorous terms.

We have $i\in\left[  m\right]  $, so that $1\leq i\leq m$. Now, we claim the following:

\begin{statement}
\textit{Observation 1:} We have $\left(  f_{g}\circ f_{g-1}\circ\cdots\circ
f_{1}\right)  \left(  x\right)  =%
\begin{cases}
x, & \text{if }g<i;\\
y, & \text{if }g\geq i
\end{cases}
$ for each $g\in\left\{  0,1,\ldots,m\right\}  $.
\end{statement}

[\textit{Proof of Observation 1:} We shall prove Observation 1 by induction on
$g$:

\textit{Induction base:} We have $0<i$ (since $i\in\left[  m\right]  $). Thus,
$%
\begin{cases}
x, & \text{if }0<i;\\
y, & \text{if }0\geq i
\end{cases}
=x$. Comparing this with%
\[
\underbrace{\left(  f_{0}\circ f_{0-1}\circ\cdots\circ f_{1}\right)
}_{\substack{=\left(  \text{empty composition of maps }X\rightarrow X\right)
\\=\operatorname*{id}}}\left(  x\right)  =\operatorname*{id}\left(  x\right)
=x,
\]
we obtain $\left(  f_{0}\circ f_{0-1}\circ\cdots\circ f_{1}\right)  \left(
x\right)  =%
\begin{cases}
x, & \text{if }0<i;\\
y, & \text{if }0\geq i
\end{cases}
$. In other words, Observation 1 holds for $g=0$. This completes the induction base.

\textit{Induction step:} Let $h\in\left\{  0,1,\ldots,m\right\}  $ be
positive. Assume that Observation 1 holds for $g=h-1$. We must then prove that
Observation 1 holds for $g=h$.

We have
\begin{equation}
f_{h}\left(
\begin{cases}
x, & \text{if }h-1<i;\\
y, & \text{if }h-1\geq i
\end{cases}
\right)  =%
\begin{cases}
x, & \text{if }h<i;\\
y, & \text{if }h\geq i
\end{cases}
\label{pf.lem.compose-disjoint-maps.3}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.compose-disjoint-maps.3}):} We are in
one of the following three cases:
\par
\textit{Case 1:} We have $h<i$.
\par
\textit{Case 2:} We have $h=i$.
\par
\textit{Case 3:} We have $h>i$.
\par
Let us first consider Case 1. In this case, we have $h<i$. Thus, $%
\begin{cases}
x, & \text{if }h<i;\\
y, & \text{if }h\geq i
\end{cases}
=x$.
\par
Applying (\ref{eq.lem.compose-disjoint-maps.ass1}) to $j=h$, we find
$f_{h}\left(  x\right)  =x$ (since $h<i$).
\par
Also, $h-1<h<i$. Hence, $%
\begin{cases}
x, & \text{if }h-1<i;\\
y, & \text{if }h-1\geq i
\end{cases}
=x$. Applying the map $f_{h}$ to this equality, we obtain%
\[
f_{h}\left(
\begin{cases}
x, & \text{if }h-1<i;\\
y, & \text{if }h-1\geq i
\end{cases}
\right)  =f_{h}\left(  x\right)  =x=%
\begin{cases}
x, & \text{if }h<i;\\
y, & \text{if }h\geq i
\end{cases}
.
\]
Hence, (\ref{pf.lem.compose-disjoint-maps.3}) is proven in Case 1.
\par
Let us now consider case 2. In this case, we have $h=i$. Thus, $h\geq i$.
Hence, $%
\begin{cases}
x, & \text{if }h<i;\\
y, & \text{if }h\geq i
\end{cases}
=y$.
\par
From $h=i$, we obtain $f_{h}\left(  x\right)  =f_{i}\left(  x\right)  =y$.
\par
Also, $h-1<h=i$. Hence, $%
\begin{cases}
x, & \text{if }h-1<i;\\
y, & \text{if }h-1\geq i
\end{cases}
=x$. Applying the map $f_{h}$ to this equality, we obtain%
\[
f_{h}\left(
\begin{cases}
x, & \text{if }h-1<i;\\
y, & \text{if }h-1\geq i
\end{cases}
\right)  =f_{h}\left(  x\right)  =y=%
\begin{cases}
x, & \text{if }h<i;\\
y, & \text{if }h\geq i
\end{cases}
.
\]
Hence, (\ref{pf.lem.compose-disjoint-maps.3}) is proven in Case 2.
\par
Let us first consider Case 3. In this case, we have $h>i$. Thus, $h\geq i$, so
that $%
\begin{cases}
x, & \text{if }h<i;\\
y, & \text{if }h\geq i
\end{cases}
=y$.
\par
Applying (\ref{eq.lem.compose-disjoint-maps.ass2}) to $j=h$, we find
$f_{h}\left(  y\right)  =y$ (since $h>i$).
\par
Also, $h>i$, so that $h\geq i+1$ (since $h$ and $i$ are integers). Thus,
$h-1\geq i$. Hence, $%
\begin{cases}
x, & \text{if }h-1<i;\\
y, & \text{if }h-1\geq i
\end{cases}
=y$. Applying the map $f_{h}$ to this equality, we obtain%
\[
f_{h}\left(
\begin{cases}
x, & \text{if }h-1<i;\\
y, & \text{if }h-1\geq i
\end{cases}
\right)  =f_{h}\left(  y\right)  =y=%
\begin{cases}
x, & \text{if }h<i;\\
y, & \text{if }h\geq i
\end{cases}
.
\]
Hence, (\ref{pf.lem.compose-disjoint-maps.3}) is proven in Case 3.
\par
We have now proven (\ref{pf.lem.compose-disjoint-maps.3}) in each of the three
Cases 1, 2 and 3 (which are the only cases that can occur). Thus,
(\ref{pf.lem.compose-disjoint-maps.3}) always holds.}.

But we assumed that Observation 1 holds for $g=h-1$. In other words, we have
\[
\left(  f_{h-1}\circ f_{\left(  h-1\right)  -1}\circ\cdots\circ f_{1}\right)
\left(  x\right)  =%
\begin{cases}
x, & \text{if }h-1<i;\\
y, & \text{if }h-1\geq i
\end{cases}
.
\]


Now,%
\begin{align*}
\underbrace{\left(  f_{h}\circ f_{h-1}\circ\cdots\circ f_{1}\right)
}_{\substack{=f_{h}\circ\left(  f_{h-1}\circ f_{h-2}\circ\cdots\circ
f_{1}\right)  \\=f_{h}\circ\left(  f_{h-1}\circ f_{\left(  h-1\right)
-1}\circ\cdots\circ f_{1}\right)  }}\left(  x\right)   &  =\left(  f_{h}%
\circ\left(  f_{h-1}\circ f_{\left(  h-1\right)  -1}\circ\cdots\circ
f_{1}\right)  \right)  \left(  x\right) \\
&  =f_{h}\left(  \underbrace{\left(  f_{h-1}\circ f_{\left(  h-1\right)
-1}\circ\cdots\circ f_{1}\right)  \left(  x\right)  }_{=%
\begin{cases}
x, & \text{if }h-1<i;\\
y, & \text{if }h-1\geq i
\end{cases}
}\right) \\
&  =f_{h}\left(
\begin{cases}
x, & \text{if }h-1<i;\\
y, & \text{if }h-1\geq i
\end{cases}
\right)  =%
\begin{cases}
x, & \text{if }h<i;\\
y, & \text{if }h\geq i
\end{cases}
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{pf.lem.compose-disjoint-maps.3}%
)}\right)  .
\end{align*}
In other words, Observation 1 holds for $g=h$. This completes the induction
step. Thus, Observation 1 is proven.]

We can now apply Observation 1 to $g=m$. We thus obtain%
\[
\left(  f_{m}\circ f_{m-1}\circ\cdots\circ f_{1}\right)  \left(  x\right)  =%
\begin{cases}
x, & \text{if }m<i;\\
y, & \text{if }m\geq i
\end{cases}
=y
\]
(since $m\geq i$ (since $i\leq m$)). This proves Lemma
\ref{lem.compose-disjoint-maps}.
\end{fns}
\end{proof}

\begin{lemma}
\label{lem.compose-disjoint-maps2}Let $X$ be a set. Let $m\in\mathbb{N}$. Let
$g_{1},g_{2},\ldots,g_{m}$ be $m$ maps from $X$ to $X$. Let $x$ and $y$ be two
elements of $X$.

Let $i\in\left[  m\right]  $. Assume that $g_{i}\left(  x\right)  =y$. Assume
further that%
\begin{equation}
g_{j}\left(  x\right)  =x\ \ \ \ \ \ \ \ \ \ \text{for each }j\in\left[
m\right]  \text{ satisfying }j>i. \label{eq.lem.compose-disjoint-maps2.ass1}%
\end{equation}
Assume also that%
\begin{equation}
g_{j}\left(  y\right)  =y\ \ \ \ \ \ \ \ \ \ \text{for each }j\in\left[
m\right]  \text{ satisfying }j<i. \label{eq.lem.compose-disjoint-maps2.ass2}%
\end{equation}
Then, $\left(  g_{1}\circ g_{2}\circ\cdots\circ g_{m}\right)  \left(
x\right)  =y$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.compose-disjoint-maps2}.]Lemma
\ref{lem.compose-disjoint-maps2} follows by applying Lemma
\ref{lem.compose-disjoint-maps} to $g_{m},g_{m-1},\ldots,g_{1}$ instead of
$f_{1},f_{2},\ldots,f_{m}$.

\begin{fns}
Here is the argument in more detail:

For each $j\in\left[  m\right]  $, we define a map $f_{j}$ from $X$ to $X$ by
$f_{j}=g_{m+1-j}$.

From $i\in\left[  m\right]  $, we obtain $m+1-i\in\left[  m\right]  $. Thus,
we can define $i^{\prime}\in\left[  m\right]  $ by $i^{\prime}=m+1-i$.
Consider this $i^{\prime}$. From $i^{\prime}=m+1-i$, we obtain $m+1-i^{\prime
}=i$. Now, the definition of $f_{i^{\prime}}$ yields $f_{i^{\prime}%
}=g_{m+1-i^{\prime}}=g_{i}$ (since $m+1-i^{\prime}=i$). Thus, $f_{i^{\prime}%
}\left(  x\right)  =g_{i}\left(  x\right)  =y$.

Furthermore, $f_{j}\left(  x\right)  =x$ for each $j\in\left[  m\right]  $
satisfying $j<i^{\prime}$\ \ \ \ \footnote{\textit{Proof.} Let $j\in\left[
m\right]  $ be such that $j<i^{\prime}$. Then, $m+1-j\in\left[  m\right]  $
(since $j\in\left[  m\right]  $) and $m+1-\underbrace{j}_{<i^{\prime}%
}>m+1-i^{\prime}=i$. Hence, (\ref{eq.lem.compose-disjoint-maps2.ass1})
(applied to $m+1-j$ instead of $j$) yields $g_{m+1-j}\left(  x\right)  =x$.
But the definition of $f_{j}$ yields $f_{j}=g_{m+1-j}$. Thus, $f_{j}\left(
x\right)  =g_{m+1-j}\left(  x\right)  =x$. Qed.}. Also, $f_{j}\left(
y\right)  =y$ for each $j\in\left[  m\right]  $ satisfying $j>i^{\prime}%
$\ \ \ \ \footnote{\textit{Proof.} Let $j\in\left[  m\right]  $ be such that
$j>i^{\prime}$. Then, $m+1-j\in\left[  m\right]  $ (since $j\in\left[
m\right]  $) and $m+1-\underbrace{j}_{>i^{\prime}}<m+1-i^{\prime}=i$. Hence,
(\ref{eq.lem.compose-disjoint-maps2.ass2}) (applied to $m+1-j$ instead of $j$)
yields $g_{m+1-j}\left(  y\right)  =y$. But the definition of $f_{j}$ yields
$f_{j}=g_{m+1-j}$. Thus, $f_{j}\left(  y\right)  =g_{m+1-j}\left(  y\right)
=y$. Qed.}. Hence, Lemma \ref{lem.compose-disjoint-maps} (applied to
$i^{\prime}$ instead of $i$) yields $\left(  f_{m}\circ f_{m-1}\circ
\cdots\circ f_{1}\right)  \left(  x\right)  =y$.

But each $j\in\left[  m\right]  $ satisfies
\begin{align*}
f_{m+1-j}  &  =g_{m+1-\left(  m+1-j\right)  }\ \ \ \ \ \ \ \ \ \ \left(
\text{by the definition of }f_{m+1-j}\right) \\
&  =g_{j}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }m+1-\left(  m+1-j\right)
=j\right)  .
\end{align*}
In other words, we have $\left(  f_{m},f_{m-1},\ldots,f_{1}\right)  =\left(
g_{1},g_{2},\ldots,g_{m}\right)  $. Hence, $f_{m}\circ f_{m-1}\circ\cdots\circ
f_{1}=g_{1}\circ g_{2}\circ\cdots\circ g_{m}$. Hence, $\left(  f_{m}\circ
f_{m-1}\circ\cdots\circ f_{1}\right)  \left(  x\right)  =\left(  g_{1}\circ
g_{2}\circ\cdots\circ g_{m}\right)  \left(  x\right)  $. Therefore,%
\[
\left(  g_{1}\circ g_{2}\circ\cdots\circ g_{m}\right)  \left(  x\right)
=\left(  f_{m}\circ f_{m-1}\circ\cdots\circ f_{1}\right)  \left(  x\right)
=y.
\]
This proves Lemma \ref{lem.compose-disjoint-maps2}.
\end{fns}
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.perm.rig-cyc.1} (sketched).]The map $\sigma$ is
a permutation of $X$, thus a bijection $X\rightarrow X$. Hence, in particular,
$\sigma$ is injective.

Before we properly start solving the exercise, let us make some basic observations:

\begin{statement}
\textit{Observation 1.} For every $x\in X$, there exists some positive integer
$p$ such that $\sigma^{p}\left(  x\right)  =x$.
\end{statement}

\begin{fns}
[\textit{Proof of Observation 1:} Let $x\in X$. Let $n=\left\vert X\right\vert
$. The $n+1$ elements $\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(
x\right)  ,\ldots,\sigma^{n}\left(  x\right)  $ cannot all be distinct,
because they belong to the $n$-element set $X$. Hence, at least two of these
$n+1$ elements are equal. In other words, there exist two elements $i$ and $j$
of $\left\{  0,1,\ldots,n\right\}  $ such that $i<j$ and $\sigma^{i}\left(
x\right)  =\sigma^{j}\left(  x\right)  $. Consider these $i$ and $j$. From
$i<j$, we conclude that $j-i$ is a positive integer. Thus, $\sigma^{j}%
=\sigma^{i}\circ\sigma^{j-i}$.

Also, the map $\sigma^{i}$ is injective (since the map $\sigma$ is injective,
but any composition of injective maps is injective). Hence, from
\[
\sigma^{i}\left(  x\right)  =\underbrace{\sigma^{j}}_{=\sigma^{i}\circ
\sigma^{j-i}}\left(  x\right)  =\left(  \sigma^{i}\circ\sigma^{j-i}\right)
\left(  x\right)  =\sigma^{i}\left(  \sigma^{j-i}\left(  x\right)  \right)  ,
\]
we obtain $x=\sigma^{j-i}\left(  x\right)  $. In other words, $\sigma
^{j-i}\left(  x\right)  =x$. Hence, there exists some positive integer $p$
such that $\sigma^{p}\left(  x\right)  =x$ (namely, $p=j-i$). This proves
Observation 1.]
\end{fns}

Now, we must show that $\sim$ is an equivalence relation. Indeed, the relation
$\sim$ is reflexive\footnote{\textit{Proof.} Let $x\in X$. We shall show that
$x\sim x$.
\par
Indeed, $\sigma^{0}=\operatorname*{id}\nolimits_{X}$, so that $\sigma
^{0}\left(  x\right)  =\operatorname*{id}\nolimits_{X}\left(  x\right)  =x$.
Hence, there exists some $k\in\mathbb{N}$ such that $x=\sigma^{k}\left(
x\right)  $ (namely, $k=0$). In other words, $x\sim x$ (by the definition of
the relation $\sim$).
\par
Now, forget that we fixed $x$. We thus have shown that every $x\in X$
satisfies $x\sim x$. In other words, the relation $\sim$ is reflexive.},
symmetric\footnote{\textit{Proof.} Let $x\in X$ and $y\in X$ be such that
$x\sim y$. We shall show that $y\sim x$.
\par
Indeed, we have $x\sim y$. In other words, there exists some $k\in\mathbb{N}$
such that $y=\sigma^{k}\left(  x\right)  $ (by the definition of the relation
$\sim$). Consider such a $k$, and denote it by $u$. Thus, $u\in\mathbb{N}$
satisfies $y=\sigma^{u}\left(  x\right)  $.
\par
Observation 1 yields that there exists some positive integer $p$ such that
$\sigma^{p}\left(  x\right)  =x$. Consider this $p$. Hence, Lemma
\ref{lem.perm.rig-cyc.o2} (applied to $f=\sigma$ and $k=u$) yields
$\sigma^{up}\left(  x\right)  =x$. But $p$ is positive; hence, $p\geq1$ and
thus $up\geq u1=u$. Hence, $up-u\in\mathbb{N}$. Hence, $\sigma^{up-u}%
\circ\sigma^{u}=\sigma^{\left(  up-u\right)  +u}=\sigma^{up}$. Thus, $\left(
\sigma^{up-u}\circ\sigma^{u}\right)  \left(  x\right)  =\sigma^{up}\left(
x\right)  =x$. Hence, $x=\left(  \sigma^{up-u}\circ\sigma^{u}\right)  \left(
x\right)  =\sigma^{up-u}\left(  \underbrace{\sigma^{u}\left(  x\right)  }%
_{=y}\right)  =\sigma^{up-u}\left(  y\right)  $. Thus, there exists some
$k\in\mathbb{N}$ such that $x=\sigma^{k}\left(  y\right)  $ (namely,
$k=up-u$). In other words, $y\sim x$ (by the definition of the relation $\sim
$).
\par
Now, forget that we fixed $x$ and $y$. We thus have shown that if $x\in X$ and
$y\in X$ satisfy $x\sim y$, then $y\sim x$. In other words, the relation
$\sim$ is symmetric.} and transitive\footnote{\textit{Proof.} Let $x\in X$,
$y\in X$ and $z\in X$ be such that $x\sim y$ and $y\sim z$. We shall show that
$x\sim z$.
\par
Indeed, we have $x\sim y$. In other words, there exists some $k\in\mathbb{N}$
such that $y=\sigma^{k}\left(  x\right)  $ (by the definition of the relation
$\sim$). Consider such a $k$, and denote it by $u$. Thus, $u\in\mathbb{N}$
satisfies $y=\sigma^{u}\left(  x\right)  $.
\par
Also, we have $y\sim z$. In other words, there exists some $k\in\mathbb{N}$
such that $z=\sigma^{k}\left(  y\right)  $ (by the definition of the relation
$\sim$). Consider such a $k$, and denote it by $v$. Thus, $v\in\mathbb{N}$
satisfies $z=\sigma^{v}\left(  y\right)  $.
\par
But $\sigma^{v}\circ\sigma^{u}=\sigma^{v+u}$. Thus, $\left(  \sigma^{v}%
\circ\sigma^{u}\right)  \left(  x\right)  =\sigma^{v+u}\left(  x\right)  $. In
view of $\left(  \sigma^{v}\circ\sigma^{u}\right)  \left(  x\right)
=\sigma^{v}\left(  \underbrace{\sigma^{u}\left(  x\right)  }_{=y}\right)
=\sigma^{v}\left(  y\right)  =z$, this rewrites as $z=\sigma^{v+u}\left(
x\right)  $. Thus, there exists some $k\in\mathbb{N}$ such that $z=\sigma
^{k}\left(  x\right)  $ (namely, $k=v+u$). In other words, $x\sim z$ (by the
definition of the relation $\sim$).
\par
Now, forget that we fixed $x$, $y$ and $z$. We thus have shown that if $x\in
X$, $y\in X$ and $z\in X$ satisfy $x\sim y$ and $y\sim z$, then $x\sim z$. In
other words, the relation $\sim$ is transitive.}. In other words, the relation
$\sim$ is an equivalence relation. This solves Exercise
\ref{exe.perm.rig-cyc.1} \textbf{(a)}.

\textbf{(b)} Let $x\in X$. Lemma \ref{lem.perm.rig-cyc.2} \textbf{(a)} shows
that there exists a $j\in\mathbb{N}$ such that $\sigma^{j}\left(  x\right)
\in\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{j-1}\left(  x\right)  \right\}  $. Let $p$ be the smallest
such $j$.

Lemma \ref{lem.perm.rig-cyc.2} \textbf{(b)} shows that the integer $p$ is
positive and satisfies $\sigma^{p}\left(  x\right)  =x$. Lemma
\ref{lem.perm.rig-cyc.2} \textbf{(c)} shows that the elements $\sigma
^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{p-1}\left(
x\right)  $ are pairwise distinct. Lemma \ref{lem.perm.rig-cyc.2} \textbf{(d)}
shows that $\left\{  \sigma^{h}\left(  x\right)  \ \mid\ h\in\mathbb{N}%
\right\}  =\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{p-1}\left(  x\right)  \right\}  $.

Define a set $S$ by $S=\left\{  \sigma^{h}\left(  x\right)  \ \mid
\ h\in\mathbb{N}\right\}  $. Thus,%
\[
S=\left\{  \sigma^{h}\left(  x\right)  \ \mid\ h\in\mathbb{N}\right\}
=\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{p-1}\left(  x\right)  \right\}  .
\]


The definition of the equivalence class $\left[  x\right]  _{\sim}$ of $x$
shows that
\[
\left[  x\right]  _{\sim}=\left\{  y\in X\ \mid\ y\sim x\right\}  .
\]


Now, $\left[  x\right]  _{\sim}\subseteq S$\ \ \ \ \footnote{\textit{Proof.}
Let $w\in\left[  x\right]  _{\sim}$. Thus, $w\in\left[  x\right]  _{\sim
}=\left\{  y\in X\ \mid\ y\sim x\right\}  $. In other words, $w$ is an element
of $X$ and satisfies $w\sim x$.
\par
We have $w\sim x$. Hence, $x\sim w$ (since the relation $\sim$ is symmetric).
In other words, there exists some $k\in\mathbb{N}$ such that $w=\sigma
^{k}\left(  x\right)  $ (by the definition of the relation $\sim$). Consider
this $k$. We have $w=\sigma^{k}\left(  x\right)  \in\left\{  \sigma^{h}\left(
x\right)  \ \mid\ h\in\mathbb{N}\right\}  =S$.
\par
Now, forget that we fixed $w$. We thus have shown that $w\in S$ for each
$w\in\left[  x\right]  _{\sim}$. In other words, $\left[  x\right]  _{\sim
}\subseteq S$.} and $S\subseteq\left[  x\right]  _{\sim}$%
\ \ \ \ \footnote{\textit{Proof.} Let $w\in S$. Thus, $w\in S=\left\{
\sigma^{h}\left(  x\right)  \ \mid\ h\in\mathbb{N}\right\}  $. In other words,
$w=\sigma^{h}\left(  x\right)  $ for some $h\in\mathbb{N}$. Consider this $h$.
\par
There exists some $k\in\mathbb{N}$ such that $w=\sigma^{k}\left(  x\right)  $
(namely, $k=h$). In other words, $x\sim w$ (by the definition of the relation
$\sim$). Thus, $w\sim x$ (since the relation $\sim$ is symmetric).
\par
Hence, $w$ is an element of $X$ and satisfies $w\sim x$. In other words,
$w\in\left\{  y\in X\ \mid\ y\sim x\right\}  $. In view of $\left[  x\right]
_{\sim}=\left\{  y\in X\ \mid\ y\sim x\right\}  $, this rewrites as
$w\in\left[  x\right]  _{\sim}$.
\par
Now, forget that we fixed $w$. We thus have shown that $w\in\left[  x\right]
_{\sim}$ for each $w\in S$. In other words, $S\subseteq\left[  x\right]
_{\sim}$.}. Combining these two relations, we obtain $\left[  x\right]
_{\sim}=S=\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{p-1}\left(  x\right)  \right\}  $.

The $p$ elements $\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{p-1}\left(  x\right)  $ are pairwise distinct (as we have seen
above). Thus, $\left\vert \left\{  \sigma^{0}\left(  x\right)  ,\sigma
^{1}\left(  x\right)  ,\ldots,\sigma^{p-1}\left(  x\right)  \right\}
\right\vert =p$.

Let $k=\left\vert \left[  x\right]  _{\sim}\right\vert $. Then,%
\[
k=\left\vert \left[  x\right]  _{\sim}\right\vert =\left\vert \left\{
\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma
^{p-1}\left(  x\right)  \right\}  \right\vert =p.
\]
Now,%
\[
\left[  x\right]  _{\sim}=\left\{  \sigma^{0}\left(  x\right)  ,\sigma
^{1}\left(  x\right)  ,\ldots,\sigma^{p-1}\left(  x\right)  \right\}
=\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{k-1}\left(  x\right)  \right\}
\]
(since $p=k$). This solves Exercise \ref{exe.perm.rig-cyc.1} \textbf{(b)}.

\textbf{(c)} Let $E$ be a $\sim$-equivalence class. We must prove that $c_{E}$
is a permutation of $X$.

It is clear that $c_{E}$ is well-defined. Next, we claim that%
\begin{equation}
t\in c_{E}\left(  X\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }t\in X.
\label{sol.perm.rig-cyc.1.c.1}%
\end{equation}


\begin{fns}
[\textit{Proof of (\ref{sol.perm.rig-cyc.1.c.1}):} Let $t\in X$. We must prove
that $t\in c_{E}\left(  X\right)  $.

We are in one of the following two cases:

\textit{Case 1:} We have $t\in E$.

\textit{Case 2:} We have $t\notin E$.

Let us first consider Case 1. In this case, we have $t\in E$. But $E$ is an
$\sim$-equivalence class. Hence, $E$ is an $\sim$-equivalence class containing
$t$ (since $t\in E$). In other words, $E=\left[  t\right]  _{\sim}$ (since the
only $\sim$-equivalence class containing $t$ is $\left[  t\right]  _{\sim}$).

Recall that $\sigma$ is a permutation of $X$. Hence, an element $\sigma
^{-1}\left(  t\right)  $ of $X$ is well-defined. Denote this element by $z$.
Thus, $z=\sigma^{-1}\left(  t\right)  $. Hence, $\sigma\left(  z\right)  =t$.

We have $\underbrace{\sigma^{1}}_{=\sigma}\left(  z\right)  =\sigma\left(
z\right)  =t$, so that $t=\sigma^{1}\left(  z\right)  $. Hence, there exists
some $k\in\mathbb{N}$ such that $t=\sigma^{k}\left(  z\right)  $ (namely,
$k=1$). In other words, $z\sim t$ (by the definition of the relation $\sim$).
Hence, $z$ is an element of $X$ and satisfies $z\sim t$. In other words,
$z\in\left\{  y\in X\ \mid\ y\sim t\right\}  $. But $E=\left[  t\right]
_{\sim}=\left\{  y\in X\ \mid\ y\sim t\right\}  $ (by the definition of the
equivalence class $\left[  t\right]  _{\sim}$). Hence, $z\in\left\{  y\in
X\ \mid\ y\sim t\right\}  =E$. The definition of $c_{E}$ yields
\begin{align*}
c_{E}\left(  z\right)   &  =%
\begin{cases}
\sigma\left(  z\right)  , & \text{if }z\in E;\\
z, & \text{if }z\notin E
\end{cases}
=\sigma\left(  z\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }z\in
E\right) \\
&  =t.
\end{align*}
Hence, $t=c_{E}\left(  \underbrace{z}_{\in X}\right)  \in c_{E}\left(
X\right)  $. Thus, we have proven $t\in c_{E}\left(  X\right)  $ in Case 1.

Let us now consider Case 2. In this case, we have $t\notin E$. The definition
of $c_{E}$ yields
\[
c_{E}\left(  t\right)  =%
\begin{cases}
\sigma\left(  t\right)  , & \text{if }t\in E;\\
t, & \text{if }t\notin E
\end{cases}
=t\ \ \ \ \ \ \ \ \ \ \left(  \text{since }t\notin E\right)  .
\]
Hence, $t=c_{E}\left(  \underbrace{t}_{\in X}\right)  \in c_{E}\left(
X\right)  $. Thus, we have proven $t\in c_{E}\left(  X\right)  $ in Case 2.

We have now proven $t\in c_{E}\left(  X\right)  $ in each of the two Cases 1
and 2. Hence, $t\in c_{E}\left(  X\right)  $ is proven. This proves
(\ref{sol.perm.rig-cyc.1.c.1}).]
\end{fns}

Now, (\ref{sol.perm.rig-cyc.1.c.1}) shows that $X\subseteq c_{E}\left(
X\right)  $. In other words, the map $c_{E}$ is surjective. Thus, $c_{E}$ is a
surjective map between two finite sets of the same size (namely, $X$ and $X$),
and therefore must be bijective (since any surjective map between two finite
sets of the same size is bijective). In other words, $c_{E}$ is a bijection
$X\rightarrow X$, therefore a permutation of $X$. This solves Exercise
\ref{exe.perm.rig-cyc.1} \textbf{(c)}.

\textbf{(d)} Let $x\in X$ be such that $E=\left[  x\right]  _{\sim}$. Let
$k=\left\vert \left[  x\right]  _{\sim}\right\vert $. We must prove that
$c_{E}$ can be written as $\operatorname*{cyc}\nolimits_{\sigma^{0}\left(
x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)
}$ (and in particular, we must prove that $\sigma^{0}\left(  x\right)
,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)  $ are
distinct, so that $\operatorname*{cyc}\nolimits_{\sigma^{0}\left(  x\right)
,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)  }$ is well-defined).

Lemma \ref{lem.perm.rig-cyc.2} \textbf{(a)} shows that there exists a
$j\in\mathbb{N}$ such that \newline$\sigma^{j}\left(  x\right)  \in\left\{
\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma
^{j-1}\left(  x\right)  \right\}  $. Let $p$ be the smallest such $j$. As in
the solution to Exercise \ref{exe.perm.rig-cyc.1} \textbf{(b)} (which we have
given above), we can see that $k=p$.

Lemma \ref{lem.perm.rig-cyc.2} \textbf{(b)} shows that the integer $p$ is
positive and satisfies $\sigma^{p}\left(  x\right)  =x$. In view of $k=p$,
this rewrites as follows: The integer $k$ is positive and satisfies
$\sigma^{k}\left(  x\right)  =x$. Since the integer $k$ is positive, we have
$1\in\left[  k\right]  $.

Lemma \ref{lem.perm.rig-cyc.2} \textbf{(c)} shows that the elements
$\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma
^{p-1}\left(  x\right)  $ are pairwise distinct. In view of $k=p$, this
rewrites as follows: The elements $\sigma^{0}\left(  x\right)  ,\sigma
^{1}\left(  x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)  $ are pairwise
distinct. Hence, the permutation $\operatorname*{cyc}\nolimits_{\sigma
^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{k-1}\left(
x\right)  }$ is well-defined (since $k$ is a positive integer).

Exercise \ref{exe.perm.rig-cyc.1} \textbf{(b)} shows that $\left[  x\right]
_{\sim}=\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{k-1}\left(  x\right)  \right\}  $. Hence,%
\begin{equation}
\left\{  \sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{k-1}\left(  x\right)  \right\}  =\left[  x\right]  _{\sim}=E
\label{sol.perm.rig-cyc.1.d.=E}%
\end{equation}
(since $E=\left[  x\right]  _{\sim}$).

It remains to prove that $c_{E}$ can be written as $\operatorname*{cyc}%
\nolimits_{\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)
,\ldots,\sigma^{k-1}\left(  x\right)  }$.

We define a $k$-tuple $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ of elements
of $X$ by
\begin{equation}
\left(  i_{1},i_{2},\ldots,i_{k}\right)  =\left(  \sigma^{0}\left(  x\right)
,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)  \right)  .
\label{sol.perm.rig-cyc.1.d.is=}%
\end{equation}
Thus,%
\begin{equation}
i_{u}=\sigma^{u-1}\left(  x\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }%
u\in\left[  k\right]  . \label{sol.perm.rig-cyc.1.d.iu=}%
\end{equation}
Applying this to $u=1$, we obtain $i_{1}=\sigma^{1-1}\left(  x\right)  $
(since $1\in\left[  k\right]  $).

Also, from (\ref{sol.perm.rig-cyc.1.d.is=}), we obtain%
\begin{equation}
\left\{  i_{1},i_{2},\ldots,i_{k}\right\}  =\left\{  \sigma^{0}\left(
x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)
\right\}  =E \label{sol.perm.rig-cyc.1.d.=E2}%
\end{equation}
(by (\ref{sol.perm.rig-cyc.1.d.=E})).

We also let $i_{k+1}$ stand for $i_{1}$. Thus, $i_{k+1}=i_{1}%
=\underbrace{\sigma^{1-1}}_{=\sigma^{0}=\operatorname*{id}}\left(  x\right)
=\operatorname*{id}\left(  x\right)  =x=\sigma^{k}\left(  x\right)  $ (since
$\sigma^{k}\left(  x\right)  =x$). Therefore, we see that%
\begin{equation}
i_{u}=\sigma^{u-1}\left(  x\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }%
u\in\left[  k+1\right]  . \label{sol.perm.rig-cyc.1.d.iu=2}%
\end{equation}


\begin{fns}
[\textit{Proof of (\ref{sol.perm.rig-cyc.1.d.iu=2}):} Let $u\in\left[
k+1\right]  $. We must prove that $i_{u}=\sigma^{u-1}\left(  x\right)  $. If
$u\in\left[  k\right]  $, then this follows from
(\ref{sol.perm.rig-cyc.1.d.iu=}). Hence, for the rest of this proof, we WLOG
assume that $u\notin\left[  k\right]  $. Combining $u\in\left[  k+1\right]  $
with $u\notin\left[  k\right]  $, we obtain $u\in\left[  k+1\right]
\setminus\left[  k\right]  =\left\{  k+1\right\}  $, so that $u=k+1$. Thus,
$i_{u}=i_{k+1}=\sigma^{k}\left(  x\right)  =\sigma^{u-1}\left(  x\right)  $
(since $k=u-1$ (since $u=k+1$)). This proves (\ref{sol.perm.rig-cyc.1.d.iu=2}).]
\end{fns}

We have $\operatorname*{cyc}\nolimits_{\sigma^{0}\left(  x\right)  ,\sigma
^{1}\left(  x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)  }%
=\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}$ (since $\left(
\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma
^{k-1}\left(  x\right)  \right)  =\left(  i_{1},i_{2},\ldots,i_{k}\right)  $).
But the definition of $\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}%
}$ yields%
\begin{equation}
\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}\left(  p\right)  =%
\begin{cases}
i_{j+1}, & \text{if }p=i_{j}\text{ for some }j\in\left\{  1,2,\ldots
,k\right\}  ;\\
p, & \text{otherwise}%
\end{cases}
\label{sol.perm.rig-cyc.1.d.cyc}%
\end{equation}
for every $p\in X$.

Now, we claim that%
\begin{equation}
\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}\left(  p\right)
=c_{E}\left(  p\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }p\in X.
\label{sol.perm.rig-cyc.1.d.goal}%
\end{equation}


\begin{fns}
[\textit{Proof of (\ref{sol.perm.rig-cyc.1.d.goal}):} Let $p\in X$. We must
prove the equality (\ref{sol.perm.rig-cyc.1.d.goal}).

We are in one of the following two cases:

\textit{Case 1:} We have $p=i_{j}$ for some $j\in\left\{  1,2,\ldots
,k\right\}  $.

\textit{Case 2:} We don't have $\left(  p=i_{j}\text{ for some }j\in\left\{
1,2,\ldots,k\right\}  \right)  $.

Let us first consider Case 1. In this case, we have $p=i_{j}$ for some
$j\in\left\{  1,2,\ldots,k\right\}  $. Consider this $j$. Thus,
(\ref{sol.perm.rig-cyc.1.d.cyc}) simplifies to $\operatorname*{cyc}%
\nolimits_{i_{1},i_{2},\ldots,i_{k}}\left(  p\right)  =i_{j+1}$.

We have $j\in\left\{  1,2,\ldots,k\right\}  =\left[  k\right]  $. Hence,
(\ref{sol.perm.rig-cyc.1.d.iu=}) (applied to $u=j$) yields $i_{j}=\sigma
^{j-1}\left(  x\right)  $. Hence, $\sigma^{j-1}\left(  x\right)  =i_{j}=p$.

But $j\in\left\{  1,2,\ldots,k\right\}  $, so that $j+1\in\left\{
2,3,\ldots,k+1\right\}  \subseteq\left[  k+1\right]  $. Hence,
(\ref{sol.perm.rig-cyc.1.d.iu=2}) (applied to $u=j+1$) yields
\begin{equation}
i_{j+1}=\underbrace{\sigma^{\left(  j+1\right)  -1}}_{=\sigma^{j}}\left(
x\right)  =\sigma^{j}\left(  x\right)  =\sigma\left(  \underbrace{\sigma
^{j-1}\left(  x\right)  }_{=p}\right)  =\sigma\left(  p\right)  .
\label{sol.perm.rig-cyc.1.d.goal.pf.1}%
\end{equation}


However,
\begin{align*}
p  &  =i_{j}\in\left\{  i_{1},i_{2},\ldots,i_{k}\right\}
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }j\in\left\{  1,2,\ldots,k\right\}
\right) \\
&  =E\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.perm.rig-cyc.1.d.=E2}%
)}\right)  .
\end{align*}
The definition of $c_{E}$ now shows that%
\begin{align*}
c_{E}\left(  p\right)   &  =%
\begin{cases}
\sigma\left(  p\right)  , & \text{if }p\in E;\\
p, & \text{if }p\notin E
\end{cases}
=\sigma\left(  p\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }p\in
E\right) \\
&  =i_{j+1}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.perm.rig-cyc.1.d.goal.pf.1})}\right)  .
\end{align*}
Comparing this with $\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}%
}\left(  p\right)  =i_{j+1}$, we obtain $\operatorname*{cyc}\nolimits_{i_{1}%
,i_{2},\ldots,i_{k}}\left(  p\right)  =c_{E}\left(  p\right)  $. Thus,
(\ref{sol.perm.rig-cyc.1.d.goal}) is proven in Case 1.

Let us now consider Case 2. In this case, we don't have $\left(  p=i_{j}\text{
for some }j\in\left\{  1,2,\ldots,k\right\}  \right)  $. Thus,
(\ref{sol.perm.rig-cyc.1.d.cyc}) simplifies to $\operatorname*{cyc}%
\nolimits_{i_{1},i_{2},\ldots,i_{k}}\left(  p\right)  =p$.

But we don't have $\left(  p=i_{j}\text{ for some }j\in\left\{  1,2,\ldots
,k\right\}  \right)  $. In other words, $p\notin\left\{  i_{1},i_{2}%
,\ldots,i_{k}\right\}  $. In view of (\ref{sol.perm.rig-cyc.1.d.=E2}), this
rewrites as $p\notin E$. The definition of $c_{E}$ now shows that%
\[
c_{E}\left(  p\right)  =%
\begin{cases}
\sigma\left(  p\right)  , & \text{if }p\in E;\\
p, & \text{if }p\notin E
\end{cases}
=p\ \ \ \ \ \ \ \ \ \ \left(  \text{since }p\notin E\right)  .
\]
Comparing this with $\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}%
}\left(  p\right)  =p$, we obtain $\operatorname*{cyc}\nolimits_{i_{1}%
,i_{2},\ldots,i_{k}}\left(  p\right)  =c_{E}\left(  p\right)  $. Thus,
(\ref{sol.perm.rig-cyc.1.d.goal}) is proven in Case 2.

We have now proven (\ref{sol.perm.rig-cyc.1.d.goal}) in each of the two Cases
1 and 2. This completes the proof of (\ref{sol.perm.rig-cyc.1.d.goal}).]
\end{fns}

The equality (\ref{sol.perm.rig-cyc.1.d.goal}) shows that $\operatorname*{cyc}%
\nolimits_{i_{1},i_{2},\ldots,i_{k}}=c_{E}$ (since both $\operatorname*{cyc}%
\nolimits_{i_{1},i_{2},\ldots,i_{k}}$ and $c_{E}$ are maps $X\rightarrow X$).
Thus,%
\[
c_{E}=\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}%
=\operatorname*{cyc}\nolimits_{\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(
x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)  }%
\]
(by (\ref{sol.perm.rig-cyc.1.d.is=})). In other words, $c_{E}$ can be written
as $\operatorname*{cyc}\nolimits_{\sigma^{0}\left(  x\right)  ,\sigma
^{1}\left(  x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)  }$. This concludes
the solution to Exercise \ref{exe.perm.rig-cyc.1} \textbf{(d)}.

\textbf{(e)} Recall that the $\sim$-equivalence classes form a set partition
of the set $X$ (in fact, this holds for the equivalence classes of any
equivalence relation on $X$). Thus, each element of $X$ belongs to exactly one
$\sim$-equivalence class. Since $E_{1},E_{2},\ldots,E_{m}$ are all the $\sim
$-equivalence classes (listed without repetition), we can rewrite this fact as
follows: Each element of $X$ belongs to exactly one of the sets $E_{1}%
,E_{2},\ldots,E_{m}$. Thus, the sets $E_{1},E_{2},\ldots,E_{m}$ are disjoint.
In other words, if $i$ and $j$ are two distinct elements of $\left[  m\right]
$, then%
\begin{equation}
E_{i}\cap E_{j}=\varnothing. \label{sol.perm.rig-cyc.1.e.dj}%
\end{equation}


Now, fix $x\in X$. Define $y\in X$ by $y=\sigma\left(  x\right)  $. We are
going to show that $\left(  c_{E_{1}}\circ c_{E_{2}}\circ\cdots\circ c_{E_{m}%
}\right)  \left(  x\right)  =y$.

The element $x$ of $X$ belongs to exactly one of the sets $E_{1},E_{2}%
,\ldots,E_{m}$ (since each element of $X$ belongs to exactly one of the sets
$E_{1},E_{2},\ldots,E_{m}$). In other words, there is exactly one $i\in\left[
m\right]  $ such that $x\in E_{i}$. Consider this $i$.

Hence, $i$ is the \textbf{only} element $j\in\left[  m\right]  $ such that
$x\in E_{j}$. Therefore, every $j\in\left[  m\right]  $ distinct from $i$ must
satisfy%
\begin{equation}
x\notin E_{j}. \label{sol.perm.rig-cyc.1.e.xnotinEj}%
\end{equation}


We have $x\sim y$\ \ \ \ \footnote{\textit{Proof.} We have
$y=\underbrace{\sigma}_{=\sigma^{1}}\left(  x\right)  =\sigma^{1}\left(
x\right)  $. Thus, there exists some $k\in\mathbb{N}$ such that $y=\sigma
^{k}\left(  x\right)  $ (namely, $k=1$). In other words, $x\sim y$ (since
$x\sim y$ if and only if there exists some $k\in\mathbb{N}$ such that
$y=\sigma^{k}\left(  x\right)  $).}. Thus, $y\in\left[  x\right]  _{\sim}$.
But recall that $E_{i}$ is a $\sim$-equivalence class (since $E_{1}%
,E_{2},\ldots,E_{m}$ are all the $\sim$-equivalence classes) and contains $x$
(since $x\in E_{i}$). Hence, $E_{i}$ is the $\sim$-equivalence class of $x$.
In other words, $E_{i}=\left[  x\right]  _{\sim}$. Hence, $y\in\left[
x\right]  _{\sim}=E_{i}$. Hence, every $j\in\left[  m\right]  $ distinct from
$i$ must satisfy%
\begin{equation}
y\notin E_{j} \label{sol.perm.rig-cyc.1.e.ynotinEj}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.perm.rig-cyc.1.e.ynotinEj}):} Fix
$j\in\left[  m\right]  $ distinct from $i$. We must show that $y\notin E_{j}$.
\par
Assume the contrary. Thus, $y\in E_{j}$. Combining this with $y\in E_{i}$, we
find $y\in E_{i}\cap E_{j}$. Therefore, the set $E_{i}\cap E_{j}$ is nonempty
(namely, it contains $y$). But $j$ is distinct from $i$. Hence,
(\ref{sol.perm.rig-cyc.1.e.dj}) yields $E_{i}\cap E_{j}=\varnothing$. This
contradicts the fact that the set $E_{i}\cap E_{j}$ is nonempty. This
contradiction shows that our assumption was false, qed.}.

We have $\sigma_{E_{i}}\left(  x\right)  =y$\ \ \ \ \footnote{\textit{Proof.}
The definition of $\sigma_{E_{i}}$ yields%
\begin{align*}
\sigma_{E_{i}}\left(  x\right)   &  =%
\begin{cases}
\sigma\left(  x\right)  , & \text{if }x\in E_{i};\\
x, & \text{if }x\notin E_{i}%
\end{cases}
=\sigma\left(  x\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }x\in
E_{i}\right) \\
&  =y.
\end{align*}
}. Furthermore, $\sigma_{E_{j}}\left(  x\right)  =x$ for each $j\in\left[
m\right]  $ satisfying $j>i$\ \ \ \ \footnote{\textit{Proof.} Let $j\in\left[
m\right]  $ be such that $j>i$. Thus, $j$ is distinct from $i$ (since $j>i$).
Hence, (\ref{sol.perm.rig-cyc.1.e.xnotinEj}) shows that $x\notin E_{j}$. Now,
the definition of $\sigma_{E_{j}}$ yields%
\[
\sigma_{E_{j}}\left(  x\right)  =%
\begin{cases}
\sigma\left(  x\right)  , & \text{if }x\in E_{j};\\
x, & \text{if }x\notin E_{j}%
\end{cases}
=x\ \ \ \ \ \ \ \ \ \ \left(  \text{since }x\notin E_{j}\right)  .
\]
Qed.}. Also, $\sigma_{E_{j}}\left(  y\right)  =y$ for each $j\in\left[
m\right]  $ satisfying $j<i$\ \ \ \ \footnote{\textit{Proof.} Let $j\in\left[
m\right]  $ be such that $j<i$. Thus, $j$ is distinct from $i$ (since $j<i$).
Hence, (\ref{sol.perm.rig-cyc.1.e.ynotinEj}) shows that $y\notin E_{j}$. Now,
the definition of $\sigma_{E_{j}}$ yields%
\[
\sigma_{E_{j}}\left(  y\right)  =%
\begin{cases}
\sigma\left(  y\right)  , & \text{if }y\in E_{j};\\
y, & \text{if }y\notin E_{j}%
\end{cases}
=y\ \ \ \ \ \ \ \ \ \ \left(  \text{since }y\notin E_{j}\right)  .
\]
Qed.}. Therefore, Lemma \ref{lem.compose-disjoint-maps2} (applied to
$g_{j}=\sigma_{E_{j}}$) shows that $\left(  c_{E_{1}}\circ c_{E_{2}}%
\circ\cdots\circ c_{E_{m}}\right)  \left(  x\right)  =y=\sigma\left(
x\right)  $.

Now, forget that we fixed $x$. We thus have shown that $\left(  c_{E_{1}}\circ
c_{E_{2}}\circ\cdots\circ c_{E_{m}}\right)  \left(  x\right)  =\sigma\left(
x\right)  $ for each $x\in X$. In other words, $c_{E_{1}}\circ c_{E_{2}}%
\circ\cdots\circ c_{E_{m}}=\sigma$. This solves Exercise
\ref{exe.perm.rig-cyc.1} \textbf{(e)}.

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[BleLau92]{BleLau92}D. Blessenohl and H. Laue, \textit{Algebraic
combinatorics related to the free Lie algebra}, S\'{e}minaire Lotharingien de
Combinatoire \textbf{29}, page B29e (1992).\newline\url{https://eudml.org/doc/121542}

\bibitem[Comtet74]{Comtet74}Louis Comtet, \textit{Advanced Combinatorics: The
Art of Finite and Infinite Expansions}, D. Reidel Publishing Company, 1974.

\bibitem[DanRot78]{DanRot78}%
\href{https://doi.org/10.1016/0097-3165(78)90069-9}{Ottavio D'Antona,
Gian-Carlo Rota, \textit{Two Rings Connected with the Inclusion-Exclusion
Principle}, Journal of Combinatorial Theory, Series A, Volume 24, Issue 3, May
1978, pp. 395--402.}

\bibitem[Galvin17]{Galvin}David Galvin, \textit{Basic discrete mathematics},
13 December 2017.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/60610lectures2017-Galvin.pdf}

\bibitem[Grinbe16]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 10 January 2019.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} .

\bibitem[GriRei18]{GriRei17}Darij Grinberg, Victor Reiner, \textit{Hopf
algebras in Combinatorics}, version of 11 May 2018,
\href{http://www.arxiv.org/abs/1409.8356v5}{\texttt{arXiv:1409.8356v5}}.
\newline See also
\url{http://www.cip.ifi.lmu.de/~grinberg/algebra/HopfComb-sols.pdf} for a
version that gets updated.
\end{thebibliography}
\end{proof}


\end{document}