\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 12:55:38}
%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}
\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-17}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

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

(digitized using Claude in 2026)

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

\setcounter{theo}{11}

\subsection*{3.5. The Vandermonde Identity}

\begin{theorem}
\label{thm.vandermonde}Let $n\in\mathbb{N}$, $x\in\mathbb{N}$ and
$y\in\mathbb{N}$. Then,
\[
\dbinom{x+y}{n}=\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}=\sum_{k}\dbinom
{x}{k}\dbinom{y}{n-k}.
\]

\end{theorem}

This is the \textquotedblleft Vandermonde convolution
identity\textquotedblright\ for nonnegative integers.

\medskip\noindent\textbf{1st proof.} For any $u\in\mathbb{Q}$ and
$n\in\mathbb{N}$, we have
\begin{align*}
\dbinom{u}{n} &  =\dbinom{u-1}{n-1}+\dbinom{u-1}{n}\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{by Pascal's
recursion}\right)  \\
&  =\dbinom{u-2}{n-2}+\underbrace{\dbinom{u-2}{n-1}+\dbinom{u-2}{n-1}%
}_{\text{combine these terms}}+\dbinom{u-2}{n}\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{by Pascal's recursion
for each term}\right)  \\
&  =\dbinom{u-2}{n-2}+2\dbinom{u-2}{n-1}+\dbinom{u-2}{n}\\
&  =\dbinom{u-3}{n-3}+3\dbinom{u-3}{n-2}+3\dbinom{u-3}{n-1}+\dbinom{u-3}{n}\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{again by Pascal's
recursion and combining}\right)  \\
&  =\cdots\\
&  =\dbinom{u-v}{n-v}+\cdots+\underbrace{\dbinom{v}{k}\dbinom{u-v}{n-k}%
}_{\text{general term}}+\cdots+\dbinom{u-v}{n}\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{by iterating the
above calculation}\right)  \\
&  =\sum_{k=0}^{v}\dbinom{v}{k}\dbinom{u-v}{n-k}.
\end{align*}
Now, apply this to $v=x$ and $u=x+y$. \qed

\medskip\noindent\textbf{2nd proof.} How many ways are there to choose an
$n$-element subset of $\{1,2,\ldots,x\}\cup\{-1,-2,\ldots,-y\}$? We answer
this question in two ways:

\begin{itemize}
\item The answer is clearly $\dbinom{x+y}{n}$.

\item Decide first how many positive integers will be in the subset; call this
number $k$. Now, choose the $k$ positive integers ($\dbinom{x}{k}$ choices)
and choose the $n-k$ negative integers ($\dbinom{y}{n-k}$ choices). Thus, the
total \# of possibilities is $\sum\limits_{k=0}^{n}\dbinom{x}{k}\dbinom
{y}{n-k}$. \qed
\end{itemize}

\medskip\noindent\textbf{3rd proof.} Induction over $n$. See \cite[Theorem
3.29]{detnotes}. \qed

\begin{remark}
We can replace $\displaystyle\sum_{k=0}^{n}$ by $\displaystyle\sum_{k=0}^{x}$
in Theorem \ref{thm.vandermonde}.
\end{remark}

\setcounter{theo}{13}

\begin{corollary}
\label{cor.14}For any $n\in\mathbb{N}$, we have $\displaystyle\sum_{k=0}%
^{n}\dbinom{n}{k}^{2}=\dbinom{2n}{n}$.
\end{corollary}

\begin{proof}
We have%
\[
\sum_{k=0}^{n}\dbinom{n}{k}^{2}=\sum_{k=0}^{n}\dbinom{n}{k}\underbrace{\dbinom
{n}{k}}_{\substack{=\dbinom{n}{n-k}\\\text{(by symmetry)}}}=\sum_{k=0}%
^{n}\dbinom{n}{k}\dbinom{n}{n-k}=\dbinom{n+n}{n}%
\]
by Theorem~\ref{thm.vandermonde} (applied to $x=n$ and $y=n$).
\end{proof}

\subsection*{3.7. Inclusion/Exclusion}

Consider the following facts about cardinalities of finite sets:

\begin{itemize}
\item If $A$ is a finite set, then $\left\vert A\right\vert =\left\vert
A\right\vert $.

\item If $A$ and $B$ are finite sets, then $\left\vert A\cup B\right\vert
=\left\vert A\right\vert +\left\vert B\right\vert -\left\vert A\cap
B\right\vert $.

\item If $A$, $B$ and $C$ are finite sets, then
\[
\left\vert A\cup B\cup C\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert +\left\vert C\right\vert -\left\vert A\cap B\right\vert
-\left\vert A\cap C\right\vert -\left\vert B\cap C\right\vert +\left\vert
A\cap B\cap C\right\vert .
\]

\end{itemize}

How do we generalize this?

\setcounter{theo}{34}

\begin{theorem}
[Principle of Inclusion/Exclusion, aka the Sylvester Sieve]\label{thm.PIE}Let
$A_{1},A_{2},\ldots,A_{n}$ be finite sets.

\begin{enumerate}
\item[\textbf{(a)}] We have%
\begin{align*}
\left\vert A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right\vert  & =\left\vert
A_{1}\right\vert +\left\vert A_{2}\right\vert +\cdots+\left\vert
A_{n}\right\vert \\
& \ \ \ \ \ \ \ \ \ \ -\left\vert A_{1}\cap A_{2}\right\vert -\left\vert
A_{1}\cap A_{3}\right\vert -\cdots-\left\vert A_{n-1}\cap A_{n}\right\vert \\
& \ \ \ \ \ \ \ \ \ \ +\left\vert A_{1}\cap A_{2}\cap A_{3}\right\vert
+\left\vert A_{1}\cap A_{2}\cap A_{4}\right\vert +\cdots\\
& \ \ \ \ \ \ \ \ \ \ -\left\vert A_{1}\cap A_{2}\cap A_{3}\cap A_{4}%
\right\vert -\cdots\\
& \ \ \ \ \ \ \ \ \ \ +\cdots-\cdots+\cdots-\cdots\cdots\cdots\\
& \ \ \ \ \ \ \ \ \ \ +\left(  -1\right)  ^{n-1}\left\vert A_{1}\cap A_{2}%
\cap\cdots\cap A_{n}\right\vert .
\end{align*}
Or, to put this rigorously:%
\[
\left\vert \bigcup_{i=1}^{n}A_{i}\right\vert =\sum_{\substack{I\subseteq
\lbrack n];\\I\neq\varnothing}}(-1)^{|I|-1}\left\vert \bigcap_{i\in I}%
A_{i}\right\vert .
\]
(The expression $\bigcap_{i\in I}A_{i}$ on the right hand side means the
intersection of all $A_{i}$ for $i\in I$. For example, $\displaystyle\bigcap
_{i\in\{2,3,6\}}A_{i}=A_{2}\cap A_{3}\cap A_{6}$.)

\item[\textbf{(b)}] Let $U$ be a finite set containing all $A_{i}$'s as
subsets. Then,%
\[
\left\vert U\setminus\bigcup_{i=1}^{n}A_{i}\right\vert =\sum_{I\subseteq
\lbrack n]}(-1)^{|I|}\left\vert \bigcap_{i\in I}A_{i}\right\vert ,
\]
where $\displaystyle\bigcap_{i\in\varnothing}A_{i}$ means $U$.
\end{enumerate}
\end{theorem}

\begin{proof}
First, we notice that \textbf{(a)} $\Longleftrightarrow$ \textbf{(b)}. In
fact,
\begin{align*}
\text{LHS of \textbf{(b)}} &  =|U|\ -\ \text{LHS of \textbf{(a)}}%
,\qquad\text{but also}\\
\text{RHS of \textbf{(b)}} &  =\underbrace{(-1)^{|\varnothing|}}%
_{=1}\left\vert \underbrace{\bigcap_{i\in\varnothing}A_{i}}_{=U}\right\vert
+\sum_{\substack{I\subseteq\lbrack n];\\I\neq\varnothing}}(-1)^{|I|}\left\vert
\bigcap_{i\in I}A_{i}\right\vert \\
&  =\left\vert U\right\vert +\sum_{\substack{I\subseteq\lbrack n];\\I\neq
\varnothing}}\underbrace{(-1)^{|I|}}_{=-(-1)^{|I|-1}}\left\vert \bigcap_{i\in
I}A_{i}\right\vert \\
&  =\left\vert U\right\vert -\underbrace{\sum_{\substack{I\subseteq\lbrack
n];\\I\neq\varnothing}}(-1)^{|I|-1}\left\vert \bigcap_{i\in I}A_{i}\right\vert
}_{=\text{RHS of \textbf{(a)}}}\\
&  =\left\vert U\right\vert -\ \text{RHS of \textbf{(a)}}.
\end{align*}
So it remains to prove one of \textbf{(a)} and \textbf{(b)}. Let's prove
\textbf{(b)}.

We will use Iverson bracket notation (i.e., the truth value of a statement $S$
will be denoted $\left[  S\right]  $). For any $x\in U$, we have%
\begin{align}
\left[  x\in U\setminus\bigcup_{i=1}^{n}A_{i}\right]   &  =\left[  x\in
\bigcap_{i=1}^{n}\left(  U\setminus A_{i}\right)  \right]
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }U\setminus\bigcup_{i=1}^{n}%
A_{i}=\bigcap_{i=1}^{n}\left(  U\setminus A_{i}\right)  \right)  \nonumber\\
&  =\left[  x\in U\setminus A_{1}\ \wedge\ x\in U\setminus A_{2}%
\ \wedge\ \cdots\ \wedge\ x\in U\setminus A_{n}\right]  \nonumber\\
&  =\prod_{i=1}^{n}\left[  x\in U\setminus A_{i}\right]
\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since }[S_{1}\wedge S_{2}\wedge\cdots\wedge S_{n}]=\prod\limits_{i=1}%
^{n}[S_{i}]\\
\text{for any statements }S_{1},S_{2},\ldots,S_{n}%
\end{array}
\right)  \nonumber\\
&  =\prod_{i=1}^{n}\left(  1-[x\in A_{i}]\right)  \nonumber\\
&  =\sum_{I\subseteq\lbrack n]}(-1)^{|I|}\underbrace{\prod_{i\in I}[x\in
A_{i}]}_{\substack{=\left[  \bigwedge_{i\in I}(x\in A_{i})\right]  \\=[x\in
A_{i}\;\forall\,i\in I]\\=\left[  x\in\bigcap_{i\in I}A_{i}\right]
}}\nonumber\\
&  =\sum_{I\subseteq\lbrack n]}(-1)^{|I|}\left[  x\in\bigcap_{i\in I}%
A_{i}\right]  .\label{eq.4990-2017oct17.1}%
\end{align}


If $P$ is any subset of $U$, then
\begin{equation}
\left\vert P\right\vert =\sum_{x\in U}[x\in P].\label{eq.4990-2017oct17.2}%
\end{equation}


Apply this to $P=U\setminus\bigcup_{i=1}^{n}A_{i}$, and obtain%
\begin{align*}
\left\vert U\setminus\bigcup_{i=1}^{n}A_{i}\right\vert  &  =\sum_{x\in
U}\left[  x\in U\setminus\bigcup_{i=1}^{n}A_{i}\right]  \\
&  =\sum_{x\in U}\ \ \sum_{I\subseteq\lbrack n]}(-1)^{|I|}\left[  x\in
\bigcap_{i\in I}A_{i}\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{eq.4990-2017oct17.1})}\right)  \\
&  =\sum_{I\subseteq\lbrack n]}(-1)^{|I|}\underbrace{\sum_{x\in U}\left[
x\in\bigcap_{i\in I}A_{i}\right]  }_{\substack{=\left\vert \bigcap_{i\in
I}A_{i}\right\vert \\\text{(by (\ref{eq.4990-2017oct17.2}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{by switching
sums}\right)  \\
&  =\sum_{I\subseteq\lbrack n]}(-1)^{|I|}\left\vert \bigcap_{i\in I}%
A_{i}\right\vert .
\end{align*}
This proves \textbf{(b)}. Hence, \textbf{(a)} follows. \qed

\noindent(See also \cite[\S 16]{Galvin} for this proof.)
\end{proof}

\subsubsection*{Example 1: Derangements}

A \emph{derangement} of a set $X$ means a permutation of $X$ that has no fixed points.

Let $D_{n}$ be the \# of derangements of $[n]$.

What is $D_{n}$?

Let $U=\{\text{all permutations of }[n]\}$. For each $i\in\lbrack n]$, let
$A_{i}=\{\pi\in U\mid\pi(i)=i\}$. Then,%
\[
D_{n}=\left\vert U\setminus\bigcup_{i=1}^{n}A_{i}\right\vert =\sum
_{I\subseteq\lbrack n]}(-1)^{|I|}\left\vert \bigcap_{i\in I}A_{i}\right\vert
\]
by Thm.~\ref{thm.PIE} \textbf{(b)}. But for any $I\subseteq\lbrack n]$, we
have%
\begin{align*}
\left\vert \bigcap_{i\in I}A_{i}\right\vert  &  =|\{\pi\in U\ \mid
\ \pi(i)=i\;\forall\,i\in I\}|\\
&  =\left(  n-\left\vert I\right\vert \right)  \left(  n-\left\vert
I\right\vert -1\right)  \cdots1\\
&  =(n-\left\vert I\right\vert )!,
\end{align*}
so this becomes%
\[
D_{n}=\sum_{I\subseteq\lbrack n]}(-1)^{|I|}(n-|I|)!=\sum_{k=0}^{n}%
(-1)^{k}(n-k)!\dbinom{n}{k}.
\]
So we have%
\begin{align*}
D_{n} &  =\sum_{k=0}^{n}(-1)^{k}\underbrace{\dbinom{n}{k}(n-k)!}_{=\dfrac
{n!}{k!}}=\sum_{k=0}^{n}(-1)^{k}\dfrac{n!}{k!}\\
&  =n!\sum_{k=0}^{n}\dfrac{(-1)^{k}}{k!},
\end{align*}
thus%
\[
\dfrac{D_{n}}{n!}=\sum_{k=0}^{n}\dfrac{(-1)^{k}}{k!}\approx\sum_{k=0}^{\infty
}\dfrac{(-1)^{k}}{k!}=e^{-1}.
\]
Actually, $D_{n}=\operatorname{round}(n!/e)$ for $n\geq1$, where
$\operatorname*{round}x$ denotes the result of rounding the real number $x$ to
the nearest integer.

\setcounter{theo}{35}

\begin{corollary}
\label{cor.derangements}We have $D_{n}=n!\sum\limits_{k=0}^{n}\dfrac{(-1)^{k}%
}{k!}$ for all $n\in\mathbb{N}$.
\end{corollary}

\subsubsection*{Example 2: Surjections, again}

Fix $n\in\mathbb{N}$ and $k\in\mathbb{N}$. Compute
\[
\operatorname{sur}(n,k)=\#\text{ of surjections from }[n]\text{ to }[k].
\]


Set $U=\{\text{maps }[n]\rightarrow\lbrack k]\}$. For each $i\in\lbrack k]$,
set%
\[
A_{i}=\{\text{maps }[n]\rightarrow\lbrack k]\text{ which miss }i\}
\]
(we say that a map $f$ misses $i$ if $i$ is not in its image).

Then, $U\setminus\bigcup_{i=1}^{k}A_{i}=\{\text{surjections from }%
[n]\to\lbrack k]\}$.

But Thm.~\ref{thm.PIE} \textbf{(b)} yields%
\begin{align*}
\left\vert U\setminus\bigcup_{i=1}^{k}A_{i}\right\vert  &  =\sum
_{I\subseteq\lbrack k]}(-1)^{|I|}\left\vert \underbrace{\bigcap_{i\in I}A_{i}%
}_{\substack{=\{\text{maps missing all }i\in I\}\\\cong\{\text{maps
}[n]\rightarrow\lbrack k]\setminus I\}}}\right\vert \\
&  =\sum_{I\subseteq\lbrack k]}(-1)^{|I|}\underbrace{\left\vert \{\text{maps
}[n]\rightarrow\lbrack k]\setminus I\}\right\vert }_{\substack{=(k-|I|)^{n}%
}}\\
&  =\sum_{I\subseteq\lbrack k]}(-1)^{|I|}(k-|I|)^{n}\\
&  =\sum_{i=0}^{k}(-1)^{i}(k-i)^{n}\dbinom{k}{i}.
\end{align*}
So
\[
\operatorname{sur}(n,k)=\sum_{i=0}^{k}(-1)^{i}\dbinom{k}{i}(k-i)^{n}%
=\sum_{j=0}^{k}(-1)^{k-j}\dbinom{k}{j}j^{n}.
\]


This was a HW2 problem (Exercise 4 on homework set 2).

\subsubsection*{Example 3: Euler's $\phi$-function}

\emph{Euler's }$\phi$\emph{-function} (also called \emph{Euler's totient
function}, also written $\varphi$) is defined as a function $\phi
\colon\{1,2,3,\ldots\}\rightarrow\mathbb{N}$ given by%
\[
\phi(n)=\#\text{ of all }m\in\lbrack n]\text{ coprime to }n.
\]
Examples:
\begin{align*}
\phi(2) &  =|\{1,\cancel{2}\}|=1.\\
\phi(4) &  =|\{1,\cancel{2},3,\cancel{4}\}|=2.\\
\phi(6) &  =|\{1,\cancel{2},\cancel{3},\cancel{4},5,\cancel{6}\}|=2.\\
\phi(12) &
=|\{1,\cancel{2},\cancel{3},\cancel{4},5,\cancel{6},7,\cancel{8},\cancel{9},\cancel{10},11,\cancel{12}\}|=4.
\end{align*}


Can we find a formula for $\phi(n)$ in general?

Let $p_{1},p_{2},\ldots,p_{k}$ be the distinct prime factors of $n$. Let
$U=[n]$, and for each $i\in\lbrack k]$, let
\[
A_{i}=\{x\in\lbrack n]\mid\underbrace{x\in p_{i}\mathbb{Z}}_{\text{this says
}p_{i}\mid x}\}.
\]
Then
\[
\{m\in\lbrack n]\text{ coprime to }n\}=U\setminus\bigcup_{i=1}^{k}A_{i}.
\]


Hence,%
\begin{align*}
\phi(n) &  =\left\vert U\setminus\bigcup_{i=1}^{k}A_{i}\right\vert
=\sum_{I\subseteq\lbrack k]}(-1)^{|I|}\underbrace{\left\vert \bigcap_{i\in
I}A_{i}\right\vert }_{\substack{=\#\text{ of all }m\in\lbrack n]\\\text{that
are multiples of all }p_{i}\text{ (for }i\in I\text{)}\\=\#\text{ of all }%
m\in\lbrack n]\\\text{that are multiples of }\prod_{i\in I}p_{i}\\=\dfrac
{n}{\prod_{i\in I}p_{i}}}}\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{by Thm.~\ref{thm.PIE}
\textbf{(b)}}\right)  \\
&  =\sum_{I\subseteq\lbrack k]}(-1)^{|I|}\dfrac{n}{\prod_{i\in I}p_{i}%
}=n\underbrace{\sum_{I\subseteq\lbrack k]}(-1)^{\left\vert I\right\vert }%
\prod_{i\in I}\dfrac{1}{p_{i}}}_{=\prod_{i=1}^{k}\left(  1-\dfrac{1}{p_{i}%
}\right)  }\\
&  =n\prod_{i=1}^{k}\left(  1-\dfrac{1}{p_{i}}\right)  .
\end{align*}


\subsection*{3.8. More about Derangements}

Corollary \ref{cor.derangements} gave an explicit formula for $D_{n}$. Next
time, we will prove a recursive one:

\setcounter{theo}{40}

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



\begin{thebibliography}{99999999}                                                                                         %
\bibitem[Galvin17]{Galvin}David Galvin, \textit{Basic discrete mathematics},
13 December 2017.\newline%
\url{https://www3.nd.edu/~dgalvin1/60610/60610_S21/index.html} \newline(Follow
the Overleaf link and compile main.tex and Course-notes.tex. See also
\url{https://web.archive.org/web/20180205122609/http://www-users.math.umn.edu/~dgrinber/comb/60610lectures2017-Galvin.pdf}
for an archived old version.)

\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}.
\end{thebibliography}


\end{document}