% Like most advanced LaTeX files, this one begins with a lot of
% boilerplate. You don't need to understand (or even read) most of it.
% All you need to do is fill in your name, UMN ID, email address,
% and the number of the pset. (Search for "METADATA" to find the place
% for this.) Then, you can go straight to the "EXERCISE 1"
% section and start writing your solutions.
% The "VARIOUS USEFUL COMMANDS" section is probably worth taking a
% look at at some point.

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[paper=a4, fontsize=12pt]{scrartcl} % A4 paper and 12pt font size
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages
\usepackage{mathrsfs}    % More math packages
\usepackage{sectsty}  % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all section titles centered, the default font and small caps %remove this to left align section tites
\usepackage{hyperref} % Turns cross-references into hyperlinks,
                      % and defines \url and \href commands.
\usepackage{graphicx} % For embedding graphics files.
\usepackage{framed}   % For the "leftbar" environment used below.
\usepackage{ifthen}   % Used for the \powset command below.
\usepackage{lastpage} % for counting the number of pages
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}     % This is a powerful tool to draw vector
                      % graphics inside LaTeX. In particular, you can
                      % use it to draw graphs.
\usepackage{verbatim} % For the "verbatim" environment, in which
                      % special symbols can be used freely without
                      % confusing the compiler. (And it's typeset in
                      % a constant-width font.)
                      % Useful, e.g., for quoting code (or ASCII art).
\usepackage{ytableau}

%\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{20pt} % Makes indentation for paragraphs longer.
                           % This makes paragraphs stand out more.

%----------------------------------------------------------------------------------------
%	VARIOUS USEFUL COMMANDS
%----------------------------------------------------------------------------------------
% The commands below might be convenient. For example, you probably
% prefer to write $\powset[2]{V}$ for the set of $2$-element subsets
% of $V$, rather than writing $\mathcal{P}_2(V)$.
% Notice that you can easily define your own commands like this.
% Caveat: Some of these commands need to be properly "guarded" when
% they occur in subscripts or superscripts. So you should not write
% $K_\CC$, but rather $K_{\CC}$.
\newcommand{\CC}{\mathbb{C}} % complex numbers
\newcommand{\RR}{\mathbb{R}} % real numbers
\newcommand{\QQ}{\mathbb{Q}} % rational numbers
\newcommand{\NN}{\mathbb{N}} % nonnegative integers
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}} % integers modulo k
                                            % (syntax: "\Z{k}")
\newcommand{\ZZ}{\mathbb{Z}} % integers
\newcommand{\id}{\operatorname{id}} % identity map
\newcommand{\lcm}{\operatorname{lcm}}
% Lowest common multiple. For historical reasons, LaTeX has a \gcd
% command built in, but not an \lcm command. The preceding line
% rectifies that.
\newcommand{\Des}{\operatorname{Des}} % descent set of a permutation
\newcommand{\des}{\operatorname{des}} % descent number of a permutation
\newcommand{\OLN}{\operatorname{OLN}} % one-line notation of a permutation
\newcommand{\cyc}{\operatorname{cyc}} % notation for cyclic permutations
\newcommand{\rev}{\operatorname{rev}} % reversal of a walk
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ compiles to {...} (set-brackets).
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ compiles to |...| (absolute value, or size of a set).
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ compiles to (...) (parentheses, or tuple-brackets).
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ compiles to [...] (Iverson bracket, aka truth value).
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
% $\floor{...}$ compiles to |_..._| (floor function).
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ compiles to V(...) (vertex set of a graph/digraph).
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ compiles to E(...) (edge set of a graph).
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ compiles to A(...) (arc set of a digraph).
\newcommand{\lf}[2]{#1^{\underline{#2}}}
% $\lf{...1}{...2}$ compiles to $...1^{\underline{...2}}$.
% This is a notation for the falling factorial.
\newcommand{\euleri}[2]{\genfrac{\langle}{\rangle}{0pt}{0}{#1}{#2}}
% $\euleri{...1}{...2} compiles to the angular-brackets notation
% for the Eulerian number of $n$ and $k$.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications. For example, try this out:
% $ \underbrack{(a+b)^2}{= a^2 + 2ab + b^2 \\ \text{(by the binomial formula)}} $
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\newcommand{\nnn}{\nonumber\\} % Don't number this line in an "align" environment, and move on to the next line.
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}} % Quotient of division with remainder.

%----------------------------------------------------------------------------------------
%	MAKING SUMMATION SIGNS ALWAYS PUT THEIR BOUNDS ABOVE AND BELOW
%	THE SIGN
%----------------------------------------------------------------------------------------
% The following are hacks to ensure that sums (such as
% $\sum_{k=1}^n k$) always put their bounds (i.e., the $k=1$ and the
% $n$) underneath and above the sign, as opposed to on its right.
% Same for products (\prod), set unions (\bigcup) and set
% intersections (\bigcap). Remove the 8 lines below if you do not want
% this behavior.
\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}

%----------------------------------------------------------------------------------------
%	ENVIRONMENTS
%----------------------------------------------------------------------------------------
% The incantations below define how theorem environments
% (\begin{theorem} ... \end{theorem}) and their likes will look like.
\newtheoremstyle{plainsl}% <name>
  {8pt plus 2pt minus 4pt}% <Space above>
  {8pt plus 2pt minus 4pt}% <Space below>
  {\slshape}% <Body font>
  {0pt}% <Indent amount>
  {\bfseries}% <Theorem head font>
  {.}% <Punctuation after theorem head>
  {5pt plus 1pt minus 1pt}% <Space after theorem headi>
  {}% <Theorem head spec (can be left empty, meaning `normal')>

% Environments which make the text inside them slanted:
\theoremstyle{plainsl}
  \newtheorem{theorem}{Theorem}[section]
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{conjecture}[theorem]{Conjecture}
% Environments that don't:
\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}}

%----------------------------------------------------------------------------------------
%	METADATA
%----------------------------------------------------------------------------------------
\newcommand{\myname}{Darij Grinberg} % ENTER YOUR NAME HERE
\newcommand{\myid}{00000000} % ENTER YOUR UMN ID HERE
\newcommand{\mymail}{dgrinber@umn.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{2} % ENTER THE NUMBER OF THIS PSET HERE

%----------------------------------------------------------------------------------------
%	HEADER AND FOOTER
%----------------------------------------------------------------------------------------
\ihead{Solutions to midterm \#\psetnumber} % Page header left
\ohead{page \thepage\ of \pageref{LastPage}} % Page header right
\ifoot{\myname, \myid} % left footer
\ofoot{\mymail} % right footer

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------
\title{	
\normalfont \normalsize 
\textsc{University of Minnesota, School of Mathematics} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Math 5705: Enumerative Combinatorics, \\
Fall 2018:
Midterm \psetnumber\\% The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{\myname}

\begin{document}

\maketitle % Print the title

\begin{center} % Delete this if you want to save space!
{\large due date: \textbf{Wednesday, 14 November 2018} at the beginning of class, \\
or before that by email or canvas.

Please solve \textbf{at most 4 of the 6 exercises}!

Beware: \textbf{Collaboration is not allowed} on midterms!}
\end{center}

%----------------------------------------------------------------------------------------
%	NOTATIONS
%----------------------------------------------------------------------------------------
\horrule{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 $\ive{n}$ for the set $\set{1, 2, \ldots, n}$
(when $n \in \ZZ$).

\item If $n \in \NN$, then $S_n$ denotes the set of all permutations
of $\ive{n}$.

\item If $n \in \NN$ and $\sigma \in S_n$, then:

\begin{itemize}
\item a \textit{descent} of the permutation $\sigma$
denotes an element $k \in \ive{n-1}$ satisfying
$\sigma \tup{k} > \sigma \tup{k+1}$.

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

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

\item the \textit{one-line notation} $\OLN \sigma$
of $\sigma$ is defined as the $n$-tuple
$\tup{ \sigma\tup{1}, \sigma\tup{2}, \ldots, \sigma\tup{n} }$.
Often, this $n$-tuple is written with square brackets,
i.e., as
$\ive{ \sigma\tup{1}, \sigma\tup{2}, \ldots, \sigma\tup{n} }$.

\item for each $i \in \ive{n}$, we define
$\ell_i\tup{\sigma}$ to be the number of all
$j \in \set{i+1, i+2, \ldots, n}$ satisfying
$\sigma\tup{i} > \sigma\tup{j}$.

\item we say that $\sigma$ is \textit{312-avoiding}
if there exist no three elements $i, j, k \in \ive{n}$
satisfying $i < j < k$ and
$\sigma\tup{j} < \sigma\tup{k} < \sigma\tup{i}$.

\item we say that $\sigma$ is \textit{321-avoiding}
if there exist no three elements $i, j, k \in \ive{n}$
satisfying $i < j < k$ and
$\sigma\tup{k} < \sigma\tup{j} < \sigma\tup{i}$.

\end{itemize}

\item For any $n \in \NN$ and any $i \in \ive{n-1}$, we
let $s_i$ denote the permutation in $S_n$ that swaps $i$
with $i+1$ while leaving all other elements of $\ive{n}$
unchanged.
(This assumes that $n$ is determined by the context.)

\item For any $n \in \NN$ and any $k$ distinct elements
$i_1, i_2, \ldots, i_k$ of $\ive{n}$, we let
$\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 $\ive{n}$
unchanged.
(Again, this relies on $n$ being clear from the context.)

\item For any $n \in \NN$ and $k \in \NN$, the notation
$\euleri{n}{k}$ 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 \NN$,
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} = \tup{f^a}^b$
for any $a, b \in \NN$); but be careful with several maps
(e.g., two maps $f : X \to X$ and $g : X \to X$ don't
always satisfy $\tup{fg}^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 = \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\tup{x} \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
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 1}

\subsection{Problem}

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

For each $i \in \set{0, 1, \ldots, n-1}$ 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).
\[
\OLN \tup{ \tau^{i\_} }
=
\tup{ \tau\tup{1}, \tau\tup{2}, \ldots, \tau\tup{i},
      n,
      \tau\tup{i+1}, \tau\tup{i+2}, \ldots, \tau\tup{n-1} }
\]
(that is, $\OLN \tup{ \tau^{i\_} }$ is obtained from
$\OLN \tau$ by inserting an $n$ right after the $i$-th entry).

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

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

\item[\textbf{(c)}]
Prove that
\[
\euleri{n}{k} = \tup{k+1} \euleri{n-1}{k} + \tup{n-k} \euleri{n-1}{k-1} .
\]

\end{enumerate}

[\textbf{Hint:} You don't need to write more than a few sentences for parts
\textbf{(a)} and \textbf{(b)}.]

\subsection{Solution}

[...]

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

\section{Exercise 2}

\subsection{Problem}

Let $n \in \NN$ and $\sigma \in S_n$.
For each $i \in \ive{n}$, let
\[
a_i = \cyc_{i', i'-1, \ldots, i} = s_{i'-1} s_{i'-2} \cdots s_i \in S_n ,
\qquad \text{where } i' = i + \ell_i \tup{\sigma} .
\]

Prove that $\sigma = a_1 a_2 \cdots a_n$.

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

\subsection{Solution}

[...]

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

\section{Exercise 3}

\subsection{Problem}

Let $n \in \NN$.

\begin{enumerate}
\item[\textbf{(a)}]
Prove that any $\sigma \in S_n$ and any $i \in \ive{n}$
satisfy $\sigma\tup{i} \leq i + \ell_i \tup{\sigma}$.

\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 \tup{i} \leq i+1$ for all $i \in \ive{n-1}$.

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

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

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

\end{enumerate}

\subsection{Solution}

[...]

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

\section{Exercise 4}

\subsection{Problem}

Let $n \geq 2$, and set $S = \ive{n}$.
Let $i \in \ive{n-1}$. Prove that:

\begin{enumerate}

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

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

\end{enumerate}

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

\subsection{Solution}

[...]

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

\section{Exercise 5}

\subsection{Problem}

\begin{enumerate}

\item[\textbf{(a)}]
For each $n \in \NN$,
prove that the number of fixed-point-free involutions
$\ive{n} \to \ive{n}$ is
\[
\begin{cases}
1 \cdot 3 \cdot 5 \cdot \cdots \cdot \tup{n-1}, & \text{ if $n$ is even}; \\
                                             0, & \text{ if $n$ is odd} .
\end{cases}
\]

\item[\textbf{(b)}]
For each $n \in \NN$, we let $t_n$ be the number of all
involutions in $S_n$.
Prove that
\[
t_n
=
\sum_{k=0}^n \dbinom{n}{2k}
\tup{1 \cdot 3 \cdot 5 \cdot \cdots \cdot \tup{2k-1} }
\qquad \text{for each $n \in \NN$}.
\]

\item[\textbf{(c)}]
For each $n \in \NN$, prove that the number of maps
$f : \ive{n} \to \ive{n}$ 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}

[...]

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

\section{Exercise 6}

\subsection{Problem}

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

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

A permutation $\sigma \in S_n$ shall be called a
\textit{$p$-desarrangement} if it satisfies
\[
\text{ \textbf{either} } \tup{ \sigma = \id \text{ and } 2 \mid n }
\text{ \textbf{or} }     \sigma\tup{1} \leq p
\text{ \textbf{or} }     \tup{ \sigma \neq \id \text{ and } 2 \mid \min \tup{\Des \sigma} } .
\]
(The condition $2 \mid \min \tup{\Des \sigma}$ means
that the smallest descent of $\sigma$ is
even.\footnote{Here
are all permutations $\sigma \neq \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*}
\ive{1, 2, 3, \underline{5}, 4}, \qquad
\ive{1, 2, 4, \underline{5}, 3}, \qquad
\ive{1, \underline{3}, 2, 4, 5}, \qquad
\ive{1, \underline{3}, 2, 5, 4}, \qquad
\ive{1, 3, 4, \underline{5}, 2}, \\
\ive{1, \underline{4}, 2, 3, 5}, \qquad
\ive{1, \underline{4}, 2, 5, 3}, \qquad
\ive{1, \underline{4}, 3, 2, 5}, \qquad
\ive{1, \underline{4}, 3, 5, 2}, \qquad
\ive{1, \underline{5}, 2, 3, 4}, \\
\ive{1, \underline{5}, 2, 4, 3}, \qquad
\ive{1, \underline{5}, 3, 2, 4}, \qquad
\ive{1, \underline{5}, 3, 4, 2}, \qquad
\ive{1, \underline{5}, 4, 2, 3}, \qquad
\ive{1, \underline{5}, 4, 3, 2}, \\
\ive{2, \underline{3}, 1, 4, 5}, \qquad
\ive{2, \underline{3}, 1, 5, 4}, \qquad
\ive{2, 3, 4, \underline{5}, 1}, \qquad
\ive{2, \underline{4}, 1, 3, 5}, \qquad
\ive{2, \underline{4}, 1, 5, 3}, \\
\ive{2, \underline{4}, 3, 1, 5}, \qquad
\ive{2, \underline{4}, 3, 5, 1}, \qquad
\ive{2, \underline{5}, 1, 3, 4}, \qquad
\ive{2, \underline{5}, 1, 4, 3}, \qquad
\ive{2, \underline{5}, 3, 1, 4}, \\
\ive{2, \underline{5}, 3, 4, 1}, \qquad
\ive{2, \underline{5}, 4, 1, 3}, \qquad
\ive{2, \underline{5}, 4, 3, 1}, \qquad
\ive{3, \underline{4}, 1, 2, 5}, \qquad
\ive{3, \underline{4}, 1, 5, 2}, \\
\ive{3, \underline{4}, 2, 1, 5}, \qquad
\ive{3, \underline{4}, 2, 5, 1}, \qquad
\ive{3, \underline{5}, 1, 2, 4}, \qquad
\ive{3, \underline{5}, 1, 4, 2}, \qquad
\ive{3, \underline{5}, 2, 1, 4}, \\
\ive{3, \underline{5}, 2, 4, 1}, \qquad
\ive{3, \underline{5}, 4, 1, 2}, \qquad
\ive{3, \underline{5}, 4, 2, 1}, \qquad
\ive{4, \underline{5}, 1, 2, 3}, \qquad
\ive{4, \underline{5}, 1, 3, 2}, \\
\ive{4, \underline{5}, 2, 1, 3}, \qquad
\ive{4, \underline{5}, 2, 3, 1}, \qquad
\ive{4, \underline{5}, 3, 1, 2}, \qquad
\ive{4, \underline{5}, 3, 2, 1}.
\end{align*}
}
This is well-defined, since $\sigma \neq \id$ shows that
$\sigma$ has at least one descent.
Further $p$-desarrangements are $\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 \tup{-1}^k \tup{n-k}! .
\]

\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 = \id$ or
$\tup{\sigma \neq \id \text{ and } 2 \mid \min \tup{\Des \sigma}}$.
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\tup{\sigma}$.

\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 = \cyc_{a_{1, 1}, a_{1, 2}, \ldots, a_{1, n_1}}
         \cyc_{a_{2, 1}, a_{2, 2}, \ldots, a_{2, n_2}}
         \cdots
         \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\tup{\sigma}$ be the permutation whose one-line
notation is
\[
\tup{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}} .
\]

\end{itemize}

For example, if $n = 7$ and
$\sigma = \ive{5, 3, 7, 6, 1, 4, 2}$ in one-line notation,
then the appropriate representation of $\sigma$ is
$\sigma = \cyc_{1, 5} \cyc_{4, 6} \cyc_{3, 7, 2}$ and thus
$F\tup{\sigma} = \ive{1, 5, 4, 6, 3, 7, 2}$ 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 \neq 0$.
Feel free to explore.
(But the simplest way to solve the exercise is not by
bijection.)

\subsection{Solution}

[...]

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

\end{thebibliography}

\end{document}

