\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{<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 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<v\leq n!$ and $f^{u}=f^{v}$.

[\textbf{Hint:} First prove part \textbf{(b)} in the case when $f$ is a
permutation (hint: what does the pigeonhole principle say about the
permutations $f^{0},f^{1},\ldots,f^{n!}$ ?). Then, use this to show part
\textbf{(a)}. Finally, prove part \textbf{(b)} in the general case, by
applying part \textbf{(a)} to the map $g$ from Exercise
\ref{exe.order-of-map.1}.]
\end{exercise}


\end{document}