% 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]{\ZZ/#1\ZZ} % 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{\Des}{\operatorname{Des}} % descent set of a permutation
\newcommand{\des}{\operatorname{des}} % descent number of a permutation
\newcommand{\OLN}{\operatorname{OLN}} % one-line notation of a permutation
\newcommand{\cyc}{\operatorname{cyc}} % notation for cyclic permutations
\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{\floor}[1]{\left\lfloor #1 \right\rfloor}
% $\floor{...}$ compiles to |_..._| (floor function).
\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{\euleri}[2]{\genfrac{\langle}{\rangle}{0pt}{0}{#1}{#2}}
% $\euleri{...1}{...2} compiles to the angular-brackets notation
% for the Eulerian number of $n$ and $k$.
\newcommand{\ii}{\mathbf{i}} % integers
\newcommand\kstaircasepath[6]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
-- ++(0,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\draw[dashed] (#1) -- +(#5,#6);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
\coordinate (dep) at (0,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\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.
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}} % Quotient of division with remainder.

%----------------------------------------------------------------------------------------
%	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}{3} % ENTER THE NUMBER OF THIS PSET HERE

%----------------------------------------------------------------------------------------
%	HEADER AND FOOTER
%----------------------------------------------------------------------------------------
\ihead{Solutions to midterm \#\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:
Midterm \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, 12 December 2018} at the beginning of class, \\
or before that by email or canvas.

Please solve \textbf{at most 3 of the 7 exercises}!

Beware: \textbf{Collaboration is not allowed} on midterms!}
\end{center}

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

\section*{Notations}

Here is a list of notations that are used in this homework:

\begin{itemize}

\item As usual, $\NN$ means the set $\set{0, 1, 2, \ldots}$
of all nonnegative integers.

\item We shall use the Iverson bracket notation as well as the notation
$\ive{n}$ for the set $\set{1, 2, \ldots, n}$ (when $n \in \ZZ$).

\item If $n \in \NN$, then $S_n$ denotes the set of all permutations
of $\ive{n}$.

\item A \textit{point} shall mean an element of $\ZZ^2$, that is, a
pair of integers. We depict these points as lattice points on the Cartesian
plane, and add and subtract them as vectors. Recall the notion of a
\textit{lattice path}, defined in \S 6.1
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-12.pdf}{class
notes from 2018-11-12}) and (equivalently) in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/mt1s.pdf}{UMN Spring 2018
Math 4707 Midterm 1}. (Lattice paths have up-steps and right-steps.)
We abbreviate ``lattice path'' as ``\textit{LP}''.

\item A \textit{formal power series} (short \textit{FPS}) shall always mean a
formal power series in the indeterminate $x$ with rational coefficients
(as defined in class).

If $f$ is an FPS and if $n \in \NN$, then $\ive{x^n} f$ shall
denote the coefficient of $x^n$ in $f$.

\end{itemize}

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

\section{Exercise 1}

\subsection{Problem}

Let $n \in \NN$. Let $x \in \QQ$ and $y \in \QQ$.

\begin{enumerate}
\item[\textbf{(a)}]
Prove that
\[
\sum_{k=0}^n \dbinom{n}{k} \tup{x+k}^k \tup{y-k}^{n-k}
= \sum_{t=0}^n \dfrac{n!}{t!} \tup{x+y}^t .
\]

\item[\textbf{(b)}]
Prove that
\[
\sum_{k=0}^n \dbinom{n}{k} x \tup{x+k}^{k-1} \tup{y-k}^{n-k}
= \tup{x+y}^n .
\]
(Here, the ``$x \tup{x+k}^{k-1}$'' expression should be understood
as $1$ when $k=0$; this gives it meaning even if $x=0$.)
\end{enumerate}

[\textbf{Hint:} \textbf{(a)} Expand $\tup{x+k}^k$ and
$\tup{y-k}^{n-k}$ by the binomial theorem, then try using
\cite[Exercise 2]{Grinbe18}.

\textbf{(b)} Rewrite $x \tup{x+k}^{k-1}$ as
$\tup{x+k}^k - k \tup{x+k}^{k-1}$, thus splitting the left hand side into two
sums. Apply part \textbf{(a)} to both of them.]

\subsection{Solution}

[...]

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

\section{Exercise 2}

\subsection{Problem}

Let $n$ be a positive integer.

\begin{enumerate}
\item[\textbf{(a)}]
Let $A$ be the $n \times n$-matrix
$\tup{ \ive{ i \neq j } }_{i, j \in \ive{n}}$.
(This is the $n \times n$-matrix whose diagonal entries are
$0$ while all its other entries are $1$.
For example, for $n=3$, it is
$\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{pmatrix}$.)

Prove that $\det A = \tup{-1}^{n-1} \tup{n-1}$.

\item[\textbf{(b)}]
Prove that
\[
\sum_{\substack{\sigma \in S_n \text{ is a}\\ \text{derangement}}}
\tup{-1}^\sigma
= \tup{-1}^{n-1} \tup{n-1} .
\]

\item[\textbf{(c)}]
Let $b_1, b_2, \ldots, b_n$ be any $n$ numbers.
Let $B$ be the $n \times n$-matrix
$\tup{ \ive{ i \neq j } \prod_{h \in \ive{n} \setminus \set{i, j}} b_h }
_{i, j \in \ive{n}}$.
(For example, for $n=4$, we have
\[
B=
\begin{pmatrix}
0 & b_3 b_4  & b_2 b_4  & b_2 b_3 \\
b_3 b_4  & 0 & b_1 b_4  & b_1 b_3 \\
b_2 b_4  & b_1 b_4  & 0 & b_1 b_2 \\
b_2 b_3  & b_1 b_3  & b_1 b_2  & 0
\end{pmatrix} . \text{ )}
\]
Prove that
\[
\det B
= \tup{-1}^{n-1} \tup{n-1} \prod_{h \in \ive{n}} b_h^{n-2} .
\]
(Here, the
``$\tup{-1}^{n-1} \tup{n-1} \prod_{h \in \ive{n}} b_h^{n-2}$''
expression should be understood as $0$ if $n = 1$, even if
$\prod_{h \in \ive{n}} b_h^{n-2}$ may be undefined in this case
when some of the $b_h$ are $0$.)

\end{enumerate}

[\textbf{Hint:} \textbf{(a)} If you need a reminder on the basic properties
of determinants, see, e.g., \cite[Exercises 6.7 and 6.8]{detnotes}.

\textbf{(c)} If you divide by some $b_h$ in your proof,
make sure to argue why this is legitimate, or separately treat
the case when some of the $b_h$ are $0$.
(There is a combinatorial proof that does not require any division.)]

\subsection{Solution}

[...]

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

\section{Exercise 3}

\subsection{Problem}

Let $n$ be a positive integer.
If $\ii = \tup{ i_1, i_2, \ldots, i_n } \in \set{0, 1}^n$
and $k \in \ive{n}$, then

\begin{itemize}
\item we say that $k$ is a \textit{1-position} of $\ii$ if $i_k = 1$;

\item we say that $k$ is a \textit{10-position} of $\ii$ if $k < n$,
$i_k = 1$ and $i_{k+1} = 0$;

\item we say that $k$ is a \textit{cyclic 10-position} of $\ii$ if
$i_k = 1$ and $i_{k+1} = 0$, where $i_{n+1}$ is understood to be $i_1$.
% (This latter notion only makes sense when $n > 0$.)
\end{itemize}

(The first two of these concepts have already been defined in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw2s.pdf}{Homework set \#2}
Exercise 5.
The concept of a ``cyclic 10-position'' differs from that of a
``10-position'' only in that we consider the $n$-tuple to
``wrap around''.)

Let $k \in \NN$ and $a \in \set{0, 1, \ldots, n-1}$.
Prove the following:

\begin{enumerate}
\item[\textbf{(a)}]
The number of $n$-tuples $\ii \in \set{0, 1}^n$ having exactly $a$
1-positions and exactly $k$ 10-positions
is $\dbinom{a}{k} \dbinom{n-a}{k}$.

\item[\textbf{(b)}]
The number of $n$-tuples $\ii \in \set{0, 1}^n$ having exactly $a$
1-positions and exactly $k$ cyclic 10-positions is
$\dfrac{n}{n-a} \dbinom{a-1}{a-k} \dbinom{n-a}{k}$
(this expression should be interpreted as $\ive{k = 0}$ when $a = n$).

\item[\textbf{(c)}]
The number of $n$-tuples $\ii \in \set{0, 1}^n$ starting with a $0$
and having exactly $a$ 1-positions and exactly
$k$ cyclic 10-positions is $\dbinom{a-1}{a-k} \dbinom{n-a}{k}$.
\end{enumerate}

\subsection{Remark}

\begin{enumerate}
\item You can rewrite the ``$\dbinom{a}{k}$'' in part \textbf{(a)}
as ``$\dbinom{a}{a-k}$'' in order to make the similarity to the
other two parts more glaring.
Likewise, you could rewrite the ``$\dbinom{a-1}{a-k}$'' in parts
\textbf{(b)} and \textbf{(c)} as $\dbinom{a-1}{k-1}$ when $a > 0$,
but not in the border case when $a = 0$.

\item Sanity check: By summing over all $a$, we conclude from part
\textbf{(a)} that the number of $n$-tuples $\ii \in \set{0, 1}^n$
having exactly $k$ 10-positions is
\[
\sum_{a=0}^n \dbinom{a}{k} \dbinom{n-a}{k} = \dbinom{n+1}{2k+1}
\]
(by a simple application of Proposition 2.21 in the
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-26.pdf}{class from 2018-09-26}).
This is exactly the result of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw2s.pdf}{Homework set \#2}
Exercise 5.

\item Part \textbf{(b)} has an application to counting
$\tup{a, b}$-legal paths in the sense of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-14.pdf}{\S 6.4 from class}.

Indeed, let $a$ and $b$ be two coprime positive integers. We say that an LP
$\mathbf{v}$ is \textit{$\tup{a, b}$-legal} if each
$\tup{x, y} \in \mathbf{v}$ satisfies $ax \geq by$.
Proposition 6.7 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-14.pdf}{the
class from 2018-11-14} shows that the number of $\tup{a, b}$-legal
paths from $\tup{0, 0}$ to $\tup{b, a}$ is
$\dfrac{1}{a+b}\dbinom{a+b}{a}$.
(This is a so-called \textit{rational Catalan number}\footnote{
The word ``rational'' refers to the fact that the line $ax = by$ has
a rational (not integer in general) slope; the rational Catalan
number is still an integer.}.)

Now, let us define a \textit{left turn} of an LP $\mathbf{v}
= \tup{ v_0, v_1, \ldots, v_n }$ to be an $i \in \ive{n-1}$ such
that the $i$-th step of $\mathbf{v}$ is a right-step (i.e., we have
$v_i - v_{i-1} = \tup{1, 0}$) but the $\tup{i+1}$-st step
of $\mathbf{v}$ is an up-step (i.e., we have $v_{i+1} - v_i = \tup{0, 1}$).
For instance, the LP from $\tup{0, 0}$ to $\tup{8, 5}$ depicted in
\[
\begin{tikzpicture}
\kstaircasepath{0,0}{8}{5}{1,1,0,1,1,0,1,1,1,0,0,1,0}{8}{5};
\end{tikzpicture}
\]
is $\tup{5, 8}$-legal and has the left turns $2$, $5$, $9$ and $12$.

Now, given $k \in \NN$, we claim that the number of
$\tup{a, b}$-legal LPs from $\tup{0, 0}$ to $\tup{b, a}$ having
exactly $k$ left turns is
$\dfrac{1}{b} \dbinom{a-1}{a-k} \dbinom{b}{k}$
(this is a so-called \textit{rational Narayana number}).
Indeed, set $n = a + b$; then,
every LP from $\tup{0, 0}$ to $\tup{b, a}$ can be encoded
as an $n$-tuple $\ii \in \set{0, 1}^n$ with $a$ 1-positions
(by encoding each right-step as a $0$ and each up-step as a $1$).
If a given LP is encoded by an $n$-tuple $\tup{ i_1, i_2, \ldots, i_n }$,
then its shift (defined as in the proof of Proposition 6.7
in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-14.pdf}{the
class from 2018-11-14}) is encoded by the $n$-tuple
$\tup{ i_2, i_3, \ldots, i_n, i_1 }$. As we know, each cycle of $S$ (again, see
the proof of Proposition 6.7 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-14.pdf}{the
class from 2018-11-14} for the definition of $S$) has size $a + b$ and contains
exactly one $\tup{a, b}$-legal LP;
this $\tup{a, b}$-legal LP clearly starts with a right-step and ends
with an up-step;
hence it is easy to see that its left turns are in bijection with
the cyclic 10-positions of the corresponding $n$-tuple\footnote{
Indeed, if we define ``cyclic 01-positions'' in the obvious way, then
the left turns of our $\tup{a, b}$-legal LP are exactly the cyclic
01-positions of the corresponding $n$-tuple. But the latter are
in bijection with the cyclic 10-positions, because the cyclic
01-positions and the cyclic 10-positions alternate.}. It is
now easy to conclude from part \textbf{(b)} that the number of
$\tup{a, b}$-legal LPs from $\tup{0, 0}$ to $\tup{b, a}$
having exactly $k$ left turns is
$\dfrac{1}{n-a} \dbinom{a-1}{a-k} \dbinom{n-a}{k}
= \dfrac{1}{b} \dbinom{a-1}{a-k} \dbinom{b}{k}$.

\item It may be easiest to solve the problem starting with part \textbf{(c)}.
\end{enumerate}

\subsection{Solution}

[...]

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

\section{Exercise 4}

\subsection{Problem}

An \textit{integer formal power series} (short \textit{IFPS}) shall mean a
formal power series whose coefficients all are integers.
For example, $1 - 2x + 3x^2 - 4x^3 \pm \cdots$ is an IFPS,
while $1 - \dfrac{1}{2} x$ is not.

If $m$ is an integer, and if $a$ and $b$ are two IFPSs, then we say that
$a \equiv b \mod m$ if and only if there exists an IFPS $c$ such
that $a - b = mc$.
(This is completely analogous to the definition of congruence
modulo $m$ for integers.)
The following facts hold:

\begin{enumerate}
\item[(A1)] Two IFPSs $a$ and $b$ and an integer $m$ satisfy
$a \equiv b \mod m$ if and only if each $n \in \NN$ satisfies
$\ive{x^n} a \equiv \ive{x^n} b \mod m$ (that is,
each coefficient of $a$ is congruent to the corresponding coefficient of $b$
modulo $m$).

\item[(A2)] Each integer $m$ and each IFPS $a$ satisfy
$a \equiv a \mod m$.

\item[(A3)] If $m$ is an integer, and if $a$ and $b$ are two IFPSs satisfying
$a \equiv b \mod m$, then $b \equiv a \mod m$.

\item[(A4)] If $m$ is an integer, and if $a$, $b$ and $c$ are three IFPSs
satisfying $a \equiv b \mod m$ and $b \equiv c \mod m$,
then $a \equiv c \mod m$.

\item[(A5)] If $m$ is an integer, and if $a$, $b$, $c$ and $d$ are four IFPSs
satisfying $a \equiv c \mod m$ and $b \equiv d \mod m$,
then
\[
a + b \equiv c + d \mod m, \qquad
a - b \equiv c - d \mod m, \qquad \text{and }
a   b \equiv c   d \mod m .
\]

\item[(A6)] If $m$ is an integer, and if $a$ and $b$ are two IFPSs with
constant terms $\pm1$ (that is, $\ive{x^0} a = \pm1$ and
$\ive{x^0} b = \pm1$) satisfying $a \equiv b \mod m$, then
\[
a^{-1} \equiv b^{-1} \mod m.
\]

\item[(A7)] If $m$ is an integer and $n$ is a nonnegative integer, and if $a$
and $b$ are two IFPSs satisfying $a \equiv b \mod m$, then
\[
a^n \equiv b^n \mod m.
\]
Furthermore, if $a$ and $b$ have constant terms $\pm1$, then this also holds
for negative $n$.
\end{enumerate}

(You can use all these seven facts without proof, but if you are curious: Fact
(A1) is essentially obvious; facts (A2)--(A5) are proven just as for integers.
Fact (A6) follows by observing that
$a^{-1} - b^{-1} = - a^{-1} b^{-1} \tup{a-b}$,
since the assumption on the constant terms forces $a^{-1}$ and $b^{-1}$ to be
well-defined IFPSs.
Finally, fact (A7) is proven by forwards induction for
$n \geq 0$ and then by backwards induction for $n < 0$.)

\vspace{0.8pc}

Now, let $p$ be a prime.

\begin{enumerate}
\item[\textbf{(a)}]
Prove that $\tup{1 + x}^p \equiv 1 + x^p \mod p$.

\item[\textbf{(b)}]
Prove \textit{Lucas's congruence}:
Any $a, b \in \ZZ$ and $c, d \in \set{0, 1, \ldots, p-1}$ satisfy
\[
\dbinom{ap+c}{bp+d} \equiv \dbinom{a}{b} \dbinom{c}{d} \mod p.
\]

\item[\textbf{(c)}]
Prove that if $m \in \NN$, and if $a$ and $b$ are two
IFPSs satisfying $a \equiv b \mod m$, then
$a^m \equiv b^m \mod m^2$.

\item[\textbf{(d)}]
Prove that any $a, b \in \ZZ$ satisfy
\[
\dbinom{ap}{bp} \equiv \dbinom{a}{b} \mod p^2 .
\]

\end{enumerate}

[\textbf{Hint:} \textbf{(a)} What do you remember about $\dbinom{p}{k}$ ?

\textbf{(b)} $\tup{1 + x}^{ap+c} = \tup{ \tup{1+x}^p }^a \tup{1+x}^c$.
It is helpful to define $\ive{x^n} f = 0$ for any negative $n$ and
any FPS $f$.

\textbf{(c)} Write $a$ as $b+mc$ for some IFPS $c$.
The same congruence holds for integers.]

\subsection{Solution}

[...]

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

\section{Exercise 5}

\subsection{Problem}

For each $n \in \NN$, we define two FPSs $P_n$ and $S_n$ by
\[
P_n = \prod_{s=1}^n \tup{1 - x^s}  \qquad \text{and} \qquad
S_n = \sum_{s=-n}^n \tup{-1}^s x^{s\tup{3s+1}/2}.
\]

(For example,
\[
P_4 =
\tup{1-x} \tup{1-x^2} \tup{1-x^3} \tup{1-x^4}
= 1 - x - x^2 + 2x^5 - x^8 - x^9 + x^{10}
\]
and
\[
S_4
= 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} .\ \ \text{)}
\]


\begin{enumerate}
\item[\textbf{(a)}]
Show that $S_n$ is well-defined, i.e., that all of the
exponents $s\tup{3s+1}/2$ are nonnegative integers (even when $s < 0$).

\item[\textbf{(b)}] Set
\[
F_n = \sum_{s=0}^n \tup{-1}^s \dfrac{P_n}{P_s} x^{sn+s\tup{s+1}/2}
\qquad \text{for each }n \in \NN .
\]

Show that $F_n = S_n$ for each $n \in \NN$.
\end{enumerate}

[\textbf{Hint:} \textbf{(b)} Induction on $n$. In the induction step, use
$P_n = P_{n-1} - x^n P_{n-1}$ to split the sum defining $F_n$ into two
subsums after first splitting off the $s = n$ addend. This leads to
$F_n - F_{n-1} = S_n - S_{n-1}$.]

\subsection{Remark}

If we take the limit $n \to \infty$ in the claim of part \textbf{(b)}
(see \cite[\S 7.5]{Loehr-BC} for the meaning of ``limit'' here),
then we quickly obtain
\[
\prod_{s=1}^{\infty} \tup{1 - x^s}
= \sum_{s=-\infty}^{\infty} \tup{-1}^s x^{s\tup{3s+1}/2}.
\]
(Indeed, each of the addends
$\tup{-1}^s \dfrac{P_n}{P_s} x^{sn+s\tup{s+1}/2}$ for $s>0$ tends to
$0$ when $n \to \infty$.)
This is Euler's pentagonal number theorem again.

\subsection{Solution}

[...]

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

\section{Exercise 6}

\subsection{Problem}

Recall that we are using the following notations:

\begin{itemize}
\item A \textit{partition} means a weakly decreasing sequence of
positive integers.
(Thus, a partition is the same as a partition of some $n \in \NN$.)

\item Given any $n \in \ZZ$, we let $p \tup{n}$ denote the
number of all partitions of $n$.
(This is $0$ when $n < 0$.)

\item Given any $n \in \ZZ$ and $k \in \NN$, we let $p_k \tup{n}$
denote the number of all partitions of $n$ into $k$ parts.
\end{itemize}

Prove the following:

\begin{enumerate}
\item[\textbf{(a)}]
Any $n \in \NN$ satisfies
\[
n p \tup{n}
= \sum_{k=1}^n \sigma \tup{k} p \tup{n-k} ,
\]
where $\sigma \tup{k}$ denotes the sum of all positive divisors of
$k$.

\item[\textbf{(b)}] Any $n \in \NN$ satisfies
\[
\sum_{k=0}^n k p_k \tup{n}
= \sum_{k=1}^n \partial \tup{k} p \tup{n-k} ,
\]
where $\partial \tup{k}$ denotes the number of positive divisors of
$k$.

\item[\textbf{(c)}]
Let $a : \set{1, 2, 3, \ldots} \to \QQ$ be any map.
For any partition $\lambda = \tup{\lambda_1, \lambda_2, \ldots, \lambda_k}$,
we let $a \tup{\lambda}$ denote the sum
$a \tup{\lambda_1} + a \tup{\lambda_2} + \cdots + a \tup{\lambda_k}$.
Then, any $n \in \NN$ satisfies
\[
\sum_{\lambda \vdash n} a \tup{\lambda}
= \sum_{k=1}^n \tup{ \sum_{d \mid k} a \tup{d} } p \tup{n-k} .
\]
Here, the summation sign ``$\sum_{\lambda \vdash n}$''
means ``sum over all partitions $\lambda$ of $n$'', whereas
the summation sign ``$\sum_{d \mid k}$'' means ``sum over all
positive divisors $d$ of $k$''.
\end{enumerate}

[\textbf{Hint:} Parts \textbf{(a)} and \textbf{(b)} are particular cases of
\textbf{(c)}. Particular cases are not always easier to prove than
generalizations.]

\subsection{Solution}

[...]

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

\section{Exercise 7}

\subsection{Problem}

Let $n$ be an even positive integer.

\begin{enumerate}
\item[\textbf{(a)}]
For each $\sigma \in S_n$, prove that there exist two
distinct elements $i$ and $j$ of $\ive{n}$ such that
$\sigma \tup{i} - i \equiv \sigma \tup{j} - j \mod n$.

\item[\textbf{(b)}] If $n$ people are seated around a table at lunch, and
the same $n$ people are seated around the same table at dinner, then prove
that you can find two distinct people which have the same distance at the
lunch as they have at the dinner.
(The \textit{distance} between two people means the number of persons
sitting between them, counted along the shorter arc, plus $1$.
For instance, two neighbors will have distance $1$.)

\item[\textbf{(c)}] Prove that both \textbf{(a)} and \textbf{(b)} are false if
$n=5$.

\item[\textbf{(d)}] What about $n=7$ ?
\end{enumerate}

[\textbf{Hint:} \textbf{(a)} If there are no such $i$ and $j$,
what can you say about the
remainders of the $n$ numbers
$\sigma \tup{1} - 1 , \sigma \tup{2} - 2 , \ldots , \sigma \tup{n} - n$
modulo $n$, and what can you say about
$\sum_{i=1}^n \tup{ \sigma \tup{i} - i }$ ?]

\subsection{Remark}

What about $n = 9$ ?
What about other odd $n$ ? (Talking about part \textbf{(b)}
in particular; the answer for part \textbf{(a)} is simple.)

\subsection{Solution}

[...]
\begin{thebibliography}{99999999}                                                                                         


\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[Grinbe18]{Grinbe18}Darij Grinberg,
\textit{\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw3s.pdf}{\textit{Solutions
to UMN Spring 2018 Math 4707 homework set \#3}}}.\\
\url{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw3s.pdf}

\bibitem[Loehr11]{Loehr-BC}
\href{http://www.math.vt.edu/people/nloehr/bijbook.html}{Nicholas A. Loehr,
\textit{Bijective Combinatorics}, Chapman \& Hall/CRC 2011.}
\end{thebibliography}

\end{document}

