% Like most advanced LaTeX files, this one begins with a lot of
% boilerplate. You don't need to understand (or even read) most of it.
% All you need to do is fill in your name, UMN ID, email address,
% and the number of the pset. (Search for "METADATA" to find the place
% for this.) Then, you can go straight to the "EXERCISE 1"
% section and start writing your solutions.
% The "VARIOUS USEFUL COMMANDS" section is probably worth taking a
% look at at some point.

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[paper=a4, fontsize=12pt]{scrartcl} % A4 paper and 12pt font size
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages
\usepackage{mathrsfs}    % More math packages
\usepackage{sectsty}  % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all section titles centered, the default font and small caps %remove this to left align section tites
\usepackage{hyperref} % Turns cross-references into hyperlinks,
                      % and defines \url and \href commands.
\usepackage{graphicx} % For embedding graphics files.
\usepackage{framed}   % For the "leftbar" environment used below.
\usepackage{ifthen}   % Used for the \powset command below.
\usepackage{lastpage} % for counting the number of pages
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}     % This is a powerful tool to draw vector
                      % graphics inside LaTeX. In particular, you can
                      % use it to draw graphs.
\usepackage{verbatim} % For the "verbatim" environment, in which
                      % special symbols can be used freely without
                      % confusing the compiler. (And it's typeset in
                      % a constant-width font.)
                      % Useful, e.g., for quoting code (or ASCII art).
\usepackage{ytableau}

%\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{20pt} % Makes indentation for paragraphs longer.
                           % This makes paragraphs stand out more.

%----------------------------------------------------------------------------------------
%	VARIOUS USEFUL COMMANDS
%----------------------------------------------------------------------------------------
% The commands below might be convenient. For example, you probably
% prefer to write $\powset[2]{V}$ for the set of $2$-element subsets
% of $V$, rather than writing $\mathcal{P}_2(V)$.
% Notice that you can easily define your own commands like this.
% Caveat: Some of these commands need to be properly "guarded" when
% they occur in subscripts or superscripts. So you should not write
% $K_\CC$, but rather $K_{\CC}$.
\newcommand{\CC}{\mathbb{C}} % complex numbers
\newcommand{\RR}{\mathbb{R}} % real numbers
\newcommand{\QQ}{\mathbb{Q}} % rational numbers
\newcommand{\NN}{\mathbb{N}} % nonnegative integers
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}} % integers modulo k
                                            % (syntax: "\Z{k}")
\newcommand{\ZZ}{\mathbb{Z}} % integers
\newcommand{\id}{\operatorname{id}} % identity map
\newcommand{\lcm}{\operatorname{lcm}}
% Lowest common multiple. For historical reasons, LaTeX has a \gcd
% command built in, but not an \lcm command. The preceding line
% rectifies that.
\newcommand{\rev}{\operatorname{rev}} % reversal of a walk
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ compiles to {...} (set-brackets).
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ compiles to |...| (absolute value, or size of a set).
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ compiles to (...) (parentheses, or tuple-brackets).
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ compiles to [...] (Iverson bracket, aka truth value).
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ compiles to V(...) (vertex set of a graph/digraph).
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ compiles to E(...) (edge set of a graph).
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ compiles to A(...) (arc set of a digraph).
\newcommand{\lf}[2]{#1^{\underline{#2}}}
% $\lf{...1}{...2}$ compiles to $...1^{\underline{...2}}$.
% This is a notation for the falling factorial.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications. For example, try this out:
% $ \underbrack{(a+b)^2}{= a^2 + 2ab + b^2 \\ \text{(by the binomial formula)}} $
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\newcommand{\nnn}{\nonumber\\} % Don't number this line in an "align" environment, and move on to the next line.

%----------------------------------------------------------------------------------------
%	MAKING SUMMATION SIGNS ALWAYS PUT THEIR BOUNDS ABOVE AND BELOW
%	THE SIGN
%----------------------------------------------------------------------------------------
% The following are hacks to ensure that sums (such as
% $\sum_{k=1}^n k$) always put their bounds (i.e., the $k=1$ and the
% $n$) underneath and above the sign, as opposed to on its right.
% Same for products (\prod), set unions (\bigcup) and set
% intersections (\bigcap). Remove the 8 lines below if you do not want
% this behavior.
\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}

%----------------------------------------------------------------------------------------
%	ENVIRONMENTS
%----------------------------------------------------------------------------------------
% The incantations below define how theorem environments
% (\begin{theorem} ... \end{theorem}) and their likes will look like.
\newtheoremstyle{plainsl}% <name>
  {8pt plus 2pt minus 4pt}% <Space above>
  {8pt plus 2pt minus 4pt}% <Space below>
  {\slshape}% <Body font>
  {0pt}% <Indent amount>
  {\bfseries}% <Theorem head font>
  {.}% <Punctuation after theorem head>
  {5pt plus 1pt minus 1pt}% <Space after theorem headi>
  {}% <Theorem head spec (can be left empty, meaning `normal')>

% Environments which make the text inside them slanted:
\theoremstyle{plainsl}
  \newtheorem{theorem}{Theorem}[section]
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{conjecture}[theorem]{Conjecture}
% Environments that don't:
\theoremstyle{definition}
  \newtheorem{definition}[theorem]{Definition}
  \newtheorem{example}[theorem]{Example}
  \newtheorem{exercise}[theorem]{Exercise}
  \newtheorem{examples}[theorem]{Examples}
  \newtheorem{algorithm}[theorem]{Algorithm}
  \newtheorem{question}[theorem]{Question}
 \theoremstyle{remark}
  \newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}

%----------------------------------------------------------------------------------------
%	METADATA
%----------------------------------------------------------------------------------------
\newcommand{\myname}{Darij Grinberg} % ENTER YOUR NAME HERE
\newcommand{\myid}{00000000} % ENTER YOUR UMN ID HERE
\newcommand{\mymail}{dgrinber@umn.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{1} % ENTER THE NUMBER OF THIS PSET HERE

%----------------------------------------------------------------------------------------
%	HEADER AND FOOTER
%----------------------------------------------------------------------------------------
\ihead{Solutions to homework set \#\psetnumber} % Page header left
\ohead{page \thepage\ of \pageref{LastPage}} % Page header right
\ifoot{\myname, \myid} % left footer
\ofoot{\mymail} % right footer

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------
\title{	
\normalfont \normalsize 
\textsc{University of Minnesota, School of Mathematics} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Math 5705: Enumerative Combinatorics, \\
Fall 2018:
Homework \psetnumber\\% The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{\myname}

\begin{document}

\maketitle % Print the title

\begin{center} % Delete this if you want to save space!
{\large due date: \textbf{Wednesday, 19 September 2018} at the beginning of class, \\
or before that by email or canvas.

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

%----------------------------------------------------------------------------------------
%	EXERCISE 1
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 1}

\subsection{Problem}

Let $n$ be a positive integer.

An $n$-tuple $\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2, 3}^n$
is said to be \textit{even} if the sum $i_1 + i_2 + \cdots + i_n$ is even.
(For example, the $4$-tuple $\tup{2, 3, 1, 2}$ is even, whereas
$\tup{1, 2, 3, 1}$ is not.)

Compute the number of all even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2, 3}^n$.

(Here and in all future exercises, all answers need to be proven.)

[\textbf{Hint:} Compare with Exercise 3 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw-template.pdf}{Homework set \#0}.]

\subsection{Solution}

[...]

%----------------------------------------------------------------------------------------
%	EXERCISE 2
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 2}

\subsection{Problem}

Let $n \in \NN$.

An $n$-tuple $\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2}^n$
is said to be \textit{even} if the sum $i_1 + i_2 + \cdots + i_n$ is even.
(For example, the $4$-tuple $\tup{2, 1, 1, 2}$ is even, whereas
$\tup{1, 2, 2, 2}$ is not.)

Let $e_n$ be the number of all even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2}^n$.

Prove that $e_n = \dfrac{3^n + 1}{2}$.

[\textbf{Hint:} Induction on $n$.]

\subsection{Solution}

[...]

%----------------------------------------------------------------------------------------
%	EXERCISE 3
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 3}

\subsection{Problem}

For any real number $x$ and any $k \in \NN$, we define the lower
factorial $\lf{x}{k}$ as in Exercise 2 of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw-template.pdf}{Homework set \#0}.
(Thus, $\lf{x}{k} = x \tup{x-1} \tup{x-2} \cdots \tup{x-k+1} = \prod_{i=0}^{k-1} \tup{x-i}$.
This boils down to $\lf{x}{0} = 1$ when $k = 0$, since empty products
are defined to be $1$.)

Let $k$, $a$ and $b$ be three positive integers such that
$k \leq a \leq b$. Prove that
\begin{equation}
\tup{k-1} \sum_{i=a}^b \dfrac{1}{\lf{i}{k}}
= \dfrac{1}{\lf{\tup{a-1}}{k-1}} - \dfrac{1}{\lf{b}{k-1}}.
\label{eq.exe3.claim}
\end{equation}

\subsection{Remark}

\begin{remark}
This is similar to Exercise 2 of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw-template.pdf}{Homework set \#0},
but here the lower factorials are in the denominators.
The analogous fact from calculus is
\[
\tup{k-1} \int_a^b \dfrac{1}{x^k} dx
= \dfrac{1}{a^{k-1}} - \dfrac{1}{b^{k-1}} .
\]
\end{remark}

\subsection{Solution}

[...]

%----------------------------------------------------------------------------------------
%	EXERCISE 4
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 4}

\subsection{Problem}

\begin{definition} \label{def.fib}
The
\textit{\href{https://en.wikipedia.org/wiki/Fibonacci_number}{Fibonacci
sequence}} is the sequence $\tup{f_0, f_1, f_2, \ldots}$ of
integers which is defined recursively by $f_0 = 0$, $f_1 = 1$, and
\begin{equation}
f_n = f_{n-1} + f_{n-2} \qquad \text{for all } n \geq 2 .
\label{eq.fib.rec}
\end{equation}
Here is a table of some of its first terms:
\[
\begin{tabular}{|c|cccccccccc|}
\hline
$n$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ \\ \hline
$f_n$ & $0$ & $1$ & $1$ & $2$ & $3$ & $5$ & $8$ & $13$ & $21$ & $34$ \\ \hline
\end{tabular}
\]
\end{definition}

Let $n \in \NN$. Recall some definitions from class:

Let $R_{n,2}$ denote the set $\ive{n} \times \ive{2}$,
which we regard as a rectangle
of width $n$ and height $2$ (by identifying the squares with pairs of
coordinates).

A \textit{vertical domino} is a set of the form
$\set{ \tup{i, j}, \tup{i, j+1} }$ for some $i \in \ZZ$ and $j \in \ZZ$.

A \textit{horizontal domino} is a set of the form
$\set{ \tup{i, j}, \tup{i+1, j} }$ for some $i \in \ZZ$ and $j \in \ZZ$.

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*}
% Ugly code below, sorry.
\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}
\ , \qquad
\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}
\ , \\
\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}
\ , \qquad
\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}
\ , \qquad
\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}%
\ .
\end{align*}
Written as a set of dominos, the second of these tilings is
\[
\set{ \set{ \tup{1, 1}, \tup{1, 2} },
      \set{ \tup{2, 1}, \tup{2, 2} },
      \set{ \tup{3, 1}, \tup{4, 1} },
      \set{ \tup{3, 2}, \tup{4, 2} } }.
\]

We have seen in class
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-05.pdf}{September 5})
that
\begin{equation}
\text{the number of domino tilings of $R_{n,2}$ is $f_{n+1}$.}
\label{eq.exe.domino.censymm.fn+1}
\end{equation}

We have also counted ``axisymmetric'' domino tilings.

Let us now define a different kind of symmetry:
A domino tiling $S$ of $R_{n,2}$ is said to be \textit{centrosymmetric} if
reflecting it across the center of the rectangle $R_{n,2}$ leaves it
unchanged.
(Formally, if $S$ is regarded as a set, it means that for every
domino $\set{ \tup{i, j}, \tup{i', j'} } \in S$, its
``opposite domino''
$\set{ \tup{n+1-i, 3-j}, \tup{n+1-i', 3-j'} }$ is also in $S$.)
For example, among the $5$ domino tilings of
$R_{4,2}$ listed above, exactly $3$ are centrosymmetric (namely, the first, the
fourth and the fifth).

Let $s_n$ be the number of centrosymmetric domino tilings of $R_{n,2}$.

\begin{enumerate}

\item[\textbf{(a)}] Prove that $s_n = f_{\tup{n+1}/2}$ if $n$ is odd.

\item[\textbf{(b)}] Prove that $s_n = f_{n/2+2}$ if $n$ is even.

\end{enumerate}

(Note that these are the same numbers as for axisymmetric domino
tilings!)

[\textbf{Hint:} This is a bit of a trick problem.]

\subsection{Solution}

[...]

%----------------------------------------------------------------------------------------
%	EXERCISE 5
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 5}

\subsection{Problem}

Let $n \in \NN$.
Let $S_{n,2}$ be the set
\[
\tup{\ive{n+1} \times \ive{2}} \setminus \set{ \tup{1, 2}, \tup{n+1, 1} } .
\]
For example, here is how $S_{6,2}$ looks like:
\[
\ydiagram{1+6, 0+6}
\]
Find the number of domino tilings of $S_{n,2}$.

\subsection{Solution}

[...]

%----------------------------------------------------------------------------------------
%	EXERCISE 6
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 6}

\subsection{Problem}

Let $n \in \NN$.
If $S$ is a finite nonempty set of integers, then $\max S$ denotes the
maximum of $S$ (that is, the largest element of $S$).

\begin{enumerate}

\item[\textbf{(a)}]
Find the number of nonempty subsets $S$ of $\ive{n}$
satisfying $\max S = \abs{S}$.

\item[\textbf{(b)}]
Find the number of nonempty subsets $S$ of $\ive{n}$
satisfying $\max S = \abs{S} + 1$.

\end{enumerate}

[\textbf{Hint:} Exercise 7 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw1s.pdf}{Spring 2018 Math 4707 Homework set \#1}
is similar to part \textbf{(a)}, but uses the minimum
instead of the maximum.
Does this mean the answer should be similar?]

\subsection{Solution}

[...]

%----------------------------------------------------------------------------------------
%	EXERCISE 7
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 7}

\subsection{Problem}

For any nonnegative integers $a$ and $b$ and any real $x$,
prove that
\begin{equation}
\lf{x}{a} \lf{x}{b}
= \sum_{r = \max\set{a, b}}^{a+b}
    \dfrac{a! b!}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!} \lf{x}{r} .
\label{eq.exe7.XrXs}
\end{equation}

[\textbf{Hint:} Induction. First show the identities
$\lf{x}{k} = \lf{x}{k-1} \tup{x-k+1}$ and
$x \lf{x}{k} = \lf{x}{k+1} + k \lf{x}{k}$.]

\subsection{Solution}

[...]

\end{document}

