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.2 Counting Derangements and Euler’s \(\phi\) Function
Counting Derangements. Suppose we randomly distributed name table tents corresponding only to students here today. How many ways can we do this in which no one gets their own table tent?
A
permutation of
\([n]\) is a bijection from
\([n]\) to
\([n]\text{.}\)
Peer instruction question 1.
A
derangement of
\([n]\) is a permutation
\(\sigma\) of
\([n]\) if
\(\sigma(i)\neq i\) for all
\(i\in[n]\text{.}\)
A permutation
\(\sigma\) of
\([n]\) satisfies property
\(P_i\) provided that
.
To frame your discussion, think about how to fill in this blank: With inclusion-exclusion, our goal is to count the objects that satisfy
of the properties.
Peer instruction question 2.
Activity 7.2.1 .
Let’s count derangements of
\([n]\text{.}\)
(a) How many properties are in
\(\mc{P}\text{?}\)
(b) How many permutations satisfy
\(P_{1}\text{?}\) What about
\(P_{3}\text{?}\)
(c) How many permutations satisfy
\(P_{1}\) and \(P_{3}\text{?}\)
(d) Let
\(S\subseteq [n]\) with
\(|S|=4\text{.}\) How many permutations satisfy all properties with subscript in
\(S\text{?}\)
(e) Let
\(S\subseteq [n]\) with
\(|S|=j\text{.}\) How many permutations satisfy all properties with subscript in
\(S\text{?}\)
(f) How many subsets of
\([n]\) have size
\(j\text{?}\)
(g) Use inclusion-exclusion to find
\(d_{n}\text{,}\) the number of derangements of
\([n]\)
\begin{equation*}
d_{n} = \sum_{j=0}^{n} (-1)^{j}\binom{n}{j}(n-j)!\phantom{= n! \sum_{j=0}^{n} \frac{(-1)^{j}}{j!}\approx \frac{n!}{e}}
\end{equation*}
Euler \(\phi\) function.
Definition 7.7 .
Let
\(m\) and
\(n\) be integers. The
greatest common divisor of
\(m\) and
\(n\) is an integer
\(t\) such that
\(t\) divides both
\(m\) and
\(n\) and if
\(t'\) also divides
\(m\) and
\(n\text{,}\) then
\(t'\leq t\text{.}\) We say that
\(m\) and
\(n\) are
relatively prime provided that
\(\gcd(m,n)=1\text{.}\)
Peer instruction question 3.
Definition 7.8 .
If \(n\geq 2\) is an integer, define the Euler \(\phi\) function (sometimes Euler totient function )
\begin{equation*}
\phi(n) = \left\vert\{m\in [n]\colon \gcd(m,n) = 1\}\right\vert\text{.}
\end{equation*}
Activity 7.2.2 .
With your group, find the following by listing the integers counted by each:
\(\displaystyle \phi(4)\)
\(\displaystyle \phi(12)\)
\(\displaystyle \phi(13)\)
We can also say that two integers are relatively prime if and only if they do not have any common prime factors.
Activity 7.2.3 .
Use inclusion-exclusion to find
\(\phi(30)\) by excluding those numbers having a common prime factor with
\(30=2\cdot 3\cdot 5\text{.}\)
2
2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30
3
3, 6, 9, 12, 15, 18, 21, 24, 27, 30
5
5, 10, 15, 20, 25, 30
Proposition 7.9 .
Let \(n\geq 2\text{,}\) \(k\geq 1\text{,}\) and let \(p_{1},p_{2},\dots,p_{k}\) be distinct primes each of which divide \(n\text{.}\) The number of integers from \([n]\) which are divisible by each of these \(k\) primes is
\begin{equation*}
\phantom{\frac{n}{p_{1}p_{2}\cdots p_{k}}.}
\end{equation*}
Theorem 7.10 .
Let \(n\ge2\) be a positive integer and suppose that \(n\) has \(m\) distinct prime factors: \(p_{1}\text{,}\) \(p_{2},\dots,p_{m}\text{.}\) Then
\begin{equation*}
\phi(n) = n\prod_{i = 1}^{m}\frac{p_{i}-1}{p_{i}}.
\end{equation*}
Example 7.11 .
Use the fact that
\begin{equation*}
1369122257328767073 = (3)^{3}(11)(19)^{4}(31)^{2}(6067)^{2}
\end{equation*}
to compute \(\phi(1369122257328767073)\text{.}\)
Solution .
\begin{equation*}
\phi(1369122257328767073) = (3)^{3}(11)(19)^{4}(31)^{2}(6067)^{2}\cdot \frac{2}{3} \frac{10}{11}\frac{18}{19}\frac{30}{31}\frac{6066}{6067} = (3)^{2}(19)^{3}(31)(6067)\cdot 2\cdot 10\cdot 18\cdot 30\cdot 6066
\end{equation*}
Activity 7.2.4 .
(a)
Find \(\phi(n)\) for each of the following integers \(n\text{.}\) (Use reliable technology such as WolframAlpha to factor!)
\(\displaystyle 8675309\)
(b)
Suppose you need to find \(\phi(n)\) where
\begin{align*}
n = \amp 31484972786199768889479107860964368171543984609017931\\
\amp 39001922159851668531040708539722329324902813359241016\\
\amp 93211209710523\text{.}
\end{align*}
Why might this be hard, despite the information we have learned today?
(c)
Would knowing that \(n= p_{1}p_{2}\) for primes
\begin{align*}
p_{1} \amp = 470287785858076441566723507866751092927015824834881906763507\\
p_{2} \amp = 669483106578092405936560831017556154622901950048903016651289
\end{align*}
help?
Activity 7.2.5 .
What’s wrong with this exercise?
A graduate student eats lunch in the campus food court every Tuesday over the course of a 15-week semester. He is joined each week by some subset of a group of six friends from across campus. Over the course of a semester, he ate lunch with each friend 11 times, each pair 9 times, and each triple 6 times. He ate lunch with each group of four friends 4 times and each group of five friends 4 times. All seven of them ate lunch together only once that semester. Did the graduate student ever eat lunch alone? If so, how many times?
