\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, February 23, 2018 17:56:35}
%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 Spring 2018 (Darij Grinberg): homework set 1}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 Spring 2018 (Darij Grinberg): homework set 1}

due date: Wednesday 31 January 2018

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

Please write your name on each page. Feel free to use LaTeX
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw-template.tex}{here} is
a sample file with lots of amenities included).

See \cite[solution to Exercise 8]{fall2017-hw1s} for an example of how a
counting proof can be written.

\subsection{Binomial coefficient basics}

\begin{definition}
The notation $\mathbb{N}$ shall always stand for the set $\left\{
0,1,2,\ldots\right\}  $ of nonnegative integers.
\end{definition}

\begin{definition}
If $n\in\mathbb{N}$, then $n!$ shall denote the product $1\cdot2\cdot
\cdots\cdot n$. For example, $3!=1\cdot2\cdot3=6$ and $1!=1$ and $0!=\left(
\text{empty product}\right)  =1$. (An empty product is defined to be $1$.)
\end{definition}

\begin{definition}
\textbf{(a)} We define the \textit{binomial coefficient} $\dbinom{n}{k}$ by%
\[
\dbinom{n}{k}=\dfrac{n\left(  n-1\right)  \cdots\left(  n-k+1\right)  }{k!}%
\]
for every $n\in\mathbb{Q}$ and $k\in\mathbb{N}$.

For example, $\dbinom{-3}{4}=\dfrac{\left(  -3\right)  \left(  -4\right)
\left(  -5\right)  \left(  -6\right)  }{4!}=15$ and $\dbinom{4}{1}=\dfrac
{4}{1!}=4$ and $\dbinom{4}{0}=\dfrac{\left(  \text{empty product}\right)
}{0!}=\dfrac{1}{1}=1$.

\textbf{(b)} If $n\in\mathbb{Q}$ and $k\in\mathbb{Q}\setminus\mathbb{N}$, then
$\dbinom{n}{k}$ is defined to be $0$.
\end{definition}

See \cite[Chapter 3]{detnotes} for various properties of binomial
coefficients. You are free to use those shown in \cite[\S 3.1]{detnotes}
without proof. In particular, you are free to use the following fact:

\begin{proposition}
[recurrence of the binomial coefficients]\label{prop.binom.rec.neg}Let
$n\in\mathbb{Q}$ and $k\in\mathbb{Z}$. Then,%
\[
\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}.
\]

\end{proposition}

(This is exactly \cite[Proposition 3.11]{detnotes} when $k$ is a
positive integer. The cases $k=0$ and $k<0$ are easy.)

\begin{exercise}
\label{exe.bincoeff-basics1}\textbf{(a)} Show that $\dbinom{-1}{k}=\left(
-1\right)  ^{k}$ for each $k\in\mathbb{N}$.

\textbf{(b)} Show that $\dbinom{-2}{k}=\left(  -1\right)  ^{k}\left(
k+1\right)  $ for each $k\in\mathbb{N}$.

\textbf{(c)} Show that $\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2n\right)
!}{n!}$ is a perfect square (i.e., the square of an integer) whenever
$n\in\mathbb{N}$ is even.
\end{exercise}

\subsection{A fraction appears}

\begin{definition}
Let $x$ be a real number. Then, $\left\lfloor x\right\rfloor $ is defined to
be the unique integer $n$ satisfying $n\leq x<n+1$. This integer $\left\lfloor
x\right\rfloor $ is called the \textit{floor} of $x$, or the \textit{integer
part} of $x$. For example,%
\begin{align*}
\left\lfloor n\right\rfloor  &  =n\ \ \ \ \ \ \ \ \ \ \text{for every }%
n\in\mathbb{Z};\\
\left\lfloor 1.32\right\rfloor  &  =1;\ \ \ \ \ \ \ \ \ \ \left\lfloor
\pi\right\rfloor =3;\ \ \ \ \ \ \ \ \ \ \left\lfloor 0.98\right\rfloor =0;\\
\left\lfloor -2.3\right\rfloor  &  =-3;\ \ \ \ \ \ \ \ \ \ \left\lfloor
-0.4\right\rfloor =-1.
\end{align*}

\end{definition}

\begin{exercise}
\label{exe.sum--2choosek}Let $n\in\mathbb{N}$. Prove that%
\[
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right)  =\left(  -1\right)
^{n}\left\lfloor \dfrac{n+2}{2}\right\rfloor .
\]

\end{exercise}

\subsection{Lemmas for the Sierpinski gasket appearing in Pascal's triangle}

\begin{exercise}
\label{exe.pascal-lucas2}Let $a\in\mathbb{N}$ and $b\in\mathbb{N}$.

\textbf{(a)} Prove that $\dbinom{2a}{2b}\equiv\dbinom{a}{b}\operatorname{mod}%
2$.

\textbf{(b)} Prove that $\dbinom{2a+1}{2b}\equiv\dbinom{a}{b}%
\operatorname{mod}2$.

\textbf{(c)} Prove that $\dbinom{2a}{2b+1}\equiv0\operatorname{mod}2$.

\textbf{(d)} Prove that $\dbinom{2a+1}{2b+1}\equiv\dbinom{a}{b}%
\operatorname{mod}2$.

[\textbf{Hint:} Prove all four parts simultaneously by an induction on $a$,
using Proposition \ref{prop.binom.rec.neg}.]
\end{exercise}

\begin{exercise}
\label{exe.pascal-sierpinski}Let $n\in\mathbb{N}$. Let $a$ and $b$ be two
elements of $\left\{  0,1,\ldots,2^{n}-1\right\}  $. Prove that%
\begin{align*}
\dbinom{2^{n}+a}{b} &  \equiv\dbinom{a}{b}\operatorname{mod}%
2\ \ \ \ \ \ \ \ \ \ \text{and}\\
\dbinom{2^{n}+a}{2^{n}+b} &  \equiv\dbinom{a}{b}\operatorname{mod}2.
\end{align*}


[Here, \textquotedblleft$\left\{  0,1,\ldots,2^{n}-1\right\}  $%
\textquotedblright\ means the set of all integers $k$ satisfying $0\leq
k\leq2^{n}-1$.]

[\textbf{Hint:} Induction on $n$. You can use Exercise \ref{exe.pascal-lucas2}
here even if you have not solved it.]
\end{exercise}

Back in class, Exercise \ref{exe.pascal-sierpinski} helped us prove that
Pascal's triangle becomes a Sierpinski gasket (see, e.g.,
\href{https://en.wikipedia.org/wiki/Sierpinski_triangle#Pascal's_triangle}{the
Wikipedia}) if its entries are replaced by their parities.

\subsection{More on Fibonacci numbers}

\begin{definition}
The \textit{\href{https://en.wikipedia.org/wiki/Fibonacci_number}{Fibonacci
sequence}} is the sequence $\left(  f_{0},f_{1},f_{2},\ldots\right)  $ of
integers which is defined recursively by $f_{0}=0$, $f_{1}=1$, and
$f_{n}=f_{n-1}+f_{n-2}$ for all $n\geq2$. Its first terms are%
\begin{align*}
f_{0}  &  =0,\ \ \ \ \ \ \ \ \ \ f_{1}=1,\ \ \ \ \ \ \ \ \ \ f_{2}%
=1,\ \ \ \ \ \ \ \ \ \ f_{3}=2,\ \ \ \ \ \ \ \ \ \ f_{4}%
=3,\ \ \ \ \ \ \ \ \ \ f_{5}=5,\\
f_{6}  &  =8,\ \ \ \ \ \ \ \ \ \ f_{7}=13,\ \ \ \ \ \ \ \ \ \ f_{8}%
=21,\ \ \ \ \ \ \ \ \ \ f_{9}=34,\ \ \ \ \ \ \ \ \ \ f_{10}=55,\\
f_{11}  &  =89,\ \ \ \ \ \ \ \ \ \ f_{12}=144,\ \ \ \ \ \ \ \ \ \ f_{13}=233.
\end{align*}

\end{definition}

\begin{exercise}
\label{exe.domino.axisymm}Let $n\in\mathbb{N}$. Let $R_{n,2}$ denote the set
$\left[  n\right]  \times\left[  2\right]  $, which we regard as a rectangle
of width $n$ and height $2$ (by identifying the squares with pairs of
coordinates). (Note: I might have been careless in class and confused width
with height a few times. In case of doubt, follow the conventions just given.)

A \textit{vertical domino} is a set of the form $\left\{  \left(  i,j\right)
,\left(  i,j+1\right)  \right\}  $ for some $i\in\mathbb{Z}$ and
$j\in\mathbb{Z}$.

A \textit{horizontal domino} is a set of the form $\left\{  \left(
i+1,j\right)  ,\left(  i,j\right)  \right\}  $ for some $i\in\mathbb{Z}$ and
$j\in\mathbb{Z}$.

A \textit{domino tiling} of $R_{n,2}$ means a set of disjoint dominos (i.e.,
vertical dominos and horizontal dominos) whose union is $R_{n,2}$.

For example, there are $5$ domino tilings of $R_{4,2}$, namely%
\begin{align*}
&
%TCIMACRO{\TeXButton{tabular}{\begin{tabular}{ | c | c | c | c | }
%\hline\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \multicolumn{1}%
%{c}{\phantom{a}} & \phantom{a} \\ \hline\multicolumn{1}{| c}{\phantom{a}}
%& \phantom{a} & \multicolumn{1}{c}{\phantom{a}} & \phantom{a} \\ \hline
%\end{tabular}}}%
%BeginExpansion
\begin{tabular}{ | c | c | c | c | }
\hline\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \multicolumn{1}%
{c}{\phantom{a}} & \phantom{a} \\ \hline\multicolumn{1}{| c}{\phantom{a}}
& \phantom{a} & \multicolumn{1}{c}{\phantom{a}} & \phantom{a} \\ \hline
\end{tabular}%
%EndExpansion
\ ,\ \ \ \ \ \ \ \ \ \
%TCIMACRO{\TeXButton{tabular}{\begin{tabular}{ | c | c | c | c | }
%\hline\phantom{a} & \phantom{a} & \multicolumn{1}{c}{\phantom{a}}
%& \phantom{a} \\ \cline{3-4}
%\phantom{a} & \phantom{a} & \multicolumn{1}{c}{\phantom{a}} & \phantom{a}
%\\ \hline\end{tabular}}}%
%BeginExpansion
\begin{tabular}{ | c | c | c | c | }
\hline\phantom{a} & \phantom{a} & \multicolumn{1}{c}{\phantom{a}}
& \phantom{a} \\ \cline{3-4}
\phantom{a} & \phantom{a} & \multicolumn{1}{c}{\phantom{a}} & \phantom{a}
\\ \hline\end{tabular}%
%EndExpansion
\ ,\ \ \ \ \ \ \ \ \ \
%TCIMACRO{\TeXButton{tabular}{\begin{tabular}{ | c | c | c | c | }
%\hline\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \phantom{a}
%& \phantom{a} \\ \cline{1-2}
%\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \phantom{a} & \phantom{a}
%\\ \hline\end{tabular}}}%
%BeginExpansion
\begin{tabular}{ | c | c | c | c | }
\hline\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \phantom{a}
& \phantom{a} \\ \cline{1-2}
\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \phantom{a} & \phantom{a}
\\ \hline\end{tabular}%
%EndExpansion
\ ,\\
&
%TCIMACRO{\TeXButton{tabular}{\begin{tabular}{ | c | c | c | c | }
%\hline\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a}
%& \phantom{a} \\ \cline{2-3}
%\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a} & \phantom{a}
%\\ \hline\end{tabular}}}%
%BeginExpansion
\begin{tabular}{ | c | c | c | c | }
\hline\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a}
& \phantom{a} \\ \cline{2-3}
\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a} & \phantom{a}
\\ \hline\end{tabular}%
%EndExpansion
\ ,\ \ \ \ \ \ \ \ \ \
%TCIMACRO{\TeXButton{tabular}{\begin{tabular}{ | c | c | c | c | }
%\hline\phantom{a} & \phantom{a} & \phantom{a} & \phantom{a} \\
%\phantom{a} & \phantom{a} & \phantom{a} & \phantom{a} \\ \hline\end{tabular}%
%}}%
%BeginExpansion
\begin{tabular}{ | c | c | c | c | }
\hline\phantom{a} & \phantom{a} & \phantom{a} & \phantom{a} \\
\phantom{a} & \phantom{a} & \phantom{a} & \phantom{a} \\ \hline\end{tabular}%
%EndExpansion
\ .
\end{align*}
Written as a set of dominos, the second of these tilings is
\[
\left\{  \left\{  \left(  1,1\right)  ,\left(  1,2\right)  \right\}  ,\left\{
\left(  2,1\right)  ,\left(  2,2\right)  \right\}  ,\left\{  \left(
3,1\right)  ,\left(  4,1\right)  \right\}  ,\left\{  \left(  3,2\right)
,\left(  4,2\right)  \right\}  \right\}  .
\]


We have seen in class
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018jan17.pdf}{January
17}) that the number of domino tilings of $R_{n,2}$ is $f_{n+1}$.

A domino tiling $S$ of $R_{n,2}$ is said to be \textit{axisymmetric} if
reflecting it across the vertical axis of the rectangle $R_{n,2}$ leaves it
unchanged. (Formally, if $S$ is regarded as a set, it means that for every
domino $\left\{  \left(  i,j\right)  ,\left(  i^{\prime},j^{\prime}\right)
\right\}  \in S$, its \textquotedblleft mirror domino\textquotedblright%
\ $\left\{  \left(  n+1-i,j\right)  ,\left(  n+1-i^{\prime},j^{\prime}\right)
\right\}  $ is also in $S$.) For example, among the $5$ domino tilings of
$R_{4,2}$ listed above, exactly $3$ are axisymmetric (namely, the first, the
fourth and the fifth).

Let $s_{n}$ be the number of axisymmetric domino tilings of $R_{n,2}$.

\textbf{(a)} Prove that $s_{n}=f_{\left(  n+1\right)  /2}$ if $n$ is odd.

\textbf{(b)} Prove that $s_{n}=f_{n/2+2}$ if $n$ is even.
\end{exercise}

\subsection{Some basic counting}

\begin{definition}
Let $n\in\mathbb{Z}$. Then, $\left[  n\right]  $ shall denote the set
$\left\{  1,2,\ldots,n\right\}  $. This is an empty set if $n\leq0$.
\end{definition}

Recall that if $n\in\mathbb{N}$ and $k\in\mathbb{Z}$, and if $S$ is an
$n$-element set, then $\dbinom{n}{k}$ is the number of $k$-element subsets of
$S$. (This can be used without proof; see, e.g., \cite[Proposition
3.12]{detnotes}, or any text on combinatorics.)

\begin{exercise}
\label{exe.basic-count1}Let $n\in\mathbb{N}$, $a\in\mathbb{N}$ and
$b\in\mathbb{N}$. Let $N$ be the number of subsets of $\left[  n\right]  $
that contain exactly $a$ even elements and exactly $b$ odd elements.

\textbf{(a)} Prove that $N=\dbinom{n/2}{a}\dbinom{n/2}{b}$ if $n$ is even.

\textbf{(b)} Compute $N$ when $n$ is odd.
\end{exercise}

\begin{exercise}
\label{exe.f2}A set $S$ of integers shall be called \textit{self-starting} if
its size $\left\vert S\right\vert $ is also its smallest element. (For
example, $\left\{  3,5,6\right\}  $ is self-starting, while $\left\{
2,3,4\right\}  $ and $\left\{  3\right\}  $ are not.)

Let $n\in\mathbb{N}$.

\textbf{(a)} For any $k\in\left[  n\right]  $, find the number of
self-starting subsets of $\left[  n\right]  $ having size $k$.

\textbf{(b)} Find the number of all self-starting subsets of $\left[
n\right]  $.
\end{exercise}

\begin{thebibliography}{9999999999999}                                                                                    %


\bibitem[Grinbe16]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 10 January 2019.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} .

\bibitem[Fall2017-HW1s]{fall2017-hw1s}Darij Grinberg, \textit{Math 4707 \&
Math 4990 Fall 2017 (Darij Grinberg): homework set 1 with solutions.}\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}
\end{thebibliography}


\end{document}