\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=Sunday, October 15, 2017 18:26:22}
%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 [corrected 15 Oct
2017]}

due date: Tuesday 17 Oct 2017 at the beginning of class, or before that by
email or by moodle.

Please solve \textbf{at most 5} of the 6 exercises.
\end{center}

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

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

\begin{exercise}
\label{exe.periodic.2}This continues Exercise 7 from 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}


\end{document}