% The LaTeX below is mostly computer-generated (for reasons of speed); don't expect it to be very readable. Sorry.

\documentclass[paper=a4, fontsize=12pt]{scrartcl}%
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathrsfs}
\usepackage{sectsty}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{framed}
\usepackage{ifthen}
\usepackage{lastpage}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usepackage{verbatim}
\usepackage{ytableau}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, January 10, 2019 01:56:08}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\allsectionsfont{\centering \normalfont\scshape}
\setlength\parindent{20pt}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\Des}{\operatorname{Des}}
\newcommand{\des}{\operatorname{des}}
\newcommand{\OLN}{\operatorname{OLN}}
\newcommand{\cyc}{\operatorname{cyc}}
\newcommand{\rev}{\operatorname{rev}}
\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{\floor}[1]{\left\lfloor #1 \right\rfloor}
\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{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\euleri}[2]{\genfrac{\langle}{\rangle}{0pt}{0}{#1}{#2}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\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}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newcommand{\myname}{Darij Grinberg}
\newcommand{\myid}{00000000}
\newcommand{\mymail}{dgrinber@umn.edu}
\newcommand{\psetnumber}{2}
\ihead{Solutions to midterm \#\psetnumber}
\ohead{page \thepage\ of \pageref{LastPage}}
\ifoot{\myname, \myid}
\ofoot{\mymail}
\begin{document}

\title{ \normalfont {\normalsize \textsc{University of Minnesota, School of
Mathematics} }\\[25pt] \rule{\linewidth}{0.5pt} \\[0.4cm] {\huge Math 5705: Enumerative Combinatorics, }\\Fall 2018: Midterm 2 (preliminary version)\\\rule{\linewidth}{2pt} \\[0.5cm] }
\author{Darij Grinberg}
\maketitle

%----------------------------------------------------------------------------------------
%	NOTATIONS
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section*{Notations}

Here is a list of notations that are used in this homework:

\begin{itemize}
\item We shall use the Iverson bracket notation as well as the notation
$\left[  n \right]  $ for the set $\left\{  1, 2, \ldots, n \right\}  $ (when
$n \in\mathbb{Z}$).

\item If $n \in\mathbb{N}$, then $S_{n}$ denotes the set of all permutations
of $\left[  n \right]  $.

\item If $n \in\mathbb{N}$ and $\sigma\in S_{n}$, then:

\begin{itemize}
\item a \textit{descent} of the permutation $\sigma$ denotes an element $k
\in\left[  n-1 \right]  $ satisfying $\sigma\left(  k \right)  > \sigma\left(
k+1 \right)  $.

\item the \textit{descent set} $\operatorname{Des} \sigma$ of $\sigma$ is
defined as the set of all descents of $\sigma$.

\item the \textit{descent number} $\operatorname{des} \sigma$ of $\sigma$ is
defined as the number of all descents of $\sigma$ (that is,
$\operatorname{des} \sigma= \left|  \operatorname{Des} \sigma\right|  $).

\item the \textit{one-line notation} $\operatorname{OLN} \sigma$ of $\sigma$
is defined as the $n$-tuple $\left(  \sigma\left(  1 \right)  , \sigma\left(
2 \right)  , \ldots, \sigma\left(  n \right)  \right)  $. Often, this
$n$-tuple is written with square brackets, i.e., as $\left[  \sigma\left(  1
\right)  , \sigma\left(  2 \right)  , \ldots, \sigma\left(  n \right)
\right]  $.

\item for each $i \in\left[  n \right]  $, we define $\ell_{i}\left(
\sigma\right)  $ to be the number of all $j \in\left\{  i+1, i+2, \ldots, n
\right\}  $ satisfying $\sigma\left(  i \right)  > \sigma\left(  j \right)  $.

\item we say that $\sigma$ is \textit{312-avoiding} if there exist no three
elements $i, j, k \in\left[  n \right]  $ satisfying $i < j < k$ and
$\sigma\left(  j \right)  < \sigma\left(  k \right)  < \sigma\left(  i
\right)  $.

\item we say that $\sigma$ is \textit{321-avoiding} if there exist no three
elements $i, j, k \in\left[  n \right]  $ satisfying $i < j < k$ and
$\sigma\left(  k \right)  < \sigma\left(  j \right)  < \sigma\left(  i
\right)  $.
\end{itemize}

\item For any $n \in\mathbb{N}$ and any $i \in\left[  n-1 \right]  $, we let
$s_{i}$ denote the permutation in $S_{n}$ that swaps $i$ with $i+1$ while
leaving all other elements of $\left[  n \right]  $ unchanged. (This assumes
that $n$ is determined by the context.)

\item For any $n \in\mathbb{N}$ and any $k$ distinct elements $i_{1}, i_{2},
\ldots, i_{k}$ of $\left[  n \right]  $, we let $\operatorname{cyc}_{i_{1},
i_{2}, \ldots, i_{k}}$ be the permutation in $S_{n}$ that sends $i_{1}, i_{2},
\ldots, i_{k-1}, i_{k}$ to $i_{2}, i_{3}, \ldots, i_{k} , i_{1}$
(respectively) while leaving all the other elements of $\left[  n \right]  $
unchanged. (Again, this relies on $n$ being clear from the context.)

\item For any $n \in\mathbb{N}$ and $k \in\mathbb{N}$, the notation $%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n}{k}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n}{k}%
%EndExpansion
$ denotes the number of all permutations $\sigma\in S_{n}$ having exactly $k$
descents. This is called an \textit{Eulerian number}.

\item If $X$ is a set, and if $\alpha: X \to X$ and $\beta: X \to X$ are two
maps, then the composition $\alpha\circ\beta: X \to X$ is simply denoted by
$\alpha\beta$, and is called the \textit{product} of $\alpha$ and $\beta$.
This notation is used for permutations, in particular.

\item If $X$ is a set, if $k \in\mathbb{N}$, and if $f : X \to X$ is any map,
then the map $f^{k} : X \to X$ is defined by
\[
f^{k} = \underbrace{f \circ f \circ\cdots\circ f}_{k \text{ times}} =
\underbrace{f f \cdots f}_{k \text{ times}} .
\]
This map $f^{k}$ is called the \textit{$k$-th power of $f$} (or \textit{$k$-th
composition power of $f$}). These powers behave as one would expect as long as
you have only one map $f : X \to X$ (meaning that $f^{a+b} = f^{a} f^{b}$ and
$f^{ab} = \left(  f^{a} \right)  ^{b}$ for any $a, b \in\mathbb{N}$); but be
careful with several maps (e.g., two maps $f : X \to X$ and $g : X \to X$
don't always satisfy $\left(  fg \right)  ^{a} = f^{a} g^{a}$). See
\cite[Section 2.13.8]{detnotes} for details (where I write $f^{\circ k}$
instead of $f^{k}$).

\item If $X$ is a set, and if $f : X \to X$ is a map, then:

\begin{itemize}
\item we say that $f$ is an \textit{involution} if and only if $f^{2} =
\operatorname{id}$. (Note that every involution is automatically a permutation.)

\item we say that $f$ is \textit{fixed-point-free} if each $x \in X$ satisfies
$f\left(  x \right)  \neq x$ (that is, if $f$ has no fixed points). (Note that
the fixed-point-free permutations are precisely the derangements.)
\end{itemize}
\end{itemize}

%----------------------------------------------------------------------------------------
%	EXERCISE 1
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 1}

\subsection{Problem}

Let $n$ and $k$ be positive integers.

For each $i \in\left\{  0, 1, \ldots, n-1 \right\}  $ and $\tau\in S_{n-1}$,
we let $\tau^{i\_}\in S_{n}$ be the permutation such that
%To get an underscore, you need to write "\_", not just "_".
%The latter would give you a subscript (or an error message).%
\[
\operatorname{OLN} \left(  \tau^{i\_} \right)  = \left(  \tau\left(  1
\right)  , \tau\left(  2 \right)  , \ldots, \tau\left(  i \right)  , n,
\tau\left(  i+1 \right)  , \tau\left(  i+2 \right)  , \ldots, \tau\left(  n-1
\right)  \right)
\]
(that is, $\operatorname{OLN} \left(  \tau^{i\_} \right)  $ is obtained from
$\operatorname{OLN} \tau$ by inserting an $n$ right after the $i$-th entry).

\begin{enumerate}
\item[\textbf{(a)}] Prove that each $i \in\left\{  0, 1, \ldots, n-1 \right\}
$ and $\tau\in S_{n-1}$ satisfy
\begin{align*}
&  \left[  \operatorname{des} \left(  \tau^{i\_} \right)  = k \right] \\
&  = \left[  \operatorname{des} \tau= k-1 \text{ and } \tau\left(  i \right)
< \tau\left(  i+1 \right)  \right]  + \left[  \operatorname{des} \tau= k
\text{ and } \tau\left(  i \right)  > \tau\left(  i+1 \right)  \right]  ,
\end{align*}
where we set $\tau\left(  0 \right)  = 0$ and $\tau\left(  n \right)  = 0$.

\item[\textbf{(b)}] Prove that the map
\begin{align*}
\left\{  0, 1, \ldots, n-1 \right\}  \times S_{n-1}  &  \to S_{n},\\
\left(  i , \tau\right)   &  \mapsto\tau^{i\_}%
\end{align*}
is a bijection.

\item[\textbf{(c)}] Prove that
\[%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n}{k}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n}{k}%
%EndExpansion
=\left(  k+1\right)
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n-1}{k}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k}%
%EndExpansion
+\left(  n-k\right)
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n-1}{k-1}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k-1}%
%EndExpansion
.
\]

\end{enumerate}

\subsection{Solution sketch}

\textbf{(a)} Let $i\in\left\{  0,1,\ldots,n-1\right\}  $ and $\tau\in S_{n-1}%
$. Set $\tau\left(  0\right)  =0$ and $\tau\left(  n\right)  =0$.

Let us first recall some definitions: If $\sigma\in S_{m}$ is a permutation
for some $m\in\mathbb{N}$, then the descents of $\sigma$ are the numbers
$g\in\left[  m-1\right]  $ satisfying $\sigma\left(  g\right)  >\sigma\left(
g+1\right)  $; in other words, the descents of $\sigma$ are the positions at
which an entry in $\operatorname*{OLN}\sigma$ is followed by a smaller entry.
Furthermore, $\operatorname*{des}\sigma$ is the number of these descents.

Now, we have%
\begin{align*}
\operatorname{OLN}\tau &  =\left(  \tau\left(  1\right)  ,\tau\left(
2\right)  ,\ldots,\tau\left(  i\right)  ,\tau\left(  i+1\right)  ,\tau\left(
i+2\right)  ,\ldots,\tau\left(  n-1\right)  \right)  \qquad\text{and}\\
\operatorname{OLN}\left(  \tau^{i\_}\right)   &  =\left(  \tau\left(
1\right)  ,\tau\left(  2\right)  ,\ldots,\tau\left(  i\right)  ,n,\tau\left(
i+1\right)  ,\tau\left(  i+2\right)  ,\ldots,\tau\left(  n-1\right)  \right)
\end{align*}
(by the definition of $\tau^{i\_}$). Thus, the descents of $\tau^{i\_}$ can be
characterized as follows:

\begin{itemize}
\item Any number $g\in\left[  i-1\right]  $ is a descent of $\tau^{i\_}$ if
and only if it is a descent of $\tau$ (because the first $i$ entries of
$\operatorname{OLN}\left(  \tau^{i\_}\right)  $ are precisely the first $i$
entries of $\operatorname{OLN}\tau$).

\item The number $i$ is never a descent of $\tau^{i\_}$ (since $\tau\left(
i\right)  >n$ never holds).

\item If $i\neq n-1$, then the number $i+1$ is always a descent of $\tau
^{i\_}$ (since $n>\tau\left(  i+1\right)  $ always holds).

\item Any number $g\in\left\{  i+2,i+3,\ldots,n-1\right\}  $ is a descent of
$\tau^{i\_}$ if and only if $g-1$ is a descent of $\tau$ (because the last
$n-1-i$ entries of $\operatorname{OLN}\left(  \tau^{i\_}\right)  $ are
precisely the last $n-1-i$ entries of $\operatorname{OLN}\tau$).
\end{itemize}

Thus, when we go from $\tau$ to $\tau^{i\_}$, the descents are
\textquotedblleft more or less\textquotedblright\ preserved in the sense that

\begin{itemize}
\item some of the descents (namely, those that are larger than $i$) get
shifted by $1$;

\item the descent $i$ is lost (if $i$ was a descent of $\tau$ to begin with); and

\item a descent $i+1$ is created if $i\neq n-1$.
\end{itemize}

Hence, the total number of descents decreases by $1$ if $i$ was a descent of
$\tau$, and furthermore increases by $1$ if $i\neq n-1$. In other words,%
\begin{align}
\operatorname*{des}\left(  \tau^{i\_}\right)   &  =\operatorname*{des}%
\tau-\underbrace{\left[  i\text{ is a descent of }\tau\right]  }_{=\left[
i\in\operatorname*{Des}\tau\right]  }+\left[  i\neq n-1\right]
=\operatorname*{des}\tau-\left[  i\in\operatorname*{Des}\tau\right]  +\left[
i\neq n-1\right] \nonumber\\
&  =\operatorname*{des}\tau+\left[  i\neq n-1\right]  -\left[  i\in
\operatorname*{Des}\tau\right]  . \label{sol.perm.eulerian.rec.a.3}%
\end{align}
But it is easy to see that
\begin{equation}
\left[  i\neq n-1\right]  -\left[  i\in\operatorname*{Des}\tau\right]
=\left[  \tau\left(  i\right)  <\tau\left(  i+1\right)  \right]  .
\label{sol.perm.eulerian.rec.a.4}%
\end{equation}
\ \ \ \ 

[\textit{Proof of \eqref{sol.perm.eulerian.rec.a.4}:} In order to prove
\eqref{sol.perm.eulerian.rec.a.4}, we can distinguish between the following
three cases:

\begin{itemize}
\item \textit{Case 1:} We have $i\neq n-1$ and $\tau\left(  i\right)
<\tau\left(  i+1\right)  $.

\item \textit{Case 2:} We have $i\neq n-1$ and $\tau\left(  i\right)
>\tau\left(  i+1\right)  $.

\item \textit{Case 3:} We have $i=n-1$.
\end{itemize}

(No other cases can occur, because $\tau\left(  i\right)  \neq\tau\left(
i+1\right)  $.)

In Case 1, the equality \eqref{sol.perm.eulerian.rec.a.4} boils down to
$1-0=1$ (since $\tau\left(  i\right)  <\tau\left(  i+1\right)  $ yields
$i\notin\operatorname*{Des}\tau$), which is true.

In Case 2, the equality \eqref{sol.perm.eulerian.rec.a.4} boils down to
$1-1=0$ (since $\tau\left(  i\right)  >\tau\left(  i+1\right)  $ yields
$i\in\operatorname*{Des}\tau$), which is true.

In Case 3, the equality \eqref{sol.perm.eulerian.rec.a.4} boils down to
$0-0=0$ (since $i=n-1$ yields $n=i+1$ and thus $\tau\left(  i\right)
>0=\tau\left(  \underbrace{n}_{=i+1}\right)  =\tau\left(  i+1\right)  $),
which is true.

Thus, the equality \eqref{sol.perm.eulerian.rec.a.4} is proven in all three cases.]

Now, \eqref{sol.perm.eulerian.rec.a.3} becomes%
\[
\operatorname*{des}\left(  \tau^{i\_}\right)  =\operatorname*{des}%
\tau+\underbrace{\left[  i\neq n-1\right]  -\left[  i\in\operatorname*{Des}%
\tau\right]  }_{\substack{=\left[  \tau\left(  i\right)  <\tau\left(
i+1\right)  \right]  \\\text{(by \eqref{sol.perm.eulerian.rec.a.4})}%
}}=\operatorname*{des}\tau+\left[  \tau\left(  i\right)  <\tau\left(
i+1\right)  \right]  .
\]
Hence,%
\begin{align*}
&  \left[  \operatorname{des}\left(  \tau^{i\_}\right)  =k\right] \\
&  =\left[  \operatorname*{des}\tau+\left[  \tau\left(  i\right)  <\tau\left(
i+1\right)  \right]  =k\right] \\
&  =\left[  \tau\left(  i\right)  <\tau\left(  i+1\right)  \text{ and
}\operatorname*{des}\tau+\underbrace{\left[  \tau\left(  i\right)
<\tau\left(  i+1\right)  \right]  }_{\substack{=1\\\text{(since }\tau\left(
i\right)  <\tau\left(  i+1\right)  \text{)}}}=k\right] \\
&  \qquad+\left[  \tau\left(  i\right)  >\tau\left(  i+1\right)  \text{ and
}\operatorname*{des}\tau+\underbrace{\left[  \tau\left(  i\right)
<\tau\left(  i+1\right)  \right]  }_{\substack{=0\\\text{(since }\tau\left(
i\right)  >\tau\left(  i+1\right)  \text{)}}}=k\right] \\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{since we always have either }\tau\left(  i\right)  <\tau\left(
i+1\right)  \text{ or }\tau\left(  i\right)  >\tau\left(  i+1\right)
\text{,}\\
\text{but never both at once}%
\end{array}
\right) \\
&  =\underbrace{\left[  \tau\left(  i\right)  <\tau\left(  i+1\right)  \text{
and }\operatorname*{des}\tau+1=k\right]  }_{\substack{=\left[  \tau\left(
i\right)  <\tau\left(  i+1\right)  \text{ and }\operatorname*{des}%
\tau=k-1\right]  \\=\left[  \operatorname{des}\tau=k-1\text{ and }\tau\left(
i\right)  <\tau\left(  i+1\right)  \right]  }}+\underbrace{\left[  \tau\left(
i\right)  >\tau\left(  i+1\right)  \text{ and }\operatorname*{des}%
\tau=k\right]  }_{=\left[  \operatorname{des}\tau=k\text{ and }\tau\left(
i\right)  >\tau\left(  i+1\right)  \right]  }\\
&  =\left[  \operatorname{des}\tau=k-1\text{ and }\tau\left(  i\right)
<\tau\left(  i+1\right)  \right]  +\left[  \operatorname{des}\tau=k\text{ and
}\tau\left(  i\right)  >\tau\left(  i+1\right)  \right]  .
\end{align*}
This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} The map%
\begin{align*}
\left\{  0,1,\ldots,n-1\right\}  \times S_{n-1}  &  \rightarrow S_{n},\\
\left(  i,\tau\right)   &  \mapsto\tau^{i\_}%
\end{align*}
is invertible. In fact, its inverse is the map that sends each $\sigma\in
S_{n}$ to the pair $\left(  i,\tau\right)  \in\left\{  0,1,\ldots,n-1\right\}
\times S_{n-1}$, where $i=\sigma^{-1}\left(  n\right)  -1$ and where $\tau\in
S_{n-1}$ is (uniquely) determined by%
\[
\operatorname{OLN}\tau=\left(  \sigma\left(  1\right)  ,\sigma\left(
2\right)  ,\ldots,\sigma\left(  i\right)  ,\sigma\left(  i+2\right)
,\sigma\left(  i+3\right)  ,\ldots,\sigma\left(  n\right)  \right)  .
\]
(Proving this is straightforward.)

\bigskip

\textbf{(c)} We WLOG assume that $n\neq1$ (since the proof in the case $n=1$
is straightforward). Thus, $n-1\neq0$ and $n>1$.

The definition of $%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n}{k}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n}{k}%
%EndExpansion
$ yields%
\begin{align}%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n}{k}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n}{k}%
%EndExpansion
&  =\left(  \text{the number of all permutations }\sigma\in S_{n}\text{ having
exactly }k\text{ descents}\right) \nonumber\\
&  =\left(  \text{the number of all permutations }\sigma\in S_{n}\text{ such
that }\operatorname*{des}\sigma=k\right) \nonumber\\
&  =\left\vert \left\{  \sigma\in S_{n}\ \mid\ \operatorname*{des}%
\sigma=k\right\}  \right\vert \nonumber\\
&  =\sum_{\sigma\in S_{n}}\left[  \operatorname*{des}\sigma=k\right]
\label{sol.perm.eulerian.rec.c.nk}%
\end{align}
(since%

\begin{align*}
\sum_{\sigma\in S_{n}}\left[  \operatorname*{des}\sigma=k\right]   &
=\sum_{\substack{\sigma\in S_{n};\\\operatorname*{des}\sigma=k}%
}\underbrace{\left[  \operatorname*{des}\sigma=k\right]  }%
_{\substack{=1\\\text{(since }\operatorname*{des}\sigma=k\text{)}}%
}+\sum_{\substack{\sigma\in S_{n};\\\operatorname*{des}\sigma\neq
k}}\underbrace{\left[  \operatorname*{des}\sigma=k\right]  }%
_{\substack{=0\\\text{(since }\operatorname*{des}\sigma\neq k\text{)}}%
}=\sum_{\substack{\sigma\in S_{n};\\\operatorname*{des}\sigma=k}%
}1+\underbrace{\sum_{\substack{\sigma\in S_{n};\\\operatorname*{des}\sigma\neq
k}}0}_{=0}\\
&  =\sum_{\substack{\sigma\in S_{n};\\\operatorname*{des}\sigma=k}%
}1=\left\vert \left\{  \sigma\in S_{n}\ \mid\ \operatorname*{des}%
\sigma=k\right\}  \right\vert \cdot1=\left\vert \left\{  \sigma\in S_{n}%
\ \mid\ \operatorname*{des}\sigma=k\right\}  \right\vert
\end{align*}
). The same argument (applied to $n-1$ instead of $n$) yields%
\begin{equation}%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n-1}{k}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k}%
%EndExpansion
=\sum_{\sigma\in S_{n-1}}\left[  \operatorname*{des}\sigma=k\right]
=\sum_{\tau\in S_{n-1}}\left[  \operatorname*{des}\tau=k\right]  .
\label{sol.perm.eulerian.rec.c.n-1k}%
\end{equation}
The same argument (applied to $k-1$ instead of $k$) yields%
\begin{equation}%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n-1}{k-1}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k-1}%
%EndExpansion
=\sum_{\tau\in S_{n-1}}\left[  \operatorname*{des}\tau=k-1\right]  .
\label{sol.perm.eulerian.rec.c.n-1k-1}%
\end{equation}


Now, \eqref{sol.perm.eulerian.rec.c.nk} becomes%
\begin{align}%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n}{k}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n}{k}%
%EndExpansion
&  =\sum_{\sigma\in S_{n}}\left[  \operatorname*{des}\sigma=k\right]
=\underbrace{\sum_{\left(  i,\tau\right)  \in\left\{  0,1,\ldots,n-1\right\}
\times S_{n-1}}}_{=\sum_{\tau\in S_{n-1}}\sum_{i\in\left\{  0,1,\ldots
,n-1\right\}  }}\ \ \ \underbrace{\left[  \operatorname*{des}\left(
\tau^{i\_}\right)  =k\right]  }_{\substack{=\left[  \operatorname{des}%
\tau=k-1\text{ and }\tau\left(  i\right)  <\tau\left(  i+1\right)  \right]
+\left[  \operatorname{des}\tau=k\text{ and }\tau\left(  i\right)
>\tau\left(  i+1\right)  \right]  \\\text{(by part \textbf{(a)} of the
exercise)}}}\nonumber\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have substituted }\tau^{i\_}\text{ for }\sigma\text{ in the
sum,}\\
\text{since the map }\left\{  0,1,\ldots,n-1\right\}  \times S_{n-1}%
\rightarrow S_{n},\ \left(  i,\tau\right)  \mapsto\tau^{i\_}\\
\text{is a bijection (by part \textbf{(b)} of the exercise)}%
\end{array}
\right) \nonumber\\
&  =\sum_{\tau\in S_{n-1}}\sum_{i\in\left\{  0,1,\ldots,n-1\right\}  }\left(
\left[  \operatorname{des}\tau=k-1\text{ and }\tau\left(  i\right)
<\tau\left(  i+1\right)  \right]  +\left[  \operatorname{des}\tau=k\text{ and
}\tau\left(  i\right)  >\tau\left(  i+1\right)  \right]  \right) \nonumber\\
&  =\sum_{\tau\in S_{n-1}}\sum_{i\in\left\{  0,1,\ldots,n-1\right\}
}\underbrace{\left[  \operatorname{des}\tau=k-1\text{ and }\tau\left(
i\right)  <\tau\left(  i+1\right)  \right]  }_{=\left[  \operatorname*{des}%
\tau=k-1\right]  \left[  \tau\left(  i\right)  <\tau\left(  i+1\right)
\right]  }\nonumber\\
&  \qquad+\sum_{\tau\in S_{n-1}}\sum_{i\in\left\{  0,1,\ldots,n-1\right\}
}\underbrace{\left[  \operatorname{des}\tau=k\text{ and }\tau\left(  i\right)
>\tau\left(  i+1\right)  \right]  }_{=\left[  \operatorname*{des}%
\tau=k-1\right]  \left[  \tau\left(  i\right)  >\tau\left(  i+1\right)
\right]  }\nonumber\\
&  =\sum_{\tau\in S_{n-1}}\left[  \operatorname*{des}\tau=k-1\right]
\sum_{i\in\left\{  0,1,\ldots,n-1\right\}  }\left[  \tau\left(  i\right)
<\tau\left(  i+1\right)  \right] \nonumber\\
&  \qquad+\sum_{\tau\in S_{n-1}}\left[  \operatorname*{des}\tau=k\right]
\sum_{i\in\left\{  0,1,\ldots,n-1\right\}  }\left[  \tau\left(  i\right)
>\tau\left(  i+1\right)  \right]  . \label{sol.perm.eulerian.rec.c.5}%
\end{align}
But each $\tau\in S_{n-1}$ satisfies%
\begin{align*}
&  \sum_{i\in\left\{  0,1,\ldots,n-1\right\}  }\left[  \tau\left(  i\right)
<\tau\left(  i+1\right)  \right] \\
&  =\underbrace{\left[  \tau\left(  0\right)  <\tau\left(  1\right)  \right]
}_{\substack{=1\\\text{(since }\tau\left(  0\right)  =0<\tau\left(  1\right)
\text{)}}}+\sum_{i\in\left[  n-2\right]  }\underbrace{\left[  \tau\left(
i\right)  <\tau\left(  i+1\right)  \right]  }_{\substack{=\left[  \text{not
}\tau\left(  i\right)  \geq\tau\left(  i+1\right)  \right]  \\=\left[
\text{not }\tau\left(  i\right)  >\tau\left(  i+1\right)  \right]
\\\text{(since }\tau\left(  i\right)  \neq\tau\left(  i+1\right)  \text{)}%
}}+\underbrace{\left[  \tau\left(  n-1\right)  <\tau\left(  n\right)  \right]
}_{\substack{=0\\\text{(since }\tau\left(  n-1\right)  >0=\tau\left(
n\right)  \text{)}}}\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split off the addends for }i=0\text{ and for }i=n-1\\
\text{from the sum (and these are indeed two distinct addends,}\\
\text{since }n-1\neq0\text{)}%
\end{array}
\right) \\
&  =1+\underbrace{\sum_{i\in\left[  n-2\right]  }\left[  \text{not }%
\tau\left(  i\right)  >\tau\left(  i+1\right)  \right]  }_{=\left\vert
\left\{  i\in\left[  n-2\right]  \ \mid\ \text{not }\tau\left(  i\right)
>\tau\left(  i+1\right)  \right\}  \right\vert }\\
&  =1+\left\vert \underbrace{\left\{  i\in\left[  n-2\right]  \ \mid
\ \text{not }\tau\left(  i\right)  >\tau\left(  i+1\right)  \right\}
}_{\substack{=\left[  n-2\right]  \setminus\operatorname*{Des}\tau
\\\text{(since }\tau\in S_{n-1}\text{ and thus }\operatorname*{Des}%
\tau=\left\{  i\in\left[  n-2\right]  \ \mid\ \tau\left(  i\right)
>\tau\left(  i+1\right)  \right\}  \text{)}}}\right\vert
=1+\underbrace{\left\vert \left[  n-2\right]  \setminus\operatorname*{Des}%
\tau\right\vert }_{\substack{=\left(  n-2\right)  -\left\vert
\operatorname*{Des}\tau\right\vert \\\text{(since }\operatorname*{Des}%
\tau\subseteq\left[  n-2\right]  \text{)}}}\\
&  =1+\left(  n-2\right)  -\left\vert \operatorname*{Des}\tau\right\vert
=n-1-\underbrace{\left\vert \operatorname*{Des}\tau\right\vert }%
_{=\operatorname*{des}\tau}=n-1-\operatorname*{des}\tau
\end{align*}
and%
\begin{align*}
&  \sum_{i\in\left\{  0,1,\ldots,n-1\right\}  }\left[  \tau\left(  i\right)
>\tau\left(  i+1\right)  \right] \\
&  =\underbrace{\left[  \tau\left(  0\right)  >\tau\left(  1\right)  \right]
}_{\substack{=0\\\text{(since }\tau\left(  0\right)  =0<\tau\left(  1\right)
\text{)}}}+\underbrace{\sum_{i\in\left[  n-2\right]  }\left[  \tau\left(
i\right)  >\tau\left(  i+1\right)  \right]  }_{=\left\vert \left\{
i\in\left[  n-2\right]  \ \mid\ \tau\left(  i\right)  >\tau\left(  i+1\right)
\right\}  \right\vert }+\underbrace{\left[  \tau\left(  n-1\right)
>\tau\left(  n\right)  \right]  }_{\substack{=1\\\text{(since }\tau\left(
n-1\right)  >0=\tau\left(  n\right)  \text{)}}}\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split off the addends for }i=0\text{ and for }i=n-1\\
\text{from the sum (and these are indeed two distinct addends,}\\
\text{since }n-1\neq0\text{)}%
\end{array}
\right) \\
&  =1+\left\vert \underbrace{\left\{  i\in\left[  n-2\right]  \ \mid
\ \tau\left(  i\right)  >\tau\left(  i+1\right)  \right\}  }%
_{\substack{=\operatorname*{Des}\tau\\\text{(since }\tau\in S_{n-1}\text{)}%
}}\right\vert =1+\underbrace{\left\vert \operatorname*{Des}\tau\right\vert
}_{=\operatorname*{des}\tau}=1+\operatorname*{des}\tau=\operatorname*{des}%
\tau+1.
\end{align*}
Hence, \eqref{sol.perm.eulerian.rec.c.5} becomes%
\begin{align*}%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n}{k}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n}{k}%
%EndExpansion
&  =\sum_{\tau\in S_{n-1}}\left[  \operatorname*{des}\tau=k-1\right]
\underbrace{\sum_{i\in\left\{  0,1,\ldots,n-1\right\}  }\left[  \tau\left(
i\right)  <\tau\left(  i+1\right)  \right]  }_{=n-1-\operatorname*{des}\tau}\\
&  \qquad+\sum_{\tau\in S_{n-1}}\left[  \operatorname*{des}\tau=k\right]
\underbrace{\sum_{i\in\left\{  0,1,\ldots,n-1\right\}  }\left[  \tau\left(
i\right)  >\tau\left(  i+1\right)  \right]  }_{=\operatorname*{des}\tau+1}\\
&  =\sum_{\tau\in S_{n-1}}\underbrace{\left[  \operatorname*{des}%
\tau=k-1\right]  \cdot\left(  n-1-\operatorname*{des}\tau\right)
}_{\substack{=\left[  \operatorname*{des}\tau=k-1\right]  \cdot\left(
n-1-\left(  k-1\right)  \right)  \\\text{(indeed, this equality clearly
holds}\\\text{when }\operatorname*{des}\tau=k-1\text{; but when }%
\operatorname*{des}\tau\neq k-1\text{,}\\\text{it simply boils down to
}0=0\text{)}}}+\sum_{\tau\in S_{n-1}}\underbrace{\left[  \operatorname*{des}%
\tau=k\right]  \cdot\left(  \operatorname*{des}\tau+1\right)  }%
_{\substack{=\left[  \operatorname*{des}\tau=k\right]  \cdot\left(
k+1\right)  \\\text{(indeed, this equality clearly holds}\\\text{when
}\operatorname*{des}\tau=k\text{; but when }\operatorname*{des}\tau\neq
k\text{,}\\\text{it simply boils down to }0=0\text{)}}}\\
&  =\underbrace{\sum_{\tau\in S_{n-1}}\left[  \operatorname*{des}%
\tau=k-1\right]  }_{\substack{=%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n-1}{k-1}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k-1}%
%EndExpansion
\\\text{(by \eqref{sol.perm.eulerian.rec.c.n-1k-1})}}}\cdot\underbrace{\left(
n-1-\left(  k-1\right)  \right)  }_{=n-k}+\underbrace{\sum_{\tau\in S_{n-1}%
}\left[  \operatorname*{des}\tau=k\right]  }_{\substack{=%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n-1}{k}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k}%
%EndExpansion
\\\text{(by \eqref{sol.perm.eulerian.rec.c.n-1k})}}}\cdot\left(  k+1\right) \\
&  =%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n-1}{k-1}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k-1}%
%EndExpansion
\cdot\left(  n-k\right)  +%
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n-1}{k}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k}%
%EndExpansion
\cdot\left(  k+1\right)  =\left(  k+1\right)
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n-1}{k}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k}%
%EndExpansion
+\left(  n-k\right)
%TCIMACRO{\QDATOPD{\langle}{\rangle}{n-1}{k-1}}%
%BeginExpansion
\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k-1}%
%EndExpansion
.
\end{align*}


This solves part \textbf{(c)} of the exercise.

%----------------------------------------------------------------------------------------
%	EXERCISE 2
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 2}

\subsection{Problem}

Let $n \in\mathbb{N}$ and $\sigma\in S_{n}$. For each $i \in\left[  n \right]
$, let
\[
a_{i} = \operatorname{cyc}_{i^{\prime}, i^{\prime}-1, \ldots, i} =
s_{i^{\prime}-1} s_{i^{\prime}-2} \cdots s_{i} \in S_{n} , \qquad\text{where }
i^{\prime}= i + \ell_{i} \left(  \sigma\right)  .
\]


Prove that $\sigma= a_{1} a_{2} \cdots a_{n}$.

[\textbf{Hint:} Prove, \textquotedblleft more generally\textquotedblright,
that if $j\in\left\{  0,1,\ldots,n\right\}  $ is such that $1,2,\ldots,j$ are
fixed points of $\sigma$, then $\sigma=a_{j+1}a_{j+2}\cdots a_{n}$.]

\subsection{Remark}

This exercise shows a direct way of expressing every $\sigma\in S_{n}$ as a
product of $\ell\left(  \sigma\right)  $ many simple transpositions (indeed,
it represents $\sigma$ as the product $a_{1}a_{2}\cdots a_{n}$, but we can
then rewrite each $a_{i}$ as $s_{i^{\prime}-1}s_{i^{\prime}-2}\cdots s_{i}$,
which turns $a_{1}a_{2}\cdots a_{n}$ into a product of $\ell_{1}\left(
\sigma\right)  +\ell_{2}\left(  \sigma\right)  +\cdots+\ell_{n}\left(
\sigma\right)  =\ell\left(  \sigma\right)  $ many simple transpositions). This
way is occasionally stated visually in terms of the Rothe diagram of $\sigma$
(see, for example,
\url{https://sumidiot.blogspot.com/2008/05/rothe-diagram.html} or
\cite[Corollary 11.3.5]{Kerber99}).

The exercise also appears in \cite[Exercise 5.21 \textbf{(c)}]{detnotes}. The
solution I give below follows the same strategy as the solution given in
\cite{detnotes}, but differs in the execution.

\subsection{Solution sketch}

Forget that we fixed $n$ and $\sigma$. First, we need the following definition:

\begin{definition}
Let $T$ and $Q$ be two subsets of $\mathbb{Z}$. Let $f:T\rightarrow Q$ be any
map. Then, we say that the map $f$ is \textit{strictly increasing} if every
two elements $t_{1}$ and $t_{2}$ of $T$ satisfying $t_{1}<t_{2}$ satisfy
$f\left(  t_{1}\right)  <f\left(  t_{2}\right)  $. (Thus, if $T=\left\{
i_{1}<i_{2}<\cdots<i_{k}\right\}  $ is a finite set, then $f$ is strictly
increasing if and only if $f\left(  i_{1}\right)  <f\left(  i_{2}\right)
<\cdots<f\left(  i_{k}\right)  $.) It is easy to see that if $f$ is strictly
increasing, then for any two elements $t_{1}$ and $t_{2}$ of $T$, we have the
logical equivalence%
\[
\left(  t_{1}>t_{2}\right)  \ \Longleftrightarrow\ \left(  f\left(
t_{1}\right)  >f\left(  t_{2}\right)  \right)  .
\]

\end{definition}

Note that this notion of \textquotedblleft strictly
increasing\textquotedblright\ is defined for maps on arbitrary subsets of
$\mathbb{Z}$, not just on intervals.

\begin{example}
Let $\pi\in S_{5}$ be the permutation given in one-line notation as $\left[
2,1,4,3,5\right]  $. Then, $\pi$ itself is not strictly increasing (since, for
example, $1<2$ but we don't have $\pi\left(  1\right)  <\pi\left(  2\right)
$). But its restriction $\pi\mid_{\left\{  1,4,5\right\}  }:\left\{
1,4,5\right\}  \rightarrow\left[  5\right]  $ is strictly increasing (since
the images of $1,4,5$ under $\pi$ are $2,3,5$, and these satisfy $2<3<5$).
\end{example}

\begin{lemma}
\label{lem.perm.lehmer.cyc.strinc}Let $n\in\mathbb{N}$. Let $a,b\in\left[
n\right]  $ satisfy $a\leq b$. Let $\alpha=\operatorname*{cyc}%
\nolimits_{a,a+1,\ldots,b}\in S_{n}$. Let $U$ be a subset of $\left[
n\right]  $ such that $b\notin U$. Then, the restriction $\alpha\mid
_{U}:U\rightarrow\left[  n\right]  $ is strictly increasing.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.perm.lehmer.cyc.strinc}.]We have $U\subseteq\left[
n\right]  \setminus\left\{  b\right\}  $ (since $U$ is a subset of $\left[
n\right]  $ such that $b\notin U$). Thus, the restriction $\alpha\mid
_{U}:U\rightarrow\left[  n\right]  $ is a restriction of the restriction
$\alpha\mid_{\left[  n\right]  \setminus\left\{  b\right\}  }:\left[
n\right]  \setminus\left\{  b\right\}  \rightarrow\left[  n\right]  $ (because
if $X$, $Y$ and $Z$ are three sets such that $X\subseteq Y\subseteq Z$, and if
$f$ is a map from $Z$, then $f\mid_{X}=\left(  f\mid_{Y}\right)  \mid_{X}$).
Note that a restriction of a strictly increasing map to a subset is always
strictly increasing.

But $\alpha=\operatorname*{cyc}\nolimits_{a,a+1,\ldots,b}$. Hence, the map
$\alpha$ sends the elements%
\[%
\begin{array}
[c]{ccccccccccccc}
& 1, & 2, & \ldots, & a-1, & a, & a+1, & \ldots, & b-1, & b+1, & b+2, &
\ldots, & n\\
\text{to } & 1, & 2, & \ldots, & a-1, & a+1, & a+2, & \ldots, & b, & b+1, &
b+2, & \ldots, & n,
\end{array}
\]
respectively. In other words, the map $\alpha$ sends the elements
$1,2,\ldots,b-1,b+1,b+2,\ldots,n$ to $1,2,\ldots,a-1,a+1,a+2,\ldots,n$ in this
order. Thus, its restriction $\alpha\mid_{\left[  n\right]  \setminus\left\{
b\right\}  }:\left[  n\right]  \setminus\left\{  b\right\}  \rightarrow\left[
n\right]  $ is strictly increasing (since $1<2<\cdots<a-1<a+1<a+2<\cdots<n$).
Hence, the restriction $\alpha\mid_{U}:U\rightarrow\left[  n\right]  $ is
strictly increasing as well (since it is a restriction of the restriction
$\alpha\mid_{\left[  n\right]  \setminus\left\{  b\right\}  }:\left[
n\right]  \setminus\left\{  b\right\}  \rightarrow\left[  n\right]  $). Hence,
Lemma \ref{lem.perm.lehmer.cyc.strinc} is proven.
\end{proof}

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

\textbf{(a)} We have $i+\ell_{i}\left(  \sigma\right)  \in\left[  n\right]  $
and $i+\ell_{i}\left(  \sigma\right)  \geq i$.

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

\textbf{(c)} Let $\alpha\in S_{n}$ be a further permutation such that the
restriction $\alpha\mid_{\sigma\left(  \left\{  i,i+1,\ldots,n\right\}
\right)  }:\sigma\left(  \left\{  i,i+1,\ldots,n\right\}  \right)
\rightarrow\left[  n\right]  $ is strictly increasing. Let $\tau=\alpha
\circ\sigma$. Then, $\ell_{i}\left(  \tau\right)  =\ell_{i}\left(
\sigma\right)  $.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.perm.lehmer.iplusli}.]Recall that $\ell_{i}\left(
\sigma\right)  $ was defined as the number of all $j\in\left\{  i+1,i+2,\ldots
,n\right\}  $ satisfying $\sigma\left(  i\right)  >\sigma\left(  j\right)  $.
Thus, $\ell_{i}\left(  \sigma\right)  $ is $\leq$ to the number of
\textbf{all} $j\in\left\{  i+1,i+2,\ldots,n\right\}  $. In other words,
$\ell_{i}\left(  \sigma\right)  $ is $\leq$ to $n-i$ (since the number of all
$j\in\left\{  i+1,i+2,\ldots,n\right\}  $ is $n-i$). In other words, $\ell
_{i}\left(  \sigma\right)  \leq n-i$, so that $i+\ell_{i}\left(
\sigma\right)  \leq n$ and thus $i+\ell_{i}\left(  \sigma\right)  \in\left[
n\right]  $ (because $i+\underbrace{\ell_{i}\left(  \sigma\right)  }_{\geq
0}\geq i\geq1$). Moreover, $i+\underbrace{\ell_{i}\left(  \sigma\right)
}_{\geq0}\geq i$. This proves Lemma \ref{lem.perm.lehmer.iplusli} \textbf{(a)}.

\textbf{(b)} This is \cite[Lemma 5.48 \textbf{(b)}]{detnotes}; see
\cite[solution to Exercise 5.18]{detnotes} for a detailed proof. Here is a
sketch: The definition of $\ell_{i}\left(  \sigma\right)  $ rewrites as%
\[
\ell_{i}\left(  \sigma\right)  =\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 .
\]
But there is a bijection $\left\{  j\in\left\{  i+1,i+2,\ldots,n\right\}
\ \mid\ \sigma\left(  i\right)  >\sigma\left(  j\right)  \right\}
\rightarrow\left[  \sigma\left(  i\right)  -1\right]  \setminus\sigma\left(
\left[  i-1\right]  \right)  $ (namely, the map sending each $j$ to
$\sigma\left(  j\right)  $); so we have%
\[
\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
=\left\vert \left[  \sigma\left(  i\right)  -1\right]  \setminus\sigma\left(
\left[  i-1\right]  \right)  \right\vert .
\]
Combining these two equations, we obtain Lemma \ref{lem.perm.lehmer.iplusli}
\textbf{(b)}.

\textbf{(c)} Recall that $\ell_{i}\left(  \sigma\right)  $ was defined as the
number of all $j\in\left\{  i+1,i+2,\ldots,n\right\}  $ satisfying
$\sigma\left(  i\right)  >\sigma\left(  j\right)  $. Likewise, $\ell
_{i}\left(  \tau\right)  $ was defined as the number of all $j\in\left\{
i+1,i+2,\ldots,n\right\}  $ satisfying $\tau\left(  i\right)  >\tau\left(
j\right)  $. Comparing these two definitions, we see that in order to prove
$\ell_{i}\left(  \tau\right)  =\ell_{i}\left(  \sigma\right)  $, it suffices
to prove that the $j\in\left\{  i+1,i+2,\ldots,n\right\}  $ satisfying
$\sigma\left(  i\right)  >\sigma\left(  j\right)  $ are precisely the
$j\in\left\{  i+1,i+2,\ldots,n\right\}  $ satisfying $\tau\left(  i\right)
>\tau\left(  j\right)  $. In other words, it suffices to prove that for each
$j\in\left\{  i+1,i+2,\ldots,n\right\}  $, we have the logical equivalence
$\left(  \sigma\left(  i\right)  >\sigma\left(  j\right)  \right)
\ \Longleftrightarrow\ \left(  \tau\left(  i\right)  >\tau\left(  j\right)
\right)  $.

So let us prove this. Fix $j\in\left\{  i+1,i+2,\ldots,n\right\}  $. Then,
both $i$ and $j$ belong to the set $\left\{  i,i+1,\ldots,n\right\}  $. Hence,
both $\sigma\left(  i\right)  $ and $\sigma\left(  j\right)  $ belong to the
set $\sigma\left(  \left\{  i,i+1,\ldots,n\right\}  \right)  $. Therefore, we
have the logical equivalence%
\[
\left(  \sigma\left(  i\right)  >\sigma\left(  j\right)  \right)
\ \Longleftrightarrow\ \left(  \left(  \alpha\mid_{\sigma\left(  \left\{
i,i+1,\ldots,n\right\}  \right)  }\right)  \left(  \sigma\left(  i\right)
\right)  >\left(  \alpha\mid_{\sigma\left(  \left\{  i,i+1,\ldots,n\right\}
\right)  }\right)  \left(  \sigma\left(  j\right)  \right)  \right)
\]
(since the map $\alpha\mid_{\sigma\left(  \left\{  i,i+1,\ldots,n\right\}
\right)  }:\sigma\left(  \left\{  i,i+1,\ldots,n\right\}  \right)
\rightarrow\left[  n\right]  $ is strictly increasing).

Thus, we have the following chain of equivalences:%
\begin{align*}
&  \left(  \sigma\left(  i\right)  >\sigma\left(  j\right)  \right) \\
&  \Longleftrightarrow\ \left(  \underbrace{\left(  \alpha\mid_{\sigma\left(
\left\{  i,i+1,\ldots,n\right\}  \right)  }\right)  \left(  \sigma\left(
i\right)  \right)  }_{=\alpha\left(  \sigma\left(  i\right)  \right)  =\left(
\alpha\circ\sigma\right)  \left(  i\right)  }>\underbrace{\left(  \alpha
\mid_{\sigma\left(  \left\{  i,i+1,\ldots,n\right\}  \right)  }\right)
\left(  \sigma\left(  j\right)  \right)  }_{=\alpha\left(  \sigma\left(
j\right)  \right)  =\left(  \alpha\circ\sigma\right)  \left(  j\right)
}\right) \\
&  \Longleftrightarrow\ \left(  \left(  \alpha\circ\sigma\right)  \left(
i\right)  >\left(  \alpha\circ\sigma\right)  \left(  j\right)  \right)
\ \Longleftrightarrow\ \left(  \tau\left(  i\right)  >\tau\left(  j\right)
\right)  \qquad\left(  \text{since }\alpha\circ\sigma=\tau\right)  .
\end{align*}
Hence, we have the logical equivalence $\left(  \sigma\left(  i\right)
>\sigma\left(  j\right)  \right)  \ \Longleftrightarrow\ \left(  \tau\left(
i\right)  >\tau\left(  j\right)  \right)  $. This completes the proof of Lemma
\ref{lem.perm.lehmer.iplusli} \textbf{(c)}.
\end{proof}

Now, for each $i\in\left[  n\right]  $, the permutations $\operatorname{cyc}%
_{i^{\prime},i^{\prime}-1,\ldots,i}$ and $s_{i^{\prime}-1}s_{i^{\prime}%
-2}\cdots s_{i}$ appearing in the exercise are well-defined (because Lemma
\ref{lem.perm.lehmer.iplusli} \textbf{(a)} yields that $i^{\prime}=i+\ell
_{i}\left(  \sigma\right)  $ satisfies $i^{\prime}\in\left[  n\right]  $ and
$i^{\prime}\geq i$). Moreover, these permutations are equal (for each
$i\in\left[  n\right]  $ separately), because of the following fact:

\begin{lemma}
\label{lem.perm.lehmer.cyc=sss}Let $n\in\mathbb{N}$. Let $i$ and $i^{\prime}$
be two elements of $\left[  n\right]  $ such that $i^{\prime}\geq i$. Then,
$\operatorname{cyc}_{i^{\prime},i^{\prime}-1,\ldots,i}=s_{i^{\prime}%
-1}s_{i^{\prime}-2}\cdots s_{i}$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.perm.lehmer.cyc=sss}.]Proposition 4.3 \textbf{(a)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-10-17.pdf}{the
class notes from 2018-10-17} (applied to $k=i^{\prime}-i+1$ and $\left(
i_{1},i_{2},\ldots,i_{k}\right)  =\left(  i^{\prime},i^{\prime}-1,\ldots
,i\right)  $) yields%
\[
\operatorname{cyc}_{i^{\prime},i^{\prime}-1,\ldots,i}=\underbrace{t_{i^{\prime
},i^{\prime}-1}}_{=t_{i^{\prime}-1,i^{\prime}}=s_{i^{\prime}-1}}%
\underbrace{t_{i^{\prime}-1,i^{\prime}-2}}_{=t_{i^{\prime}-2,i^{\prime}%
-1}=s_{i^{\prime}-2}}\cdots\underbrace{t_{i+1,i}}_{=t_{i,i+1}=s_{i}%
}=s_{i^{\prime}-1}s_{i^{\prime}-2}\cdots s_{i}.
\]
This proves Lemma \ref{lem.perm.lehmer.cyc=sss}.
\end{proof}

Thus, the definition of $a_{i}$ given in the exercise makes sense.

Next, we recall the principle of \textit{backwards induction} -- i.e., the
following induction principle (stated here in a form tailored to our specific situation):

\begin{theorem}
\label{thm.ind.BIP-nj0}Let $n\in\mathbb{N}$. For each $p\in\left\{
0,1,\ldots,n\right\}  $, let $\mathcal{A}\left(  p\right)  $ be a logical statement.

Assume the following:

\begin{statement}
\textit{Assumption 1:} The statement $\mathcal{A}\left(  n\right)  $ holds.
\end{statement}

\begin{statement}
\textit{Assumption 2:} If $j\in\left[  n\right]  $ is such that $\mathcal{A}%
\left(  j\right)  $ holds, then $\mathcal{A}\left(  j-1\right)  $ also holds.
\end{statement}

Then, $\mathcal{A}\left(  p\right)  $ holds for each $p\in\left\{
0,1,\ldots,n\right\}  $.
\end{theorem}

It is easy to prove Theorem \ref{thm.ind.BIP-nj0} by deriving it from the
usual induction principle. (Namely, argue by induction on $k$ that
$\mathcal{A}\left(  n-k\right)  $ holds for each $k\in\left\{  0,1,\ldots
,n\right\}  $. Assumption 1 provides the induction base, while Assumption 2
provides the induction step.)

Now, let us solve the exercise. We shall follow the hint. Fix $n\in\mathbb{N}%
$. For each $p\in\left\{  0,1,\ldots,n\right\}  $, let us define a statement
$\mathcal{A}\left(  p\right)  $ as follows:

\begin{statement}
\textit{Statement $\mathcal{A}\left(  p\right)  $:} Let $\sigma\in S_{n}$ be
such that $1,2,\ldots,p$ are fixed points of $\sigma$.

For each $i\in\left\{  p+1,p+2,\ldots,n\right\}  $, let $a_{i}%
=\operatorname{cyc}_{i^{\prime},i^{\prime}-1,\ldots,i}$, where $i^{\prime
}=i+\ell_{i}\left(  \sigma\right)  $. (This is well-defined, because Lemma
\ref{lem.perm.lehmer.iplusli} \textbf{(a)} shows that $i^{\prime}\in\left[
n\right]  $ and $i^{\prime}\geq i$.) Then, $\sigma=a_{p+1}a_{p+2}\cdots a_{n}$.
\end{statement}

Our goal is to prove that $\mathcal{A}\left(  p\right)  $ holds for each
$p\in\left\{  0,1,\ldots,n\right\}  $. This is, as the hint says,
\textquotedblleft more general\textquotedblright\ than the exercise, because
the claim of the exercise is precisely the statement $\mathcal{A}\left(
0\right)  $ (indeed, the requirement that $1,2,\ldots,0$ are fixed points of
$\sigma$ is vacuously true). But the words \textquotedblleft more
general\textquotedblright\ are in quotation marks because all of these
statements $\mathcal{A}\left(  p\right)  $ can be easily derived from the
exercise, once the latter is solved; they are thus mere stepping stones for
our solution.

We take aim at proving that Assumptions 1 and 2 of Theorem
\ref{thm.ind.BIP-nj0} hold for these statements $\mathcal{A}\left(  0\right)
,\mathcal{A}\left(  1\right)  ,\ldots,\mathcal{A}\left(  n\right)  $:

[\textit{Proof of Assumption 1:} We must prove that if $\sigma\in S_{n}$ is
such that $1,2,\ldots,n$ are fixed points of $\sigma$, then $\sigma
=a_{n+1}a_{n+2}\cdots a_{n}$. But this is clear: If $\sigma\in S_{n}$ is such
that $1,2,\ldots,n$ are fixed points of $\sigma$, then $\sigma
=\operatorname*{id}=\left(  \text{empty product}\right)  =a_{n+1}a_{n+2}\cdots
a_{n}$. Thus, Statement $\mathcal{A}\left(  n\right)  $ holds. This concludes
the proof of Assumption 1.]

[\textit{Proof of Assumption 2:} Let $j\in\left[  n\right]  $ be such that
$\mathcal{A}\left(  j\right)  $ holds. We must prove that $\mathcal{A}\left(
j-1\right)  $ also holds.

Let $\sigma\in S_{n}$ be such that $1,2,\ldots,j-1$ are fixed points of
$\sigma$. For each $i\in\left\{  j,j+1,\ldots,n\right\}  $, set $i^{\prime
}=i+\ell_{i}\left(  \sigma\right)  $ and $a_{i}=\operatorname{cyc}_{i^{\prime
},i^{\prime}-1,\ldots,i}$. (This is well-defined, because Lemma
\ref{lem.perm.lehmer.iplusli} \textbf{(a)} shows that $i^{\prime}\in\left[
n\right]  $ and $i^{\prime}\geq i$.) We are going to prove that $\sigma
=a_{j}a_{j+1}\cdots a_{n}$.

First, however, let us check that $\sigma\left(  j\right)  =j^{\prime}$.
Indeed, $\sigma\left(  \left[  j-1\right]  \right)  =\left[  j-1\right]  $
(since $1,2,\ldots,j-1$ are fixed points of $\sigma$). Moreover,
$\sigma\left(  j\right)  \geq j$ (because otherwise, we would have
$\sigma\left(  j\right)  <j$, so that $\sigma\left(  j\right)  \in\left[
j-1\right]  =\sigma\left(  \left[  j-1\right]  \right)  $, which would mean
that $\sigma\left(  j\right)  =\sigma\left(  k\right)  $ for some $k\in\left[
j-1\right]  $; but this would contradict the injectivity of $\sigma$).

Now, Lemma \ref{lem.perm.lehmer.iplusli} \textbf{(b)} (applied to $j$ instead
of $i$) yields
\begin{align*}
\ell_{j}\left(  \sigma\right)   &  =\left\vert \left[  \sigma\left(  j\right)
-1\right]  \setminus\underbrace{\sigma\left(  \left[  j-1\right]  \right)
}_{=\left[  j-1\right]  }\right\vert =\left\vert \underbrace{\left[
\sigma\left(  j\right)  -1\right]  \setminus\left[  j-1\right]  }_{=\left\{
j,j+1,\ldots,\sigma\left(  j\right)  -1\right\}  }\right\vert =\left\vert
\left\{  j,j+1,\ldots,\sigma\left(  j\right)  -1\right\}  \right\vert \\
&  =\sigma\left(  j\right)  -j\qquad\left(  \text{since }\sigma\left(
j\right)  \geq j\right)  .
\end{align*}
Hence, $j+\ell_{j}\left(  \sigma\right)  =\sigma\left(  j\right)  $. Now, the
definition of $j^{\prime}$ yields $j^{\prime}=j+\ell_{j}\left(  \sigma\right)
=\sigma\left(  j\right)  $. But the definition of $a_{j}$ yields
$a_{j}=\operatorname*{cyc}\nolimits_{j^{\prime},j^{\prime}-1,\ldots,j}$,
whence $a_{j}\left(  j\right)  =j^{\prime}=\sigma\left(  j\right)  $, so that
$a_{j}^{-1}\left(  \sigma\left(  j\right)  \right)  =j$.

We have $a_{j}=\operatorname*{cyc}\nolimits_{j^{\prime},j^{\prime}-1,\ldots
,j}$ (by the definition of $a_{j}$). Now, each $k\in\left[  j-1\right]  $
satisfies $k\leq j-1<j$ and thus $k\notin\left\{  j^{\prime},j^{\prime
}-1,\ldots,j\right\}  $ (since all elements of $\left\{  j^{\prime},j^{\prime
}-1,\ldots,j\right\}  $ are $\geq j$) and therefore $\operatorname*{cyc}%
\nolimits_{j^{\prime},j^{\prime}-1,\ldots,j}\left(  k\right)  =k$ and thus
$\underbrace{a_{j}}_{=\operatorname*{cyc}\nolimits_{j^{\prime},j^{\prime
}-1,\ldots,j}}\left(  k\right)  =\operatorname*{cyc}\nolimits_{j^{\prime
},j^{\prime}-1,\ldots,j}\left(  k\right)  =k$ and thus%
\begin{equation}
a_{j}^{-1}\left(  k\right)  =k. \label{sol.perm.lehmer.redword.2}%
\end{equation}


Now, let $\tau\in S_{n}$ be the permutation $a_{j}^{-1}\circ\sigma$. Then,
$\tau\left(  j\right)  =\left(  a_{j}^{-1}\circ\sigma\right)  \left(
j\right)  =a_{j}^{-1}\left(  \sigma\left(  j\right)  \right)  =j$. In other
words, $j$ is a fixed point of $\tau$.

Moreover, each $k\in\left[  j-1\right]  $ satisfies $\sigma\left(  k\right)
=k$ (since $1,2,\ldots,j-1$ are fixed points of $\sigma$) and thus
\[
\underbrace{\tau}_{=a_{j}^{-1}\circ\sigma}\left(  k\right)  =\left(
a_{j}^{-1}\circ\sigma\right)  \left(  k\right)  =a_{j}^{-1}\left(
\underbrace{\sigma\left(  k\right)  }_{=k}\right)  =a_{j}^{-1}\left(
k\right)  =k\qquad\left(  \text{by \eqref{sol.perm.lehmer.redword.2}}\right)
.
\]
In other words, $1,2,\ldots,j-1$ are fixed points of $\tau$. Since $j$ is also
a fixed point of $\tau$, we thus conclude that $1,2,\ldots,j$ are fixed points
of $\tau$.

Next, let $i\in\left\{  j+1,j+2,\ldots,n\right\}  $ be arbitrary. Thus, $i\geq
j+1>j$. Therefore, $j^{\prime}\notin\sigma\left(  \left\{  i,i+1,\ldots
,n\right\}  \right)  $\ \ \ \ \footnote{\textit{Proof.} Assume the contrary.
Thus, $j^{\prime}\in\sigma\left(  \left\{  i,i+1,\ldots,n\right\}  \right)  $.
In other words, there exists some $k\in\left\{  i,i+1,\ldots,n\right\}  $ such
that $j^{\prime}=\sigma\left(  k\right)  $. Consider this $k$. Comparing
$j^{\prime}=\sigma\left(  k\right)  $ with $j^{\prime}=\sigma\left(  j\right)
$, we obtain $\sigma\left(  k\right)  =\sigma\left(  j\right)  $, and thus
$k=j$ (since $\sigma$ is injective). From $k\in\left\{  i,i+1,\ldots
,n\right\}  $, we obtain $k\geq i>j$ and therefore $k\neq j$. This contradicts
$k=j$. This contradiction shows that our assumption was false, qed.}. Also,
$j^{\prime}=j+\underbrace{\ell_{j}\left(  \sigma\right)  }_{\geq0}\geq j$, so
that $j\leq j^{\prime}$.

Define a permutation $\alpha\in S_{n}$ by $\alpha=a_{j}^{-1}$. Then,
$\tau=\underbrace{a_{j}^{-1}}_{=\alpha}\circ\sigma=\alpha\circ\sigma$.

From $a_{j}=\operatorname*{cyc}\nolimits_{j^{\prime},j^{\prime}-1,\ldots,j}$,
we obtain $a_{j}^{-1}=\left(  \operatorname*{cyc}\nolimits_{j^{\prime
},j^{\prime}-1,\ldots,j}\right)  ^{-1}=\operatorname*{cyc}%
\nolimits_{j,j+1,\ldots,j^{\prime}}$. Thus, $\alpha=a_{j}^{-1}%
=\operatorname*{cyc}\nolimits_{j,j+1,\ldots,j^{\prime}}$. Hence, Lemma
\ref{lem.perm.lehmer.cyc.strinc} (applied to $a=j$, $b=j^{\prime}$ and
$U=\sigma\left(  \left\{  i,i+1,\ldots,n\right\}  \right)  $) yields that the
restriction $\alpha\mid_{\sigma\left(  \left\{  i,i+1,\ldots,n\right\}
\right)  }:\sigma\left(  \left\{  i,i+1,\ldots,n\right\}  \right)
\rightarrow\left[  n\right]  $ is strictly increasing (since $j^{\prime}%
\notin\sigma\left(  \left\{  i,i+1,\ldots,n\right\}  \right)  $). Hence, Lemma
\ref{lem.perm.lehmer.iplusli} \textbf{(c)} yields $\ell_{i}\left(
\tau\right)  =\ell_{i}\left(  \sigma\right)  $.

Now, forget that we fixed $i$. We thus have shown that each $i\in\left\{
j+1,j+2,\ldots,n\right\}  $ satisfies%
\begin{equation}
\ell_{i}\left(  \tau\right)  =\ell_{i}\left(  \sigma\right)  .
\label{sol.perm.lehmer.redword.3}%
\end{equation}
Thus, each $i\in\left\{  j+1,j+2,\ldots,n\right\}  $ satisfies
\begin{equation}
i^{\prime}=i+\underbrace{\ell_{i}\left(  \sigma\right)  }_{\substack{=\ell
_{i}\left(  \tau\right)  \\\text{(by \eqref{sol.perm.lehmer.redword.3})}%
}}=i+\ell_{i}\left(  \tau\right)  . \label{sol.perm.lehmer.redword.4}%
\end{equation}


Now let us see where we stand: The permutation $\tau\in S_{n}$ has the
property that $1,2,\ldots,j$ are fixed points of $\tau$. For each
$i\in\left\{  j+1,j+2,\ldots,n\right\}  $, we have $a_{i}=\operatorname{cyc}%
_{i^{\prime},i^{\prime}-1,\ldots,i}$, where $i^{\prime}=i+\ell_{i}\left(
\tau\right)  $ (by \eqref{sol.perm.lehmer.redword.4}). Hence, we can apply
Statement $\mathcal{A}\left(  j\right)  $ (which we have assumed to hold) to
$\tau$ instead of $\sigma$. We thus conclude that $\tau=a_{j+1}a_{j+2}\cdots
a_{n}$. From $\tau=a_{j}^{-1}\circ\sigma=a_{j}^{-1}\sigma$, we obtain%
\[
\sigma=a_{j}\underbrace{\tau}_{=a_{j+1}a_{j+2}\cdots a_{n}}=a_{j}\left(
a_{j+1}a_{j+2}\cdots a_{n}\right)  =a_{j}a_{j+1}\cdots a_{n}.
\]


Now, forget that we fixed $\sigma$. We thus have shown that if $\sigma\in
S_{n}$ is such that $1,2,\ldots,j-1$ are fixed points of $\sigma$, and if we
set
\[
a_{i}=\operatorname{cyc}_{i^{\prime},i^{\prime}-1,\ldots,i}\text{ (where
}i^{\prime}=i+\ell_{i}\left(  \sigma\right)  \text{)}\qquad\text{for each
}i\in\left\{  j,j+1,\ldots,n\right\}  ,
\]
then $\sigma=a_{j}a_{j+1}\cdots a_{n}$. But this is precisely the statement
$\mathcal{A}\left(  j-1\right)  $. So we have shown that $\mathcal{A}\left(
j-1\right)  $ holds. This proves Assumption 2.]

We have now verified that both Assumptions 1 and 2 of Theorem
\ref{thm.ind.BIP-nj0} hold. Hence, Theorem \ref{thm.ind.BIP-nj0} shows that
$\mathcal{A}\left(  p\right)  $ holds for each $p\in\left\{  0,1,\ldots
,n\right\}  $. Thus, in particular, $\mathcal{A}\left(  0\right)  $ holds. But
$\mathcal{A}\left(  0\right)  $ is precisely the claim of the exercise (since
every permutation $\sigma\in S_{n}$ has the property that $1,2,\ldots,0$ are
fixed points of $\sigma$). Thus, the exercise is solved.

\subsection{Remark}

Let $w_{0}$ be the permutation of $\left[  n\right]  $ that sends each
$k\in\left[  n\right]  $ to $n+1-k$. Applying the exercise to $\sigma=w_{0}$,
we obtain%
\begin{align}
w_{0}  & =\operatorname*{cyc}\nolimits_{n,n-1,\ldots,1}\operatorname*{cyc}%
\nolimits_{n,n-1,\ldots,2}\cdots\operatorname*{cyc}\nolimits_{n,n-1,n-2}%
\operatorname*{cyc}\nolimits_{n,n-1}\operatorname*{cyc}\nolimits_{n}%
\nonumber\\
& =\left(  s_{n-1}s_{n-2}\cdots s_{1}\right)  \left(  s_{n-1}s_{n-2}\cdots
s_{2}\right)  \cdots\left(  s_{n-1}s_{n-2}s_{n-3}\right)  \left(
s_{n-1}s_{n-2}\right)  \left(  s_{n-1}\right)
\label{sol.perm.lehmer.redword.rmk.w0.1}%
\end{align}
(because setting $\sigma=w_{0}$, we get $\ell_{i}\left(  \sigma\right)  =n-i$
and thus $a_{i}=\operatorname*{cyc}\nolimits_{n,n-1,\ldots,i}=s_{n-1}%
s_{n-2}\cdots s_{i}$ for each $i\in\left[  n\right]  $).

On the other hand, Part of Proposition 4.3 \textbf{(h)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-10-17.pdf}{the
class notes from 2018-10-17} is the claim that%
\begin{align}
w_{0} &  =\operatorname*{cyc}\nolimits_{1}\operatorname*{cyc}\nolimits_{2,1}%
\operatorname*{cyc}\nolimits_{3,2,1}\cdots\operatorname*{cyc}%
\nolimits_{n,n-1,\ldots,1}\nonumber\\
&  =s_{1}\left(  s_{2}s_{1}\right)  \left(  s_{3}s_{2}s_{1}\right)
\cdots\left(  s_{n-1}s_{n-2}\cdots s_{1}\right)
.\label{sol.perm.lehmer.redword.rmk.w0.2}%
\end{align}


Do you see why the two equalities \eqref{sol.perm.lehmer.redword.rmk.w0.1} and
\eqref{sol.perm.lehmer.redword.rmk.w0.2} are equivalent? (\textit{Hint:} We
have $w_{0}=w_{0}^{-1}$ and also $w_{0}s_{i}w_{0}^{-1}=s_{n-i}$ for each
$i\in\left[  n-1\right]  $.)

%----------------------------------------------------------------------------------------
%	EXERCISE 3
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 3}

\subsection{Problem}

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

\begin{enumerate}
\item[\textbf{(a)}] Prove that any $\sigma\in S_{n}$ and any $i \in\left[  n
\right]  $ satisfy $\sigma\left(  i \right)  \leq i + \ell_{i} \left(
\sigma\right)  $.

\item[\textbf{(b)}] Prove that, for a given $\sigma\in S_{n}$, the following
three statements are equivalent:

\begin{enumerate}
\item[$A$:] We have $\sigma\left(  i \right)  \leq i+1$ for all $i \in\left[
n-1 \right]  $.

\item[$B$:] The permutation $\sigma$ is both 321-avoiding and 312-avoiding.

\item[$C$:] We have $\ell_{i} \left(  \sigma\right)  \in\left\{  0, 1
\right\}  $ for each $i \in\left[  n \right]  $. (In other words, the Lehmer
code of $\sigma$ consists only of $0$'s and $1$'s.)
\end{enumerate}

\item[\textbf{(c)}] Assuming that $n\geq1$, prove that the number of
$\sigma\in S_{n}$ satisfying these three statements is $2^{n-1}$.
\end{enumerate}

\subsection{Remark}

Part \textbf{(a)} of this exercise is exactly \cite[Lemma 5.48 \textbf{(c)}%
]{detnotes}.

\subsection{Solution sketch}

\textbf{(a)} Let $\sigma\in S_{n}$ and $i\in\left[  n\right]  $. Lemma
\ref{lem.perm.lehmer.iplusli} \textbf{(b)} yields
\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
\geq\left\vert \left[  \sigma\left(  i\right)  -1\right]  \right\vert
-\underbrace{\left\vert \sigma\left(  \left[  i-1\right]  \right)  \right\vert
}_{\substack{=\left\vert \left[  i-1\right]  \right\vert \\\text{(since the
map }\sigma\text{ is injective)}}}\\
&  \qquad\left(  \text{since }\left\vert A\setminus B\right\vert
\geq\left\vert A\right\vert -\left\vert B\right\vert \text{ for any two finite
sets }A\text{ and }B\right) \\
&  =\underbrace{\left\vert \left[  \sigma\left(  i\right)  -1\right]
\right\vert }_{=\sigma\left(  i\right)  -1}-\underbrace{\left\vert \left[
i-1\right]  \right\vert }_{=i-1}=\left(  \sigma\left(  i\right)  -1\right)
-\left(  i-1\right)  =\sigma\left(  i\right)  -i.
\end{align*}
In other words, $\sigma\left(  i\right)  \leq i+\ell_{i}\left(  \sigma\right)
$. This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} We shall prove the three implications $A\Longrightarrow B$,
$B\Longrightarrow C$ and $C\Longrightarrow A$:

\textit{Proof of the implication }$A\Longrightarrow B$\textit{:} Assume that
statement $A$ holds. Thus, $\sigma\left(  i\right)  \leq i+1$ for all
$i\in\left[  n-1\right]  $. This inequality clearly also holds for $i=n$
(since $\sigma\left(  n\right)  \leq n\leq n+1$); thus, it holds for all
$i\in\left[  n\right]  $. In other words, we have%
\begin{equation}
\sigma\left(  i\right)  \leq i+1\qquad\text{for all }i\in\left[  n\right]  .
\label{sol.perm.lehmer.321-312.b.1}%
\end{equation}


Let $i,j,k\in\left[  n\right]  $ be three elements satisfying $i<j<k$ and
$\sigma\left(  j\right)  <\sigma\left(  k\right)  <\sigma\left(  i\right)  $.
We shall derive a contradiction.

Indeed, every $p\in\left[  i\right]  $ satisfies
\begin{align*}
\sigma\left(  p\right)   &  \leq p+1\qquad\left(  \text{by
\eqref{sol.perm.lehmer.321-312.b.1}, applied to }p\text{ instead of }i\right)
\\
&  \leq i+1\qquad\left(  \text{since }p\leq i\right)
\end{align*}
and thus $\sigma\left(  p\right)  \in\left[  i+1\right]  $. In other words,
$\sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
i\right)  $ are $i$ elements of the set $\left[  i+1\right]  $.

Also, $\sigma\left(  j\right)  <\sigma\left(  i\right)  \leq i+1$ (by
\eqref{sol.perm.lehmer.321-312.b.1}); hence, $\sigma\left(  j\right)  $ is an
element of the set $\left[  i+1\right]  $ as well. Similarly, $\sigma\left(
k\right)  $ is an element of the set $\left[  i+1\right]  $ as well.

The $i+2$ elements $\underbrace{1,2,\ldots,i}_{\text{the elements of }\left[
i\right]  },j,k$ are distinct (since $i<j<k$). Hence, their images under
$\sigma$ are distinct as well (since $\sigma$ is injective). In other words,
the $i+2$ elements $\sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  i\right)  ,\sigma\left(  j\right)  ,\sigma\left(
k\right)  $ are distinct. But we know that these $i+2$ distinct elements must
belong to the $\left(  i+1\right)  $-element set $\left[  i+1\right]  $ (since
we have shown that $\sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  i\right)  $ are $i$ elements of the set $\left[
i+1\right]  $, that $\sigma\left(  j\right)  $ is an element of the set
$\left[  i+1\right]  $, and that $\sigma\left(  k\right)  $ is an element of
the set $\left[  i+1\right]  $). This, of course, contradicts the Pigeonhole
Principle (as $i+2>i+1$).

Now, forget that we fixed $i,j,k$. We thus have derived a contradiction for
each three elements $i,j,k\in\left[  n\right]  $ satisfying $i<j<k$ and
$\sigma\left(  j\right)  <\sigma\left(  k\right)  <\sigma\left(  i\right)  $.
Hence, there exist no such three elements $i,j,k$. In other words, $\sigma$ is
312-avoiding (by the definition of \textquotedblleft%
312-avoiding\textquotedblright). An analogous argument shows that $\sigma$ is
321-avoiding. Hence, the permutation $\sigma$ is both 321-avoiding and
312-avoiding. In other words, statement $B$ holds. This proves the implication
$A\Longrightarrow B$.

\textit{Proof of the implication }$B\Longrightarrow C$\textit{:} Assume that
statement $B$ holds. Thus, the permutation $\sigma$ is both 321-avoiding and 312-avoiding.

Now, let $i\in\left[  n\right]  $. We shall show that $\ell_{i}\left(
\sigma\right)  \in\left\{  0,1\right\}  $.

Indeed, assume the contrary. Thus, $\ell_{i}\left(  \sigma\right)
\notin\left\{  0,1\right\}  $. Hence, $\ell_{i}\left(  \sigma\right)  \geq2$
(since $\ell_{i}\left(  \sigma\right)  $ is a nonnegative integer). In other
words, there exist at least two $j\in\left\{  i+1,i+2,\ldots,n\right\}  $
satisfying $\sigma\left(  i\right)  >\sigma\left(  j\right)  $ (since
$\ell_{i}\left(  \sigma\right)  $ is the number of all such $j$'s). Fix two
distinct such $j$; denote them by $j_{1}$ and $j_{2}$. Thus, $j_{1}$ and
$j_{2}$ are two distinct $j\in\left\{  i+1,i+2,\ldots,n\right\}  $ satisfying
$\sigma\left(  i\right)  >\sigma\left(  j\right)  $.

Hence, $j_{1}\in\left\{  i+1,i+2,\ldots,n\right\}  $; therefore, $j_{1}\geq
i+1>i$ and $j_{1}\in\left[  n\right]  $. Similarly, $j_{2}>i$ and $j_{2}%
\in\left[  n\right]  $. Also, $\sigma\left(  i\right)  >\sigma\left(
j_{1}\right)  $ (by the definition of $j_{1}$) and $\sigma\left(  i\right)
>\sigma\left(  j_{2}\right)  $ (similarly).

We WLOG assume that $j_{1}\leq j_{2}$ (since otherwise, we can simply swap
$j_{1}$ with $j_{2}$). Hence, $j_{1}<j_{2}$ (since $j_{1}$ and $j_{2}$ are
distinct), so that $i<j_{1}<j_{2}$. Moreover, $\sigma$ is injective, and thus
$\sigma\left(  j_{1}\right)  \neq\sigma\left(  j_{2}\right)  $ (since $j_{1}$
and $j_{2}$ are distinct).

But if we had $\sigma\left(  j_{1}\right)  <\sigma\left(  j_{2}\right)  $,
then $\sigma$ would not be 312-avoiding (since the three elements
$i,j_{1},j_{2}\in\left[  n\right]  $ would satisfy $i<j_{1}<j_{2}$ and
$\sigma\left(  j_{1}\right)  <\sigma\left(  j_{2}\right)  <\sigma\left(
i\right)  $, which would make them the exact kind of three elements $i,j,k$
that the definition of \textquotedblleft312-avoiding\textquotedblright%
\ disallows). Hence, we cannot have $\sigma\left(  j_{1}\right)
<\sigma\left(  j_{2}\right)  $.

If we had $\sigma\left(  j_{1}\right)  >\sigma\left(  j_{2}\right)  $, then
$\sigma$ would not be 321-avoiding (since the three elements $i,j_{1},j_{2}%
\in\left[  n\right]  $ would satisfy $i<j_{1}<j_{2}$ and $\sigma\left(
j_{2}\right)  <\sigma\left(  j_{1}\right)  <\sigma\left(  i\right)  $, which
would make them the exact kind of three elements $i,j,k$ that the definition
of \textquotedblleft321-avoiding\textquotedblright\ disallows). Hence, we
cannot have $\sigma\left(  j_{1}\right)  >\sigma\left(  j_{2}\right)  $.

Therefore, neither $\sigma\left(  j_{1}\right)  <\sigma\left(  j_{2}\right)  $
nor $\sigma\left(  j_{1}\right)  >\sigma\left(  j_{2}\right)  $ is possible.
Hence, we must have $\sigma\left(  j_{1}\right)  =\sigma\left(  j_{2}\right)
$. This contradicts $\sigma\left(  j_{1}\right)  \neq\sigma\left(
j_{2}\right)  $.

This contradiction shows that our assumption was false. Hence, $\ell
_{i}\left(  \sigma\right)  \in\left\{  0,1\right\}  $ is proven.

Now, forget that we fixed $i$. We thus have shown that we have $\ell
_{i}\left(  \sigma\right)  \in\left\{  0,1\right\}  $ for each $i\in\left[
n\right]  $. In other words, statement $C$ holds. This proves the implication
$B\Longrightarrow C$.

\textit{Proof of the implication }$C\Longrightarrow A$\textit{:} Assume that
statement $C$ holds. Thus, we have $\ell_{i}\left(  \sigma\right)  \in\left\{
0,1\right\}  $ for each $i\in\left[  n\right]  $. In other words,
\begin{equation}
\ell_{i}\left(  \sigma\right)  \leq1\qquad\text{for each }i\in\left[
n\right]  . \label{sol.perm.lehmer.321-312.b.7}%
\end{equation}
Hence, for each $i\in\left[  n-1\right]  $, we have%
\begin{align*}
\sigma\left(  i\right)   &  \leq i+\underbrace{\ell_{i}\left(  \sigma\right)
}_{\substack{\leq1\\\text{(by \eqref{sol.perm.lehmer.321-312.b.7})}}}
\qquad\left(  \text{by part \textbf{(a)} of the exercise}\right) \\
&  \leq i+1.
\end{align*}
In other words, statement $A$ holds. This proves the implication
$C\Longrightarrow A$.

We have now proven the three implications $A\Longrightarrow B$,
$B\Longrightarrow C$ and $C\Longrightarrow A$. Combining them, we conclude
that the three statements $A$, $B$ and $C$ are equivalent. Thus, part
\textbf{(b)} of the exercise is solved.

\bigskip

\textbf{(c)} Assume that $n\geq1$.

Whenever $m$ is an integer, we shall use the notation $\left[  m\right]  _{0}$
for the set $\left\{  0,1,\ldots,m\right\}  $. (This is an empty set when
$m<0$.)

Let $H$ denote the set $\left[  n-1\right]  _{0}\times\left[  n-2\right]
_{0}\times\cdots\times\left[  n-n\right]  _{0}$.

Let $H_{1}$ denote the subset $\underbrace{\left\{  0,1\right\}
\times\left\{  0,1\right\}  \times\cdots\times\left\{  0,1\right\}
}_{n-1\text{ times}}\times\left\{  0\right\}  $ of $H$. Thus, $\left\vert
H_{1}\right\vert =2^{n-1}$.

Define the map $L:S_{n}\rightarrow H$ by%
\[
\left(  L\left(  \sigma\right)  =\left(  \ell_{1}\left(  \sigma\right)
,\ell_{2}\left(  \sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)
\right)  \qquad\text{for each }\sigma\in S_{n}\right)  .
\]
It is known that this map $L$ is well-defined and is a bijection (see, e.g.,
\cite[Theorem 5.52]{detnotes}).\footnote{This map $L$ is known as the
\textit{Lehmer code} (or, rather, $L\left(  \sigma\right)  $ is known as the
Lehmer code of the permutation $\sigma\in S_{n}$).} Hence,%
\[
\left(  \text{the number of }\sigma\in S_{n}\text{ satisfying }L\left(
\sigma\right)  \in H_{1}\right)  =\left\vert H_{1}\right\vert =2^{n-1}.
\]


Note that each $\sigma\in S_{n}$ satisfies
\begin{equation}
\ell_{n}\left(  \sigma\right)  =0 \label{sol.perm.lehmer.321-312.c.n0}%
\end{equation}
(since $\ell_{n}\left(  \sigma\right)  $ is defined as the number of all
$j\in\left\{  n+1,n+2,\ldots,n\right\}  $ satisfying $\sigma\left(  n\right)
>\sigma\left(  j\right)  $; but there are clearly no such $j$).

Hence, for each $\sigma\in S_{n}$, we have the following logical equivalence:%
\begin{equation}
\left(  \ell_{i}\left(  \sigma\right)  \in\left\{  0,1\right\}  \text{ for all
}i\in\left[  n\right]  \right)  \ \Longleftrightarrow\ \left(  L\left(
\sigma\right)  \in H_{1}\right)  . \label{sol.perm.lehmer.321-312.c.2}%
\end{equation}


[\textit{Proof of \eqref{sol.perm.lehmer.321-312.c.2}:} Let $\sigma\in S_{n}$.
We must prove the equivalence \eqref{sol.perm.lehmer.321-312.c.2}. We shall
prove its \textquotedblleft$\Longrightarrow$\textquotedblright\ and
\textquotedblleft$\Longleftarrow$\textquotedblright\ directions separately:

$\Longrightarrow:$ Assume that $\ell_{i}\left(  \sigma\right)  \in\left\{
0,1\right\}  $ for all $i\in\left[  n\right]  $. We must prove that $L\left(
\sigma\right)  \in H_{1}$.

We have assumed that $\ell_{i}\left(  \sigma\right)  \in\left\{  0,1\right\}
$ for all $i\in\left[  n\right]  $. Hence, $\ell_{1}\left(  \sigma\right)
,\ell_{2}\left(  \sigma\right)  ,\ldots,\ell_{n-1}\left(  \sigma\right)
\in\left\{  0,1\right\}  $. Furthermore, \eqref{sol.perm.lehmer.321-312.c.n0}
yields $\ell_{n}\left(  \sigma\right)  =0\in\left\{  0\right\}  $. Now, the
definition of $L$ yields%
\begin{align*}
L\left(  \sigma\right)   &  =\left(  \ell_{1}\left(  \sigma\right)  ,\ell
_{2}\left(  \sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)  \right)
\in\underbrace{\left\{  0,1\right\}  \times\left\{  0,1\right\}  \times
\cdots\times\left\{  0,1\right\}  }_{n-1\text{ times}}\times\left\{  0\right\}
\\
&  \qquad\left(  \text{since }\ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(
\sigma\right)  ,\ldots,\ell_{n-1}\left(  \sigma\right)  \in\left\{
0,1\right\}  \text{ and }\ell_{n}\left(  \sigma\right)  \in\left\{  0\right\}
\right) \\
&  =H_{1}\qquad\left(  \text{by the definition of }H_{1}\right)  .
\end{align*}


Now, forget that we assumed that $\ell_{i}\left(  \sigma\right)  \in\left\{
0,1\right\}  $ for all $i\in\left[  n\right]  $. We thus have shown that if
$\ell_{i}\left(  \sigma\right)  \in\left\{  0,1\right\}  $ for all
$i\in\left[  n\right]  $, then $L\left(  \sigma\right)  \in H_{1}$. In other
words, we have proven the \textquotedblleft$\Longrightarrow$\textquotedblright%
\ direction of the equivalence \eqref{sol.perm.lehmer.321-312.c.2}.

$\Longleftarrow:$ Assume that $L\left(  \sigma\right)  \in H_{1}$. We must
prove that $\ell_{i}\left(  \sigma\right)  \in\left\{  0,1\right\}  $ for all
$i\in\left[  n\right]  $.

We have assumed that $L\left(  \sigma\right)  \in H_{1}$. But the definition
of $L$ yields \newline$L\left(  \sigma\right)  =\left(  \ell_{1}\left(
\sigma\right)  ,\ell_{2}\left(  \sigma\right)  ,\ldots,\ell_{n}\left(
\sigma\right)  \right)  $. Hence,%
\begin{align*}
\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(  \sigma\right)
,\ldots,\ell_{n}\left(  \sigma\right)  \right)   &  =L\left(  \sigma\right)
\in H_{1}=\underbrace{\left\{  0,1\right\}  \times\left\{  0,1\right\}
\times\cdots\times\left\{  0,1\right\}  }_{n-1\text{ times}}\times
\underbrace{\left\{  0\right\}  }_{\subseteq\left\{  0,1\right\}  }\\
&  \qquad\left(  \text{by the definition of }H_{1}\right) \\
&  \subseteq\underbrace{\left\{  0,1\right\}  \times\left\{  0,1\right\}
\times\cdots\times\left\{  0,1\right\}  }_{n-1\text{ times}}\times\left\{
0,1\right\} \\
&  =\underbrace{\left\{  0,1\right\}  \times\left\{  0,1\right\}  \times
\cdots\times\left\{  0,1\right\}  }_{n\text{ times}}=\left\{  0,1\right\}
^{n}.
\end{align*}
In other words, $\ell_{i}\left(  \sigma\right)  \in\left\{  0,1\right\}  $ for
all $i\in\left[  n\right]  $.

Now, forget that we assumed that $L\left(  \sigma\right)  \in H_{1}$. We thus
have shown that if $L\left(  \sigma\right)  \in H_{1}$, then $\ell_{i}\left(
\sigma\right)  \in\left\{  0,1\right\}  $ for all $i\in\left[  n\right]  $. In
other words, we have proven the \textquotedblleft$\Longleftarrow
$\textquotedblright\ direction of the equivalence \eqref{sol.perm.lehmer.321-312.c.2}.

We now have proven both the \textquotedblleft$\Longrightarrow$%
\textquotedblright\ and the \textquotedblleft$\Longleftarrow$%
\textquotedblright\ directions of the equivalence
\eqref{sol.perm.lehmer.321-312.c.2}. Hence, this equivalence is proven.]

Now, consider the statements $A$, $B$ and $C$ from part \textbf{(b)} of the
exercise. These three statements are equivalent (by part \textbf{(b)}). Hence,%
\begin{align*}
&  \left(  \text{the number of }\sigma\in S_{n}\text{ satisfying statements
}A\text{, }B\text{ and }C\right) \\
&  =\left(  \text{the number of }\sigma\in S_{n}\text{ satisfying statement
}C\right) \\
&  =\left(  \text{the number of }\sigma\in S_{n}\text{ satisfying
}\underbrace{\ell_{i}\left(  \sigma\right)  \in\left\{  0,1\right\}  \text{
for all }i\in\left[  n\right]  }_{\substack{\Longleftrightarrow\ \left(
L\left(  \sigma\right)  \in H_{1}\right)  \\\text{(by
\eqref{sol.perm.lehmer.321-312.c.2})}}}\right) \\
&  =\left(  \text{the number of }\sigma\in S_{n}\text{ satisfying }L\left(
\sigma\right)  \in H_{1}\right)  =2^{n-1}.
\end{align*}
This solves part \textbf{(c)} of the exercise.

%----------------------------------------------------------------------------------------
%	EXERCISE 4
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 4}

\subsection{Problem}

Let $n \geq2$, and set $S = \left[  n \right]  $. Let $i \in\left[  n-1
\right]  $. Prove that:

\begin{enumerate}
\item[\textbf{(a)}] The number of maps $f : S \to S$ with $f \left(  i
\right)  = n$ and $f^{n} \left(  S \right)  = \left\{  n \right\}  $ is
$2n^{n-3}$.

\item[\textbf{(b)}] Let $j \in\left[  n-1 \right]  $ be such that $i \neq j$.
The number of maps $f : S \to S$ with $f \left(  i \right)  = j$ and $f^{n}
\left(  S \right)  = \left\{  n \right\}  $ is $n^{n-3}$.
\end{enumerate}

[\textbf{Hint:} Substitute appropriate numbers for the variables in the
Matrix-Tree Theorem.]

\subsection{Solution sketch}

Forget that we fixed $i$.

Before we solve anything, let us agree on a notation: If $i$ and $j$ are two
elements of $\left[  n\right]  $, then we define a set $A_{i,j}$ by%
\[
A_{i,j}=\left\{  f:S\rightarrow S\ \mid\ f\left(  i\right)  =j\text{ and
}f^{n}\left(  S\right)  =\left\{  n\right\}  \right\}  .
\]
Thus, $\left\vert A_{i,j}\right\vert $ is the number of maps $f:S\rightarrow
S$ with $f\left(  i\right)  =j$ and $f^{n}\left(  S\right)  =\left\{
n\right\}  $. Hence, part \textbf{(a)} of the exercise is equivalent to saying
that $\left\vert A_{i,n}\right\vert =2n^{n-3}$ for any $i\in\left[
n-1\right]  $, whereas part \textbf{(b)} of the exercise is equivalent to
saying that $\left\vert A_{i,j}\right\vert =n^{n-3}$ for any $i\in\left[
n-1\right]  $ and $j\in\left[  n-1\right]  $ satisfying $i\neq j$. It is in
these forms that we shall solve the exercise.

\bigskip

\textbf{(a)} \textit{First solution to part \textbf{(a)}:} Here is the
matrix-tree theorem, as stated in class (Theorem 5.4 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-05.pdf}{the
class notes from 2018-11-05}):\footnote{Keep in mind that we have not fixed
$i$, so we can use this letter for various other needs.}

\begin{theorem}
\label{thm.endofunctions.MTT.1}Let $n\geq1$. Let $S=\left[  n\right]  $. For
any distinct $i,j\in\left[  n\right]  $, let $a_{i,j}$ be a number (or an indeterminate).

For each $i\in\left[  n\right]  $, we let $b_{i}=a_{i,1}+a_{i,2}%
+\cdots+\widehat{a_{i,i}}+\cdots+a_{i,n}$. Here, the hat over the
\textquotedblleft$a_{i,i}$\textquotedblright\ means that the addend $a_{i,i}$
should not be included in the sum (so that the sum is $a_{i,1}+a_{i,2}%
+\cdots+a_{i,i-1}+a_{i,i+1}+a_{i,i+2}+\cdots+a_{i,n}$).

Let $L$ be the $\left(  n-1\right)  \times\left(  n-1\right)  $-matrix whose
$\left(  i,j\right)  $-th entry is $%
\begin{cases}
b_{i}, & \text{if }i=j;\\
-a_{i,j}, & \text{if }i\neq j
\end{cases}
$ for all $i,j\in\left[  n-1\right]  $.

Then,%
\[
\sum_{\substack{f:S\rightarrow S;\\f^{n}\left(  S\right)  =\left\{  n\right\}
}}\prod_{i\in\left[  n-1\right]  }a_{i,f\left(  i\right)  }=\det L.
\]

\end{theorem}

Now, recall that our goal is to solve part \textbf{(a)} of the exercise; in
other words, our goal is to prove that $\left\vert A_{i,n}\right\vert
=2n^{n-3}$ for any $i\in\left[  n-1\right]  $ (because part \textbf{(a)} is
equivalent to this). First, we notice that the specific value of the number
$i$ is irrelevant: If $i_{1}$ and $i_{2}$ are two elements of $\left[
n-1\right]  $, then $\left\vert A_{i_{1},n}\right\vert =\left\vert A_{i_{2}%
,n}\right\vert $\ \ \ \ \footnote{\textit{Proof.} Let $i_{1}$ and $i_{2}$ be
two elements of $\left[  n-1\right]  $. We must prove that $\left\vert
A_{i_{1},n}\right\vert =\left\vert A_{i_{2},n}\right\vert $. If $i_{1}=i_{2}$,
then this is obvious. Thus, WLOG assume that $i_{1}\neq i_{2}$. Hence, the
transposition $t_{i_{1},i_{2}}\in S_{n}$ is well-defined. Clearly, $n$ is a
fixed point of $t_{i_{1},i_{2}}$, and $t_{i_{1},i_{2}}$ is an involution. Now,
it is easy to see that the map%
\[
A_{i_{1},n}\rightarrow A_{i_{2},n},\qquad f\mapsto t_{i_{1},i_{2}}\circ f\circ
t_{i_{1},i_{2}}%
\]
is well-defined (after all, it simply interchanges the roles of $i_{1}$ and
$i_{2}$, so that it sends a map $f$ satisfying $f\left(  i_{1}\right)  =j$ to
a map $f$ satisfying $f\left(  i_{2}\right)  =j$ without disrupting the
\textquotedblleft$f^{n}\left(  S\right)  =\left\{  n\right\}  $%
\textquotedblright\ behavior) and is a bijection (its inverse map is defined
in the same way). Thus, $\left\vert A_{i_{1},n}\right\vert =\left\vert
A_{i_{2},n}\right\vert $, qed.}. Applying this to $i_{1}=i$ and $i_{2}=n-1$,
we conclude that
\begin{equation}
\left\vert A_{i,n}\right\vert =\left\vert A_{n-1,n}\right\vert \qquad\text{for
each }i\in\left[  n-1\right]  . \label{sol.endofunctions.nn-3.a.i-irrev}%
\end{equation}
Hence, in order to prove that $\left\vert A_{i,n}\right\vert =2n^{n-3}$ for
any $i\in\left[  n-1\right]  $, it suffices to prove that $\left\vert
A_{n-1,n}\right\vert =2n^{n-3}$. This is what we shall prove in the following.

We WLOG assume that $n\geq3$, since otherwise the result is easy to check by hand.

For any distinct $i,j\in\left[  n\right]  $, let $a_{i,j}=\left[  i\neq
n-1\text{ or }j=n\right]  $. Thus, $a_{i,j}=1$ whenever $i\neq n-1$, whereas
$a_{n-1,j}=\left[  j=n\right]  $. Now, define $b_{i}$ and $L$ as in Theorem
\ref{thm.endofunctions.MTT.1}. Then, each $i\in\left[  n-1\right]  $ satisfies%
\begin{align*}
b_{i}  &  =a_{i,1}+a_{i,2}+\cdots+\widehat{a_{i,i}}+\cdots+a_{i,n}%
=\sum_{\substack{j\in\left[  n\right]  ;\\j\neq i}}\underbrace{a_{i,j}%
}_{=\left[  i\neq n-1\text{ or }j=n\right]  }\\
&  =\sum_{\substack{j\in\left[  n\right]  ;\\j\neq i}}\left[  i\neq n-1\text{
or }j=n\right]  =%
\begin{cases}
n-1, & \text{if }i\neq n-1;\\
1, & \text{if }i=n-1
\end{cases}
\end{align*}
(because if $i\neq n-1$, then all $n-1$ addends of the sum $\sum
_{\substack{j\in\left[  n\right]  ;\\j\neq i}}\left[  i\neq n-1\text{ or
}j=n\right]  $ equal $1$, whereas otherwise one of these addends equals $1$
whereas all others equal $0$). Hence, the $\left(  n-1\right)  \times\left(
n-1\right)  $-matrix $L$ has the following form:\footnote{We are using a
slightly nonstandard notation here: We are putting the size of a matrix as a
subscript on the bottom right of the matrix. Thus, for example,
\textquotedblleft$\left(
\begin{array}
[c]{cccc}%
1 & 1 & \cdots & 1\\
1 & 1 & \cdots & 1\\
\vdots & \vdots & \ddots & \vdots\\
1 & 1 & \cdots & 1
\end{array}
\right)  _{7\times7}$\textquotedblright\ will mean the $7\times7$-matrix whose
all entries equal $1$. This prevents ambiguities (for example, without the
subscript, \textquotedblleft$\left(
\begin{array}
[c]{cccc}%
1 & 1 & \cdots & 1\\
1 & 1 & \cdots & 1\\
\vdots & \vdots & \ddots & \vdots\\
1 & 1 & \cdots & 1
\end{array}
\right)  $\textquotedblright\ would be ambiguous, because the size of the
matrix would not be clear).}%
\[
L=\left(
\begin{array}
[c]{cccccc}%
n-1 & -1 & -1 & \cdots & -1 & -1\\
-1 & n-1 & -1 & \cdots & -1 & -1\\
-1 & -1 & n-1 & \cdots & -1 & -1\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
-1 & -1 & -1 & \cdots & n-1 & -1\\
0 & 0 & 0 & \cdots & 0 & 1
\end{array}
\right)  _{\left(  n-1\right)  \times\left(  n-1\right)  }%
\]
(viz.: its diagonal entries are $\underbrace{n-1,n-1,\ldots,n-1}_{n-2\text{
times}},1$; its last row is $\underbrace{0,0,\ldots,0}_{n-2\text{ times}},1$;
and all its other entries equal $-1$). Hence,%
\begin{align*}
\det L  &  =\det\left(
\begin{array}
[c]{ccccc}%
n-1 & -1 & -1 & \cdots & -1\\
-1 & n-1 & -1 & \cdots & -1\\
-1 & -1 & n-1 & \cdots & -1\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
-1 & -1 & -1 & \cdots & n-1
\end{array}
\right)  _{\left(  n-2\right)  \times\left(  n-2\right)  }\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we expanded the determinant along the last row,}\\
\text{which gave us only one cofactor because the last row}\\
\text{of }L\text{ has only one nonzero entry}%
\end{array}
\right) \\
&  =\det\left(
\begin{array}
[c]{ccccc}%
n-1 & -1 & -1 & \cdots & -1\\
-n & n & 0 & \cdots & 0\\
-n & 0 & n & \cdots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
-n & 0 & 0 & \cdots & n
\end{array}
\right)  _{\left(  n-2\right)  \times\left(  n-2\right)  }\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have subtracted the first row of the matrix}\\
\text{from each of the other rows}%
\end{array}
\right) \\
&  =n^{n-3}\det\left(
\begin{array}
[c]{ccccc}%
n-1 & -1 & -1 & \cdots & -1\\
-1 & 1 & 0 & \cdots & 0\\
-1 & 0 & 1 & \cdots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
-1 & 0 & 0 & \cdots & 1
\end{array}
\right)  _{\left(  n-2\right)  \times\left(  n-2\right)  }\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have factored out an }n\text{ from each row of the}\\
\text{matrix except of the first row}%
\end{array}
\right) \\
&  =n^{n-3}\underbrace{\det\left(
\begin{array}
[c]{ccccc}%
2 & 0 & 0 & \cdots & 0\\
-1 & 1 & 0 & \cdots & 0\\
-1 & 0 & 1 & \cdots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
-1 & 0 & 0 & \cdots & 1
\end{array}
\right)  _{\left(  n-2\right)  \times\left(  n-2\right)  }}_{\substack{=2\cdot
1\cdot1\cdot\cdots\cdot1\\\text{(since the determinant of a lower-triangular}%
\\\text{matrix equals the product of its diagonal entries)}}}\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have added each row of the matrix except of}\\
\text{the first row to the first row}%
\end{array}
\right) \\
&  =n^{n-3}\cdot\left(  2\cdot1\cdot1\cdot\cdots\cdot1\right)  =2n^{n-3}.
\end{align*}


Thus, Theorem \ref{thm.endofunctions.MTT.1} yields%
\[
\sum_{\substack{f:S\rightarrow S;\\f^{n}\left(  S\right)  =\left\{  n\right\}
}}\prod_{i\in\left[  n-1\right]  }a_{i,f\left(  i\right)  }=\det L=2n^{n-3}.
\]
Comparing this with%
\begin{align*}
&  \sum_{\substack{f:S\rightarrow S;\\f^{n}\left(  S\right)  =\left\{
n\right\}  }}\prod_{i\in\left[  n-1\right]  }\underbrace{a_{i,f\left(
i\right)  }}_{\substack{=\left[  i\neq n-1\text{ or }f\left(  i\right)
=n\right]  \\\text{(by the definition of }a_{i,f\left(  i\right)  }\text{)}%
}}\\
&  =\sum_{\substack{f:S\rightarrow S;\\f^{n}\left(  S\right)  =\left\{
n\right\}  }}\underbrace{\prod_{i\in\left[  n-1\right]  }\left[  i\neq
n-1\text{ or }f\left(  i\right)  =n\right]  }_{\substack{=\left(  \prod
_{i\in\left[  n-2\right]  }\left[  i\neq n-1\text{ or }f\left(  i\right)
=n\right]  \right)  \cdot\left[  n-1\neq n-1\text{ or }f\left(  n-1\right)
=n\right]  \\\text{(here, we have split off the factor for }i=n-1\text{ from
the product)}}}\\
&  =\sum_{\substack{f:S\rightarrow S;\\f^{n}\left(  S\right)  =\left\{
n\right\}  }}\left(  \prod_{i\in\left[  n-2\right]  }\underbrace{\left[  i\neq
n-1\text{ or }f\left(  i\right)  =n\right]  }_{\substack{=1\\\text{(since
}i\neq n-1\text{)}}}\right)  \cdot\underbrace{\left[  n-1\neq n-1\text{ or
}f\left(  n-1\right)  =n\right]  }_{\substack{=\left[  f\left(  n-1\right)
=n\right]  \\\text{(since }n-1\neq n-1\text{ does not hold)}}}\\
&  =\sum_{\substack{f:S\rightarrow S;\\f^{n}\left(  S\right)  =\left\{
n\right\}  }}\underbrace{\left(  \prod_{i\in\left[  n-2\right]  }1\right)
}_{=1}\cdot\left[  f\left(  n-1\right)  =n\right]  =\sum
_{\substack{f:S\rightarrow S;\\f^{n}\left(  S\right)  =\left\{  n\right\}
}}\left[  f\left(  n-1\right)  =n\right] \\
&  =\sum_{\substack{f:S\rightarrow S;\\f^{n}\left(  S\right)  =\left\{
n\right\}  ;\\f\left(  n-1\right)  =n}}\underbrace{\left[  f\left(
n-1\right)  =n\right]  }_{\substack{=1\\\text{(since }f\left(  n-1\right)
=n\text{)}}}+\sum_{\substack{f:S\rightarrow S;\\f^{n}\left(  S\right)
=\left\{  n\right\}  ;\\f\left(  n-1\right)  \neq n}}\underbrace{\left[
f\left(  n-1\right)  =n\right]  }_{\substack{=0\\\text{(since }f\left(
n-1\right)  \neq n\text{)}}}\\
&  =\sum_{\substack{f:S\rightarrow S;\\f^{n}\left(  S\right)  =\left\{
n\right\}  ;\\f\left(  n-1\right)  =n}}1+\underbrace{\sum
_{\substack{f:S\rightarrow S;\\f^{n}\left(  S\right)  =\left\{  n\right\}
;\\f\left(  n-1\right)  \neq n}}0}_{=0}=\sum_{\substack{f:S\rightarrow
S;\\f^{n}\left(  S\right)  =\left\{  n\right\}  ;\\f\left(  n-1\right)
=n}}1\\
&  =\left\vert \left\{  f:S\rightarrow S\ \mid\ f^{n}\left(  S\right)
=\left\{  n\right\}  \text{ and }f\left(  n-1\right)  =n\right\}  \right\vert
\cdot1\\
&  =\left\vert \left\{  f:S\rightarrow S\ \mid\ f^{n}\left(  S\right)
=\left\{  n\right\}  \text{ and }f\left(  n-1\right)  =n\right\}  \right\vert
\\
&  =\left\vert \underbrace{\left\{  f:S\rightarrow S\ \mid\ f\left(
n-1\right)  =n\text{ and }f^{n}\left(  S\right)  =\left\{  n\right\}
\right\}  }_{\substack{=A_{n-1,n}\\\text{(by the definition of }%
A_{n-1,n}\text{)}}}\right\vert =\left\vert A_{n-1,n}\right\vert ,
\end{align*}
we obtain $\left\vert A_{n-1,n}\right\vert =2n^{n-3}$. As we have explained,
this solves part \textbf{(a)} of the exercise.

\bigskip

\textit{Second solution to part \textbf{(a)}:} I shall \textbf{not} follow the
hint this time. Instead, let me recall a fact proven in class (during the
proof of Theorem 5.2 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-05.pdf}{the
class notes from 2018-11-05}):

\begin{proposition}
\label{prop.endofunctions.tree-for-count.1}Let $n\geq1$, and set $S=\left[
n\right]  $. For each subset $T$ of $S$, we set
\begin{equation}
\Phi\left(  T\right)  =\left\{  f:S\rightarrow S\ \mid\ f^{n}\left(  S\right)
\subseteq T\text{ and }T\subseteq\operatorname*{Fix}f\right\}  ,
\label{eq.prop.endofunctions.tree-for-count.1.1}%
\end{equation}
where $\operatorname*{Fix}f:=\left\{  x\in S\ \mid\ f\left(  x\right)
=x\right\}  $.

Then, there are integers $g_{0},g_{1},\ldots,g_{n}$ such that%
\begin{equation}
g_{i}=\left\vert \Phi\left(  T\right)  \right\vert \qquad\text{for every
}i\text{-element subset }T\text{ of }S\text{,}
\label{eq.prop.endofunctions.tree-for-count.1.2}%
\end{equation}
and these integers are given by%
\begin{equation}
g_{k}=kn^{n-k-1}\qquad\text{for each }k\in\left\{  0,1,\ldots,n\right\}  .
\label{eq.prop.endofunctions.tree-for-count.1.3}%
\end{equation}

\end{proposition}

Consider the integers $g_{0},g_{1},\ldots,g_{n}$ from Proposition
\ref{prop.endofunctions.tree-for-count.1}. Applying
(\ref{eq.prop.endofunctions.tree-for-count.1.3}) to $k=2$, we obtain
$g_{2}=2n^{n-2-1}=2n^{n-3}$.

Also, let us introduce another notation: If $f:S\rightarrow S$ is any map, and
if $a$ and $b$ are any two elements of $S$, then
\[
\left(  f\text{ but }a\mapsto b\right)
\]
shall denote the map from $S$ to $S$ that sends each $s\in S$ to $%
\begin{cases}
f\left(  s\right)  , & \text{if }s\neq a;\\
b, & \text{if }s=a.
\end{cases}
$ In other words, the map $\left(  f\text{ but }a\mapsto b\right)  $ differs
from $f$ only in that it sends $a$ to $b$.

Now, fix $i\in\left[  n-1\right]  $. Let $T$ be the subset $\left\{
i,n\right\}  $ of $S$. Then, $T$ is a $2$-element subset (since $i\neq n$
(because $i\in\left[  n-1\right]  $)); thus,
\eqref{eq.prop.endofunctions.tree-for-count.1.2} (applied to $i=2$) yields
$g_{2}=\left\vert \Phi\left(  T\right)  \right\vert $. Hence, $\left\vert
\Phi\left(  T\right)  \right\vert =g_{2}=2n^{n-3}$. The definition of
$\Phi\left(  T\right)  $ yields%
\begin{align*}
\Phi\left(  T\right)   &  =\left\{  f:S\rightarrow S\ \mid\ f^{n}\left(
S\right)  \subseteq T\text{ and }T\subseteq\operatorname*{Fix}f\right\} \\
&  =\left\{  f:S\rightarrow S\ \mid\ f^{n}\left(  S\right)  \subseteq\left\{
i,n\right\}  \text{ and }\left\{  i,n\right\}  \subseteq\operatorname*{Fix}%
f\right\}  \qquad\left(  \text{since }T=\left\{  i,n\right\}  \right) \\
&  =\left\{  f:S\rightarrow S\ \mid\ f^{n}\left(  S\right)  \subseteq\left\{
i,n\right\}  \text{ and }f\left(  i\right)  =i\text{ and }f\left(  n\right)
=n\right\}  .
\end{align*}


The definition of $A_{i,n}$ yields%
\begin{equation}
A_{i,n}=\left\{  f:S\rightarrow S\ \mid\ f\left(  i\right)  =n\text{ and
}f^{n}\left(  S\right)  =\left\{  n\right\}  \right\}  .
\label{sol.endofunctions.nn-3.4}%
\end{equation}
It is easy to see that the map%
\begin{align*}
\Phi\left(  T\right)   &  \rightarrow A_{i,n},\\
f  &  \mapsto\left(  f\text{ but }i\mapsto n\right)
\end{align*}
is well-defined\footnote{To prove this, you need to show that every $f\in
\Phi\left(  T\right)  $ satisfies $\left(  f\text{ but }i\mapsto n\right)
\left(  i\right)  =n$ and $\left(  f\text{ but }i\mapsto n\right)  ^{n}\left(
S\right)  =\left\{  n\right\}  $. The first of these two equalities is
obvious. The second can be argued (roughly speaking) as follows: Since
$f\in\Phi\left(  T\right)  $, we have $f^{n}\left(  S\right)  \subseteq
\left\{  i,n\right\}  $; hence, each element of $S$ will eventually reach
either $i$ or $n$ when we apply $f$ to it many times. Thus, if we keep
applying $\left(  f\text{ but }i\mapsto n\right)  $ to it instead of $f$, it
will eventually reach $n$ (because it will move in the same way as if we apply
$f$ to it, unless and until it reaches $i$; but at that point, $\left(
f\text{ but }i\mapsto n\right)  $ will send it directly to $n$). Hence,
$\left(  f\text{ but }i\mapsto n\right)  ^{n}\left(  S\right)  =\left\{
n\right\}  $, qed.}. It is also easy to see that the map%
\begin{align*}
A_{i,n}  &  \rightarrow\Phi\left(  T\right)  ,\\
f  &  \mapsto\left(  f\text{ but }i\mapsto i\right)
\end{align*}
is well-defined. Furthermore, these two maps are mutually inverse (since each
$f\in\Phi\left(  T\right)  $ sends $i$ to $i$, while each $f\in A_{i,n}$ sends
$i$ to $n$). Thus, these maps are bijections. Hence, we have found a bijection
from $A_{i,n}$ to $\Phi\left(  T\right)  $. Thus, $\left\vert A_{i,n}%
\right\vert =\left\vert \Phi\left(  T\right)  \right\vert =2n^{n-3}$. In view
of \eqref{sol.endofunctions.nn-3.4}, this rewrites as%
\[
\left\vert \left\{  f:S\rightarrow S\ \mid\ f\left(  i\right)  =n\text{ and
}f^{n}\left(  S\right)  =\left\{  n\right\}  \right\}  \right\vert =2n^{n-3}.
\]
In other words, the number of maps $f:S\rightarrow S$ with $f\left(  i\right)
=n$ and $f^{n}\left(  S\right)  =\left\{  n\right\}  $ is $2n^{n-3}$. This
solves part \textbf{(a)} of the exercise again.

\bigskip

\textbf{(b)} While it is certainly possible to solve part \textbf{(b)} using
the Matrix-Tree Theorem (as we did with part \textbf{(a)}), it is also more
complicated than what we did above. Fortunately, there is a simpler approach:

As we know, part \textbf{(b)} of the exercise is equivalent to saying that
$\left\vert A_{i,j}\right\vert =n^{n-3}$ for any $i\in\left[  n-1\right]  $
and $j\in\left[  n-1\right]  $ satisfying $i\neq j$. Thus, it suffices to
prove that $\left\vert A_{i,j}\right\vert =n^{n-3}$ for any $i\in\left[
n-1\right]  $ and $j\in\left[  n-1\right]  $ satisfying $i\neq j$.

Fix $i\in\left[  n-1\right]  $. We must thus show that $\left\vert
A_{i,j}\right\vert =n^{n-3}$ for any $j\in\left[  n-1\right]  $ satisfying
$i\neq j$.

We notice that the specific value of the number $j$ is irrelevant (as long as
$i\neq j$ holds): If $j_{1}$ and $j_{2}$ are two elements of $\left[
n-1\right]  $ such that $i\neq j_{1}$ and $i\neq j_{2}$, then
\begin{equation}
\left\vert A_{i,j_{1}}\right\vert =\left\vert A_{i,j_{2}}\right\vert
\label{sol.endofunctions.nn-3.b.symmetry}%
\end{equation}
\footnote{\textit{Proof.} Let $j_{1}$ and $j_{2}$ be two elements of $\left[
n-1\right]  $ satisfying $i\neq j_{1}$ and $i\neq j_{2}$. We must prove that
$\left\vert A_{i,j_{1}}\right\vert =\left\vert A_{i,j_{2}}\right\vert $. If
$j_{1}=j_{2}$, then this is obvious. Thus, WLOG assume that $j_{1}\neq j_{2}$.
Hence, the transposition $t_{j_{1},j_{2}}\in S_{n}$ is well-defined. Clearly,
both $i$ and $n$ are fixed points of $t_{j_{1},j_{2}}$ (since $i\neq j_{1}$
and $i\neq j_{2}$ and $j_{1},j_{2}\in\left[  n-1\right]  $), and
$t_{j_{1},j_{2}}$ is an involution. Now, it is easy to see that the map%
\[
A_{i,j_{1}}\rightarrow A_{i,j_{2}},\qquad f\mapsto t_{j_{1},j_{2}}\circ f\circ
t_{j_{1},j_{2}}%
\]
is well-defined (after all, it simply interchanges the roles of $j_{1}$ and
$j_{2}$, so that it sends a map $f$ satisfying $f\left(  i\right)  =j_{1}$ to
a map $f$ satisfying $f\left(  i\right)  =j_{2}$ without disrupting the
\textquotedblleft$f^{n}\left(  S\right)  =\left\{  n\right\}  $%
\textquotedblright\ behavior) and is a bijection (its inverse map is defined
in the same way). Thus, $\left\vert A_{i,j_{1}}\right\vert =\left\vert
A_{i,j_{2}}\right\vert $, qed.}. Furthermore, $A_{i,i}=\varnothing$ (indeed,
any $f\in A_{i,i}$ would have to satisfy both $f\left(  i\right)  =i$ and
$f^{n}\left(  S\right)  =\left\{  n\right\}  $; but these two equalities
contradict each other\footnote{Indeed, the equality $f\left(  i\right)  =i$
leads to $f^{k}\left(  i\right)  =i$ for all $k\in\mathbb{N}$; thus,
$f^{n}\left(  i\right)  =i\notin\left\{  n\right\}  $, which contradicts
$f^{n}\left(  \underbrace{i}_{\in S}\right)  \in f^{n}\left(  S\right)
=\left\{  n\right\}  $.}), and thus $\left\vert A_{i,i}\right\vert =0$.

Now, let $j\in\left[  n-1\right]  $ be such that $i\neq j$. We must prove that
$\left\vert A_{i,j}\right\vert =n^{n-3}$. Note that $i$ and $j$ are two
distinct elements of the set $\left[  n-1\right]  $ (since $i\neq j$); thus,
this set $\left[  n-1\right]  $ has at least two elements. In other words,
$\left\vert \left[  n-1\right]  \right\vert \geq2$. Thus, $n-1=\left\vert
\left[  n-1\right]  \right\vert \geq2$, so that $n\geq3$. Hence, $n-2\neq0$.

We have $i\in\left[  n-1\right]  $. Hence, we can split off the addend for
$u=i$ from the sum $\sum_{u\in\left[  n-1\right]  }\left\vert A_{i,u}%
\right\vert $. We thus obtain%
\begin{align}
\sum_{u\in\left[  n-1\right]  }\left\vert A_{i,u}\right\vert  &
=\underbrace{\left\vert A_{i,i}\right\vert }_{=0}+\sum_{\substack{u\in\left[
n-1\right]  ;\\u\neq i}}\underbrace{\left\vert A_{i,u}\right\vert
}_{\substack{=\left\vert A_{i,j}\right\vert \\\text{(by
\eqref{sol.endofunctions.nn-3.b.symmetry}, applied to }j_{1}=u\\\text{and
}j_{2}=j\text{)}}}=\sum_{\substack{u\in\left[  n-1\right]  ;\\u\neq
i}}\left\vert A_{i,j}\right\vert \nonumber\\
&  =\left(  n-2\right)  \left\vert A_{i,j}\right\vert
\label{sol.endofunctions.nn-3.b.4}%
\end{align}
(since the number of $u\in\left[  n-1\right]  $ satisfying $u\neq i$ is
$n-2$). But each $u\in\left[  n\right]  $ satisfies%
\[
A_{i,u}=\left\{  f:S\rightarrow S\ \mid\ f\left(  i\right)  =u\text{ and
}f^{n}\left(  S\right)  =\left\{  n\right\}  \right\}
\]
(by the definition of $A_{i,u}$). Thus, the $n$ sets $A_{i,1},A_{i,2}%
,\ldots,A_{i,n}$ are disjoint, and their union is $\left\{  f:S\rightarrow
S\ \mid\ f^{n}\left(  S\right)  =\left\{  n\right\}  \right\}  $. Hence,%
\begin{align*}
\left\vert A_{i,1}\right\vert +\left\vert A_{i,2}\right\vert +\cdots
+\left\vert A_{i,n}\right\vert  &  =\left\vert \left\{  f:S\rightarrow
S\ \mid\ f^{n}\left(  S\right)  =\left\{  n\right\}  \right\}  \right\vert \\
&  =\left(  \text{the number of maps }f:S\rightarrow S\text{ satisfying }%
f^{n}\left(  S\right)  =\left\{  n\right\}  \right) \\
&  =n^{n-2}%
\end{align*}
(by Theorem 5.2 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-05.pdf}{the
class notes from 2018-11-05}). Hence,%
\begin{align*}
n^{n-2}  &  =\left\vert A_{i,1}\right\vert +\left\vert A_{i,2}\right\vert
+\cdots+\left\vert A_{i,n}\right\vert =\sum_{u\in\left[  n\right]  }\left\vert
A_{i,u}\right\vert =\underbrace{\sum_{u\in\left[  n-1\right]  }\left\vert
A_{i,u}\right\vert }_{\substack{=\left(  n-2\right)  \left\vert A_{i,j}%
\right\vert \\\text{(by \eqref{sol.endofunctions.nn-3.b.4})}}%
}+\underbrace{\left\vert A_{i,n}\right\vert }_{\substack{=2n^{n-3}\\\text{(by
part \textbf{(a)}}\\\text{of the exercise)}}}\\
&  \qquad\left(  \text{here, we have split off the addend for }u=n\text{ from
the sum}\right) \\
&  =\left(  n-2\right)  \left\vert A_{i,j}\right\vert +2n^{n-3}.
\end{align*}
We can solve this equation for $\left\vert A_{i,j}\right\vert $ (since
$n-2\neq0$), and obtain $\left\vert A_{i,j}\right\vert =\dfrac{n^{n-2}%
-2n^{n-3}}{n-2}=\dfrac{\left(  n-2\right)  n^{n-3}}{n-2}=n^{n-3}$. This is
exactly what we wanted to show. Thus, part \textbf{(b)} of the exercise is solved.

%----------------------------------------------------------------------------------------
%	EXERCISE 5
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 5}

\subsection{Problem}

\begin{enumerate}
\item[\textbf{(a)}] For each $n \in\mathbb{N}$, prove that the number of
fixed-point-free involutions $\left[  n \right]  \to\left[  n \right]  $ is
\[%
\begin{cases}
1 \cdot3 \cdot5 \cdot\cdots\cdot\left(  n-1 \right)  , & \text{ if $n$ is
even};\\
0, & \text{ if $n$ is odd} .
\end{cases}
\]


\item[\textbf{(b)}] For each $n \in\mathbb{N}$, we let $t_{n}$ be the number
of all involutions in $S_{n}$. Prove that
\[
t_{n} = \sum_{k=0}^{n} \dbinom{n}{2k} \left(  1 \cdot3 \cdot5 \cdot\cdots
\cdot\left(  2k-1 \right)  \right)  \qquad\text{for each $n \in\mathbb{N}$}.
\]


\item[\textbf{(c)}] For each $n \in\mathbb{N}$, prove that the number of maps
$f : \left[  n \right]  \to\left[  n \right]  $ satisfying $f^{3} = f$ is
\[
\sum_{k=0}^{n} \binom{n}{k} k^{n-k} t_{k} .
\]

\end{enumerate}

\subsection{Remark}

The numbers in part \textbf{(a)} form the
\href{https://oeis.org/A123023}{sequence A123023 in the OEIS}. (And if you
omit the terms for odd $n$, which are all zero, then you obtain
\href{https://oeis.org/A001147}{sequence A001147}, known as the \textit{double
factorials}.)

The numbers $t_{0}, t_{1}, t_{2}, \ldots$ in part \textbf{(b)} are sometimes
called the \textit{telephone numbers}, because an involution in $S_{n}$ is a
way how phone calls can be happening between $n$ people $1, 2, \ldots, n$,
assuming there are no conference calls. This is
\href{https://oeis.org/A000085}{sequence A000085 in the OEIS}.

Finally, the numbers in part \textbf{(c)} form
\href{https://oeis.org/A060905}{sequence A060905}.

\subsection{Solution sketch}

\textbf{(a)} \textit{First solution to part \textbf{(a)} (sketched):} The
fixed-point-free involutions $\left[  n\right]  \rightarrow\left[  n\right]  $
are precisely the derangements in $S_{n}$ that are also involutions. But the
latter derangements have been counted in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018may2.pdf}{UMN
Spring 2018 Math 4707 notes from 2018-05-02} (pages 9--20).

\textit{Second solution to part \textbf{(a)} (sketched):} We WLOG assume that
$n\geq2$, since the cases when $n<2$ are trivial to check.

The fixed-point-free involutions $\left[  n\right]  \rightarrow\left[
n\right]  $ are precisely the permutations $\sigma\in S_{n}$ whose cycles are
all $2$-cycles (because any cycle of length $>2$ would prevent $\sigma$ from
being an involution, whereas any cycle of length $<2$ would prevent $\sigma$
from being fixed-point-free). Thus, they are precisely the permutations
$\sigma\in S_{n}$ that have exactly $n/2$ many $2$-cycles and no cycles of any
other length\footnote{Indeed, if the cycles of $\sigma$ are all $2$-cycles,
then there must be exactly $n/2$ of these $2$-cycles (since each of the $n$
elements of $\left[  n\right]  $ must be caught up in exactly $1$ of these
$2$-cycles, but each $2$-cycle catches exactly two elements of $\left[
n\right]  $).}. Thus, if $n$ is odd, then there exist no such involutions
(since $n/2$ is not an integer in this case), i.e., their number is $0$. For
the same reason, if $n$ is even, we have%
\begin{align*}
&  \left(  \text{the number of fixed-point-free involutions }\left[  n\right]
\rightarrow\left[  n\right]  \right) \\
&  =\left(  \text{the number of permutations }\sigma\in S_{n}\text{ that have
exactly }n/2\text{ many }2\text{-cycles}\right. \\
&  \qquad\qquad\left.  \text{and no cycles of any other length}\right) \\
&  =\dfrac{n!}{0!\left(  n/2\right)  !0!0!\cdots0!1^{0}2^{n/2}3^{0}4^{0}\cdots
n^{0}}\qquad\left(
\begin{array}
[c]{c}%
\text{by the exercise on pages 234--236}\\
\text{of
\text{\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-10-24.pdf}{\text{the
2018-10-24 notes}}}}%
\end{array}
\right) \\
&  =\dfrac{n!}{\left(  n/2\right)  !2^{n/2}}\qquad\left(  \text{since
}0!=1\text{ and }k^{0}=1\text{ for each }k\in\mathbb{Z}\right) \\
&  =\dfrac{1}{2^{n/2}}\cdot\dfrac{1}{\left(  n/2\right)  !}\cdot
\underbrace{n!}_{\substack{=1\cdot2\cdot\cdots\cdot n\\=\left(  1\cdot
3\cdot5\cdot\cdots\cdot\left(  n-1\right)  \right)  \cdot\left(  2\cdot
4\cdot6\cdot\cdots\cdot n\right)  \\\text{(since }n\text{ is even)}}}\\
&  =\dfrac{1}{2^{n/2}}\cdot\dfrac{1}{\left(  n/2\right)  !}\cdot\left(
1\cdot3\cdot5\cdot\cdots\cdot\left(  n-1\right)  \right)  \cdot
\underbrace{\left(  2\cdot4\cdot6\cdot\cdots\cdot n\right)  }_{=2^{n/2}%
\cdot\left(  1\cdot2\cdot3\cdot\cdots\cdot\left(  n/2\right)  \right)  }\\
&  =\dfrac{1}{2^{n/2}}\cdot\dfrac{1}{\left(  n/2\right)  !}\cdot\left(
1\cdot3\cdot5\cdot\cdots\cdot\left(  n-1\right)  \right)  \cdot2^{n/2}%
\cdot\left(  1\cdot2\cdot3\cdot\cdots\cdot\left(  n/2\right)  \right) \\
&  =\dfrac{1}{\left(  n/2\right)  !}\cdot\left(  1\cdot3\cdot5\cdot\cdots
\cdot\left(  n-1\right)  \right)  \cdot\underbrace{\left(  1\cdot2\cdot
3\cdot\cdots\cdot\left(  n/2\right)  \right)  }_{=\left(  n/2\right)
!}=1\cdot3\cdot5\cdot\cdots\cdot\left(  n-1\right)  .
\end{align*}
Combining the claims in the previous two sentences, we conclude that part
\textbf{(a)} of the exercise is solved.

\textbf{(b)} Let $n\in\mathbb{N}$. To construct an involution $\sigma\in
S_{n}$, we can use the following algorithm:

\begin{itemize}
\item First choose the number $m$ of fixed points of $\sigma$; this must be a
number in $\left\{  0,1,\ldots,n\right\}  $.

\item Next, choose the set $P$ of all fixed points of $\sigma$; this must be
an $m$-element subset of $\left[  n\right]  $. There are $\dbinom{n}{m}$ ways
of choosing this subset $P$.

\item Note that $\left\vert P\right\vert =m$ and thus $\left\vert \left[
n\right]  \setminus P\right\vert =n-m$.

\item Now, the values $\sigma\left(  p\right)  $ for all $p\in P$ are already
determined (indeed, we must have $\sigma\left(  p\right)  =p$ for all $p\in
P$, since $P$ should be the set of all fixed points of $\sigma$), and we have
$\sigma\left(  P\right)  =P$. Thus, it remains to choose the values
$\sigma\left(  q\right)  $ for $q\in\left[  n\right]  \setminus P$. Since
$\sigma$ should be a permutation, we must have $\sigma\left(  \left[
n\right]  \setminus P\right)  =\left[  n\right]  \setminus\underbrace{\sigma
\left(  P\right)  }_{=P}=\left[  n\right]  \setminus P$; therefore, these
values $\sigma\left(  q\right)  $ must belong to $\left[  n\right]  \setminus
P$. Thus, the restriction of $\sigma$ to $\left[  n\right]  \setminus P$
should be a permutation of $\left[  n\right]  \setminus P$. This permutation
should be an involution (since $\sigma$ should be an involution) and should be
fixed-point-free (since we want $P$ to be the set of all fixed points of
$\sigma$, and thus any fixed points of $\sigma$ must lie in $P$). Thus, the
restriction of $\sigma$ to $\left[  n\right]  \setminus P$ should be a
fixed-point-free involution of $\left[  n\right]  \setminus P$. Hence, the
number of ways of choosing this restriction (i.e., choosing the values
$\sigma\left(  q\right)  $ for $q\in\left[  n\right]  \setminus P$) is%
\begin{align*}
&  \left(  \text{the number of all fixed-point-free involutions of }\left[
n\right]  \setminus P\right) \\
&  =\left(  \text{the number of all fixed-point-free involutions of }\left[
n-m\right]  \right) \\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{since there is a bijection between }\left[  n\right]  \setminus P\text{
and }\left[  n-m\right] \\
\text{(because }\left\vert \left[  n\right]  \setminus P\right\vert
=n-m\text{)}%
\end{array}
\right) \\
&  =%
\begin{cases}
1\cdot3\cdot5\cdot\cdots\cdot\left(  \left(  n-m\right)  -1\right)  , & \text{
if }n-m\text{ is even};\\
0, & \text{ if }n-m\text{ is odd}%
\end{cases}
\\
&  \qquad\left(  \text{by part \textbf{(a)} of this exercise, applied to
}n-m\text{ instead of }n\right)  .
\end{align*}

\end{itemize}

Hence, the total number of involutions $\sigma\in S_{n}$ is%
\begin{align*}
&  \sum_{m\in\left\{  0,1,\ldots,n\right\}  }\dbinom{n}{m}%
\begin{cases}
1\cdot3\cdot5\cdot\cdots\cdot\left(  \left(  n-m\right)  -1\right)  , & \text{
if }n-m\text{ is even};\\
0, & \text{ if }n-m\text{ is odd}%
\end{cases}
\\
&  =\sum_{\substack{m\in\left\{  0,1,\ldots,n\right\}  ;\\n-m\text{ is even}%
}}\dbinom{n}{m}\left(  1\cdot3\cdot5\cdot\cdots\cdot\left(  \left(
n-m\right)  -1\right)  \right) \\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have removed the addends for which }n-m\text{ is odd,}\\
\text{since these addends are }0
\end{array}
\right) \\
&  =\sum_{\substack{m\in\left\{  0,1,\ldots,n\right\}  ;\\m\text{ is even}%
}}\underbrace{\dbinom{n}{n-m}}_{=\dbinom{n}{m}}\left(  1\cdot3\cdot
5\cdot\cdots\cdot\left(  m-1\right)  \right) \\
&  \qquad\left(  \text{here, we have substituted }m\text{ for }n-m\text{ in
the sum}\right) \\
&  =\sum_{\substack{m\in\left\{  0,1,\ldots,n\right\}  ;\\m\text{ is even}%
}}\dbinom{n}{m}\left(  1\cdot3\cdot5\cdot\cdots\cdot\left(  m-1\right)
\right) \\
&  =\sum_{\substack{m\in\left\{  0,1,\ldots,2n\right\}  ;\\m\text{ is even}%
}}\dbinom{n}{m}\left(  1\cdot3\cdot5\cdot\cdots\cdot\left(  m-1\right)
\right) \\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have extended the sum by loosening}\\
\text{the \textquotedblleft}m\in\left\{  0,1,\ldots,n\right\}
\text{\textquotedblright\ condition to \textquotedblleft}m\in\left\{
0,1,\ldots,2n\right\}  \text{\textquotedblright;}\\
\text{this did not affect the value of the sum, since}\\
\text{all addends with }m>n\text{ are }0
\end{array}
\right) \\
&  =\sum_{k=0}^{n}\dbinom{n}{2k}\left(  1\cdot3\cdot5\cdot\cdots\cdot\left(
2k-1\right)  \right) \\
&  \qquad\left(  \text{here, we have substituted }2k\text{ for }m\text{ in the
sum}\right)  .
\end{align*}
In other words, $t_{n}=\sum_{k=0}^{n}\dbinom{n}{2k}\left(  1\cdot3\cdot
5\cdot\cdots\cdot\left(  2k-1\right)  \right)  $ (since $t_{n}$ is the number
of involutions $\sigma\in S_{n}$). This solves part \textbf{(b)} of the exercise.

\textbf{(c)} It is easy to see that a map $f:\left[  n\right]  \rightarrow
\left[  n\right]  $ satisfies $f^{3}=f$ if and only if its restriction
$f\mid_{f\left(  \left[  n\right]  \right)  }$ (to its own image) is an
involution. Thus, any map $f:\left[  n\right]  \rightarrow\left[  n\right]  $
satisfying $f^{3}=f$ can be constructed as follows:

\begin{itemize}
\item Choose the size $k$ of its image $f\left(  \left[  n\right]  \right)  $;
this is an integer in $\left\{  0,1,\ldots,n\right\}  $.

\item Then choose this image $f\left(  \left[  n\right]  \right)  $ as a
$k$-element subset of $\left[  n\right]  $; there are $\dbinom{n}{k}$ choices
for this subset.

\item Then choose the restriction $f\mid_{f\left(  \left[  n\right]  \right)
}$ as an involution of $f\left(  \left[  n\right]  \right)  $; there are
$t_{k}$ choices for this involution\footnote{Indeed, $f\left(  \left[
n\right]  \right)  $ is a $k$-element set, and thus there exists a bijection
between $f\left(  \left[  n\right]  \right)  $ and $\left[  k\right]  $.
Hence, the number of involutions of $f\left(  \left[  n\right]  \right)  $
equals the number of involutions of $\left[  k\right]  $. But the latter
number is precisely $t_{k}$ (by the definition of $t_{k}$). Hence, the number
of involutions of $f\left(  \left[  n\right]  \right)  $ is $t_{k}$.}.

\item Finally, choose the values of $f$ on the $n-k$ elements of $\left[
n\right]  \setminus f\left(  \left[  n\right]  \right)  $. These values must
belong to $f\left(  \left[  n\right]  \right)  $, so we have $k^{n-k}$ choices
here (because $f\left(  \left[  n\right]  \right)  $ is a $k$-element set).
\end{itemize}

Hence, the total number of maps $f:\left[  n\right]  \rightarrow\left[
n\right]  $ satisfying $f^{3}=f$ is
\[
\sum_{k=0}^{n}\binom{n}{k}t_{k}k^{n-k}=\sum_{k=0}^{n}\binom{n}{k}k^{n-k}%
t_{k}.
\]


%----------------------------------------------------------------------------------------
%	EXERCISE 6
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 6}

\subsection{Problem}

%\# desarrangements = \# derangements, incl. generalization:


Let $n$ be a positive integer, and let $p \in\left\{  0, 1, \ldots, n
\right\}  $.

A permutation $\sigma\in S_{n}$ shall be called a \textit{$p$-desarrangement}
if it satisfies
\[
\text{ \textbf{either} } \left(  \sigma= \operatorname{id} \text{ and } 2 \mid
n \right)  \text{ \textbf{or} } \sigma\left(  1 \right)  \leq p \text{
\textbf{or} } \left(  \sigma\neq\operatorname{id} \text{ and } 2 \mid
\min\left(  \operatorname{Des} \sigma\right)  \right)  .
\]
(The condition $2 \mid\min\left(  \operatorname{Des} \sigma\right)  $ means
that the smallest descent of $\sigma$ is even.\footnote{Here are all
permutations $\sigma\neq\operatorname{id}$ in $S_{5}$ that satisfy this
condition (written in one-line notation, with an underline marking the
position of the smallest descent):
\begin{align*}
\left[  1, 2, 3, \underline{5}, 4 \right]  , \qquad\left[  1, 2, 4,
\underline{5}, 3 \right]  , \qquad\left[  1, \underline{3}, 2, 4, 5 \right]  ,
\qquad\left[  1, \underline{3}, 2, 5, 4 \right]  , \qquad\left[  1, 3, 4,
\underline{5}, 2 \right]  ,\\
\left[  1, \underline{4}, 2, 3, 5 \right]  , \qquad\left[  1, \underline{4},
2, 5, 3 \right]  , \qquad\left[  1, \underline{4}, 3, 2, 5 \right]  ,
\qquad\left[  1, \underline{4}, 3, 5, 2 \right]  , \qquad\left[  1,
\underline{5}, 2, 3, 4 \right]  ,\\
\left[  1, \underline{5}, 2, 4, 3 \right]  , \qquad\left[  1, \underline{5},
3, 2, 4 \right]  , \qquad\left[  1, \underline{5}, 3, 4, 2 \right]  ,
\qquad\left[  1, \underline{5}, 4, 2, 3 \right]  , \qquad\left[  1,
\underline{5}, 4, 3, 2 \right]  ,\\
\left[  2, \underline{3}, 1, 4, 5 \right]  , \qquad\left[  2, \underline{3},
1, 5, 4 \right]  , \qquad\left[  2, 3, 4, \underline{5}, 1 \right]  ,
\qquad\left[  2, \underline{4}, 1, 3, 5 \right]  , \qquad\left[  2,
\underline{4}, 1, 5, 3 \right]  ,\\
\left[  2, \underline{4}, 3, 1, 5 \right]  , \qquad\left[  2, \underline{4},
3, 5, 1 \right]  , \qquad\left[  2, \underline{5}, 1, 3, 4 \right]  ,
\qquad\left[  2, \underline{5}, 1, 4, 3 \right]  , \qquad\left[  2,
\underline{5}, 3, 1, 4 \right]  ,\\
\left[  2, \underline{5}, 3, 4, 1 \right]  , \qquad\left[  2, \underline{5},
4, 1, 3 \right]  , \qquad\left[  2, \underline{5}, 4, 3, 1 \right]  ,
\qquad\left[  3, \underline{4}, 1, 2, 5 \right]  , \qquad\left[  3,
\underline{4}, 1, 5, 2 \right]  ,\\
\left[  3, \underline{4}, 2, 1, 5 \right]  , \qquad\left[  3, \underline{4},
2, 5, 1 \right]  , \qquad\left[  3, \underline{5}, 1, 2, 4 \right]  ,
\qquad\left[  3, \underline{5}, 1, 4, 2 \right]  , \qquad\left[  3,
\underline{5}, 2, 1, 4 \right]  ,\\
\left[  3, \underline{5}, 2, 4, 1 \right]  , \qquad\left[  3, \underline{5},
4, 1, 2 \right]  , \qquad\left[  3, \underline{5}, 4, 2, 1 \right]  ,
\qquad\left[  4, \underline{5}, 1, 2, 3 \right]  , \qquad\left[  4,
\underline{5}, 1, 3, 2 \right]  ,\\
\left[  4, \underline{5}, 2, 1, 3 \right]  , \qquad\left[  4, \underline{5},
2, 3, 1 \right]  , \qquad\left[  4, \underline{5}, 3, 1, 2 \right]  ,
\qquad\left[  4, \underline{5}, 3, 2, 1 \right]  .
\end{align*}
} This is well-defined, since $\sigma\neq\operatorname{id}$ shows that
$\sigma$ has at least one descent. Further $p$-desarrangements are
$\operatorname{id}$ when $n$ is even, and all permutations starting with a
number $\leq p$ (in one-line notation).)

Prove that the number of $p$-desarrangements in $S_{n}$ is
\[
\sum_{k=0}^{n-p} \dbinom{n-p}{k} \cdot\left(  -1 \right)  ^{k} \left(  n-k
\right)  ! .
\]


\subsection{Remark}

This number is exactly the number of $p$-derangements in $S_{n}$, as defined
in Exercise 5 of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/mt1s.pdf}{midterm \#1}.
This suggests the existence of a bijection between the $p$-desarrangements and
the $p$-derangements. Such a thing has indeed been found in the case when $p =
0$. In this case, the $0$-desarrangements are known as
\textit{desarrangements} (a pun on the name
\href{https://doi.org/10.1016/0097-3165(93)90100-M}{D\'esarmenien} and the
word ``derangement''), whereas the $0$-derangements are precisely the
derangements. The desarrangements are just the permutations $\sigma\in S_{n}$
satisfying either $\sigma= \operatorname{id}$ or $\left(  \sigma
\neq\operatorname{id} \text{ and } 2 \mid\min\left(  \operatorname{Des}
\sigma\right)  \right)  $. One known bijection between the derangements and
the desarrangements proceeds as follows:

\begin{itemize}
\item Let $\sigma\in S_{n}$ be a derangement. We want to define the
corresponding desarrangement $F\left(  \sigma\right)  $.

\item Compute the disjoint cycle decomposition of $\sigma$, and write it in
such a way that each cycle contains its \textbf{largest} entry in its
\textbf{second} position, and that the cycles are ordered in
\textbf{increasing order of their largest entries}. That is, write
\[
\sigma= \operatorname{cyc}_{a_{1, 1}, a_{1, 2}, \ldots, a_{1, n_{1}}}
\operatorname{cyc}_{a_{2, 1}, a_{2, 2}, \ldots, a_{2, n_{2}}} \cdots
\operatorname{cyc}_{a_{k, 1}, a_{k, 2}, \ldots, a_{k, n_{k}}} ,
\]
where each of the numbers $1, 2, \ldots, n$ appears exactly once among the
$a_{i, j}$, and where
\begin{align*}
a_{i, 2}  &  \geq a_{i, j} \qquad\text{ for all } i \text{ and } j,
\qquad\text{and} \qquad a_{1, 2} < a_{2, 2} < \cdots< a_{k, 2} .
\end{align*}


\item Now, let $F\left(  \sigma\right)  $ be the permutation whose one-line
notation is
\[
\left(  a_{1, 1}, a_{1, 2}, \ldots, a_{1, n_{1}}, a_{2, 1}, a_{2, 2}, \ldots,
a_{2, n_{2}}, \ldots, a_{k, 1}, a_{k, 2}, \ldots, a_{k, n_{k}} \right)  .
\]

\end{itemize}

For example, if $n = 7$ and $\sigma= \left[  5, 3, 7, 6, 1, 4, 2 \right]  $ in
one-line notation, then the appropriate representation of $\sigma$ is $\sigma=
\operatorname{cyc}_{1, 5} \operatorname{cyc}_{4, 6} \operatorname{cyc}_{3, 7,
2}$ and thus $F\left(  \sigma\right)  = \left[  1, 5, 4, 6, 3, 7, 2 \right]  $
in one-line notation.

It is far from trivial to check that this is actually a well-defined
bijection. I don't know if anything like that exists for $p \neq0$. Feel free
to explore. (But the simplest way to solve the exercise is not by bijection.)

\subsection{Solution sketch}

Let us introduce some notations first. If $\sigma\in S_{n}$ is any
permutation, then we set $\sigma\left(  k\right)  =0$ for all $k>n$.

For each $k\in\mathbb{N}$, we let%
\[
B_{k}=\left\{  \sigma\in S_{n}\mid p<\sigma\left(  1\right)  <\sigma\left(
2\right)  <\cdots<\sigma\left(  k\right)  \right\}  .
\]
Note that the chain of inequalities $p<\sigma\left(  1\right)  <\sigma\left(
2\right)  <\cdots<\sigma\left(  k\right)  $ is vacuously true when $k=0$;
thus, $B_{0}$ is simply the set $S_{n}$ of all permutations $\sigma\in S_{n}$.
In other words, every $\sigma\in S_{n}$ satisfies $\sigma\in B_{0}$. Also, for
any $k>n$, we have $B_{k}=\varnothing$, because no $\sigma\in S_{n}$ satisfies
$p<\sigma\left(  1\right)  <\sigma\left(  2\right)  <\cdots<\sigma\left(
k\right)  $ (indeed, the last member of this chain of inequalities is
$\sigma\left(  k\right)  =0$, which is not larger than $p$). Thus, the
sequence $\left(  \left\vert B_{0}\right\vert ,\left\vert B_{1}\right\vert
,\left\vert B_{2}\right\vert ,\ldots\right)  $ is finitely supported.

For each $k\in\left\{  0,1,\ldots,n\right\}  $, we have%
\begin{equation}
\left\vert B_{k}\right\vert =\dbinom{n-p}{k}\left(  n-k\right)  ! .
\label{sol.perm.p-desarr.Bk=}%
\end{equation}


[\textit{Proof of \eqref{sol.perm.p-desarr.Bk=}:} Let $k\in\left\{
0,1,\ldots,n\right\}  $. In order to construct a permutation $\sigma\in S_{n}$
satisfying $p<\sigma\left(  1\right)  <\sigma\left(  2\right)  <\cdots
<\sigma\left(  k\right)  $, we can proceed as follows: First choose the first
$k$ values $\sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots
,\sigma\left(  k\right)  $ in $\dbinom{n-p}{k}$ many ways (since we only need
to choose their set as a $k$-element subset of the $\left(  n-p\right)
$-element set $\left\{  p+1,p+2,\ldots,n\right\}  $; their order is then
uniquely determined), and then choose the remaining $n-k$ values
$\sigma\left(  k+1\right)  ,\sigma\left(  k+2\right)  ,\ldots,\sigma\left(
n\right)  $ in $\left(  n-k\right)  !$ many ways. Thus, the total number of
such permutations is $\dbinom{n-p}{k}\left(  n-k\right)  !$. In other words,
$\left\vert B_{k}\right\vert =\dbinom{n-p}{k}\left(  n-k\right)  !$ (since the
set of all such permutations is $B_{k}$). This proves \eqref{sol.perm.p-desarr.Bk=}.]

It is also clear that $B_{0}\supseteq B_{1}\supseteq B_{2}\supseteq\cdots$.

Now, it is easy to see that a permutation $\sigma\in S_{n}$ is a
$p$-desarrangement if and only if it satisfies

\begin{itemize}
\item \textbf{either} $p\geq\sigma\left(  1\right)  $,

\item \textbf{or} $p<\sigma\left(  1\right)  <\sigma\left(  2\right)
\geq\sigma\left(  3\right)  $,

\item \textbf{or} $p<\sigma\left(  1\right)  <\sigma\left(  2\right)
<\sigma\left(  3\right)  <\sigma\left(  4\right)  \geq\sigma\left(  5\right)
$,

\item \textbf{or }$p<\sigma\left(  1\right)  <\sigma\left(  2\right)
<\sigma\left(  3\right)  <\sigma\left(  4\right)  <\sigma\left(  5\right)
<\sigma\left(  6\right)  \geq\sigma\left(  7\right)  $,

\item etc.
\end{itemize}

In other words, a permutation $\sigma\in S_{n}$ is a $p$-desarrangement if and
only if it satisfies

\begin{itemize}
\item \textbf{either} $\left(  \text{not }p<\sigma\left(  1\right)  \right)  $,

\item \textbf{or} $\left(  p<\sigma\left(  1\right)  <\sigma\left(  2\right)
\text{ but not }p<\sigma\left(  1\right)  <\sigma\left(  2\right)
<\sigma\left(  3\right)  \right)  $,

\item \textbf{or} $\left(  p<\sigma\left(  1\right)  <\sigma\left(  2\right)
<\sigma\left(  3\right)  <\sigma\left(  4\right)  \text{ but not }%
p<\sigma\left(  1\right)  <\sigma\left(  2\right)  <\cdots<\sigma\left(
5\right)  \right)  $,

\item \textbf{or }$\left(  p<\sigma\left(  1\right)  <\sigma\left(  2\right)
<\cdots<\sigma\left(  6\right)  \text{ but not }p<\sigma\left(  1\right)
<\sigma\left(  2\right)  <\cdots<\sigma\left(  7\right)  \right)  $,

\item etc.
\end{itemize}

In other words, a permutation $\sigma\in S_{n}$ is a $p$-desarrangement if and
only if it satisfies

\begin{itemize}
\item \textbf{either} $\left(  \text{not }\sigma\in B_{1}\right)  $,

\item \textbf{or} $\left(  \sigma\in B_{2}\text{ but not }\sigma\in
B_{3}\right)  $,

\item \textbf{or} $\left(  \sigma\in B_{4}\text{ but not }\sigma\in
B_{5}\right)  $,

\item \textbf{or }$\left(  \sigma\in B_{6}\text{ but not }\sigma\in
B_{7}\right)  $,

\item etc.
\end{itemize}

\noindent(since for any given $k\in\mathbb{N}$, the condition
\textquotedblleft$p<\sigma\left(  1\right)  <\sigma\left(  2\right)
<\cdots<\sigma\left(  k\right)  $\textquotedblright\ is equivalent to the
condition \textquotedblleft$\sigma\in B_{k}$\textquotedblright).

Moreover, all these possibilities are mutually exclusive (since $B_{0}%
\supseteq B_{1}\supseteq B_{2}\supseteq\cdots$, and therefore no $\sigma\in
S_{n}$ can fail to satisfy $\sigma\in B_{2i+1}$ for some $i$ and yet satisfy
$\sigma\in B_{2j}$ for some larger $j$). Hence,%
\begin{align*}
&  \left(  \text{the number of }p\text{-desarrangements}\right) \\
&  =\underbrace{\left(  \text{the number of }\sigma\in S_{n}\text{ such that
}\left(  \text{not }\sigma\in B_{1}\right)  \right)  }_{\substack{=\left(
\text{the number of }\sigma\in S_{n}\text{ such that }\left(  \sigma\in
B_{0}\text{ but not }\sigma\in B_{1}\right)  \right)  \\\text{(because every
}\sigma\in S_{n}\text{ satisfies }\sigma\in B_{0}\text{)}}}\\
&  \qquad+\left(  \text{the number of }\sigma\in S_{n}\text{ such that
}\left(  \sigma\in B_{2}\text{ but not }\sigma\in B_{3}\right)  \right) \\
&  \qquad+\left(  \text{the number of }\sigma\in S_{n}\text{ such that
}\left(  \sigma\in B_{4}\text{ but not }\sigma\in B_{5}\right)  \right) \\
&  \qquad+\left(  \text{the number of }\sigma\in S_{n}\text{ such that
}\left(  \sigma\in B_{6}\text{ but not }\sigma\in B_{7}\right)  \right) \\
&  \qquad+\cdots\\
&  =\left(  \text{the number of }\sigma\in S_{n}\text{ such that }\left(
\sigma\in B_{0}\text{ but not }\sigma\in B_{1}\right)  \right) \\
&  \qquad+\left(  \text{the number of }\sigma\in S_{n}\text{ such that
}\left(  \sigma\in B_{2}\text{ but not }\sigma\in B_{3}\right)  \right) \\
&  \qquad+\left(  \text{the number of }\sigma\in S_{n}\text{ such that
}\left(  \sigma\in B_{4}\text{ but not }\sigma\in B_{5}\right)  \right) \\
&  \qquad+\left(  \text{the number of }\sigma\in S_{n}\text{ such that
}\left(  \sigma\in B_{6}\text{ but not }\sigma\in B_{7}\right)  \right) \\
&  \qquad+\cdots\\
&  =\sum_{i\geq0}\underbrace{\left(  \text{the number of }\sigma\in
S_{n}\text{ such that }\left(  \sigma\in B_{2i}\text{ but not }\sigma\in
B_{2i+1}\right)  \right)  }_{\substack{=\left\vert B_{2i}\setminus
B_{2i+1}\right\vert =\left\vert B_{2i}\right\vert -\left\vert B_{2i+1}%
\right\vert \\\text{(since }B_{2i+1}\subseteq B_{2i}\text{ (because }%
B_{0}\supseteq B_{1}\supseteq B_{2}\supseteq\cdots\text{))}}}\\
&  =\sum_{i\geq0}\left(  \left\vert B_{2i}\right\vert -\left\vert
B_{2i+1}\right\vert \right)  =\sum_{k\geq0}\left(  -1\right)  ^{k}\left\vert
B_{k}\right\vert \\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{because every finitely supported sequence }\left(  a_{0},a_{1}%
,a_{2},\ldots\right)  \text{ of numbers}\\
\text{satisfies }\sum_{i\geq0}\left(  a_{2i}-a_{2i+1}\right)  =\sum_{k\geq
0}\left(  -1\right)  ^{k}a_{k}%
\end{array}
\right) \\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\underbrace{\left\vert B_{k}%
\right\vert }_{\substack{=\dbinom{n-p}{k}\left(  n-k\right)  !\\\text{(by
\eqref{sol.perm.p-desarr.Bk=})}}}+\sum_{k>n}\left(  -1\right)  ^{k}%
\underbrace{\left\vert B_{k}\right\vert }_{\substack{=0\\\text{(since }%
B_{k}=\varnothing\text{ for }k>n\text{)}}}=\sum_{k=0}^{n}\left(  -1\right)
^{k}\dbinom{n-p}{k}\left(  n-k\right)  !\\
&  =\sum_{k=0}^{n-p}\left(  -1\right)  ^{k}\dbinom{n-p}{k}\left(  n-k\right)
!+\sum_{k=n-p+1}^{n}\left(  -1\right)  ^{k}\underbrace{\dbinom{n-p}{k}%
}_{\substack{=0\\\text{(since }k>n-p\text{)}}}\left(  n-k\right)  !\\
&  =\sum_{k=0}^{n-p}\dbinom{n-p}{k}\cdot\left(  -1\right)  ^{k}\left(
n-k\right)  !.
\end{align*}
This solves the exercise.

\begin{thebibliography}{99999999}                                                                                         %


\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[Kerber99]{Kerber99}%
\href{https://doi.org/10.1007/978-3-662-11167-3}{Adalbert Kerber,
\textit{Applied Finite Group Actions}, 2nd edition, Springer 1999.}
\end{thebibliography}


\end{document}