\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{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Friday, March 17, 2023 22:07:32}
%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}}
\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]}
\ihead{Math 4990 Fall 2017 (Darij Grinberg): homework set 3}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4990 Fall 2017 (Darij Grinberg): homework set 3 with solutions}
\end{center}

%

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


\subsection{Counting triples}

Recall that the word \textquotedblleft\textit{triple}\textquotedblright\ means
a $3$-tuple. Tuples are always ordered by definition.

\begin{exercise}
\label{exe.ABC}Let $n\in\mathbb{N}$.

\textbf{(a)} Find the number of all triples $\left(  A,B,C\right)  $ of
subsets of $\left[  n\right]  $ satisfying $A\cup B\cup C=\left[  n\right]  $
and $A\cap B\cap C=\varnothing$.

\textbf{(b)} Find the number of all triples $\left(  A,B,C\right)  $ of
subsets of $\left[  n\right]  $ satisfying $B\cap C=C\cap A=A\cap B$.

\textbf{(c)} Find the number of all triples $\left(  A,B,C\right)  $ of
subsets of $\left[  n\right]  $ satisfying $A\cap B=A\cap C$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.ABC} (sketched).]\textbf{(a)} The number of
such triples is $6^{n}$.

\textit{Proof.} Let me first give a quick but informal argument.

Clearly, a triple $\left(  A,B,C\right)  $ of subsets of $\left[  n\right]  $
satisfies $A\cup B\cup C=\left[  n\right]  $ and $A\cap B\cap C=\varnothing$
if and only if it has the following property: Each $i\in\left[  n\right]  $
belongs to \textbf{at least one} of the three sets $A,B,C$, but \textbf{no}
$i\in\left[  n\right]  $ belongs to \textbf{all three} of them. Thus, the
following simple algorithm constructs every triple $\left(  A,B,C\right)  $ of
subsets of $\left[  n\right]  $ satisfying $A\cup B\cup C=\left[  n\right]  $
and $A\cap B\cap C=\varnothing$: For each $i\in\left[  n\right]  $, we decide
whether the element $i$ should be contained in the set $A$ only (i.e., in $A$
but not in $B$ and not in $C$), or in the set $B$ only, or in the set $C$
only, or in the sets $A$ and $B$ only (i.e., in $A$ and $B$ but not in $C$),
or in the sets $A$ and $C$ only, or in the sets $B$ and $C$ only. There are
clearly $6$ options to choose from in this decision. Thus, in total, there are
$6^{n}$ possible triples (because we are making this decision once for each of
the $n$ elements $i$ of $\left[  n\right]  $). This completes our informal proof.

A rigorous way to present the above argument is the following: Let
$\mathfrak{A}$ be the set of all triples $\left(  A,B,C\right)  $ of subsets
of $\left[  n\right]  $ satisfies $A\cup B\cup C=\left[  n\right]  $ and
$A\cap B\cap C=\varnothing$. We must show that $\left\vert \mathfrak{A}%
\right\vert =6^{n}$. We know that the set $\left[  6\right]  ^{\left[
n\right]  }$ (that is, the set of all maps $\left[  n\right]  \rightarrow
\left[  6\right]  $) has size $\left\vert \left[  6\right]  ^{\left[
n\right]  }\right\vert =\left\vert \left[  6\right]  \right\vert ^{\left\vert
\left[  n\right]  \right\vert }=6^{n}$; thus, it will suffice to exhibit a
bijection $\mathfrak{A}\rightarrow\left[  6\right]  ^{\left[  n\right]  }$.

We define such a bijection $\Xi:\mathfrak{A}\rightarrow\left[  6\right]
^{\left[  n\right]  }$ as follows: It should send any triple $\left(
A,B,C\right)  \in\mathfrak{A}$ to the map $f:\left[  n\right]  \rightarrow
\left[  6\right]  $ that sends each $i\in\left[  n\right]  $ to
\begin{equation}%
\begin{cases}
1, & \text{if }i\in A\text{ but }i\notin B\text{ and }i\notin C;\\
2, & \text{if }i\in B\text{ but }i\notin C\text{ and }i\notin A;\\
3, & \text{if }i\in C\text{ but }i\notin A\text{ and }i\notin B;\\
4, & \text{if }i\in A\text{ and }i\in B\text{ but }i\notin C;\\
5, & \text{if }i\in A\text{ and }i\in C\text{ but }i\notin B;\\
6, & \text{if }i\in B\text{ and }i\in C\text{ but }i\notin A
\end{cases}
\label{sol.ABC.a.f-values}%
\end{equation}
\footnote{From the point of view of logic, the word \textquotedblleft
but\textquotedblright\ is merely a synonym for \textquotedblleft
and\textquotedblright. But in this definition, it is meant to reinforce the
intuition: We say "if $i\in A$ but $i\notin B$ and $i\notin C$%
\textquotedblright\ because we clearly want to contrast the sets to which $i$
belongs on one side against the sets to which $i$ does not belong on the
other.}. (As I said, this is merely a translation of our above informal
argument into rigorous language; in particular, the $6$ possible values in
(\ref{sol.ABC.a.f-values}) are our \textquotedblleft$6$
options\textquotedblright, and we are defining a map $f:\left[  n\right]
\rightarrow\left[  6\right]  $ because we are choosing among these $6$ options
for each element of $\left[  n\right]  $.)

We are not yet done. We must prove, first of all, that the expression in
(\ref{sol.ABC.a.f-values}) is well-defined, i.e., that each $i\in\left[
n\right]  $ will satisfy exactly one of the conditions \textquotedblleft$i\in
A$ but $i\notin B$ and $i\notin C$\textquotedblright\ and \textquotedblleft%
$i\in B$ but $i\notin C$ and $i\notin A$\textquotedblright\ and
\textquotedblleft$i\in C$ but $i\notin A$ and $i\notin B$\textquotedblright%
\ and \textquotedblleft$i\in A$ and $i\in B$ but $i\notin C$\textquotedblright%
\ and \textquotedblleft$i\in A$ and $i\in C$ but $i\notin B$\textquotedblright%
\ and \textquotedblleft$i\in B$ and $i\in C$ but $i\notin A$\textquotedblright%
. This is easy\footnote{It is clear enough that $i$ cannot satisfy more than
one of these conditions. In order to see that $i$ has to satisfy at least one
of them, we must rule out the possibilities that $\left(  i\in A\text{ and
}i\in B\text{ and }i\in C\right)  $ and $\left(  i\notin A\text{ and }i\notin
B\text{ and }i\notin C\right)  $. But this is easy: The first of these
possibilities is ruled out by $A\cap B\cap C=\varnothing$, while the second is
ruled out by $A\cup B\cup C=\left[  n\right]  $.}. This shows that the map
$f:\left[  n\right]  \rightarrow\left[  6\right]  $ is well-defined for each
$\left(  A,B,C\right)  \in\mathfrak{A}$, and therefore the map $\Xi
:\mathfrak{A}\rightarrow\left[  6\right]  ^{\left[  n\right]  }$ is
well-defined. In order to prove that this $\Xi$ is a bijection, it is most
reasonable to construct an inverse for $\Xi$.

I claim that such an inverse is the map $\left[  6\right]  ^{\left[  n\right]
}\rightarrow\mathfrak{A}$ that sends each $f:\left[  n\right]  \rightarrow
\left[  6\right]  $ to the triple $\left(  A,B,C\right)  $, where%
\begin{align*}
A  &  =\left\{  i\in\left[  n\right]  \ \mid\ f\left(  i\right)  \in\left\{
1,4,5\right\}  \right\}  ;\\
B  &  =\left\{  i\in\left[  n\right]  \ \mid\ f\left(  i\right)  \in\left\{
2,4,6\right\}  \right\}  ;\\
C  &  =\left\{  i\in\left[  n\right]  \ \mid\ f\left(  i\right)  \in\left\{
3,5,6\right\}  \right\}  .
\end{align*}
Indeed, it is straightforward to check that this map is well-defined, and
actually inverse to $\Xi$. (How did I come up with this map? Well, I wanted an
inverse to $\Xi$, so I was looking for a map that reconstructs any triple
$\left(  A,B,C\right)  \in\mathfrak{A}$ from the map $f:\left[  n\right]
\rightarrow\left[  6\right]  $ that sends each $i\in\left[  n\right]  $ to
(\ref{sol.ABC.a.f-values}). This is a rather simple reconstruction problem:
For example, the first entry $A$ of this triple $\left(  A,B,C\right)  $ can
be reconstructed from $f$ as the set $\left\{  i\in\left[  n\right]
\ \mid\ f\left(  i\right)  \in\left\{  1,4,5\right\}  \right\}  $, because the
elements of $A$ are exactly those elements $i\in\left[  n\right]  $ whose
image under $f$ is $1$, $4$ or $5$.) This completes the rigorous proof of
\textbf{(a)}.

\textbf{(b)} The number of such triples is $5^{n}$.

\textit{Proof.} I shall give an informal proof only, trusting that you can
translate it into a rigorous bijective argument as I've done above for part
\textbf{(a)}.

Clearly, a triple $\left(  A,B,C\right)  $ of subsets of $\left[  n\right]  $
satisfies $B\cap C=C\cap A=A\cap B$ if and only if it has the following
property: Each $i\in\left[  n\right]  $ \textbf{either belongs to at most one
}of the three sets $A,B,C$, \textbf{or belongs to all three} of them. Thus,
the following simple algorithm constructs every triple $\left(  A,B,C\right)
$ of subsets of $\left[  n\right]  $ satisfying $B\cap C=C\cap A=A\cap B$: For
each $i\in\left[  n\right]  $, we decide whether the element $i$ should be
contained in none of the sets $A$, $B$ and $C$, or in the set $A$ only (i.e.,
in $A$ but not in $B$ and not in $C$), or in the set $B$ only, or in the set
$C$ only, or in all three sets $A$, $B$ and $C$. There are clearly $5$ options
to choose from in this decision. Thus, in total, there are $5^{n}$ possible
triples (because we are making this decision once for each of the $n$ elements
$i$ of $\left[  n\right]  $). This completes our informal proof.

\textbf{(c)} The number of such triples is $6^{n}$.

\textit{Proof.} I shall give an informal proof only, trusting that you can
translate it into a rigorous bijective argument as I've done above for part
\textbf{(a)}.

Clearly, a triple $\left(  A,B,C\right)  $ of subsets of $\left[  n\right]  $
satisfies $A\cap B=A\cap C$ if and only if it has the following property: Each
$i\in\left[  n\right]  $ \textbf{either belongs to at most one }of the three
sets $A,B,C$, \textbf{or belongs to }$B$ \textbf{and }$C$ \textbf{only, or
belongs to all three} of them. Thus, the following simple algorithm constructs
every triple $\left(  A,B,C\right)  $ of subsets of $\left[  n\right]  $
satisfying $A\cap B=A\cap C$: For each $i\in\left[  n\right]  $, we decide
whether the element $i$ should be contained in none of the sets $A$, $B$ and
$C$, or in the set $A$ only (i.e., in $A$ but not in $B$ and not in $C$), or
in the set $B$ only, or in the set $C$ only, or in the sets $B$ and $C$ only
(i.e., in $B$ and in $C$ but not in $A$), or in all three sets $A$, $B$ and
$C$. There are clearly $6$ options to choose from in this decision. Thus, in
total, there are $6^{n}$ possible triples (because we are making this decision
once for each of the $n$ elements $i$ of $\left[  n\right]  $). This completes
our informal proof.
\end{proof}

\subsection{Stirling numbers of the 2nd kind, again}

Recall that if $n\in\mathbb{N}$ and $k\in\mathbb{N}$, then
$\operatorname*{sur}\left(  n,k\right)  $ denotes the number of surjections
$\left[  n\right]  \rightarrow\left[  k\right]  $, and $%
%TCIMACRO{\QDATOPD{\{}{\}}{n}{k}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{n}{k}%
%EndExpansion
$ denotes the Stirling number of the 2nd kind (defined as $\operatorname*{sur}%
\left(  n,k\right)  /k!$).

Recall furthermore that we are using the convention that $\dbinom{a}{b}=0$
when $b\notin\mathbb{N}$.

\begin{exercise}
\label{exe.sur2}Let $n$ be a positive integer. Let $k\in\mathbb{N}$.

\textbf{(a)} Prove that%
\[
\operatorname*{sur}\left(  n,k\right)  =k\sum_{i=0}^{k}\left(  -1\right)
^{k-i}\dbinom{k-1}{i-1}i^{n-1}.
\]


\textbf{(b)} Prove that%
\[%
%TCIMACRO{\QDATOPD{\{}{\}}{n}{k}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{n}{k}%
%EndExpansion
=\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dfrac{i^{n}}{i!\left(  k-i\right)
!}.
\]

\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.sur2}.]Exercise 4 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{Math 4990 homework
set \#2} showed that%
\begin{equation}
\operatorname*{sur}\left(  n,k\right)  =\sum_{i=0}^{k}\left(  -1\right)
^{k-i}\dbinom{k}{i}i^{n}. \label{sol.sur2.oldexe}%
\end{equation}
But Exercise 2 \textbf{(b)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{Math 4990 homework
set \#1} showed that%
\begin{equation}
K\dbinom{N}{K}=N\dbinom{N-1}{K-1} \label{sol.sur2.oldoldexe}%
\end{equation}
for any $N\in\mathbb{Q}$ and any positive integer $K$. (The variables $N$ and
$K$ in this equality have been called $n$ and $k$ in the exercise we have
cited, but we are using the notations $n$ and $k$ for different purposes
here.) Furthermore, we know that%
\begin{equation}
\dbinom{N}{K}=\dfrac{N!}{K!\left(  N-K\right)  !} \label{sol.sur2.factfor}%
\end{equation}
for each $N\in\mathbb{N}$ and each $K\in\left\{  0,1,\ldots,N\right\}  $.

\textbf{(a)} From (\ref{sol.sur2.oldexe}), we obtain%
\begin{align*}
\operatorname*{sur}\left(  n,k\right)   &  =\sum_{i=0}^{k}\left(  -1\right)
^{k-i}\dbinom{k}{i}i^{n}=\left(  -1\right)  ^{k-0}\dbinom{k}{0}%
\underbrace{0^{n}}_{\substack{=0\\\text{(since }n\text{ is positive)}}%
}+\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{k}{i}i^{n}\\
&  =\underbrace{\left(  -1\right)  ^{k-0}\dbinom{k}{0}0}_{=0}+\sum_{i=1}%
^{k}\left(  -1\right)  ^{k-i}\dbinom{k}{i}i^{n}=\sum_{i=1}^{k}\left(
-1\right)  ^{k-i}\dbinom{k}{i}\underbrace{i^{n}}_{\substack{=ii^{n-1}%
\\\text{(since }n\text{ is positive)}}}\\
&  =\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\underbrace{\dbinom{k}{i}%
i}_{=i\dbinom{k}{i}}i^{n-1}=\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}%
\underbrace{i\dbinom{k}{i}}_{\substack{=k\dbinom{k-1}{i-1}\\\text{(by
(\ref{sol.sur2.oldoldexe}), applied}\\\text{to }N=k\text{ and }K=i\text{)}%
}}i^{n-1}\\
&  =\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}k\dbinom{k-1}{i-1}i^{n-1}%
=k\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i-1}i^{n-1}.
\end{align*}
Comparing this with%
\begin{align*}
&  k\underbrace{\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}%
{i-1}i^{n-1}}_{=\left(  -1\right)  ^{k-0}\dbinom{k-1}{0-1}0^{n-1}+\sum
_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i-1}i^{n-1}}\\
&  =k\left(  \left(  -1\right)  ^{k-0}\underbrace{\dbinom{k-1}{0-1}%
}_{\substack{=0\\\text{(since }0-1<0\text{)}}}0^{n-1}+\sum_{i=1}^{k}\left(
-1\right)  ^{k-i}\dbinom{k-1}{i-1}i^{n-1}\right) \\
&  =k\left(  \underbrace{\left(  -1\right)  ^{k-0}0\cdot0^{n-1}}_{=0}%
+\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i-1}i^{n-1}\right) \\
&  =k\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i-1}i^{n-1},
\end{align*}
we obtain%
\[
\operatorname*{sur}\left(  n,k\right)  =k\sum_{i=0}^{k}\left(  -1\right)
^{k-i}\dbinom{k-1}{i-1}i^{n-1}.
\]
This solves Exercise \ref{exe.sur2} \textbf{(a)}.

\textbf{(b)} We know from class that%
\begin{align*}%
%TCIMACRO{\QDATOPD{\{}{\}}{n}{k} }%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{n}{k}
%EndExpansion
&  =\dfrac{\operatorname*{sur}\left(  n,k\right)  }{k!}=\dfrac{1}%
{k!}\underbrace{\operatorname*{sur}\left(  n,k\right)  }_{\substack{=\sum
_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{k}{i}i^{n}\\\text{(by
(\ref{sol.sur2.oldexe}))}}}=\dfrac{1}{k!}\cdot\sum_{i=0}^{k}\left(  -1\right)
^{k-i}\underbrace{\dbinom{k}{i}}_{\substack{=\dfrac{k!}{i!\left(  k-i\right)
!}\\\text{(by (\ref{sol.sur2.factfor}), applied}\\\text{to }N=k\text{ and
}K=i\text{)}}}i^{n}\\
&  =\dfrac{1}{k!}\cdot\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dfrac
{k!}{i!\left(  k-i\right)  !}i^{n}=\underbrace{\dfrac{1}{k!}\cdot k!}_{=1}%
\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dfrac{1}{i!\left(  k-i\right)  !}%
i^{n}\\
&  =\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dfrac{1}{i!\left(  k-i\right)
!}i^{n}=\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dfrac{i^{n}}{i!\left(
k-i\right)  !}.
\end{align*}
This solves Exercise \ref{exe.sur2} \textbf{(b)}.
\end{proof}

\subsection{Counting $2$-lacunar subsets}

\begin{exercise}
\label{exe.2lac}A set $S$ of integers is said to be $2$\textit{-lacunar} if
every $i\in S$ satisfies $i+1\notin S$ and $i+2\notin S$. (That is, any two
distinct elements of $S$ are at least a distance of $3$ apart on the real
axis.) For example, $\left\{  1,5,8\right\}  $ is $2$-lacunar, but $\left\{
1,5,7\right\}  $ is not.

For any $n\in\mathbb{N}$, we let $h\left(  n\right)  $ denote the number of
all $2$-lacunar subsets of $\left[  n\right]  $.

\textbf{(a)} Prove that $h\left(  n\right)  =h\left(  n-1\right)  +h\left(
n-3\right)  $ for each $n\geq3$.

\textbf{(b)} Prove that $h\left(  n\right)  =\sum_{\substack{k\in
\mathbb{N};\\2k\leq n+2}}\dbinom{n+2-2k}{k}$ for each $n\in\mathbb{N}$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.2lac} (sketched).]Most of the arguments used in
this exercise are straightforward adaptations of arguments used in Exercise 4
\textbf{(b)} on \href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{Math
4990 homework set \#1} and in Exercise 3 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{Math 4990 homework
set \#2}. Thus, we shall be very brief this time, pointing out only the differences.

\textbf{(a)} Exercise \ref{exe.2lac} is solved in the same way as Exercise 4
\textbf{(b)} on \href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{Math
4990 homework set \#1} was solved. This time, of course, instead of finding a
bijection from $\left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is
lacunar and }n\in S\right\}  $ to $\left\{  S\subseteq\left[  n-2\right]
\ \mid\ S\text{ is lacunar}\right\}  $, we need to find a a bijection from
$\left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is }2\text{-lacunar and
}n\in S\right\}  $ to $\left\{  S\subseteq\left[  n-3\right]  \ \mid\ S\text{
is }2\text{-lacunar}\right\}  $. The bijection is defined in exactly the same
way as before: It sends each $T$ to $T\setminus\left\{  n\right\}  $.

\textbf{(b)} We begin with the following fact:

\begin{statement}
\textit{Observation 0:} Let $S$ be a $2$-lacunar subset of $\left[  n\right]
$. Then,%
\[
\left\vert S\right\vert \leq\dfrac{n+2}{3}.
\]

\end{statement}

[\textit{Proof of Observation 0:} Let $S^{\prime}$ be the subset $\left\{
s+1\ \mid\ s\in S\right\}  $ of $\left[  n+1\right]  $. Let $S^{\prime\prime}$
be the subset $\left\{  s+2\ \mid\ s\in S\right\}  $ of $\left[  n+2\right]
$. Both subsets $S^{\prime}$ and $S^{\prime\prime}$ are just copies of $S$,
shifted by $1$ and by $2$, respectively; thus, their sizes are the same as the
size of $S$: that is, we have $\left\vert S\right\vert =\left\vert S^{\prime
}\right\vert =\left\vert S^{\prime\prime}\right\vert $. Also, it is easy to
see that the three sets $S,S^{\prime},S^{\prime\prime}$ are
disjoint\footnote{\textit{Proof.} Let us just check that $S$ and
$S^{\prime\prime}$ are disjoint. (The other two statements are proven
similarly.)
\par
Indeed, let $j\in S\cap S^{\prime\prime}$. Then, $j\in S$ and $j\in
S^{\prime\prime}$. From $j\in S^{\prime\prime}$, it follows that $j=s+2$ for
some $s\in S$ (by the definition of $S^{\prime\prime}$). Consider this $s$.
Now, recall that every $i\in S$ satisfies $i+2\notin S$ (since $S$ is
$2$-lacunar). Applying this to $i=s$, we obtain $s+2\notin S$. This
contradicts $s+2=j\in S$.
\par
Now, forget that we fixed $j$. We thus have obtained a contradiction for each
$j\in S\cap S^{\prime\prime}$. Hence, there exists no $j\in S\cap
S^{\prime\prime}$. In other words, the sets $S$ and $S^{\prime\prime}$ are
disjoint.}. Hence, $\left\vert S\cup S^{\prime}\cup S^{\prime\prime
}\right\vert =\left\vert S\right\vert +\left\vert S^{\prime}\right\vert
+\left\vert S^{\prime\prime}\right\vert =3\left\vert S\right\vert $ (since
$\left\vert S\right\vert =\left\vert S^{\prime}\right\vert =\left\vert
S^{\prime\prime}\right\vert $). But $S$, $S^{\prime}$ and $S^{\prime\prime}$
are subsets of $\left[  n+2\right]  $; therefore, so is $S\cup S^{\prime}\cup
S^{\prime\prime}$. Hence, $\left\vert S\cup S^{\prime}\cup S^{\prime\prime
}\right\vert \leq\left\vert \left[  n+2\right]  \right\vert =n+2$. In view of
$\left\vert S\cup S^{\prime}\cup S^{\prime\prime}\right\vert =3\left\vert
S\right\vert $, this rewrites as $3\left\vert S\right\vert \leq n+2$, so that
$\left\vert S\right\vert \leq\dfrac{n+2}{3}$. This proves Observation 0.]

Next, we need to prove the following statement:

\begin{statement}
\textit{Observation 1:} Let $n\in\mathbb{N}$. For any $k\in\mathbb{N}$
satisfying $2k\leq n+2$, the number of all $2$-lacunar $k$-element subsets of
$\left[  n\right]  $ is $\dbinom{n-2k+2}{k}$.
\end{statement}

[\textit{Proof of Observation 1:} One way to prove this is analogous to the
first solution of Exercise 3 \textbf{(a)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{Math 4990 homework
set \#2}. The main differences are:

\begin{itemize}
\item The set $\operatorname*{Lac}\nolimits_{k}\left(  n\right)  $ of all
lacunar $k$-element subsets of $\left[  n\right]  $ is replaced by the set
$\operatorname*{Lac}\nolimits_{k,2}\left(  n\right)  $ of all $2$-lacunar
$k$-element subsets of $\left[  n\right]  $.

\item The maps $\Phi:\operatorname*{Lac}\nolimits_{k}\left(  n\right)
\rightarrow\mathcal{P}_{k}\left(  \left[  n-k+1\right]  \right)  $ and
$\Psi:\mathcal{P}_{k}\left(  \left[  n-k+1\right]  \right)  \rightarrow
\operatorname*{Lac}\nolimits_{k}\left(  n\right)  $ are replaced by maps
$\widetilde{\Phi}:\operatorname*{Lac}\nolimits_{k,2}\left(  n\right)
\rightarrow\mathcal{P}_{k}\left(  \left[  n-2k+2\right]  \right)  $ and
$\widetilde{\Psi}:\mathcal{P}_{k}\left(  \left[  n-2k+2\right]  \right)
\rightarrow\operatorname*{Lac}\nolimits_{k,2}\left(  n\right)  $ defined as
follows: $\widetilde{\Phi}$ sends any $S=\left\{  s_{1}<s_{2}<\cdots
<s_{k}\right\}  \in\operatorname*{Lac}\nolimits_{k,2}\left(  n\right)  $ to%
\[
\left\{  s_{1}-0<s_{2}-2<s_{3}-4<\cdots<s_{k}-2\left(  k-1\right)  \right\}
=\left\{  s_{i}-2\left(  i-1\right)  \ \mid\ i\in\left[  k\right]  \right\}
,
\]
whereas $\widetilde{\Psi}$ sends any $T=\left\{  t_{1}<t_{2}<\cdots
<t_{k}\right\}  \in\mathcal{P}_{k}\left(  \left[  n-2k+2\right]  \right)  $
to
\[
\left\{  t_{1}+0<t_{2}+2<t_{3}+4<\cdots<t_{k}+2\left(  k-1\right)  \right\}
=\left\{  t_{i}+2\left(  i-1\right)  \ \mid\ i\in\left[  k\right]  \right\}
.
\]
(In other words, instead of increasing/decreasing gaps between neighboring
elements of the subset by $1$, we are now increasing/decreasing them by $2$.)
\end{itemize}

Alternatively, Observation 1 can also be proven similarly to the second
solution of Exercise 3 \textbf{(a)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{Math 4990 homework
set \#2}. The analogue of Claim 1 should now state that $g_{k}\left(
n\right)  =g_{k}\left(  n-1\right)  +g_{k-1}\left(  n-3\right)  $ for all
$n\geq1$ and $k\in\mathbb{Z}$ (where $g_{k}\left(  n\right)  $ denotes the
number of all $2$-lacunar $k$-element subsets of $\left[  n\right]  $); and
the analogue of Claim 2 should now state that each $n\in\left\{
-2,-1,0,1,2,\ldots\right\}  $ and $k\in\mathbb{N}$ with $2k\leq n+2$ satisfy
$g_{k}\left(  n\right)  =\dbinom{n-2k+2}{k}$. (In the proof of Claim 2, the
case of $2k=m+2$ needs to be treated separately, in the same way as we had to
treat the case $k=m+1$ separately back in homework set \#2. This is slightly
harder this time, however. Observation 0 shows that a $k$-element $2$-lacunar
subset of $\left[  m\right]  $ must have size $k\leq\dfrac{m+2}{3}<\dfrac
{m+2}{2}$, whence it cannot satisfy $2k=m+2$ unless $m=-2$.)

Either way, Observation 1 is eventually proven.]

Now, we proceed similarly to the solution of Exercise 3 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{Math 4990 homework
set \#2}: Fix $n\in\mathbb{N}$. The size of any $2$-lacunar subset of $\left[
n\right]  $ is a $k\in\mathbb{N}$ satisfying $2k\leq n+2$ (because Observation
0 yields that it is $\leq\dfrac{n+2}{3}\leq\dfrac{n+2}{2}$). Now,%
\begin{align*}
h\left(  n\right)   &  =\left(  \text{the number of all }2\text{-lacunar
subsets of }\left[  n\right]  \right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }h\left(  n\right)
\right) \\
&  =\sum_{\substack{k\in\mathbb{N};\\2k\leq n+2}}\underbrace{\left(  \text{the
number of all }2\text{-lacunar subsets of }\left[  n\right]  \text{ having
size }k\right)  }_{\substack{=\left(  \text{the number of all }2\text{-lacunar
}k\text{-element subsets of }\left[  n\right]  \right)  \\=\dbinom{n-2k+2}%
{k}\\\text{(by Observation 1)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because the size of any }2\text{-lacunar subset of }\left[  n\right] \\
\text{is a }k\in\mathbb{N}\text{ satisfying }2k\leq n+2
\end{array}
\right) \\
&  =\sum_{\substack{k\in\mathbb{N};\\2k\leq n+2}}\dbinom{n-2k+2}{k}%
=\sum_{\substack{k\in\mathbb{N};\\2k\leq n+2}}\dbinom{n+2-2k}{k}.
\end{align*}
This solves Exercise \ref{exe.2lac} \textbf{(b)}.
\end{proof}

\subsection{Counting shadowed subsets}

\begin{exercise}
\label{exe.if2i}A set $S$ of integers is said to be \textit{shadowed} if it
has the following property: Whenever an \textbf{odd} integer $i$ belongs to
$S$, the next integer $i+1$ must also belong to $S$. (For example,
$\varnothing$, $\left\{  2,4\right\}  $ and $\left\{  1,2,5,6,8\right\}  $ are
shadowed, but $\left\{  1,5,6\right\}  $ is not, since $1$ belongs to
$\left\{  1,5,6\right\}  $ but $2$ does not.)

\textbf{(a)} Let $n\in\mathbb{N}$ be even. How many shadowed subsets of
$\left[  n\right]  $ exist?

\textbf{(b)} Let $n\in\mathbb{N}$ be odd. How many shadowed subsets of
$\left[  n\right]  $ exist?
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.if2i} (sketched).]\textbf{(a)} The number of
shadowed subsets of $\left[  n\right]  $ is $3^{n/2}$.

\textit{Proof.} Here is an informal argument:

The definition of a \textquotedblleft shadowed\textquotedblright\ set can be
rewritten as follows: A set $S$ of integers is shadowed if and only if, for
each integer $i$, it either contains \textbf{none} of the two integers $2i-1$
and $2i$, or it contains $2i$ \textbf{but not} $2i-1$, or it contains
\textbf{both} $2i-1$ and $2i$. (What it cannot do is contain $2i-1$ but not
$2i$.) When we are studying subsets of $\left[  n\right]  $, we can restrict
ourselves to only considering the integers $i\in\left[  n/2\right]  $, because
each of the elements of $\left[  n\right]  $ can be uniquely represented in
the form $2i-1$ or in the form $2i$ for some $i\in\left[  n/2\right]  $. Thus,
a subset $S$ of $\left[  n\right]  $ is shadowed if and only if, for each
$i\in\left[  n/2\right]  $, it either contains \textbf{none} of the two
integers $2i-1$ and $2i$, or it contains $2i$ \textbf{but not} $2i-1$, or it
contains \textbf{both} $2i-1$ and $2i$. Furthermore, if we know for each
$i\in\left[  n/2\right]  $ which of these three options it satisfies, then we
know the whole subset $S$.

Thus, the following simple algorithm constructs every shadowed subset of
$\left[  n\right]  $: For each $i\in\left[  n/2\right]  $, we decide whether
our subset should contain \textbf{none} of the two integers $2i-1$ and $2i$,
or it should contain $2i$ \textbf{but not} $2i-1$, or it should contain
\textbf{both} $2i-1$ and $2i$. There are clearly $3$ options to choose from in
this decision. Thus, in total, there are $3^{n/2}$ possible shadowed subsets
of $\left[  n\right]  $ (because we are making this decision once for each of
the $n/2$ elements $i$ of $\left[  n/2\right]  $). This completes our informal proof.

This argument can be translated into a formal proof (by bijection) in the same
way as this was done in our solution to Exercise \ref{exe.ABC} \textbf{(a)}
above. Let me be very brief: Let $\mathfrak{A}$ be the set of all shadowed
subsets of $\left[  n\right]  $. We must show that $\left\vert \mathfrak{A}%
\right\vert =3^{n/2}$. It will suffice to exhibit a bijection $\mathfrak{A}%
\rightarrow\left[  3\right]  ^{\left[  n/2\right]  }$.

We define such a bijection $\Xi:\mathfrak{A}\rightarrow\left[  3\right]
^{\left[  n/2\right]  }$ as follows: It should send any shadowed subset $S$ of
$\left[  n\right]  $ to the map $f:\left[  n/2\right]  \rightarrow\left[
3\right]  $ that sends each $i\in\left[  n/2\right]  $ to
\[%
\begin{cases}
1, & \text{if }S\text{ contains \textbf{none} of }2i-1\text{ and }2i;\\
2, & \text{if }S\text{ contains }2i\text{ \textbf{but not }}2i-1;\\
3, & \text{if }S\text{ contains \textbf{both} }2i-1\text{ and }2i
\end{cases}
.
\]
The reader can easily check that this $\Xi$ is well-defined and has an
inverse, and that completes the proof.

\textbf{(b)} The number of shadowed subsets of $\left[  n\right]  $ is
$3^{\left(  n-1\right)  /2}$.

\textit{Proof.} We know that $n\neq0$ (since $n$ is odd); thus, $n$ is a
positive integer (since $n\in\mathbb{N}$). Hence, $n-1\in\mathbb{N}$.
Moreover, $n-1$ is even (since $n$ is odd). Hence, Exercise \ref{exe.if2i}
\textbf{(a)} (applied to $n-1$ instead of $n$) shows that the number of
shadowed subsets of $\left[  n-1\right]  $ is $3^{\left(  n-1\right)  /2}$.

But any shadowed subset of $\left[  n\right]  $ must be a subset of $\left[
n-1\right]  $\ \ \ \ \footnote{\textit{Proof.} Let $S$ be a shadowed subset of
$\left[  n\right]  $. We must show that $S$ is a subset of $\left[
n-1\right]  $.
\par
We know that $S$ is shadowed. In other words, whenever an \textbf{odd} integer
$i$ belongs to $S$, the next integer $i+1$ must also belong to $S$. Applying
this to $i=n$, we conclude that if $n$ belongs to $S$, then $n+1$ must also
belong to $S$ (since $n$ is an odd integer). Therefore, $n$ cannot belong to
$S$ (since $n+1$ cannot belong to $S$ (because $S$ is a subset of $\left[
n\right]  $, and $n+1$ does not belong to $\left[  n\right]  $)). Therefore,
$S$ is a subset of $\left[  n\right]  \setminus\left\{  n\right\}  =\left[
n-1\right]  $. Qed.}. Hence, the shadowed subsets of $\left[  n\right]  $ are
precisely the shadowed subsets of $\left[  n-1\right]  $; consequently, their
number is $3^{\left(  n-1\right)  /2}$ (because we have just shown that the
number of shadowed subsets of $\left[  n-1\right]  $ is $3^{\left(
n-1\right)  /2}$). This completes the proof.
\end{proof}

\subsection{Counting smords (Smirnov words, or Carlitz words)}

\begin{exercise}
\label{exe.swords}Let $n$ and $k$ be positive integers. A $k$\textit{-smord}
will mean a $k$-tuple $\left(  a_{1},a_{2},\ldots,a_{k}\right)  \in\left[
n\right]  ^{k}$ such that no two consecutive entries of the $k$-tuple are
equal (i.e., we have $a_{i}\neq a_{i+1}$ for all $i\in\left[  k-1\right]  $).
For example, $\left(  3,1,3,2\right)  $ is a $4$-smord (when $n\geq3$), but
$\left(  1,3,3,2\right)  $ is not.

\textbf{(a)} Compute the number of all $k$-smords.

\textbf{(b)} A $k$-smord $\left(  a_{1},a_{2},\ldots,a_{k}\right)  $ is said
to be \textit{rounded} if it furthermore satisfies $a_{k}\neq a_{1}$. Compute
the number of all rounded $k$-smords.
\end{exercise}

Before I come to the solution of this exercise, let me quickly comment on
where it comes from. What I call \textquotedblleft$k$-smords\textquotedblright%
\ in Exercise \ref{exe.swords} is usually called \textquotedblleft%
\textit{Smirnov words}\textquotedblright\footnote{I have abbreviated this to
\textquotedblleft smords\textquotedblright\ in the exercise to make it harder
to google. The definition of \textquotedblleft smord\textquotedblright\ in
Urban Dictionary is an (unintended) red herring.} or \textquotedblleft%
\textit{Carlitz words}\textquotedblright\ (of length $k$, over the alphabet
$\left[  n\right]  $). Generally, combinatorialists often use the word
\textquotedblleft word of length $k$ over an alphabet $A$\textquotedblright%
\ as a synonym for \textquotedblleft$k$-tuple of elements of $A$%
\textquotedblright, with no linguistic or semantic connotations in mind.

The exercise, however, has a deeper significance in combinatorics: It provides
two simple examples for the computation of a \textit{chromatic polynomial}. I
hope we will come to see the general case in class.

\begin{noncompile}
TODO: Say more about chromatic polynomials!
\end{noncompile}

\begin{proof}
[Solution to Exercise \ref{exe.swords} (sketched).]\textbf{(a)} The number of
all $k$-smords is $n\left(  n-1\right)  ^{k-1}$.

\textit{Proof.} A $k$-smord is simply a $k$-tuple of elements of $\left[
n\right]  $ such that each entry (apart from the first) is distinct from the
previous entry. Thus, the following algorithm constructs each $k$-smord:

\begin{itemize}
\item First, choose the first entry of the $k$-smord. There are $n$ choices here.

\item Then, choose the second entry of the $k$-smord. There are $n-1$ choices
for this, because it has to be distinct from the previous entry.

\item Then, choose the third entry of the $k$-smord. There are $n-1$ choices
for this, because it has to be distinct from the previous entry.

\item And so on, until all entries have been chosen.
\end{itemize}

Thus, in total, there are
\[
n\underbrace{\left(  n-1\right)  \left(  n-1\right)  \cdots\left(  n-1\right)
}_{k-1\text{ times}}=n\left(  n-1\right)  ^{k-1}%
\]
ways to perform this algorithm. Hence, the number of all $k$-smords is
$n\left(  n-1\right)  ^{k-1}$.

\textbf{(b)} The number of all rounded $k$-smords is $\left(  n-1\right)
^{k}+\left(  -1\right)  ^{k}\left(  n-1\right)  $.

\textit{Proof.} Let $r_{k}\left(  n\right)  $ denote the number of all rounded
$k$-smords. We must prove that%
\begin{equation}
r_{k}\left(  n\right)  =\left(  n-1\right)  ^{k}+\left(  -1\right)
^{k}\left(  n-1\right)  . \label{sol.swords.b.claim}%
\end{equation}


Let us forget that we fixed $k$. We shall now prove (\ref{sol.swords.b.claim})
by induction over $k$:

\textit{Induction base:} A $1$-smord $\left(  a\right)  $ is rounded if and
only if it satisfies $a\neq a$ (by the definition of \textquotedblleft
rounded\textquotedblright); thus, there exist no rounded $1$-smords (because
$a\neq a$ never holds). Hence, the number of all rounded $1$-smords is $0$. In
other words, $r_{1}\left(  n\right)  =0$ (since $r_{1}\left(  n\right)  $ was
defined to be the number of all rounded $1$-smords). Comparing this with
$\left(  n-1\right)  ^{1}+\left(  -1\right)  ^{1}\left(  n-1\right)  =0$, we
obtain $r_{1}\left(  n\right)  =\left(  n-1\right)  ^{1}+\left(  -1\right)
^{1}\left(  n-1\right)  $. In other words, (\ref{sol.swords.b.claim}) holds
for $k=1$. This completes the induction base.

\textit{Induction step:} You have seen lots of induction steps by now, so let
me take away one piece of railing for the sake of brevity. Namely, instead of
stepping \textquotedblleft from $k=m$ to $k=m+1$\textquotedblright, I shall
simply \textquotedblleft step from $k$ to $k+1$\textquotedblright. This is
just a matter of notation, which at this point should not be too confusing any longer.

So let $k$ be a positive integer, and assume (as our induction hypothesis)
that (\ref{sol.swords.b.claim}) holds \textquotedblleft for this particular
$k$\textquotedblright\ (that is, we have $r_{k}\left(  n\right)  =\left(
n-1\right)  ^{k}+\left(  -1\right)  ^{k}\left(  n-1\right)  $). Then, we must
show that (\ref{sol.swords.b.claim}) holds \textquotedblleft for $k+1$ as
well\textquotedblright\ (that is, we must show that $r_{k+1}\left(  n\right)
=\left(  n-1\right)  ^{k+1}+\left(  -1\right)  ^{k+1}\left(  n-1\right)  $).

We say that a $\left(  k+1\right)  $-smord is \textit{non-rounded} if it is
not rounded. (Duh.)

Exercise \ref{exe.swords} \textbf{(a)} (applied to $k+1$ instead of $k$) shows
that the number of all $\left(  k+1\right)  $-smords is $n\left(  n-1\right)
^{\left(  k+1\right)  -1}=n\left(  n-1\right)  ^{k}$. Hence,%
\begin{align}
n\left(  n-1\right)  ^{k}  &  =\left(  \text{the number of all }\left(
k+1\right)  \text{-smords}\right) \nonumber\\
&  =\left(  \text{the number of all rounded }\left(  k+1\right)
\text{-smords}\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{the number of all non-rounded }\left(
k+1\right)  \text{-smords}\right)  . \label{sol.swords.b.3}%
\end{align}
We shall now find the number of all non-rounded $\left(  k+1\right)  $-smords.

A $\left(  k+1\right)  $-smord $\left(  a_{1},a_{2},\ldots,a_{k+1}\right)  $
is rounded if and only if it satisfies $a_{k+1}\neq a_{1}$ (by the definition
of \textquotedblleft rounded\textquotedblright). Hence, a $\left(  k+1\right)
$-smord $\left(  a_{1},a_{2},\ldots,a_{k+1}\right)  $ is non-rounded if and
only if it satisfies $a_{k+1}=a_{1}$. Thus, a non-rounded $\left(  k+1\right)
$-smord $\left(  a_{1},a_{2},\ldots,a_{k+1}\right)  $ is uniquely determined
by its first $k$ entries $a_{1},a_{2},\ldots,a_{k}$. Moreover, these first $k$
entries must themselves form a $k$-smord (since $a_{i}\neq a_{i+1}$ holds for
all $i\in\left[  k\right]  $ and therefore also for all $i\in\left[
k-1\right]  $), and this $k$-smord $\left(  a_{1},a_{2},\ldots,a_{k}\right)  $
is rounded (because $a_{i}\neq a_{i+1}$ for all $i\in\left[  k\right]  $,
whence $a_{k}\neq a_{k+1}=a_{1}$, but this says precisely that the $k$-smord
$\left(  a_{1},a_{2},\ldots,a_{k}\right)  $ is rounded). Hence, we can define
a map%
\begin{align*}
\phi:\left\{  \text{non-rounded }\left(  k+1\right)  \text{-smords}\right\}
&  \rightarrow\left\{  \text{rounded }k\text{-smords}\right\}  ,\\
\left(  a_{1},a_{2},\ldots,a_{k+1}\right)   &  \mapsto\left(  a_{1}%
,a_{2},\ldots,a_{k}\right)  .
\end{align*}
Conversely, if $\left(  a_{1},a_{2},\ldots,a_{k}\right)  $ is a rounded
$k$-smord, then $\left(  a_{1},a_{2},\ldots,a_{k},a_{1}\right)  $ is a
non-rounded $\left(  k+1\right)  $-smord (in fact, it is a $\left(
k+1\right)  $-smord because the roundedness of $\left(  a_{1},a_{2}%
,\ldots,a_{k}\right)  $ leads to $a_{k}\neq a_{1}$; and it is non-rounded
because $a_{1}=a_{1}$). Thus, we can define a map%
\begin{align*}
\psi:\left\{  \text{rounded }k\text{-smords}\right\}   &  \rightarrow\left\{
\text{non-rounded }\left(  k+1\right)  \text{-smords}\right\}  ,\\
\left(  a_{1},a_{2},\ldots,a_{k}\right)   &  \mapsto\left(  a_{1},a_{2}%
,\ldots,a_{k},a_{1}\right)  .
\end{align*}
The two maps $\phi$ and $\psi$ are mutually inverse (to check this, just
remember that any non-rounded $\left(  k+1\right)  $-smord $\left(
a_{1},a_{2},\ldots,a_{k+1}\right)  $ must satisfy $a_{k+1}=a_{1}$, so it is
identical with $\left(  a_{1},a_{2},\ldots,a_{k},a_{1}\right)  $), and thus
are bijections. Hence, we have found a bijection from $\left\{
\text{non-rounded }\left(  k+1\right)  \text{-smords}\right\}  $ to $\left\{
\text{rounded }k\text{-smords}\right\}  $ (namely, $\phi$). Therefore,%
\begin{align*}
&  \left(  \text{the number of all non-rounded }\left(  k+1\right)
\text{-smords}\right) \\
&  =\left(  \text{the number of all rounded }k\text{-smords}\right)  .
\end{align*}
Thus, (\ref{sol.swords.b.3}) becomes%
\begin{align*}
n\left(  n-1\right)  ^{k}  &  =\underbrace{\left(  \text{the number of all
rounded }\left(  k+1\right)  \text{-smords}\right)  }_{\substack{=r_{k+1}%
\left(  n\right)  \\\text{(since }r_{k+1}\left(  n\right)  \text{ is defined
as the number of all rounded }\left(  k+1\right)  \text{-smords)}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of all
non-rounded }\left(  k+1\right)  \text{-smords}\right)  }_{\substack{=\left(
\text{the number of all rounded }k\text{-smords}\right)  =r_{k}\left(
n\right)  \\\text{(since }r_{k}\left(  n\right)  \text{ is defined as the
number of all rounded }k\text{-smords)}}}\\
&  =r_{k+1}\left(  n\right)  +r_{k}\left(  n\right)  .
\end{align*}
Therefore,%
\begin{align*}
r_{k+1}\left(  n\right)   &  =n\left(  n-1\right)  ^{k}-\underbrace{r_{k}%
\left(  n\right)  }_{\substack{=\left(  n-1\right)  ^{k}+\left(  -1\right)
^{k}\left(  n-1\right)  \\\text{(by the induction hypothesis)}}}=n\left(
n-1\right)  ^{k}-\left(  \left(  n-1\right)  ^{k}+\left(  -1\right)
^{k}\left(  n-1\right)  \right) \\
&  =\underbrace{n\left(  n-1\right)  ^{k}-\left(  n-1\right)  ^{k}}_{=\left(
n-1\right)  \left(  n-1\right)  ^{k}=\left(  n-1\right)  ^{k+1}}%
-\underbrace{\left(  -1\right)  ^{k}}_{=-\left(  -1\right)  ^{k+1}}\left(
n-1\right)  =\left(  n-1\right)  ^{k+1}-\left(  \left(  -1\right)
^{k+1}\right)  \left(  n-1\right) \\
&  =\left(  n-1\right)  ^{k+1}+\left(  -1\right)  ^{k+1}\left(  n-1\right)  .
\end{align*}
In other words, (\ref{sol.swords.b.claim}) holds \textquotedblleft for $k+1$
as well\textquotedblright. This completes the induction step. Thus, the
induction proof of (\ref{sol.swords.b.claim}) is finished, and with it the
solution of Exercise \ref{exe.swords} \textbf{(b)}.
\end{proof}

\subsection{Necklaces 2: rotational equivalence of tuples}

Let us recall a basic property of maps (proven in Exercise 6 \textbf{(a)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{Math 4990 homework
set \#2}): If $S$ is a set, and if $f:S\rightarrow S$ a map, then%
\begin{equation}
f^{n}\circ f^{m}=f^{n+m} \label{eq.fnfm}%
\end{equation}
for each $n,m\in\mathbb{N}$.

\begin{exercise}
\label{exe.periodic.2}This continues Exercise 7 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{Math 4990 homework
set \#2}.

Let $n$ be a positive integer. Let $X$ be a set.

We define a map $c:X^{n}\rightarrow X^{n}$ by
\[
c\left(  x_{1},x_{2},\ldots,x_{n}\right)  =\left(  x_{2},x_{3},\ldots
,x_{n},x_{1}\right)  \ \ \ \ \ \ \ \ \ \ \text{for all }\left(  x_{1}%
,x_{2},\ldots,x_{n}\right)  \in X^{n}.
\]
(In other words, the map $c$ transforms any $n$-tuple $\left(  x_{1}%
,x_{2},\ldots,x_{n}\right)  \in X^{n}$ by \textquotedblleft
rotating\textquotedblright\ it one step to the left, or, equivalently, moving
its first entry to the last position.)

For two $n$-tuples $\mathbf{x}$ and $\mathbf{y}$, we say that $\mathbf{x}%
\sim\mathbf{y}$ if there exists some $k\in\mathbb{N}$ such that $\mathbf{y}%
=c^{k}\left(  \mathbf{x}\right)  $. (For example, $\left(  1,5,2,4\right)
\sim\left(  2,4,1,5\right)  $, because $\left(  2,4,1,5\right)  =c^{2}\left(
1,5,2,4\right)  $.)

\textbf{(a)} Prove that $\sim$ is an equivalence relation, i.e., is reflexive,
transitive and symmetric. (For example, symmetry boils down to showing that if
there exists some $k\in\mathbb{N}$ satisfying $\mathbf{y}=c^{k}\left(
\mathbf{x}\right)  $, then there exists some $\ell\in\mathbb{N}$ satisfying
$\mathbf{x}=c^{\ell}\left(  \mathbf{y}\right)  $.)

\textbf{(b)} An $n$\textit{-necklace} (over $X$) shall mean a $\sim
$-equivalence class. We denote the $\sim$-equivalence class of a tuple
$\mathbf{x}\in X^{n}$ by $\left[  \mathbf{x}\right]  _{\sim}$.

Let $\mathbf{x}\in X^{n}$ be an $n$-tuple. Let $m$ be the smallest nonzero
period of the $n$-tuple $\mathbf{x}\in X^{n}$.

Prove that $\left[  \mathbf{x}\right]  _{\sim}=\left\{  c^{0}\left(
\mathbf{x}\right)  ,c^{1}\left(  \mathbf{x}\right)  ,\ldots,c^{m-1}\left(
\mathbf{x}\right)  \right\}  $.

\textbf{(c)} Show that the $m$ tuples $c^{0}\left(  \mathbf{x}\right)
,c^{1}\left(  \mathbf{x}\right)  ,\ldots,c^{m-1}\left(  \mathbf{x}\right)  $
are distinct. Conclude that $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =m$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.periodic.2}.]Before we properly start solving
this exercise, let us make some basic observations:

\begin{statement}
\textit{Observation 1:} We have $c^{n}\left(  \mathbf{x}\right)  =\mathbf{x}$
for each $\mathbf{x}\in X^{n}$.
\end{statement}

[\textit{Proof of Observation 1:} Let $\mathbf{x}\in X^{n}$. We have proven
$c^{n}\left(  \mathbf{x}\right)  =\mathbf{x}$ during our solution to Exercise
7 \textbf{(d)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{Math 4990 homework
set \#2}. Thus, Observation 1 follows.]

\begin{statement}
\textit{Observation 2:} Let $\mathbf{x}\in X^{n}$. Let $p\in\mathbb{N}$ be
such that $c^{p}\left(  \mathbf{x}\right)  =\mathbf{x}$. Then, $c^{kp}\left(
\mathbf{x}\right)  =\mathbf{x}$ for each $k\in\mathbb{N}$.
\end{statement}

[\textit{Proof of Observation 2:} Observation 2 is intuitively obvious: All it
says is that if applying the map $c$ to $\mathbf{x}$ a total of $p$ times
brings you back to $\mathbf{x}$, then applying the map $c$ to $\mathbf{x}$ a
total of $kp$ times brings you back to $\mathbf{x}$ as well. This intuition
can easily be translated into a rigorous argument:

We shall prove Observation 2 by induction over $k$:

\textit{Induction base:} We have $c^{0p}=c^{0}=\operatorname*{id}%
\nolimits_{X^{n}}$, so that $c^{0p}\left(  \mathbf{x}\right)
=\operatorname*{id}\nolimits_{X^{n}}\left(  \mathbf{x}\right)  =\mathbf{x}$.
Thus, Observation 2 holds for $k=0$. This completes the induction base.

\textit{Induction step:} Let $m\in\mathbb{N}$. Assume that Observation 2 holds
for $k=m$. We must prove that Observation 2 holds for $k=m+1$.

Let $\mathbf{x}\in X^{n}$. Let $p\in\mathbb{N}$ be such that $c^{p}\left(
\mathbf{x}\right)  =\mathbf{x}$. Then, $c^{mp}\left(  \mathbf{x}\right)
=\mathbf{x}$ (since Observation 2 holds for $k=m$). But (\ref{eq.fnfm})
(applied to $X^{n}$, $c$, $mp$ and $p$ instead of $S$, $f$, $n$ and $m$)
yields $c^{mp}\circ c^{p}=c^{mp+p}=c^{\left(  m+1\right)  p}$. Hence, $\left(
c^{mp}\circ c^{p}\right)  \left(  \mathbf{x}\right)  =c^{\left(  m+1\right)
p}\left(  \mathbf{x}\right)  $, and therefore%
\[
c^{\left(  m+1\right)  p}\left(  \mathbf{x}\right)  =\left(  c^{mp}\circ
c^{p}\right)  \left(  \mathbf{x}\right)  =c^{mp}\left(  \underbrace{c^{p}%
\left(  \mathbf{x}\right)  }_{=\mathbf{x}}\right)  =c^{mp}\left(
\mathbf{x}\right)  =\mathbf{x}.
\]
In other words, Observation 2 holds for $k=m+1$. This completes the induction
step. Thus, Observation 2 is proven.]

Now, we must show that $\sim$ is an equivalence relation. Indeed, the relation
$\sim$ is reflexive\footnote{\textit{Proof.} Let $\mathbf{x}\in X^{n}$. We
shall show that $\mathbf{x}\sim\mathbf{x}$.
\par
Indeed, $c^{0}=\operatorname*{id}\nolimits_{X^{n}}$, so that $c^{0}\left(
\mathbf{x}\right)  =\operatorname*{id}\nolimits_{X^{n}}\left(  \mathbf{x}%
\right)  =\mathbf{x}$. Hence, there exists some $k\in\mathbb{N}$ such that
$\mathbf{x}=c^{k}\left(  \mathbf{x}\right)  $ (namely, $k=0$). In other words,
$\mathbf{x}\sim\mathbf{x}$ (by the definition of the relation $\sim$).
\par
Now, forget that we fixed $\mathbf{x}$. We thus have shown that every
$\mathbf{x}\in X^{n}$ satisfies $\mathbf{x}\sim\mathbf{x}$. In other words,
the relation $\sim$ is reflexive.}, symmetric\footnote{\textit{Proof.} Let
$\mathbf{x}\in X^{n}$ and $\mathbf{y}\in X^{n}$ be such that $\mathbf{x}%
\sim\mathbf{y}$. We shall show that $\mathbf{y}\sim\mathbf{x}$.
\par
Indeed, we have $\mathbf{x}\sim\mathbf{y}$. In other words, there exists some
$k\in\mathbb{N}$ such that $\mathbf{y}=c^{k}\left(  \mathbf{x}\right)  $ (by
the definition of the relation $\sim$). Consider such a $k$, and denote it by
$u$. Thus, $u\in\mathbb{N}$ satisfies $\mathbf{y}=c^{u}\left(  \mathbf{x}%
\right)  $.
\par
Observation 1 yields $c^{n}\left(  \mathbf{x}\right)  =\mathbf{x}$. Hence,
Observation 2 (applied to $p=n$ and $k=u$) yields $c^{un}\left(
\mathbf{x}\right)  =\mathbf{x}$. But $n$ is positive; hence, $n\geq1$ and thus
$un\geq u1=u$. Hence, $un-u\in\mathbb{N}$. Applying (\ref{eq.fnfm}) to $X^{n}%
$, $c$, $un-u$ and $u$ instead of $S$, $f$, $n$ and $m$, we obtain
$c^{un-u}\circ c^{u}=c^{\left(  un-u\right)  +u}=c^{un}$. Thus, $\left(
c^{un-u}\circ c^{u}\right)  \left(  \mathbf{x}\right)  =c^{un}\left(
\mathbf{x}\right)  =\mathbf{x}$. Hence, $\mathbf{x}=\left(  c^{un-u}\circ
c^{u}\right)  \left(  \mathbf{x}\right)  =c^{un-u}\left(  \underbrace{c^{u}%
\left(  \mathbf{x}\right)  }_{=\mathbf{y}}\right)  =c^{un-u}\left(
\mathbf{y}\right)  $. Thus, there exists some $k\in\mathbb{N}$ such that
$\mathbf{x}=c^{k}\left(  \mathbf{y}\right)  $ (namely, $k=un-u$). In other
words, $\mathbf{y}\sim\mathbf{x}$ (by the definition of the relation $\sim$).
\par
Now, forget that we fixed $\mathbf{x}$ and $\mathbf{y}$. We thus have shown
that if $\mathbf{x}\in X^{n}$ and $\mathbf{y}\in X^{n}$ satisfy $\mathbf{x}%
\sim\mathbf{y}$, then $\mathbf{y}\sim\mathbf{x}$. In other words, the relation
$\sim$ is symmetric.} and transitive\footnote{\textit{Proof.} Let
$\mathbf{x}\in X^{n}$, $\mathbf{y}\in X^{n}$ and $\mathbf{z}\in X^{n}$ be such
that $\mathbf{x}\sim\mathbf{y}$ and $\mathbf{y}\sim\mathbf{z}$. We shall show
that $\mathbf{x}\sim\mathbf{z}$.
\par
Indeed, we have $\mathbf{x}\sim\mathbf{y}$. In other words, there exists some
$k\in\mathbb{N}$ such that $\mathbf{y}=c^{k}\left(  \mathbf{x}\right)  $ (by
the definition of the relation $\sim$). Consider such a $k$, and denote it by
$u$. Thus, $u\in\mathbb{N}$ satisfies $\mathbf{y}=c^{u}\left(  \mathbf{x}%
\right)  $.
\par
Also, we have $\mathbf{y}\sim\mathbf{z}$. In other words, there exists some
$k\in\mathbb{N}$ such that $\mathbf{z}=c^{k}\left(  \mathbf{y}\right)  $ (by
the definition of the relation $\sim$). Consider such a $k$, and denote it by
$v$. Thus, $v\in\mathbb{N}$ satisfies $\mathbf{z}=c^{v}\left(  \mathbf{y}%
\right)  $.
\par
Applying (\ref{eq.fnfm}) to $X^{n}$, $c$, $v$ and $u$ instead of $S$, $f$, $n$
and $m$, we obtain $c^{v}\circ c^{u}=c^{v+u}$. Thus, $\left(  c^{v}\circ
c^{u}\right)  \left(  \mathbf{x}\right)  =c^{v+u}\left(  \mathbf{x}\right)  $.
In view of $\left(  c^{v}\circ c^{u}\right)  \left(  \mathbf{x}\right)
=c^{v}\left(  \underbrace{c^{u}\left(  \mathbf{x}\right)  }_{=\mathbf{y}%
}\right)  =c^{v}\left(  \mathbf{y}\right)  =\mathbf{z}$, this rewrites as
$\mathbf{z}=c^{v+u}\left(  \mathbf{x}\right)  $. Thus, there exists some
$k\in\mathbb{N}$ such that $\mathbf{z}=c^{k}\left(  \mathbf{x}\right)  $
(namely, $k=v+u$). In other words, $\mathbf{x}\sim\mathbf{z}$ (by the
definition of the relation $\sim$).
\par
Now, forget that we fixed $\mathbf{x}$, $\mathbf{y}$ and $\mathbf{z}$. We thus
have shown that if $\mathbf{x}\in X^{n}$, $\mathbf{y}\in X^{n}$ and
$\mathbf{z}\in X^{n}$ satisfy $\mathbf{x}\sim\mathbf{y}$ and $\mathbf{y}%
\sim\mathbf{z}$, then $\mathbf{x}\sim\mathbf{z}$. In other words, the relation
$\sim$ is transitive.}. In other words, the relation $\sim$ is an equivalence
relation. This solves Exercise \ref{exe.periodic.2} \textbf{(a)}.

\textbf{(b)} The number $m$ is the smallest nonzero period of the $n$-tuple
$\mathbf{x}\in X^{n}$. In particular, $m$ is a period of $\mathbf{x}$. In
other words, $m\in\mathbb{N}$ and $c^{m}\left(  \mathbf{x}\right)
=\mathbf{x}$.

The definition of the equivalence class $\left[  \mathbf{x}\right]  _{\sim}$
of $\mathbf{x}$ shows that
\begin{equation}
\left[  \mathbf{x}\right]  _{\sim}=\left\{  \mathbf{y}\in X^{n}\ \mid
\ \mathbf{y}\sim\mathbf{x}\right\}  . \label{sol.periodic.2.b.eqclass}%
\end{equation}


Let $S$ denote the set $\left\{  c^{0}\left(  \mathbf{x}\right)  ,c^{1}\left(
\mathbf{x}\right)  ,\ldots,c^{m-1}\left(  \mathbf{x}\right)  \right\}  $.
Then, $S\subseteq\left[  \mathbf{x}\right]  _{\sim}$%
\ \ \ \ \footnote{\textit{Proof.} Let $\mathbf{s}\in S$. Then, $\mathbf{s}\in
S=\left\{  c^{0}\left(  \mathbf{x}\right)  ,c^{1}\left(  \mathbf{x}\right)
,\ldots,c^{m-1}\left(  \mathbf{x}\right)  \right\}  $. In other words,
$\mathbf{s}=c^{i}\left(  \mathbf{x}\right)  $ for some $i\in\left\{
0,1,\ldots,m-1\right\}  $. Consider this $i$.
\par
Hence, $\mathbf{s}\in X^{n}$. Furthermore, there exists some $k\in\mathbb{N}$
such that $\mathbf{s}=c^{k}\left(  \mathbf{x}\right)  $ (namely, $k=i$). In
other words, $\mathbf{x}\sim\mathbf{s}$ (by the definition of the relation
$\sim$). Hence, $\mathbf{s}\sim\mathbf{x}$ (since the relation $\sim$ is
symmetric). Therefore, $\mathbf{s}\in\left\{  \mathbf{y}\in X^{n}%
\ \mid\ \mathbf{y}\sim\mathbf{x}\right\}  $. In light of
(\ref{sol.periodic.2.b.eqclass}), this rewrites as $\mathbf{s}\in\left[
\mathbf{x}\right]  _{\sim}$.
\par
Now, forget that we fixed $\mathbf{s}$. We thus have shown that $\mathbf{s}%
\in\left[  \mathbf{x}\right]  _{\sim}$ for each $\mathbf{s}\in S$. In other
words, $S\subseteq\left[  \mathbf{x}\right]  _{\sim}$.}.

On the other hand, we claim the following:

\begin{statement}
\textit{Observation 3:} We have $c^{k}\left(  \mathbf{x}\right)  \in S$ for
each $k\in\mathbb{N}$.
\end{statement}

[\textit{Proof of Observation 3:} We proceed by strong induction over $k$:

\textit{Induction step:} Let $h\in\mathbb{N}$. Assume that Observation 3 holds
whenever $k<h$. We now must prove that Observation 3 holds for $k=h$. In other
words, we must prove that $c^{h}\left(  \mathbf{x}\right)  \in S$.

If $h<m$, then this is obvious\footnote{\textit{Proof.} Assume that $h<m$.
Thus, $h\in\left\{  0,1,\ldots,m-1\right\}  $ (since $h\in\mathbb{N}$), and
thus $c^{h}\left(  \mathbf{x}\right)  \in\left\{  c^{0}\left(  \mathbf{x}%
\right)  ,c^{1}\left(  \mathbf{x}\right)  ,\ldots,c^{m-1}\left(
\mathbf{x}\right)  \right\}  =S$, qed.}. Hence, for the rest of this proof
(i.e., of the induction step), we WLOG assume that we don't have $h<m$. Thus,
$h\geq m$, so that $h-m\in\mathbb{N}$.

We know that $m$ is nonzero, and therefore positive (since $m\in\mathbb{N}$).
Hence, $h-m<h$. Therefore (and because of $h-m\in\mathbb{N}$), we can apply
Observation 3 to $k=h-m$ (since we have assumed that Observation 3 holds
whenever $k<h$). We thus obtain $c^{h-m}\left(  \mathbf{x}\right)  \in S$.

But (\ref{eq.fnfm}) (applied to $X^{n}$, $c$, $h-m$ and $m$ instead of $S$,
$f$, $n$ and $m$) shows that $c^{h-m}\circ c^{m}=c^{\left(  h-m\right)
+m}=c^{h}$. Hence, $\left(  c^{h-m}\circ c^{m}\right)  \left(  \mathbf{x}%
\right)  =c^{h}\left(  \mathbf{x}\right)  $, so that%
\[
c^{h}\left(  \mathbf{x}\right)  =\left(  c^{h-m}\circ c^{m}\right)  \left(
\mathbf{x}\right)  =c^{h-m}\left(  \underbrace{c^{m}\left(  \mathbf{x}\right)
}_{=\mathbf{x}}\right)  =c^{h-m}\left(  \mathbf{x}\right)  \in S.
\]
In other words, Observation 3 holds for $k=h$. This completes the induction
step. Observation 3 is thus proven.]

Now, it is easy to see that $\left[  \mathbf{x}\right]  _{\sim}\subseteq
S$\ \ \ \ \footnote{\textit{Proof.} Let $\mathbf{s}\in\left[  \mathbf{x}%
\right]  _{\sim}$. Then, $\mathbf{s}\in\left[  \mathbf{x}\right]  _{\sim
}=\left\{  \mathbf{y}\in X^{n}\ \mid\ \mathbf{y}\sim\mathbf{x}\right\}  $ (by
(\ref{sol.periodic.2.b.eqclass})). In other words, $\mathbf{s}\in X^{n}$ and
$\mathbf{s}\sim\mathbf{x}$. From $\mathbf{s}\sim\mathbf{x}$, we obtain
$\mathbf{x}\sim\mathbf{s}$ (since the relation $\sim$ is symmetric). In other
words, there exists some $k\in\mathbb{N}$ such that $\mathbf{s}=c^{k}\left(
\mathbf{x}\right)  $ (by the definition of the relation $\sim$). Consider this
$k$. Now, Observation 3 yields $c^{k}\left(  \mathbf{x}\right)  \in S$. Hence,
$\mathbf{s}=c^{k}\left(  \mathbf{x}\right)  \in S$.
\par
Now, forget that we fixed $\mathbf{s}$. We thus have shown that $\mathbf{s}\in
S$ for each $\mathbf{s}\in\left[  \mathbf{x}\right]  _{\sim}$. In other words,
$\left[  \mathbf{x}\right]  _{\sim}\subseteq S$.}. Combining this with
$S\subseteq\left[  \mathbf{x}\right]  _{\sim}$, we obtain $\left[
\mathbf{x}\right]  _{\sim}=S=\left\{  c^{0}\left(  \mathbf{x}\right)
,c^{1}\left(  \mathbf{x}\right)  ,\ldots,c^{m-1}\left(  \mathbf{x}\right)
\right\}  $ (by the definition of $S$). This solves Exercise
\ref{exe.periodic.2} \textbf{(b)}.

\textbf{(c)} We observe that $m\in\mathbb{N}$ and $c^{m}\left(  \mathbf{x}%
\right)  =\mathbf{x}$ (as we have already seen in the solution to part
\textbf{(b)}).

Now, we are going to show the following:

\begin{statement}
\textit{Observation 4:} Let $i$ and $j$ be two distinct elements of $\left\{
0,1,\ldots,m-1\right\}  $. Then, $c^{i}\left(  \mathbf{x}\right)  \neq
c^{j}\left(  \mathbf{x}\right)  $.
\end{statement}

[\textit{Proof of Observation 4:} We WLOG assume that $i\leq j$ (since
otherwise, we can simply switch $i$ with $j$ to ensure that $i\leq j$). Hence,
$i<j$ (since $i$ and $j$ are distinct).

Assume (for the sake of contradiction) that $c^{i}\left(  \mathbf{x}\right)
=c^{j}\left(  \mathbf{x}\right)  $. Since $j\in\left\{  0,1,\ldots
,m-1\right\}  $, we have $j\leq m-1<m$. Hence, $\left(  m-\underbrace{j}%
_{<m}\right)  +i>\left(  m-m\right)  +i=i\geq0$.

Also $m-j\in\mathbb{N}$ (since $j<m$). Therefore, (\ref{eq.fnfm}) (applied to
$X^{n}$, $c$, $m-j$ and $j$ instead of $S$, $f$, $n$ and $m$) shows that
$c^{m-j}\circ c^{j}=c^{\left(  m-j\right)  +j}=c^{m}$. Hence, $\left(
c^{m-j}\circ c^{j}\right)  \left(  \mathbf{x}\right)  =c^{m}\left(
\mathbf{x}\right)  =\mathbf{x}$. Therefore,%
\begin{equation}
\mathbf{x}=\left(  c^{m-j}\circ c^{j}\right)  \left(  \mathbf{x}\right)
=c^{m-j}\left(  c^{j}\left(  \mathbf{x}\right)  \right)  .
\label{sol.periodic.2.c.3}%
\end{equation}


On the other hand, (\ref{eq.fnfm}) (applied to $X^{n}$, $c$, $m-j$ and $i$
instead of $S$, $f$, $n$ and $m$) shows that $c^{m-j}\circ c^{i}=c^{\left(
m-j\right)  +i}$. Hence, $\left(  c^{m-j}\circ c^{i}\right)  \left(
\mathbf{x}\right)  =c^{\left(  m-j\right)  +i}\left(  \mathbf{x}\right)  $.
Therefore,%
\[
c^{\left(  m-j\right)  +i}\left(  \mathbf{x}\right)  =\left(  c^{m-j}\circ
c^{i}\right)  \left(  \mathbf{x}\right)  =c^{m-j}\left(  \underbrace{c^{i}%
\left(  \mathbf{x}\right)  }_{\substack{=c^{j}\left(  \mathbf{x}\right)
\\\text{(by our assumption)}}}\right)  =c^{m-j}\left(  c^{j}\left(
\mathbf{x}\right)  \right)  =\mathbf{x}%
\]
(by (\ref{sol.periodic.2.c.3})).

Now, the integer $\left(  m-j\right)  +i$ belongs to $\mathbb{N}$ (since
$\left(  m-j\right)  +i>0$) and satisfies $c^{\left(  m-j\right)  +i}\left(
\mathbf{x}\right)  =\mathbf{x}$. In other words, $\left(  m-j\right)  +i$ is a
period of $\mathbf{x}$ (by the definition of a \textquotedblleft
period\textquotedblright). Moreover, this period $\left(  m-j\right)  +i$ is
nonzero (since $\left(  m-j\right)  +i>0$).

Recall that $m$ is the \textbf{smallest} nonzero period of the $n$-tuple
$\mathbf{x}\in X^{n}$. Hence, every nonzero period $p$ of $\mathbf{x}$
satisfies $p\geq m$. Applying this to $p=\left(  m-j\right)  +i$, we obtain
$\left(  m-j\right)  +i\geq m$ (since $\left(  m-j\right)  +i$ is a nonzero
period of $\mathbf{x}$). This contradicts $\left(  m-j\right)  +\underbrace{i}%
_{<j}<\left(  m-j\right)  +j=m$. This contradiction shows that our assumption
(that $c^{i}\left(  \mathbf{x}\right)  =c^{j}\left(  \mathbf{x}\right)  $) was
wrong. Hence, $c^{i}\left(  \mathbf{x}\right)  \neq c^{j}\left(
\mathbf{x}\right)  $. This proves Observation 4.]

Observation 4 shows that the $m$ tuples $c^{0}\left(  \mathbf{x}\right)
,c^{1}\left(  \mathbf{x}\right)  ,\ldots,c^{m-1}\left(  \mathbf{x}\right)  $
are distinct. Hence, the set $\left\{  c^{0}\left(  \mathbf{x}\right)
,c^{1}\left(  \mathbf{x}\right)  ,\ldots,c^{m-1}\left(  \mathbf{x}\right)
\right\}  $ contains $m$ distinct elements. Therefore, $\left\vert \left\{
c^{0}\left(  \mathbf{x}\right)  ,c^{1}\left(  \mathbf{x}\right)
,\ldots,c^{m-1}\left(  \mathbf{x}\right)  \right\}  \right\vert =m$. But
Exercise \ref{exe.periodic.2} \textbf{(b)} shows that $\left[  \mathbf{x}%
\right]  _{\sim}=\left\{  c^{0}\left(  \mathbf{x}\right)  ,c^{1}\left(
\mathbf{x}\right)  ,\ldots,c^{m-1}\left(  \mathbf{x}\right)  \right\}  $.
Thus, $\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert =\left\vert
\left\{  c^{0}\left(  \mathbf{x}\right)  ,c^{1}\left(  \mathbf{x}\right)
,\ldots,c^{m-1}\left(  \mathbf{x}\right)  \right\}  \right\vert =m$. This
solves Exercise \ref{exe.periodic.2} \textbf{(c)}.
\end{proof}


\end{document}