\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:31}
%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 (corrected
version 20 Mar 2018)}

due date: Wednesday 21 March 2018 at the beginning of class, or before that by
email or moodle

Please solve \textbf{at most 3} of the 6 exercises!
\end{center}

%

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


\bigskip

Please write your name on each page. Feel free to use LaTeX
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw-template.tex}{here} is a
sample file with lots of amenities included).

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}

\subsection{Another binomial identity}

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


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

\subsection{More on inclusion/exclusion}

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

\subsection{Multijections, set compositions and set partitions}

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.

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}

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

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

\begin{noncompile}
https://oeis.org/A006153
\end{noncompile}

\subsection{Counting certain tuples}

\begin{exercise}
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}

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

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


\end{document}