\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=Monday, February 19, 2018 19:09:40}
%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 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

due date: Wednesday 4 Oct 2017 at the beginning of class

Please solve \textbf{at most 4} of the 7 exercises!
\end{center}

\begin{exercise}
\label{exe.-1/2}Let $n\in\mathbb{N}$.

\textbf{(a)} Prove that%
\[
\left(  2n-1\right)  \cdot\left(  2n-3\right)  \cdot\cdots\cdot1=\dfrac
{\left(  2n\right)  !}{2^{n}n!}.
\]
(The left hand side is understood to be the product of all odd integers from
$1$ to $2n-1$.)

\textbf{(b)} Prove that
\[
\dbinom{-1/2}{n}=\left(  \dfrac{-1}{4}\right)  ^{n}\dbinom{2n}{n}.
\]


\textbf{(c)} Prove that%
\[
\dbinom{-1/3}{n}\dbinom{-2/3}{n}=\dfrac{\left(  3n\right)  !}{\left(
3^{n}n!\right)  ^{3}}.
\]

\end{exercise}

\begin{exercise}
\label{exe.rewr-prod}Let $n\in\mathbb{Q}$, $a\in\mathbb{N}$ and $b\in
\mathbb{N}$.

\textbf{(a)} Prove that every integer $j\geq a$ satisfies%
\[
\dbinom{n}{j}\dbinom{j}{a}\dbinom{n-j}{b}=\dbinom{n}{a}\dbinom{n-a}{b}%
\dbinom{n-a-b}{j-a}.
\]


\textbf{(b)} Compute the sum $\sum_{j=a}^{n}\dbinom{n}{j}\dbinom{j}{a}%
\dbinom{n-j}{b}$ for every integer $n\geq a$. (The result should contain no
summation signs.)
\end{exercise}

Recall the concept of lacunar sets, as defined in homework set 1. Recall also
the Fibonacci sequence $\left(  f_{0},f_{1},f_{2},\ldots\right)  $ defined by
$f_{0}=0$, $f_{1}=1$, and $f_{n}=f_{n-1}+f_{n-2}$ for all $n\geq2$. Exercise 4
\textbf{(c)} on homework set 1 told us that the number $g\left(  n\right)  $
of all lacunar subsets of $\left[  n\right]  $ is $f_{n+2}$. We shall now see more.

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

\textbf{(a)} For any $k\in\left\{  0,1,\ldots,n+1\right\}  $, prove that the
number of all lacunar $k$-element subsets of $\left[  n\right]  $ is
$\dbinom{n-k+1}{k}$.

[Notice that this equals $0$ whenever $2k>n+1$. You shouldn't need a separate
argument for this case, but make sure you understand why the $0$ is not surprising.]

\textbf{(b)} Conclude that%
\[
f_{n+2}=\sum_{k=0}^{n}\dbinom{n-k+1}{k}.
\]

\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]  $. In class, we have shown the
following two recursive formulas:

\begin{itemize}
\item We have%
\[
\operatorname*{sur}\left(  n,0\right)  =\left[  n=0\right]
\ \ \ \ \ \ \ \ \ \ \text{for all }n\in\mathbb{N}\text{,}%
\]
and%
\[
\operatorname*{sur}\left(  n,k\right)  =\sum_{j=0}^{n-1}\dbinom{n}%
{j}\operatorname*{sur}\left(  j,k-1\right)  \ \ \ \ \ \ \ \ \ \ \text{for all
}n\in\mathbb{N}\text{ and }k>0.
\]


\item We have%
\[
\operatorname*{sur}\left(  n,0\right)  =\left[  n=0\right]
\ \ \ \ \ \ \ \ \ \ \text{for all }n\in\mathbb{N}\text{,}%
\]%
\[
\operatorname*{sur}\left(  0,k\right)  =\left[  k=0\right]
\ \ \ \ \ \ \ \ \ \ \text{for all }k\in\mathbb{N}\text{,}%
\]
and%
\[
\operatorname*{sur}\left(  n,k\right)  =k\left(  \operatorname*{sur}\left(
n-1,k\right)  +\operatorname*{sur}\left(  n-1,k-1\right)  \right)
\ \ \ \ \ \ \ \ \ \ \text{for all }n>0\text{ and }k>0.
\]

\end{itemize}

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


[\textbf{Hint:} Use one of the above recursions in the induction step. You are
allowed to use the binomial formula
\[
\left(  x+y\right)  ^{n}=\sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k},
\]
which holds for any $x,y\in\mathbb{Q}$ and any $n\in\mathbb{N}$.]
\end{exercise}

\begin{exercise}
\label{exe.oddlike}Let $n\in\mathbb{N}$. Let me call a permutation of $\left[
n\right]  $ \textit{oddlike} if it sends every odd element of $\left[
n\right]  $ to an odd element of $\left[  n\right]  $. (For example, the
permutation of $\left[  5\right]  $ sending $1,2,3,4,5$ to $3,4,5,2,1$ is oddlike.)

\textbf{(a)} Prove that any oddlike permutation of $\left[  n\right]  $ must
also send every even element of $\left[  n\right]  $ to an even element of
$\left[  n\right]  $.

\textbf{(b)} Find a formula for the number of oddlike permutations of $\left[
n\right]  $. [\textbf{Hint:} The answer may depend on the parity of $n$.]
\end{exercise}

\begin{definition}
Let $S$ be a set. Let $f:S\rightarrow S$ be a map from $S$ to $S$. Then, for
every $k\in\mathbb{N}$, the map $f^{k}:S\rightarrow S$ is defined to be
\[
\underbrace{f\circ f\circ\cdots\circ f}_{k\text{ times}}.
\]
For example, if $f:\mathbb{Z}\rightarrow\mathbb{Z}$ is the map $x\mapsto
x^{2}$, then $f^{k}$ is the map $x\mapsto\underbrace{\left(  \left(  \left(
x^{2}\right)  ^{2}\right)  \cdots\right)  ^{2}}_{k\text{ squarings}%
}=x^{\left(  2^{k}\right)  }$.

Note that $f^{0}=\underbrace{f\circ f\circ\cdots\circ f}_{0\text{ times}%
}=\operatorname*{id}\nolimits_{S}$, since a composition of no maps
(\textquotedblleft empty composition\textquotedblright) is always understood
as the identity map.
\end{definition}

\begin{exercise}
\label{exe.powerlaw}Let $S$ be a set. Let $f:S\rightarrow S$ be a map.

\textbf{(a)} Prove that $f^{n}\circ f^{m}=f^{n+m}$ for each $n,m\in\mathbb{N}%
$. [Yes, this is a one-liner; you don't need induction.]

\textbf{(b)} Let $g:S\rightarrow S$ be a further map such that $f\circ
g=g\circ f$. Prove that $\left(  f\circ g\right)  ^{n}=f^{n}\circ g^{n}$ for
each $n\in\mathbb{N}$.

\textbf{(c)} Find an example in which the claim of \textbf{(b)} fails if we
drop the assumption that $f\circ g=g\circ f$.
\end{exercise}

\begin{exercise}
\label{exe.periodic.1}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.)

\textbf{(a)} Prove that
\[
c^{k}\left(  x_{1},x_{2},\ldots,x_{n}\right)  =\left(  x_{k+1},x_{k+2}%
,\ldots,x_{n},x_{1},x_{2},\ldots,x_{k}\right)
\]
for each $k\in\left\{  0,1,\ldots,n\right\}  $ and each $\left(  x_{1}%
,x_{2},\ldots,x_{n}\right)  \in X^{n}$. (Note that $\left(  x_{k+1}%
,x_{k+2},\ldots,x_{n},x_{1},x_{2},\ldots,x_{k}\right)  $ is to be understood
as $\left(  x_{1},x_{2},\ldots,x_{n}\right)  $ if $k$ equals either $0$ or $n$.)

[\textbf{Note:} This might be intuitively clear -- after all, if $c$ rotates a
tuple, then $c^{k}$ rotates it $k$ times, which causes its first $k$ entries
to move to the rightmost spot. But the point is to give a rigorous proof.
Induction is recommended.]

\textbf{(b)} Let $\mathbf{x}=\left(  x_{1},x_{2},\ldots,x_{n}\right)  $ be an
$n$-tuple in $X^{n}$. A nonnegative integer $k$ is said to be a
\textit{period} of $\mathbf{x}$ if it satisfies $c^{k}\left(  \mathbf{x}%
\right)  =\mathbf{x}$. (For example, $0$ is always a period of $\mathbf{x}$.
For another example, the periods of the $6$-tuple $\left(  1,4,2,1,4,2\right)
$ are $0,3,6,9,\ldots$.)

Prove that if $p$ and $q$ are two periods of $\mathbf{x}$ satisfying $p\geq
q$, then $p-q$ is also a period of $\mathbf{x}$.

\textbf{(c)} Let $m$ be the smallest nonzero period of the $n$-tuple
$\mathbf{x}\in X^{n}$. Prove that $m$ divides any period of $\mathbf{x}$.

\textbf{(d)} Conclude that $m$ divides $n$.
\end{exercise}


\end{document}