\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, November 05, 2017 20:53:52}
%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): midterm 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 Fall 2017 (Darij Grinberg): midterm 2}

due date: Wednesday 8 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{Idempotent maps}

If $S$ is a set, then a map $f:S\rightarrow S$ is said to be
\textit{idempotent} if and only if $f\circ f=f$. For instance, the map
$\left[  3\right]  \rightarrow\left[  3\right]  $ sending $1,2,3$ to $1,3,3$
(respectively) is idempotent.

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

\textbf{(a)} Prove that a map $f:\left[  n\right]  \rightarrow\left[
n\right]  $ is idempotent if and only if $f\left(  y\right)  =y$ for every $y$
in the image of $f$.

\textbf{(b)} Prove that the number of idempotent maps $\left[  n\right]
\rightarrow\left[  n\right]  $ is $\sum_{k=0}^{n}\dbinom{n}{k}k^{n-k}$.

\textbf{(c)} Prove that the number of idempotent maps $\left[  n\right]
\rightarrow\left[  n\right]  $ has the form $an+1$ for some $a\in\mathbb{N}$.
(Of course, $a$ will depend on $n$.)

[\textbf{Hint:} When is $\dbinom{n}{k}k^{n-k}$ divisible by $n$ ?]
\end{exercise}

\subsection{Fixed points}

\begin{exercise}
Let $S$ be a finite set. For any map $f:S\rightarrow S$, we let
$\operatorname*{Fix}f$ denote the set of all fixed points of $f$. (That is,
$\operatorname*{Fix}f=\left\{  s\in S\ \mid\ f\left(  s\right)  =s\right\}  $.)

\textbf{(a)} Prove that $\left\vert \operatorname*{Fix}\left(  f\circ
g\right)  \right\vert =\left\vert \operatorname*{Fix}\left(  g\circ f\right)
\right\vert $ for any two maps $f:S\rightarrow S$ and $g:S\rightarrow S$.

\textbf{(b)} Is it true that every three maps $f,g,h$ from $S$ to $S$ satisfy
$\left\vert \operatorname*{Fix}\left(  f\circ g\circ h\right)  \right\vert
=\left\vert \operatorname*{Fix}\left(  g\circ f\circ h\right)  \right\vert $ ?

[\textbf{Hint:} For \textbf{(a)}, find a bijection.]
\end{exercise}

\subsection{A binomial coefficient in a denominator}

\begin{exercise}
\label{exe.schmitt-iha-eq9.2}Let $n$ and $a$ be two integers with $n\geq
a\geq1$. Prove that%
\[
\sum_{k=a}^{n}\dfrac{\left(  -1\right)  ^{k}}{k}\dbinom{n-a}{k-a}%
=\dfrac{\left(  -1\right)  ^{a}}{a\dbinom{n}{a}}.
\]

\end{exercise}

\subsection{Derangements with at most 1 descent}

\begin{exercise}
\label{exe.1descent.der}Let $n\in\mathbb{N}$. How many derangements $\sigma$
of $\left[  n\right]  $ have at most $1$ descent?
\end{exercise}

(See \href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw5o.pdf}{homework set
\#5} for the definitions of descents and of derangements.)

\subsection{Connected permutations}

\begin{definition}
Let $n$ be a positive integer. A permutation $\sigma$ of $\left[  n\right]  $
is said to be \textit{connected} if and only if there exists no $k\in\left[
n-1\right]  $ such that $\sigma\left(  \left[  k\right]  \right)  =\left[
k\right]  $.
\end{definition}

For example, the permutation $\sigma$ of $\left[  5\right]  $ sending
$1,2,3,4,5$ to $2,4,1,5,3$ is connected, since it satisfies
\begin{align*}
\sigma\left(  \left[  1\right]  \right)   &  =\left\{  2\right\}  \neq\left[
1\right]  ,\ \ \ \ \ \ \ \ \ \ \sigma\left(  \left[  2\right]  \right)
=\left\{  2,4\right\}  \neq\left[  2\right]  ,\\
\sigma\left(  \left[  3\right]  \right)   &  =\left\{  2,4,1\right\}
\neq\left[  3\right]  ,\ \ \ \ \ \ \ \ \ \ \sigma\left(  \left[  4\right]
\right)  =\left\{  2,4,1,5\right\}  \neq\left[  4\right]  .
\end{align*}
But the permutation $\sigma$ of $\left[  4\right]  $ sending $1,2,3,4$ to
$2,1,4,3$ is not connected, because it satisfies $\sigma\left(  \left[
2\right]  \right)  =\left[  2\right]  $. Likewise, a permutation $\sigma$ of
$\left[  n\right]  $ (for $n>1$) satisfying $\sigma\left(  1\right)  =1$ is
never connected (since $\sigma\left(  \left[  1\right]  \right)  =\left[
1\right]  $); the same holds for a permutation $\sigma$ satisfying
$\sigma\left(  n\right)  =n$ (since $\sigma\left(  \left[  n-1\right]
\right)  =\left[  n-1\right]  $).

\begin{exercise}
\label{exe.connperm}For each positive integer $n$, let $c_{n}$ denote the
number of all connected permutations of $\left[  n\right]  $. (Thus, $c_{1}%
=1$, $c_{2}=1$ and $c_{3}=3$.)

Prove that%
\[
n!=\sum_{k=1}^{n}c_{k}\left(  n-k\right)  !\ \ \ \ \ \ \ \ \ \ \text{for each
positive integer }n.
\]

\end{exercise}

\subsection{Permutations and intervals}

An \textit{integer interval} means a set of the form $\left\{  a,a+1,\ldots
,b\right\}  $ for some integers $a$ and $b$. (If $a>b$, then this set is
understood to be empty.)

\begin{exercise}
\label{exe.perm-int}Let $n\in\mathbb{N}$ and $r\in\left[  n\right]  $. A
permutation $\sigma$ of $\left[  n\right]  $ is said to be $r$%
\textit{-friendly} if for each $k\in\left\{  r,r+1,\ldots,n\right\}  $, the
set $\sigma\left(  \left[  k\right]  \right)  $ is an integer interval.

(For example, the permutation $\sigma$ of $\left[  6\right]  $ sending
$1,2,3,4,5,6$ to $2,4,3,5,1,6$ is $3$-friendly (since $\sigma\left(  \left[
3\right]  \right)  =\left\{  2,3,4\right\}  $, $\sigma\left(  \left[
4\right]  \right)  =\left\{  2,3,4,5\right\}  $, $\sigma\left(  \left[
5\right]  \right)  =\left\{  1,2,3,4,5\right\}  $ and $\sigma\left(  \left[
6\right]  \right)  =\left\{  1,2,3,4,5,6\right\}  $ are integer intervals),
and thus also $r$-friendly for each $r\geq3$, but not $2$-friendly (since
$\sigma\left(  \left[  2\right]  \right)  =\left\{  2,4\right\}  $ is not an
integer interval).)

Prove that the number of $r$-friendly permutations of $\left[  n\right]  $ is
$2^{n-r}r!$.
\end{exercise}

\subsection{Inverting a power series}

\begin{exercise}
\label{exe.inverting-ps}Find and prove an explicit formula for the coefficient
of $x^{n}$ in the formal power series $\dfrac{1}{1-x-x^{2}+x^{3}}$.

[\textbf{Hint:} The standard strategy is to factor $1-x-x^{2}+x^{3}$, then do
partial fraction decomposition. But it is perfectly legitimate to guess the
formula based on solving%
\[
\left(  1-x-x^{2}+x^{3}\right)  \left(  b_{0}+b_{1}x+b_{2}x^{2}+b_{3}%
x^{3}+b_{4}x^{4}+\cdots\right)  =1
\]
for the first few of the unknown coefficients $b_{0},b_{1},b_{2},\ldots$, and
then prove it by multiplying out. Either option works.]
\end{exercise}


\end{document}