\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, October 27, 2017 18:16:03}
%TCIDATA{}
%TCIDATA{}
%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 4707 Fall 2017 (Darij Grinberg): homework set 4}
\ohead{page \thepage}
\cfoot{}
\begin{document}
\begin{center}
\textbf{Math 4707 Fall 2017 (Darij Grinberg): homework set 4 [corrected 27 Oct
2017]}
due date: Wednesday 1 Nov 2017 at the beginning of class, or before that by
email or moodle
Please solve \textbf{at most 4} of the 7 exercises!
\end{center}
\subsection{The binomial transform, again}
If $\mathbf{a}=\left( a_{0},a_{1},\ldots,a_{N}\right) $ is a
list\footnote{The words \textquotedblleft finite list\textquotedblright,
\textquotedblleft tuple\textquotedblright\ and \textquotedblleft finite
sequence\textquotedblright\ mean the same thing. I only consider finite lists
on this homework set.} of rational numbers, then the \textit{binomial
transform} of this list $\mathbf{a}$ is defined to be the list $\left(
b_{0},b_{1},\ldots,b_{N}\right) $ of rational numbers, where%
\[
b_{n}=\sum_{i=0}^{n}\left( -1\right) ^{i}\dbinom{n}{i}a_{i}%
\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\left\{ 0,1,\ldots,N\right\} .
\]
We shall denote the binomial transform of the list $\mathbf{a}$ by $B\left(
\mathbf{a}\right) $. We have already studied binomial transforms implicitly
on the previous homework set: Namely, Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw3.pdf}{homework set \#3}
says that if $\mathbf{b}$ is the binomial transform of a list $\mathbf{a}$,
then $\mathbf{a}$ is (in turn) the binomial transform of $\mathbf{b}$. In
other words: If $\mathbf{b}=B\left( \mathbf{a}\right) $, then $\mathbf{a}%
=B\left( \mathbf{b}\right) $. In other words, if we regard $B$ as a map that
transforms lists into lists, then $B^{2}=B\circ B=\operatorname*{id}$.
\begin{exercise}
\label{exe.bintra2}Let $N\in\mathbb{N}$.
\textbf{(a)} Find the binomial transform of the list $\left( 1,1,\ldots
,1\right) $ (with $N+1$ entries).
\textbf{(b)} For any given $a\in\mathbb{N}$, find the binomial transform of
the list $\left( \dbinom{0}{a},\dbinom{1}{a},\ldots,\dbinom{N}{a}\right) $.
\textbf{(c)} For any given $q\in\mathbb{Z}$, find the binomial transform of
the list $\left( q^{0},q^{1},\ldots,q^{N}\right) $.
\textbf{(d)} Find the binomial transform of the list $\left(
1,0,1,0,1,0,\ldots\right) $ (this ends with $1$ if $N$ is even, and with $0$
if $N$ is odd).
\end{exercise}
\begin{exercise}
\label{exe.bintra3}Let $N\in\mathbb{N}$. If $\mathbf{a}=\left( a_{0}%
,a_{1},\ldots,a_{N}\right) $ is a list of rational numbers, then $W\left(
\mathbf{a}\right) $ denotes the list $\left( \left( -1\right) ^{N}%
a_{N},\left( -1\right) ^{N}a_{N-1},\ldots,\left( -1\right) ^{N}%
a_{0}\right) $ of rational numbers. (Thus, the list $W\left( \mathbf{a}%
\right) $ is obtained by reversing the list $\mathbf{a}$ and then multiplying
each of its entries by $\left( -1\right) ^{N}$.) Hence, $W$ and $B$ are two
maps, each transforming lists into lists.
Prove that $B\circ W\circ B=W\circ B\circ W$ and $\left( B\circ W\right)
^{3}=\operatorname*{id}$.
\end{exercise}
The equality $\left( B\circ W\right) ^{3}=\operatorname*{id}$, spelt out in
words, says that if we start with a list, apply the map $W$, apply the
binomial transform, then apply the map $W$ to the result, then again apply the
binomial transform, then again apply the map $W$ to the result, then apply the
binomial transform once again, then we end up with the original list.
\subsection{Another recurrence}
\begin{exercise}
\label{exe.another-rec}Consider the sequence $\left( a_{0},a_{1},a_{2}%
,\ldots\right) $ of integers given by%
\[
a_{0}=2,\ \ \ \ \ \ \ \ \ \ a_{1}=20,\ \ \ \ \ \ \ \ \ \ a_{n}=20a_{n-1}%
-99a_{n-2}\ \ \ \ \ \ \ \ \ \ \text{for }n\geq2.
\]
Find an explicit formula for $a_{n}$.
[\textbf{Hint:} Use of generating functions is allowed. To solve Exercise
\ref{exe.another-rec} in the same way as I proved Binet's formula in class,
partial fraction decomposition is needed. The
\href{https://en.wikipedia.org/wiki/Partial_fraction_decomposition#Examples}{Wikipedia
examples} can be useful.]
\end{exercise}
\subsection{Counting permutations by descents}
If $\sigma$ is a permutation of $\left[ n\right] $ for some $n\in\mathbb{N}%
$, then a \textit{descent} of $\sigma$ means an element $i\in\left[
n-1\right] $ satisfying $\sigma\left( i\right) >\sigma\left( i+1\right)
$. For example, the permutation $\sigma$ of $\left[ 5\right] $ with $\left(
\sigma\left( 1\right) ,\sigma\left( 2\right) ,\sigma\left( 3\right)
,\sigma\left( 4\right) ,\sigma\left( 5\right) \right) =\left(
3,1,4,5,2\right) $ has descents $1$ (since $3>1$) and $4$ (since $5>2$).
\begin{exercise}
\label{exe.1descent}Let $n$ be a positive integer. How many permutations of
$\left[ n\right] $ have at most $1$ descent?
\end{exercise}
(For example, the permutation $\sigma$ of $\left[ 5\right] $ with $\left(
\sigma\left( 1\right) ,\sigma\left( 2\right) ,\sigma\left( 3\right)
,\sigma\left( 4\right) ,\sigma\left( 5\right) \right) =\left(
1,4,2,3,5\right) $ has exactly $1$ descent: namely, $2$ is its only descent.)
\subsection{Counting derangements squaring to the identity}
\begin{exercise}
Let $n\in\mathbb{N}$. How many derangements $\sigma$ of $\left[ n\right] $
satisfy $\sigma^{2}=\operatorname*{id}$ ?
(For example, the derangement $\sigma$ of $\left[ 6\right] $ sending
$1,2,3,4,5,6$ to $3,6,1,5,4,2$ satisfies $\sigma^{2}=\operatorname*{id}$.)
[\textbf{Hint:} The answer will depend on whether $n$ is even or odd.]
\end{exercise}
\subsection{Iteration of maps on finite sets}
The next two exercises study what happens if you apply a map from a finite set
to itself several times.
\begin{exercise}
\label{exe.order-of-map.1}Let $n\in\mathbb{N}$. Let $S$ be an $n$-element set.
Let $f:S\rightarrow S$ be any map.
\textbf{(a)} Prove that $f^{0}\left( S\right) \supseteq f^{1}\left(
S\right) \supseteq f^{2}\left( S\right) \supseteq\cdots$.
\textbf{(b)} Prove that $f^{n}\left( S\right) =f^{k}\left( S\right) $ for
each integer $k\geq n$.
\textbf{(c)} Define a map $g:f^{n}\left( S\right) \rightarrow f^{n}\left(
S\right) $ by%
\[
g\left( x\right) =f\left( x\right) \ \ \ \ \ \ \ \ \ \ \text{for each
}x\in f^{n}\left( S\right) .
\]
(Thus, $g$ is the restriction of $f$ onto the image $f^{n}\left( S\right) $,
regarded as a map from $f^{n}\left( S\right) $ to $f^{n}\left( S\right) $.)
Prove that $g$ is well-defined (i.e., that $f\left( x\right) $ actually
belongs to $f^{n}\left( S\right) $ for each $x\in f^{n}\left( S\right) $)
and is a permutation of $f^{n}\left( S\right) $.
[\textbf{Hint:} For part \textbf{(b)}, first prove that there exists some
$m\in\left\{ 0,1,\ldots,n\right\} $ such that $f^{m}\left( S\right)
=f^{m+1}\left( S\right) $. Then argue that $f^{n}\left( S\right)
=f^{n+1}\left( S\right) $.]
\end{exercise}
\Needspace{10cm}
\begin{example}
Let $n=7$. Let $S=\left[ 7\right] $. Let $f:S\rightarrow S$ be the map with
\[
\left( f\left( 1\right) ,f\left( 2\right) ,f\left( 3\right) ,f\left(
4\right) ,f\left( 5\right) ,f\left( 6\right) ,f\left( 7\right) \right)
=\left( 4,4,5,5,2,3,3\right) .
\]
Then,
\begin{align*}
f^{0}\left( S\right) & =S=\left\{ 1,2,3,4,5,6,7\right\} ;\\
f^{1}\left( S\right) & =f\left( S\right) =\left\{ 2,3,4,5\right\} ;\\
f^{2}\left( S\right) & =\left\{ 2,4,5\right\} ;\\
f^{k}\left( S\right) & =\left\{ 2,4,5\right\}
\ \ \ \ \ \ \ \ \ \ \text{for each }k\geq2.
\end{align*}
Thus, in particular, $f^{n}\left( S\right) =\left\{ 2,4,5\right\} $. The
map $g$ is the permutation of this set $f^{n}\left( S\right) =\left\{
2,4,5\right\} $ sending $2,4,5$ to $4,5,2$, respectively. It is perhaps
worthwhile to draw the \textquotedblleft cycle digraph\textquotedblright\ of
$f$ (which is not literally a cycle digraph, because $f$ is not a permutation,
but is constructed in the same way):%
\[%
%TCIMACRO{\TeXButton{cycle digraph of f}{\xymatrix{
%& 6 \ar[dr] & & 7 \ar[dl] \\
%1 \ar[d] & & 3 \ar[d] \\
%4 \ar[rr] & & 5 \ar[dl] \\
%& 2 \ar[ul]
%}}}%
%BeginExpansion
\xymatrix{
& 6 \ar[dr] & & 7 \ar[dl] \\
1 \ar[d] & & 3 \ar[d] \\
4 \ar[rr] & & 5 \ar[dl] \\
& 2 \ar[ul]
}%
%EndExpansion
.
\]
\end{example}
\begin{exercise}
\label{exe.order-of-map.2}Let $n\in\mathbb{N}$. Let $S$ be an $n$-element set.
Let $f:S\rightarrow S$ be any map.
\textbf{(a)} If $f$ is a permutation of $S$, then prove that there exists some
$p\in\left[ n!\right] $ such that $f^{p}=\operatorname*{id}$.
\textbf{(b)} Prove in general (i.e., not only when $f$ is a permutation) that
there exist two integers $u$ and $v$ with $0\leq u