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

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

%

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

\subsection{Reminders on binomial coefficients}

Let us first recall some facts about binomial coefficients:

\begin{proposition}
\label{prop.vandermonde.QQ}For every $x\in\mathbb{Q}$ and $y\in\mathbb{Q}$ and
$n\in\mathbb{N}$, we have
\[
\dbinom{x+y}{n}=\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}.
\]

\end{proposition}

\begin{proposition}
\label{prop.bincoeff!}Let $a$ and $b$ be two integers such that $a\geq b\geq
0$. Then,
\[
\dbinom{a}{b}=\dfrac{a!}{b!\left(  a-b\right)  !}.
\]

\end{proposition}

\begin{proposition}
\label{prop.binom.upperneg}We have
\[
\dbinom{n}{k}=\left(  -1\right)  ^{k}\dbinom{k-n-1}{k}%
\]
for any $n\in\mathbb{Q}$ and $k\in\mathbb{N}$.
\end{proposition}

\begin{proposition}
\label{prop.binom.knk}We have $k\dbinom{n}{k}=n\dbinom{n-1}{k-1}$ for any
$n\in\mathbb{Q}$ and any positive integer $k$.
\end{proposition}

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

\begin{proposition}
\label{prop.binom.revision}If $n\in\mathbb{Q}$ and if $a$ and $b$ are two
integers such that $a\geq b\geq0$, then
\[
\dbinom{n}{a}\dbinom{a}{b}=\dbinom{n}{b}\dbinom{n-b}{a-b}.
\]

\end{proposition}

\begin{proposition}
\label{prop.binom.mm}We have $\dbinom{m}{m}=1$ for every $m\in\mathbb{N}$.
\end{proposition}

\begin{proposition}
\label{prop.binom.symm}We have%
\begin{equation}
\dbinom{m}{n}=\dbinom{m}{m-n} \label{eq.binom.symm}%
\end{equation}
for any $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfying $m\geq n$.
\end{proposition}

Proposition \ref{prop.vandermonde.QQ} is the \textit{Vandermonde convolution
identity}, and is proven in multiple places\footnote{For an elementary proof,
see, e.g., \cite[first proof of Theorem 3.29]{detnotes}.}. Proposition
\ref{prop.bincoeff!} was proven in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{the solutions to
homework set 1}. Proposition \ref{prop.binom.upperneg} is Exercise 2
\textbf{(a)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{homework set 1}.
Proposition \ref{prop.binom.knk} is Exercise 2 \textbf{(b)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{homework set 1}.
Proposition \ref{prop.binom.0} is fundamental and easy to prove. Proposition
\ref{prop.binom.revision} is Exercise 2 \textbf{(c)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{homework set 1}.
Proposition \ref{prop.binom.mm} and Proposition \ref{prop.binom.symm} are easy
to check.

\subsection{Idempotent maps}

If $S$ is a set, then a map $f:S\rightarrow S$ is said to be
\textit{idempotent} if and only if $f\circ f=f$. For instance, the map
$\left[  3\right]  \rightarrow\left[  3\right]  $ sending $1,2,3$ to $1,3,3$
(respectively) is idempotent.

\begin{exercise}
\label{exe.idp}Let $n\in\mathbb{N}$.

\textbf{(a)} Prove that a map $f:\left[  n\right]  \rightarrow\left[
n\right]  $ is idempotent if and only if every $y\in f\left(  \left[
n\right]  \right)  $ satisfies $f\left(  y\right)  =y$.

\textbf{(b)} Prove that the number of idempotent maps $\left[  n\right]
\rightarrow\left[  n\right]  $ is $\sum_{k=0}^{n}\dbinom{n}{k}k^{n-k}$.

\textbf{(c)} Prove that the number of idempotent maps $\left[  n\right]
\rightarrow\left[  n\right]  $ has the form $an+1$ for some $a\in\mathbb{N}$.
(Of course, $a$ will depend on $n$.)

[\textbf{Hint:} When is $\dbinom{n}{k}k^{n-k}$ divisible by $n$ ?]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.idp} (sketched).]\textbf{(a)} Let $f:\left[
n\right]  \rightarrow\left[  n\right]  $ be a map. We must prove that $f$ is
idempotent if and only if every $y\in f\left(  \left[  n\right]  \right)  $
satisfies $f\left(  y\right)  =y$.

$\Longrightarrow:$ Assume that $f$ is idempotent. We must prove that every
$y\in f\left(  \left[  n\right]  \right)  $ satisfies $f\left(  y\right)  =y$.

We have assumed that $f$ is idempotent. In other words, $f\circ f=f$. Now, let
$y\in f\left(  \left[  n\right]  \right)  $. Thus, there exists some
$x\in\left[  n\right]  $ satisfying $y=f\left(  x\right)  $. Consider this
$x$. We have $f\left(  \underbrace{y}_{=f\left(  x\right)  }\right)  =f\left(
f\left(  x\right)  \right)  =\underbrace{\left(  f\circ f\right)  }%
_{=f}\left(  x\right)  =f\left(  x\right)  =y$. Now, forget that we fixed $y$.
We thus have shown that every $y\in f\left(  \left[  n\right]  \right)  $
satisfies $f\left(  y\right)  =y$. This proves the \textquotedblleft%
$\Longrightarrow$\textquotedblright\ direction of Exercise \ref{exe.idp}
\textbf{(a)}.

$\Longleftarrow:$ Assume that every $y\in f\left(  \left[  n\right]  \right)
$ satisfies $f\left(  y\right)  =y$. We must prove that $f$ is idempotent.

Let $x\in\left[  n\right]  $. Thus, $f\left(  x\right)  \in f\left(  \left[
n\right]  \right)  $. But we assumed that every $y\in f\left(  \left[
n\right]  \right)  $ satisfies $f\left(  y\right)  =y$. Applying this to
$y=f\left(  x\right)  $, we obtain $f\left(  f\left(  x\right)  \right)
=f\left(  x\right)  $ (since $f\left(  x\right)  \in f\left(  \left[
n\right]  \right)  $). Hence, $\left(  f\circ f\right)  \left(  x\right)
=f\left(  f\left(  x\right)  \right)  =f\left(  x\right)  $. Now, forget that
we fixed $x$. We thus have proven that $\left(  f\circ f\right)  \left(
x\right)  =f\left(  x\right)  $ for each $x\in\left[  n\right]  $. In other
words, $f\circ f=f$. In other words, $f$ is idempotent (by the definition of
\textquotedblleft idempotent\textquotedblright). This proves the
\textquotedblleft$\Longleftarrow$\textquotedblright\ direction of Exercise
\ref{exe.idp} \textbf{(a)}.

Hence, Exercise \ref{exe.idp} \textbf{(a)} is solved (since we have proven
both of its directions).

\textbf{(b)} The following algorithm constructs every idempotent map
$f:\left[  n\right]  \rightarrow\left[  n\right]  $:

\begin{itemize}
\item First, we choose an integer $k\in\left\{  0,1,\ldots,n\right\}  $. This
integer $k$ shall be the size $\left\vert f\left(  \left[  n\right]  \right)
\right\vert $ of the image of $f$. (Of course, this size has to be in
$\left\{  0,1,\ldots,n\right\}  $, because $f\left(  \left[  n\right]
\right)  $ must be a subset of $\left[  n\right]  $.)

\item Next, we choose a $k$-element subset $S$ of $\left[  n\right]  $. This
subset $S$ shall be the image $f\left(  \left[  n\right]  \right)  $ of $f$.
There are $\dbinom{n}{k}$ choices for $S$ (since the number of $k$-element
subsets of $\left[  n\right]  $ is $\dbinom{n}{k}$).

\item At this point, the values of $f$ on all elements of $S$ are already
uniquely determined: Indeed, Exercise \ref{exe.idp} \textbf{(a)} shows that
every $y\in f\left(  \left[  n\right]  \right)  $ has to satisfy $f\left(
y\right)  =y$ for $f$ to be idempotent; in other words, every $y\in S$ has to
satisfy $f\left(  y\right)  =y$ (since we want $f\left(  \left[  n\right]
\right)  $ to be $S$).

\item Finally, we choose the values of $f$ on all remaining elements of
$\left[  n\right]  $ (that is, on all elements of $\left[  n\right]  \setminus
S$). These values must belong to $S$ (because we want $f\left(  \left[
n\right]  \right)  $ to be $S$), but are otherwise unconstrained\footnote{At
this step, we do not need to ensure that every element of $S$ is taken as a
value of $f$, because this has already been ensured (indeed, every $y\in S$
satisfies $f\left(  y\right)  =y$, so that $y$ is already a value of $f$).}.
Thus, there are $\left\vert S\right\vert ^{\left\vert \left[  n\right]
\setminus S\right\vert }$ choices at this step. In other words, there are
$k^{n-k}$ choices at this step (since $\left\vert S\right\vert =k$ and
$\left\vert \left[  n\right]  \setminus S\right\vert =n-\underbrace{\left\vert
S\right\vert }_{=k}=n-k$).
\end{itemize}

It is easy to check that this algorithm really constructs idempotent maps
$f:\left[  n\right]  \rightarrow\left[  n\right]  $, and constructs each of
them exactly once. Thus, the number of idempotent maps $f:\left[  n\right]
\rightarrow\left[  n\right]  $ is%
\[
\sum_{k\in\left\{  0,1,\ldots,n\right\}  }\dbinom{n}{k}k^{n-k}%
\]
(since we get to choose $k\in\left\{  0,1,\ldots,n\right\}  $ in the first
step of the algorithm, then we have $\dbinom{n}{k}$ choices in the second
step, then a unique choice in the third step, and finally $k^{n-k}$ choices in
the fourth step). Hence, the number of idempotent maps $f:\left[  n\right]
\rightarrow\left[  n\right]  $ is%
\[
\sum_{k\in\left\{  0,1,\ldots,n\right\}  }\dbinom{n}{k}k^{n-k}=\sum_{k=0}%
^{n}\dbinom{n}{k}k^{n-k}.
\]
This solves Exercise \ref{exe.idp} \textbf{(b)}.

\textbf{(c)} If $n=0$, then the number of idempotent maps $\left[  n\right]
\rightarrow\left[  n\right]  $ is $1$, which clearly has the form $an+1$ for
some $a\in\mathbb{N}$ (namely, for $a=0$). Hence, for the rest of this
solution, we WLOG assume that we don't have $n=0$. Thus, $n>0$, so that
$n\geq1$.

For each $k\in\left\{  1,2,\ldots,n-1\right\}  $, the number $\dbinom
{n-1}{k-1}k^{n-k-1}$ is a nonnegative integer\footnote{\textit{Proof.} Let
$k\in\left\{  1,2,\ldots,n-1\right\}  $. Thus, $1\leq k\leq n-1$. From $1\leq
k$, we obtain $k-1\in\mathbb{N}$. Also, $n-1\in\mathbb{N}$ (since $n\geq1$).
Hence, $\dbinom{n-1}{k-1}$ is the number of $\left(  k-1\right)  $-element
subsets of the set $\left[  n-1\right]  $ (by the combinatorial interpretation
of binomial coefficients). Therefore, $\dbinom{n-1}{k-1}$ is a nonnegative
integer. Also, $n-\underbrace{k}_{\leq n-1}-1\geq n-\left(  n-1\right)  -1=0$,
so that $n-k-1\in\mathbb{N}$. Thus, $k^{n-k-1}\in\mathbb{N}$ (since
$k\in\left\{  1,2,\ldots,n-1\right\}  \subseteq\mathbb{N}$). In other words,
$k^{n-k-1}$ is a nonnegative integer. Hence, the number $\dbinom{n-1}%
{k-1}k^{n-k-1}$ is a product of two nonnegative integers, hence itself a
nonnegative integer. Qed.}. Hence, $\sum_{k=1}^{n-1}\dbinom{n-1}{k-1}%
k^{n-k-1}$ is a sum of nonnegative integers, thus itself a nonnegative
integer. In other words,%
\[
\sum_{k=1}^{n-1}\dbinom{n-1}{k-1}k^{n-k-1}\in\mathbb{N}.
\]


Exercise \ref{exe.idp} \textbf{(b)} shows that the number of idempotent maps
$\left[  n\right]  \rightarrow\left[  n\right]  $ is%
\begin{align*}
\sum_{k=0}^{n}\dbinom{n}{k}k^{n-k}  &  =\sum_{k=0}^{n-1}\dbinom{n}%
{k}\underbrace{k^{n-k}}_{\substack{=kk^{n-k-1}\\\text{(since }%
n-k>0\\\text{(since }k\leq n-1<n\text{))}}}+\underbrace{\dbinom{n}{n}%
}_{\substack{=1\\\text{(by Proposition \ref{prop.binom.mm},}\\\text{applied to
}m=n\text{)}}}\underbrace{n^{n-n}}_{=n^{0}=1}\\
&  =\underbrace{\sum_{k=0}^{n-1}\dbinom{n}{k}kk^{n-k-1}}_{\substack{=\dbinom
{n}{0}0\cdot0^{n-0-1}+\sum_{k=1}^{n-1}\dbinom{n}{k}kk^{n-k-1}\\\text{(since
}n\geq1\text{)}}}+1\\
&  =\underbrace{\dbinom{n}{0}0\cdot0^{n-0-1}}_{=0}+\sum_{k=1}^{n-1}%
\underbrace{\dbinom{n}{k}k}_{\substack{=k\dbinom{n}{k}=n\dbinom{n-1}%
{k-1}\\\text{(by Proposition \ref{prop.binom.knk})}}}k^{n-k-1}+1\\
&  =\underbrace{\sum_{k=1}^{n-1}n\dbinom{n-1}{k-1}k^{n-k-1}}_{=\left(
\sum_{k=1}^{n-1}\dbinom{n-1}{k-1}k^{n-k-1}\right)  n}+1=\left(  \sum
_{k=1}^{n-1}\dbinom{n-1}{k-1}k^{n-k-1}\right)  n+1.
\end{align*}
Hence, this number has the form $an+1$ for some $a\in\mathbb{N}$ (namely, for
$a=\sum_{k=1}^{n-1}\dbinom{n-1}{k-1}k^{n-k-1}$). This solves Exercise
\ref{exe.idp} \textbf{(c)}.
\end{proof}

\subsection{Fixed points}

\begin{exercise}
\label{exe.Fixfg}Let $S$ be a finite set. For any map $f:S\rightarrow S$, we
let $\operatorname*{Fix}f$ denote the set of all fixed points of $f$. (That
is, $\operatorname*{Fix}f=\left\{  s\in S\ \mid\ f\left(  s\right)
=s\right\}  $.)

\textbf{(a)} Prove that $\left\vert \operatorname*{Fix}\left(  f\circ
g\right)  \right\vert =\left\vert \operatorname*{Fix}\left(  g\circ f\right)
\right\vert $ for any two maps $f:S\rightarrow S$ and $g:S\rightarrow S$.

\textbf{(b)} Is it true that every three maps $f,g,h$ from $S$ to $S$ satisfy
$\left\vert \operatorname*{Fix}\left(  f\circ g\circ h\right)  \right\vert
=\left\vert \operatorname*{Fix}\left(  g\circ f\circ h\right)  \right\vert $ ?

[\textbf{Hint:} For \textbf{(a)}, find a bijection.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.Fixfg}.]\textbf{(a)} Let $f:S\rightarrow S$ and
$g:S\rightarrow S$ be two maps. Then, $g\left(  x\right)  \in
\operatorname*{Fix}\left(  g\circ f\right)  $ for each $x\in
\operatorname*{Fix}\left(  f\circ g\right)  $\ \ \ \ \footnote{\textit{Proof.}
Let $x\in\operatorname*{Fix}\left(  f\circ g\right)  $. We must show that
$g\left(  x\right)  \in\operatorname*{Fix}\left(  g\circ f\right)  $.
\par
We know that $x\in\operatorname*{Fix}\left(  f\circ g\right)  $. In other
words, $x$ is a fixed point of $f\circ g$ (since $\operatorname*{Fix}\left(
f\circ g\right)  $ is defined as the set of all fixed points of $f\circ g$).
In other words, $\left(  f\circ g\right)  \left(  x\right)  =x$. Thus,
$f\left(  g\left(  x\right)  \right)  =\left(  f\circ g\right)  \left(
x\right)  =x$. Hence,%
\[
\left(  g\circ f\right)  \left(  g\left(  x\right)  \right)  =g\left(
\underbrace{f\left(  g\left(  x\right)  \right)  }_{=x}\right)  =g\left(
x\right)  .
\]
In other words, $g\left(  x\right)  $ is a fixed point of $g\circ f$. In other
words, $g\left(  x\right)  \in\operatorname*{Fix}\left(  g\circ f\right)  $
(since $\operatorname*{Fix}\left(  g\circ f\right)  $ is defined as the set of
all fixed points of $g\circ f$). This completes our proof.}. The same argument
(applied to $g$ and $f$ instead of $f$ and $g$) shows that $f\left(  x\right)
\in\operatorname*{Fix}\left(  f\circ g\right)  $ for each $x\in
\operatorname*{Fix}\left(  g\circ f\right)  $.

Let $\gamma$ be the map%
\[
\operatorname*{Fix}\left(  f\circ g\right)  \rightarrow\operatorname*{Fix}%
\left(  g\circ f\right)  ,\ \ \ \ \ \ \ \ \ \ x\mapsto g\left(  x\right)  .
\]
(This is well-defined, because $g\left(  x\right)  \in\operatorname*{Fix}%
\left(  g\circ f\right)  $ for each $x\in\operatorname*{Fix}\left(  f\circ
g\right)  $.)

Let $\varphi$ be the map%
\[
\operatorname*{Fix}\left(  g\circ f\right)  \rightarrow\operatorname*{Fix}%
\left(  f\circ g\right)  ,\ \ \ \ \ \ \ \ \ \ x\mapsto f\left(  x\right)  .
\]
(This is well-defined, because $f\left(  x\right)  \in\operatorname*{Fix}%
\left(  f\circ g\right)  $ for each $x\in\operatorname*{Fix}\left(  g\circ
f\right)  $.)

We have $\varphi\circ\gamma=\operatorname*{id}$%
\ \ \ \ \footnote{\textit{Proof.} Let $x\in\operatorname*{Fix}\left(  f\circ
g\right)  $. Thus, $\gamma\left(  x\right)  =g\left(  x\right)  $ (by the
definition of $\gamma$). But $\gamma\left(  x\right)  \in\operatorname*{Fix}%
\left(  g\circ f\right)  $, so that $\varphi\left(  \gamma\left(  x\right)
\right)  =f\left(  \gamma\left(  x\right)  \right)  $ (by the definition of
$\varphi$).
\par
We have $x\in\operatorname*{Fix}\left(  f\circ g\right)  $. In other words,
$x$ is a fixed point of $f\circ g$ (since $\operatorname*{Fix}\left(  f\circ
g\right)  $ is defined as the set of all fixed points of $f\circ g$). In other
words, $\left(  f\circ g\right)  \left(  x\right)  =x$. Now,%
\[
\left(  \varphi\circ\gamma\right)  \left(  x\right)  =\varphi\left(
\gamma\left(  x\right)  \right)  =f\left(  \underbrace{\gamma\left(  x\right)
}_{=g\left(  x\right)  }\right)  =f\left(  g\left(  x\right)  \right)
=\left(  f\circ g\right)  \left(  x\right)  =x=\operatorname*{id}\left(
x\right)  .
\]
\par
Now, forget that we fixed $x$. We thus have proven that $\left(  \varphi
\circ\gamma\right)  \left(  x\right)  =\operatorname*{id}\left(  x\right)  $
for each $x\in\operatorname*{Fix}\left(  f\circ g\right)  $. In other words,
$\varphi\circ\gamma=\operatorname*{id}$.}. The same argument (applied to $g$,
$f$, $\gamma$ and $\varphi$ instead of $f$, $g$, $\varphi$ and $\gamma$) shows
that $\gamma\circ\varphi=\operatorname*{id}$.

The maps $\varphi$ and $\gamma$ are mutually inverse (since $\varphi
\circ\gamma=\operatorname*{id}$ and $\gamma\circ\varphi=\operatorname*{id}$),
and thus bijections. Hence, we have found a bijection $\operatorname*{Fix}%
\left(  f\circ g\right)  \rightarrow\operatorname*{Fix}\left(  g\circ
f\right)  $ (namely, $\gamma$). Hence, $\left\vert \operatorname*{Fix}\left(
f\circ g\right)  \right\vert =\left\vert \operatorname*{Fix}\left(  g\circ
f\right)  \right\vert $. This solves Exercise \ref{exe.Fixfg} \textbf{(a)}.

\textbf{(b)} It is false. Here is one of many possible counterexamples:

Let $S$ be the $3$-element set $\left[  3\right]  =\left\{  1,2,3\right\}  $.
Let $s_{1}$ be the permutation of $\left[  3\right]  $ that switches $1$ and
$2$ while leaving $3$ unchanged. Let $s_{2}$ be the permutation of $\left[
3\right]  $ that switches $2$ and $3$ while leaving $1$ unchanged. Then,
$s_{1}\circ s_{1}=\operatorname*{id}$ and $s_{2}\circ s_{2}=\operatorname*{id}%
$.

Now, set $f=s_{1}$, $g=s_{2}$ and $h=s_{1}\circ s_{2}$. Then, the map $f\circ
g\circ h=s_{1}\circ s_{2}\circ s_{1}\circ s_{2}$ has no fixed points at all
(check this!), so that $\left\vert \operatorname*{Fix}\left(  f\circ g\circ
h\right)  \right\vert =0$. But
\[
g\circ f\circ h=s_{2}\circ\underbrace{s_{1}\circ s_{1}}_{=\operatorname*{id}%
}\circ s_{2}=s_{2}\circ s_{2}=\operatorname*{id},
\]
and thus $\left\vert \operatorname*{Fix}\left(  g\circ f\circ h\right)
\right\vert =\left\vert \operatorname*{Fix}\left(  \operatorname*{id}\right)
\right\vert =\left\vert S\right\vert =3$. Hence, $\left\vert
\operatorname*{Fix}\left(  f\circ g\circ h\right)  \right\vert \neq\left\vert
\operatorname*{Fix}\left(  g\circ f\circ h\right)  \right\vert $. This solves
Exercise \ref{exe.Fixfg} \textbf{(b)}.
\end{proof}

\begin{remark}
Exercise \ref{exe.Fixfg} \textbf{(a)} can be slightly generalized:

\begin{proposition}
\label{prop.Fixfg.a-gen}Let $S$ and $T$ be two finite sets. Then, $\left\vert
\operatorname*{Fix}\left(  f\circ g\right)  \right\vert =\left\vert
\operatorname*{Fix}\left(  g\circ f\right)  \right\vert $ for any two maps
$f:S\rightarrow T$ and $g:T\rightarrow S$.
\end{proposition}

Setting $T=S$ in Proposition \ref{prop.Fixfg.a-gen}, we recover Exercise
\ref{exe.Fixfg} \textbf{(a)}. The proof of Proposition \ref{prop.Fixfg.a-gen}
is analogous to the above solution of Exercise \ref{exe.Fixfg} \textbf{(a)}.
\end{remark}

\begin{remark}
Exercise \ref{exe.Fixfg} (and Proposition \ref{prop.Fixfg.a-gen}) might remind
you of something you have seen in linear algebra. Namely, if $A$ is an
$n\times m$-matrix and $B$ is an $m\times n$-matrix (so that both products
$AB$ and $BA$ are well-defined), then
\begin{equation}
\operatorname*{Tr}\left(  AB\right)  =\operatorname*{Tr}\left(  BA\right)  ,
\label{rmk.Fixfg.TrAB}%
\end{equation}
but it is not true that any three $n\times n$-matrices $A,B,C$ satisfy
$\operatorname*{Tr}\left(  ABC\right)  =\operatorname*{Tr}\left(  BAC\right)
$.

This is more than just a similarity. You can actually prove Proposition
\ref{prop.Fixfg.a-gen} using (\ref{rmk.Fixfg.TrAB}). Here is an outline of
this proof: To any map $w:\left[  p\right]  \rightarrow\left[  q\right]  $
(where $p$ and $q$ are two nonnegative integers), we assign a $q\times
p$-matrix $M_{w}$ whose $\left(  i,j\right)  $-th entry is $\left[  i=w\left(
j\right)  \right]  $ (where we are using the Iverson bracket notation). In
other words, $M_{w}$ is the matrix whose $j$-th column has a $1$ in its
$w\left(  j\right)  $-th row and $0$'s everywhere else. If $p=q$ (so that $w$
is a map from the set $\left[  p\right]  $ to itself), then this matrix
$M_{w}$ is a square matrix with trace
\begin{equation}
\operatorname*{Tr}\left(  M_{w}\right)  =\left\vert \operatorname*{Fix}%
w\right\vert \label{rmk.Fixfg.TrMw}%
\end{equation}
(check this!). Now, let $f:S\rightarrow T$ and $g:T\rightarrow S$ be two maps.
WLOG assume that $S=\left[  n\right]  $ and $T=\left[  m\right]  $ for two
nonnegative integers $n$ and $m$ (otherwise, \textquotedblleft
relabel\textquotedblright\ the elements of $S$ and $T$). Then, it is easy to
see that $M_{f\circ g}=M_{f}M_{g}$ and $M_{g\circ f}=M_{g}M_{f}$. Meanwhile,
(\ref{rmk.Fixfg.TrMw}) yields $\operatorname*{Tr}\left(  M_{f\circ g}\right)
=\left\vert \operatorname*{Fix}\left(  f\circ g\right)  \right\vert $ and
$\operatorname*{Tr}\left(  M_{g\circ f}\right)  =\left\vert
\operatorname*{Fix}\left(  g\circ f\right)  \right\vert $. Hence,%
\begin{align*}
\left\vert \operatorname*{Fix}\left(  f\circ g\right)  \right\vert  &
=\operatorname*{Tr}\left(  \underbrace{M_{f\circ g}}_{=M_{f}M_{g}}\right)
=\operatorname*{Tr}\left(  M_{f}M_{g}\right)  =\operatorname*{Tr}\left(
\underbrace{M_{g}M_{f}}_{=M_{g\circ f}}\right)  \ \ \ \ \ \ \ \ \ \ \left(
\text{by (\ref{rmk.Fixfg.TrAB})}\right) \\
&  =\operatorname*{Tr}\left(  M_{g\circ f}\right)  =\left\vert
\operatorname*{Fix}\left(  g\circ f\right)  \right\vert .
\end{align*}
So we have again proved Proposition \ref{prop.Fixfg.a-gen}.
\end{remark}

\subsection{A binomial coefficient in a denominator}

\begin{exercise}
\label{exe.schmitt-iha-eq9.2}Let $n$ and $a$ be two integers with $n\geq
a\geq1$. Prove that%
\[
\sum_{k=a}^{n}\dfrac{\left(  -1\right)  ^{k}}{k}\dbinom{n-a}{k-a}%
=\dfrac{\left(  -1\right)  ^{a}}{a\dbinom{n}{a}}.
\]

\end{exercise}

Exercise \ref{exe.schmitt-iha-eq9.2} is an identity that tends to creep up in
various seemingly(?) unrelated situations in mathematics. I have first
encountered it in \cite[proof of Theorem 9.5]{Schmitt04} (where it appears
with an incorrect power of $-1$ on the right hand side). It also has recently
appeared on math.stackexchange (\cite{dilemi17}, with $a$, $n-a$ and $k-a$
renamed as $p$, $n$ and $k$), where it has been proven in three different
ways: once using the beta function, once using residues, and once (by myself
in the comments) using finite differences. Let me here give a different,
elementary proof.\footnote{This proof also appears in \cite[solution to
Exercise 3.16]{detnotes}.}

We begin with the following identities:

\begin{proposition}
\label{prop.schmitt-iha-eq9.2.binoms}Let $i\in\mathbb{Z}$, $n\in\mathbb{Z}$
and $j\in\mathbb{N}$. Then:

\textbf{(a)} We have
\[
\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{n}{j-k}\dbinom{k+i-1}{k}%
=\dbinom{n-i}{j}.
\]


\textbf{(b)} If $i$ is positive, then%
\[
\sum_{k=0}^{j}\dfrac{\left(  -1\right)  ^{k}}{k+i}\dbinom{n}{j-k}\dbinom
{k+i}{i}=\dfrac{1}{i}\dbinom{n-i}{j}.
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.schmitt-iha-eq9.2.binoms}.]\textbf{(a)}
Proposition \ref{prop.vandermonde.QQ} (applied to $-i$, $n$ and $j$ instead of
$x$, $y$ and $n$) yields%
\begin{align*}
\dbinom{\left(  -i\right)  +n}{j}  &  =\sum_{k=0}^{j}\underbrace{\dbinom
{-i}{k}}_{\substack{=\left(  -1\right)  ^{k}\dbinom{k-\left(  -i\right)
-1}{k}\\\text{(by Proposition \ref{prop.binom.upperneg},}\\\text{applied to
}-i\text{ instead of }n\text{)}}}\dbinom{n}{j-k}\\
&  =\sum_{k=0}^{j}\left(  -1\right)  ^{k}\underbrace{\dbinom{k-\left(
-i\right)  -1}{k}}_{\substack{=\dbinom{k+i-1}{k}\\\text{(since }k-\left(
-i\right)  -1=k+i-1\text{)}}}\dbinom{n}{j-k}\\
&  =\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{k+i-1}{k}\dbinom{n}{j-k}%
=\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{n}{j-k}\dbinom{k+i-1}{k}.
\end{align*}
Thus,%
\[
\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{n}{j-k}\dbinom{k+i-1}{k}%
=\dbinom{\left(  -i\right)  +n}{j}=\dbinom{n-i}{j}.
\]
This proves Proposition \ref{prop.schmitt-iha-eq9.2.binoms} \textbf{(a)}.

\textbf{(b)} Assume that $i$ is positive. Let $k\in\mathbb{N}$. Then,
$i-1\in\mathbb{N}$ (since $i$ is a positive integer). Thus, $i-1\geq0$. Also,
$\underbrace{k}_{\geq0}+i-1\geq i-1$. Hence, Proposition \ref{prop.binom.symm}
(applied to $k+i-1$ and $i-1$ instead of $m$ and $n$) yields
\[
\dbinom{k+i-1}{i-1}=\dbinom{k+i-1}{\left(  k+i-1\right)  -\left(  i-1\right)
}=\dbinom{k+i-1}{k}%
\]
(since $\left(  k+i-1\right)  -\left(  i-1\right)  =k$).

Furthermore, Proposition \ref{prop.binom.knk} (applied to $k+i$ and $i$
instead of $n$ and $k$) yields%
\[
i\dbinom{k+i}{i}=\left(  k+i\right)  \underbrace{\dbinom{k+i-1}{i-1}%
}_{=\dbinom{k+i-1}{k}}=\left(  k+i\right)  \dbinom{k+i-1}{k}.
\]
Hence,
\[
\dbinom{k+i}{i}=\dfrac{1}{i}\left(  k+i\right)  \dbinom{k+i-1}{k}.
\]
Thus,%
\begin{align}
&  \dfrac{\left(  -1\right)  ^{k}}{k+i}\dbinom{n}{j-k}\underbrace{\dbinom
{k+i}{i}}_{=\dfrac{1}{i}\left(  k+i\right)  \dbinom{k+i-1}{k}}\nonumber\\
&  =\dfrac{\left(  -1\right)  ^{k}}{k+i}\dbinom{n}{j-k}\cdot\dfrac{1}%
{i}\left(  k+i\right)  \dbinom{k+i-1}{k}\nonumber\\
&  =\dfrac{1}{i}\left(  -1\right)  ^{k}\dbinom{n}{j-k}\dbinom{k+i-1}{k}.
\label{pf.prop.schmitt-iha-eq9.2.binoms.b.3}%
\end{align}


Now, forget that we fixed $k$. We thus have proven
(\ref{pf.prop.schmitt-iha-eq9.2.binoms.b.3}) for each $k\in\mathbb{N}$. Now,%
\begin{align*}
&  \sum_{k=0}^{j}\underbrace{\dfrac{\left(  -1\right)  ^{k}}{k+i}\dbinom
{n}{j-k}\dbinom{k+i}{i}}_{\substack{=\dfrac{1}{i}\left(  -1\right)
^{k}\dbinom{n}{j-k}\dbinom{k+i-1}{k}\\\text{(by
(\ref{pf.prop.schmitt-iha-eq9.2.binoms.b.3}))}}}\\
&  =\sum_{k=0}^{j}\dfrac{1}{i}\left(  -1\right)  ^{k}\dbinom{n}{j-k}%
\dbinom{k+i-1}{k}\\
&  =\dfrac{1}{i}\underbrace{\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom
{n}{j-k}\dbinom{k+i-1}{k}}_{\substack{=\dbinom{n-i}{j}\\\text{(by Proposition
\ref{prop.schmitt-iha-eq9.2.binoms} \textbf{(a)})}}}=\dfrac{1}{i}\dbinom
{n-i}{j}.
\end{align*}
This proves Proposition \ref{prop.schmitt-iha-eq9.2.binoms} \textbf{(b)}.
\end{proof}

Let us now solve the actual exercise:

\begin{proof}
[Solution to Exercise \ref{exe.schmitt-iha-eq9.2}.]From $n\geq a$, we obtain
$n-a\in\mathbb{N}$. Also, $n\geq a\geq1\geq0$, and therefore Proposition
\ref{prop.bincoeff!} (applied to $n$ and $a$ instead of $a$ and $b$) yields
$\dbinom{n}{a}=\dfrac{n!}{a!\left(  n-a\right)  !}\neq0$ (since $n!\neq0$).

Any $k\in\left\{  a,a+1,\ldots,n\right\}  $ satisfies%
\begin{equation}
\dbinom{n}{a}\dbinom{n-a}{k-a}=\dbinom{n}{n-k}\dbinom{k}{a}
\label{sol.schmitt-iha-eq9.2.1}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.schmitt-iha-eq9.2.1}):} Let $k\in\left\{
a,a+1,\ldots,n\right\}  $. Thus, $a\leq k\leq n$, so that $k\geq a\geq1\geq0$,
so that $k\in\mathbb{N}$. Hence, Proposition \ref{prop.binom.symm} (applied to
$n$ and $k$ instead of $m$ and $n$) yields $\dbinom{n}{k}=\dbinom{n}{n-k}$.
\par
But Proposition \ref{prop.binom.revision} (applied to $k$ and $a$ instead of
$a$ and $b$) shows that%
\[
\dbinom{n}{k}\dbinom{k}{a}=\dbinom{n}{a}\dbinom{n-a}{k-a}.
\]
Hence,%
\[
\dbinom{n}{a}\dbinom{n-a}{k-a}=\underbrace{\dbinom{n}{k}}_{=\dbinom{n}{n-k}%
}\dbinom{k}{a}=\dbinom{n}{n-k}\dbinom{k}{a}.
\]
This proves (\ref{sol.schmitt-iha-eq9.2.1}).}. We have%
\begin{align*}
&  \dbinom{n}{a}\sum_{k=a}^{n}\dfrac{\left(  -1\right)  ^{k}}{k}\dbinom
{n-a}{k-a}\\
&  =\sum_{k=a}^{n}\dfrac{\left(  -1\right)  ^{k}}{k}\underbrace{\dbinom{n}%
{a}\dbinom{n-a}{k-a}}_{\substack{=\dbinom{n}{n-k}\dbinom{k}{a}\\\text{(by
(\ref{sol.schmitt-iha-eq9.2.1}))}}}\\
&  =\sum_{k=a}^{n}\dfrac{\left(  -1\right)  ^{k}}{k}\dbinom{n}{n-k}\dbinom
{k}{a}=\sum_{k=0}^{n-a}\underbrace{\dfrac{\left(  -1\right)  ^{k+a}}{k+a}%
}_{\substack{=\dfrac{\left(  -1\right)  ^{k}\left(  -1\right)  ^{a}}%
{k+a}\\\text{(since }\left(  -1\right)  ^{k+a}=\left(  -1\right)  ^{k}\left(
-1\right)  ^{a}\text{)}}}\underbrace{\dbinom{n}{n-\left(  k+a\right)  }%
}_{\substack{=\dbinom{n}{\left(  n-a\right)  -k}\\\text{(since }n-\left(
k+a\right)  =\left(  n-a\right)  -k\text{)}}}\dbinom{k+a}{a}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }k+a\text{ for
}k\text{ in the sum}\right) \\
&  =\sum_{k=0}^{n-a}\dfrac{\left(  -1\right)  ^{k}\left(  -1\right)  ^{a}%
}{k+a}\dbinom{n}{\left(  n-a\right)  -k}\dbinom{k+a}{a}=\left(  -1\right)
^{a}\underbrace{\sum_{k=0}^{n-a}\dfrac{\left(  -1\right)  ^{k}}{k+a}\dbinom
{n}{\left(  n-a\right)  -k}\dbinom{k+a}{a}}_{\substack{=\dfrac{1}{a}%
\dbinom{n-a}{n-a}\\\text{(by Proposition \ref{prop.schmitt-iha-eq9.2.binoms}
\textbf{(b)},}\\\text{applied to }j=n-a\text{ and }i=a\text{)}}}\\
&  =\left(  -1\right)  ^{a}\dfrac{1}{a}\underbrace{\dbinom{n-a}{n-a}%
}_{\substack{=1\\\text{(by Proposition \ref{prop.binom.mm},}\\\text{applied to
}m=n-a\text{)}}}=\left(  -1\right)  ^{a}\dfrac{1}{a}.
\end{align*}
We can divide both sides of this equality by $\dbinom{n}{a}$ (since
$\dbinom{n}{a}\neq0$). Thus, we find%
\[
\sum_{k=a}^{n}\dfrac{\left(  -1\right)  ^{k}}{k}\dbinom{n-a}{k-a}=\left(
-1\right)  ^{a}\dfrac{1}{a}/\dbinom{n}{a}=\dfrac{\left(  -1\right)  ^{a}%
}{a\dbinom{n}{a}}.
\]
This solves Exercise \ref{exe.schmitt-iha-eq9.2}.
\end{proof}

\subsection{Derangements with at most 1 descent}

\begin{exercise}
\label{exe.1descent.der}Let $n\in\mathbb{N}$. How many derangements $\sigma$
of $\left[  n\right]  $ have at most $1$ descent?
\end{exercise}

(See \href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw5os.pdf}{homework
set \#5} for the definitions of descents and of derangements.)

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

The main work of the solution to Exercise \ref{exe.1descent.der} is done by
the following fact:

\begin{proposition}
\label{prop.1descent.i}Let $n \in\mathbb{N}$. Let $i\in\left[  n-1\right]  $.
Then,%
\begin{align*}
&  \left(  \text{the number of derangements of }\left[  n\right]  \text{ whose
only descent is }i\right) \\
&  =\dbinom{n-2}{i-1}.
\end{align*}

\end{proposition}

Proposition \ref{prop.1descent.i} is a result by Gessel and Reutenauer
\cite[Theorem 9.5]{GesReu93}, which they obtained using the theory of
quasisymmetric functions. We shall instead prove it by elementary combinatorics.

To simplify its proof, let us first verify a lemma:

\begin{lemma}
\label{lem.1descent.der} Let $n\in\mathbb{N}$. Let $i\in\left[  n-1\right]  $.
Let $\sigma\in S_{n}$ be a permutation satisfying $\sigma\left(  1\right)
<\sigma\left(  2\right)  <\cdots<\sigma\left(  i\right)  $ and $\sigma\left(
i+1\right)  <\sigma\left(  i+2\right)  <\cdots<\sigma\left(  n\right)  $ and
$\sigma\left(  1\right)  \neq1$ and $\sigma\left(  n\right)  \neq n$. Then,
$\sigma$ is a derangement of $\left[  n\right]  $ whose only descent is $i$.
\end{lemma}

\begin{proof}
[Proof of Lemma~\ref{lem.1descent.der}.]Let $k$ be a fixed point of $\sigma$.
We shall derive a contradiction (from which we will, of course, conclude that
$\sigma$ has no fixed points).

We have $\sigma\left(  k\right)  = k$ (since $k$ is a fixed point of $\sigma$).

\begin{noncompile}
If we had $k=1$, then we would have $\sigma\left(  k\right)  =\sigma\left(
1\right)  \neq1=k$, which would contradict $\sigma\left(  k\right)  =k$. Thus,
we cannot have $k=1$. Hence, we have $k\neq1$, so that $k>1$.

If we had $k=n$, then we would have $\sigma\left(  k\right)  =\sigma\left(
n\right)  \neq n=k$, which would contradict $\sigma\left(  k\right)  =k$.
Thus, we cannot have $k=n$. Hence, we have $k\neq n$, so that $k<n$.
\end{noncompile}

Assume first that $k\leq i$. We have $\sigma\left(  1\right)  <\sigma\left(
2\right)  <\cdots<\sigma\left(  i\right)  $, thus $\sigma\left(  1\right)
<\sigma\left(  2\right)  <\cdots<\sigma\left(  k\right)  $ (since $k\leq i$).
Thus, the $k$ integers $\sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  k\right)  $ are distinct.

Also, $\sigma\left(  1\right)  \neq1$, so that $\sigma\left(  1\right)  >1$,
so that $\sigma\left(  1\right)  \geq2$. Hence,
\[
2\leq\sigma\left(  1\right)  <\sigma\left(  2\right)  <\cdots<\sigma\left(
k\right)  =k.
\]
Hence, the $k$ integers $\sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  k\right)  $ all lie between $2$ and $k$; that is, they
lie in the set $\left\{  2,3,\ldots,k\right\}  $. Since this set $\left\{
2,3,\ldots,k\right\}  $ has only $k-1$ elements, this shows (by the pigeonhole
principle) that at least two of the $k$ integers $\sigma\left(  1\right)
,\sigma\left(  2\right)  ,\ldots,\sigma\left(  k\right)  $ must be equal. But
this contradicts the fact that the $k$ integers $\sigma\left(  1\right)
,\sigma\left(  2\right)  ,\ldots,\sigma\left(  k\right)  $ are distinct.

This contradiction shows that our assumption (that $k\leq i$) was false.
Hence, we don't have $k\leq i$. In other words, we have $k>i$. Hence, $k\geq
i+1$.

We have $\sigma\left(  i+1\right)  <\sigma\left(  i+2\right)  <\cdots
<\sigma\left(  n\right)  $, thus $\sigma\left(  k\right)  <\sigma\left(
k+1\right)  <\cdots<\sigma\left(  n\right)  $ (since $k\geq i+1$). Thus, the
$n-k+1$ integers $\sigma\left(  k\right)  ,\sigma\left(  k+1\right)
,\ldots,\sigma\left(  n\right)  $ are distinct.

But $\sigma\left(  n\right)  \neq n$, so that $\sigma\left(  n\right)  <n$, so
that $\sigma\left(  n\right)  \leq n-1$. From $\sigma\left(  k\right)  =k$, we
obtain%
\[
k=\sigma\left(  k\right)  <\sigma\left(  k+1\right)  <\cdots<\sigma\left(
n\right)  \leq n-1.
\]
Hence, the $n-k+1$ integers $\sigma\left(  k\right)  ,\sigma\left(
k+1\right)  ,\ldots,\sigma\left(  n\right)  $ all lie between $k$ and $n-1$;
that is, they lie in the set $\left\{  k,k+1,\ldots,n-1\right\}  $. Since this
set $\left\{  k,k+1,\ldots,n-1\right\}  $ has only $n-k$ elements, this shows
(by the pigeonhole principle) that at least two of the $n-k+1$ integers
$\sigma\left(  k\right)  ,\sigma\left(  k+1\right)  ,\ldots,\sigma\left(
n\right)  $ must be equal. But this contradicts the fact that the $n-k+1$
integers $\sigma\left(  k\right)  ,\sigma\left(  k+1\right)  ,\ldots
,\sigma\left(  n\right)  $ are distinct.

Now, forget that we fixed $k$. We thus have derived a contradiction for any
fixed point $k$ of $\sigma$. Hence, there exists no fixed point $k$ of
$\sigma$. In other words, the permutation $\sigma$ has no fixed points. In
other words, $\sigma$ is a derangement.

Next, we shall show that the only descent of $\sigma$ is $i$.

The map $\sigma$ is a permutation, thus injective. Hence, $\sigma\left(
i\right)  \neq\sigma\left(  i+1\right)  $.

Assume (for the sake of contradiction) that $\sigma\left(  i\right)
\leq\sigma\left(  i+1\right)  $. Hence, $\sigma\left(  i\right)
<\sigma\left(  i+1\right)  $ (since $\sigma\left(  i\right)  \neq\sigma\left(
i+1\right)  $). Now,%
\[
\sigma\left(  1\right)  <\sigma\left(  2\right)  <\cdots<\sigma\left(
i\right)  <\sigma\left(  i+1\right)  <\sigma\left(  i+2\right)  <\cdots
<\sigma\left(  n\right)  .
\]
In other words, $\sigma\left(  1\right)  <\sigma\left(  2\right)
<\cdots<\sigma\left(  n\right)  $. Hence, the numbers $\sigma\left(  1\right)
,\sigma\left(  2\right)  ,\ldots,\sigma\left(  n\right)  $ are precisely the
elements of $\left[  n\right]  $ written down in increasing order (since
$\sigma$ is a permutation). In other words, $\sigma\left(  k\right)  =k$ for
each $k\in\left[  n\right]  $. Applying this to $k=1$, we find $\sigma\left(
1\right)  =1$. This contradicts $\sigma\left(  1\right)  \neq1$.

This contradiction shows that our assumption (that $\sigma\left(  i\right)
\leq\sigma\left(  i+1\right)  $) was false. Thus, we have $\sigma\left(
i\right)  >\sigma\left(  i+1\right)  $. In other words, $i$ is a descent of
$\sigma$. Moreover, $\sigma$ cannot have any other descents than $i$ (since
$\sigma\left(  1\right)  <\sigma\left(  2\right)  <\cdots<\sigma\left(
i\right)  $ and $\sigma\left(  i+1\right)  <\sigma\left(  i+2\right)
<\cdots<\sigma\left(  n\right)  $); thus, $i$ is the only descent of $\sigma$.
Hence, $\sigma$ is a derangement of $\left[  n\right]  $ whose only descent is
$i$. This proves Lemma \ref{lem.1descent.der}.
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.1descent.i}.]From $i \in\left[  n-1\right]  $,
we obtain $1 \leq i \leq n-1$, so that $n-1 \geq1$. Hence, $n \geq2$.

Let us first analyze how a derangement of $\left[  n\right]  $ whose only
descent is $i$ looks like.

Let $\sigma$ be a derangement of $\left[  n\right]  $ whose only descent is
$i$. Thus,%
\begin{equation}
\sigma\left(  1\right)  <\sigma\left(  2\right)  <\cdots<\sigma\left(
i\right)  \label{sol.1descent.der.main.pf.1}%
\end{equation}
and%
\begin{equation}
\sigma\left(  i+1\right)  <\sigma\left(  i+2\right)  <\cdots<\sigma\left(
n\right)  \label{sol.1descent.der.main.pf.2}%
\end{equation}
but $\sigma\left(  i\right)  >\sigma\left(  i+1\right)  $.

Since $\sigma$ is a derangement, we know that $\sigma$ has no fixed points.
Hence, in particular, $1$ cannot be a fixed point of $\sigma$. Thus,
$\sigma\left(  1\right)  \neq1$. Also, (\ref{sol.1descent.der.main.pf.1})
shows that the numbers $\sigma\left(  2\right)  ,\sigma\left(  3\right)
,\ldots,\sigma\left(  i\right)  $ are greater than $\sigma\left(  1\right)  $,
and therefore greater than $1$ (since $\sigma\left(  1\right)  \geq1$); thus,
they are distinct from $1$. Hence, all the $i$ numbers $\sigma\left(
1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(  i\right)  $ are
distinct from $1$.

Furthermore, $n$ cannot be a fixed point of $\sigma$ (since $\sigma$ has no
fixed points). Hence, $\sigma\left(  n\right)  \neq n$. Also,
(\ref{sol.1descent.der.main.pf.2}) shows that the numbers $\sigma\left(
i+1\right)  ,\sigma\left(  i+2\right)  ,\ldots,\sigma\left(  n-1\right)  $ are
smaller than $\sigma\left(  n\right)  $, and thus smaller than $n$ (since
$\sigma\left(  n\right)  \leq n$); thus, they are distinct from $n$. Hence,
all the $n-i$ numbers $\sigma\left(  i+1\right)  ,\sigma\left(  i+2\right)
,\ldots,\sigma\left(  n\right)  $ are distinct from $n$. Therefore,
$\sigma^{-1}\left(  n\right)  \notin\left\{  i+1,i+2,\ldots,n\right\}  $.
Thus,%
\[
\sigma^{-1}\left(  n\right)  \in\left[  n\right]  \setminus\left\{
i+1,i+2,\ldots,n\right\}  =\left\{  1,2,\ldots,i\right\}  .
\]
In other words, $n=\sigma\left(  j\right)  $ for some $j\in\left\{
1,2,\ldots,i\right\}  $. In other words, one of the numbers $\sigma\left(
1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(  i\right)  $ is $n$.

So we know that all the $i$ numbers $\sigma\left(  1\right)  ,\sigma\left(
2\right)  ,\ldots,\sigma\left(  i\right)  $ are distinct from $1$, but one of
these numbers is $n$. Thus, $\left\{  \sigma\left(  1\right)  ,\sigma\left(
2\right)  ,\ldots,\sigma\left(  i\right)  \right\}  $ is a subset of $\left\{
2,3,\ldots,n\right\}  $ that contains $n$. This subset is clearly an
$i$-element subset (since $\sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  i\right)  $ are distinct).

Now, forget that we fixed $\sigma$. We thus have proven that if $\sigma$ is a
derangement of $\left[  n\right]  $ whose only descent is $i$, then $\left\{
\sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
i\right)  \right\}  $ is an $i$-element subset of $\left\{  2,3,\ldots
,n\right\}  $ that contains $n$. Furthermore, if we know this subset, then we
can uniquely reconstruct the whole permutation $\sigma$: Indeed, its first $i$
values $\sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
i\right)  $ are simply the elements of this subset written in increasing order
(because of (\ref{sol.1descent.der.main.pf.1})), whereas the remaining $n-i$
values $\sigma\left(  i+1\right)  ,\sigma\left(  i+2\right)  ,\ldots
,\sigma\left(  n\right)  $ are the remaining $n-i$ elements of $\left[
n\right]  $ written in increasing order (because of
(\ref{sol.1descent.der.main.pf.2})).

Thus, the following algorithm constructs every possible derangement $\sigma$
of $\left[  n\right]  $ whose only descent is $i$:

\begin{itemize}
\item First, choose an $i$-element subset $S$ of $\left\{  2,3,\ldots
,n\right\}  $ that contains $n$ to become the set $\left\{  \sigma\left(
1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(  i\right)  \right\}
$. There are $\dbinom{n-2}{i-1}$ choices here\footnote{Here, we are using the
fact that the number of $i$-element subsets $S$ of $\left\{  2,3,\ldots
,n\right\}  $ that contain $n$ is $\dbinom{n-2}{i-1}$. This is easy to prove
(in fact, choosing such a subset means choosing its $i-1$ elements other than
$n$; and these $i-1$ elements are chosen from the $\left(  n-2\right)
$-element set $\left\{  2,3,\ldots,n-1\right\}  $).}.

\item Then, the values of $\sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  i\right)  $ are uniquely determined (indeed, they have
to be the $i$ elements of $S$ in increasing order).

\item Furthermore, the values of $\sigma\left(  i+1\right)  ,\sigma\left(
i+2\right)  ,\ldots,\sigma\left(  n\right)  $ are also uniquely determined
(indeed, they have to be the $n-i$ elements of $\left[  n\right]  \setminus S$
in increasing order).
\end{itemize}

Furthermore, every permutation $\sigma$ constructed by this algorithm is
actually a derangement $\sigma$ of $\left[  n\right]  $ whose only descent is
$i$\ \ \ \ \footnote{\textit{Proof.} Let $\sigma$ be a permutation constructed
by this algorithm. From the definition of the algorithm, it follows
immediately that $\sigma\left(  1\right)  <\sigma\left(  2\right)
<\cdots<\sigma\left(  i\right)  $ and $\sigma\left(  i+1\right)
<\sigma\left(  i+2\right)  <\cdots<\sigma\left(  n\right)  $ and $\left\{
\sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
i\right)  \right\}  =S$ (where $S$ is the $i$-element subset of $\left\{
2,3,\ldots,n\right\}  $ that was chosen during the algorithm).
\par
We have $i\geq1$, so that $\sigma\left(  1\right)  \in\left\{  \sigma\left(
1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(  i\right)  \right\}
=S\subseteq\left\{  2,3,\ldots,n\right\}  $. Thus, $\sigma\left(  1\right)
\geq2>1$, so that $\sigma\left(  1\right)  \neq1$.
\par
The definition of $S$ yields $n\in S=\left\{  \sigma\left(  1\right)
,\sigma\left(  2\right)  ,\ldots,\sigma\left(  i\right)  \right\}  $, so that
$\sigma^{-1}\left(  n\right)  \in\left\{  1,2,\ldots,i\right\}  $ and thus
$\sigma^{-1}\left(  n\right)  \leq i\leq n-1<n$. Thus, $\sigma^{-1}\left(
n\right)  \neq n$, so that $\sigma\left(  n\right)  \neq n$.
\par
Thus, Lemma \ref{lem.1descent.der} shows that $\sigma$ is a derangement of
$\left[  n\right]  $ whose only descent is $i$. This is what we wanted to
prove.}. Hence, the number of derangements $\sigma$ of $\left[  n\right]  $
whose only descent is $i$ equals the number of ways to perform the above
algorithm. But the latter number is clearly $\dbinom{n-2}{i-1}$ (since there
are $\dbinom{n-2}{i-1}$ choices in the first step, and the next two steps are
uniquely determined). Thus, the number of derangements $\sigma$ of $\left[
n\right]  $ whose only descent is $i$ equals $\dbinom{n-2}{i-1}$. This proves
Proposition \ref{prop.1descent.i}.
\end{proof}

Let us next recall a fundamental fact (which has already been proven in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{the solutions to
homework set 1}):

\begin{proposition}
\label{prop.pascal-rowsum}Let $m\in\mathbb{N}$. Then,%
\[
\sum_{k=0}^{m}\dbinom{m}{k}=2^{m}.
\]

\end{proposition}

\begin{proof}
[Solution to Exercise \ref{exe.1descent.der} (sketched).]The answer is%
\[%
\begin{cases}
1, & \text{if }n=0;\\
0, & \text{if }n=1;\\
2^{n-2}, & \text{if }n>1
\end{cases}
.
\]


\textit{Proof.} We WLOG assume that $n>1$ (since the cases when $n=0$ and when
$n=1$ can be easily dealt with). Thus, $n\geq2$, so that $n-2\in\mathbb{N}$.

The only permutation having no descents is $\operatorname*{id}$, and this is
not a derangement (since $\operatorname*{id}$ has $n>0$ fixed points). Thus,
there exists no derangement having no descents. In other words,%
\[
\left(  \text{the number of all derangements having no descents}\right)  =0.
\]


Now,
\begin{align*}
&  \left(  \text{the number of all derangements having at most }1\text{
descent}\right) \\
&  =\underbrace{\left(  \text{the number of all derangements having no
descents}\right)  }_{=0}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{the number of all derangements having
exactly }1\text{ descent}\right) \\
&  =\left(  \text{the number of all derangements having exactly }1\text{
descent}\right) \\
&  =\underbrace{\sum_{i\in\left[  n-1\right]  }}_{=\sum_{i=1}^{n-1}%
}\underbrace{\left(  \text{the number of derangements of }\left[  n\right]
\text{ whose only descent is }i\right)  }_{\substack{=\dbinom{n-2}%
{i-1}\\\text{(by Proposition \ref{prop.1descent.i})}}}\\
&  =\sum_{i=1}^{n-1}\dbinom{n-2}{i-1}=\sum_{k=0}^{n-2}\dbinom{n-2}%
{k}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have substituted }k\\
\text{for }i-1\text{ in the sum}%
\end{array}
\right) \\
&  =2^{n-2}\ \ \ \ \ \ \ \ \ \ \left(  \text{by Proposition
\ref{prop.pascal-rowsum}, applied to }m=n-2\right) \\
&  =%
\begin{cases}
1, & \text{if }n=0;\\
0, & \text{if }n=1;\\
2^{n-2}, & \text{if }n>1
\end{cases}
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }n>1\right)  .
\end{align*}
This completes the proof.
\end{proof}

\subsection{Connected permutations}

\begin{definition}
Let $n$ be a positive integer. A permutation $\sigma$ of $\left[  n\right]  $
is said to be \textit{connected} if and only if there exists no $k\in\left[
n-1\right]  $ such that $\sigma\left(  \left[  k\right]  \right)  =\left[
k\right]  $.
\end{definition}

For example, the permutation $\sigma$ of $\left[  5\right]  $ sending
$1,2,3,4,5$ to $2,4,1,5,3$ is connected, since it satisfies
\begin{align*}
\sigma\left(  \left[  1\right]  \right)   &  =\left\{  2\right\}  \neq\left[
1\right]  ,\ \ \ \ \ \ \ \ \ \ \sigma\left(  \left[  2\right]  \right)
=\left\{  2,4\right\}  \neq\left[  2\right]  ,\\
\sigma\left(  \left[  3\right]  \right)   &  =\left\{  2,4,1\right\}
\neq\left[  3\right]  ,\ \ \ \ \ \ \ \ \ \ \sigma\left(  \left[  4\right]
\right)  =\left\{  2,4,1,5\right\}  \neq\left[  4\right]  .
\end{align*}
But the permutation $\sigma$ of $\left[  4\right]  $ sending $1,2,3,4$ to
$2,1,4,3$ is not connected, because it satisfies $\sigma\left(  \left[
2\right]  \right)  =\left[  2\right]  $. Likewise, a permutation $\sigma$ of
$\left[  n\right]  $ (for $n>1$) satisfying $\sigma\left(  1\right)  =1$ is
never connected (since $\sigma\left(  \left[  1\right]  \right)  =\left[
1\right]  $); the same holds for a permutation $\sigma$ satisfying
$\sigma\left(  n\right)  =n$ (since $\sigma\left(  \left[  n-1\right]
\right)  =\left[  n-1\right]  $).

\begin{exercise}
\label{exe.connperm}For each positive integer $n$, let $c_{n}$ denote the
number of all connected permutations of $\left[  n\right]  $. (Thus, $c_{1}%
=1$, $c_{2}=1$ and $c_{3}=3$.)

Prove that%
\[
n!=\sum_{k=1}^{n}c_{k}\left(  n-k\right)  !\ \ \ \ \ \ \ \ \ \ \text{for each
positive integer }n.
\]

\end{exercise}

Exercise \ref{exe.connperm} appears (with an outline of a solution) in
\cite[\S 3.4, Example: Connected permutations]{Cameron-AC1}. See also
\href{https://oeis.org/A003319}{Sequence A003319 in the OEIS database} for the
sequence $\left(  c_{1},c_{2},c_{3},\ldots\right)  $.

\begin{proof}
[Solution to Exercise \ref{exe.connperm} (sketched).]Let $n$ be a positive integer.

If $\sigma\in S_{n}$, then a \textit{return} of $\sigma$ shall denote a
positive integer $k\in\left[  n\right]  $ satisfying $\sigma\left(  \left[
k\right]  \right)  =\left[  k\right]  $. Every $\sigma\in S_{n}$ has at least
one return, namely the number $n$ (since $\sigma\left(  \left[  n\right]
\right)  =\left[  n\right]  $); thus, the smallest return of $\sigma$ is well-defined.

It is easy to see that a permutation $\sigma\in S_{n}$ is connected if and
only if its smallest return is $n$. We shall not use this, but we shall use
the following closely connected fact:

\begin{statement}
\textit{Observation 1:} Let $j\in\left[  n\right]  $. The number of
permutations $\sigma\in S_{n}$ whose smallest return is $j$ equals
$c_{j}\left(  n-j\right)  !$.
\end{statement}

[\textit{Proof of Observation 1:} Let $\sigma\in S_{n}$ be a permutation whose
smallest return is $j$. Then, $j$ is a return of $\sigma$; in other words,
$\sigma\left(  \left[  j\right]  \right)  =\left[  j\right]  $ (by the
definition of a return). Hence, $\sigma\left(  h\right)  \in\sigma\left(
\left[  j\right]  \right)  =\left[  j\right]  $ for each $h\in\left[
j\right]  $. Thus, we can define a map
\[
\tau:\left[  j\right]  \rightarrow\left[  j\right]
,\ \ \ \ \ \ \ \ \ \ h\mapsto\sigma\left(  h\right)  .
\]
(This map $\tau$ is essentially the restriction of $\sigma$ to $\left[
j\right]  $, but the codomain is also being restricted to $\left[  j\right]
$.) The map $\tau$ is injective (since $\sigma$ is injective), and thus is a
permutation of $\left[  j\right]  $ (since it is an injective map between two
finite sets of equal size). Moreover, the permutation $\tau$ of $\left[
j\right]  $ is connected\footnote{\textit{Proof.} If there was some
$k\in\left[  j-1\right]  $ such that $\tau\left(  \left[  k\right]  \right)
=\left[  k\right]  $, then this $k$ would be a return of $\sigma$ (because the
definition of $\tau$ shows that $\tau\left(  \left[  k\right]  \right)
=\sigma\left(  \left[  k\right]  \right)  $, so that $\sigma\left(  \left[
k\right]  \right)  =\tau\left(  \left[  k\right]  \right)  =\left[  k\right]
$), which would contradict the fact that $j$ is the \textbf{smallest} return
of $\sigma$ (indeed, $k$ is smaller than $j$). Hence, there exists no
$k\in\left[  j-1\right]  $ such that $\tau\left(  \left[  k\right]  \right)
=\left[  k\right]  $. In other words, the permutation $\tau$ of $\left[
j\right]  $ is connected (by the definition of \textquotedblleft
connected\textquotedblright).}.

Now, forget that we fixed $\sigma$. Thus, for each permutation $\sigma\in
S_{n}$ whose smallest return is $j$, we have constructed a connected
permutation $\tau$ of $\left[  j\right]  $. Let us denote this $\tau$ by
$\tau_{\sigma}$ (to stress its dependence on $\sigma$). We now have the
following algorithm to construct every permutation $\sigma\in S_{n}$ whose
smallest return is $j$:

\begin{itemize}
\item First, pick any connected permutation $\tau$ of $\left[  j\right]  $;
this permutation shall be the $\tau_{\sigma}$ corresponding to our $\sigma$.
There are $c_{j}$ choices at this step, since the number of connected
permutations of $\left[  j\right]  $ is $c_{j}$ (by the definition of $c_{j}$).

\item The values $\sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  j\right)  $ are now uniquely determined (because they
are the values of the already chosen permutation $\tau_{\sigma}=\tau$), and
are simply the numbers $1,2,\ldots,j$ in some order. Next, choose the
remaining values $\sigma\left(  j+1\right)  ,\sigma\left(  j+2\right)
,\ldots,\sigma\left(  n\right)  $. These $n-j$ values must be the numbers
$j+1,j+2,\ldots,n$ in some order; the only choice at this step is which order
they are in. Thus, there are $\left(  n-j\right)  !$ choices at this step.
\end{itemize}

Our argument above shows that each permutation $\sigma\in S_{n}$ whose
smallest return is $j$ can be constructed by this algorithm. Conversely, it is
easy to see (more or less by reversing the above argument) that every $\sigma$
constructed by this algorithm is a permutation $\sigma\in S_{n}$ whose
smallest return is $j$. Moreover, every set of choices during the algorithm
yields a different such permutation. Thus, the number of permutations
$\sigma\in S_{n}$ whose smallest return is $j$ equals the number of ways of
making choices during the algorithm. But the latter number is $c_{j}\left(
n-j\right)  !$ (since we have $c_{j}$ choices at the first step, and $\left(
n-j\right)  !$ choices at the second step). Thus, the number of permutations
$\sigma\in S_{n}$ whose smallest return is $j$ equals $c_{j}\left(
n-j\right)  !$. This proves Observation 1.]

Now,
\begin{align*}
n!  &  =\left(  \text{the number of permutations }\sigma\in S_{n}\right) \\
&  =\underbrace{\sum_{j\in\left[  n\right]  }}_{=\sum_{j=1}^{n}}%
\underbrace{\left(  \text{the number of permutations }\sigma\in S_{n}\text{
whose smallest return is }j\right)  }_{\substack{=c_{j}\left(  n-j\right)
!\\\text{(by Observation 1)}}}\\
&  =\sum_{j=1}^{n}c_{j}\left(  n-j\right)  !=\sum_{k=1}^{n}c_{k}\left(
n-k\right)  !
\end{align*}
(here, we have renamed the summation index $j$ as $k$). This solves Exercise
\ref{exe.connperm}.
\end{proof}

\begin{remark}
Notice the similarity between our above solution of Exercise
\ref{exe.connperm} and the proof of the recursion%
\[
m_{n}=\sum_{k=0}^{n-1}m_{k}m_{n-k-1}%
\]
(for $n>0$) for the Catalan numbers $m_{0},m_{1},m_{2},\ldots$ (see, e.g.,
\cite[\S 24, problem (2)]{Galvin17}).
\end{remark}

\subsection{Permutations and intervals}

An \textit{integer interval} means a set of the form $\left\{  a,a+1,\ldots
,b\right\}  $ for some integers $a$ and $b$. (If $a>b$, then this set is
understood to be empty.)

\begin{exercise}
\label{exe.perm-int}Let $n\in\mathbb{N}$ and $r\in\left[  n\right]  $. A
permutation $\sigma$ of $\left[  n\right]  $ is said to be $r$%
\textit{-friendly} if for each $k\in\left\{  r,r+1,\ldots,n\right\}  $, the
set $\sigma\left(  \left[  k\right]  \right)  $ is an integer interval.

(For example, the permutation $\sigma$ of $\left[  6\right]  $ sending
$1,2,3,4,5,6$ to $2,4,3,5,1,6$ is $3$-friendly (since $\sigma\left(  \left[
3\right]  \right)  =\left\{  2,3,4\right\}  $, $\sigma\left(  \left[
4\right]  \right)  =\left\{  2,3,4,5\right\}  $, $\sigma\left(  \left[
5\right]  \right)  =\left\{  1,2,3,4,5\right\}  $ and $\sigma\left(  \left[
6\right]  \right)  =\left\{  1,2,3,4,5,6\right\}  $ are integer intervals),
and thus also $r$-friendly for each $r\geq3$, but not $2$-friendly (since
$\sigma\left(  \left[  2\right]  \right)  =\left\{  2,4\right\}  $ is not an
integer interval).)

Prove that the number of $r$-friendly permutations of $\left[  n\right]  $ is
$2^{n-r}r!$.
\end{exercise}

See
\url{https://artofproblemsolving.com/community/c6h1542350_rfriendly_permutations_sending_some_intervals_to_intervals}
for a discussion of this exercise.

Before we solve this exercise, let us state two simple lemmas:

\begin{lemma}
\label{lem.perm-int.int-s}Let $S$ and $T$ be two integer intervals such that
$T\subseteq S$ and $\left\vert S\right\vert =\left\vert T\right\vert +1$.
Then, either $T=S\setminus\left\{  \max S\right\}  $ or $T=S\setminus\left\{
\min S\right\}  $ (or both).
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.perm-int.int-s} (sketched).]Write the integer
interval $S$ in the form $S=\left\{  a,a+1,\ldots,b\right\}  $ for some
integers $a$ and $b$.

From $T\subseteq S$, we obtain $\left\vert S\setminus T\right\vert =\left\vert
S\right\vert -\left\vert T\right\vert =1$ (since $\left\vert S\right\vert
=\left\vert T\right\vert +1$). In other words, $S\setminus T$ is a $1$-element
set. In other words, $S\setminus T=\left\{  k\right\}  $ for some object $k$.
Consider this $k$.

From $T\subseteq S$, we obtain $T=S\setminus\underbrace{\left(  S\setminus
T\right)  }_{=\left\{  k\right\}  }=S\setminus\left\{  k\right\}  $. Thus,
$S\setminus\left\{  k\right\}  $ is an integer interval (since $T$ is an
integer interval).

Also, $k\in\left\{  k\right\}  =S\setminus T\subseteq S=\left\{
a,a+1,\ldots,b\right\}  $. Hence, $k$ is an integer satisfying $a\leq k\leq b$.

From $S=\left\{  a,a+1,\ldots,b\right\}  $ (and $a\leq b$), we obtain $\min
S=a$ and $\max S=b$.

Recall that $k\in\left\{  a,a+1,\ldots,b\right\}  $. Thus, we are in one of
the following three cases:

\textit{Case 1:} We have $k=a$.

\textit{Case 2:} We have $a<k<b$.

\textit{Case 3:} We have $k=b$.

Let us first consider Case 1. In this case, we have $k=a$. Thus,
$T=S\setminus\left\{  \underbrace{k}_{=a=\min S}\right\}  =S\setminus\left\{
\min S\right\}  $. Hence, either $T=S\setminus\left\{  \max S\right\}  $ or
$T=S\setminus\left\{  \min S\right\}  $ (or both). Therefore, Lemma
\ref{lem.perm-int.int-s} is proven in Case 1.

Let us now consider Case 2. In this case, we have $a<k<b$. Now,%
\begin{align*}
T  &  =\underbrace{S}_{=\left\{  a,a+1,\ldots,b\right\}  }\setminus\left\{
k\right\}  =\left\{  a,a+1,\ldots,b\right\}  \setminus\left\{  k\right\} \\
&  =\left\{  a,a+1,\ldots,k-1,k+1,k+2,\ldots,b\right\}
\end{align*}
(since $a<k<b$). Hence, the set $T$ contains the two elements $a$ and $b$ but
not the element $k$ that lies between them (in the sense of being larger than
$a$ but smaller than $b$). Therefore, the set $T$ is not an integer interval.
This contradicts the fact that $T$ is an integer interval. Hence, Case 2 is impossible.

Let us finally consider Case 3. In this case, we have $k=b$. Thus,
$T=S\setminus\left\{  \underbrace{k}_{=b=\max S}\right\}  =S\setminus\left\{
\max S\right\}  $. Hence, either $T=S\setminus\left\{  \max S\right\}  $ or
$T=S\setminus\left\{  \min S\right\}  $ (or both). Therefore, Lemma
\ref{lem.perm-int.int-s} is proven in Case 3.

We have thus proven Lemma \ref{lem.perm-int.int-s} in the two Cases 1 and 3.
Since these two cases are the only possibilities (because we have shown that
Case 2 is impossible), we thus conclude that Lemma \ref{lem.perm-int.int-s}
always holds.
\end{proof}

\begin{lemma}
\label{lem.perm-int.2}Let $n\in\mathbb{N}$ and $r\in\left[  n\right]  $. Let
$\sigma$ be an $r$-friendly permutation of $\left[  n\right]  $. Let
$k\in\left\{  r+1,r+2,\ldots,n\right\}  $. Then, the following holds:

\textbf{(a)} Both $\sigma\left(  \left[  k-1\right]  \right)  $ and
$\sigma\left(  \left[  k\right]  \right)  $ are integer intervals.

\textbf{(b)} The integer interval $\sigma\left(  \left[  k-1\right]  \right)
$ is obtained from the integer interval $\sigma\left(  \left[  k\right]
\right)  $ by removing either its largest or its smallest element.

\textbf{(c)} This element removed from $\sigma\left(  \left[  k\right]
\right)  $ is $\sigma\left(  k\right)  $.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.perm-int.2}.]\textbf{(a)} We have $k\in\left\{
r+1,r+2,\ldots,n\right\}  $, so that $k-1\in\left\{  r,r+1,\ldots,n-1\right\}
\subseteq\left\{  r, r+1, \ldots, n \right\}  $.

But $\sigma$ is $r$-friendly. Thus, $\sigma\left(  \left[  k-1\right]
\right)  $ is an integer interval (since $k-1\in\left\{  r,r+1,\ldots
,n\right\}  $). For the same reason, $\sigma\left(  \left[  k\right]  \right)
$ is an integer interval (since $k\in\left\{  r+1,r+2,\ldots,n\right\}
\subseteq\left\{  r,r+1,\ldots,n\right\}  $). Thus, Lemma~\ref{lem.perm-int.2}
\textbf{(a)} is proven.

\textbf{(b)} From Lemma~\ref{lem.perm-int.2} \textbf{(a)}, we know that both
$\sigma\left(  \left[  k-1\right]  \right)  $ and $\sigma\left(  \left[
k\right]  \right)  $ are integer intervals. Moreover, the map $\sigma$ is
injective; therefore, $\left\vert \sigma\left(  \left[  k\right]  \right)
\right\vert =\left\vert \left[  k\right]  \right\vert =k$ and similarly
$\left\vert \sigma\left(  \left[  k-1\right]  \right)  \right\vert =k-1$.
Hence, $\left\vert \sigma\left(  \left[  k-1\right]  \right)  \right\vert
+1=k$. Comparing this with $\left\vert \sigma\left(  \left[  k\right]
\right)  \right\vert =k$, we obtain $\left\vert \sigma\left(  \left[
k\right]  \right)  \right\vert =\left\vert \sigma\left(  \left[  k-1\right]
\right)  \right\vert +1$.

But $\left[  k-1\right]  \subseteq\left[  k\right]  $, so that $\sigma\left(
\left[  k-1\right]  \right)  \subseteq\sigma\left(  \left[  k\right]  \right)
$. Hence, Lemma \ref{lem.perm-int.int-s} (applied to $S=\sigma\left(  \left[
k\right]  \right)  $ and $T=\sigma\left(  \left[  k-1\right]  \right)  $)
shows that either $\sigma\left(  \left[  k-1\right]  \right)  =\sigma\left(
\left[  k\right]  \right)  \setminus\left\{  \max\left(  \sigma\left(  \left[
k\right]  \right)  \right)  \right\}  $ or $\sigma\left(  \left[  k-1\right]
\right)  =\sigma\left(  \left[  k\right]  \right)  \setminus\left\{
\min\left(  \sigma\left(  \left[  k\right]  \right)  \right)  \right\}  $ (or
both). In other words, the integer interval $\sigma\left(  \left[  k-1\right]
\right)  $ is obtained from the integer interval $\sigma\left(  \left[
k\right]  \right)  $ by removing either its largest or its smallest element.
This proves Lemma \ref{lem.perm-int.2} \textbf{(b)}.

\textbf{(c)} The element removed from $\sigma\left(  \left[  k\right]
\right)  $ is the unique element of $\sigma\left(  \left[  k\right]  \right)
\setminus\sigma\left(  \left[  k-1\right]  \right)  $. Thus, we must prove
that the unique element of $\sigma\left(  \left[  k\right]  \right)
\setminus\sigma\left(  \left[  k-1\right]  \right)  $ is $\sigma\left(
k\right)  $.

The map $\sigma$ is a bijection. Hence, $\sigma\left(  X\setminus Y\right)
=\sigma\left(  X\right)  \setminus\sigma\left(  Y\right)  $ for any two
subsets $X$ and $Y$ of $\left[  n\right]  $. Applying this to $X=\sigma\left(
\left[  k\right]  \right)  $ and $Y=\sigma\left(  \left[  k-1\right]  \right)
$, we obtain $\sigma\left(  \left[  k\right]  \setminus\left[  k-1\right]
\right)  =\sigma\left(  \left[  k\right]  \right)  \setminus\sigma\left(
\left[  k-1\right]  \right)  $. Hence,%
\[
\sigma\left(  \left[  k\right]  \right)  \setminus\sigma\left(  \left[
k-1\right]  \right)  =\sigma\left(  \underbrace{\left[  k\right]
\setminus\left[  k-1\right]  }_{=\left\{  k\right\}  }\right)  =\sigma\left(
\left\{  k\right\}  \right)  =\left\{  \sigma\left(  k\right)  \right\}  .
\]
Hence, the unique element of $\sigma\left(  \left[  k\right]  \right)
\setminus\sigma\left(  \left[  k-1\right]  \right)  $ is $\sigma\left(
k\right)  $. This proves Lemma~\ref{lem.perm-int.2} \textbf{(c)}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.perm-int} (sketched).]I claim that the
following algorithm constructs every $r$-friendly permutation $\sigma$ of
$\left[  n\right]  $:

\begin{itemize}
\item We construct a sequence $\left(  I_{n},I_{n-1},\ldots,I_{r}\right)  $ of
subsets of $\left[  n\right]  $ with the property that $I_{n}\supseteq
I_{n-1}\supseteq\cdots\supseteq I_{r}$ and that each $I_{i}$ is an integer
interval of size $i$. This construction proceeds recursively (i.e., we start
with $I_{n}$, then construct $I_{n-1}$, then $I_{n-2}$, and so on until
$I_{r}$); it begins by setting $I_{n}=\left[  n\right]  $ (which is clearly a
subset of $\left[  n\right]  $ and an integer interval of size $n$). Then,
whenever a subset $I_{p}$ of $\left[  n\right]  $ is constructed (with
$p\in\left\{  r+1,r+2,\ldots,n\right\}  $), we define $I_{p-1}$ by removing
either the largest or the smallest element from $I_{p}$.

This construction clearly guarantees that $I_{p-1}$ will be a subset of
$\left[  n\right]  $ and an integer interval of size $p-1$, provided that
$I_{p}$ is a subset of $\left[  n\right]  $ and an integer interval of size
$p$. Also, it clearly guarantees that $I_{n}\supseteq I_{n-1}\supseteq
\cdots\supseteq I_{r}$.

\item Now, we define a map $\sigma:\left[  n\right]  \rightarrow\left[
n\right]  $ as follows: For each $p\in\left\{  r+1,r+2,\ldots,n\right\}  $, we
let $\sigma\left(  p\right)  $ be the element of $I_{p}$ that was removed in
the construction of $I_{p-1}$ (that is, the unique element of $I_{p}$ that is
not in $I_{p-1}$). Then, we define $\sigma\left(  1\right)  ,\sigma\left(
2\right)  ,\ldots,\sigma\left(  r\right)  $ to be the $r$ elements of $I_{r}$
in any order.

Thus, a map $\sigma:\left[  n\right]  \rightarrow\left[  n\right]  $ is defined.
\end{itemize}

This algorithm has the following properties:

\begin{statement}
\textit{Observation 1:} The algorithm constructs an $r$-friendly permutation
$\sigma$ of $\left[  n\right]  $ (whatever choices were made during the algorithm).
\end{statement}

\begin{statement}
\textit{Observation 2:} Every $r$-friendly permutation of $\left[  n\right]  $
can be obtained through the algorithm. (That is, if $\tau$ is any $r$-friendly
permutation of $\left[  n\right]  $, then we can make the choices in the
algorithm in such a way that the resulting permutation $\sigma$ will be $\tau$.)
\end{statement}

\begin{statement}
\textit{Observation 3:} The algorithm can be performed in $2^{n-r}r!$ ways
(i.e., there is a total of $2^{n-r}r!$ options for the choices made during the algorithm).
\end{statement}

\begin{statement}
\textit{Observation 4:} Any two of these $2^{n-r}r!$ ways give rise to
different permutations $\sigma$.
\end{statement}

Clearly, once these four Observations are proven, we will immediately see that
the number of $r$-friendly permutations of $\left[  n\right]  $ is $2^{n-r}%
r!$. Thus, Exercise \ref{exe.perm-int} will be solved. Hence, it remains to
prove the four Observations.

[\textit{Proof of Observation 1:} We must prove that the map $\sigma:\left[
n\right]  \rightarrow\left[  n\right]  $ constructed by the algorithm is an
$r$-friendly permutation of $\left[  n\right]  $.

Indeed, this map $\sigma$ has the property that $\left\{  \sigma\left(
1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(  r\right)  \right\}
=I_{r}$ (because $\sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  r\right)  $ were defined to be the $r$ elements of
$I_{r}$ in any order). Hence,
\[
\sigma\left(  \left[  r\right]  \right)  =\sigma\left(  \left\{
1,2,\ldots,r\right\}  \right)  =\left\{  \sigma\left(  1\right)
,\sigma\left(  2\right)  ,\ldots,\sigma\left(  r\right)  \right\}  =I_{r}.
\]
Now, it is easy to check that
\begin{equation}
\sigma\left(  \left[  p\right]  \right)  =I_{p} \label{sol.perm-int.ob1.pf.1}%
\end{equation}
for each $p\in\left\{  r,r+1,\ldots,n\right\}  $%
\ \ \ \ \footnote{\textit{Proof of (\ref{sol.perm-int.ob1.pf.1}):} We shall
prove (\ref{sol.perm-int.ob1.pf.1}) by induction over $p$:
\par
The \textit{induction base} (i.e., the case $p=r$) follows from $\sigma\left(
\left[  r\right]  \right)  =I_{r}$.
\par
Now, let us handle the \textit{induction step}. Thus, we must prove
$\sigma\left(  \left[  p\right]  \right)  =I_{p}$ under the assumption that
$\sigma\left(  \left[  p-1\right]  \right)  =I_{p-1}$. Recall that
$\sigma\left(  p\right)  $ is the unique element of $I_{p}$ that is not in
$I_{p-1}$ (this is how $\sigma\left(  p\right)  $ was defined). Thus,
$I_{p}\setminus I_{p-1}=\left\{  \sigma\left(  p\right)  \right\}  $, so that
$I_{p}=I_{p-1}\cup\left\{  \sigma\left(  p\right)  \right\}  $ (since
$I_{p}\supseteq I_{p-1}$).
\par
Now,%
\begin{align*}
\sigma\left(  \underbrace{\left[  p\right]  }_{=\left[  p-1\right]
\cup\left\{  p\right\}  }\right)   &  =\sigma\left(  \left[  p-1\right]
\cup\left\{  p\right\}  \right)  =\underbrace{\sigma\left(  \left[
p-1\right]  \right)  }_{=I_{p-1}}\cup\underbrace{\sigma\left(  \left\{
p\right\}  \right)  }_{=\left\{  \sigma\left(  p\right)  \right\}  }%
=I_{p-1}\cup\left\{  \sigma\left(  p\right)  \right\} \\
&  =I_{p}.
\end{align*}
This completes the induction step. Thus, (\ref{sol.perm-int.ob1.pf.1}) is
proven.}. Applying this to $p=n$, we obtain $\sigma\left(  \left[  n\right]
\right)  =I_{n}=\left[  n\right]  $. Hence, the map $\sigma$ is surjective.
Thus, $\sigma$ is bijective (since any surjective map between two finite sets
of equal sizes is bijective). In other words, $\sigma$ is a permutation of
$\left[  n\right]  $. It remains to prove that $\sigma$ is $r$-friendly.

For each $p\in\left\{  r,r+1,\ldots,n\right\}  $, the set $\sigma\left(
\left[  p\right]  \right)  $ is the set $I_{p}$ (by
(\ref{sol.perm-int.ob1.pf.1})), and thus is an integer interval (since $I_{p}$
is an integer interval). Renaming $p$ as $k$ in this statement, we obtain the
following: For each $k\in\left\{  r,r+1,\ldots,n\right\}  $, the set
$\sigma\left(  \left[  k\right]  \right)  $ is an integer interval. In other
words, the permutation $\sigma$ is $r$-friendly (by the definition of
\textquotedblleft$r$-friendly\textquotedblright). Thus, Observation 1 is proven.]

[\textit{Proof of Observation 2:} Let $\tau$ be an $r$-friendly permutation of
$\left[  n\right]  $. We must show that $\tau$ can be obtained through the
algorithm. In other words, we have to explain which options we need to choose
in order for the resulting permutation $\sigma$ to be $\tau$.

This is actually easy. There are two kinds of choices in the algorithm: The
first kind of choice is the one made in the construction of $I_{p-1}$ from
$I_{p}$, in which we have to choose whether to remove the largest or the
smallest element from $I_{p}$. The second kind of choice is the choice of
order in which the elements of $I_{r}$ are set to be $\sigma\left(  1\right)
,\sigma\left(  2\right)  ,\ldots,\sigma\left(  r\right)  $.

So which options do we choose? In the first kind of choice, we choose to
remove the element $\tau\left(  r\right)  $;

TODO

Let $\sigma$ be an $r$-friendly permutation of $\left[  n\right]  $. Let
$k\in\left[  n-r\right]  $. Thus, $k\leq n-r$, so that $n-k\geq r$. Hence, the
two numbers $n-k$ and $n-k+1$ are both $\geq r$. Therefore, the sets
$\sigma\left(  \left[  n-k\right]  \right)  $ and $\sigma\left(  \left[
n-k+1\right]  \right)  $ are two integer intervals (since $\sigma$ is $r$-friendly).

TODO

]

[\textit{Proof of Observation 3:} TODO]

[\textit{Proof of Observation 4:} TODO]
\end{proof}

\subsection{Inverting a power series}

\begin{exercise}
\label{exe.inverting-ps}Find and prove an explicit formula for the coefficient
of $x^{n}$ in the formal power series $\dfrac{1}{1-x-x^{2}+x^{3}}$.

[\textbf{Hint:} The standard strategy is to factor $1-x-x^{2}+x^{3}$, then do
partial fraction decomposition. But it is perfectly legitimate to guess the
formula based on solving%
\[
\left(  1-x-x^{2}+x^{3}\right)  \left(  b_{0}+b_{1}x+b_{2}x^{2}+b_{3}%
x^{3}+b_{4}x^{4}+\cdots\right)  =1
\]
for the first few of the unknown coefficients $b_{0},b_{1},b_{2},\ldots$, and
then prove it by multiplying out. Either option works.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.inverting-ps} (sketched).]The answer is%
\begin{align*}
\dfrac{1}{1-x-x^{2}+x^{3}}  &  =\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}%
{2}\right\rfloor x^{n}\\
&  =1+x+2x^{2}+2x^{3}+3x^{4}+3x^{5}+4x^{6}+4x^{7}+\cdots.
\end{align*}


One simple way to prove this is to check that%
\begin{align}
&  \left(  1-x-x^{2}+x^{3}\right)  \left(  \sum_{n=0}^{\infty}\left\lfloor
\dfrac{n+2}{2}\right\rfloor x^{n}\right) \nonumber\\
&  =\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor x^{n}%
-x\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor x^{n}-x^{2}%
\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor x^{n}+x^{3}%
\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor x^{n}\nonumber\\
&  =\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor x^{n}%
-\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor x^{n+1}%
-\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor x^{n+2}%
+\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor x^{n+3}%
\nonumber\\
&  =\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor x^{n}%
-\sum_{n=1}^{\infty}\left\lfloor \dfrac{n+1}{2}\right\rfloor x^{n}-\sum
_{n=2}^{\infty}\left\lfloor \dfrac{n}{2}\right\rfloor x^{n}+\sum_{n=3}%
^{\infty}\left\lfloor \dfrac{n-1}{2}\right\rfloor x^{n}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have substituted }n-1\text{ for }n\text{ in the second sum,}\\
n-2\text{ for }n\text{ in the third, and }n-3\text{ for }n\text{ in the
fourth}%
\end{array}
\right) \nonumber\\
&  =\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor x^{n}-\left(
\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+1}{2}\right\rfloor x^{n}-\left\lfloor
\dfrac{0+1}{2}\right\rfloor x^{0}\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ -\left(  \sum_{n=0}^{\infty}\left\lfloor \dfrac{n}%
{2}\right\rfloor x^{n}-\left\lfloor \dfrac{0}{2}\right\rfloor x^{0}%
-\left\lfloor \dfrac{1}{2}\right\rfloor x^{1}\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \sum_{n=0}^{\infty}\left\lfloor \dfrac{n-1}%
{2}\right\rfloor x^{n}-\left\lfloor \dfrac{0-1}{2}\right\rfloor x^{0}%
-\left\lfloor \dfrac{1-1}{2}\right\rfloor x^{1}-\left\lfloor \dfrac{2-1}%
{2}\right\rfloor x^{2}\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have extended the ranges of the last three}\\
\text{sums in order for all of them to start at }n=0\text{; then, we}\\
\text{have subtracted back the extraneous addends}%
\end{array}
\right) \nonumber\\
&  =\underbrace{\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor
x^{n}-\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+1}{2}\right\rfloor x^{n}%
-\sum_{n=0}^{\infty}\left\lfloor \dfrac{n}{2}\right\rfloor x^{n}+\sum
_{n=0}^{\infty}\left\lfloor \dfrac{n-1}{2}\right\rfloor x^{n}}_{=\sum
_{n=0}^{\infty}\left(  \left\lfloor \dfrac{n+2}{2}\right\rfloor -\left\lfloor
\dfrac{n+1}{2}\right\rfloor -\left\lfloor \dfrac{n}{2}\right\rfloor
+\left\lfloor \dfrac{n-1}{2}\right\rfloor \right)  x^{n}}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left\lfloor \dfrac{0+1}{2}\right\rfloor
x^{0}+\left\lfloor \dfrac{0}{2}\right\rfloor x^{0}+\left\lfloor \dfrac{1}%
{2}\right\rfloor x^{1}-\left\lfloor \dfrac{0-1}{2}\right\rfloor x^{0}%
-\left\lfloor \dfrac{1-1}{2}\right\rfloor x^{1}-\left\lfloor \dfrac{2-1}%
{2}\right\rfloor x^{2}}_{=1}\nonumber\\
&  =\sum_{n=0}^{\infty}\left(  \left\lfloor \dfrac{n+2}{2}\right\rfloor
-\left\lfloor \dfrac{n+1}{2}\right\rfloor -\left\lfloor \dfrac{n}%
{2}\right\rfloor +\left\lfloor \dfrac{n-1}{2}\right\rfloor \right)  x^{n}+1.
\label{sol.inverting-ps.4}%
\end{align}


But each $q\in\mathbb{Q}$ satisfies%
\begin{equation}
\left\lfloor q+1\right\rfloor =\left\lfloor q\right\rfloor +1
\label{sol.inverting-ps.q}%
\end{equation}
(this is easy to check). Hence, each $n\in\mathbb{N}$ satisfies%
\begin{align}
&  \underbrace{\left\lfloor \dfrac{n+2}{2}\right\rfloor }%
_{\substack{=\left\lfloor \dfrac{n}{2}+1\right\rfloor =\left\lfloor \dfrac
{n}{2}\right\rfloor +1\\\text{(by (\ref{sol.inverting-ps.q}))}}%
}-\underbrace{\left\lfloor \dfrac{n+1}{2}\right\rfloor }%
_{\substack{=\left\lfloor \dfrac{n-1}{2}+1\right\rfloor =\left\lfloor
\dfrac{n-1}{2}\right\rfloor +1\\\text{(by (\ref{sol.inverting-ps.q}))}%
}}-\left\lfloor \dfrac{n}{2}\right\rfloor +\left\lfloor \dfrac{n-1}%
{2}\right\rfloor \nonumber\\
&  =\left(  \left\lfloor \dfrac{n}{2}\right\rfloor +1\right)  -\left(
\left\lfloor \dfrac{n-1}{2}\right\rfloor +1\right)  -\left\lfloor \dfrac{n}%
{2}\right\rfloor +\left\lfloor \dfrac{n-1}{2}\right\rfloor \nonumber\\
&  =0. \label{sol.inverting-ps.6}%
\end{align}
Thus, (\ref{sol.inverting-ps.4}) becomes%
\begin{align*}
&  \left(  1-x-x^{2}+x^{3}\right)  \left(  \sum_{n=0}^{\infty}\left\lfloor
\dfrac{n+2}{2}\right\rfloor x^{n}\right) \\
&  =\sum_{n=0}^{\infty}\underbrace{\left(  \left\lfloor \dfrac{n+2}%
{2}\right\rfloor -\left\lfloor \dfrac{n+1}{2}\right\rfloor -\left\lfloor
\dfrac{n}{2}\right\rfloor +\left\lfloor \dfrac{n-1}{2}\right\rfloor \right)
}_{\substack{=0\\\text{(by (\ref{sol.inverting-ps.6}))}}}x^{n}+1\\
&  =\underbrace{\sum_{n=0}^{\infty}0x^{n}}_{=0}+1=1.
\end{align*}
Hence, $\dfrac{1}{1-x-x^{2}+x^{3}}=\sum_{n=0}^{\infty}\left\lfloor \dfrac
{n+2}{2}\right\rfloor x^{n}$.

[\textit{Remark:} The above solution is a neat a-posteriori proof, but it does
not explain how the answer $\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}%
{2}\right\rfloor x^{n}$ could have been found. Here is a quick sketch of this:
The polynomial $1-x-x^{2}+x^{3}$ factors as $1-x-x^{2}+x^{3}=\left(
1+x\right)  \left(  1-x\right)  ^{2}$. Thus, partial fraction decomposition
yields%
\begin{align*}
\dfrac{1}{1-x-x^{2}+x^{3}}  &  =\dfrac{1}{4\left(  1+x\right)  }+\dfrac
{1}{4\left(  1-x\right)  }+\dfrac{1}{2\left(  1-x\right)  ^{2}}\\
&  =\dfrac{1}{4}\sum_{n=0}^{\infty}\left(  -1\right)  ^{n}x^{n}+\dfrac{1}%
{4}\sum_{n=0}^{\infty}x^{n}+\dfrac{1}{2}\sum_{n=0}^{\infty}\left(  n+1\right)
x^{n}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we used the formulas }\dfrac{1}{1+x}=\sum_{n=0}^{\infty}\left(
-1\right)  ^{n}x^{n}\text{,}\\
\dfrac{1}{1-x}=\sum_{n=0}^{\infty}x^{n}\text{ and }\dfrac{1}{\left(
1-x\right)  ^{2}}=\sum_{n=0}^{\infty}\left(  n+1\right)  x^{n}%
\end{array}
\right) \\
&  =\sum_{n=0}^{\infty}\underbrace{\left(  \dfrac{1}{4}\left(  -1\right)
^{n}+\dfrac{1}{4}+\dfrac{1}{2}\left(  n+1\right)  \right)  }%
_{\substack{=\left\lfloor \dfrac{n+2}{2}\right\rfloor \\\text{(this can be
proven by a simple case distinction,}\\\text{depending on }n\text{ being even
or odd)}}}x^{n}\\
&  =\sum_{n=0}^{\infty}\left\lfloor \dfrac{n+2}{2}\right\rfloor x^{n}.
\end{align*}
This is also a valid proof.]
\end{proof}

\begin{thebibliography}{999999999}                                                                                        %


\bibitem[Camero16]{Cameron-AC1}Peter J. Cameron, \textit{St Andrews Notes on
Advanced Combinatorics, Part 1: The Art of Counting}, 28 March 2016.\newline%
\url{https://cameroncounts.files.wordpress.com/2016/04/acnotes1.pdf}\newline
Errata can be found at \url{http://www.cip.ifi.lmu.de/~grinberg/algebra/acnotes1-errata.pdf}

\bibitem[dilemi17]{dilemi17}Dilemian et al, \textit{math.stackexchange post
\#2455428 (\textquotedblleft An identity involving binomial coefficients and
rational functions\textquotedblright)},
\url{https://math.stackexchange.com/q/2455428} .

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

\bibitem[GesReu93]{GesReu93}Ira M. Gessel, Christophe Reutenauer,
\textit{Counting Permutations with Given Cycle Structure and Descent Set},
Journal of Combinatorial Theory, Series A, \textbf{64}, Issue 2, November
1993, pp. 189--215.\newline\url{https://doi.org/10.1016/0097-3165(93)90095-P}

\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[Schmit04]{Schmitt04}William R. Schmitt, \textit{Incidence Hopf
algebras}, Journal of Pure and Applied Algebra \textbf{96} (1994), pp.
299--330, \url{https://doi.org/10.1016/0022-4049(94)90105-8} .
\end{thebibliography}


\end{document}