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\,}$}}}
\)
Handout 7.1 Introduction; Counting Surjections
Overcounting. No, undercounting. Wait, overcounting! Hmm, undercounting?
Example 7.1 . Revisiting an Old Problem.
How many lattice paths from
\((0,0)\) to
\((6,7)\) do not pass through
\((2,3)\) or
\((3,5)\text{?}\)
Solution .
We count all lattice paths from \((0,0)\) to \((6,7)\) and subtract those that path through either \((2,3)\) or \((3,5)\text{.}\) We do this by first subtracting those that pass through \((2,3)\) and then subtracting those that pass through \((3,5\) ). However, this subtracts those that pass through both intermediate points twice, so we need to add back that number. This gives us
\begin{equation*}
\binom{13}{6} - \binom{5}{2}\binom{8}{4} - \binom{8}{3}\binom{5}{3} + \binom{5}{2}\binom{3}{1}\binom{5}{3}\text{.}
\end{equation*}
We need to introduce some notation:
A
property \(P_{i}\) is something that an element of a set either satisfies or does not satisfy.
If \(\mc{P}=\{P_{1},\dots,P_{m}\}\) is a family of properties and \(S\subseteq [m]\text{,}\) then \(N(S)\) is the number of objects that satisfy \(P_{i}\) for every \(i\in S\text{.}\)
If
\(S=\{1,2,5\}\text{,}\) then
\(N(S)\) is the number of objects satisfying
Theorem 7.2 . Principle of Inclusion-Exclusion.
Let \(X\) be a set and \(\mathcal{P}=\{P_{1},\dots,P_{m}\}\) a family of properties. The number of elements of \(X\) which satisfy none of the properties in \(\mathcal{P}\) is given by
\begin{equation*}
\sum_{S\subseteq [m]}(-1)^{|S|}N(S)\text{.}
\end{equation*}
Peer instruction question 1.
Activity 7.1.1 .
A class of
\(50\) students was polled to determine the programming languages in which they were proficient.
\(\#\) Language(s)
\(\#\) Language(s)
\(\#\) Language(s)
32
ALGOL60
12
ALGOL60 + PL/I
2
All 3
17
PL/I
17
ALGOL60 + COBOL
26
COBOL
3
PL/I + COBOL
How many of the students are proficient in
none of the languages? Answer this question by doing the following:
(a) (b) Write out inclusion-exclusion sum.
Counting Surjections.
Definition 7.3 .
A function
\(f\colon X\to Y\) is called a
surjection provided that for every
\(y\in Y\text{,}\) there is at least one
\(x\in X\) such that
\(f(x) = y\text{.}\) Surjections are also called
onto functions .
Definition 7.4 .
The range of a function \(f\colon X\to Y\) is the set
\begin{equation*}
\{y\in Y\colon \text{ there is }x\in X\text{ such that }f(x) = y\}\text{.}
\end{equation*}
Peer instruction question 2.
Definition 7.5 .
Let
\(X\) be the set of all functions from
\([n]\) to
\([m]\text{.}\) We say
\(f\in X\) satisfies property
\(P_{i}\) if
\(i\) is
not in the
range of
\(f\text{.}\)
Peer instruction questions 3–4 followed by activity handout.
Theorem 7.6 .
The number \(S(n,m)\) of surjections from \([n]\) to \([m]\) is given by
\begin{equation*}
S(n,m) = \sum_{j=0}^{m} (-1)^{j}\binom{m}{j}(m-j)^{n}\text{.}
\end{equation*}
Formula will be provided to you on Test II and the Final Exam.
You will not be expected to derive this formula.
You will be expected to recognize when a counting problem calls for surjections and to use the formula in answers.
