\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{tikz}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Wednesday, October 10, 2018 20:19:22}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\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}}
\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]}
\ihead{Math 4990 Fall 2017 (Darij Grinberg): homework set 8}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

%

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


\bigskip

I am giving just hints or brief outlines of the solutions below;
unfortunately, this is all I have the time for. I hope they are reasonably
clear. Please let me know ( \url{mailto:dgrinber@umn.edu} ) if you are stuck
in some of the details.

\subsection{Strange integers}

\begin{exercise}
\label{exe.supercat}For any $m\in\mathbb{N}$ and $n\in\mathbb{N}$, define a
rational number $T\left(  m,n\right)  $ by%
\[
T\left(  m,n\right)  =\dfrac{\left(  2m\right)  !\left(  2n\right)
!}{m!n!\left(  m+n\right)  !}.
\]


\textbf{(a)} Prove that $4T\left(  m,n\right)  =T\left(  m+1,n\right)
+T\left(  m,n+1\right)  $ for every $m\in\mathbb{N}$ and $n\in\mathbb{N}$.

\textbf{(b)} Prove that $T\left(  m,n\right)  \in\mathbb{N}$ for every
$m\in\mathbb{N}$ and $n\in\mathbb{N}$.

\textbf{(c)} Prove that $T\left(  m,n\right)  $ is an \textbf{even} integer
for every $m\in\mathbb{N}$ and $n\in\mathbb{N}$ unless $\left(  m,n\right)
=\left(  0,0\right)  $.

\textbf{(d)} If $m\in\mathbb{N}$ and $n\in\mathbb{N}$ are such that $m+n$ is
odd and $m+n>1$, then prove that $4\mid T\left(  m,n\right)  $.
\end{exercise}

The numbers $T\left(  m,n\right)  $ introduced in Exercise \ref{exe.supercat}
are the so-called \textit{super-Catalan numbers}; they are a subject of active
research (see, e.g., \cite{Gessel92} and \cite{AleGhe14}). Exercise
\ref{exe.supercat} \textbf{(b)} suggests that these numbers count something,
but no one has so far discovered what; combinatorial proofs aren't always the
easiest to find. The thread
\url{https://artofproblemsolving.com/community/c6h1553916s1_supercatalan_numbers}
on Art of Problem Solving also discusses the super-Catalan numbers and
Exercise \ref{exe.supercat}.

A detailed solution of Exercise \ref{exe.supercat} can be found in
\cite[solution to Exercise 3.25]{detnotes}. We will be rather brief here.

To solve Exercise \ref{exe.supercat}, we need the following lemma (which is
\cite[Exercise 3.24]{detnotes}):

\begin{lemma}
\label{lem.2g-choose-g.even}Let $m$ be a positive integer.

\textbf{(a)} The binomial coefficient $\dbinom{2m}{m}$ is even.

\textbf{(b)} Assume that $m$ is odd and satisfies $m>1$. Then, the binomial
coefficient $\dbinom{2m-1}{m-1}$ is even.

\textbf{(c)} Assume that $m$ is odd and satisfies $m>1$. Then, $\dbinom{2m}{m}
\equiv0 \mod 4$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.2g-choose-g.even} (sketched).]\textbf{(a)} This
follows from $\dbinom{2m}{m}=2\dbinom{2m-1}{m-1}$.

\textbf{(b)} Lemma \ref{lem.2g-choose-g.even} \textbf{(a)} (applied to $m-1$
instead of $m$) shows that $\dbinom{2\left(  m-1\right)  }{m-1}$ is even. In
other words, $\dbinom{2\left(  m-1\right)  }{m-1}\equiv0\operatorname{mod}2$.
But $m$ is odd; thus, $m\equiv1\operatorname{mod}2$. Now,%
\[
m\dbinom{2m-1}{m-1}=\left(  2m-1\right)  \underbrace{\dbinom{2\left(
m-1\right)  }{m-1}}_{\equiv0\operatorname{mod}2}\equiv0\operatorname{mod}2,
\]
so that $0\equiv\underbrace{m}_{\equiv1\operatorname{mod}2}\dbinom{2m-1}%
{m-1}\equiv\dbinom{2m-1}{m-1}\operatorname{mod}2$. In other words,
$\dbinom{2m-1}{m-1}$ is even. This proves Lemma \ref{lem.2g-choose-g.even}
\textbf{(b)}.

\textbf{(c)} We have $\dbinom{2m}{m}=2\dbinom{2m-1}{m-1}\equiv
0\operatorname{mod}4$ (since Lemma \ref{lem.2g-choose-g.even} \textbf{(b)}
shows that $\dbinom{2m-1}{m-1}$ is even). This proves Lemma
\ref{lem.2g-choose-g.even} \textbf{(c)}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.supercat} (sketched).]\textbf{(a)} This is a
straightforward computation: For $m\in\mathbb{N}$ and $n\in\mathbb{N}$, we
have%
\begin{align*}
T\left(  m+1,n\right)   &  =\dfrac{\left(  2\left(  m+1\right)  \right)
!\left(  2n\right)  !}{\left(  m+1\right)  !n!\left(  m+1+n\right)  !}%
=\dfrac{\left(  2m+2\right)  \left(  2m+1\right)  \cdot\left(  2m\right)
!\left(  2n\right)  !}{\left(  m+1\right)  \cdot m!n!\cdot\left(
m+1+n\right)  \cdot\left(  m+n\right)  !}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since }\left(  2\left(  m+1\right)  \right)  !=\left(  2m+2\right)
\left(  2m+1\right)  \cdot\left(  2m\right)  !\text{ and}\\
\left(  m+1\right)  !=\left(  m+1\right)  \cdot m!\text{ and }\left(
m+1+n\right)  !=\left(  m+1+n\right)  \cdot\left(  m+n\right)  !
\end{array}
\right) \\
&  =\underbrace{\dfrac{\left(  2m+2\right)  \left(  2m+1\right)  }{\left(
m+1\right)  \left(  m+1+n\right)  }}_{=\dfrac{4m+2}{m+1+n}}\cdot
\underbrace{\dfrac{\left(  2m\right)  !\left(  2n\right)  !}{m!n!\left(
m+n\right)  !}}_{=T\left(  m,n\right)  }=\dfrac{4m+2}{m+1+n}\cdot T\left(
m,n\right)
\end{align*}
and similarly%
\[
T\left(  m,n+1\right)  =\dfrac{4n+2}{m+1+n}\cdot T\left(  m,n\right)  .
\]
Add these two equalities and simplify.

\textbf{(b)} Apply induction on $n$:

\textit{Induction base:} For each $m\in\mathbb{N}$, we have%
\[
T\left(  m,0\right)  =\dfrac{\left(  2m\right)  !\left(  2\cdot0\right)
!}{m!0!\left(  m+0\right)  !}=\dfrac{\left(  2m\right)  !}{m!m!}=\dbinom
{2m}{m}\in\mathbb{N}.
\]
In other words, Exercise \ref{exe.supercat} \textbf{(b)} holds for $n=0$.

\textit{Induction step:} Let $N\in\mathbb{N}$. Assume (as the induction
hypothesis) that Exercise \ref{exe.supercat} \textbf{(b)} holds for $n=N$. We
must prove that Exercise \ref{exe.supercat} \textbf{(b)} holds for $n=N+1$.

For each $m\in\mathbb{N}$, we have%
\begin{align*}
T\left(  m,N+1\right)   &  =4\underbrace{T\left(  m,N\right)  }_{\substack{\in
\mathbb{N}\\\text{(by the induction}\\\text{hypothesis)}}%
}-\underbrace{T\left(  m+1,N\right)  }_{\substack{\in\mathbb{N}\\\text{(by the
induction}\\\text{hypothesis)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since Exercise \ref{exe.supercat}
\textbf{(a)} yields }4T\left(  m,N\right)  =T\left(  m+1,N\right)  +T\left(
m,N+1\right)  \right) \\
&  \in\mathbb{Z}%
\end{align*}
and therefore $T\left(  m,N+1\right)  \in\mathbb{N}$ (since the definition of
$T\left(  m,N+1\right)  $ shows that $T\left(  m,N+1\right)  $ is positive).
In other words, Exercise \ref{exe.supercat} \textbf{(b)} holds for $n=N+1$.
This completes the induction step. Hence, Exercise \ref{exe.supercat}
\textbf{(b)} is proven.

\textbf{(c)} Apply induction on $n$:

\textit{Induction base:} For each positive integer $m$, we have%
\[
T\left(  m,0\right)  =\dfrac{\left(  2m\right)  !\left(  2\cdot0\right)
!}{m!0!\left(  m+0\right)  !}=\dfrac{\left(  2m\right)  !}{m!m!}=\dbinom
{2m}{m},
\]
and this is even (by Lemma \ref{lem.2g-choose-g.even} \textbf{(a)}). In other
words, for each positive integer $m$, the number $T\left(  m,0\right)  $ is an
even integer. In other words, Exercise \ref{exe.supercat} \textbf{(c)} holds
for $n=0$ (because if $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfy $\left(
m,n\right)  \neq\left(  0,0\right)  $ but $n=0$, then $m$ must be a positive integer).

\textit{Induction step:} Let $N\in\mathbb{N}$. Assume (as the induction
hypothesis) that Exercise \ref{exe.supercat} \textbf{(c)} holds for $n=N$. We
must prove that Exercise \ref{exe.supercat} \textbf{(c)} holds for $n=N+1$.

Let $m\in\mathbb{N}$. Exercise \ref{exe.supercat} \textbf{(b)} shows that
$T\left(  m,N\right)  $ is an integer. Thus, $4T\left(  m,N\right)
\equiv0\operatorname{mod}2$. Also, $\left(  m+1,N\right)  \neq\left(
0,0\right)  $ (since $m+1$ is positive). Thus, the induction hypothesis yields
that $T\left(  m+1,N\right)  $ is an even integer. Hence, $T\left(
m+1,N\right)  \equiv0\operatorname{mod}2$.

Now, Exercise \ref{exe.supercat} \textbf{(a)} yields $4T\left(  m,N\right)
=T\left(  m+1,N\right)  +T\left(  m,N+1\right)  $. Thus,%
\[
T\left(  m,N+1\right)  =\underbrace{4T\left(  m,N\right)  }_{\equiv
0\operatorname{mod}2}-\underbrace{T\left(  m+1,N\right)  }_{\substack{\equiv
0\operatorname{mod}2}}\equiv0\operatorname{mod}2.
\]
In other words, $T\left(  m,N+1\right)  $ is even. In other words, Exercise
\ref{exe.supercat} \textbf{(c)} holds for $n=N+1$. This completes the
induction step. Hence, Exercise \ref{exe.supercat} \textbf{(c)} is proven.

\textbf{(d)} Apply induction on $n$:

\textit{Induction base:} We must prove Exercise \ref{exe.supercat}
\textbf{(d)} for $n=0$. In other words, we must show that if $m\in\mathbb{N}$
is such that $m+0$ is odd and $m+0>1$, then $4\mid T\left(  m,0\right)  $.

Let $m\in\mathbb{N}$ be such that $m+0$ is odd and $m+0>1$. From $m=m+0>1$, we
conclude that $m$ is a positive integer. Also, $m=m+0$ is odd. Now,
\[
T\left(  m,0\right)  =\dfrac{\left(  2m\right)  !\left(  2\cdot0\right)
!}{m!0!\left(  m+0\right)  !}=\dfrac{\left(  2m\right)  !}{m!m!}=\dbinom
{2m}{m}\equiv0\operatorname{mod}4
\]
(by Lemma \ref{lem.2g-choose-g.even} \textbf{(b)}). In other words, $4\mid
T\left(  m,0\right)  $. This completes our proof that Exercise
\ref{exe.supercat} \textbf{(d)} holds for $n=0$.

\textit{Induction step:} Let $N\in\mathbb{N}$. Assume (as the induction
hypothesis) that Exercise \ref{exe.supercat} \textbf{(d)} holds for $n=N$. We
must prove that Exercise \ref{exe.supercat} \textbf{(d)} holds for $n=N+1$.

Let $m\in\mathbb{N}$ be such that $m+\left(  N+1\right)  $ is odd and
$m+\left(  N+1\right)  >1$. Then, $\left(  m+1\right)  +N=m+\left(
N+1\right)  $ is odd and $\left(  m+1\right)  +N=m+\left(  N+1\right)  >1$.
Thus, the induction hypothesis yields that $4\mid T\left(  m+1,N\right)  $.
Hence, $T\left(  m+1,N\right)  \equiv0\operatorname{mod}4$. Also, Exercise
\ref{exe.supercat} \textbf{(b)} shows that $T\left(  m,N\right)  $ is an
integer. Thus, $4T\left(  m,N\right)  \equiv0\operatorname{mod}4$.

Now, Exercise \ref{exe.supercat} \textbf{(a)} yields $4T\left(  m,N\right)
=T\left(  m+1,N\right)  +T\left(  m,N+1\right)  $. Thus,%
\[
T\left(  m,N+1\right)  =\underbrace{4T\left(  m,N\right)  }_{\equiv
0\operatorname{mod}4}-\underbrace{T\left(  m+1,N\right)  }_{\substack{\equiv
0\operatorname{mod}4}}\equiv0\operatorname{mod}4.
\]
In other words, $4\mid T\left(  m,N+1\right)  $. In other words, Exercise
\ref{exe.supercat} \textbf{(d)} holds for $n=N+1$. This completes the
induction step. Hence, Exercise \ref{exe.supercat} \textbf{(d)} is proven.
\end{proof}

\begin{exercise}
\label{exe.supercat2}Let $m\in\mathbb{N}$ and $n\in\mathbb{N}$. Let
$p=\min\left\{  m,n\right\}  $.

\textbf{(a)} Prove that%
\[
\sum_{k=-p}^{p}\left(  -1\right)  ^{k}\dbinom{m+n}{m+k}\dbinom{m+n}%
{n+k}=\dbinom{m+n}{m}.
\]


\textbf{(b)} Prove that%
\[
T\left(  m,n\right)  =\sum_{k=-p}^{p}\left(  -1\right)  ^{k}\dbinom{2m}%
{m+k}\dbinom{2n}{n-k},
\]
where $T\left(  m,n\right)  $ is defined as in Exercise \ref{exe.supercat}.

[\textbf{Hint:} Part \textbf{(a)} should follow from something done in class.
Then, compare part \textbf{(b)} with part \textbf{(a)}.]
\end{exercise}

Exercise \ref{exe.supercat2} \textbf{(b)} is a result of von Szily (1894); see
\cite[(29)]{Gessel92}. Needless to say, Exercise \ref{exe.supercat2}
\textbf{(b)} provides an alternative solution to Exercise \ref{exe.supercat}
\textbf{(b)}.

A full solution of Exercise \ref{exe.supercat2} can be found in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw8os-chen.pdf}{Angela
Chen's homework} and in \cite[solution to Exercise 3.25]{detnotes} (this is
one and the same solution, written up in slightly different ways).

\subsection{The length of a permutation}

\begin{definition}
Let $n\in\mathbb{N}$.

\textbf{(a)} We let $S_{n}$ denote the set of all permutations of $\left[
n\right]  $.

Let $\sigma\in S_{n}$ be a permutation of $\left[  n\right]  $.

\textbf{(b)} An \textit{inversion} of $\sigma$ means a pair $\left(
i,j\right)  $ of elements of $\left[  n\right]  $ satisfying $i<j$ and
$\sigma\left(  i\right)  >\sigma\left(  j\right)  $.

\textbf{(c)} The \textit{length} of $\sigma$ is defined to be the number of
inversions of $\sigma$. This length is denoted by $\ell\left(  \sigma\right)
$.

\textbf{(d)} The \textit{sign} of $\sigma$ is defined to be the integer
$\left(  -1\right)  ^{\ell\left(  \sigma\right)  }$. It is denoted by $\left(
-1\right)  ^{\sigma}$.
\end{definition}

\begin{exercise}
\label{exe.sign-matrix}Let $p\in\mathbb{N}$ and $q\in\mathbb{N}$. Let $n=pq$.
Consider the permutation $\sigma\in S_{n}$ that maps $\left(  i-1\right)  q+j$
to $\left(  j-1\right)  p+i$ for every $i\in\left[  p\right]  $ and
$j\in\left[  q\right]  $.

(This permutation $\sigma$ can be visualized as follows: Fill in a $p\times
q$-matrix $A$ with the entries $1,2,\ldots,n$ by going row by row from top to
bottom:%
\[
A=\left(
\begin{array}
[c]{ccccc}%
1 & 2 & 3 & \cdots & q\\
q+1 & q+2 & q+3 & \cdots & 2q\\
2q+1 & 2q+2 & 2q+3 & \cdots & 3q\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
\left(  p-1\right)  q+1 & \left(  p-1\right)  q+2 & \left(  p-1\right)  q+3 &
\cdots & pq
\end{array}
\right)  .
\]
Fill in a $p\times q$-matrix $B$ with the entries $1,2,\ldots,n$ by going
column by column from left to right:%
\[
B=\left(
\begin{array}
[c]{ccccc}%
1 & p+1 & 2p+1 & \cdots & \left(  q-1\right)  p+1\\
2 & p+2 & 2p+2 & \cdots & \left(  q-1\right)  p+2\\
3 & p+3 & 2p+3 & \cdots & \left(  q-1\right)  p+3\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
p & 2p & 3p & \cdots & qp
\end{array}
\right)  .
\]
The permutation $\sigma$ then sends each entry of $A$ to the corresponding
entry of $B$.)

Find the length $\ell\left(  \sigma\right)  $ of the permutation $\sigma$.
\end{exercise}

A full solution of Exercise \ref{exe.sign-matrix} can be found in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw8os-chen.pdf}{Angela
Chen's homework}. (This is also the solution I had in mind.) We shall later
sketch the solution after Definition \ref{def.perm.lehmer.li} (which somewhat
simplifies it).

\subsection{Two equal counts}

\begin{exercise}
\label{exe.dumont-in-han-denert}Let $n\in\mathbb{N}$ and $\sigma\in S_{n}$.
Prove that%
\begin{align*}
&  \left(  \text{the number of all }\left(  i,j\right)  \in\left[  n\right]
\times\left[  n\right]  \text{ such that }i\geq j>\sigma\left(  i\right)
\right) \\
&  =\left(  \text{the number of all }\left(  i,j\right)  \in\left[  n\right]
\times\left[  n\right]  \text{ such that }\sigma\left(  i\right)  \geq
j>i\right)  .
\end{align*}

\end{exercise}

Exercise \ref{exe.dumont-in-han-denert} is a consequence of the following fact:

\begin{lemma}
\label{lem.dumont}Let $n\in\mathbb{N}$. Let $\sigma\in S_{n}$ and $j\in\left[
n\right]  $. Then,%
\begin{align}
&  \left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}i\geq j>\sigma\left(  i\right)  \right) \nonumber\\
&  =\left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}\sigma\left(  i\right)  \geq j>i\right)  . \label{eq.lem.dumont.eq}%
\end{align}

\end{lemma}

Indeed, if we sum up the equality (\ref{eq.lem.dumont.eq}) over all
$j\in\left[  n\right]  $, then we obtain precisely the claim of Exercise
\ref{exe.dumont-in-han-denert}.

Lemma \ref{lem.dumont} is \cite[Lemme 2.1]{Han92}. Anyway, it is also easy to prove:

\begin{proof}
[First proof of Lemma \ref{lem.dumont} (sketched).]The map $\sigma$ is a
permutation of $\left[  n\right]  $ (since $\sigma\in S_{n}$), thus a
bijection $\left[  n\right]  \rightarrow\left[  n\right]  $.

Use the Iverson bracket notation. Then, any three integers $p$, $q$ and $r$
satisfy%
\begin{align}
\left[  p\geq q>r\right]   &  =\left[  p\geq q\text{ and }q>r\right]  =\left[
p\geq q\right]  \underbrace{\left[  q>r\right]  }_{\substack{=\left[
\text{not }r\geq q\right]  \\=1-\left[  r\geq q\right]  }}=\left[  p\geq
q\right]  \left(  1-\left[  r\geq q\right]  \right) \nonumber\\
&  =\left[  p\geq q\right]  -\left[  p\geq q\right]  \left[  r\geq q\right]  .
\label{pf.lem.dumont.pf1.1}%
\end{align}
But%
\begin{align}
&  \left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}i\geq j>\sigma\left(  i\right)  \right) \nonumber\\
&  =\sum_{i\in\left[  n\right]  }\underbrace{\left[  i\geq j>\sigma\left(
i\right)  \right]  }_{\substack{=\left[  i\geq j\right]  -\left[  i\geq
j\right]  \left[  \sigma\left(  i\right)  \geq j\right]  \\\text{(by
(\ref{pf.lem.dumont.pf1.1}))}}}=\sum_{i\in\left[  n\right]  }\left(  \left[
i\geq j\right]  -\left[  i\geq j\right]  \left[  \sigma\left(  i\right)  \geq
j\right]  \right) \nonumber\\
&  =\sum_{i\in\left[  n\right]  }\left[  i\geq j\right]  -\sum_{i\in\left[
n\right]  }\left[  i\geq j\right]  \left[  \sigma\left(  i\right)  \geq
j\right]  \label{pf.lem.dumont.pf1.2}%
\end{align}
and similarly%
\begin{align*}
&  \left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}\sigma\left(  i\right)  \geq j>i\right) \\
&  =\sum_{i\in\left[  n\right]  }\left[  \sigma\left(  i\right)  \geq
j\right]  -\sum_{i\in\left[  n\right]  }\left[  \sigma\left(  i\right)  \geq
j\right]  \left[  i\geq j\right]  .
\end{align*}
Hence,%
\begin{align*}
&  \left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}\sigma\left(  i\right)  \geq j>i\right) \\
&  =\underbrace{\sum_{i\in\left[  n\right]  }\left[  \sigma\left(  i\right)
\geq j\right]  }_{\substack{=\sum_{i\in\left[  n\right]  }\left[  i\geq
j\right]  \\\text{(here, we have substituted }i\\\text{for }\sigma\left(
i\right)  \text{ in the sum, since}\\\text{the map }\sigma\text{ is a
bijection }\left[  n\right]  \rightarrow\left[  n\right]  \text{)}}%
}-\sum_{i\in\left[  n\right]  }\underbrace{\left[  \sigma\left(  i\right)
\geq j\right]  \left[  i\geq j\right]  }_{=\left[  i\geq j\right]  \left[
\sigma\left(  i\right)  \geq j\right]  }\\
&  =\sum_{i\in\left[  n\right]  }\left[  i\geq j\right]  -\sum_{i\in\left[
n\right]  }\left[  i\geq j\right]  \left[  \sigma\left(  i\right)  \geq
j\right] \\
&  =\left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}i\geq j>\sigma\left(  i\right)  \right)
\end{align*}
(by (\ref{pf.lem.dumont.pf1.2})). This proves Lemma \ref{lem.dumont}.
\end{proof}

\begin{proof}
[Second proof of Lemma \ref{lem.dumont} (sketched).]The map $\sigma$ is a
permutation of $\left[  n\right]  $ (since $\sigma\in S_{n}$), thus a
bijection $\left[  n\right]  \rightarrow\left[  n\right]  $.

We have%
\begin{align*}
&  \left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}\underbrace{i\geq j>\sigma\left(  i\right)  }_{\Longleftrightarrow\ \left(
i\geq j\text{ but \textbf{not} }\sigma\left(  i\right)  \geq j\right)
}\right) \\
&  =\left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}i\geq j\text{ but \textbf{not} }\sigma\left(  i\right)  \geq j\right) \\
&  =\left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}i\geq j\right) \\
&  \ \ \ \ \ \ \ \ \ \ -\left(  \text{the number of all }i\in\left[  n\right]
\text{ such that }i\geq j\text{ and }\sigma\left(  i\right)  \geq j\right)
\end{align*}
and%
\begin{align*}
&  \left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}\underbrace{\sigma\left(  i\right)  \geq j>i}_{\Longleftrightarrow\ \left(
\sigma\left(  i\right)  \geq j\text{ but \textbf{not} }i\geq j\right)
}\right) \\
&  =\left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}\sigma\left(  i\right)  \geq j\text{ but \textbf{not} }i\geq j\right) \\
&  =\underbrace{\left(  \text{the number of all }i\in\left[  n\right]  \text{
such that }\sigma\left(  i\right)  \geq j\right)  }_{\substack{=\left(
\text{the number of all }i\in\left[  n\right]  \text{ such that }i\geq
j\right)  \\\text{(here, we have substituted }i\text{ for }\sigma\left(
i\right)  \text{, since the map }\sigma\text{ is a bijection }\left[
n\right]  \rightarrow\left[  n\right]  \text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ -\left(  \text{the number of all }i\in\left[  n\right]
\text{ such that }\underbrace{\sigma\left(  i\right)  \geq j\text{ and }i\geq
j}_{\Longleftrightarrow\ \left(  i\geq j\text{ and }\sigma\left(  i\right)
\geq j\right)  }\right) \\
&  =\left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}i\geq j\right) \\
&  \ \ \ \ \ \ \ \ \ \ -\left(  \text{the number of all }i\in\left[  n\right]
\text{ such that }i\geq j\text{ and }\sigma\left(  i\right)  \geq j\right)  .
\end{align*}
Comparing these two equalities, we obtain%
\begin{align*}
&  \left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}i\geq j>\sigma\left(  i\right)  \right) \\
&  =\left(  \text{the number of all }i\in\left[  n\right]  \text{ such that
}\sigma\left(  i\right)  \geq j>i\right)  .
\end{align*}
This proves Lemma \ref{lem.dumont} again.
\end{proof}

Note that none of the above proofs of Lemma \ref{lem.dumont} is bijective.
Maja Schryer found a bijective proof:

\begin{proof}
[Third proof of Lemma \ref{lem.dumont} (sketched).]The map%
\begin{align*}
\left\{  i\in\left[  n\right]  \ \mid\ i\geq j>\sigma\left(  i\right)
\right\}   &  \rightarrow\left\{  i\in\left[  n\right]  \ \mid\ \sigma\left(
i\right)  \geq j>i\right\}  ,\\
i  &  \mapsto\left(  \sigma^{k-1}\left(  i\right)  \text{, where }k\text{ is
the smallest positive}\right. \\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{integer satisfying }\sigma^{k}\left(
i\right)  \geq j\right)
\end{align*}
is well-defined (indeed, it is easy to see that a positive integer $k$
satisfying $\sigma^{k}\left(  i\right)  \geq j$ exists for every $i\in\left[
n\right]  $ satisfying $i\geq j$). Similarly, the map%
\begin{align*}
\left\{  i\in\left[  n\right]  \ \mid\ \sigma\left(  i\right)  \geq
j>i\right\}   &  \rightarrow\left\{  i\in\left[  n\right]  \ \mid\ i\geq
j>\sigma\left(  i\right)  \right\}  ,\\
i  &  \mapsto\left(  \left(  \sigma^{-1}\right)  ^{k}\left(  i\right)  \text{,
where }k\text{ is the smallest nonnegative}\right. \\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{integer satisfying }\left(  \sigma
^{-1}\right)  ^{k}\left(  i\right)  \geq j\right)
\end{align*}
is well-defined (notice that we are using $\left(  \sigma^{-1}\right)  ^{k}$
here, not $\left(  \sigma^{-1}\right)  ^{k-1}$). It is easy to check that
these two maps are mutually inverse, and thus bijective. This bijection yields
Lemma \ref{lem.dumont}.
\end{proof}

\subsection{Lehmer codes}

Recall the following definition from the preceding homework set:

\begin{definition}
\label{def.perm.lehmer.li}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}

\begin{exercise}
\label{exe.perm.lehmer2}Let $n\in\mathbb{N}$. Let $G$ be the set of all
$n$-tuples $\left(  j_{1},j_{2},\ldots,j_{n}\right)  $ of integers satisfying
$0\leq j_{k}\leq n-k$ for each $k\in\left[  n\right]  $. (In other words,
$G=\left\{  0,1,\ldots,n-1\right\}  \times\left\{  0,1,\ldots,n-2\right\}
\times\cdots\times\left\{  0,1,\ldots,n-n\right\}  $.)

\textbf{(a)} For any $\sigma\in S_{n}$ and $i\in\left[  n\right]  $, prove
that $\sigma\left(  i\right)  $ is the $\left(  \ell_{i}\left(  \sigma\right)
+1\right)  $-th smallest element of the set $\left[  n\right]  \setminus
\left\{  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots
,\sigma\left(  i-1\right)  \right\}  $.

\textbf{(b)} For any $\sigma\in S_{n}$, prove that
\[
\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(  \sigma\right)
,\ldots,\ell_{n}\left(  \sigma\right)  \right)  \in G.
\]


\textbf{(c)} Prove that the map%
\begin{align*}
S_{n}  &  \rightarrow G,\\
\sigma &  \mapsto\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(
\sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)  \right)
\end{align*}
is bijective.

\textbf{(d)} Show that $\ell\left(  \sigma\right)  =\ell_{1}\left(
\sigma\right)  +\ell_{2}\left(  \sigma\right)  +\cdots+\ell_{n}\left(
\sigma\right)  $ for each $\sigma\in S_{n}$.

\textbf{(e)} Show that%
\[
\sum_{\sigma\in S_{n}}x^{\ell\left(  \sigma\right)  }=\left(  1+x\right)
\left(  1+x+x^{2}\right)  \cdots\left(  1+x+x^{2}+\cdots+x^{n-1}\right)
\]
(an equality between polynomials in $x$). (If $n\leq1$, then the right hand
side of this equality is an empty product, and thus equals $1$.)
\end{exercise}

Note that the $n$-tuple $\left(  \ell_{1}\left(  \sigma\right)  ,\ell
_{2}\left(  \sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)  \right)  $
is known as the \textit{Lehmer code} of the permutation $\sigma$.

Parts \textbf{(b)}, \textbf{(c)}, \textbf{(d)} and \textbf{(e)} of Exercise
\ref{exe.perm.lehmer2} are proven in \cite[\S 5.8 and the solution to Exercise
5.18]{detnotes}. (Specifically, Exercise \ref{exe.perm.lehmer2} \textbf{(b)}
is \cite[Proposition 5.47]{detnotes}; Exercise \ref{exe.perm.lehmer2}
\textbf{(c)} is \cite[Theorem 5.52]{detnotes}; Exercise \ref{exe.perm.lehmer2}
\textbf{(d)} is \cite[Proposition 5.46]{detnotes}; Exercise
\ref{exe.perm.lehmer2} \textbf{(e)} is \cite[Corollary 5.53]{detnotes}). But
let us sketch the simple proofs here as well (they are simple because we have
laid all the groundwork on the previous homework set):

\begin{proof}
[Solution to Exercise \ref{exe.perm.lehmer2} (sketched).]\textbf{(a)} Let
$\sigma\in S_{n}$ and $i\in\left[  n\right]  $. Then, $\sigma$ is a
permutation. Thus, the numbers $\sigma\left(  1\right)  ,\sigma\left(
2\right)  ,\ldots,\sigma\left(  n\right)  $ are distinct. Now,%
\begin{align}
&  \underbrace{\left[  n\right]  }_{\substack{=\left\{  1,2,\ldots,n\right\}
\\=\left\{  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots
,\sigma\left(  n\right)  \right\}  \\\text{(since }\sigma\text{ is a
permutation)}}}\setminus\left\{  \sigma\left(  1\right)  ,\sigma\left(
2\right)  ,\ldots,\sigma\left(  i-1\right)  \right\} \nonumber\\
&  =\left\{  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots
,\sigma\left(  n\right)  \right\}  \setminus\left\{  \sigma\left(  1\right)
,\sigma\left(  2\right)  ,\ldots,\sigma\left(  i-1\right)  \right\}
\nonumber\\
&  =\left\{  \sigma\left(  i\right)  ,\sigma\left(  i+1\right)  ,\ldots
,\sigma\left(  n\right)  \right\}  \label{sol.perm.lehmer2.a.1}%
\end{align}
(since $\sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
n\right)  $ are distinct).

Recall that $\ell_{i}\left(  \sigma\right)  $ denotes the number of
$j\in\left\{  i+1,i+2,\ldots,n\right\}  $ such that $\sigma\left(  i\right)
>\sigma\left(  j\right)  $. In other words, $\ell_{i}\left(  \sigma\right)  $
is the number of $j\in\left\{  i+1,i+2,\ldots,n\right\}  $ such that
$\sigma\left(  j\right)  <\sigma\left(  i\right)  $. In other words, $\ell
_{i}\left(  \sigma\right)  $ is the number of entries of the sequence $\left(
\sigma\left(  i+1\right)  ,\sigma\left(  i+2\right)  ,\ldots,\sigma\left(
n\right)  \right)  $ that are smaller than $\sigma\left(  i\right)  $. Thus,
there are precisely $\ell_{i}\left(  \sigma\right)  $ entries in the sequence
$\left(  \sigma\left(  i+1\right)  ,\sigma\left(  i+2\right)  ,\ldots
,\sigma\left(  n\right)  \right)  $ that are smaller than $\sigma\left(
i\right)  $. If we add an entry $\sigma\left(  i\right)  $ to this sequence,
then this fact does not change (because this new entry $\sigma\left(
i\right)  $ is not smaller than $\sigma\left(  i\right)  $). Thus, there are
precisely $\ell_{i}\left(  \sigma\right)  $ entries in the sequence $\left(
\sigma\left(  i\right)  ,\sigma\left(  i+1\right)  ,\ldots,\sigma\left(
n\right)  \right)  $ that are smaller than $\sigma\left(  i\right)  $. Since
the entries of this sequence are distinct (because $\sigma\left(  1\right)
,\sigma\left(  2\right)  ,\ldots,\sigma\left(  n\right)  $ are distinct), we
can rewrite this as follows: There are precisely $\ell_{i}\left(
\sigma\right)  $ elements of the set $\left\{  \sigma\left(  i\right)
,\sigma\left(  i+1\right)  ,\ldots,\sigma\left(  n\right)  \right\}  $ that
are smaller than $\sigma\left(  i\right)  $. In other words, $\sigma\left(
i\right)  $ is the $\left(  \ell_{i}\left(  \sigma\right)  +1\right)  $-th
smallest element of the set $\left\{  \sigma\left(  i\right)  ,\sigma\left(
i+1\right)  ,\ldots,\sigma\left(  n\right)  \right\}  $. In view of
(\ref{sol.perm.lehmer2.a.1}), this rewrites as follows: $\sigma\left(
i\right)  $ is the $\left(  \ell_{i}\left(  \sigma\right)  +1\right)  $-th
smallest element of the set $\left[  n\right]  \setminus\left\{  \sigma\left(
1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(  i-1\right)  \right\}
$. This solves Exercise \ref{exe.perm.lehmer2} \textbf{(a)}.

\textbf{(b)} Let $\sigma\in S_{n}$. For each $i\in\left\{  1,2,\ldots
,n\right\}  $, we have $\ell_{i}\left(  \sigma\right)  \leq n-i$ (since
$\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)  $, and clearly this number cannot be larger than $\left\vert
\left\{  i+1,i+2,\ldots,n\right\}  \right\vert =n-i$) and thus $\ell
_{i}\left(  \sigma\right)  \in\left\{  0,1,\ldots,n-i\right\}  $. Hence,%
\begin{align*}
\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(  \sigma\right)
,\ldots,\ell_{n}\left(  \sigma\right)  \right)   &  \in\left\{  0,1,\ldots
,n-1\right\}  \times\left\{  0,1,\ldots,n-2\right\}  \times\cdots
\times\left\{  0,1,\ldots,n-n\right\} \\
&  =G.
\end{align*}
This solves Exercise \ref{exe.perm.lehmer2} \textbf{(b)}.

\textbf{(c)} The sets $S_{n}$ and $G$ are finite and have the same size
(namely, $n!$). But the map%
\begin{align*}
S_{n}  &  \rightarrow G,\\
\sigma &  \mapsto\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(
\sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)  \right)
\end{align*}
is injective (by Exercise 5 \textbf{(b)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw7os.pdf}{homework set
\#7}), and therefore bijective (because any injective map between two finite
sets having the same size must be bijective). This solves Exercise
\ref{exe.perm.lehmer2} \textbf{(c)}.

\textbf{(d)} Let $\sigma\in S_{n}$. The definition of $\ell\left(
\sigma\right)  $ yields that%
\begin{align*}
\ell\left(  \sigma\right)   &  =\left(  \text{the number of inversions of
}\sigma\right) \\
&  =\left(  \text{the number of pairs }\left(  i,j\right)  \text{ of elements
of }\left[  n\right]  \text{ satisfying }i<j\text{ and }\sigma\left(
i\right)  >\sigma\left(  j\right)  \right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of an inversion}\right)
\\
&  =\sum_{i\in\left[  n\right]  }\underbrace{\left(  \text{the number of }%
j\in\left[  n\right]  \text{ satisfying }i<j\text{ and }\sigma\left(
i\right)  >\sigma\left(  j\right)  \right)  }_{\substack{=\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)  \\\text{(since the
}j\in\left[  n\right]  \text{ satisfying }i<j\text{ are precisely the }%
j\in\left\{  i+1,i+2,\ldots,n\right\}  \text{)}}}\\
&  =\sum_{i\in\left[  n\right]  }\underbrace{\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)  }_{\substack{=\ell_{i}\left(
\sigma\right)  \\\text{(by the definition of }\ell_{i}\left(  \sigma\right)
\text{)}}}\\
&  =\sum_{i\in\left[  n\right]  }\ell_{i}\left(  \sigma\right)  =\ell
_{1}\left(  \sigma\right)  +\ell_{2}\left(  \sigma\right)  +\cdots+\ell
_{n}\left(  \sigma\right)  .
\end{align*}
This solves Exercise \ref{exe.perm.lehmer2} \textbf{(d)}.

\textbf{(e)} We have%
\begin{align*}
&  \sum_{\sigma\in S_{n}}\underbrace{x^{\ell\left(  \sigma\right)  }%
}_{\substack{=\ell_{1}\left(  \sigma\right)  +\ell_{2}\left(  \sigma\right)
+\cdots+\ell_{n}\left(  \sigma\right)  \\\text{(by Exercise
\ref{exe.perm.lehmer2} \textbf{(d)})}}}\\
&  =\sum_{\sigma\in S_{n}}x^{\ell_{1}\left(  \sigma\right)  +\ell_{2}\left(
\sigma\right)  +\cdots+\ell_{n}\left(  \sigma\right)  }=\underbrace{\sum
_{\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in G}}_{\substack{=\sum_{\left(
i_{1},i_{2},\ldots,i_{n}\right)  \in\left\{  0,1,\ldots,n-1\right\}
\times\left\{  0,1,\ldots,n-2\right\}  \times\cdots\times\left\{
0,1,\ldots,n-n\right\}  }\\\text{(since }G=\left\{  0,1,\ldots,n-1\right\}
\times\left\{  0,1,\ldots,n-2\right\}  \times\cdots\times\left\{
0,1,\ldots,n-n\right\}  \text{)}}}\underbrace{x^{i_{1}+i_{2}+\cdots+i_{n}}%
}_{=x^{i_{1}}x^{i_{2}}\cdots x^{i_{n}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have substituted }\left(  i_{1},i_{2},\ldots,i_{n}\right)
\text{ for }\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(
\sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)  \right) \\
\text{in the sum, since the map }S_{n}\rightarrow G,\ \sigma\mapsto\left(
\ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(  \sigma\right)  ,\ldots
,\ell_{n}\left(  \sigma\right)  \right) \\
\text{is a bijection (by Exercise \ref{exe.perm.lehmer2} \textbf{(c)})}%
\end{array}
\right) \\
&  =\underbrace{\sum_{\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in\left\{
0,1,\ldots,n-1\right\}  \times\left\{  0,1,\ldots,n-2\right\}  \times
\cdots\times\left\{  0,1,\ldots,n-n\right\}  }}_{=\sum_{i_{1}\in\left\{
0,1,\ldots,n-1\right\}  }\sum_{i_{2}\in\left\{  0,1,\ldots,n-2\right\}
}\cdots\sum_{i_{n}\in\left\{  0,1,\ldots,n-n\right\}  }}x^{i_{1}}x^{i_{2}%
}\cdots x^{i_{n}}\\
&  =\sum_{i_{1}\in\left\{  0,1,\ldots,n-1\right\}  }\sum_{i_{2}\in\left\{
0,1,\ldots,n-2\right\}  }\cdots\sum_{i_{n}\in\left\{  0,1,\ldots,n-n\right\}
}x^{i_{1}}x^{i_{2}}\cdots x^{i_{n}}\\
&  =\underbrace{\left(  \sum_{i_{1}\in\left\{  0,1,\ldots,n-1\right\}
}x^{i_{1}}\right)  }_{=1+x+x^{2}+\cdots+x^{n-1}}\underbrace{\left(
\sum_{i_{2}\in\left\{  0,1,\ldots,n-2\right\}  }x^{i_{2}}\right)
}_{=1+x+x^{2}+\cdots+x^{n-2}}\cdots\underbrace{\left(  \sum_{i_{n}\in\left\{
0,1,\ldots,n-n\right\}  }x^{i_{n}}\right)  }_{=1+x+x^{2}+\cdots+x^{n-n}}\\
&  =\left(  1+x+x^{2}+\cdots+x^{n-1}\right)  \left(  1+x+x^{2}+\cdots
+x^{n-2}\right)  \cdots\left(  1+x+x^{2}+\cdots+x^{n-n}\right) \\
&  =\left(  1+x+x^{2}+\cdots+x^{n-1}\right)  \left(  1+x+x^{2}+\cdots
+x^{n-2}\right)  \cdots\left(  1+x\right)  1\\
&  =\left(  1+x+x^{2}+\cdots+x^{n-1}\right)  \left(  1+x+x^{2}+\cdots
+x^{n-2}\right)  \cdots\left(  1+x\right) \\
&  =\left(  1+x\right)  \left(  1+x+x^{2}\right)  \cdots\left(  1+x+x^{2}%
+\cdots+x^{n-1}\right)  .
\end{align*}
This solves Exercise \ref{exe.perm.lehmer2} \textbf{(e)}.
\end{proof}

Exercise \ref{exe.perm.lehmer2} \textbf{(d)} also lets us solve Exercise
\ref{exe.sign-matrix} with less trouble than otherwise:

\begin{proof}
[Hints to Exercise \ref{exe.sign-matrix}.]The map $\left[  p\right]
\times\left[  q\right]  \rightarrow\left[  n\right]  ,\ \left(  i,j\right)
\mapsto\left(  i-1\right)  q+j$ is a bijection (since $n=pq$). In other words,
the map $\left[  p\right]  \times\left[  q\right]  \rightarrow\left[
n\right]  ,\ \left(  u,v\right)  \mapsto\left(  u-1\right)  q+v$ is a bijection.

If $\left(  i,j\right)  $ and $\left(  u,v\right)  $ are two elements of
$\left[  p\right]  \times\left[  q\right]  $, then we have the following
equivalences:%
\begin{equation}
\left(  \left(  i-1\right)  q+j<\left(  u-1\right)  q+v\right)
\ \Longleftrightarrow\ \left(  i<u\text{ or }\left(  i=u\text{ and
}j<v\right)  \right)  \label{sol.sign-matrix.eq1}%
\end{equation}
and%
\begin{equation}
\left(  \left(  j-1\right)  p+i>\left(  v-1\right)  p+u\right)
\ \Longleftrightarrow\ \left(  j>v\text{ or }\left(  j=v\text{ and
}i>u\right)  \right)  . \label{sol.sign-matrix.eq2}%
\end{equation}
(Indeed, both of these equivalences can easily be checked, by recalling that
$j$ and $v$ belong to $\left[  q\right]  $ and that $i$ and $u$ belong to
$\left[  p\right]  $.)

Let $k\in\left[  n\right]  $. Then, the definition of $\ell_{k}\left(
\sigma\right)  $ yields
\begin{align}
&  \ell_{k}\left(  \sigma\right) \nonumber\\
&  =\left(  \text{the number of all }j\in\left\{  k+1,k+2,\ldots,n\right\}
\text{ such that }\sigma\left(  k\right)  >\sigma\left(  j\right)  \right)
\nonumber\\
&  =\left(  \text{the number of all }j\in\left[  n\right]  \text{ such that
}k<j\text{ and }\sigma\left(  k\right)  >\sigma\left(  j\right)  \right)
\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the }j\in\left\{  k+1,k+2,\ldots,n\right\}  \text{ are
precisely}\\
\text{the }j\in\left[  n\right]  \text{ such that }k<j
\end{array}
\right) \nonumber\\
&  =\left(  \text{the number of all }h\in\left[  n\right]  \text{ such that
}k<h\text{ and }\sigma\left(  k\right)  >\sigma\left(  h\right)  \right)
\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have renamed the index }j\text{
as }h\right)  . \label{sol.sign-matrix.1}%
\end{align}


Now, forget that we fixed $k$. We thus have proven (\ref{sol.sign-matrix.1})
for each $k\in\left[  n\right]  $.

Fix $\left(  i,j\right)  \in\left[  p\right]  \times\left[  q\right]  $. Set
$k=\left(  i-1\right)  q+j$. Then, $k\in\left[  n\right]  $, and thus
(\ref{sol.sign-matrix.1}) yields%
\begin{align*}
&  \ell_{k}\left(  \sigma\right) \\
&  =\left(  \text{the number of all }h\in\left[  n\right]  \text{ such that
}k<h\text{ and }\sigma\left(  k\right)  >\sigma\left(  h\right)  \right) \\
&  =\left(  \text{the number of all }\left(  u,v\right)  \in\left[  p\right]
\times\left[  q\right]  \text{ such that }\underbrace{k}_{=\left(  i-1\right)
q+j}<\left(  u-1\right)  q+v\right. \\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{and }\sigma\left(  \underbrace{k}%
_{=\left(  i-1\right)  q+j}\right)  >\sigma\left(  \left(  u-1\right)
q+v\right)  \right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have substituted }\left(  u-1\right)  q+v\text{ for }h\text{,
since the}\\
\text{map }\left[  p\right]  \times\left[  q\right]  \rightarrow\left[
n\right]  ,\ \left(  u,v\right)  \mapsto\left(  u-1\right)  q+v\text{ is a
bijection}%
\end{array}
\right) \\
&  =\left(  \text{the number of all }\left(  u,v\right)  \in\left[  p\right]
\times\left[  q\right]  \text{ such that }\left(  i-1\right)  q+j<\left(
u-1\right)  q+v\right. \\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{and }\underbrace{\sigma\left(  \left(
i-1\right)  q+j\right)  }_{\substack{=\left(  j-1\right)  p+i\\\text{(by the
definition of }\sigma\text{)}}}>\underbrace{\sigma\left(  \left(  u-1\right)
q+v\right)  }_{\substack{=\left(  v-1\right)  p+u\\\text{(by the definition of
}\sigma\text{)}}}\right) \\
&  =\left(  \text{the number of all }\left(  u,v\right)  \in\left[  p\right]
\times\left[  q\right]  \text{ such that }\underbrace{\left(  i-1\right)
q+j<\left(  u-1\right)  q+v}_{\substack{\Longleftrightarrow\ \left(  i<u\text{
or }\left(  i=u\text{ and }j<v\right)  \right)  \\\text{(by
(\ref{sol.sign-matrix.eq1}))}}}\right. \\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{and }\underbrace{\left(  j-1\right)
p+i>\left(  v-1\right)  p+u}_{\substack{\Longleftrightarrow\ \left(  j>v\text{
or }\left(  j=v\text{ and }i>u\right)  \right)  \\\text{(by
(\ref{sol.sign-matrix.eq2}))}}}\right)
\end{align*}%
\begin{align*}
&  =\left(  \text{the number of all }\left(  u,v\right)  \in\left[  p\right]
\times\left[  q\right]  \text{ such that }\left(  i<u\text{ or }\left(
i=u\text{ and }j<v\right)  \right)  \right. \\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{and }\left(  j>v\text{ or }\left(
j=v\text{ and }i>u\right)  \right)  \right) \\
&  =\left(  \text{the number of all }\left(  u,v\right)  \in\left[  p\right]
\times\left[  q\right]  \text{ such that }\left(  i<u\text{ or }\left(
i=u\text{ and }j<v\right)  \right)  \right. \\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{and }j>v\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have dismissed the possibility that }\left(  j=v\text{ and
}i>u\right)  \text{,}\\
\text{because this possibility is incompatible with}\\
\text{the condition }\left(  i<u\text{ or }\left(  i=u\text{ and }j<v\right)
\right)
\end{array}
\right) \\
&  =\left(  \text{the number of all }\left(  u,v\right)  \in\left[  p\right]
\times\left[  q\right]  \text{ such that }i<u\text{ and }j>v\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have dismissed the possibility that }\left(  i=u\text{ and
}j<v\right)  \text{,}\\
\text{because this possibility is incompatible with the condition }j>v
\end{array}
\right) \\
&  =\underbrace{\left(  \text{the number of all }u\in\left[  p\right]  \text{
such that }i<u\right)  }_{=p-i}\\
&  \ \ \ \ \ \ \ \ \ \ \cdot\underbrace{\left(  \text{the number of all }%
v\in\left[  q\right]  \text{ such that }j>v\right)  }_{=j-1}\\
&  =\left(  p-i\right)  \left(  j-1\right)  .
\end{align*}
In view of $k=\left(  i-1\right)  q+j$, this rewrites as%
\begin{equation}
\ell_{\left(  i-1\right)  q+j}\left(  \sigma\right)  =\left(  p-i\right)
\left(  j-1\right)  . \label{sol.sign-matrix.4}%
\end{equation}


Now, forget that we fixed $\left(  i,j\right)  $. We thus have proven
(\ref{sol.sign-matrix.4}) for each $\left(  i,j\right)  \in\left[  p\right]
\times\left[  q\right]  $.

Exercise \ref{exe.perm.lehmer2} \textbf{(d)} yields%
\begin{align*}
\ell\left(  \sigma\right)   &  =\ell_{1}\left(  \sigma\right)  +\ell
_{2}\left(  \sigma\right)  +\cdots+\ell_{n}\left(  \sigma\right) \\
&  =\sum_{k\in\left[  n\right]  }\ell_{k}\left(  \sigma\right)
=\underbrace{\sum_{\left(  i,j\right)  \in\left[  p\right]  \times\left[
q\right]  }}_{=\sum_{i=1}^{p}\sum_{j=1}^{q}}\underbrace{\ell_{\left(
i-1\right)  q+j}\left(  \sigma\right)  }_{\substack{=\left(  p-i\right)
\left(  j-1\right)  \\\text{(by (\ref{sol.sign-matrix.4}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have substituted }\left(  i-1\right)  q+j\text{ for }k\text{ in
the sum,}\\
\text{since the map }\left[  p\right]  \times\left[  q\right]  \rightarrow
\left[  n\right]  ,\ \left(  i,j\right)  \mapsto\left(  i-1\right)  q+j\\
\text{is a bijection}%
\end{array}
\right) \\
&  =\sum_{i=1}^{p}\sum_{j=1}^{q}\left(  p-i\right)  \left(  j-1\right)
=\underbrace{\left(  \sum_{i=1}^{p}\left(  p-i\right)  \right)  }%
_{\substack{=\sum_{k=0}^{p-1}k\\\text{(here, we have substituted }k\\\text{for
}p-i\text{ in the sum)}}}\underbrace{\left(  \sum_{j=1}^{q}\left(  j-1\right)
\right)  }_{\substack{=\sum_{k=0}^{q-1}k\\\text{(here, we have substituted
}k\\\text{for }j-1\text{ in the sum)}}}\\
&  =\underbrace{\left(  \sum_{k=0}^{p-1}k\right)  }_{=\dfrac{\left(
p-1\right)  p}{2}}\underbrace{\left(  \sum_{k=0}^{q-1}k\right)  }%
_{=\dfrac{\left(  q-1\right)  q}{2}}=\dfrac{\left(  p-1\right)  p}{2}%
\cdot\dfrac{\left(  q-1\right)  q}{2} =\dfrac{pq\left(  p-1\right)  \left(
q-1\right)  }{4}.
\end{align*}
This solves Exercise \ref{exe.sign-matrix}.
\end{proof}

\subsection{Permutations as composed transpositions}

Recall a basic notation regarding permutations, which we shall now extend:

\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}.

Let us furthermore set $t_{i,i}=\operatorname*{id}$ for each $i\in\left[
n\right]  $. Thus, $t_{i,j}$ is defined even when $i$ and $j$ are not distinct.
\end{definition}

Thus, we have defined a permutation $t_{i,j}\in S_{n}$ whenever $n\in
\mathbb{N}$ and whenever $i$ and $j$ are two elements of $\left[  n\right]  $.
This permutation has the following properties:

\begin{itemize}
\item It satisfies $t_{i,j}\left(  i\right)  =j$ and $t_{i,j}\left(  j\right)
=i$.

\item It leaves any element of $\left[  n\right]  $ other than $i$ and $j$
unchanged. (In other words, it satisfies $t_{i,j}\left(  k\right)  =k$ for
each $k\in\left[  n\right]  \setminus\left\{  i,j\right\}  $.)

\item It is an involution, i.e., it satisfies $t_{i,j}\circ t_{i,j}%
=\operatorname*{id}$.
\end{itemize}

\begin{exercise}
\label{exe.perm.transpos-code}Let $n\in\mathbb{N}$. Let $\sigma\in S_{n}$.

\textbf{(a)} Prove that there is a unique $n$-tuple $\left(  i_{1}%
,i_{2},\ldots,i_{n}\right)  \in\left[  1\right]  \times\left[  2\right]
\times\cdots\times\left[  n\right]  $ such that%
\[
\sigma=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{n,i_{n}}.
\]


\textbf{(b)} Consider this $n$-tuple $\left(  i_{1},i_{2},\ldots,i_{n}\right)
$. Define the relation $\sim$ and the $\sim$-equivalence classes $E_{1}%
,E_{2},\ldots,E_{m}$ as in Exercise 7 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw7os.pdf}{homework set
\#7} (for $X=\left[  n\right]  $). (Thus, $m$ is the number of cycles in the
cycle decomposition of $\sigma$.)

Prove that $m$ is the number of all $k\in\left[  n\right]  $ satisfying
$i_{k}=k$.
\end{exercise}

A detailed solution to Exercise \ref{exe.perm.transpos-code} \textbf{(a)} can
be found in \cite[solution to Exercise 5.9]{detnotes}. Let us here give a
brief sketch:

\begin{proof}
[Solution to Exercise \ref{exe.perm.transpos-code} (sketched).]\textbf{(a)}
The trick is to prove the following:

\begin{statement}
\textit{Observation 1:} Let $n\in\mathbb{N}$. Let $k\in\left\{  0,1,\ldots
,n\right\}  $. Let $\sigma\in S_{n}$ be such that%
\begin{equation}
\left(  \sigma\left(  i\right)  =i\text{ for each }i\in\left\{  k+1,k+2,\ldots
,n\right\}  \right)  . \label{sol.perm.transpos-code.cl1.ass}%
\end{equation}
Then, there is a unique $k$-tuple $\left(  i_{1},i_{2},\ldots,i_{k}\right)
\in\left[  1\right]  \times\left[  2\right]  \times\cdots\times\left[
k\right]  $ such that $\sigma=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ
t_{k,i_{k}}$.
\end{statement}

[\textit{Proof of Observation 1:} This is proven by induction on $k$.

The \textit{induction base} (the case $k=0$) is a trivial exercise in
understanding empty lists\footnote{Specifically, you need to know that there
is only one $0$-tuple $\left(  i_{1},i_{2},\ldots,i_{0}\right)  $, namely the
empty $0$-tuple $\left(  {}\right)  $.}. (In fact, for $k=0$, the equality
(\ref{sol.perm.transpos-code.cl1.ass}) shows that $\sigma\left(  i\right)  =i$
for each $i\in\left[  n\right]  $, and thus $\sigma=\operatorname*{id}=\left(
\text{empty composition of permutations}\right)  =t_{1,i_{1}}\circ t_{2,i_{2}%
}\circ\cdots\circ t_{0,i_{0}}$ for the $0$-tuple $\left(  i_{1},i_{2}%
,\ldots,i_{0}\right)  =\left(  {}\right)  $.)

\textit{Induction step:} Let $k\in\left\{  0,1,\ldots,n\right\}  $ be
positive. Assume (as the induction hypothesis) that Observation 1 holds for
$k-1$ instead of $k$. We then must prove Observation 1 for $k$. So let
$\sigma\in S_{n}$ be such that (\ref{sol.perm.transpos-code.cl1.ass}) holds.
We must prove that there is a unique $k$-tuple $\left(  i_{1},i_{2}%
,\ldots,i_{k}\right)  \in\left[  1\right]  \times\left[  2\right]
\times\cdots\times\left[  k\right]  $ such that $\sigma=t_{1,i_{1}}\circ
t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}}$.

Set $g=\sigma^{-1}\left(  k\right)  $. Thus, $\sigma\left(  g\right)  =k$ and
$g\in\left[  k\right]  $\ \ \ \ \footnote{\textit{Proof.} Assume the contrary.
Thus, $g\notin\left[  k\right]  $, so that $g\in\left\{  k+1,k+2,\ldots
,n\right\}  $. Therefore, (\ref{sol.perm.transpos-code.cl1.ass}) (applied to
$i=g$) yields $\sigma\left(  g\right)  =g$. But $\sigma\left(  g\right)
=k\in\left[  k\right]  $. This contradicts $\sigma\left(  g\right)
=g\notin\left[  k\right]  $. This contradiction shows that our assumption was
false, qed.}. Thus, $k$ and $g$ belong to the set $\left[  k\right]  $.

The permutation $t_{k,g}$ is either a transposition (if $k\neq g$) or the
identity map (if $k=g$). In either case, it satisfies $t_{k,g}\circ
t_{k,g}=\operatorname*{id}$ and leaves all elements of $\left[  n\right]  $
other than $k$ and $g$ unchanged. Hence, the permutation $t_{k,g}$ leaves each
$i\in\left\{  k+1,k+2,\ldots,n\right\}  $ unchanged (since $i$ does
\textbf{not} belong to the set $\left[  k\right]  $, and thus $i$ equals
neither $k$ nor $g$).

Define $\tau\in S_{n}$ by $\tau=\sigma\circ t_{k,g}$. (Notice that $\left(
t_{k,g}\right)  ^{-1}=t_{k,g}$.) Then, from
(\ref{sol.perm.transpos-code.cl1.ass}), we can easily derive that $\tau\left(
i\right)  =i$ for each $i\in\left\{  k+1,k+2,\ldots,n\right\}  $ (because the
permutation $t_{k,g}$ leaves $i$ unchanged). Combining this with the fact that
$\tau\left(  k\right)  =k$ (because $\underbrace{\tau}_{=\sigma\circ t_{k,g}%
}\left(  k\right)  =\sigma\left(  \underbrace{t_{k,g}\left(  k\right)  }%
_{=g}\right)  =\sigma\left(  g\right)  =k$), we conclude that $\tau\left(
i\right)  =i$ for each $i\in\left\{  k,k+1,\ldots,n\right\}  $. Hence, by the
induction hypothesis, we can apply Observation 1 to $k-1$ and $\tau$ instead
of $k$ and $\sigma$. We conclude that there is a unique $\left(  k-1\right)
$-tuple $\left(  i_{1},i_{2},\ldots,i_{k-1}\right)  \in\left[  1\right]
\times\left[  2\right]  \times\cdots\times\left[  k-1\right]  $ such that
$\tau=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{k-1,i_{k-1}}$. We can
easily extend this $\left(  k-1\right)  $-tuple to a $k$-tuple $\left(
i_{1},i_{2},\ldots,i_{k}\right)  \in\left[  1\right]  \times\left[  2\right]
\times\cdots\times\left[  k\right]  $ such that $\sigma=t_{1,i_{1}}\circ
t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}}$\ \ \ \ \footnote{\textit{Proof.} To
extend the $\left(  k-1\right)  $-tuple $\left(  i_{1},i_{2},\ldots
,i_{k-1}\right)  \in\left[  1\right]  \times\left[  2\right]  \times
\cdots\times\left[  k-1\right]  $ to a $k$-tuple $\left(  i_{1},i_{2}%
,\ldots,i_{k}\right)  \in\left[  1\right]  \times\left[  2\right]
\times\cdots\times\left[  k\right]  $, we need only to define $i_{k}$. Let us
define $i_{k}$ by $i_{k}=g$. This yields a well-defined $k$-tuple $\left(
i_{1},i_{2},\ldots,i_{k}\right)  \in\left[  1\right]  \times\left[  2\right]
\times\cdots\times\left[  k\right]  $, because $i_{k}=g\in\left[  k\right]  $.
It remains to prove that this $k$-tuple satisfies $\sigma=t_{1,i_{1}}\circ
t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}}$.
\par
We have $\tau=\sigma\circ t_{k,g}$, so that $\tau\circ t_{k,g}=\sigma
\circ\underbrace{t_{k,g}\circ t_{k,g}}_{=\operatorname*{id}}=\sigma$, so that
\[
\sigma=\underbrace{\tau}_{=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ
t_{k-1,i_{k-1}}}\circ\underbrace{t_{k,g}}_{\substack{=t_{k,i_{k}%
}\\\text{(since }g=i_{k}\text{)}}}=\left(  t_{1,i_{1}}\circ t_{2,i_{2}}%
\circ\cdots\circ t_{k-1,i_{k-1}}\right)  \circ t_{k,i_{k}}=t_{1,i_{1}}\circ
t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}}.
\]
This completes our proof.}. Thus, there exists \textbf{at least one} $k$-tuple
$\left(  i_{1},i_{2},\ldots,i_{k}\right)  \in\left[  1\right]  \times\left[
2\right]  \times\cdots\times\left[  k\right]  $ such that $\sigma=t_{1,i_{1}%
}\circ t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}}$.

Recall that we must prove that there is a \textbf{unique} $k$-tuple $\left(
i_{1},i_{2},\ldots,i_{k}\right)  \in\left[  1\right]  \times\left[  2\right]
\times\cdots\times\left[  k\right]  $ such that $\sigma=t_{1,i_{1}}\circ
t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}}$. We have just proven that there
exists \textbf{at least one} such $k$-tuple. Hence, it only remains to show
that there exists \textbf{at most one} such $k$-tuple.

Let $\left(  u_{1},u_{2},\ldots,u_{k}\right)  $ and $\left(  v_{1}%
,v_{2},\ldots,v_{k}\right)  $ be two $k$-tuples $\left(  i_{1},i_{2}%
,\ldots,i_{k}\right)  \in\left[  1\right]  \times\left[  2\right]
\times\cdots\times\left[  k\right]  $ such that $\sigma=t_{1,i_{1}}\circ
t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}}$. We shall prove that $\left(
u_{1},u_{2},\ldots,u_{k}\right)  =\left(  v_{1},v_{2},\ldots,v_{k}\right)  $.
This will, of course, entail that there exists \textbf{at most one} such
$k$-tuple; thus, the induction step will be complete.

We know that $\left(  u_{1},u_{2},\ldots,u_{k}\right)  $ is a $k$-tuple
$\left(  i_{1},i_{2},\ldots,i_{k}\right)  \in\left[  1\right]  \times\left[
2\right]  \times\cdots\times\left[  k\right]  $ such that $\sigma=t_{1,i_{1}%
}\circ t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}}$. In other words, $\left(
u_{1},u_{2},\ldots,u_{k}\right)  \in\left[  1\right]  \times\left[  2\right]
\times\cdots\times\left[  k\right]  $ and $\sigma=t_{1,u_{1}}\circ t_{2,u_{2}%
}\circ\cdots\circ t_{k,u_{k}}$. Notice that $\left(  u_{1},u_{2},\ldots
,u_{k}\right)  \in\left[  1\right]  \times\left[  2\right]  \times\cdots
\times\left[  k\right]  $ shows that $u_{j}\in\left[  j\right]  $ for each
$j\in\left[  k\right]  $. In other words, $u_{j}\leq j$ for each $j\in\left[
k\right]  $. Thus, each $j\in\left[  k-1\right]  $ satisfies $t_{j,u_{j}%
}\left(  k\right)  =k$ (because $k$ equals neither $j$ nor $u_{j}$ (since
$u_{j}\leq j\leq k-1<k$)). In other words, the permutations $t_{1,u_{1}%
},t_{2,u_{2}},\ldots,t_{k-1,u_{k-1}}$ leave $k$ unchanged. Now,%
\begin{align*}
\underbrace{\sigma}_{=t_{1,u_{1}}\circ t_{2,u_{2}}\circ\cdots\circ t_{k,u_{k}%
}}\left(  u_{k}\right)   &  =\left(  t_{1,u_{1}}\circ t_{2,u_{2}}\circ
\cdots\circ t_{k,u_{k}}\right)  \left(  u_{k}\right) \\
&  =\left(  t_{1,u_{1}}\circ t_{2,u_{2}}\circ\cdots\circ t_{k-1,u_{k-1}%
}\right)  \left(  \underbrace{t_{k,u_{k}}\left(  u_{k}\right)  }_{=k}\right)
\\
&  =\left(  t_{1,u_{1}}\circ t_{2,u_{2}}\circ\cdots\circ t_{k-1,u_{k-1}%
}\right)  \left(  k\right)  =k
\end{align*}
(since the permutations $t_{1,u_{1}},t_{2,u_{2}},\ldots,t_{k-1,u_{k-1}}$ leave
$k$ unchanged). Thus, $u_{k}=\sigma^{-1}\left(  k\right)  =g$. Similarly,
$v_{k}=g$.

Now,%
\begin{align*}
\sigma &  =t_{1,u_{1}}\circ t_{2,u_{2}}\circ\cdots\circ t_{k,u_{k}}=\left(
t_{1,u_{1}}\circ t_{2,u_{2}}\circ\cdots\circ t_{k-1,u_{k-1}}\right)  \circ
t_{k,u_{k}}\\
&  =\left(  t_{1,u_{1}}\circ t_{2,u_{2}}\circ\cdots\circ t_{k-1,u_{k-1}%
}\right)  \circ t_{k,g}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }%
u_{k}=g\right)  ,
\end{align*}
so that
\begin{align*}
\tau &  =\underbrace{\sigma}_{=\left(  t_{1,u_{1}}\circ t_{2,u_{2}}\circ
\cdots\circ t_{k-1,u_{k-1}}\right)  \circ t_{k,g}}\circ t_{k,g}=\left(
t_{1,u_{1}}\circ t_{2,u_{2}}\circ\cdots\circ t_{k-1,u_{k-1}}\right)
\circ\underbrace{t_{k,g}\circ t_{k,g}}_{=\operatorname*{id}}\\
&  =t_{1,u_{1}}\circ t_{2,u_{2}}\circ\cdots\circ t_{k-1,u_{k-1}}.
\end{align*}
In other words, $\left(  u_{1},u_{2},\ldots,u_{k-1}\right)  $ is a $\left(
k-1\right)  $-tuple $\left(  i_{1},i_{2},\ldots,i_{k-1}\right)  \in\left[
1\right]  \times\left[  2\right]  \times\cdots\times\left[  k-1\right]  $ such
that $\tau=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{k-1,i_{k-1}}$.
Similarly, $\left(  v_{1},v_{2},\ldots,v_{k-1}\right)  $ is such a $\left(
k-1\right)  $-tuple as well.

But recall that there is a unique $\left(  k-1\right)  $-tuple $\left(
i_{1},i_{2},\ldots,i_{k-1}\right)  \in\left[  1\right]  \times\left[
2\right]  \times\cdots\times\left[  k-1\right]  $ such that $\tau=t_{1,i_{1}%
}\circ t_{2,i_{2}}\circ\cdots\circ t_{k-1,i_{k-1}}$. Thus, any two such
$\left(  k-1\right)  $-tuples are identical. Hence, $\left(  u_{1}%
,u_{2},\ldots,u_{k-1}\right)  $ and $\left(  v_{1},v_{2},\ldots,v_{k-1}%
\right)  $ are identical (since $\left(  u_{1},u_{2},\ldots,u_{k-1}\right)  $
and $\left(  v_{1},v_{2},\ldots,v_{k-1}\right)  $ are two such $\left(
k-1\right)  $-tuples). Combining this with $u_{k} = v_{k}$ (which follows from
$u_{k} = g$ and $v_{k} = g$), we obtain $\left(  u_{1},u_{2},\ldots
,u_{k}\right)  =\left(  v_{1},v_{2},\ldots,v_{k}\right)  $. As we have said,
this completes the induction step. Thus, Observation 1 is proven.]

Now, let $n\in\mathbb{N}$ and $\sigma\in S_{n}$. Then, $\left\{
n+1,n+2,\ldots,n\right\}  $ is the empty set. In other words, there exists no
$i\in\left\{  n+1,n+2,\ldots,n\right\}  $. Hence, the statement $\left(
\sigma\left(  i\right)  =i\text{ for each }i\in\left\{  n+1,n+2,\ldots
,n\right\}  \right)  $ is vacuously true. Thus, Observation 1 (applied to
$k=n$) shows that there is a unique $n$-tuple $\left(  i_{1},i_{2}%
,\ldots,i_{n}\right)  \in\left[  1\right]  \times\left[  2\right]
\times\cdots\times\left[  n\right]  $ such that $\sigma=t_{1,i_{1}}\circ
t_{2,i_{2}}\circ\cdots\circ t_{n,i_{n}}$. This solves Exercise
\ref{exe.perm.transpos-code} \textbf{(a)}.

\textbf{(b)} If $\tau\in S_{n}$ is any permutation, then $z\left(
\tau\right)  $ shall denote the number of cycles in the cycle decomposition of
$\tau$. Thus, $m=z\left(  \sigma\right)  $ (since $m$ is the number of cycles
in the cycle decomposition of $\sigma$). Hence, it remains to prove that
$z\left(  \sigma\right)  $ is the number of all $k\in\left[  n\right]  $
satisfying $i_{k}=k$.

Let us first prove a basic fact:

\begin{statement}
\textit{Observation 2:} Let $\tau\in S_{n}$ and $p\in\left[  n\right]  $ be
such that $\tau\left(  p\right)  =p$. Let $q$ be an element of $\left[
n\right]  $ distinct from $p$. Then, $z\left(  \tau\circ t_{p,q}\right)
=z\left(  \tau\right)  -1$.
\end{statement}

[\textit{Example:} For this example, let $n=9$, and let $\tau\in S_{9}$ be the
permutation whose one-line notation is $\left(  4,6,1,3,5,2,9,8,7\right)  $
(that is, which satisfies $\left(  \tau\left(  1\right)  ,\tau\left(
2\right)  ,\ldots,\tau\left(  9\right)  \right)  =\left(
4,6,1,3,5,2,9,8,7\right)  $). Then, the cycle decomposition of $\tau$ looks as
follows:%
\[
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}] \node[main node] (1) {1}; \node[main node] (3) [below right of=1] {3}; \node[main node] (4) [above right of=1] {4}; \node[main node] (2) [above left of=1] {2}; \node[main node] (6) [below left of=1] {6}; \node[main node] (5) [below right of=4] {5}; \node[main node] (7) [above right of=5] {7}; \node[main node] (9) [below right of=5] {9}; \node[main node] (8) [above right of=9] {8}; \path[every node/.style={font=\sffamily\small}] (1) edge (4) (2) edge [bend right] (6) (3) edge (1) (4) edge (3) (5) edge [loop left] (5) (6) edge [bend right] (2) (7) edge [bend right] (9) (8) edge [loop left] (8) (9) edge [bend right] (7); \end{tikzpicture}.
\]
This contains $5$ cycles. Thus, $z\left(  \tau\right)  =5$.

Now, let $p=5$ and $q=3$. (This clearly satisfies $\tau\left(  p\right)  =p$.)
Then, Observation 2 yields $z\left(  \tau\circ t_{p,q}\right)
=\underbrace{z\left(  \tau\right)  }_{=5}-1=5-1=4$. And we can indeed confirm
this: The cycle decomposition of $\tau\circ t_{p,q}=\tau\circ t_{5,3}$ looks
as follows:%
\[
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
\node[main node] (1) {1};
\node[main node] (5) [below right of=1] {5};
\node[main node] (4) [above right of=1] {4};
\node[main node] (3) [below right of=4] {3};
\node[main node] (2) [above left of=1] {2};
\node[main node] (6) [below left of=1] {6};
\node[main node] (7) [above right of=3] {7};
\node[main node] (9) [below right of=3] {9};
\node[main node] (8) [above right of=9] {8};
\path[every node/.style={font=\sffamily\small}] (1) edge (4) (4) edge (3) (3) edge (5) (5) edge (1) (2) edge [bend right] (6) (6) edge [bend right] (2) (7) edge [bend right] (9) (8) edge [loop left] (8) (9) edge [bend right] (7); \end{tikzpicture}.
\]
This contains $4$ cycles. Thus, $z\left(  \tau\circ t_{p,q}\right)  =4$,
exactly as Observation 2 foretold.

As this example shows, the cycle decomposition of $\tau\circ t_{p,q}$ is
actually \textquotedblleft almost the same as\textquotedblright\ that of
$\tau$; more precisely, all cycles of $\tau$ appear in the cycle decomposition
of $\tau\circ t_{p,q}$, with the exception of two cycles (the cycles $\left\{
5\right\}  $ and $\left\{  3,1,4\right\}  $), which get merged into a single
cycle in the cycle decomposition of $\tau\circ t_{p,q}$. Visually speaking,
when we compose $\tau$ with $t_{p,q}$, we \textquotedblleft
re-route\textquotedblright\ the arc from $\sigma^{-1}\left(  q\right)  =4$ to
$q=3$ through the vertex $p=5$; therefore, the vertex $p$ (which formed a
$1$-vertex cycle in $\tau$, since $\tau\left(  p\right)  =p$) gets
\textquotedblleft caught up\textquotedblright\ in the cycle $\left\{
3,1,4\right\}  $, which causes the two cycles to get merged. This behavior
clearly generalizes; the proof below just makes this more formal.]

[\textit{Proof of Observation 2:} The cycle decomposition of $\tau$ has a
cycle containing the element $p$ alone (since $\tau\left(  p\right)  =p$). Let
$\mathfrak{z}_{1}$ be this cycle. Thus, $\mathfrak{z}_{1}=\left\{  p\right\}
$. Hence, $\mathfrak{z}_{1}$ does not contain $q$ (since $q\neq p$).

Furthermore, let $\mathfrak{z}_{2}$ be the cycle in the cycle decomposition of
$\tau$ that contains the element $q$. This cycle $\mathfrak{z}_{2}$ is
distinct from $\mathfrak{z}_{1}$ (because $\mathfrak{z}_{1}$ does not contain
$q$). Thus, $\mathfrak{z}_{2}$ does not contain $p$ (since $p$ is contained in
the cycle $\mathfrak{z}_{1}$, which is distinct from $\mathfrak{z}_{2}$). In
other words, $p\notin\mathfrak{z}_{2}$.

Let us analyze what happens to the cycle decomposition of $\tau$ when we
compose $\tau$ with $t_{p,q}$ (thus obtaining $\tau\circ t_{p,q}$). The only
values of $\tau$ that change when we compose $\tau$ with $t_{p,q}$ are the
values at the numbers $p$ and $q$ (because $t_{p,q}$ leaves all other numbers
unchanged). Hence, all cycles other than $\mathfrak{z}_{1}$ and $\mathfrak{z}%
_{2}$ in the cycle decomposition of $\tau$ remain unchanged in the cycle
decomposition of $\tau\circ t_{p,q}$ (because these cycles contain neither $p$
nor $q$). The only two cycles that can possibly change are $\mathfrak{z}_{1}$
and $\mathfrak{z}_{2}$. We claim that these two cycles are \textbf{merged into
a single cycle} in $\tau\circ t_{p,q}$.

Indeed, let us write the cycle $\mathfrak{z}_{2}$ in the form $\mathfrak{z}%
_{2}=\left\{  \tau^{0}\left(  q\right)  ,\tau^{1}\left(  q\right)
,\ldots,\tau^{k-1}\left(  q\right)  \right\}  $, where $k$ is the smallest
positive integer satisfying $\tau^{k}\left(  q\right)  =q$. (Indeed,
$\mathfrak{z}_{2}$ can be written in this form, since $\mathfrak{z}_{2}$ is
the cycle of $\tau$ that contains $q$.) Thus,%
\[
\mathfrak{z}_{2}=\left\{  \tau^{0}\left(  q\right)  ,\tau^{1}\left(  q\right)
,\ldots,\tau^{k-1}\left(  q\right)  \right\}  =\left\{  \tau^{1}\left(
q\right)  ,\tau^{2}\left(  q\right)  ,\ldots,\tau^{k}\left(  q\right)
\right\}
\]
(since $\tau^{0}\left(  q\right)  =q=\tau^{k}\left(  q\right)  $).

Let $\gamma$ be the permutation $\tau\circ t_{p,q}\in S_{n}$. Thus, each
$i\in\left[  k-1\right]  $ satisfies $\gamma\left(  \tau^{i}\left(  q\right)
\right)  =\tau^{i+1}\left(  q\right)  $\ \ \ \ \footnote{\textit{Proof.} Let
$i\in\left[  k-1\right]  $. Hence, $\tau^{i}\left(  q\right)  \neq q$ (since
$k$ is the \textbf{smallest} positive integer satisfying $\tau^{k}\left(
q\right)  =q$). Also, $\tau^{i}\left(  q\right)  \neq p$ (since $\tau
^{i}\left(  q\right)  \in\left\{  \tau^{0}\left(  q\right)  ,\tau^{1}\left(
q\right)  ,\ldots,\tau^{k-1}\left(  q\right)  \right\}  =\mathfrak{z}_{2}$ but
$p\notin\mathfrak{z}_{2}$). Thus, $\tau^{i}\left(  q\right)  $ equals neither
$p$ nor $q$. Hence, the transposition $t_{p,q}$ leaves $\tau^{i}\left(
q\right)  $ unchanged. In other words, $t_{p,q}\left(  \tau^{i}\left(
q\right)  \right)  =\tau^{i}\left(  q\right)  $.
\par
Now, $\underbrace{\gamma}_{=\tau\circ t_{p,q}}\left(  \tau^{i}\left(
q\right)  \right)  =\left(  \tau\circ t_{p,q}\right)  \left(  \tau^{i}\left(
q\right)  \right)  =\tau\left(  \underbrace{t_{p,q}\left(  \tau^{i}\left(
q\right)  \right)  }_{=\tau^{i}\left(  q\right)  }\right)  =\tau\left(
\tau^{i}\left(  q\right)  \right)  =\tau^{i+1}\left(  q\right)  $, qed.}. In
other words, the permutation $\gamma$ sends each of the elements $\tau
^{1}\left(  q\right)  ,\tau^{2}\left(  q\right)  ,\ldots,\tau^{k}\left(
q\right)  $ (apart from the last one) to the next one. Hence, the elements
$\tau^{1}\left(  q\right)  ,\tau^{2}\left(  q\right)  ,\ldots,\tau^{k}\left(
q\right)  $ lie on one and the same cycle in the cycle decomposition of
$\gamma$. Let us denote this cycle by $\mathfrak{z}^{\prime}$. Thus, $\tau
^{i}\left(  q\right)  \in\mathfrak{z}^{\prime}$ for each $i\in\left[
k\right]  $. Applying this to $i=k$, we conclude that $\tau^{k}\left(
q\right)  \in\mathfrak{z}^{\prime}$. Thus, $q=\tau^{k}\left(  q\right)
\in\mathfrak{z}^{\prime}$.

The cycle $\mathfrak{z}^{\prime}$ contains $\tau^{1}\left(  q\right)
,\tau^{2}\left(  q\right)  ,\ldots,\tau^{k}\left(  q\right)  $. In other
words, the cycle $\mathfrak{z}^{\prime}$ contains all elements of
$\mathfrak{z}_{2}$ (since $\mathfrak{z}_{2}=\left\{  \tau^{1}\left(  q\right)
,\tau^{2}\left(  q\right)  ,\ldots,\tau^{k}\left(  q\right)  \right\}  $).

Also, $\underbrace{\gamma}_{=\tau\circ t_{p,q}}\left(  q\right)  =\left(
\tau\circ t_{p,q}\right)  \left(  q\right)  =\tau\left(  \underbrace{t_{p,q}%
\left(  q\right)  }_{=p}\right)  =\tau\left(  p\right)  =p$. Hence, $p$ lies
on the same cycle in the cycle decomposition of $\gamma$ as $q$. In other
words, $p$ lies on the cycle in the cycle decomposition of $\gamma$ that
contains $q$. Since the latter cycle is $\mathfrak{z}^{\prime}$ (because
$q\in\mathfrak{z}^{\prime}$), we thus conclude that $p$ lies on $\mathfrak{z}%
^{\prime}$. In other words, $p\in\mathfrak{z}^{\prime}$. In other words, the
cycle $\mathfrak{z}^{\prime}$ contains all elements of $\mathfrak{z}_{1}$
(since $\mathfrak{z}_{1}=\left\{  p\right\}  $).

The cycle $\mathfrak{z}^{\prime}$ in the cycle decomposition of $\gamma$ thus
contains all elements of $\mathfrak{z}_{1}$ and all elements of $\mathfrak{z}%
_{2}$. In view of $\gamma=\tau\circ t_{p,q}$, this rewrites as follows: The
cycle $\mathfrak{z}^{\prime}$ in the cycle decomposition of $\tau\circ
t_{p,q}$ contains all elements of $\mathfrak{z}_{1}$ and all elements of
$\mathfrak{z}_{2}$. Furthermore, this cycle $\mathfrak{z}^{\prime}$ cannot
contain any other elements (because if it did, then it would contain elements
from cycles in the cycle decomposition of $\tau$ other than $\mathfrak{z}_{1}$
and $\mathfrak{z}_{2}$; but this would contradict the fact that all cycles
other than $\mathfrak{z}_{1}$ and $\mathfrak{z}_{2}$ in the cycle
decomposition of $\tau$ remain unchanged in the cycle decomposition of
$\tau\circ t_{p,q}$). Hence, this cycle $\mathfrak{z}^{\prime}$ contains all
elements of $\mathfrak{z}_{1}$ and all elements of $\mathfrak{z}_{2}$ and no
more elements. Thus, the cycles $\mathfrak{z}_{1}$ and $\mathfrak{z}_{2}$ are
merged into a single cycle in $\tau\circ t_{p,q}$.

So we have seen that when we compose $\tau$ with $t_{p,q}$, the cycle
decomposition does not change except for the fact that the two cycles
$\mathfrak{z}_{1}$ and $\mathfrak{z}_{2}$ get merged into a single cycle.
Thus, the total number of cycles in the cycle decomposition decreases by $1$.
In other words, the total number of cycles in the cycle decomposition of
$\tau\circ t_{p,q}$ is $1$ less than the total number of cycles in the cycle
decomposition of $\tau$. In other words, $z\left(  \tau\circ t_{p,q}\right)
=z\left(  \tau\right)  -1$. This proves Observation 2.]

Next, we make the following claim: For each $p\in\left\{  0,1,\ldots
,n\right\}  $, we have%
\begin{equation}
z\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{p,i_{p}}\right)
=n-p+\left\vert \left\{  k\in\left[  p\right]  \ \mid\ i_{k}=k\right\}
\right\vert . \label{sol.perm.transpos-code.b.goal}%
\end{equation}


[\textit{Proof of (\ref{sol.perm.transpos-code.b.goal}):} We shall prove
(\ref{sol.perm.transpos-code.b.goal}) by induction on $p$:

\textit{Induction base:} We have%
\[
z\left(  \underbrace{t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{0,i_{0}}%
}_{=\operatorname*{id}}\right)  =z\left(  \operatorname*{id}\right)  =n
\]
(since the permutation $\operatorname*{id}$ has $n$ cycles in its cycle
decomposition). Comparing this with%
\[
n-0+\left\vert \underbrace{\left\{  k\in\left[  0\right]  \ \mid
\ i_{k}=k\right\}  }_{\substack{=\varnothing\\\text{(since }\left[  0\right]
=\varnothing\text{)}}}\right\vert =n-0+\underbrace{\left\vert \varnothing
\right\vert }_{=0}=n,
\]
we obtain $z\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{0,i_{0}%
}\right)  =n-0+\left\vert \left\{  k\in\left[  0\right]  \ \mid\ i_{k}%
=k\right\}  \right\vert $. In other words,
(\ref{sol.perm.transpos-code.b.goal}) holds for $p=0$. This completes the
induction base.

\textit{Induction step:} Let $p\in\left\{  0,1,\ldots,n\right\}  $ be
positive. Assume that (\ref{sol.perm.transpos-code.b.goal}) holds for $p-1$
instead of $p$. In other words, assume that%
\begin{equation}
z\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{p-1,i_{p-1}}\right)
=n-\left(  p-1\right)  +\left\vert \left\{  k\in\left[  p-1\right]
\ \mid\ i_{k}=k\right\}  \right\vert .
\label{sol.perm.transpos-code.b.goal.pf.hyp}%
\end{equation}


We must prove that (\ref{sol.perm.transpos-code.b.goal}) holds for $p$.

We have $p\in\left[  n\right]  $ (since $p\in\left\{  0,1,\ldots,n\right\}  $
is positive). Also,%
\begin{align}
&  \left\{  k\in\underbrace{\left[  p\right]  }_{=\left\{  p\right\}
\cup\left[  p-1\right]  }\ \mid\ i_{k}=k\right\} \nonumber\\
&  =\left\{  k\in\left\{  p\right\}  \cup\left[  p-1\right]  \ \mid
\ i_{k}=k\right\}  =\underbrace{\left\{  k\in\left\{  p\right\}  \ \mid
\ i_{k}=k\right\}  }_{=%
\begin{cases}
\left\{  p\right\}  , & \text{if }i_{p}=p;\\
\varnothing, & \text{if }i_{p}\neq p
\end{cases}
}\cup\left\{  k\in\left[  p-1\right]  \ \mid\ i_{k}=k\right\} \nonumber\\
&  =%
\begin{cases}
\left\{  p\right\}  , & \text{if }i_{p}=p;\\
\varnothing, & \text{if }i_{p}\neq p
\end{cases}
\cup\left\{  k\in\left[  p-1\right]  \ \mid\ i_{k}=k\right\}  .
\label{sol.perm.transpos-code.b.goal.pf.3}%
\end{align}


We are in one of the following two cases:

\textit{Case 1:} We have $i_{p}=p$.

\textit{Case 2:} We have $i_{p}\neq p$.

Let us first consider Case 1. In this case, we have $i_{p}=p$. Thus,
$t_{p,i_{p}}=\operatorname*{id}$. Also,
(\ref{sol.perm.transpos-code.b.goal.pf.3}) becomes%
\begin{align*}
&  \left\{  k\in\left[  p\right]  \ \mid\ i_{k}=k\right\} \\
&  =\underbrace{%
\begin{cases}
\left\{  p\right\}  , & \text{if }i_{p}=p;\\
\varnothing, & \text{if }i_{p}\neq p
\end{cases}
}_{\substack{=\left\{  p\right\}  \\\text{(since }i_{p}=p\text{)}}%
}\cup\left\{  k\in\left[  p-1\right]  \ \mid\ i_{k}=k\right\}  =\left\{
p\right\}  \cup\left\{  k\in\left[  p-1\right]  \ \mid\ i_{k}=k\right\}  ,
\end{align*}
so that%
\begin{align}
\left\vert \left\{  k\in\left[  p\right]  \ \mid\ i_{k}=k\right\}
\right\vert  &  =\left\vert \left\{  p\right\}  \cup\left\{  k\in\left[
p-1\right]  \ \mid\ i_{k}=k\right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  k\in\left[  p-1\right]  \ \mid\ i_{k}=k\right\}
\right\vert +1 \label{sol.perm.transpos-code.b.goal.pf.3a}%
\end{align}
(since $p\notin\left\{  k\in\left[  p-1\right]  \ \mid\ i_{k}=k\right\}  $).

Now,%
\[
t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{p,i_{p}}=\left(  t_{1,i_{1}%
}\circ t_{2,i_{2}}\circ\cdots\circ t_{p-1,i_{p-1}}\right)  \circ
\underbrace{t_{p,i_{p}}}_{=\operatorname*{id}}=t_{1,i_{1}}\circ t_{2,i_{2}%
}\circ\cdots\circ t_{p-1,i_{p-1}}.
\]
Hence,%
\begin{align*}
z\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{p,i_{p}}\right)   &
=z\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{p-1,i_{p-1}}\right)
\\
&  =n-\left(  p-1\right)  +\left\vert \left\{  k\in\left[  p-1\right]
\ \mid\ i_{k}=k\right\}  \right\vert \ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.perm.transpos-code.b.goal.pf.hyp})}\right) \\
&  =n-p+\underbrace{\left\vert \left\{  k\in\left[  p-1\right]  \ \mid
\ i_{k}=k\right\}  \right\vert +1}_{\substack{=\left\vert \left\{  k\in\left[
p\right]  \ \mid\ i_{k}=k\right\}  \right\vert \\\text{(by
(\ref{sol.perm.transpos-code.b.goal.pf.3a}))}}}\\
&  =n-p+\left\vert \left\{  k\in\left[  p\right]  \ \mid\ i_{k}=k\right\}
\right\vert .
\end{align*}
Thus, we have proven that (\ref{sol.perm.transpos-code.b.goal}) holds for $p$
in Case 1.

Let us now consider Case 2. In this case, we have $i_{p}\neq p$. But $i_{p}%
\in\left[  p\right]  $ (since $\left(  i_{1},i_{2},\ldots,i_{n}\right)
\in\left[  1\right]  \times\left[  2\right]  \times\cdots\times\left[
n\right]  $), so that $i_{p}\leq p$. Thus, $i_{p}<p$ (since $i_{p}\neq p$).

Also, (\ref{sol.perm.transpos-code.b.goal.pf.3}) becomes%
\begin{align}
&  \left\{  k\in\left[  p\right]  \ \mid\ i_{k}=k\right\} \nonumber\\
&  =\underbrace{%
\begin{cases}
\left\{  p\right\}  , & \text{if }i_{p}=p;\\
\varnothing, & \text{if }i_{p}\neq p
\end{cases}
}_{\substack{=\varnothing\\\text{(since }i_{p}\neq p\text{)}}}\cup\left\{
k\in\left[  p-1\right]  \ \mid\ i_{k}=k\right\} \nonumber\\
&  =\left\{  k\in\left[  p-1\right]  \ \mid\ i_{k}=k\right\}  .
\label{sol.perm.transpos-code.b.goal.pf.3b}%
\end{align}


Let $\tau=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{p-1,i_{p-1}}$. Thus,%
\begin{align}
z\left(  \tau\right)   &  =z\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ
\cdots\circ t_{p-1,i_{p-1}}\right)  =\underbrace{n-\left(  p-1\right)
}_{=n-p+1}+\left\vert \underbrace{\left\{  k\in\left[  p-1\right]
\ \mid\ i_{k}=k\right\}  }_{\substack{=\left\{  k\in\left[  p\right]
\ \mid\ i_{k}=k\right\}  \\\text{(by
(\ref{sol.perm.transpos-code.b.goal.pf.3b}))}}}\right\vert \nonumber\\
&  =n-p+1+\left\vert \left\{  k\in\left[  p\right]  \ \mid\ i_{k}=k\right\}
\right\vert . \label{sol.perm.transpos-code.b.goal.pf.5}%
\end{align}


But%
\begin{equation}
t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{p,i_{p}}=\underbrace{\left(
t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{p-1,i_{p-1}}\right)  }_{=\tau
}\circ t_{p,i_{p}}=\tau\circ t_{p,i_{p}}.
\label{sol.perm.transpos-code.b.goal.pf.4}%
\end{equation}


We have $\tau\left(  p\right)  =p$\ \ \ \ \footnote{\textit{Proof.} From
$\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in\left[  1\right]  \times\left[
2\right]  \times\cdots\times\left[  n\right]  $, we conclude that $i_{j}%
\in\left[  j\right]  $ for each $j\in\left[  n\right]  $. Thus, for each
$j\in\left[  p-1\right]  $, we have $i_{j}\in\left[  j\right]  $, so that
$i_{j}\leq j\leq p-1<p$. Therefore, for each $j\in\left[  p-1\right]  $, the
permutation $t_{j,i_{j}}$ leaves the number $p$ unchanged (since $p$ equals
neither $j$ nor $i_{j}$ (because $i_{j}\leq j<p$)). In other words, the
permutations $t_{1,i_{1}},t_{2,i_{2}},\ldots,t_{p-1,i_{p-1}}$ leave the number
$p$ unchanged. Hence, $\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ
t_{p-1,i_{p-1}}\right)  \left(  p\right)  =p$. In view of $\tau=t_{1,i_{1}%
}\circ t_{2,i_{2}}\circ\cdots\circ t_{p-1,i_{p-1}}$, this rewrites as
$\tau\left(  p\right)  =p$.}. Hence, Observation 2 (applied to $q=i_{p}$)
yields $z\left(  \tau\circ t_{p,i_{p}}\right)  =z\left(  \tau\right)  -1$. But
from (\ref{sol.perm.transpos-code.b.goal.pf.4}), we obtain%
\begin{align*}
z\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{p,i_{p}}\right)   &
=z\left(  \tau\circ t_{p,i_{p}}\right)  =z\left(  \tau\right)  -1\\
&  =n-p+\left\vert \left\{  k\in\left[  p\right]  \ \mid\ i_{k}=k\right\}
\right\vert \ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.perm.transpos-code.b.goal.pf.5})}\right)  .
\end{align*}
Thus, we have proven that (\ref{sol.perm.transpos-code.b.goal}) holds for $p$
in Case 2.

We thus know that (\ref{sol.perm.transpos-code.b.goal}) holds for $p$ (because
we have proven this in each of the two Cases 1 and 2). This completes the
induction step. Thus, (\ref{sol.perm.transpos-code.b.goal}) is proven.]

Now, apply (\ref{sol.perm.transpos-code.b.goal}) to $p=n$. The result is%
\[
z\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{n,i_{n}}\right)
=\underbrace{n-n}_{=0}+\left\vert \left\{  k\in\left[  n\right]  \ \mid
\ i_{k}=k\right\}  \right\vert =\left\vert \left\{  k\in\left[  n\right]
\ \mid\ i_{k}=k\right\}  \right\vert .
\]
In view of $\sigma=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{n,i_{n}}$,
this rewrites as $z\left(  \sigma\right)  =\left\vert \left\{  k\in\left[
n\right]  \ \mid\ i_{k}=k\right\}  \right\vert $. In other words, $z\left(
\sigma\right)  $ is the number of all $k\in\left[  n\right]  $ satisfying
$i_{k}=k$. This solves Exercise \ref{exe.perm.transpos-code} \textbf{(b)}.
\end{proof}

\subsection{Another partition identity}

Recall the following:

\begin{definition}
Let $n\in\mathbb{Z}$. A \textit{partition} of $n$ means a finite list $\left(
i_{1},i_{2},\ldots,i_{k}\right)  $ of positive integers satisfying%
\[
i_{1}\geq i_{2}\geq\cdots\geq i_{k}\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ i_{1}+i_{2}+\cdots+i_{k}=n.
\]

\end{definition}

\begin{exercise}
\label{exe.partitions.atleastp}Let $n\in\mathbb{N}$ and $p\in\mathbb{N}$. Let
$a$ be the number of all partitions $\left(  i_{1},i_{2},\ldots,i_{k}\right)
$ of $n$ satisfying $k\geq p$ and $i_{1}=i_{2}=\cdots=i_{p}$. Let $b$ be the
number of all nonempty partitions $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $
of $n$ such that all of $i_{1},i_{2},\ldots,i_{k}$ are $\geq p$. Prove that
$a=b$.
\end{exercise}

\begin{example}
Let $n=9$ and $p=3$. Then, the partitions counted by $a$ in Exercise
\ref{exe.partitions.atleastp} are%
\[
\left(  3,3,3\right)  ,\ \ \ \ \ \ \ \ \ \ \left(  2,2,2,2,1\right)
,\ \ \ \ \ \ \ \ \ \ \left(  2,2,2,1,1,1\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
1,1,1,1,1,1,1,1,1\right)  .
\]
Meanwhile, the partitions counted by $b$ in Exercise
\ref{exe.partitions.atleastp} are%
\[
\left(  9\right)  ,\ \ \ \ \ \ \ \ \ \ \left(  6,3\right)
,\ \ \ \ \ \ \ \ \ \ \left(  5,4\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
3,3,3\right)  .
\]
Thus, $a=4$ and $b=4$ in this case.
\end{example}

A full solution of Exercise \ref{exe.partitions.atleastp} can be found in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw8os-chen.pdf}{Angela
Chen's homework}. (This is also the solution I had in mind.)

Further reading on partitions includes:

\begin{itemize}
\item Herbert S. Wilf, \textit{Lectures on Integer Partitions}, 2009.\newline\url{https://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf}

\item George E. Andrews, Kimmo Eriksson, \textit{Integer Partitions},
Cambridge University Press 2004.

\item Igor Pak, \textit{Partition bijections, a survey}, Ramanujan Journal,
vol. 12 (2006), pp. 5--75.\newline\url{http://www.math.ucla.edu/~pak/papers/psurvey.pdf}
\end{itemize}

The Wikipedia articles on
\href{https://en.wikipedia.org/wiki/Partition_(number_theory)}{partitions},
the \href{https://en.wikipedia.org/wiki/Pentagonal_number_theorem}{pentagonal
number theorem} and
\href{https://en.wikipedia.org/wiki/Ramanujan's_congruences}{Ramanujan's
congruences} are also useful. That said, none of these is necessary for the
above exercise.

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[AleGhe14]{AleGhe14}\href{https://arxiv.org/abs/1403.5246v2}{Emily
Allen, Irina Gheorghiciuc, \textit{A weighted interpretation for the super
Catalan numbers}, arXiv:1403.5246v2.}

\bibitem[Gessel92]{Gessel92}Ira M. Gessel, \textit{Super Ballot Numbers},
Journal of Symbolic Computation, Volume 14, Issues 2--3, August-September
1992, pp. 179--194.\newline\url{https://doi.org/10.1016/0747-7171(92)90034-2}

\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[Han92]{Han92}Guo-Niu Han, \textit{Calcul Denertien}, PhD thesis
1991.\newline\url{http://emis.ams.org/journals/SLC/books/hanthese.html}
\end{thebibliography}


\end{document}