Skip to main content
Contents Embed Prev Up Next \(\newcommand{\set}[1]{\{#1\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Worksheet 7.1 Counting Surjections
1. Let’s first focus on the case of counting surjections from
\([8]\) to
\([5]\text{.}\)
(a) How many properties are in
\(\mc{P}\text{?}\) What are they?
Solution .
There are
\(5\) properties:
\(P_1,P_2,P_3,P_4,P_5\text{.}\)
(b) How many functions satisfy
\(P_{1}\text{?}\) What about
\(P_{3}\text{?}\)
Solution .
\(4^8\text{,}\) \(4^8\text{.}\) In each case,
\(1\) number has been excluded from the possible outputs.
(c) How many functions satisfy
\(P_{1}\) and \(P_{3}\text{?}\)
Solution .
\(3^8\) since
\(2\) numbers have been excluded from the possible outputs.
(d) How many functions satisfy
\(P_{2}\) and \(P_{5}\text{?}\)
Solution .
\(3^8\) since
\(2\) numbers have been excluded from the possible outputs.
(e) Let
\(S\subseteq [5]\) with
\(|S|=3\text{.}\) How many functions satisfy all properties in
\(S\text{?}\)
Solution .
\(2^8\) since
\(3\) numbers have been excluded from the possible outputs.
(f) Use inclusion-exclusion to find the number of surjections from
\([8]\) to
\([5]\text{.}\) (You might want to put your formula into an online calculator.)
Solution .
\begin{equation*}
\sum_{j=0}^5 (-1)^j\binom{5}{j}(5-j)^8 = 126\, 000
\end{equation*}
2. Now let’s count surjections from
\([n]\) to
\([m]\) (
\(n\geq m\) ).
(a) How many properties are in
\(\mc{P}\text{?}\)
Solution .
There are
\(m\) properties: one for each element of the set of possible outputs
\([m]\text{.}\)
(b) How many functions satisfy
\(P_{1}\text{?}\) What about
\(P_{3}\text{?}\)
Solution .
In each case, one possible output is excluded, so there are
\((m-1)^n\text{.}\)
(c) How many functions satisfy
\(P_{1}\) and \(P_{3}\text{?}\)
Solution .
Here two possible outputs are excluded, so we have
\((m-2)^n\text{.}\)
(d) Let
\(S\subseteq [m]\) with
\(|S|=4\text{.}\) How many functions satisfy all properties in
\(S\text{?}\)
Solution .
Here four possible outputs are excluded, giving us
\((m-4)^n\text{.}\)
(e) Let
\(S\subseteq [m]\) with
\(|S|=j\text{.}\) How many functions satisfy all properties in
\(S\text{?}\)
Solution .
Here
\(j\) possible outputs are excluded, giving us
\((m-j)^n\text{.}\)
(f) How many subsets of
\([m]\) have size
\(j\text{?}\)
Solution .
There are
\(C(m,j)\) such subsets, which tells us how many times
\((m-j)^n\) is added/subtracted in the inclusion-exclusion sum.
(g) Use inclusion-exclusion to find the number of surjections from
\([n]\) to
\([m]\text{.}\)
Solution .
\begin{equation*}
\sum_{j=0}^m (-1)^j \binom{m}{j}(m-j)^n
\end{equation*}
