\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage{cancel}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, April 09, 2026 14:38:52}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{shapes.geometric, arrows.meta, fit, positioning}
\tikzset{|/.tip={Bar[width=1ex,round]}}
\newcounter{exer}
\newcounter{rmk}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}
\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}[rmk]{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*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand{\iverson}[1]{\left[#1\right]}
\newcommand{\sur}{\operatorname{sur}}
\ihead{Math 4990 Fall 2017 (Darij Grinberg): handwritten notes 2017-10-24}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4990 Fall 2017 (Darij Grinberg):}

\textbf{handwritten notes from the lecture of 24 October 2017}

(digitized using Claude in 2026)

\textbf{Note:} This is \textbf{not} a polished text!
\end{center}

\subsection*{3.8. More about Derangements (continued)}

Recall that $D_{n}$ denotes the \# of all derangements (= permutations with no
fixed points) of $\left[  n\right]  $.

\setcounter{theo}{40}

\begin{proposition}
\label{prop.Dn.recursion}We have $D_{n}=(n-1)(D_{n-1}+D_{n-2})$ for all
$n\geq2$.
\end{proposition}

\medskip\noindent\textbf{1st proof.} Just compute the $D_{i}$ using
Corollary~36:
\[
\text{LHS}=D_{n}=n!\sum_{k=0}^{n}\dfrac{(-1)^{k}}{k!}=n!\left(  \sum
_{k=0}^{n-1}\dfrac{(-1)^{k}}{k!}+\dfrac{(-1)^{n}}{n!}\right)
\]
and%
\begin{align*}
\text{RHS}  &  =(n-1)\left(  D_{n-1}+D_{n-2}\right) \\
&  =(n-1)\left(  (n-1)!\sum_{k=0}^{n-1}\dfrac{(-1)^{k}}{k!}+(n-2)!\sum
_{k=0}^{n-2}\dfrac{(-1)^{k}}{k!}\right) \\
&  =(n-1)(n-1)!\sum_{k=0}^{n-1}\dfrac{(-1)^{k}}{k!}+\underbrace{(n-1)(n-2)!}%
_{=\left(  n-1\right)  !}\underbrace{\sum_{k=0}^{n-2}\dfrac{(-1)^{k}}{k!}%
}_{\substack{=\sum_{k=0}^{n-1}\dfrac{(-1)^{k}}{k!}-\dfrac{(-1)^{n-1}}{(n-1)!}%
}}\\
&  =(n-1)(n-1)!\sum_{k=0}^{n-1}\dfrac{(-1)^{k}}{k!}+\left(  n-1\right)
!\left(  \sum_{k=0}^{n-1}\dfrac{(-1)^{k}}{k!}-\dfrac{(-1)^{n-1}}%
{(n-1)!}\right) \\
&  =(n-1)(n-1)!\sum_{k=0}^{n-1}\dfrac{(-1)^{k}}{k!}+(n-1)!\sum_{k=0}%
^{n-1}\dfrac{(-1)^{k}}{k!}-\underbrace{(n-1)!\cdot\dfrac{(-1)^{n-1}}{(n-1)!}%
}_{=\left(  -1\right)  ^{n-1}}\\
&  =\underbrace{\left(  (n-1)(n-1)!+(n-1)!\right)  }_{=n(n-1)!=n!}\sum
_{k=0}^{n-1}\dfrac{(-1)^{k}}{k!}-\underbrace{\left(  -1\right)  ^{n-1}%
}_{=-\left(  -1\right)  ^{n}}\\
&  =n!\sum_{k=0}^{n-1}\dfrac{(-1)^{k}}{k!}+(-1)^{n}=n!\left(  \sum_{k=0}%
^{n-1}\dfrac{(-1)^{k}}{k!}+\dfrac{(-1)^{n}}{n!}\right)  ,
\end{align*}
which is the same. \qed


\medskip\noindent\textbf{2nd proof.} Classify the $D_{n}$ derangements of
$[n]$ into $n-1$ \textquotedblleft kingdoms\textquotedblright, each of which
will contain 2 \textquotedblleft genera\textquotedblright\ (see the picture
below for an illustration, which has $n-1=6$).

\begin{center}
\begin{tikzpicture}[scale=1.3]
% Draw the circle (the "pie")
\draw[thick] (0,0) circle (2.5cm);
% Draw the bold radial lines for the 6 kingdoms
\foreach \angle/\lab in {0/K_1, 60/K_2, 120/K_3, 180/K_4, 240/K_5, 300/K_6}
{
\draw[very thick] (0,0) -- (\angle:2.5);
}
% Draw the lighter concentric separating circle for the two genera
\draw[thick, densely dashed] (0,0) circle (1.5cm);
% Shade the inner genera (genus 1) lightly
\foreach \i in {0,1,...,5}
{
\fill[blue!8] (0,0) -- ({60*\i}:1.5) arc ({60*\i}:{60*\i+60}:1.5) -- cycle;
}
% Shade the outer genera (genus 2) slightly differently
\foreach \i in {0,1,...,5}
{
\fill[red!8] ({60*\i}:1.5) arc ({60*\i}:{60*\i+60}:1.5) --
({60*\i+60}:2.5) arc ({60*\i+60}:{60*\i}:2.5) -- cycle;
}
% Redraw lines on top
\draw[thick] (0,0) circle (2.5cm);
\draw[thick, densely dashed] (0,0) circle (1.5cm);
\foreach \angle in {0, 60, 120, 180, 240, 300}
{
\draw[very thick] (0,0) -- (\angle:2.5);
}
% Labels for kingdoms
\foreach \angle/\lab in {30/$K_1$, 90/$K_2$, 150/$K_3$, 210/$K_4$, 270/$K_5$, 330/$K_6$}
{
\node[fill=white] at (\angle:1.5) {\lab};
}
% Labels for genera
\node at (30:0.9) {\small$G_{1,1}$};
\node at (30:2.15) {\small$G_{1,2}$};
\end{tikzpicture}



\end{center}

For each $i\in\lbrack n-1]$, the $i$-th kingdom $K_{i}$ consists of the
derangements $\pi$ of $[n]$ with $\pi(n)=i$. Then each derangement lies in
exactly $1$ kingdom (since $\pi(n)\neq n$).

The $1$st genus $G_{i,1}$ of the $i$-th kingdom consists of those $\pi\in
K_{i}$ with $\pi(i)=n$.

The $2$nd genus $G_{i,2}$ of the $i$-th kingdom consists of those $\pi\in
K_{i}$ with $\pi(i)\neq n$.

\medskip\noindent\textbf{Claim 1:} Each $1$st genus $G_{i,1}$ contains
$D_{n-2}$ derangements.

\medskip\noindent\textbf{Claim 2:} Each $2$nd genus $G_{i,2}$ contains
$D_{n-1}$ derangements.

\medskip\noindent\textit{Proof of Claim 1:} How can we construct a derangement
in $G_{i,1}$? We take a derangement of the $(n-2)$-element set $[n]\setminus
\{n,i\}$, then extend it to the set $[n]$ by sending $n\mapsto i$ and
$i\mapsto n$. For this, we have $D_{n-2}$ options (since an $(n-2)$-element
set has $D_{n-2}$ derangements). \qed


\medskip\noindent\textit{Proof of Claim 2:} How can we construct a derangement
in $G_{i,2}$? We choose a derangement $\delta$ of $[n-1]$, and then we
\textquotedblleft stick in\textquotedblright\ $n$ \textquotedblleft
between\textquotedblright\ $\delta^{-1}(i)$ and $i$.

Formally: We start with a derangement $\delta$ of $[n-1]$, and then define
$\pi\colon\lbrack n]\rightarrow\lbrack n]$ by%
\[
\pi(k)=%
\begin{cases}
\delta(k), & \text{if }k\neq n\text{ and }k\neq\delta^{-1}(i);\\
n, & \text{if }k=\delta^{-1}(i);\\
i, & \text{if }k=n.
\end{cases}
\]
It is easy to check that $\pi$ is a derangement in $G_{i,2}$ (since
$\delta^{-1}(i)\neq i$).

Conversely, if $\pi$ is a derangement in $G_{i,2}$, then the map $\delta
\colon\lbrack n-1]\rightarrow\lbrack n-1]$ defined by%
\[
\delta(k)=%
\begin{cases}
\pi(k), & \text{if }k\neq\pi^{-1}(n);\\
i, & \text{if }k=\pi^{-1}(n)
\end{cases}
\]
is a derangement of $[n-1]$.

The maps $\pi\mapsto\delta$ and $\delta\mapsto\pi$ are mutually inverse, thus
are bijections. So the \# of derangements in $G_{i,2}$ equals the \# of
derangements of $\left[  n-1\right]  $, that is, $D_{n-1}$. \qed


Now,
\begin{align*}
D_{n}  &  =\sum_{i=1}^{n-1}\underbrace{|K_{i}|}_{=|G_{i,1}|+|G_{i,2}|}%
=\sum_{i=1}^{n-1}(|G_{i,1}|+|G_{i,2}|)\\
&  =\sum_{i=1}^{n-1}(D_{n-2}+D_{n-1})\ \ \ \ \ \ \ \ \ \ \left(  \text{by
Claim 1 and Claim 2}\right) \\
&  =(n-1)(D_{n-2}+D_{n-1}).
\end{align*}
This proves Proposition \ref{prop.Dn.recursion} again. \qed


\medskip Our above proof of Claim 2 was secretly inspired by the \emph{cycle
decomposition} of a permutation. Here is a short introduction to it:

Given a permutation $\zeta$ of a set $X$, we represent it by a
\textquotedblleft picture\textquotedblright: Draw a point (\textquotedblleft
node\textquotedblright) for each $x\in X$, and draw an arrow
(\textquotedblleft arc\textquotedblright) from each node $x$ to the node
$\zeta(x)$.

\begin{statement}
\textbf{Examples:}

\begin{enumerate}
\item[\textbf{(a)}] If $\zeta$ is the permutation of $[5]$ sending $1,2,3,4,5$
to $3,5,4,1,2$, then the picture is%
\[
\begin{tikzpicture}[>=Stealth, thick, every node/.style={circle, draw,
inner sep=2pt, minimum size=6mm}]
% Nodes in a row, roughly as in the handwritten notes
\node (1) at (0,0) {$1$};
\node (2) at (1.5,0) {$2$};
\node (3) at (3,0) {$3$};
\node (4) at (4.5,0) {$4$};
\node (5) at (6,0) {$5$};
% 1->3: arc curving upward over 2
\draw[->] (1) to[bend left=40] (3);
% 3->4: short arc curving slightly above
\draw[->] (3) to[bend left=30] (4);
% 4->1: long arc curving below
\draw[->] (4) to[bend left=40] (1);
% 2->5: long arc curving high above 3,4
\draw[->] (2) to[bend left=50] (5);
% 5->2: arc curving below
\draw[->] (5) to[bend left=50] (2);
\end{tikzpicture}
\]
or, equivalently,%
\[
\begin{tikzpicture}[>=Stealth, thick, every node/.style={circle, draw,
inner sep=2pt, minimum size=6mm}]
% Cycle 1: 1->3->4->1
\node (1) at (210:1.5) {$1$};
\node (3) at (90:1.5) {$3$};
\node (4) at (330:1.5) {$4$};
\draw[->] (1) to[bend left=20] (3);
\draw[->] (3) to[bend left=20] (4);
\draw[->] (4) to[bend left=20] (1);
% Cycle 2: 2->5->2
\node (2) at (4,0.5) {$2$};
\node (5) at (6,0.5) {$5$};
\draw[->] (2) to[bend left=30] (5);
\draw[->] (5) to[bend left=30] (2);
\end{tikzpicture}
\]
(the positions of nodes don't matter).

\item[\textbf{(b)}] If $\zeta$ is the permutation of $[5]$ sending $1,2,3,4,5$
to $4,3,2,1,5$, then the picture is%
\[
\begin{tikzpicture}[>=Stealth, thick, every node/.style={circle, draw,
inner sep=2pt, minimum size=6mm}, scale=1.2]
% Cycle 1: 1->4->1
\node (1) at (0,0) {$1$};
\node (4) at (1.5,0) {$4$};
\draw[->] (1) to[bend left=30] (4);
\draw[->] (4) to[bend left=30] (1);
% Cycle 2: 2->3->2
\node (2) at (3.5,0) {$2$};
\node (3) at (5,0) {$3$};
\draw[->] (2) to[bend left=30] (3);
\draw[->] (3) to[bend left=30] (2);
% Cycle 3: 5->5
\node (5) at (7,0) {$5$};
\draw[->] (5) to[loop right, looseness=30] (5);
\end{tikzpicture}
\]

\end{enumerate}
\end{statement}

This picture is called the \emph{cycle digraph} of $\zeta$. It is/represents a
digraph ($=$~directed graph), which we'll study later. The permutation $\zeta$
can be uniquely reconstructed from this picture. Each node has exactly $1$
outgoing arc and exactly $1$ incoming arc. If $X$ is finite, then the picture
consists of a bunch of disjoint cycles (\textquotedblleft
disjoint\textquotedblright\ $=$ having no nodes in common).

A permutation $\zeta$ is a derangement iff it has no $1$-node cycles.

In terms of cycle digraphs, the bijection $\delta\mapsto\pi$ in the proof of
Claim 2 inserts $n$ into a cycle just before $i$:%
\[
\begin{tikzpicture}[>=Stealth, thick]
% === Left cycle (without n) ===
\node[circle, draw, inner sep=2pt, minimum size=7mm] (di) at (360/5:2) {$\delta^{-1}(i)$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (i1) at (0:2) {$i$};
% Arc from delta^{-1}(i) down to i (the direct arc)
\draw[->] (di) to[bend left=30] (i1);
\coordinate (i2) at (-360/5:2);
\coordinate (i4) at (2*360/5:2);
\coordinate (i2p) at (-360/5-5:2);
\coordinate (i3) at (-2*360/5:2);
\coordinate (i4p) at (2*360/5+5:2);
\draw[->] (i1) to[bend left=30] (i2);
\draw[->] (i4) to[bend left=30] (di);
\draw[densely dotted] (i2p) to[bend left=32] (i3);
\draw[densely dotted] (i3) to[bend left=32] (i4p);
 
% === Mapping arrow ===
\draw[|->, very thick] (3.2,0) -- node[above, draw=none, inner sep=0pt, font=\footnotesize] {} (4.3,0);
 
% === Right cycle (with n inserted) ===
\begin{scope}[xshift=7cm]
\node[circle, draw, inner sep=2pt, minimum size=7mm] (di) at (360/5:2) {$\delta^{-1}(i)$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (i1) at (0:2) {$i$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (n2) at (360/10:3) {$n$};
% Arc from delta^{-1}(i) down to i (the direct arc)
\draw[->] (di) to[bend left=30] (n2);
\draw[->] (n2) to[bend left=30] (i1);
\coordinate (i2) at (-360/5:2);
\coordinate (i4) at (2*360/5:2);
\coordinate (i2p) at (-360/5-5:2);
\coordinate (i3) at (-2*360/5:2);
\coordinate (i4p) at (2*360/5+5:2);
\draw[->] (i1) to[bend left=30] (i2);
\draw[->] (i4) to[bend left=30] (di);
\draw[densely dotted] (i2p) to[bend left=32] (i3);
\draw[densely dotted] (i3) to[bend left=32] (i4p);
\end{scope}
\end{tikzpicture}
\]


The inverse bijection removes $n$ from its cycle:%
\[
\begin{tikzpicture}[>=Stealth, thick]
% === Left cycle (without n) ===
\node[circle, draw, inner sep=2pt, minimum size=7mm] (di) at (360/3:2) {$\pi^{-1}(n)$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (i0) at (360/6:2) {$n$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (i1) at (0:2) {$i$};
\draw[->] (di) to[bend left=30] (i0);
\draw[->] (i0) to[bend left=30] (i1);
\coordinate (i2) at (-360/6:2);
\coordinate (i3) at (-360/3:2);
\coordinate (i4) at (180:2);
\coordinate (i2p) at (-360/6-5:2);
\coordinate (i4p) at (180+5:2);
\draw[->] (i1) to[bend left=30] (i2);
\draw[->] (i4) to[bend left=30] (di);
\draw[densely dotted] (i2p) to[bend left=26] (i3);
\draw[densely dotted] (i3) to[bend left=26] (i4p);
 
% === Mapping arrow ===
\draw[|->, very thick] (3.2,0) -- node[above, draw=none, inner sep=0pt, font=\footnotesize] {} (4.3,0);
 
% === Right cycle (with n inserted) ===
\begin{scope}[xshift=7cm]
\node[circle, draw, inner sep=2pt, minimum size=7mm] (di) at (360/3:2) {$\pi^{-1}(n)$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (i1) at (0:2) {$i$};
\draw[->] (di) to[bend left=30] (i1);
\coordinate (i2) at (-360/6:2);
\coordinate (i3) at (-360/3:2);
\coordinate (i4) at (180:2);
\coordinate (i2p) at (-360/6-5:2);
\coordinate (i4p) at (180+5:2);
\draw[->] (i1) to[bend left=30] (i2);
\draw[->] (i4) to[bend left=30] (di);
\draw[densely dotted] (i2p) to[bend left=26] (i3);
\draw[densely dotted] (i3) to[bend left=26] (i4p);
\end{scope}
\end{tikzpicture}
\]
 


\bigskip

\setcounter{theo}{39}

\begin{proposition}
\label{prop.40}We have $\displaystyle n!=\sum_{k=0}^{n}\dbinom{n}{k}D_{k}$ for
all $n\in\mathbb{N}$.
\end{proposition}

\begin{proof}
We can construct any permutation $\pi$ of $[n]$ in the following way:

\begin{itemize}
\item Choose the \# of non-fixed points of $\pi$. Call it $k$.

\item Choose the $k$ non-fixed points of $\pi$; there are $\dbinom{n}{k}$ ways
to do this.

\item Choose what $\pi$ does to these $k$ points. There are $D_{k}$ ways to do
this (since we are choosing a derangement of a $k$-element set).
\end{itemize}

Thus, $n!=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}D_{k}$.
\end{proof}

\medskip\noindent\textbf{Remark.}\quad Corollary~36 is equivalent to
Proposition~\ref{prop.40}.

Indeed,
\begin{align*}
\text{Corollary~36}\quad &  \Longleftrightarrow\quad D_{n}=\sum_{k=0}^{n}%
(-1)^{k}\dbinom{n}{k}(n-k)!\\
&  \overset{\text{substitute\ $i$ for $n-k$}}{\Longleftrightarrow}\quad
D_{n}=\sum_{i=0}^{n}(-1)^{n-i}\dbinom{n}{i}\,i!\\
&  \Longleftrightarrow\quad(-1)^{n}D_{n}=\sum_{i=0}^{n}(-1)^{i}\dbinom{n}%
{i}\,i!\\
&  \overset{\text{HW4 exercise~\#5}}{\Longleftrightarrow}\quad n!=\sum
_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\left(  -1\right)  ^{i}D_{i}\\
&  \Longleftrightarrow\quad n!=\sum_{i=0}^{n}\dbinom{n}{i}D_{i}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since the two }\left(  -1\right)  ^{i}\text{
factors cancel}\right) \\
&  \Longleftrightarrow\quad\text{Prop.~\ref{prop.40}}.
\end{align*}


Here is another recursion for the $D_{n}$:

\setcounter{theo}{41}

\begin{proposition}
\label{prop.42}We have $D_{n}=nD_{n-1}+(-1)^{n}$ for all $n\geq1$.
\end{proposition}

\begin{proof}
Easy using Corollary~36 (exercise).

A bijective proof is much trickier (see \cite{BenOrn} or \cite{Elizal20}).
\end{proof}

\subsection*{3.9. PS on Inclusion \& Exclusion}

Here is another application of the Principle of Inclusion/Exclusion:

\begin{proposition}
\label{prop.43}For any $n\in\mathbb{N}$ and $m\in\mathbb{N}$ and
$x\in\mathbb{Q}$, set
\[
z_{m,n}(x)=\sum_{k=0}^{n}(-1)^{k}\dbinom{n}{k}(x^{n-k}-1)^{m}.
\]
Then, $z_{m,n}(x)=z_{n,m}(x)$.
\end{proposition}

This is \cite[Exercise 3.21]{detnotes}. But it has a combinatorial proof for
$x\in\mathbb{N}$:

Namely, $z_{m,n}(x)=\#$ of all $m\times n$-matrices with entries from
$\{0,1,\ldots,x-1\}$ with no zero rows and no zero columns.

(This is because we can set $U=\{m\times n\text{-matrices with entries from
}\{0,1,\ldots,x-1\}\text{ with no zero rows}\}$ and $A_{i}=\{\text{matrices in
}U\text{ whose }i\text{-th column is }0\}$.

Then,%
\begin{align*}
&  \left(  \#\text{ of }m\times n\text{-matrices with no zero columns and no
zero rows}\right) \\
&  =\left\vert U\setminus(A_{1}\cup A_{2}\cup\cdots\cup A_{n})\right\vert
=\left\vert U\setminus\bigcup_{i=1}^{n}A_{i}\right\vert \\
&  =\sum_{I\subseteq\lbrack n]}(-1)^{|I|}\underbrace{\left(  \#\text{ of
matrices in }U\text{ having }i\text{-th column }=0\;\forall\,i\in I\right)
}_{\substack{=(x^{n-|I|}-1)^{m}\\\text{(choose each row separately)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{by the Principle of
Inclusion/Exclusion}\right) \\
&  =\sum_{I\subseteq\lbrack n]}(-1)^{|I|}(x^{n-|I|}-1)^{m}=\sum_{k=0}%
^{n}(-1)^{k}\dbinom{n}{k}(x^{n-k}-1)^{m}\\
&  =z_{m,n}(x),
\end{align*}
just as we claimed.) Thus, in order to prove $z_{m,n}(x)=z_{n,m}(x)$, we must
show that the $\#$ of $m\times n$-matrices with no zero columns and no zero
rows equals the $\#$ of $n\times m$-matrices with the same property. But this
is clear, as you can get a bijection by transposing the matrices. \qed


\section*{4. Generating Functions}

\subsection*{4.1. Examples}

Let me show what generating functions (\textquotedblleft
gf's\textquotedblright) are good for. Then, in \S 4.2, I'll explain what they
are. Suspend your disbelief for \S 4.1, please.

\medskip\noindent\textbf{The basic idea of generating functions:} Any sequence
$(a_{0},a_{1},a_{2},\ldots)$ of numbers gives rise to a \textquotedblleft
power series\textquotedblright\ $a_{0}+a_{1}x+a_{2}x^{2}+\cdots$, called its
\emph{generating function}. What does this mean? See later. (For a systematic
introduction to generating functions, and for much more about them, see
\cite{Loehr-BC}.)

Before we make this rigorous, some examples:

\subsubsection*{Example 1.}

Recall the Fibonacci sequence $(f_{0},f_{1},f_{2},\ldots)$ with $f_{0}=0$ and
$f_{1}=1$ and $f_{n}=f_{n-1}+f_{n-2}$. Consider its gf
\begin{align*}
F(x)  &  =f_{0}+f_{1}x+f_{2}x^{2}+\cdots\\
&  =0+1x+1x^{2}+2x^{3}+3x^{4}+\cdots\,.
\end{align*}
By the recursion $f_{n}=f_{n-1}+f_{n-2}$, this rewrites as%
\begin{align*}
F(x)  &  =0+1x+(f_{0}+f_{1})x^{2}+(f_{1}+f_{2})x^{3}+(f_{2}+f_{3})x^{4}%
+\cdots\\
&  =x+(f_{0}x^{2}+f_{1}x^{3}+f_{2}x^{4}+\cdots)\\
&  \qquad+(f_{1}x^{2}+f_{2}x^{3}+f_{3}x^{4}+\cdots)\\
&  =x+x^{2}(f_{0}+f_{1}x+f_{2}x^{2}+\cdots)\\
&  \qquad+x(f_{0}+f_{1}x+f_{2}x^{2}+\cdots)\qquad\text{(since }f_{0}%
=0\text{)}\\
&  =x+x^{2}F(x)+xF(x).
\end{align*}
Solving this for $F(x)$ yields%
\begin{align}
F(x)  &  =\dfrac{x}{1-x-x^{2}}\nonumber\\
&  =\dfrac{1}{\sqrt{5}}\cdot\dfrac{1}{1-\phi_{1}x}-\dfrac{1}{\sqrt{5}}%
\cdot\dfrac{1}{1-\phi_{2}x} \label{eq.4990-2017oct24.1}%
\end{align}
(by partial fraction decomposition), where $\phi_{1}=(1+\sqrt{5})/2$ and
$\phi_{2}=(1-\sqrt{5})/2$ are the \textquotedblleft golden
ratios\textquotedblright.

To expand this back in powers of $x$, we ask ourselves: What is $\dfrac
{1}{1-\alpha x}$ for a given complex number $\alpha$?

Well: we have%
\[
\dfrac{1}{1-x}=1+x+x^{2}+x^{3}+\cdots
\]
(since $(1-x)(1+x+x^{2}+x^{3}+\cdots)=(1+x+x^{2}+x^{3}+\cdots)-(x+x^{2}%
+x^{3}+x^{4}+\cdots)=1$), so if we substitute $\alpha x$ for $x$ where
$\alpha\in\mathbb{C}$, we get%
\[
\dfrac{1}{1-\alpha x}=1+\alpha x+(\alpha x)^{2}+(\alpha x)^{3}+\cdots=1+\alpha
x+\alpha^{2}x^{2}+\alpha^{3}x^{3}+\cdots\,.
\]
Thus, \eqref{eq.4990-2017oct24.1} becomes%
\begin{align*}
F(x)  &  =\dfrac{1}{\sqrt{5}}(1+\phi_{1}x+\phi_{1}^{2}x^{2}+\cdots)-\dfrac
{1}{\sqrt{5}}(1+\phi_{2}x+\phi_{2}^{2}x^{2}+\cdots)\\
&  =\left(  \dfrac{1}{\sqrt{5}}\cdot1-\dfrac{1}{\sqrt{5}}\cdot1\right)
+\left(  \dfrac{1}{\sqrt{5}}\phi_{1}-\dfrac{1}{\sqrt{5}}\phi_{2}\right)
x+\left(  \dfrac{1}{\sqrt{5}}\phi_{1}^{2}-\dfrac{1}{\sqrt{5}}\phi_{2}%
^{2}\right)  x^{2}+\cdots\,.
\end{align*}
Now, comparing coefficients before $x^{n}$ in this equality, we find%
\[
\boxed{f_{n}=\dfrac{1}{\sqrt{5}}\phi_{1}^{n}-\dfrac{1}{\sqrt{5}}\phi_{2}^{n}}\,.
\]
This is an explicit formula for Fibonacci numbers, known as \emph{Binet's
formula}.

\subsubsection*{Example 2.}

A \emph{Dyck word} of length $2n$ is a $2n$-tuple that contains $n$ many $0$'s
and $n$ many $1$'s and has the property that for each $k$, the \# of $0$'s
among its first $k$ entries is $\leq$ the \# of $1$'s among its first $k$ entries.

\textbf{Examples of Dyck words:} $(1,0,1,0)$,\ $(1,1,0,0)$%
,\ $(1,1,0,1,0,0)$,\ $()$,\ $(1,0)$.

\textbf{Examples of Non-Dyck words:} $(1,0,0,1)$,\ $(0,1)$%
,\ $(1,1,0)$,\ $(1)$.

We often write D for $0$ and U for $1$.

\medskip A \emph{Dyck path} is a path $(0,0)\to(2n,0)$ that moves by
\textquotedblleft NE steps\textquotedblright\ ($=$~steps $(1,1)$) and
\textquotedblleft SE steps\textquotedblright\ ($=$~steps $(1,-1)$) and never
falls below the $x$-axis.

Examples:%
\[
\begin{tikzpicture}[scale=0.5]
% First example: UUDD = (1,1,0,0) for n=2
\foreach \x/\y in {0/0,1/1,2/2,3/1,4/0} {
\node[circle, fill, inner sep=1.5pt] at (\x,\y) {};
}
\draw (0,0) -- (1,1) -- (2,2) -- (3,1) -- (4,0);
\node at (5,1) {or};
% Second example: UDUD = (1,0,1,0) for n=2
\begin{scope}[xshift=7cm]
\foreach \x/\y in {0/0,1/1,2/0,3/1,4/0} {
\node[circle, fill, inner sep=1.5pt] at (\x,\y) {};
}
\draw (0,0) -- (1,1) -- (2,0) -- (3,1) -- (4,0);
\end{scope}
\end{tikzpicture}
\]


The Dyck paths $(0,0)\rightarrow(2n,0)$ can be viewed as \textquotedblleft
mountain ranges\textquotedblright\ made of $n$ many $\diagup$-steps and $n$
many $\diagdown$-steps.

There is a simple bijection between Dyck words of length $2n$ and Dyck paths
$(0,0)\rightarrow(2n,0)$:
\[
\text{send each }%
\begin{cases}
1\text{ in the word} & \text{to a }\diagup\text{-step in the path};\\
0\text{ in the word} & \text{to a }\diagdown\text{-step in the path.}%
\end{cases}
\]


But how many Dyck paths (or words) are there?

\begin{statement}
\textbf{Example:}\quad The Dyck paths $(0,0)\rightarrow(6,0)$ are%
\[
\begin{tikzpicture}[scale=0.4]
% Path 1: UUUDDD
\foreach \x/\y in {0/0,1/1,2/2,3/3,4/2,5/1,6/0} {
\node[circle, draw, fill=black, inner sep=1pt] at (\x,\y) {};
}
\draw (0,0)--(1,1)--(2,2)--(3,3)--(4,2)--(5,1)--(6,0);
\draw (7,-1) -- (7,4);
% Path 2: UUDUDD
\begin{scope}[xshift=8cm]
\foreach \x/\y in {0/0,1/1,2/2,3/1,4/2,5/1,6/0} {
\node[circle, draw, fill=black, inner sep=1pt] at (\x,\y) {};
}
\draw (0,0)--(1,1)--(2,2)--(3,1)--(4,2)--(5,1)--(6,0);
\end{scope}
\draw (15,-1) -- (15,4);
% Path 3: UUDDUD
\begin{scope}[xshift=16cm]
\foreach \x/\y in {0/0,1/1,2/2,3/1,4/0,5/1,6/0} {
\node[circle, draw, fill=black, inner sep=1pt] at (\x,\y) {};
}
\draw (0,0)--(1,1)--(2,2)--(3,1)--(4,0)--(5,1)--(6,0);
\end{scope}
\draw (23,-1) -- (23,4);
% Path 4: UDUDUD
\begin{scope}[xshift=24cm]
\foreach \x/\y in {0/0,1/1,2/0,3/1,4/0,5/1,6/0} {
\node[circle, draw, fill=black, inner sep=1pt] at (\x,\y) {};
}
\draw (0,0)--(1,1)--(2,0)--(3,1)--(4,0)--(5,1)--(6,0);
\end{scope}
\draw (31,-1) -- (31,4);
% Path 5: UDUUDD
\begin{scope}[xshift=32cm]
\foreach \x/\y in {0/0,1/1,2/0,3/1,4/2,5/1,6/0} {
\node[circle, draw, fill=black, inner sep=1pt] at (\x,\y) {};
}
\draw (0,0)--(1,1)--(2,0)--(3,1)--(4,2)--(5,1)--(6,0);
\end{scope}
\end{tikzpicture}
\]
So there are $5$ of them.
\end{statement}

For each $n\geq0$, let
\begin{align*}
c_{n}  &  =\#\ \left(  \text{Dyck paths }(0,0)\rightarrow(2n,0)\right) \\
&  =\#\ (\text{Dyck words of length }2n).
\end{align*}


Then,%
\begin{align*}
c_{0}  &  =1,\\
c_{1}  &  =1,\\
c_{2}  &  =2,\\
c_{3}  &  =5,\\
c_{4}  &  =14,\\
c_{n}  &  =\;?
\end{align*}


These numbers $c_{n}$ are called \emph{Catalan numbers}. See \cite{Stanle15}
for much more about them. We shall next find a recurrence relation and an
explicit formula for them.

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[BenOrn17]{BenOrn}
\href{https://www.fq.math.ca/Papers1/55-5/BenjaminOrnstein.pdf}{Arthur T. Benjamin, Joel Ornstein, \textit{A
Bijective Proof of a Derangement Recurrence}, Fibonacci Quarterly \textbf{55}
(2017), pp. 28--29.}

\bibitem[Elizal20]{Elizal20}\href{https://arxiv.org/abs/2005.11312v1}{Sergi
Elizalde, \textit{A simple bijective proof of a familiar derangement
recurrence}, arXiv:2005.11312v1.}

\bibitem[Grinbe15]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 15 September 2022.\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/2022-09-15c} or
\href{https://arxiv.org/abs/2008.09862v3}{arXiv:2008.09862v3}.

\bibitem[Loehr11]{Loehr-BC}%
\href{http://www.math.vt.edu/people/nloehr/bijbook.html}{Nicholas A. Loehr,
\textit{Bijective Combinatorics}, Chapman \& Hall/CRC 2011.}

\bibitem[Stanle15]{Stanle15}%
\href{https://doi.org/10.1017/CBO9781139871495}{Richard P. Stanley,
\textit{Catalan Numbers}, 1st edition, Cambridge University Press
2015}.\newline See \url{http://math.mit.edu/~rstan/catalan/} for errata.
\end{thebibliography}


\end{document}