\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}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, January 24, 2021 02:22:04}
%TCIDATA{SuppressPackageManagement}
%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}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\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]}
\newcommand\staircasepath[4]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
-- ++(0,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\draw[dashed] (#1) -- +(#2,#2);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
\coordinate (dep) at (0,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\delannoypath[4]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
	  \ifnum\dir=0
-- ++(0,1)
	  \else
	  -- ++(1,1)
	  \fi
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
	  \ifnum\dir=0
\coordinate (dep) at (0,1);
	  \else
	  \coordinate (dep) at (1,1);
	  \fi
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\dyckpath[3]{
\fill[fill=lime]
(#1)
\foreach \dir in {#3}{
\ifnum\dir=1
-- ++(1,-1)
\else
-- ++(1,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(2*#2, #2);
\coordinate (prev) at (#1);
\foreach \dir in {#3}{
\ifnum\dir=1
\coordinate (dep) at (1,-1);
\else
\coordinate (dep) at (1,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\ihead{Math 4707 Spring 2018 (Darij Grinberg): homework set 3}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 Spring 2018 (Darij Grinberg): homework set 3 with solutions}
\end{center}

%

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


\bigskip

Recall the following:

\begin{itemize}
\item If $n\in\mathbb{N}$, then $\left[  n\right]  $ denotes the $n$-element
set $\left\{  1,2,\ldots,n\right\}  $.

\item We use the Iverson bracket notation.

\item If $a\in\mathbb{N}$ and $b\in\mathbb{N}$, then $\operatorname*{sur}%
\left(  a,b\right)  $ denotes the number of surjective maps from $\left[
a\right]  $ to $\left[  b\right]  $.
\end{itemize}

Also, here is a collection of identities that we shall use:

\begin{itemize}
\item We have
\begin{equation}
\dbinom{m}{n}=0 \label{eq.binom.0}%
\end{equation}
for every $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfying $m<n$.

\item We have%
\begin{equation}
\dbinom{m}{n}=\dbinom{m-1}{n-1}+\dbinom{m-1}{n} \label{eq.binom.rec.m}%
\end{equation}
for any $m\in\mathbb{Z}$ and $n\in\mathbb{Z}$. (This is the recurrence
relation of the binomial coefficients.)

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

\item We have
\begin{equation}
\dbinom{m+n}{m}=\dbinom{m+n}{n} \label{eq.binom.symm2}%
\end{equation}
for any $m\in\mathbb{N}$ and $n\in\mathbb{N}$. (This follows by applying
(\ref{eq.binom.symm}) to $m+n$ and $m$ instead of $m$ and $n$.)

\item For every $x\in\mathbb{N}$ and $y\in\mathbb{N}$ and $n\in\mathbb{N}$, we
have%
\begin{equation}
\dbinom{n+1}{x+y+1}=\sum_{k=0}^{n}\dbinom{k}{x}\dbinom{n-k}{y}.
\label{eq.vandermonde.consequences.f}%
\end{equation}
(This is Proposition 3.21 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018feb26.pdf}{the
classwork from 26 February 2018}, or \cite[Proposition 3.32 \textbf{(f)}%
]{detnotes}.)

\item We have%
\begin{equation}
\dbinom{m}{n}=\dfrac{m}{n}\dbinom{m-1}{n-1} \label{eq.binom.absorp}%
\end{equation}
for any $m\in\mathbb{Q}$ and $n\in\left\{  1,2,3,\ldots\right\}  $. (This is
the \textit{absorption identity}, and has been proven in \cite[Proposition
3.22]{detnotes}. Also, it is very easy to check.)

\item Every $n\in\mathbb{N}$ satisfies
\begin{equation}
\sum_{k=0}^{n}\dbinom{n}{k}=2^{n}. \label{eq.binom.1+1}%
\end{equation}
(This is Corollary 1.16b in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018jan22.pdf}{the
classwork from 22 January 2018}, or \cite[Proposition 3.39 \textbf{(b)}%
]{detnotes}.)

\item Every $n\in\mathbb{N}$ satisfies%
\begin{equation}
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}=\left[  n=0\right]  .
\label{eq.binom.1-1}%
\end{equation}
(This is Corollary 3.3 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018feb14.pdf}{the
classwork from 14 February 2018}, or \cite[Proposition 3.39 \textbf{(c)}%
]{detnotes}.)

\item If $m\in\mathbb{N}$ and $n\in\mathbb{N}$, and if $S$ is an $m$-element
set, then
\begin{equation}
\dbinom{m}{n}\text{ is the number of all }n\text{-element subsets of
}S\text{.} \label{eq.binom.subsets}%
\end{equation}
(This is the combinatorial interpretation of the binomial coefficients.)
\end{itemize}

\subsection{Another binomial identity}

\begin{exercise}
\label{exe.binom.Hn-altsum}Let $n\in\mathbb{N}$. Prove that%
\begin{equation}
\sum_{k=1}^{n}\dfrac{\left(  -1\right)  ^{k-1}}{k}\dbinom{n}{k}=\dfrac{1}%
{1}+\dfrac{1}{2}+\cdots+\dfrac{1}{n}. \label{eq.exe.binom.Hn-altsum.eq}%
\end{equation}


[\textbf{Hint:} How does the left hand side grow when $n$ is replaced by $n+1$ ?]
\end{exercise}

We shall outline a solution of this exercise. (For the missing details, see
\cite[solution to Exercise 3.19]{detnotes}.)

\begin{proof}
[Solution to Exercise \ref{exe.binom.Hn-altsum} (sketched).]We shall solve
Exercise \ref{exe.binom.Hn-altsum} by induction on $n$:

\textit{Induction base:} If $n=0$, then both sides of
(\ref{eq.exe.binom.Hn-altsum.eq}) are empty sums, and thus are equal. Hence,
Exercise \ref{exe.binom.Hn-altsum} holds for $n=0$. This completes the
induction base.

\textit{Induction step:} Let $m\in\mathbb{N}$. Assume that Exercise
\ref{exe.binom.Hn-altsum} holds for $n=m$. We must prove that Exercise
\ref{exe.binom.Hn-altsum} holds for $n=m+1$.

We have assumed that Exercise \ref{exe.binom.Hn-altsum} holds for $n=m$. In
other words, we have%
\begin{equation}
\sum_{k=1}^{m}\dfrac{\left(  -1\right)  ^{k-1}}{k}\dbinom{m}{k}=\dfrac{1}%
{1}+\dfrac{1}{2}+\cdots+\dfrac{1}{m}. \label{sol.binom.Hn-altsum.IH}%
\end{equation}


Now,%
\begin{align*}
&  \sum_{k=1}^{m+1}\dfrac{\left(  -1\right)  ^{k-1}}{k}\underbrace{\dbinom
{m+1}{k}}_{\substack{=\dbinom{m}{k-1}+\dbinom{m}{k}\\\text{(by the recurrence
relation}\\\text{of the binomial coefficients)}}}\\
&  =\sum_{k=1}^{m+1}\underbrace{\dfrac{\left(  -1\right)  ^{k-1}}{k}\dbinom
{m}{k-1}}_{=\dfrac{\left(  -1\right)  ^{k-1}}{m+1}\cdot\dfrac{m+1}{k}%
\dbinom{m}{k-1}}+\underbrace{\sum_{k=1}^{m+1}\dfrac{\left(  -1\right)  ^{k-1}%
}{k}\dbinom{m}{k}}_{=\sum_{k=1}^{m}\dfrac{\left(  -1\right)  ^{k-1}}{k}%
\dbinom{m}{k}+\dfrac{\left(  -1\right)  ^{\left(  m+1\right)  -1}}{m+1}%
\dbinom{m}{m+1}}\\
&  =\underbrace{\sum_{k=1}^{m+1}\dfrac{\left(  -1\right)  ^{k-1}}{m+1}%
\cdot\dfrac{m+1}{k}\dbinom{m}{k-1}}_{=\dfrac{1}{m+1}\sum_{k=1}^{m+1}\left(
-1\right)  ^{k-1}\dfrac{m+1}{k}\dbinom{m}{k-1}}+\underbrace{\sum_{k=1}%
^{m}\dfrac{\left(  -1\right)  ^{k-1}}{k}\dbinom{m}{k}}_{\substack{=\dfrac
{1}{1}+\dfrac{1}{2}+\cdots+\dfrac{1}{m}\\\text{(by
(\ref{sol.binom.Hn-altsum.IH}))}}}+\dfrac{\left(  -1\right)  ^{\left(
m+1\right)  -1}}{m+1}\underbrace{\dbinom{m}{m+1}}_{\substack{=0\\\text{(by
(\ref{eq.binom.0}))}}}\\
&  =\dfrac{1}{m+1}\sum_{k=1}^{m+1}\left(  -1\right)  ^{k-1}\dfrac{m+1}%
{k}\dbinom{m}{k-1}+\left(  \dfrac{1}{1}+\dfrac{1}{2}+\cdots+\dfrac{1}%
{m}\right)  .
\end{align*}
In view of%
\begin{align*}
&  \sum_{k=1}^{m+1}\left(  -1\right)  ^{k-1}\underbrace{\dfrac{m+1}{k}%
\dbinom{m}{k-1}}_{\substack{=\dbinom{m+1}{k}\\\text{(because
(\ref{eq.binom.absorp}) (applied to }m+1\text{ and }k\\\text{instead of
}m\text{ and }n\text{) yields}\\\dbinom{m+1}{k}=\dfrac{m+1}{k}\dbinom{m}%
{k-1}\text{)}}}\\
&  =\sum_{k=1}^{m+1}\left(  -1\right)  ^{k-1}\dbinom{m+1}{k}=\sum_{k=0}%
^{m+1}\underbrace{\left(  -1\right)  ^{k-1}}_{=-\left(  -1\right)  ^{k}%
}\dbinom{m+1}{k}-\underbrace{\left(  -1\right)  ^{0-1}}_{=-1}%
\underbrace{\dbinom{m+1}{0}}_{=1}\\
&  =-\underbrace{\sum_{k=0}^{m+1}\left(  -1\right)  ^{k}\dbinom{m+1}{k}%
}_{\substack{=\left[  m+1=0\right]  \\\text{(by (\ref{eq.binom.1-1}))}%
}}-\left(  -1\right)  =-\underbrace{\left[  m+1=0\right]  }%
_{\substack{=0\\\text{(since }m+1\neq0\text{)}}}-\left(  -1\right)  =1,
\end{align*}
this becomes%
\begin{align*}
&  \sum_{k=1}^{m+1}\dfrac{\left(  -1\right)  ^{k-1}}{k}\dbinom{m+1}{k}\\
&  =\dfrac{1}{m+1}\underbrace{\sum_{k=1}^{m+1}\left(  -1\right)  ^{k-1}%
\dfrac{m+1}{k}\dbinom{m}{k-1}}_{=1}+\left(  \dfrac{1}{1}+\dfrac{1}{2}%
+\cdots+\dfrac{1}{m}\right) \\
&  =\dfrac{1}{m+1}+\left(  \dfrac{1}{1}+\dfrac{1}{2}+\cdots+\dfrac{1}%
{m}\right)  =\dfrac{1}{1}+\dfrac{1}{2}+\cdots+\dfrac{1}{m+1}.
\end{align*}
In other words, Exercise \ref{exe.binom.Hn-altsum} holds for $n=m+1$. This
completes the induction step. Thus, Exercise \ref{exe.binom.Hn-altsum} is solved.
\end{proof}

\subsection{More on inclusion/exclusion}

\subsubsection{An exercise on counting surjections and more}

\begin{exercise}
\label{exe.DIE.count-surjs}Let $A$, $B$ and $C$ be three finite sets such that
$C\subseteq B$. Let $a=\left\vert A\right\vert $, $b=\left\vert B\right\vert $
and $c=\left\vert C\right\vert $.

\textbf{(a)} Prove that the number of maps $f:A\rightarrow B$ satisfying
$C\subseteq f\left(  A\right)  $ is%
\[
\sum_{k=0}^{c}\left(  -1\right)  ^{k}\dbinom{c}{k}\left(  b-k\right)  ^{a}.
\]


\textbf{(b)} Prove that the number of surjective maps $f:A\rightarrow B$ is%
\[
\operatorname*{sur}\left(  a,b\right)  =\sum_{k=0}^{b}\left(  -1\right)
^{k}\dbinom{b}{k}\left(  b-k\right)  ^{a}=\sum_{k=0}^{b}\left(  -1\right)
^{b-k}\dbinom{b}{k}k^{a}.
\]


[This is a formula I mentioned but did not prove in class; of course, you
cannot use it without proof.]

\textbf{(c)} Prove that%
\[
\sum_{k=0}^{c}\left(  -1\right)  ^{k}\dbinom{c}{k}\left(  b-k\right)  ^{a}=0
\]
whenever $c>a$.

\textbf{(d)} Prove that%
\[
\sum_{k=0}^{a}\left(  -1\right)  ^{k}\dbinom{a}{k}\left(  b-k\right)
^{a}=a!.
\]


[\textbf{Hint:} For part \textbf{(a)}, notice that a map $f:A\rightarrow B$
satisfies $C\subseteq f\left(  A\right)  $ if and only if the image of $f$
misses none of the $c$ elements of $C$. Parts \textbf{(b)}, \textbf{(c)} and
\textbf{(d)} should follow from \textbf{(a)}.]
\end{exercise}

This exercise has turned out to be harder than I thought when I posed it. In
particular, deriving its part \textbf{(d)} from the previous parts is tricky,
since you cannot just set $c=a$ and apply part \textbf{(a)} (indeed, in order
to set $c=a$, you would need to find a $b$-element set $B$ with an $a$-element
subset $C$, but this is only possible when $a\leq b$). We shall below outline
a solution that addresses these issues by using the \textquotedblleft
polynomial identity trick\textquotedblright\ (Lemma~\ref{lem.pi-trick.c}
below). It is also possible to prove parts \textbf{(c)} and \textbf{(d)} of
Exercise~\ref{exe.DIE.count-surjs} algebraically, completely avoiding the use
of the previous parts; this is done in \cite[proof of Corollary 2]{QEDMO6P4}.

\subsubsection{Solutions to Exercise \ref{exe.DIE.count-surjs} \textbf{(a)},
\textbf{(b)} and \textbf{(c)}}

Let us first recall the principle of inclusion and exclusion:

\begin{theorem}
\label{thm.pie}Let $n\in\mathbb{N}$. Let $A_{1},A_{2},\ldots,A_{n}$ be finite sets.

\textbf{(a)} We have%
\[
\left\vert \bigcup_{i=1}^{n}A_{i}\right\vert =\sum_{\substack{I\subseteq
\left[  n\right]  ;\\I\neq\varnothing}}\left(  -1\right)  ^{\left\vert
I\right\vert -1}\left\vert \bigcap_{i\in I}A_{i}\right\vert .
\]


\textbf{(b)} Let $S$ be a finite set. Assume that each of $A_{1},A_{2}%
,\ldots,A_{n}$ is a subset of $S$. Then,%
\[
\left\vert S\setminus\bigcup_{i=1}^{n}A_{i}\right\vert =\sum_{I\subseteq
\left[  n\right]  }\left(  -1\right)  ^{\left\vert I\right\vert }\left\vert
\bigcap_{i\in I}A_{i}\right\vert .
\]
Here, the \textquotedblleft empty\textquotedblright\ intersection
$\bigcap_{i\in\varnothing}A_{i}$ is understood to mean the set $S$.
\end{theorem}

\begin{proof}
[Solution to Exercise \ref{exe.DIE.count-surjs} (sketched).]Let us first solve
parts \textbf{(a)}, \textbf{(b)} and \textbf{(c)} of the exercise. Then, we'll
prepare a bit further for the solution to \textbf{(d)}.

We shall use the symbol $\cong$ for \textquotedblleft in bijection
with\textquotedblright; i.e., for two sets $U$ and $V$, we write
\textquotedblleft$U\cong V$\textquotedblright\ if and only if there is a
bijection from $U$ to $V$. (In abstract algebra, the symbol $\cong$ stands for
\textquotedblleft is isomorphic to\textquotedblright, which is a
generalization of our use of this symbol.)

\textbf{(a)} We WLOG assume that $C=\left[  c\right]  $ (since we can relabel
the $c$ elements of $C$ as we wish, in particular as $1,2,\ldots,c$). Thus,
$\left[  c\right]  =C\subseteq B$.

Let $S$ be the set of all maps $f:A\rightarrow B$. For each $i\in C$, we let
$T_{i}$ be the set of all maps $f:A\rightarrow B$ that satisfy $i\notin
f\left(  A\right)  $ (in other words, that never take the value $i$). Thus, we
have defined $c$ sets $T_{1},T_{2},\ldots,T_{c}$ (since $C=\left[  c\right]
$). These $c$ sets are subsets of $S$. Their union is%
\begin{align}
\bigcup_{i=1}^{c}T_{i}  &  =\left\{  f:A\rightarrow B\ \mid\ \text{there is
some }i\in\left[  c\right]  \text{ such that }i\notin f\left(  A\right)
\right\} \nonumber\\
&  =\left\{  f:A\rightarrow B\ \mid\ \underbrace{\left[  c\right]  }%
_{=C}\not \subseteq f\left(  A\right)  \right\} \nonumber\\
&  =\left\{  f:A\rightarrow B\ \mid\ C\not \subseteq f\left(  A\right)
\right\}  . \label{sol.DIE.count-surjs.cup}%
\end{align}


On the other hand, each subset $I$ of $\left[  c\right]  $ satisfies%
\begin{align*}
\bigcap_{i\in I}T_{i}  &  =\left\{  f:A\rightarrow B\ \mid\ f\text{ takes none
of the }i\in I\text{ as values}\right\} \\
&  =\left\{  f:A\rightarrow B\ \mid\ \text{all values of }f\text{ belong to
}B\setminus I\right\} \\
&  \cong\left\{  f:A\rightarrow B\setminus I\right\}
\end{align*}
(because maps $f:A\rightarrow B$ whose all values belong to $B\setminus I$ are
in bijection with maps $f:A\rightarrow B\setminus I$\ \ \ \ \footnote{To
transform a former map into a latter map, just switch its target from $B$ to
$B\setminus I$, without changing its values. Similarly for the backwards
transformation.}) and thus%
\begin{align}
\left\vert \bigcap_{i\in I}T_{i}\right\vert  &  =\left\vert \left\{
f:A\rightarrow B\setminus I\right\}  \right\vert =\left\vert B\setminus
I\right\vert ^{\left\vert A\right\vert }\nonumber\\
&  =\left(  \left\vert B\right\vert -\left\vert I\right\vert \right)
^{\left\vert A\right\vert }\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left\vert
B\setminus I\right\vert =\left\vert B\right\vert -\left\vert I\right\vert
\text{ (because }I\subseteq\left[  c\right]  \subseteq B\text{)}\right)
\nonumber\\
&  =\left(  b-\left\vert I\right\vert \right)  ^{a}
\label{sol.DIE.count-surjs.cap}%
\end{align}
(since $\left\vert B\right\vert =b$ and $\left\vert A\right\vert =a$). Note
that this holds even when $I=\varnothing$, as long as the \textquotedblleft
empty\textquotedblright\ intersection $\bigcap_{i\in\varnothing}T_{i}$ is
understood to mean the set $S$.

Theorem \ref{thm.pie} \textbf{(b)} (applied to $c$ and $T_{i}$ instead of $n$
and $A_{i}$) yields%
\begin{align*}
&  \left\vert S\setminus\bigcup_{i=1}^{c}T_{i}\right\vert \\
&  =\underbrace{\sum_{I\subseteq\left[  c\right]  }}_{=\sum_{k=0}^{c}%
\sum_{\substack{I\subseteq\left[  c\right]  ;\\\left\vert I\right\vert =k}%
}}\left(  -1\right)  ^{\left\vert I\right\vert }\underbrace{\left\vert
\bigcap_{i\in I}T_{i}\right\vert }_{\substack{=\left(  b-\left\vert
I\right\vert \right)  ^{a}\\\text{(by (\ref{sol.DIE.count-surjs.cap}))}}%
}=\sum_{k=0}^{c}\sum_{\substack{I\subseteq\left[  c\right]  ;\\\left\vert
I\right\vert =k}}\underbrace{\left(  -1\right)  ^{\left\vert I\right\vert
}\left(  b-\left\vert I\right\vert \right)  ^{a}}_{\substack{=\left(
-1\right)  ^{k}\left(  b-k\right)  ^{a}\\\text{(since }\left\vert I\right\vert
=k\text{)}}}\\
&  =\sum_{k=0}^{c}\underbrace{\sum_{\substack{I\subseteq\left[  c\right]
;\\\left\vert I\right\vert =k}}\left(  -1\right)  ^{k}\left(  b-k\right)
^{a}}_{\left(  \text{the number of all subsets }I\subseteq\left[  c\right]
\text{ satisfying }\left\vert I\right\vert =k\right)  \cdot\left(  -1\right)
^{k}\left(  b-k\right)  ^{a}}\\
&  =\sum_{k=0}^{c}\underbrace{\left(  \text{the number of all subsets
}I\subseteq\left[  c\right]  \text{ satisfying }\left\vert I\right\vert
=k\right)  }_{\substack{=\left(  \text{the number of all }k\text{-element
subsets of }\left[  c\right]  \right)  \\=\dbinom{c}{k}\\\text{(by
\eqref{eq.binom.subsets})}}}\cdot\left(  -1\right)  ^{k}\left(  b-k\right)
^{a}\\
&  =\sum_{k=0}^{c}\dbinom{c}{k}\cdot\left(  -1\right)  ^{k}\left(  b-k\right)
^{a}=\sum_{k=0}^{c}\left(  -1\right)  ^{k}\dbinom{c}{k}\left(  b-k\right)
^{a}.
\end{align*}
In view of%
\begin{align*}
S\setminus\bigcup_{i=1}^{c}T_{i}  &  =S\setminus\left\{  f:A\rightarrow
B\ \mid\ C\not \subseteq f\left(  A\right)  \right\}
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.DIE.count-surjs.cup})}\right)
\\
&  =\left\{  f:A\rightarrow B\ \mid\ \text{not }C\not \subseteq f\left(
A\right)  \right\}  =\left\{  f:A\rightarrow B\ \mid\ C\subseteq f\left(
A\right)  \right\}  ,
\end{align*}
this rewrites as%
\[
\left\vert \left\{  f:A\rightarrow B\ \mid\ C\subseteq f\left(  A\right)
\right\}  \right\vert =\sum_{k=0}^{c}\left(  -1\right)  ^{k}\dbinom{c}%
{k}\left(  b-k\right)  ^{a}.
\]
This solves Exercise \ref{exe.DIE.count-surjs} \textbf{(a)}.

\textbf{(b)} The surjective maps $f:A\rightarrow B$ are precisely the maps
$f:A\rightarrow B$ satisfying $B\subseteq f\left(  A\right)  $. Hence,
Exercise \ref{exe.DIE.count-surjs} \textbf{(a)} (applied to $B$ and $b$
instead of $C$ and $c$) yields that the number of surjective maps
$f:A\rightarrow B$ is
\begin{align*}
&  \sum_{k=0}^{b}\left(  -1\right)  ^{k}\dbinom{b}{k}\left(  b-k\right)
^{a}\\
&  =\sum_{k=0}^{b}\left(  -1\right)  ^{b-k}\underbrace{\dbinom{b}{b-k}%
}_{\substack{=\dbinom{b}{k}\\\text{(by (\ref{eq.binom.symm}))}}%
}\underbrace{\left(  b-\left(  b-k\right)  \right)  ^{a}}_{=k^{a}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }b-k\text{ for
}k\text{ in the sum}\right) \\
&  =\sum_{k=0}^{b}\left(  -1\right)  ^{b-k}\dbinom{b}{k}k^{a}.
\end{align*}
Also, of course, we know that this number is $\operatorname*{sur}\left(
a,b\right)  $ (since $\left\vert A\right\vert =a$ and $\left\vert B\right\vert
=b$). Thus, Exercise \ref{exe.DIE.count-surjs} \textbf{(b)} is solved.

\textbf{(c)} Assume that $c>a$. Thus, there exist no maps $f:A\rightarrow B$
satisfying $C\subseteq f\left(  A\right)  $ (because $C\subseteq f\left(
A\right)  $ would yield $\left\vert C\right\vert \leq\left\vert f\left(
A\right)  \right\vert \leq\left\vert A\right\vert =a<c=\left\vert C\right\vert
$, which is absurd).

Exercise \ref{exe.DIE.count-surjs} \textbf{(a)} yields that the number of maps
$f:A\rightarrow B$ satisfying $C\subseteq f\left(  A\right)  $ is%
\[
\sum_{k=0}^{c}\left(  -1\right)  ^{k}\dbinom{c}{k}\left(  b-k\right)  ^{a}.
\]
On the other hand, the same number must be $0$ (since there exist no maps
$f:A\rightarrow B$ satisfying $C\subseteq f\left(  A\right)  $). Comparing the
two results, we obtain $\sum_{k=0}^{c}\left(  -1\right)  ^{k}\dbinom{c}%
{k}\left(  b-k\right)  ^{a}=0$. This solves Exercise \ref{exe.DIE.count-surjs}
\textbf{(c)}.

Part \textbf{(d)} follows from Theorem \ref{thm.DIE.count-surjs.d-gen} below.
\end{proof}

Let us now take a break and discuss a generalization of part \textbf{(c)}. In
fact, our above solution of Exercise \ref{exe.DIE.count-surjs} \textbf{(c)}
presumes that $A$, $B$, $C$, $a$, $b$ and $c$ are as defined in Exercise
\ref{exe.DIE.count-surjs} (thus, $A$, $B$ and $C$ are three finite sets such
that $C\subseteq B$, and $a=\left\vert A\right\vert $, $b=\left\vert
B\right\vert $ and $c=\left\vert C\right\vert $). This is fine -- since the
exercise itself makes these assumptions. But you might wonder what happens
more generally, if $a$, $b$ and $c$ are \textbf{arbitrary} nonnegative
integers satisfying $c>a$, not necessarily the sizes of three finite sets $A$,
$B$ and $C$ satisfying $C\subseteq B$. Does $\sum_{k=0}^{c}\left(  -1\right)
^{k}\dbinom{c}{k}\left(  b-k\right)  ^{a}=0$ still hold in this case?

The answer is \textquotedblleft yes\textquotedblright. We can even generalize
a bit further and state this for all $b\in\mathbb{Q}$:

\begin{theorem}
\label{thm.DIE.count-surjs.c-gen}Let $a\in\mathbb{N}$, $b\in\mathbb{Q}$ and
$c\in\mathbb{N}$ be such that $c>a$. Then,%
\begin{equation}
\sum_{k=0}^{c}\left(  -1\right)  ^{k}\dbinom{c}{k}\left(  b-k\right)  ^{a}=0.
\label{eq.thm.DIE.count-surjs.c-gen.eq}%
\end{equation}

\end{theorem}

In order to prove this theorem in full generality, we will need the
\textquotedblleft polynomial identity trick\textquotedblright; specifically,
we shall use the following fact (Theorem 3.20 \textbf{(b)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018feb26.pdf}{the
classwork from 26 February 2018}):

\begin{lemma}
\label{lem.pi-trick.c}If a polynomial $P$ with rational coefficients has
infinitely many roots, then $P$ is the zero polynomial.
\end{lemma}

Our proof of Theorem \ref{thm.DIE.count-surjs.c-gen} will be similar to how we
salvaged our first two proofs of the Chu-Vandermonde convolution identity back
in class:

\begin{proof}
[Proof of Theorem \ref{thm.DIE.count-surjs.c-gen}.]Let us forget that $b$ is
fixed. Thus, $a$ and $c$ are fixed, but $b$ is not. We must prove that
(\ref{eq.thm.DIE.count-surjs.c-gen.eq}) holds for each $b\in\mathbb{Q}$.

We now claim that for every \textbf{integer} $b\geq c$, the equality
(\ref{eq.thm.DIE.count-surjs.c-gen.eq}) holds.

[\textit{Proof:} Let $b\geq a$ be an integer. Let $A=\left[  a\right]  $,
$B=\left[  b\right]  $ and $C=\left[  c\right]  $. Then, $C\subseteq B$ (since
$c\leq b$). Also, clearly, $a=\left\vert A\right\vert $ and $b=\left\vert
B\right\vert $ and $c=\left\vert C\right\vert $. Thus, Exercise
\ref{exe.DIE.count-surjs} \textbf{(c)} yields $\sum_{k=0}^{c}\left(
-1\right)  ^{k}\dbinom{c}{k}\left(  b-k\right)  ^{a}=0$. In other words, the
equality (\ref{eq.thm.DIE.count-surjs.c-gen.eq}) holds. Qed.]

So we have shown that for every \textbf{integer} $b\geq c$, the equality
(\ref{eq.thm.DIE.count-surjs.c-gen.eq}) holds. In other words, every integer
$b\geq c$ is a root of the polynomial $\sum_{k=0}^{c}\left(  -1\right)
^{k}\dbinom{c}{k}\left(  x-k\right)  ^{a}$ (in the indeterminate $x$). Thus,
this polynomial has infinitely many roots (because there are infinitely many
integers $b\geq c$). Thus, Lemma \ref{lem.pi-trick.c} shows that this
polynomial is the zero polynomial. In other words,%
\begin{equation}
\sum_{k=0}^{c}\left(  -1\right)  ^{k}\dbinom{c}{k}\left(  x-k\right)  ^{a}=0.
\label{pf.lem.pi-trick.c.almost}%
\end{equation}
Now, for any $b\in\mathbb{Q}$, we can substitute $b$ for $x$ in the identity
(\ref{pf.lem.pi-trick.c.almost}), and we obtain precisely
(\ref{eq.thm.DIE.count-surjs.c-gen.eq}). This proves Theorem
\ref{thm.DIE.count-surjs.c-gen}.
\end{proof}

\subsubsection{Solution to Exercise \ref{exe.DIE.count-surjs} \textbf{(d)}}

Let us next prove a similarly generalized part \textbf{(d)} of Exercise
\ref{exe.DIE.count-surjs}:

\begin{theorem}
\label{thm.DIE.count-surjs.d-gen}Let $a\in\mathbb{N}$ and $b\in\mathbb{Q}$.
Then,%
\begin{equation}
\sum_{k=0}^{a}\left(  -1\right)  ^{k}\dbinom{a}{k}\left(  b-k\right)  ^{a}=a!.
\label{eq.thm.DIE.count-surjs.d-gen.eq}%
\end{equation}

\end{theorem}

Our proof will rely on the following simple fact:

\begin{proposition}
\label{prop.count.ABC-injs}Let $A$, $B$ and $C$ be three finite sets such that
$C\subseteq B$ and $\left\vert C\right\vert =\left\vert A\right\vert $. Then:

\textbf{(a)} The number of injective maps $f:A\rightarrow B$ whose image is
$C$ is $\left\vert A\right\vert !$.

\textbf{(b)} The number of maps $f:A\rightarrow B$ satisfying $C\subseteq
f\left(  A\right)  $ is $\left\vert A\right\vert !$.

\textbf{(c)} The number of injective maps $f:A\rightarrow B$ satisfying
$f\left(  A\right)  \subseteq C$ is $\left\vert A\right\vert !$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.count.ABC-injs} (sketched).]\textbf{(a)} The
injective maps $f:A\rightarrow B$ whose image is $C$ can be identified with
the bijective maps from $A$ to $C$. More precisely: If $f:A\rightarrow B$ is
any map satisfying $f\left(  A\right)  \subseteq C$, then we can define a map
$\overline{f}:A\rightarrow C$ by%
\[
\left(  \overline{f}\left(  a\right)  =f\left(  a\right)
\ \ \ \ \ \ \ \ \ \ \text{for all }a\in A\right)  .
\]
This latter map $\overline{f}$ is well-defined, because $f\left(  a\right)
\in f\left(  A\right)  \subseteq C$ for each $a\in A$. Moreover, $f$ can be
reconstructed from $\overline{f}$.

If $f:A\rightarrow B$ is an \textbf{injective} map satisfying $f\left(
A\right)  \subseteq C$, then the resulting map $\overline{f}:A\rightarrow C$
is again injective. Moreover, if $f:A\rightarrow B$ is a map whose image is
$C$ (that is, we have $f\left(  A\right)  =C$, not just $f\left(  A\right)
\subseteq C$), then the resulting map $\overline{f}:A\rightarrow C$ is
surjective. Combining the preceding two statements, we conclude that if
$f:A\rightarrow B$ is an injective map whose image is $C$, then the resulting
map $\overline{f}:A\rightarrow C$ is bijective. Thus, we obtain a mapping
\begin{align*}
\left\{  \text{injective maps }f:A\rightarrow B\text{ whose image is
}C\right\}   &  \rightarrow\left\{  \text{bijective maps from }A\text{ to
}C\right\}  ,\\
f  &  \mapsto\overline{f}.
\end{align*}
This mapping is easily seen to be itself bijective (indeed, for each bijective
map $g$ from $A$ to $C$, there is a \textbf{unique} map $f:A\rightarrow B$
whose image is $C$ such that $\overline{f}=g$: namely, this $f$ is just $g$
with the target switched to $B$). Hence, we have found a bijection between the
sets $\left\{  \text{injective maps }f:A\rightarrow B\text{ whose image is
}C\right\}  $ and $\left\{  \text{bijective maps from }A\text{ to }C\right\}
$. Thus,%
\begin{align}
&  \left\vert \left\{  \text{injective maps }f:A\rightarrow B\text{ whose
image is }C\right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  \text{bijective maps from }A\text{ to }C\right\}
\right\vert . \label{pf.prop.count.ABC-injs.1}%
\end{align}


On the other hand, there exists a bijection $\phi:C\rightarrow A$ (since
$\left\vert C\right\vert =\left\vert A\right\vert $). Fix such a $\phi$. Then,
there is a bijection%
\begin{align*}
\left\{  \text{bijective maps from }A\text{ to }C\right\}   &  \rightarrow
\left\{  \text{bijective maps from }A\text{ to }A\right\}  ,\\
g  &  \mapsto\phi\circ g
\end{align*}
(its inverse is given by $g\mapsto\phi^{-1}\circ g$). Hence,%
\begin{align*}
\left\vert \left\{  \text{bijective maps from }A\text{ to }C\right\}
\right\vert  &  =\left\vert \left\{  \text{bijective maps from }A\text{ to
}A\right\}  \right\vert \\
&  =\left\vert \left\{  \text{permutations of }A\right\}  \right\vert \\
&  =\left(  \text{the number of permutations of }A\right) \\
&  =\left\vert A\right\vert !.
\end{align*}
Thus, (\ref{pf.prop.count.ABC-injs.1}) becomes%
\begin{align*}
&  \left\vert \left\{  \text{injective maps }f:A\rightarrow B\text{ whose
image is }C\right\}  \right\vert \\
&  =\left\vert \left\{  \text{bijective maps from }A\text{ to }C\right\}
\right\vert =\left\vert A\right\vert !.
\end{align*}
In other words, the number of injective maps $f:A\rightarrow B$ whose image is
$C$ is $\left\vert A\right\vert !$. This proves Proposition
\ref{prop.count.ABC-injs} \textbf{(a)}.

\textbf{(b)} The maps $f:A\rightarrow B$ satisfying $C\subseteq f\left(
A\right)  $ are the same as the maps $f:A\rightarrow B$ satisfying $C=f\left(
A\right)  $ (because the inequality $\left\vert C\right\vert =\left\vert
A\right\vert \geq\left\vert f\left(  A\right)  \right\vert $ shows that $C$
cannot be a \textbf{proper} subset of $f\left(  A\right)  $). Furthermore, all
these maps are necessarily injective (because if such a map $f:A\rightarrow B$
was not injective, then it would satisfy $\left\vert f\left(  A\right)
\right\vert <\left\vert A\right\vert =\left\vert C\right\vert $, which would
contradict the condition $C=f\left(  A\right)  $). Hence, the maps
$f:A\rightarrow B$ satisfying $C\subseteq f\left(  A\right)  $ are precisely
the injective maps $f:A\rightarrow B$ whose image is $C$. Thus, Proposition
\ref{prop.count.ABC-injs} \textbf{(b)} follows immediately from Proposition
\ref{prop.count.ABC-injs} \textbf{(a)}.

\textbf{(c)} If an injective map $f:A\rightarrow B$ satisfies $f\left(
A\right)  \subseteq C$, then it must also satisfy $f\left(  A\right)  =C$
(because the injectivity of $f$ yields $\left\vert f\left(  A\right)
\right\vert =\left\vert A\right\vert =\left\vert C\right\vert $, so that
$f\left(  A\right)  $ cannot be a \textbf{proper} subset of $C$). In other
words, if an injective map $f:A\rightarrow B$ satisfies $f\left(  A\right)
\subseteq C$, then its image must be $C$. Thus, the injective maps
$f:A\rightarrow B$ satisfying $f\left(  A\right)  \subseteq C$ are the same as
the injective maps $f:A\rightarrow B$ whose image is $C$. Hence, Proposition
\ref{prop.count.ABC-injs} \textbf{(c)} follows immediately from Proposition
\ref{prop.count.ABC-injs} \textbf{(a)}.
\end{proof}

\begin{proof}
[Proof of Theorem \ref{thm.DIE.count-surjs.d-gen} (sketched).]Let us forget
that $b$ is fixed. Thus, $a$ is fixed, but $b$ is not. We must prove that
(\ref{eq.thm.DIE.count-surjs.d-gen.eq}) holds for each $b\in\mathbb{Q}$.

We now claim that for every \textbf{integer} $b\geq a$, the equality
(\ref{eq.thm.DIE.count-surjs.d-gen.eq}) holds.

[\textit{Proof:} Let $b\geq a$ be an integer. Let $A=\left[  a\right]  $,
$B=\left[  b\right]  $ and $C=\left[  a\right]  $. Then, $C\subseteq B$ (since
$a\leq b$). Also, clearly, $a=\left\vert A\right\vert $ and $b=\left\vert
B\right\vert $ and $a=\left\vert C\right\vert $. Hence, $\left\vert
C\right\vert =a=\left\vert A\right\vert $.

Thus, Proposition \ref{prop.count.ABC-injs} \textbf{(b)} yields that the
number of maps $f:A\rightarrow B$ satisfying $C\subseteq f\left(  A\right)  $
is $\left\vert A\right\vert !=a!$ (since $\left\vert A\right\vert =a$).

On the other hand, Exercise \ref{exe.DIE.count-surjs} \textbf{(a)} (applied to
$c=a$) yields that this number is%
\[
\sum_{k=0}^{a}\left(  -1\right)  ^{k}\dbinom{a}{k}\left(  b-k\right)  ^{a}.
\]
Comparing these two results, we conclude that $\sum_{k=0}^{a}\left(
-1\right)  ^{k}\dbinom{a}{k}\left(  b-k\right)  ^{a}=a!$. In other words, the
equality (\ref{eq.thm.DIE.count-surjs.d-gen.eq}) holds. Qed.]

So we have shown that for every \textbf{integer} $b\geq a$, the equality
(\ref{eq.thm.DIE.count-surjs.d-gen.eq}) holds. In other words, every integer
$b\geq a$ is a root of the polynomial $\sum_{k=0}^{a}\left(  -1\right)
^{k}\dbinom{a}{k}\left(  x-k\right)  ^{a}-a!$ (in the indeterminate $x$).
Thus, this polynomial has infinitely many roots (because there are infinitely
many integers $b\geq a$). Thus, Lemma \ref{lem.pi-trick.c} shows that this
polynomial is the zero polynomial. In other words,%
\begin{equation}
\sum_{k=0}^{a}\left(  -1\right)  ^{k}\dbinom{a}{k}\left(  x-k\right)
^{a}-a!=0. \label{pf.lem.pi-trick.d.almost}%
\end{equation}
Now, for any $b\in\mathbb{Q}$, we can substitute $b$ for $x$ in the identity
(\ref{pf.lem.pi-trick.d.almost}), and we obtain $\sum_{k=0}^{a}\left(
-1\right)  ^{k}\dbinom{a}{k}\left(  b-k\right)  ^{a}-a!=0$. This is clearly
equivalent to (\ref{eq.thm.DIE.count-surjs.d-gen.eq}). This proves Theorem
\ref{thm.DIE.count-surjs.d-gen}.
\end{proof}

With Theorem \ref{thm.DIE.count-surjs.d-gen} proven, Exercise
\ref{exe.DIE.count-surjs} \textbf{(d)} immediately follows.

\subsection{Multijections, set compositions and set partitions}

\subsubsection{Definitions and examples}

Let us introduce set partitions and set compositions. These are important
concepts in combinatorics, and we will see more of them.

\begin{definition}
\label{def.setpart}Let $X$ be a finite set.

\textbf{(a)} A \textit{set composition} of $X$ means a tuple $\left(
S_{1},S_{2},\ldots,S_{k}\right)  $ of disjoint nonempty subsets of $X$ such
that $X=S_{1}\cup S_{2}\cup\cdots\cup S_{k}$.

\textbf{(b)} A \textit{set partition} of $X$ means a set $\left\{  S_{1}%
,S_{2},\ldots,S_{k}\right\}  $ of disjoint nonempty subsets of $X$ (written in
such a way that $S_{1},S_{2},\ldots,S_{k}$ are distinct) such that
$X=S_{1}\cup S_{2}\cup\cdots\cup S_{k}$.

\textbf{(c)} The \textit{parts} of a set composition $\left(  S_{1}%
,S_{2},\ldots,S_{k}\right)  $ are the sets $S_{1},S_{2},\ldots,S_{k}$.

\textbf{(d)} The \textit{parts} of a set partition $\left\{  S_{1}%
,S_{2},\ldots,S_{k}\right\}  $ are the sets $S_{1},S_{2},\ldots,S_{k}$.
\end{definition}

\begin{example}
For this example, let $X=\left\{  1,2,3\right\}  $.

\textbf{(a)} The $2$-tuple $\left(  \left\{  1,3\right\}  ,\left\{  2\right\}
\right)  $ is a set composition of $X$, since $\left\{  1,3\right\}  $ and
$\left\{  2\right\}  $ are disjoint nonempty subsets of $X$ satisfying
$X=\left\{  1,3\right\}  \cup\left\{  2\right\}  $.

\textbf{(b)} The $2$-tuple $\left(  \left\{  1,3\right\}  ,\left\{
2,3\right\}  \right)  $ is \textbf{not} a set composition of $X$, since
$\left\{  1,3\right\}  $ and $\left\{  2,3\right\}  $ are not disjoint.

\textbf{(c)} The $3$-tuple $\left(  \left\{  1,3\right\}  ,\left\{
{}\right\}  ,\left\{  2\right\}  \right)  $ is \textbf{not} a set composition
of $X$, since $\left\{  {}\right\}  $ is not nonempty.

\textbf{(d)} The $2$-tuple $\left(  \left\{  1\right\}  ,\left\{  3\right\}
\right)  $ is \textbf{not} a set composition of $X$, since $X\neq\left\{
1\right\}  \cup\left\{  3\right\}  $.

\textbf{(e)} The set $\left\{  \left\{  1,3\right\}  ,\left\{  2\right\}
\right\}  $ is a set partition of $X$, since $\left\{  1,3\right\}  $ and
$\left\{  2\right\}  $ are disjoint nonempty subsets of $X$ satisfying
$X=\left\{  1,3\right\}  \cup\left\{  2\right\}  $.

\textbf{(f)} If $\left(  S_{1},S_{2},\ldots,S_{k}\right)  $ is a set
composition of $X$, then $\left\{  S_{1},S_{2},\ldots,S_{k}\right\}  $ is a
set partition of $X$. The converse also holds if you assume $S_{1}%
,S_{2},\ldots,S_{k}$ to be distinct.

\textbf{(g)} The set \textbf{compositions} $\left(  \left\{  1,3\right\}
,\left\{  2\right\}  \right)  $ and $\left(  \left\{  2\right\}  ,\left\{
1,3\right\}  \right)  $ of $X$ are distinct, but the set \textbf{partitions}
$\left\{  \left\{  1,3\right\}  ,\left\{  2\right\}  \right\}  $ and $\left\{
\left\{  2\right\}  ,\left\{  1,3\right\}  \right\}  $ are identical.
\end{example}

This illustrates the difference between set compositions and set partitions:
The former come with an ordering of their parts, while the latter don't. This
is why set compositions are often called \textit{ordered set partitions}.

\begin{example}
\label{exa.set-partitions.ab}\textbf{(a)} Here are all set compositions of the
set $X=\left\{  1,2,3\right\}  $:
\begin{align*}
&  \left(  \left\{  1,2,3\right\}  \right)  ,\\
&  \left(  \left\{  1,2\right\}  ,\left\{  3\right\}  \right)
,\ \ \ \ \ \ \ \ \ \ \left(  \left\{  1,3\right\}  ,\left\{  2\right\}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(  \left\{  2,3\right\}  ,\left\{
1\right\}  \right)  ,\\
&  \left(  \left\{  1\right\}  ,\left\{  2,3\right\}  \right)
,\ \ \ \ \ \ \ \ \ \ \left(  \left\{  2\right\}  ,\left\{  1,3\right\}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(  \left\{  3\right\}  ,\left\{
1,2\right\}  \right)  ,\\
&  \left(  \left\{  1\right\}  ,\left\{  2\right\}  ,\left\{  3\right\}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(  \left\{  1\right\}  ,\left\{  3\right\}
,\left\{  2\right\}  \right)  ,\ \ \ \ \ \ \ \ \ \ \left(  \left\{  2\right\}
,\left\{  1\right\}  ,\left\{  3\right\}  \right)  ,\\
&  \left(  \left\{  2\right\}  ,\left\{  3\right\}  ,\left\{  1\right\}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(  \left\{  3\right\}  ,\left\{  1\right\}
,\left\{  2\right\}  \right)  ,\ \ \ \ \ \ \ \ \ \ \left(  \left\{  3\right\}
,\left\{  2\right\}  ,\left\{  1\right\}  \right)  .
\end{align*}
And here are the same set compositions, drawn as pictures (each part of the
set composition corresponds to a colored blob):%
\[%
\begin{array}
[c]{c|c|c|c}%
\begin{tikzpicture} \draw[fill=green!50] (0.7, 0.5) ellipse (1.3 and 1.3); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
&  & \\\hline
\begin{tikzpicture} \draw[fill=green!50] (0.75, 0) ellipse (1.4 and .5); \draw[fill=red!50] (0.8, 1.3) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw[fill=green!50, rotate=-30] (0, 0.6) ellipse (.5 and 1.4); \draw[fill=red!50] (1.5, 0) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw[fill=green!50, rotate=30] (1.3, -0.1) ellipse (.5 and 1.4); \draw[fill=red!50] (0, 0) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\\\hline
\begin{tikzpicture} \draw[fill=red!50, rotate=30] (1.3, -0.1) ellipse (.5 and 1.4); \draw[fill=green!50] (0, 0) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw[fill=red!50, rotate=-30] (0, 0.6) ellipse (.5 and 1.4); \draw[fill=green!50] (1.5, 0) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw[fill=red!50] (0.75, 0) ellipse (1.4 and .5); \draw[fill=green!50] (0.8, 1.3) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\\\hline
\begin{tikzpicture} \draw[fill=green!50] (0, 0) ellipse (0.5 and 0.5); \draw[fill=red!50] (1.5, 0) ellipse (0.5 and 0.5); \draw[fill=yellow!50] (0.75, 1.3) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw[fill=green!50] (0, 0) ellipse (0.5 and 0.5); \draw[fill=yellow!50] (1.5, 0) ellipse (0.5 and 0.5); \draw[fill=red!50] (0.75, 1.3) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw[fill=red!50] (0, 0) ellipse (0.5 and 0.5); \draw[fill=green!50] (1.5, 0) ellipse (0.5 and 0.5); \draw[fill=yellow!50] (0.75, 1.3) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\\\hline
\begin{tikzpicture} \draw[fill=yellow!50] (0, 0) ellipse (0.5 and 0.5); \draw[fill=green!50] (1.5, 0) ellipse (0.5 and 0.5); \draw[fill=red!50] (0.75, 1.3) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw[fill=red!50] (0, 0) ellipse (0.5 and 0.5); \draw[fill=yellow!50] (1.5, 0) ellipse (0.5 and 0.5); \draw[fill=green!50] (0.75, 1.3) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw[fill=yellow!50] (0, 0) ellipse (0.5 and 0.5); \draw[fill=red!50] (1.5, 0) ellipse (0.5 and 0.5); \draw[fill=green!50] (0.75, 1.3) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\end{array}
\]
Here, the colors have been chosen as follows: The green-colored blob is the
first part of the set composition; the red-colored blob is the second; the
yellow-colored blob is the third.

\textbf{(b)} Here are all set partitions of the set $X=\left\{  1,2,3\right\}
$:
\begin{align*}
&  \left\{  \left\{  1,2,3\right\}  \right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{
\left\{  1,2\right\}  ,\left\{  3\right\}  \right\}
,\ \ \ \ \ \ \ \ \ \ \left\{  \left\{  1,3\right\}  ,\left\{  2\right\}
\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{  \left\{  2,3\right\}  ,\left\{
1\right\}  \right\}  ,\\
&  \left\{  \left\{  1\right\}  ,\left\{  2\right\}  ,\left\{  3\right\}
\right\}  .
\end{align*}
And here are the same set partitions, drawn as pictures (each part of the set
partition corresponds to a blob):%
\[%
\begin{array}
[c]{c|c|c|c|c}%
\begin{tikzpicture} \draw (0.7, 0.5) ellipse (1.3 and 1.3); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw (0.75, 0) ellipse (1.4 and .5); \draw (0.8, 1.3) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw[rotate=-30] (0, 0.6) ellipse (.5 and 1.4); \draw (1.5, 0) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw[rotate=30] (1.3, -0.1) ellipse (.5 and 1.4); \draw (0, 0) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture} &
\begin{tikzpicture} \draw (0, 0) ellipse (0.5 and 0.5); \draw (1.5, 0) ellipse (0.5 and 0.5); \draw (0.75, 1.3) ellipse (0.5 and 0.5); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at +(0: 1.5) {2}; \node (c) at +(60: 1.5) {3}; \end{tikzpicture}
\end{array}
\]

\end{example}

\begin{definition}
Let $X$ be a set. Let $k\in\mathbb{N}$.

\textbf{(a)} A \textit{set composition of }$X$ \textit{into }$k$
\textit{parts} is a set composition of $X$ having exactly $k$ parts.

\textbf{(b)} A \textit{set partition of }$X$ \textit{into }$k$ \textit{parts}
is a set partition of $X$ having exactly $k$ parts.
\end{definition}

For example, $\left(  \left\{  1,5\right\}  ,\left\{  2\right\}  ,\left\{
3,4,6,7\right\}  \right)  $ is a set composition of $\left[  7\right]  $ into
$3$ parts.

\subsubsection{Counting set partitions and set compositions}

There are several natural things to be counted now:

\begin{itemize}
\item set compositions of a given set $X$;

\item set partitions of a given set $X$;

\item set compositions of a given set $X$ into $k$ parts for a given
$k\in\mathbb{N}$;

\item set partitions of a given set $X$ into $k$ parts for a given
$k\in\mathbb{N}$.
\end{itemize}

Let's only briefly comment on the first two questions, and then discuss the
last two.

\begin{fns}
\begin{itemize}
\item If $X$ is an $n$-element set, then the number of set compositions of $X$
is the $n$-th
\textit{\href{https://en.wikipedia.org/wiki/Ordered_Bell_number}{\textit{ordered
Bell number}}} $\widetilde{B}\left(  n\right)  $. Here is a list of the first
values of $\widetilde{B}\left(  n\right)  $ (see
\href{https://oeis.org/A000670}{A000670 at OEIS} for more):%
\begin{align*}
\widetilde{B}\left(  0\right)   &  =1,\ \ \ \ \ \ \ \ \ \ \widetilde{B}\left(
1\right)  =1,\ \ \ \ \ \ \ \ \ \ \widetilde{B}\left(  2\right)
=3,\ \ \ \ \ \ \ \ \ \ \widetilde{B}\left(  3\right)  =13,\\
\widetilde{B}\left(  4\right)   &  =75,\ \ \ \ \ \ \ \ \ \ \widetilde{B}%
\left(  5\right)  =541,\ \ \ \ \ \ \ \ \ \ \widetilde{B}\left(  6\right)
=4683,\ \ \ \ \ \ \ \ \ \ \widetilde{B}\left(  7\right)  =47293.
\end{align*}
No explicit formulas for $\widetilde{B}\left(  n\right)  $ are known. A quick
way to compute $\widetilde{B}\left(  n\right)  $ for arbitrary $n\in
\mathbb{N}$ is using the recursive equation%
\[
\widetilde{B}\left(  n\right)  =\sum_{i=0}^{n-1}\dbinom{n}{i}\widetilde{B}%
\left(  i\right)  \ \ \ \ \ \ \ \ \ \ \text{for all }n>0.
\]
(The proof is easy: Classify all set compositions of $\left[  n\right]  $
according to the size of their last part, and treat all the remaining parts as
a set composition of a smaller set.)

\item If $X$ is an $n$-element set, then the number of set partitions of $X$
is the $n$-th
\textit{\href{https://en.wikipedia.org/wiki/Bell_number}{\textit{Bell number}%
}} $B\left(  n\right)  $. Here is a list of the first values of $B\left(
n\right)  $ (see \href{https://oeis.org/A000110}{A000110 at OEIS} for more):%
\begin{align*}
B\left(  0\right)   &  =1,\ \ \ \ \ \ \ \ \ \ B\left(  1\right)
=1,\ \ \ \ \ \ \ \ \ \ B\left(  2\right)  =2,\ \ \ \ \ \ \ \ \ \ B\left(
3\right)  =5,\\
B\left(  4\right)   &  =15,\ \ \ \ \ \ \ \ \ \ B\left(  5\right)
=52,\ \ \ \ \ \ \ \ \ \ B\left(  6\right)  =203,\ \ \ \ \ \ \ \ \ \ B\left(
7\right)  =877.
\end{align*}
No explicit formulas for $B\left(  n\right)  $ are known. A quick way to
compute $B\left(  n\right)  $ for arbitrary $n\in\mathbb{N}$ is using the
recursive equation%
\[
B\left(  n+1\right)  =\sum_{i=0}^{n}\dbinom{n}{i}B\left(  i\right)
\ \ \ \ \ \ \ \ \ \ \text{for all }n\in\mathbb{N}.
\]
(The proof is easy: Classify all set partitions of $\left[  n+1\right]  $
according to how many elements lie in the same part as $n+1$, and treat all
the remaining parts as a set partition of a smaller set.)
\end{itemize}
\end{fns}

Now, let us study the other two questions.

\begin{definition}
Let $X$ be a set. Let $k\in\mathbb{N}$.

\textbf{(a)} We let $\operatorname*{SC}\nolimits_{k}\left(  X\right)  $ denote
the set of all set compositions of $X$ into $k$ parts.

\textbf{(b)} We let $\operatorname*{SP}\nolimits_{k}\left(  X\right)  $ denote
the set of all set partitions of $X$ into $k$ parts.
\end{definition}

\begin{proposition}
\label{prop.set-compositions.sur}Let $X$ be a finite set. Let $k\in\mathbb{N}%
$. Then, $\left\vert \operatorname*{SC}\nolimits_{k}\left(  X\right)
\right\vert =\operatorname*{sur}\left(  \left\vert X\right\vert ,k\right)  $.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.set-compositions.sur} (sketched).]For any sets
$A$ and $B$, we let $\operatorname*{Sur}\left(  A,B\right)  $ be the set of
all surjections from $A$ to $B$. If $A$ and $B$ are finite sets, then
\[
\left\vert \operatorname*{Sur}\left(  A,B\right)  \right\vert =\left(
\text{the number of surjections from }A\text{ to }B\right)
=\operatorname*{sur}\left(  \left\vert A\right\vert ,\left\vert B\right\vert
\right)
\]
(as we have shown in class). Applying this to $A=X$ and $B=\left[  k\right]
$, we obtain%
\[
\left\vert \operatorname*{Sur}\left(  X,\left[  k\right]  \right)  \right\vert
=\operatorname*{sur}\left(  \left\vert X\right\vert ,\underbrace{\left\vert
\left[  k\right]  \right\vert }_{=k}\right)  =\operatorname*{sur}\left(
\left\vert X\right\vert ,k\right)  .
\]


Here is an outline of the remainder of the proof: We want to find $\left\vert
\operatorname*{SC}\nolimits_{k}\left(  X\right)  \right\vert $; that is, we
want to count all set compositions $\left(  S_{1},S_{2},\ldots,S_{k}\right)  $
of $X$ into $k$ parts. We can construct such a set composition by choosing,
for each $x\in X$, which part $S_{i}$ it shall belong to\footnote{Each $x\in
X$ must belong to \textbf{exactly one} part of $\left(  S_{1},S_{2}%
,\ldots,S_{k}\right)  $ (because $\left(  S_{1},S_{2},\ldots,S_{k}\right)  $
is a set composition of $X$).}. This information can be encoded as a map
$f:X\rightarrow\left[  k\right]  $ (which sends each $x\in X$ to the
$i\in\left[  k\right]  $ satisfying $x\in S_{i}$); this map $f$ has to be
surjective (since the parts $S_{i}$ should be nonempty, so each $S_{i}$ must
have at least one $x\in X$ in it), but otherwise is subject to no constraints.
Hence, the number of set compositions $\left(  S_{1},S_{2},\ldots
,S_{k}\right)  $ of $X$ into $k$ parts equals the number of surjective maps
$X\rightarrow\left[  k\right]  $; in other words, it equals $\left\vert
\operatorname*{Sur}\left(  X,\left[  k\right]  \right)  \right\vert
=\operatorname*{sur}\left(  \left\vert X\right\vert ,k\right)  $. This proves
Proposition \ref{prop.set-compositions.sur}.

\begin{fns}
Here is a more rigorous way to make this argument (without vague terms such as
\textquotedblleft information\textquotedblright\ and \textquotedblleft
encoded\textquotedblright). We are going to construct a bijection
$\operatorname*{SC}\nolimits_{k}\left(  X\right)  \rightarrow
\operatorname*{Sur}\left(  X,\left[  k\right]  \right)  $ (that is, a
bijection between the set compositions of $X$ into $k$ parts and the
surjections from $X$ to $\left[  k\right]  $). Here is how:

\begin{itemize}
\item We define a map $\Phi:\operatorname*{SC}\nolimits_{k}\left(  X\right)
\rightarrow\operatorname*{Sur}\left(  X,\left[  k\right]  \right)  $ to be the
map that sends any set composition $\left(  S_{1},S_{2},\ldots,S_{k}\right)
\in\operatorname*{SC}\nolimits_{k}\left(  X\right)  $ to the map%
\begin{align*}
f:X  &  \rightarrow\left[  k\right]  ,\\
x  &  \mapsto\left(  \text{the unique }i\in\left[  k\right]  \text{ such that
}x\in S_{i}\right)  .
\end{align*}
It is easy to see that $\Phi$ is well-defined (indeed, for any set composition
$\left(  S_{1},S_{2},\ldots,S_{k}\right)  $, the resulting map $f:X\rightarrow
\left[  k\right]  $ is surjective, because the sets $S_{1},S_{2},\ldots,S_{k}$
are nonempty).

\item We define a map $\Psi:\operatorname*{Sur}\left(  X,\left[  k\right]
\right)  \rightarrow\operatorname*{SC}\nolimits_{k}\left(  X\right)  $ to be
the map that sends any surjective map $f:X\rightarrow\left[  k\right]  $ to
the set composition $\left(  S_{1},S_{2},\ldots,S_{k}\right)  \in
\operatorname*{SC}\nolimits_{k}\left(  X\right)  $, where%
\[
S_{i}=f^{-1}\left(  \left\{  i\right\}  \right)  =\left\{  x\in X\ \mid
\ f\left(  x\right)  =i\right\}  \ \ \ \ \ \ \ \ \ \ \text{for each }%
i\in\left[  k\right]  .
\]
Again, it is easily shown that this map $\Psi$ is well-defined.
\end{itemize}

It is easy to check that the maps $\Phi$ and $\Psi$ are mutually inverse, and
thus are bijections. Hence, we have found a bijection $\operatorname*{SC}%
\nolimits_{k}\left(  X\right)  \rightarrow\operatorname*{Sur}\left(  X,\left[
k\right]  \right)  $. This lets us conclude that%
\[
\left\vert \operatorname*{SC}\nolimits_{k}\left(  X\right)  \right\vert
=\left\vert \operatorname*{Sur}\left(  X,\left[  k\right]  \right)
\right\vert =\operatorname*{sur}\left(  \left\vert X\right\vert ,k\right)  .
\]
Thus, Proposition \ref{prop.set-compositions.sur} is proven.
\end{fns}
\end{proof}

Next, let us count set partitions of a given finite set $X$ into a given
number of parts:

\begin{proposition}
\label{prop.set-partitions.sur}Let $X$ be a finite set. Let $k\in\mathbb{N}$.
Then, $\left\vert \operatorname*{SP}\nolimits_{k}\left(  X\right)  \right\vert
=\dfrac{\operatorname*{sur}\left(  \left\vert X\right\vert ,k\right)  }{k!}$.
\end{proposition}

Let us give an informal proof of this proposition. A formalization of it
(omitting only really straightforward details) is given in the Appendix below.

\begin{proof}
[Outline of an informal proof of Proposition \ref{prop.set-partitions.sur}%
.]Let us count the set compositions \newline$\left(  S_{1},S_{2},\ldots
,S_{k}\right)  $ of $X$ into $k$ parts in two different ways:

\begin{itemize}
\item On the one hand, this number is $\left\vert \operatorname*{SC}%
\nolimits_{k}\left(  X\right)  \right\vert =\operatorname*{sur}\left(
\left\vert X\right\vert ,k\right)  $ (by Proposition
\ref{prop.set-compositions.sur}).

\item On the other hand, we can construct a set composition $\left(
S_{1},S_{2},\ldots,S_{k}\right)  $ of $X$ into $k$ parts by first choosing a
set partition of $X$ into $k$ parts (there are $\left\vert \operatorname*{SP}%
\nolimits_{k}\left(  X\right)  \right\vert $ ways to do this), and then
choosing how to order it\footnote{i.e., in what order to list its parts}
(there are $k!$ ways to do this, since it has $k$ distinct parts). Thus, the
number of set compositions $\left(  S_{1},S_{2},\ldots,S_{k}\right)  $ of $X$
into $k$ parts equals $\left\vert \operatorname*{SP}\nolimits_{k}\left(
X\right)  \right\vert \cdot k!$.
\end{itemize}

Comparing these two results, we conclude that $\operatorname*{sur}\left(
\left\vert X\right\vert ,k\right)  =\left\vert \operatorname*{SP}%
\nolimits_{k}\left(  X\right)  \right\vert \cdot k!$. Thus, $\dfrac
{\operatorname*{sur}\left(  \left\vert X\right\vert ,k\right)  }%
{k!}=\left\vert \operatorname*{SP}\nolimits_{k}\left(  X\right)  \right\vert
$. This proves Proposition \ref{prop.set-partitions.sur}.
\end{proof}

The above proof outline glances over technicalities such as what
\textquotedblleft ordering\textquotedblright\ a set partition means, and why
there are $k!$ ways to do this; this is the reason why I am calling it
informal and give a more complete version in the Appendix below.

The method we used to prove Proposition \ref{prop.set-partitions.sur} is
another example of the \textquotedblleft shepherd's
principle\textquotedblright\ (\textquotedblleft To count sheep, you count the
legs and then you divide by $4$\textquotedblright). Our sheep here were the
set partitions in $\operatorname*{SP}\nolimits_{k}\left(  X\right)  $, whereas
their legs were the set compositions in $\operatorname*{SC}\nolimits_{k}%
\left(  X\right)  $. A leg $\left(  S_{1},S_{2},\ldots,S_{k}\right)
\in\operatorname*{SC}\nolimits_{k}\left(  X\right)  $ belongs to the sheep
$\left\{  S_{1},S_{2},\ldots,S_{k}\right\}  \in\operatorname*{SP}%
\nolimits_{k}\left(  X\right)  $. This principle (also known as
\textquotedblleft proof by multijection\textquotedblright) is useful whenever
the legs are easier to count than the sheep. (For example, in the above case,
the legs were in bijection with the surjections $X\rightarrow\left[  k\right]
$, whereas the sheep were not in a visible bijection with anything.)

\begin{fns}
\begin{definition}
Let $n\in\mathbb{N}$ and $k\in\mathbb{N}$. The $\left(  n,k\right)
$\textit{-th
\href{https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind}{\textit{Stirling
number of the 2nd kind}}} is defined to be $\dfrac{\operatorname*{sur}\left(
n,k\right)  }{k!}$; it is commonly denoted by $%
%TCIMACRO{\QDATOPD{\{}{\}}{n}{k}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{n}{k}%
%EndExpansion
$ or by $S\left(  n,k\right)  $.

Proposition \ref{prop.set-partitions.sur} shows that $%
%TCIMACRO{\QDATOPD{\{}{\}}{n}{k}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{n}{k}%
%EndExpansion
$ is the number of set partitions of a given $n$-element set into $k$ parts.
Thus, in particular, $%
%TCIMACRO{\QDATOPD{\{}{\}}{n}{k}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{n}{k}%
%EndExpansion
$ is a nonnegative integer.

The recurrence relation $\operatorname*{sur}\left(  n,k\right)  =k\cdot\left(
\operatorname*{sur}\left(  n-1,k\right)  +\operatorname*{sur}\left(
n-1,k-1\right)  \right)  $ for arbitrary $n>0$ and $k>0$ (see, for example,
Proposition 3.12 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018feb21.pdf}{classwork
from 21 February 2018}) now leads to the following recurrence relations for
Stirling numbers of the 2nd kind:%
\[%
%TCIMACRO{\QDATOPD{\{}{\}}{n}{k}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{n}{k}%
%EndExpansion
=k%
%TCIMACRO{\QDATOPD{\{}{\}}{n-1}{k}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{n-1}{k}%
%EndExpansion
+%
%TCIMACRO{\QDATOPD{\{}{\}}{n-1}{k-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{n-1}{k-1}%
%EndExpansion
.
\]
Meanwhile, Exercise \ref{exe.DIE.count-surjs} \textbf{(b)} leads to%
\[%
%TCIMACRO{\QDATOPD{\{}{\}}{a}{b}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{a}{b}%
%EndExpansion
=\dfrac{1}{b!}\sum_{k=0}^{b}\left(  -1\right)  ^{b-k}\dbinom{b}{k}k^{a}.
\]
Without knowing about set partitions, would you have guessed that the right
hand side is a nonnegative integer?
\end{definition}
\end{fns}

Now, I want you to count a special kind of set partitions:

\begin{definition}
A \textit{perfect matching} of a set $X$ means a set partition $\mathbf{P}$ of
$X$ such that each part of $\mathbf{P}$ has size $2$.
\end{definition}

\begin{example}
\textbf{(a)} The perfect matchings of the set $\left[  4\right]  $ are%
\[
\left\{  \left\{  1,2\right\}  ,\left\{  3,4\right\}  \right\}
,\ \ \ \ \ \ \ \ \ \ \left\{  \left\{  1,3\right\}  ,\left\{  2,4\right\}
\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{  \left\{  1,4\right\}  ,\left\{
2,3\right\}  \right\}  .
\]
Here are the same $3$ perfect matchings, drawn as blobs:%
\[%
\begin{array}
[c]{c|c|c}%
\begin{tikzpicture} \draw (0, 1) ellipse (0.7 and 1.9); \draw (2, 1) ellipse (0.7 and 1.9); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at (0, 2) {2}; \node (c) at (2, 2) {3}; \node (d) at (2, 0) {4}; \end{tikzpicture} &
\begin{tikzpicture} \draw[rotate=45] (1.3, 0) ellipse (2.1 and 0.7); \draw[rotate=-45] (0, 1.3) ellipse (2.1 and 0.7); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at (0, 2) {2}; \node (c) at (2, 2) {3}; \node (d) at (2, 0) {4}; \end{tikzpicture} &
\begin{tikzpicture} \draw (1, 0) ellipse (1.9 and 0.7); \draw (1, 2) ellipse (1.9 and 0.7); \tikzstyle{every node} = [circle] \node (a) at (0, 0) {1}; \node (b) at (0, 2) {2}; \node (c) at (2, 2) {3}; \node (d) at (2, 0) {4}; \end{tikzpicture}
\end{array}
\]


\textbf{(b)} The set $\left[  6\right]  $ has $15$ perfect matchings; three of
them are%
\[
\left\{  \left\{  1,2\right\}  ,\left\{  3,4\right\}  ,\left\{  5,6\right\}
\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{  \left\{  1,4\right\}  ,\left\{
2,6\right\}  ,\left\{  3,5\right\}  \right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{
\left\{  1,6\right\}  ,\left\{  2,5\right\}  ,\left\{  3,4\right\}  \right\}
.
\]

\end{example}

Clearly, a perfect matching of a finite set $X$ must have precisely
$\left\vert X\right\vert /2$ parts (since $\left\vert X\right\vert $ is the
sum of the sizes of all parts, but these sizes all equal $2$). Thus, a perfect
matching of a finite set $X$ can only exist when $\left\vert X\right\vert $ is even.

\begin{definition}
Let $A$ and $B$ be two sets. Let $j\in\mathbb{N}$. A map $f:A\rightarrow B$
will be called $j$\textit{-multijective} if for each $b\in B$, we have%
\[
\left(  \text{the number of }a\in A\text{ satisfying }f\left(  a\right)
=b\right)  =j.
\]

\end{definition}

In the classical picture illustrating a map, a map $f:A\rightarrow B$ is
$j$-multijective if and only if each element of $B$ is hit by exactly $j$ arrows.

For example, a $1$-multijective map is the same as a bijective map (make sure
you understand why).

\begin{fns}
For another example, Proposition \ref{prop.set-partitions.k!} below says that
the map $\pi$ in that proposition is $k!$-multijective.
\end{fns}

\subsubsection{Exercise \ref{exe.set-partitions.pm}: counting perfect
matchings}

\begin{exercise}
\label{exe.set-partitions.pm}Let $n\in\mathbb{N}$. Prove the following:

\textbf{(a)} The number of all $2$-multijective maps from $\left[  2n\right]
$ to $\left[  n\right]  $ is $\dfrac{\left(  2n\right)  !}{2^{n}}$.

\textbf{(b)} The number of all set compositions $\mathbf{C}$ of $\left[
2n\right]  $ such that each part of $\mathbf{C}$ has size $2$ is
$\dfrac{\left(  2n\right)  !}{2^{n}}$.

\textbf{(c)} The number of all perfect matchings of $\left[  2n\right]  $ is
$\dfrac{\left(  2n\right)  !}{2^{n}n!}$.

[\textbf{Hint:} You don't need to imitate the level of detail that is given in
the Appendix.]
\end{exercise}

\begin{proof}
[Solution to Exercise~\ref{exe.set-partitions.pm} (sketched).]\textbf{(a)} A
map $f : \left[  2n \right]  \to\left[  n \right]  $ is $2$-multijective if
and only if for each $i \in\left[  n \right]  $, there are exactly two
elements of $\left[  2n \right]  $ that are mapped to $i$ under $f$. Thus, the
following algorithm lets us construct any $2$-multijective map $f$ from
$\left[  2n \right]  $ to $\left[  n \right]  $:

\begin{itemize}
\item First, decide which two elements of $\left[  2n \right]  $ will be
mapped to $1$ under $f$. There are $\dbinom{2n}{2}$ choices, because we are
picking two distinct elements from the $2n$-element set $\left[  2n \right]  $
(with no regard for order).

\item Then, decide which two elements of $\left[  2n \right]  $ will be mapped
to $2$ under $f$. There are $\dbinom{2n-2}{2}$ choices, because we are picking
two distinct elements from the $2n$-element set $\left[  2n \right]  $ but
allowing none of the $2$ elements chosen before (so we are really picking two
elements from a $2n-2$-element set).

\item Then, decide which two elements of $\left[  2n\right]  $ will be mapped
to $3$ under $f$. There are $\dbinom{2n-4}{2}$ choices, because we are picking
two distinct elements from the $2n$-element set $\left[  2n\right]  $ but
allowing none of the $4$ elements chosen before (so we are really picking two
elements from a $2n-4$-element set).

\item Proceed likewise, until finally deciding which two elements of $\left[
2n \right]  $ will be mapped to $n$.
\end{itemize}

In total, this algorithm can be performed in
\[
\dbinom{2n}{2}\dbinom{2n-2}{2}\dbinom{2n-4}{2}\cdots\dbinom{2n-2\left(
n-1\right)  }{2}=\prod_{i=0}^{n-1}\dbinom{2n-2i}{2}%
\]
many ways. Since this algorithm constructs each $2$-multijective map $f$ from
$\left[  2n\right]  $ to $\left[  n\right]  $ exactly once, we thus conclude
that the number of all $2$-multijective maps from $\left[  2n\right]  $ to
$\left[  n\right]  $ is
\begin{align*}
\prod_{i=0}^{n-1}\dbinom{2n-2i}{2}  &  =\prod_{k=1}^{n}\underbrace{\dbinom
{2k}{2}}_{=\dfrac{\left(  2k-1\right)  \left(  2k\right)  }{2}}\\
&  \qquad\left(  \text{here, we have substituted }k\text{ for }n-i\text{ in
the product}\right) \\
&  =\prod_{k=1}^{n}\dfrac{\left(  2k-1\right)  \left(  2k\right)  }{2}%
=\dfrac{1}{2^{n}}\underbrace{\prod_{k=1}^{n}\left(  \left(  2k-1\right)
\left(  2k\right)  \right)  }_{\substack{=\left(  1\cdot2\right)  \left(
3\cdot4\right)  \cdots\left(  \left(  2n-1\right)  \cdot\left(  2n\right)
\right)  \\=1\cdot2\cdot3\cdot4\cdot\cdots\cdot\left(  2n-1\right)
\cdot\left(  2n\right)  =\left(  2n\right)  !}}\\
&  =\dfrac{1}{2^{n}}\left(  2n\right)  !=\dfrac{\left(  2n\right)  !}{2^{n}}.
\end{align*}
This solves Exercise~\ref{exe.set-partitions.pm} \textbf{(a)}.

Now, let $X$ be the set $\left[  2n\right]  $. A \textit{$2$-block
composition} of $X$ shall mean a set composition $\mathbf{C}$ of $X$ such that
each part of $\mathbf{C}$ has size $2$. Thus, each $2$-block composition of
$X$ has exactly $n$ parts. (Indeed, each part of a $2$-block composition has
size $2$, but the sum of the sizes of all its parts is $\left\vert
X\right\vert =2n$; therefore, the number of parts must be $2n/2=n$.) Thus,
each $2$-block composition of $X$ can be written in the form $\left(
S_{1},S_{2},\ldots,S_{n}\right)  $.

\textbf{(b)} The set compositions $\mathbf{C}$ of $\left[  2n\right]  $ such
that each part of $\mathbf{C}$ has size $2$ are precisely the $2$-block
compositions of $X$ (because this is how we defined the latter). Thus, we must
prove that the number of all $2$-block compositions of $X$ is $\dfrac{\left(
2n\right)  !}{2^{n}}$.

We shall derive this from Exercise~\ref{exe.set-partitions.pm} \textbf{(a)} in
roughly the same way as we proved Proposition \ref{prop.set-compositions.sur}.

For any sets $A$ and $B$, we let $\operatorname*{Mulj}\nolimits_{2}\left(
A,B\right)  $ be the set of all $2$-multijections from $A$ to $B$. Thus,
Exercise~\ref{exe.set-partitions.pm} \textbf{(a)} says that $\left\vert
\operatorname*{Mulj}\nolimits_{2}\left(  \left[  2n\right]  ,\left[  n\right]
\right)  \right\vert =\dfrac{\left(  2n\right)  !}{2^{n}}$.

We want to count all $2$-block compositions $\left(  S_{1},S_{2},\ldots
,S_{n}\right)  $ of $X$. We can construct such a $2$-block composition by
choosing, for each $x\in X$, which part $S_{i}$ it shall belong to, as long as
we ensure that each part $S_{i}$ ends up containing exactly $2$ elements $x\in
X$. This information can be encoded as a map $f:X\rightarrow\left[  n\right]
$ (which sends each $x\in X$ to the $i\in\left[  n\right]  $ satisfying $x\in
S_{i}$); this map $f$ has to be $2$-multijective (because this says precisely
that each part $S_{i}$ contains exactly $2$ elements $x\in X$), but otherwise
is subject to no constraints. Hence, the number of $2$-block compositions
$\left(  S_{1},S_{2},\ldots,S_{n}\right)  $ of $X$ equals the number of
$2$-multijective maps $X\rightarrow\left[  n\right]  $; but this number is
\[
\left\vert \operatorname*{Mulj}\nolimits_{2}\left(  \underbrace{X}_{=\left[
2n\right]  },\left[  n\right]  \right)  \right\vert =\left\vert
\operatorname*{Mulj}\nolimits_{2}\left(  \left[  2n\right]  ,\left[  n\right]
\right)  \right\vert =\dfrac{\left(  2n\right)  !}{2^{n}}.
\]
This solves Exercise~\ref{exe.set-partitions.pm} \textbf{(b)}.

\begin{fns}
If you want to make the above argument more rigorous, you can proceed as in
the proof of Proposition \ref{prop.set-compositions.sur}, namely by
constructing a bijection $\operatorname*{SCTB}\left(  X\right)  \rightarrow
\operatorname*{Mulj}\nolimits_{2}\left(  X,\left[  n\right]  \right)  $, where
$\operatorname*{SCTB}\left(  X\right)  $ denotes the set of all $2$-block
compositions of $X$. This bijection is defined exactly as in the proof of
Proposition \ref{prop.set-compositions.sur} (but with $k$ replaced by $n$, and
other obvious changes).
\end{fns}

\textbf{(c)} This is similar to how we derived Proposition
\ref{prop.set-partitions.sur} from Proposition \ref{prop.set-compositions.sur}
(with the difference that instead of Proposition
\ref{prop.set-compositions.sur}, we now need to use
Exercise~\ref{exe.set-partitions.pm} \textbf{(b)}). Let us just give the
informal outline:

Let $\operatorname*{PM}\left(  X\right)  $ be the set of all perfect matchings
of $X$. Each perfect matching of $X$ has exactly $n$ parts. (Indeed, each part
of a perfect matching has size $2$, but the sum of the sizes of all its parts
is $\left\vert X\right\vert =2n$; therefore, the number of parts must be
$2n/2=n$.)

Recall that each $2$-block composition of $X$ can be written in the form
$\left(  S_{1},S_{2},\ldots,S_{n}\right)  $. Let us count all $2$-block
compositions $\left(  S_{1},S_{2},\ldots,S_{n}\right)  $ of $X$ in two
different ways:

\begin{itemize}
\item On the one hand, this number is $\dfrac{\left(  2n\right)  !}{2^{n}}$
(by Exercise~\ref{exe.set-partitions.pm} \textbf{(b)}).

\item On the other hand, we can construct a $2$-block composition $\left(
S_{1},S_{2},\ldots,S_{n}\right)  $ of $X$ by first choosing a perfect matching
of $X$ (there are $\left\vert \operatorname*{PM}\left(  X\right)  \right\vert
$ ways to do this), and then choosing how to order it (there are $n!$ ways to
do this, since it has $n$ distinct parts). Thus, the number of $2$-block
compositions of $X$ equals $\left\vert \operatorname*{PM}\left(  X\right)
\right\vert \cdot n!$.
\end{itemize}

Comparing these two results, we conclude that $\dfrac{\left(  2n\right)
!}{2^{n}}=\left\vert \operatorname*{PM}\left(  X\right)  \right\vert \cdot
n!$. Thus, $\left\vert \operatorname*{PM}\left(  X\right)  \right\vert
=\dfrac{\left(  2n\right)  !}{2^{n}}/n!=\dfrac{\left(  2n\right)  !}{2^{n}n!}$.

But $\operatorname*{PM}\left(  X\right)  $ is the set of all perfect matchings
of $X=\left[  2n\right]  $. Hence, the number of all perfect matchings of
$\left[  2n\right]  $ is $\left\vert \operatorname*{PM}\left(  X\right)
\right\vert =\dfrac{\left(  2n\right)  !}{2^{n}n!}$. This solves
Exercise~\ref{exe.set-partitions.pm} \textbf{(c)}.
\end{proof}

\subsection{\textquotedblleft Image-injective maps\textquotedblright}

If $S$ is a set, then a map $f:S\rightarrow S$ is said to be
\textit{image-injective}\footnote{This is my terminology; don't expect to see
it in the literature.} if and only if its restriction $f\mid_{f\left(
S\right)  }$ is injective. For example:

\begin{itemize}
\item The map $\left[  4\right]  \rightarrow\left[  4\right]  $ sending
$1,2,3,4$ to $4,1,4,1$ (respectively) is image-injective (since its image is
$\left\{  1,4\right\}  $, and its restriction to $\left\{  1,4\right\}  $ is injective).

\item The map $\left[  6\right]  \rightarrow\left[  6\right]  $ sending
$1,2,3,4,5,6$ to $2,4,4,6,6,2$ (respectively) is image-injective (since its
image is $\left\{  2,4,6\right\}  $, and its restriction to $\left\{
2,4,6\right\}  $ is injective).

\item Any injective map $f:S\rightarrow S$ is image-injective. So is any
constant map (i.e., any map $f:S\rightarrow S$ such that all values of $f$ are equal).

\item The map $\left[  3\right]  \rightarrow\left[  3\right]  $ sending
$1,2,3$ to $2,2,1$ (respectively) is not image-injective (since its
restriction to its image $\left\{  1,2\right\}  $ is not injective).
\end{itemize}

As usual, if $S$ is a set, and $f:S\rightarrow S$ is a map, then $f^{2}$ means
the map $f\circ f:S\rightarrow S$. (More generally, $f^{k}$ means the map
$\underbrace{f\circ f\circ\cdots\circ f}_{k\text{ times}}$ whenever
$k\in\mathbb{N}$.)

\begin{exercise}
\label{exe.count.weakly-injective}Let $n\in\mathbb{N}$.

\textbf{(a)} Prove that a map $f:\left[  n\right]  \rightarrow\left[
n\right]  $ is image-injective if and only if it has the following property:
For any $a\in\left[  n\right]  $ and $b\in\left[  n\right]  $ satisfying
$f^{2}\left(  a\right)  =f^{2}\left(  b\right)  $, we must have $f\left(
a\right)  =f\left(  b\right)  $.

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

\textbf{(c)} Prove that the number of image-injective maps $\left[  n\right]
\rightarrow\left[  n\right]  $ is divisible by $n$ whenever $n$ is positive.

[\textbf{Hint:} This is rather similar to \cite[Exercise 1]{fall2017-hw6os};
feel free to imitate the solution of the latter exercise.]
\end{exercise}

The sequence of integers whose $n$-th term is the number of image-injective
maps $\left[  n\right]  \rightarrow\left[  n\right]  $ appears in the OEIS as
\href{https://oeis.org/A006153}{Sequence A006153}; our definition of it is
exactly what Geoffrey Critzer wrote in his comment. It doesn't seem to have
many properties.

The solution to Exercise \ref{exe.count.weakly-injective} outlined below
imitates \cite[solution to Exercise 1]{fall2017-hw6os}, to the point that
several parts of it are copied more or less verbatim.

\begin{proof}
[Solution to Exercise \ref{exe.count.weakly-injective} (sketched).]%
\textbf{(a)} Let $f:\left[  n\right]  \rightarrow\left[  n\right]  $ be a map.
We must prove that $f$ is image-injective if and only if it has the following
property:%
\begin{equation}
\left(
\begin{array}
[c]{c}%
\text{For any }a\in\left[  n\right]  \text{ and }b\in\left[  n\right]  \text{
satisfying }f^{2}\left(  a\right)  =f^{2}\left(  b\right)  \text{,}\\
\text{we must have }f\left(  a\right)  =f\left(  b\right)
\end{array}
\right)  . \label{sol.count.weakly-injective.ii-prop}%
\end{equation}


$\Longrightarrow:$ Assume that $f$ is image-injective. We must prove that $f$
has the property (\ref{sol.count.weakly-injective.ii-prop}).

The map $f$ is image-injective. In other words, its restriction $f\mid
_{f\left(  \left[  n\right]  \right)  }$ is injective (by the definition of
\textquotedblleft image-injective\textquotedblright).

Let $a\in\left[  n\right]  $ and $b\in\left[  n\right]  $ be such that
$f^{2}\left(  a\right)  =f^{2}\left(  b\right)  $. Both $f\left(  a\right)  $
and $f\left(  b\right)  $ clearly belong to the image $f\left(  \left[
n\right]  \right)  $. Furthermore,%
\[
\left(  f\mid_{f\left(  \left[  n\right]  \right)  }\right)  \left(  f\left(
a\right)  \right)  =f\left(  f\left(  a\right)  \right)  =f^{2}\left(
a\right)  =f^{2}\left(  b\right)  =f\left(  f\left(  b\right)  \right)
=\left(  f\mid_{f\left(  \left[  n\right]  \right)  }\right)  \left(  f\left(
b\right)  \right)  .
\]
Since $f\mid_{f\left(  \left[  n\right]  \right)  }$ is injective, we thus
conclude that $f\left(  a\right)  =f\left(  b\right)  $.

Now, forget that we fixed $a$ and $b$. We thus have proven that for any
$a\in\left[  n\right]  $ and $b\in\left[  n\right]  $ satisfying $f^{2}\left(
a\right)  =f^{2}\left(  b\right)  $, we must have $f\left(  a\right)
=f\left(  b\right)  $. In other words, $f$ has the property
(\ref{sol.count.weakly-injective.ii-prop}). This proves the \textquotedblleft%
$\Longrightarrow$\textquotedblright\ direction of Exercise
\ref{exe.count.weakly-injective} \textbf{(a)}.

$\Longleftarrow:$ Assume that $f$ has the property
(\ref{sol.count.weakly-injective.ii-prop}). We must prove that $f$ is image-injective.

Let $x\in f\left(  \left[  n\right]  \right)  $ and $y\in f\left(  \left[
n\right]  \right)  $ be such that $\left(  f\mid_{f\left(  \left[  n\right]
\right)  }\right)  \left(  x\right)  =\left(  f\mid_{f\left(  \left[
n\right]  \right)  }\right)  \left(  y\right)  $. Then, $\left(
f\mid_{f\left(  \left[  n\right]  \right)  }\right)  \left(  x\right)
=f\left(  x\right)  $, so that $f\left(  x\right)  =\left(  f\mid_{f\left(
\left[  n\right]  \right)  }\right)  \left(  x\right)  =\left(  f\mid
_{f\left(  \left[  n\right]  \right)  }\right)  \left(  y\right)  =f\left(
y\right)  $.

But $x\in f\left(  \left[  n\right]  \right)  $; thus, there exists some
$a\in\left[  n\right]  $ such that $x=f\left(  a\right)  $. Consider this $a$.

Also, $y\in f\left(  \left[  n\right]  \right)  $; thus, there exists some
$b\in\left[  n\right]  $ such that $y=f\left(  b\right)  $. Consider this $b$.

We have $f^{2}\left(  a\right)  =f\left(  \underbrace{f\left(  a\right)
}_{=x}\right)  =f\left(  x\right)  =f\left(  \underbrace{y}_{=f\left(
b\right)  }\right)  =f\left(  f\left(  b\right)  \right)  =f^{2}\left(
b\right)  $. Hence, (\ref{sol.count.weakly-injective.ii-prop}) shows that
$f\left(  a\right)  =f\left(  b\right)  $. In view of $x=f\left(  a\right)  $
and $y=f\left(  b\right)  $, this rewrites as $x=y$.

Now, forget that we fixed $x$ and $y$. We thus have shown that if $x\in
f\left(  \left[  n\right]  \right)  $ and $y\in f\left(  \left[  n\right]
\right)  $ are such that $\left(  f\mid_{f\left(  \left[  n\right]  \right)
}\right)  \left(  x\right)  =\left(  f\mid_{f\left(  \left[  n\right]
\right)  }\right)  \left(  y\right)  $, then $x=y$. In other words, the map
$f\mid_{f\left(  \left[  n\right]  \right)  }$ is injective. In other words,
the map $f$ is image-injective (by the definition of \textquotedblleft
image-injective\textquotedblright). This proves the \textquotedblleft%
$\Longleftarrow$\textquotedblright\ direction of Exercise
\ref{exe.count.weakly-injective} \textbf{(a)}.

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

\textbf{(b)} We first observe the following facts:

\begin{statement}
\textit{Observation 1:} Let $f:\left[  n\right]  \rightarrow\left[  n\right]
$ be an image-injective map. Let $S=f\left(  \left[  n\right]  \right)  $. Then:

\textbf{(a)} The restriction $f\mid_{S}:S\rightarrow\left[  n\right]  $ is injective.

\textbf{(b)} We have $\left(  f\mid_{S}\right)  \left(  S\right)  \subseteq S$.
\end{statement}

[\textit{Proof of Observation 1:} \textbf{(a)} The map $f$ is image-injective.
In other words, the restriction $f\mid_{f\left(  \left[  n\right]  \right)  }$
is injective (by the definition of \textquotedblleft
image-injective\textquotedblright). Since $S=f\left(  \left[  n\right]
\right)  $, this rewrites as follows: The restriction $f\mid_{S}$ is
injective. This proves Observation 1 \textbf{(a)}.

\textbf{(b)} We have $\left(  f\mid_{S}\right)  \left(  x\right)  =f\left(
x\right)  $ for each $x\in S$. Thus, $\left(  f\mid_{S}\right)  \left(
S\right)  =f\left(  \underbrace{S}_{\subseteq\left[  n\right]  }\right)
\subseteq f\left(  \left[  n\right]  \right)  =S$. This proves Observation 1
\textbf{(b)}.]

\begin{statement}
\textit{Observation 2:} Let $f:\left[  n\right]  \rightarrow\left[  n\right]
$ be a map. Let $S$ be a subset of $\left[  n\right]  $. Assume that the
restriction $f\mid_{S}:S\rightarrow\left[  n\right]  $ is injective and
satisfies $\left(  f\mid_{S}\right)  \left(  S\right)  \subseteq S$. Assume
furthermore that $f\left(  x\right)  \in S$ for each $x\in\left[  n\right]
\setminus S$. Then:

\textbf{(a)} The map $f$ is image-injective.

\textbf{(b)} We have $f\left(  \left[  n\right]  \right)  =S$.
\end{statement}

[\textit{Proof of Observation 2:} \textbf{(b)} We have $f\left(  x\right)  \in
S$ for each $x\in\left[  n\right]  \setminus S$. In other words, we have
$f\left(  x\right)  \in S$ for each $x\in\left[  n\right]  $ that does not
belong to $S$. But we also have $f\left(  x\right)  \in S$ for each
$x\in\left[  n\right]  $ that does belong to $S$ (because each $x\in\left[
n\right]  $ that does belong to $S$ satisfies $f\left(  x\right)  =\left(
f\mid_{S}\right)  \left(  \underbrace{x}_{\in S}\right)  \in\left(  f\mid
_{S}\right)  \left(  S\right)  \subseteq S$). Combining the previous two
sentences, we conclude that $f\left(  x\right)  \in S$ for each $x\in\left[
n\right]  $ (whether or not $x$ belongs to $S$). In other words, $\left\{
f\left(  x\right)  \ \mid\ x\in\left[  n\right]  \right\}  \subseteq S$.
Hence, $f\left(  \left[  n\right]  \right)  =\left\{  f\left(  x\right)
\ \mid\ x\in\left[  n\right]  \right\}  \subseteq S$.

But the restriction $f\mid_{S}:S\rightarrow\left[  n\right]  $ is injective.
Hence, this restriction must take exactly $\left\vert S\right\vert $ distinct
values. In other words, $\left\vert \left(  f\mid_{S}\right)  \left(
S\right)  \right\vert =\left\vert S\right\vert $. Thus, $\left(  f\mid
_{S}\right)  \left(  S\right)  $ cannot be a \textbf{proper} subset of $S$
(because if it was, then it would satisfy $\left\vert \left(  f\mid
_{S}\right)  \left(  S\right)  \right\vert <\left\vert S\right\vert $, which
would contradict $\left\vert \left(  f\mid_{S}\right)  \left(  S\right)
\right\vert =\left\vert S\right\vert $). So we know that $\left(  f\mid
_{S}\right)  \left(  S\right)  $ is a subset of $S$ (since $\left(  f\mid
_{S}\right)  \left(  S\right)  \subseteq S$), but not a proper subset of $S$.
Therefore, $\left(  f\mid_{S}\right)  \left(  S\right)  =S$.

But $\left(  f\mid_{S}\right)  \left(  x\right)  =f\left(  x\right)  $ for
each $x\in S$. Hence, $\left(  f\mid_{S}\right)  \left(  S\right)  =f\left(
S\right)  $, so that $f\left(  S\right)  =\left(  f\mid_{S}\right)  \left(
S\right)  =S$.

Finally, $\left[  n\right]  \supseteq S$, so that $f\left(  \left[  n\right]
\right)  \supseteq f\left(  S\right)  =S$. Combining this with $f\left(
\left[  n\right]  \right)  \subseteq S$, we obtain $f\left(  \left[  n\right]
\right)  =S$. This proves Observation 2 \textbf{(b)}.

\textbf{(a)} Observation 2 \textbf{(b)} yields that $f\left(  \left[
n\right]  \right)  =S$. But the restriction $f\mid_{S}$ is injective (by
assumption). In view of $f\left(  \left[  n\right]  \right)  =S$, this
rewrites as follows: The restriction $f\mid_{f\left(  \left[  n\right]
\right)  }$ is injective. In other words, the map $f$ is image-injective (by
the definition of \textquotedblleft image-injective\textquotedblright). This
proves Observation 2 \textbf{(a)}.]

The following algorithm constructs every image-injective 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 Now, we choose the values $f\left(  x\right)  $ for all $x\in S$. In
other words, we choose the restriction $f\mid_{S}:S\rightarrow\left[
n\right]  $.\ We cannot choose it arbitrarily; in fact, this restriction
$f\mid_{S}$ must be an injective map (because we want $f$ to be
image-injective, and thus Observation 1 \textbf{(a)} dictates that the
restriction $f\mid_{S}:S\rightarrow\left[  n\right]  $ is injective) and must
satisfy $\left(  f\mid_{S}\right)  \left(  S\right)  \subseteq S$ (since we
want $f$ to be image-injective, and thus Observation 1 \textbf{(b)} dictates
that $\left(  f\mid_{S}\right)  \left(  S\right)  \subseteq S$). Thus, we must
choose an injective map $f\mid_{S}:S\rightarrow\left[  n\right]  $ satisfying
$\left(  f\mid_{S}\right)  \left(  S\right)  \subseteq S$. Proposition
\ref{prop.count.ABC-injs} \textbf{(c)} (applied to $A=S$, $B=\left[  n\right]
$ and $C=S$) shows that the number of such maps is $\left\vert S\right\vert
!$; in other words, it is $k!$ (since $\left\vert S\right\vert =k$).

\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{Indeed, by requiring that these values belong to $S$,
we have ensured that our map $f$ satisfies $f\left(  x\right)  \in S$ for each
$x\in\left[  n\right]  \setminus S$. Furthermore, in the previous step, we
have already ensured that the restriction $f\mid_{S}:S\rightarrow\left[
n\right]  $ is injective and satisfies $\left(  f\mid_{S}\right)  \left(
S\right)  \subseteq S$. Thus, Observation 2 \textbf{(a)} yields that our map
$f$ is image-injective, and Observation 2 \textbf{(b)} yields that it
satisfies $f\left(  \left[  n\right]  \right)  =S$ (so that the set $S$, which
was meant to be the image of $f$, will indeed be the image 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 image-injective maps
$f:\left[  n\right]  \rightarrow\left[  n\right]  $, and constructs each of
them exactly once. Thus, the number of image-injective maps $f:\left[
n\right]  \rightarrow\left[  n\right]  $ is%
\[
\sum_{k\in\left\{  0,1,\ldots,n\right\}  }\dbinom{n}{k}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 $k!$ choices in the third step, and finally $k^{n-k}$ choices in
the fourth step). Hence, the number of image-injective maps $f:\left[
n\right]  \rightarrow\left[  n\right]  $ is%
\[
\sum_{k\in\left\{  0,1,\ldots,n\right\}  }\dbinom{n}{k}k!k^{n-k}=\sum
_{k=0}^{n}\dbinom{n}{k}k!k^{n-k}.
\]
This solves Exercise \ref{exe.count.weakly-injective} \textbf{(b)}.

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

Exercise \ref{exe.count.weakly-injective} \textbf{(b)} shows that the number
of image-injective maps $\left[  n\right]  \rightarrow\left[  n\right]  $ is%
\begin{align*}
\sum_{k=0}^{n}\dbinom{n}{k}k!k^{n-k}  &  =\dbinom{n}{0}0!\underbrace{0^{n-0}%
}_{\substack{=0^{n}=0\\\text{(since }n>0\text{)}}}+\sum_{k=1}^{n}%
\underbrace{\dbinom{n}{k}}_{\substack{=\dfrac{n}{k}\dbinom{n-1}{k-1}%
\\\text{(by (\ref{eq.binom.absorp}))}}}\underbrace{k!}_{\substack{=k\cdot
\left(  k-1\right)  !\\\text{(since }k\geq1\text{)}}}k^{n-k}\\
&  =\sum_{k=1}^{n}\underbrace{\dfrac{n}{k}\dbinom{n-1}{k-1}k}_{=n\dbinom
{n-1}{k-1}}\cdot\left(  k-1\right)  !k^{n-k}=\sum_{k=1}^{n}%
n\underbrace{\dbinom{n-1}{k-1}\cdot\left(  k-1\right)  !k^{n-k}}%
_{\substack{\text{this is an integer}\\\text{(since }n-1\in\mathbb{Z}\text{
and }k-1\in\mathbb{Z}\\\text{and }n-k\in\mathbb{N}\text{)}}}\\
&  =\sum_{k=1}^{n}n\cdot\left(  \text{some integer}\right)  =n\cdot\left(
\text{some integer}\right)  .
\end{align*}
Hence, this number is divisible by $n$. This solves Exercise
\ref{exe.count.weakly-injective} \textbf{(c)}.
\end{proof}

\subsection{Counting certain tuples}

\begin{exercise}
\label{exe.binom.masul-1-even}Let $n\in\mathbb{N}$, and let $d$ be a positive integer.

An $n$-tuple $\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[  d\right]
^{n}$ will be called $1$\textit{-even} if the number $1$ occurs in it an even
number of times (i.e., the number of $i\in\left[  n\right]  $ satisfying
$x_{i}=1$ is even). (For example, the $3$-tuples $\left(  1,5,1\right)  $ and
$\left(  3,2,6\right)  $ are $1$-even (yes, $0$ is an even number), while the
$3$-tuple $\left(  2,1,4\right)  $ is not.)

Prove that the number of $1$-even $n$-tuples in $\left[  d\right]  ^{n}$ is
$\dfrac{1}{2}\left(  d^{n}+\left(  d-2\right)  ^{n}\right)  $.

[\textbf{Hint:} Set $e=d-1$; then, $\left(  d-2\right)  ^{n}=\left(
e-1\right)  ^{n}$ and $d^{n}=\left(  e+1\right)  ^{n}$. There might also be a
bijective proof -- after multiplying by $2$ --, but I don't know it.]
\end{exercise}

Exercise \ref{exe.binom.masul-1-even} is \cite[Example 1.13]{Masulo11}. Our
proof of it (taken from \cite[Example 1.13]{Masulo11}) relies on the following fact:

\begin{lemma}
\label{lem.binom.even-bin-form}Let $n\in\mathbb{N}$ and $x\in\mathbb{Q}$ and
$y\in\mathbb{Q}$. Then,%
\[
\left(  x+y\right)  ^{n}+\left(  -x+y\right)  ^{n}=2\sum_{\substack{k\in
\left\{  0,1,\ldots,n\right\}  ;\\k\text{ is even}}}\dbinom{n}{k}x^{k}%
y^{n-k}.
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.binom.even-bin-form} (sketched).]The binomial formula
yields%
\[
\left(  x+y\right)  ^{n}=\sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}.
\]
The binomial formula (applied to $-x$ instead of $x$) yields%
\[
\left(  -x+y\right)  ^{n}=\sum_{k=0}^{n}\dbinom{n}{k}\underbrace{\left(
-x\right)  ^{k}}_{=\left(  -1\right)  ^{k}x^{k}}y^{n-k}=\sum_{k=0}^{n}%
\dbinom{n}{k}\left(  -1\right)  ^{k}x^{k}y^{n-k}.
\]
Adding these two equalities together, we obtain%
\begin{align*}
&  \left(  x+y\right)  ^{n}+\left(  -x+y\right)  ^{n}\\
&  =\sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}+\sum_{k=0}^{n}\dbinom{n}{k}\left(
-1\right)  ^{k}x^{k}y^{n-k}=\sum_{k=0}^{n}\dbinom{n}{k}\left(  1+\left(
-1\right)  ^{k}\right)  x^{k}y^{n-k}\\
&  =\sum_{\substack{k\in\left\{  0,1,\ldots,n\right\}  ;\\k\text{ is even}%
}}\dbinom{n}{k}\underbrace{\left(  1+\left(  -1\right)  ^{k}\right)
}_{\substack{=2\\\text{(since }\left(  -1\right)  ^{k}=1\\\text{(since
}k\text{ is even))}}}x^{k}y^{n-k}+\sum_{\substack{k\in\left\{  0,1,\ldots
,n\right\}  ;\\k\text{ is odd}}}\dbinom{n}{k}\underbrace{\left(  1+\left(
-1\right)  ^{k}\right)  }_{\substack{=0\\\text{(since }\left(  -1\right)
^{k}=-1\\\text{(since }k\text{ is odd))}}}x^{k}y^{n-k}\\
&  =\sum_{\substack{k\in\left\{  0,1,\ldots,n\right\}  ;\\k\text{ is even}%
}}\dbinom{n}{k}2x^{k}y^{n-k}+\underbrace{\sum_{\substack{k\in\left\{
0,1,\ldots,n\right\}  ;\\k\text{ is odd}}}\dbinom{n}{k}0x^{k}y^{n-k}}%
_{=0}=2\sum_{\substack{k\in\left\{  0,1,\ldots,n\right\}  ;\\k\text{ is even}%
}}\dbinom{n}{k}x^{k}y^{n-k}.
\end{align*}
This proves Lemma \ref{lem.binom.even-bin-form}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.binom.masul-1-even} (sketched).]Set $e=d-1$.

We can construct any $1$-even $n$-tuple $\left(  x_{1},x_{2},\ldots
,x_{n}\right)  \in\left[  d\right]  ^{n}$ using the following algorithm:

\begin{itemize}
\item First, we choose the number $k$ of times the entry $1$ will appear in
this $n$-tuple. This number $k$ must be even (since we want our $n$-tuple to
be $1$-even), and must belong to $\left\{  0,1,\ldots,n\right\}  $.

\item Then, we choose the $k$ positions in which this $n$-tuple will have the
entry $1$ (in other words, choose the $k$ indices $i\in\left[  n\right]  $
that will satisfy $x_{i}=1$). This choice can be made in $\dbinom{n}{k}$ many
ways (since we are choosing $k$ out of $n$ possible indices).

\item Next, choose the entries in the remaining $n-k$ positions of our
$n$-tuple. The entries can be arbitrary, except that they must be distinct
from $1$ (since we have already chosen the entries that will equal $1$). Thus,
there are $d-1=e$ choices for each entry, and therefore $e^{n-k}$ choices
altogether in this step.
\end{itemize}

Thus, the total number of $1$-even $n$-tuples is $\sum_{\substack{k\in\left\{
0,1,\ldots,n\right\}  ;\\k\text{ is even}}}\dbinom{n}{k}e^{n-k}$.

But Lemma \ref{lem.binom.even-bin-form} (applied to $x=1$ and $y=e$) yields%
\[
\left(  1+e\right)  ^{n}+\left(  -1+e\right)  ^{n}=2\sum_{\substack{k\in
\left\{  0,1,\ldots,n\right\}  ;\\k\text{ is even}}}\dbinom{n}{k}%
\underbrace{1^{k}}_{=1}e^{n-k}=2\sum_{\substack{k\in\left\{  0,1,\ldots
,n\right\}  ;\\k\text{ is even}}}\dbinom{n}{k}e^{n-k}.
\]
Hence,%
\begin{align*}
\sum_{\substack{k\in\left\{  0,1,\ldots,n\right\}  ;\\k\text{ is even}%
}}\dbinom{n}{k}e^{n-k}  &  =\dfrac{1}{2}\left(  \left(  1+\underbrace{e}%
_{=d-1}\right)  ^{n}+\left(  -1+\underbrace{e}_{=d-1}\right)  ^{n}\right) \\
&  =\dfrac{1}{2}\left(  \left(  \underbrace{1+d-1}_{=d}\right)  ^{n}+\left(
\underbrace{-1+d-1}_{=d-2}\right)  ^{n}\right)  =\dfrac{1}{2}\left(
d^{n}+\left(  d-2\right)  ^{n}\right)  .
\end{align*}
Hence, the total number of $1$-even $n$-tuples is $\sum_{\substack{k\in
\left\{  0,1,\ldots,n\right\}  ;\\k\text{ is even}}}\dbinom{n}{k}%
e^{n-k}=\dfrac{1}{2}\left(  d^{n}+\left(  d-2\right)  ^{n}\right)  $. This
solves Exercise \ref{exe.binom.masul-1-even}.
\end{proof}

\subsection{And more binomial identities}

\begin{exercise}
\label{exe.binom.x+y=1}\textbf{(a)} Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$.
Prove that every $j\in\left\{  0,1,\ldots,n\right\}  $ satisfies%
\[
\sum_{k=0}^{n}\dbinom{m+k}{k}\dbinom{n-k}{j}=\dbinom{n+m+1}{m+j+1}.
\]


\textbf{(b)} Let $x$ and $y$ be two real numbers. Let $z=x+y$. Let
$n\in\mathbb{N}$ and $m\in\mathbb{N}$. Prove that%
\[
x^{m+1}\sum_{k=0}^{n}\dbinom{m+k}{k}y^{k}z^{n-k}=\sum_{i=m+1}^{n+m+1}%
\dbinom{n+m+1}{i}x^{i}y^{\left(  n+m+1\right)  -i}%
\]
and%
\[
y^{n+1}\sum_{k=0}^{m}\dbinom{n+k}{k}x^{k}z^{m-k}=\sum_{i=0}^{m}\dbinom
{n+m+1}{i}x^{i}y^{\left(  n+m+1\right)  -i}%
\]
and%
\[
x^{m+1}\sum_{k=0}^{n}\dbinom{m+k}{k}y^{k}z^{n-k}+y^{n+1}\sum_{k=0}^{m}%
\dbinom{n+k}{k}x^{k}z^{m-k}=z^{n+m+1}.
\]


\textbf{(c)} Let $n\in\mathbb{N}$. Prove that
\[
\sum_{k=0}^{n}\dbinom{n+k}{k}\dfrac{1}{2^{k}}=2^{n}.
\]


[\textbf{Hint:} Part \textbf{(a)} is a restatement of something proven in
class. Derive \textbf{(b)} from \textbf{(a)}, and \textbf{(c)} from
\textbf{(b)}.]
\end{exercise}

We shall outline a solution of this exercise. (For the missing details, see
\cite[solution to Exercise 3.27]{detnotes}.)

\begin{proof}
[Solution to Exercise \ref{exe.binom.x+y=1} (sketched).]\textbf{(a)} Let
$j\in\left\{  0,1,\ldots,n\right\}  $. Then,
(\ref{eq.vandermonde.consequences.f}) (applied to $n+m$, $m$ and $j$ instead
of $n$, $x$ and $y$) yields%
\begin{align*}
\dbinom{n+m+1}{m+j+1}  &  =\sum_{k=0}^{n+m}\dbinom{k}{m}\dbinom{n+m-k}{j}\\
&  =\sum_{k=0}^{m-1}\underbrace{\dbinom{k}{m}}_{\substack{=0\\\text{(by
(\ref{eq.binom.0}))}}}\dbinom{n+m-k}{j}+\sum_{k=m}^{n+m}\dbinom{k}{m}%
\dbinom{n+m-k}{j}\\
&  =\sum_{k=m}^{n+m}\dbinom{k}{m}\dbinom{n+m-k}{j}=\sum_{k=0}^{n}%
\underbrace{\dbinom{m+k}{m}}_{\substack{=\dbinom{m+k}{k}\\\text{(by
(\ref{eq.binom.symm2}))}}}\underbrace{\dbinom{n+m-\left(  m+k\right)  }{j}%
}_{=\dbinom{n-k}{j}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }m+k\text{ for
}k\text{ in the sum}\right) \\
&  =\sum_{k=0}^{n}\dbinom{m+k}{k}\dbinom{n-k}{j}.
\end{align*}
This solves Exercise \ref{exe.binom.x+y=1} \textbf{(a)}.

\textbf{(b)} Let $k\in\left\{  0,1,\ldots,n\right\}  $. From $z=x+y$, we
obtain%
\[
z^{n-k}=\left(  x+y\right)  ^{n-k}=\sum_{j=0}^{n-k}\dbinom{n-k}{j}%
x^{j}y^{\left(  n-k\right)  -j}%
\]
(by the binomial formula). Multiplying both sides of this equality by $y^{k}$,
we find%
\[
y^{k}z^{n-k}=\sum_{j=0}^{n-k}\dbinom{n-k}{j}x^{j}\underbrace{y^{\left(
n-k\right)  -j}y^{k}}_{=y^{n-j}}=\sum_{j=0}^{n-k}\dbinom{n-k}{j}x^{j}y^{n-j}.
\]
Comparing this with%
\begin{align*}
\sum_{j=0}^{n}\dbinom{n-k}{j}x^{j}y^{n-j}  &  =\sum_{j=0}^{n-k}\dbinom{n-k}%
{j}x^{j}y^{n-j}+\sum_{j=n-k+1}^{n-k}\underbrace{\dbinom{n-k}{j}}%
_{\substack{=0\\\text{(by (\ref{eq.binom.0}))}}}x^{j}y^{n-j}\\
&  =\sum_{j=0}^{n-k}\dbinom{n-k}{j}x^{j}y^{n-j},
\end{align*}
we find%
\begin{equation}
y^{k}z^{n-k}=\sum_{j=0}^{n}\dbinom{n-k}{j}x^{j}y^{n-j}.
\label{sol.binom.x+y=1.b.1}%
\end{equation}


Now, forget that we fixed $k$. We thus have proven the equality
(\ref{sol.binom.x+y=1.b.1}) for each $k\in\left\{  0,1,\ldots,n\right\}  $.

Now,%
\begin{align}
&  x^{m+1}\sum_{k=0}^{n}\dbinom{m+k}{k}\underbrace{y^{k}z^{n-k}}%
_{\substack{=\sum_{j=0}^{n}\dbinom{n-k}{j}x^{j}y^{n-j}\\\text{(by
(\ref{sol.binom.x+y=1.b.1}))}}}\nonumber\\
&  =x^{m+1}\sum_{k=0}^{n}\dbinom{m+k}{k}\sum_{j=0}^{n}\dbinom{n-k}{j}%
x^{j}y^{n-j}=x^{m+1}\sum_{j=0}^{n}\underbrace{\left(  \sum_{k=0}^{n}%
\dbinom{m+k}{k}\dbinom{n-k}{j}\right)  }_{\substack{=\dbinom{n+m+1}%
{m+j+1}\\\text{(by Exercise \ref{exe.binom.x+y=1} \textbf{(a)})}}}x^{j}%
y^{n-j}\nonumber\\
&  =x^{m+1}\sum_{j=0}^{n}\dbinom{n+m+1}{m+j+1}x^{j}y^{n-j}=\sum_{j=0}%
^{n}\dbinom{n+m+1}{m+j+1}\underbrace{x^{m+1}x^{j}}_{=x^{m+1+j}}y^{n-j}%
\nonumber\\
&  =\sum_{j=0}^{n}\dbinom{n+m+1}{m+j+1}x^{m+j+1}y^{n-j}=\sum_{i=m+1}%
^{n+m+1}\dbinom{n+m+1}{i}x^{i}y^{\left(  n+m+1\right)  -i}%
\label{sol.binom.x+y=1.b.goal1}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }i\text{ for
}\left(  m+1\right)  +j\text{ in the sum}\right)  .\nonumber
\end{align}
This proves the first of the three equalities we need to show for Exercise
\ref{exe.binom.x+y=1} \textbf{(b)}.

Now, of course, there is nothing preventing us from applying
(\ref{sol.binom.x+y=1.b.goal1}) to $y$, $x$, $m$ and $n$ instead of $x$, $y$,
$n$ and $m$ (after all, we have $z=x+y=y+x$, so the roles of $x$ and $y$ can
be interchanged). Thus we find%
\begin{align}
&  y^{n+1}\sum_{k=0}^{m}\dbinom{n+k}{k}x^{k}z^{m-k}\nonumber\\
&  =\sum_{i=n+1}^{m+n+1}\dbinom{m+n+1}{i}y^{i}x^{\left(  m+n+1\right)
-i}=\sum_{i=n+1}^{n+m+1}\underbrace{\dbinom{n+m+1}{i}}_{\substack{=\dbinom
{n+m+1}{\left(  n+m+1\right)  -i}\\\text{(by (\ref{eq.binom.symm}))}%
}}\underbrace{y^{i}x^{\left(  n+m+1\right)  -i}}_{=x^{\left(  n+m+1\right)
-i}y^{i}}\nonumber\\
&  =\sum_{i=n+1}^{n+m+1}\dbinom{n+m+1}{\left(  n+m+1\right)  -i}x^{\left(
n+m+1\right)  -i}y^{i}=\sum_{i=0}^{m}\dbinom{n+m+1}{i}x^{i}y^{\left(
n+m+1\right)  -i}\label{sol.binom.x+y=1.b.goal2}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }i\text{ for
}\left(  n+m+1\right)  -i\text{ in the sum}\right)  .\nonumber
\end{align}
This proves the second of the three equalities we need to show for Exercise
\ref{exe.binom.x+y=1} \textbf{(b)}.

To prove the third equality, we add the equalities
(\ref{sol.binom.x+y=1.b.goal1}) and (\ref{sol.binom.x+y=1.b.goal2}) together.
We obtain%
\begin{align}
&  x^{m+1}\sum_{k=0}^{n}\dbinom{m+k}{k}y^{k}z^{n-k}+y^{n+1}\sum_{k=0}%
^{m}\dbinom{n+k}{k}x^{k}z^{m-k}\nonumber\\
&  =\sum_{i=m+1}^{n+m+1}\dbinom{n+m+1}{i}x^{i}y^{\left(  n+m+1\right)
-i}+\sum_{i=0}^{m}\dbinom{n+m+1}{i}x^{i}y^{\left(  n+m+1\right)
-i}\nonumber\\
&  =\sum_{i=0}^{m}\dbinom{n+m+1}{i}x^{i}y^{\left(  n+m+1\right)  -i}%
+\sum_{i=m+1}^{n+m+1}\dbinom{n+m+1}{i}x^{i}y^{\left(  n+m+1\right)
-i}\nonumber\\
&  =\sum_{i=0}^{n+m+1}\dbinom{n+m+1}{i}x^{i}y^{\left(  n+m+1\right)
-i}=\left(  x+y\right)  ^{n+m+1}\ \ \ \ \ \ \ \ \ \ \left(  \text{by the
binomial formula}\right) \nonumber\\
&  =z^{n+m+1}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }x+y=z\right)  .
\label{sol.binom.x+y=1.b.goal3}%
\end{align}
This completes the solution of Exercise \ref{exe.binom.x+y=1} \textbf{(b)}.

\textbf{(c)} Recall that $1+1=2$. Thus, applying
(\ref{sol.binom.x+y=1.b.goal3}) to $m=n$, $x=1$, $y=1$ and $z=2$, we find%
\[
1^{n+1}\sum_{k=0}^{n}\dbinom{n+k}{k}1^{k}2^{n-k}+1^{n+1}\sum_{k=0}^{n}%
\dbinom{n+k}{k}1^{k}2^{n-k}=2^{n+n+1}.
\]
This simplifies to%
\[
\sum_{k=0}^{n}\dbinom{n+k}{k}2^{n-k}+\sum_{k=0}^{n}\dbinom{n+k}{k}%
2^{n-k}=2^{n+n+1}.
\]
In other words, $2\sum_{k=0}^{n}\dbinom{n+k}{k}2^{n-k}=2^{n+n+1}$. Dividing
this equality by $2^{n+1}$, we obtain $\sum_{k=0}^{n}\dbinom{n+k}{k}\dfrac
{1}{2^{k}}=2^{n}$. This solves Exercise \ref{exe.binom.x+y=1} \textbf{(c)}.
\end{proof}

For two other solutions to Exercise \ref{exe.binom.x+y=1} \textbf{(c)}, see
\cite[Chapter 5, Example E18]{Engel98} and \cite[Chapter 8, Problem
4]{Engel98}. (I don't know if these solutions can be generalized to give
proofs of (\ref{sol.binom.x+y=1.b.goal3}).)

\subsection{Appendix: Rigorous proof of Proposition
\ref{prop.set-partitions.sur}}

Let us now give a proof of Proposition \ref{prop.set-partitions.sur} that
keeps to the standards of rigor in most parts of mathematics. First, we need a
lemma from the \textquotedblleft isn't this obvious?\textquotedblright\ department:

\begin{lemma}
\label{lem.perm-of-set.equal-sets}Let $k\in\mathbb{N}$. Let $x_{1}%
,x_{2},\ldots,x_{k}$ be $k$ distinct objects. Let $y_{1},y_{2},\ldots,y_{k}$
be $k$ objects such that $\left\{  x_{1},x_{2},\ldots,x_{k}\right\}  =\left\{
y_{1},y_{2},\ldots,y_{k}\right\}  $. Then, there exists a permutation $\sigma$
of $\left[  k\right]  $ such that every $i\in\left[  k\right]  $ satisfies
$y_{i}=x_{\sigma\left(  i\right)  }$.
\end{lemma}

Roughly speaking, Lemma \ref{lem.perm-of-set.equal-sets} says that if $k$
distinct objects $x_{1},x_{2},\ldots,x_{k}$ form the same set as $k$ objects
$y_{1},y_{2},\ldots,y_{k}$ (which are not a-priori required to be distinct,
but it follows easily that they are), then the objects $y_{1},y_{2}%
,\ldots,y_{k}$ are just the objects $x_{1},x_{2},\ldots,x_{k}$ rearranged (the
rearrangement is what the permutation $\sigma$ is meant to take care of).
Convince yourself that this is plausible before (or instead of) reading the
following proof. Notice that $x_{1},x_{2},\ldots,x_{k}$ need to be distinct in
Lemma \ref{lem.perm-of-set.equal-sets}; otherwise, the lemma would be easily
disproven (e.g., we have $\left\{  2,2,3\right\}  =\left\{  2,3,3\right\}  $,
but there is no way to get $2,3,3$ by rearranging $2,2,3$).

\begin{fns}
\begin{proof}
[Proof of Lemma \ref{lem.perm-of-set.equal-sets} (sketched).]For each
$i\in\left[  k\right]  $, there exists some $j\in\left[  k\right]  $ such that
$y_{i}=x_{j}$ (since $y_{i}\in\left\{  y_{1},y_{2},\ldots,y_{k}\right\}
=\left\{  x_{1},x_{2},\ldots,x_{k}\right\}  $). Moreover, this $j$ is unique
(because if $j_{1}$ and $j_{2}$ were two such $j$'s, then we would have
$y_{i}=x_{j_{1}}$ and $y_{i}=x_{j_{2}}$, thus $x_{j_{1}}=y=x_{j_{2}}$, thus
$j_{1}=j_{2}$ because $x_{1},x_{2},\ldots,x_{k}$ are distinct). Let us denote
this $j$ by $\sigma\left(  i\right)  $. Thus, we have defined a $\sigma\left(
i\right)  \in\left[  k\right]  $ for each $i\in\left[  k\right]  $. In other
words, we have defined a map $\sigma:\left[  k\right]  \rightarrow\left[
k\right]  $. Clearly, this map has the property that every $i\in\left[
k\right]  $ satisfies $y_{i}=x_{\sigma\left(  i\right)  }$ (because this is
how $\sigma\left(  i\right)  $ was defined). Thus, in order to prove Lemma
\ref{lem.perm-of-set.equal-sets}, it suffices to check that this map $\sigma$
is a permutation of $\left[  k\right]  $.

Let $h\in\left[  k\right]  $. Then, $x_{h}\in\left\{  x_{1},x_{2},\ldots
,x_{k}\right\}  =\left\{  y_{1},y_{2},\ldots,y_{k}\right\}  $. In other words,
there exists some $i\in\left[  k\right]  $ such that $x_{h}=y_{i}$. Consider
this $i$. Then, $\sigma\left(  i\right)  $ is the unique $j\in\left[
k\right]  $ such that $y_{i}=x_{j}$ (by the definition of $\sigma\left(
i\right)  $). But this unique $j$ must be $h$ (since $h\in\left[  k\right]  $
and $y_{i}=x_{h}$). Hence, $\sigma\left(  i\right)  =h$.

Now, forget that we fixed $h$. We thus have shown that for each $h\in\left[
k\right]  $, there exists some $i\in\left[  k\right]  $ such that
$\sigma\left(  i\right)  =h$. In other words, the map $\sigma$ is surjective.
Since $\sigma$ is a map from $\left[  k\right]  $ to $\left[  k\right]  $,
this yields that $\sigma$ is bijective (by the Pigeonhole Principle for
surjections). In other words, $\sigma$ is a permutation of $\left[  k\right]
$. As we said, this completes the proof of Lemma
\ref{lem.perm-of-set.equal-sets}.
\end{proof}
\end{fns}

\begin{proposition}
\label{prop.set-partitions.k!}Let $X$ be a set, and let $k\in\mathbb{N}$. Let
$\pi:\operatorname*{SC}\nolimits_{k}\left(  X\right)  \rightarrow
\operatorname*{SP}\nolimits_{k}\left(  X\right)  $ be the map that sends each
set composition $\left(  S_{1},S_{2},\ldots,S_{k}\right)  $ to the set
partition $\left\{  S_{1},S_{2},\ldots,S_{k}\right\}  $. (So what the map
$\pi$ does is forgetting the order of the parts. In the language of Example
\ref{exa.set-partitions.ab}, this means forgetting the colors of the blobs.)

Then, for each set partition $\mathbf{P}\in\operatorname*{SP}\nolimits_{k}%
\left(  X\right)  $, we have%
\[
\left(  \text{the number of all }\mathbf{C}\in\operatorname*{SC}%
\nolimits_{k}\left(  X\right)  \text{ satisfying }\pi\left(  \mathbf{C}%
\right)  =\mathbf{P}\right)  =k!.
\]

\end{proposition}

\begin{example}
For this example, pick $X=\left\{  1,2,3\right\}  $ and $k=2$ and
$\mathbf{P}=\left\{  \left\{  1,3\right\}  ,\left\{  2\right\}  \right\}  $.
Then, Proposition \ref{prop.set-partitions.k!} says that the number of all set
compositions $\mathbf{C}\in\operatorname*{SC}\nolimits_{k}\left(  X\right)  $
satisfying $\pi\left(  \mathbf{C}\right)  =\mathbf{P}$ is $2!=2$. These two
set compositions are $\left(  \left\{  1,3\right\}  ,\left\{  2\right\}
\right)  $ and $\left(  \left\{  2\right\}  ,\left\{  1,3\right\}  \right)  $.
\end{example}

\begin{proof}
[Proof of Proposition \ref{prop.set-partitions.k!} (sketched).]Let
$\mathbf{P}\in\operatorname*{SP}\nolimits_{k}\left(  X\right)  $. Thus,
$\mathbf{P}$ is a set partition of $X$ into $k$ parts. We can thus write
$\mathbf{P}$ as $\mathbf{P}=\left\{  T_{1},T_{2},\ldots,T_{k}\right\}  $,
where $T_{1},T_{2},\ldots,T_{k}$ are some disjoint nonempty subsets of $X$
satisfying $T_{1}\cup T_{2}\cup\cdots\cup T_{k}=X$. Consider these
$T_{1},T_{2},\ldots,T_{k}$. These sets $T_{1},T_{2},\ldots,T_{k}$ are nonempty
and disjoint, and therefore distinct (because if two of them were equal, then
their disjointness would force them to be empty).

The rest is now easy: Informally speaking, the set compositions $\mathbf{C}%
\in\operatorname*{SC}\nolimits_{k}\left(  X\right)  $ satisfying $\pi\left(
\mathbf{C}\right)  =\mathbf{P}$ are just all possible ways to rearrange the
$k$-tuple $\left(  T_{1},T_{2},\ldots,T_{k}\right)  $ (this follows from Lemma
\ref{lem.perm-of-set.equal-sets}); thus, there are $k!$ of them (in fact, the
sets $T_{1},T_{2},\ldots,T_{k}$ are distinct, so any way of rearranging them
results in a different $k$-tuple). This proves Proposition
\ref{prop.set-partitions.k!}.

\begin{fns}
Here is a more formal way to make this argument (read this if you care; I
don't require this level of rigor in solutions): The $k$-tuple $\left(
T_{1},T_{2},\ldots,T_{k}\right)  $ is a set composition of $X$ into $k$ parts.
Thus, for each permutation $\sigma$ of $\left[  k\right]  $, the $k$-tuple
$\left(  T_{\sigma\left(  1\right)  },T_{\sigma\left(  2\right)  }%
,\ldots,T_{\sigma\left(  k\right)  }\right)  $ also is a set composition of
$X$ into $k$ parts, hence belongs to $\operatorname*{SC}\nolimits_{k}\left(
X\right)  $. Moreover, this set composition $\left(  T_{\sigma\left(
1\right)  },T_{\sigma\left(  2\right)  },\ldots,T_{\sigma\left(  k\right)
}\right)  $ is a $\mathbf{C}\in\operatorname*{SC}\nolimits_{k}\left(
X\right)  $ satisfying $\pi\left(  \mathbf{C}\right)  =\mathbf{P}$ (because
$\pi\left(  \left(  T_{\sigma\left(  1\right)  },T_{\sigma\left(  2\right)
},\ldots,T_{\sigma\left(  k\right)  }\right)  \right)  =\left\{
T_{\sigma\left(  1\right)  },T_{\sigma\left(  2\right)  },\ldots
,T_{\sigma\left(  k\right)  }\right\}  =\left\{  T_{1},T_{2},\ldots
,T_{k}\right\}  =\mathbf{P}$). Hence, we can define a map
\begin{align*}
\alpha:\left\{  \text{permutations of }\left[  k\right]  \right\}   &
\rightarrow\left\{  \mathbf{C}\in\operatorname*{SC}\nolimits_{k}\left(
X\right)  \text{\ }\mid\text{\ }\pi\left(  \mathbf{C}\right)  =\mathbf{P}%
\right\}  ,\\
\sigma &  \mapsto\left(  T_{\sigma\left(  1\right)  },T_{\sigma\left(
2\right)  },\ldots,T_{\sigma\left(  k\right)  }\right)  .
\end{align*}
This map is injective\footnote{\textit{Proof.} Let $\sigma$ and $\tau$ be two
permutations of $\left[  k\right]  $ such that $\alpha\left(  \sigma\right)
=\alpha\left(  \tau\right)  $. We must show that $\sigma=\tau$.
\par
Let $i\in\left[  k\right]  $. The definition of $\alpha$ yields $\alpha\left(
\sigma\right)  =\left(  T_{\sigma\left(  1\right)  },T_{\sigma\left(
2\right)  },\ldots,T_{\sigma\left(  k\right)  }\right)  $ and $\alpha\left(
\tau\right)  =\left(  T_{\tau\left(  1\right)  },T_{\tau\left(  2\right)
},\ldots,T_{\tau\left(  k\right)  }\right)  $. Hence, the equality
$\alpha\left(  \sigma\right)  =\alpha\left(  \tau\right)  $ rewrites as
$\left(  T_{\sigma\left(  1\right)  },T_{\sigma\left(  2\right)  }%
,\ldots,T_{\sigma\left(  k\right)  }\right)  =\left(  T_{\tau\left(  1\right)
},T_{\tau\left(  2\right)  },\ldots,T_{\tau\left(  k\right)  }\right)  $.
Thus, $T_{\sigma\left(  i\right)  }=T_{\tau\left(  i\right)  }$. Since the
sets $T_{1},T_{2},\ldots,T_{k}$ are distinct, this entails $\sigma\left(
i\right)  =\tau\left(  i\right)  $.
\par
Now, forget that we fixed $i$. We thus have shown that $\sigma\left(
i\right)  =\tau\left(  i\right)  $ for each $i\in\left[  k\right]  $.
Therefore, $\sigma=\tau$. This completes the proof of the injectivity of
$\alpha$.} and surjective\footnote{\textit{Proof.} Let $\mathbf{D}\in\left\{
\mathbf{C}\in\operatorname*{SC}\nolimits_{k}\left(  X\right)  \text{\ }%
\mid\text{\ }\pi\left(  \mathbf{C}\right)  =\mathbf{P}\right\}  $. We must
prove that $\mathbf{D}=\alpha\left(  \sigma\right)  $ for some permutation
$\sigma$ of $\left[  k\right]  $.
\par
We have $\mathbf{D}\in\left\{  \mathbf{C}\in\operatorname*{SC}\nolimits_{k}%
\left(  X\right)  \text{\ }\mid\text{\ }\pi\left(  \mathbf{C}\right)
=\mathbf{P}\right\}  $. In other words, $\mathbf{D}\in\operatorname*{SC}%
\nolimits_{k}\left(  X\right)  $ and $\pi\left(  \mathbf{D}\right)
=\mathbf{P}$. From $\mathbf{D}\in\operatorname*{SC}\nolimits_{k}\left(
X\right)  $, we conclude that $\mathbf{D}$ is a set composition of $X$ into
$k$ parts. We can thus write $\mathbf{D}$ as $\mathbf{D}=\left(  D_{1}%
,D_{2},\ldots,D_{k}\right)  $, where $D_{1},D_{2},\ldots,D_{k}$ are some
disjoint nonempty subsets of $X$ satisfying $D_{1}\cup D_{2}\cup\cdots\cup
D_{k}=X$. Consider these $D_{1},D_{2},\ldots,D_{k}$.
\par
From $\mathbf{D}=\left(  D_{1},D_{2},\ldots,D_{k}\right)  $, we conclude that
$\pi\left(  \mathbf{D}\right)  =\pi\left(  \left(  D_{1},D_{2},\ldots
,D_{k}\right)  \right)  =\left\{  D_{1},D_{2},\ldots,D_{k}\right\}  $ (by the
definition of $\pi$), so that $\left\{  D_{1},D_{2},\ldots,D_{k}\right\}
=\pi\left(  \mathbf{D}\right)  =\mathbf{P}=\left\{  T_{1},T_{2},\ldots
,T_{k}\right\}  $. In other words, $\left\{  T_{1},T_{2},\ldots,T_{k}\right\}
=\left\{  D_{1},D_{2},\ldots,D_{k}\right\}  $. Since $T_{1},T_{2},\ldots
,T_{k}$ are distinct, we can thus apply Lemma \ref{lem.perm-of-set.equal-sets}
to $x_{i}=T_{i}$ and $y_{i}=D_{i}$. We conclude that there exists a
permutation $\sigma$ of $\left[  k\right]  $ such that every $i\in\left[
k\right]  $ satisfies $D_{i}=T_{\sigma\left(  i\right)  }$. Consider this
$\sigma$. We have $\left(  D_{1},D_{2},\ldots,D_{k}\right)  =\left(
T_{\sigma\left(  1\right)  },T_{\sigma\left(  2\right)  },\ldots
,T_{\sigma\left(  k\right)  }\right)  $ (since every $i\in\left[  k\right]  $
satisfies $D_{i}=T_{\sigma\left(  i\right)  }$). The definition of $\alpha$
yields%
\[
\alpha\left(  \sigma\right)  =\left(  T_{\sigma\left(  1\right)  }%
,T_{\sigma\left(  2\right)  },\ldots,T_{\sigma\left(  k\right)  }\right)
=\left(  D_{1},D_{2},\ldots,D_{k}\right)  =\mathbf{D}.
\]
Hence, we have found a permutation $\sigma$ of $\left[  k\right]  $ such that
$\mathbf{D}=\alpha\left(  \sigma\right)  $. This completes our proof of the
surjectivity of $\alpha$.}; thus, it is bijective. We have therefore found a
bijective map from $\left\{  \text{permutations of }\left[  k\right]
\right\}  $ to $\left\{  \mathbf{C}\in\operatorname*{SC}\nolimits_{k}\left(
X\right)  \text{\ }\mid\text{\ }\pi\left(  \mathbf{C}\right)  =\mathbf{P}%
\right\}  $. Hence,
\begin{align*}
\left\vert \left\{  \text{permutations of }\left[  k\right]  \right\}
\right\vert  &  =\left\vert \left\{  \mathbf{C}\in\operatorname*{SC}%
\nolimits_{k}\left(  X\right)  \text{\ }\mid\text{\ }\pi\left(  \mathbf{C}%
\right)  =\mathbf{P}\right\}  \right\vert \\
&  =\left(  \text{the number of all }\mathbf{C}\in\operatorname*{SC}%
\nolimits_{k}\left(  X\right)  \text{ satisfying }\pi\left(  \mathbf{C}%
\right)  =\mathbf{P}\right)  ,
\end{align*}
so that%
\[
\left(  \text{the number of all }\mathbf{C}\in\operatorname*{SC}%
\nolimits_{k}\left(  X\right)  \text{ satisfying }\pi\left(  \mathbf{C}%
\right)  =\mathbf{P}\right)  =\left\vert \left\{  \text{permutations of
}\left[  k\right]  \right\}  \right\vert =k!.
\]
This proves Proposition \ref{prop.set-partitions.k!}.
\end{fns}
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.set-partitions.sur}.]Proposition
\ref{prop.set-compositions.sur} yields $\left\vert \operatorname*{SC}%
\nolimits_{k}\left(  X\right)  \right\vert =\operatorname*{sur}\left(
\left\vert X\right\vert ,k\right)  $. Thus,%
\begin{align*}
\operatorname*{sur}\left(  \left\vert X\right\vert ,k\right)   &  =\left\vert
\operatorname*{SC}\nolimits_{k}\left(  X\right)  \right\vert \\
&  =\left(  \text{the number of all }\mathbf{C}\in\operatorname*{SC}%
\nolimits_{k}\left(  X\right)  \right) \\
&  =\sum_{\mathbf{P}\in\operatorname*{SP}\nolimits_{k}\left(  X\right)
}\underbrace{\left(  \text{the number of all }\mathbf{C}\in\operatorname*{SC}%
\nolimits_{k}\left(  X\right)  \text{ satisfying }\pi\left(  \mathbf{C}%
\right)  =\mathbf{P}\right)  }_{\substack{=k!\\\text{(by Proposition
\ref{prop.set-partitions.k!})}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have subdivided our count according}\\
\text{to the value of }\pi\left(  \mathbf{C}\right)
\end{array}
\right) \\
&  =\sum_{\mathbf{P}\in\operatorname*{SP}\nolimits_{k}\left(  X\right)
}k!=\left\vert \operatorname*{SP}\nolimits_{k}\left(  X\right)  \right\vert
\cdot k!.
\end{align*}
Dividing this equality by $k!$, we find $\dfrac{\operatorname*{sur}\left(
\left\vert X\right\vert ,k\right)  }{k!}=\left\vert \operatorname*{SP}%
\nolimits_{k}\left(  X\right)  \right\vert $. This proves Proposition
\ref{prop.set-partitions.sur}.
\end{proof}

\begin{thebibliography}{99999999999999}                                                                                   %


\bibitem[Engel98]{Engel98}Arthur Engel, \textit{Problem-Solving Strategies},
Springer 1998.

\bibitem[Fall2017-HW6os]{fall2017-hw6os}Darij Grinberg, \textit{Math 4990 Fall
2017 (Darij Grinberg): homework set 6 with solutions.}\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw6os.pdf}

\bibitem[Grinbe09]{QEDMO6P4}Darij Grinberg, \textit{6th QEDMO 2009, Problem 4
(the Cauchy identity)}. \newline\url{http://www.cip.ifi.lmu.de/~grinberg/QEDMO6P4long.pdf}

\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[Masulo11]{Masulo11}Dragan Ma\v{s}ulovi\'{c}, \textit{Introduction to
Discrete Mathematics}, 14 January 2011.\newline\url{http://www.algebra.uni-linz.ac.at/Students/DiskreteMathematik/ws10/DM-WS-2010-11.pdf}
\end{thebibliography}


\end{document}