\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, March 16, 2018 02:08:10}
%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): further reading}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 Spring 2018 (Darij Grinberg): further reading on counting
and binomial coefficients}
\end{center}%

%TCIMACRO{\TeXButton{tableofcontents}{\tableofcontents}}%
%BeginExpansion
\tableofcontents
%EndExpansion


\section{Some further reading}

We have spent weeks of class studying binomial coefficients and their
combinatorial uses. Still we have merely scratched the surface, and left the
non-combinatorial applications aside completely. If you are interested, here
are suggestions for further reading.

(A lot of the text are clickable links! Make sure your PDF viewer marks them
as such.)

\subsection{Basic counting applications}

\begin{itemize}
\item \href{http://www-users.math.umn.edu/~reiner/Classes/Poker.pdf}{Drew
Armstrong, \textit{Poker hand probabilities}}.

How likely is it that a random hand of $5$ cards (out of the $52$ in a
standard deck) forms a full house? a flush? etc.

\item \href{http://mathforum.org/dr.math/faq/faq.mcdonalds.html}{Dr. Math
(Mathforum), \textit{Fast Food Combinations}}.

In 2002, McDonalds was advertising that its $8$ McChoice menu items allow for
\textquotedblleft$40,312$ Possible Combinations\textquotedblright. A rare
occurence of an \textquotedblleft inverse counting problem\textquotedblright%
\ in real life, this has left people puzzled as to what exactly McDonalds
understood as a \textquotedblleft combination\textquotedblright. (Normally,
the word means \textquotedblleft subsets\textquotedblright, which is also what
one would expect to be advertised. But there are only $2^{8}=256$ of these.)

(This is also Exercise 1.1 in
\href{https://cameroncounts.files.wordpress.com/2016/04/acnotes1.pdf}{Peter J.
Cameron, \textit{Combinatorics 1: The art of counting}}.)
\end{itemize}

\subsection{Double counting}

\begin{itemize}
\item
\href{http://www-users.math.umn.edu/~reiner/Classes/Kolata-MythMathSex.txt}{Gina
Kolata, \textit{The Myth, the Math, the Sex}, NYT, August 12, 2007}.
\end{itemize}

\subsection{Fibonacci numbers}

Much has been written on Fibonacci numbers. Here is a whole book (you might be
able to download it on campus):

\begin{itemize}
\item \href{https://link.springer.com/book/10.1007/978-3-0348-8107-4}{Nicolai
N. Vorobiev, \textit{Fibonacci Numbers}, Springer 2002}.
\end{itemize}

The \href{https://en.wikipedia.org/wiki/Fibonacci_number}{Wikipedia article}
might also be one of the longest mathematical articles on the Wikipedia (and
yes, there is an
\href{https://en.wikipedia.org/wiki/Fibonacci_numbers_in_popular_culture}{\textquotedblleft
in popular culture\textquotedblright\ page}).

Mathematicians like Fibonacci numbers in particular because they're the
simplest example of a sequence satisfying a $3$-term constant linear
recurrence (that is, $x_{n}=ax_{n-1}+bx_{n-2}$ for some constants $a$ and
$b$). Other examples abound, some extremely important (e.g., the
\href{https://en.wikipedia.org/wiki/Chebyshev_polynomials}{Chebyshev
polynomials}, highly important in approximation and numerical mathematics,
follow the same sort of recurrence, except that $a$ and $b$ are polynomials).

Actual real-life applications of the Fibonacci numbers and the (closely
related) golden ratio are somewhat controversial: they exist, but are
overhyped and subtler than pop-sci likes to claim. Apparently, many species of
flower have $f_{n}$ petals for various values of $n$:

\begin{itemize}
\item \url{http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibnat.html#petals}
\end{itemize}

but others don't. It isn't clear to me whether the proponents are on to
something or are just seeing patterns in noise.

\begin{noncompile}
\url{https://www.quora.com/How-uncommon-is-it-that-the-number-of-petals-of-a-flower-are-not-a-Fibonacci-number}
\end{noncompile}

\begin{noncompile}
\url{http://mathforum.org/kb/message.jspa?messageID=4767802}
\end{noncompile}

Here is a recent paper that tries to clean up some of the mess:

\begin{itemize}
\item \href{https://arxiv.org/abs/1704.02880}{Fran\c{c}ois Bergeron,
Christophe Reutenauer, \textit{Golden Ratio and Phyllotaxis, what is the
mathematical link?}, arXiv:1704.02880}.
\end{itemize}

And no, rabbits aren't actually immortal.

\subsection{The German tank problem}

\begin{itemize}
\item \href{https://en.wikipedia.org/wiki/German_tank_problem}{Wikipedia,
\textit{German tank problem}}.

You have captured $4$ German tanks with serial numbers $19$, $40$, $42$ and
$60$. Assuming that Germans number their tanks systematically with
$1,2,3,\ldots$ (a valid assumption in World War II; these days, no longer so),
how many tanks would you expect the Germans to have in total?

This is per-se a statistics problem with several competing models. Binomial
coefficients figure prominently in the analysis.
\end{itemize}

\subsection{The \textquotedblleft freshman's dream\textquotedblright%
\ (applications to number theory)}

The binomial formula for $\left(  a+b\right)  ^{n}$ takes a rather simple form
when $n$ is a prime, as long as you only care about the remainder modulo this prime:

\begin{theorem}
\label{thm.freshman}Let $p$ be a prime number. Then, for any two integers $a$
and $b$, we have%
\[
\left(  a+b\right)  ^{p}\equiv a^{p}+b^{p}\operatorname{mod}p.
\]

\end{theorem}

Better yet, if you expand $\left(  a+b\right)  ^{p}$ by the binomial formula,
and subtract the two \textquotedblleft border terms\textquotedblright\ $a^{p}$
and $b^{p}$, then all remaining terms will be divisible by $p$:

\begin{theorem}
\label{thm.binom.pdiv}Let $p$ be a prime number. Then, the binomial
coefficient $\dbinom{p}{k}$ is divisible by $p$ for every $k\in\left\{
1,2,\ldots,p-1\right\}  $.
\end{theorem}

In other words, in the $p$-th row of Pascal's triangle, all entries other than
the two $1$'s are divisible by $p$. For example, the entries of the $5$-th row
are $1,5,10,10,5,1$, and all of them other than the two $1$'s are divisible by
$5$.

\begin{proof}
[Proof of Theorem \ref{thm.binom.pdiv} (sketched).]Every $n\in\mathbb{Q}$ and
$k\in\mathbb{Q}$ satisfy%
\begin{equation}
k\dbinom{n}{k}=n\dbinom{n-1}{k-1}. \label{pf.thm.binom.pdiv.abs}%
\end{equation}
(This is called the \textit{absorption identity}, and can easily be checked
using the definition of binomial coefficients. Just make sure to deal with the
cases $k\in\left\{  1,2,3,\ldots\right\}  $, $k=0$ and $k\notin\mathbb{N}$
separately, since they trigger different branches in the definition of
binomial coefficients.)

Now, let $k\in\left\{  1,2,\ldots,p-1\right\}  $. Applying
(\ref{pf.thm.binom.pdiv.abs}) to $n=p$, we obtain $k\dbinom{p}{k}%
=p\dbinom{p-1}{k-1}$. Hence, $p$ divides the product $k\dbinom{p}{k}$.

But a well-known property of prime numbers\footnote{see, e.g., Lemma 9.4.2 in
\href{https://courses.csail.mit.edu/6.042/spring18/mcs.pdf}{Eric Lehman, F.
Thomson Leighton, Albert R. Meyer, \textit{Mathematics for Computer Science},
revised 27 February 2018}} says that if $p$ divides the product of two
integers, then $p$ must divide (at least) one of these integers. Hence, $p$
must divide (at least) one of the integers $k$ and $\dbinom{p}{k}$ (because
$p$ divides their product). Since $p$ cannot divide $k$ (because $k\in\left\{
1,2,\ldots,p-1\right\}  $), we thus conclude that $p$ must divide $\dbinom
{p}{k}$. This proves Theorem \ref{thm.binom.pdiv}.
\end{proof}

A lot of number theory and abstract algebra is founded on Theorem
\ref{thm.binom.pdiv}. Just one application (which can be obtained in other
ways, too):

\begin{exercise}
\label{exe.binom.fermat}Prove \textit{Fermat's little theorem}:

\textbf{(a)} If $p$ is a prime, then $a^{p}\equiv a\operatorname{mod}p$ for
each integer $a$.

\textbf{(b)} If $p$ is a prime, then $a^{p-1}\equiv1\operatorname{mod}p$ for
each integer $a$ that is not divisible by $p$.
\end{exercise}

\subsection{Bertrand's postulate}

Another number-theoretical use of binomial coefficients is the proof of
\textit{Bertrand's postulate} (\textquotedblleft postulate\textquotedblright%
\ is an old word for \textquotedblleft conjecture\textquotedblright\ in this context):

\begin{theorem}
[Bertrand's postulate]\label{thm.bertrand}Let $n$ be a positive integer. Then,
there exists a prime $p\in\left\{  n+1,n+2,\ldots,2n\right\}  $.
\end{theorem}

For the proof (which relies on studying the prime factorization of binomial
coefficients), see:

\begin{itemize}
\item
\href{https://en.wikipedia.org/wiki/Proof_of_Bertrand's_postulate}{Wikipedia,
\textit{Proof of Bertrand's postulate}}.
\end{itemize}

Applications in a similar spirit include

\begin{itemize}
\item \href{https://arxiv.org/abs/0906.2295}{Bakir Farhi, \textit{An identity
involving the least common multiple of binomial coefficients and its
application}, arXiv:0906.2295},
\end{itemize}

which uses binomial coefficients to prove that $\operatorname{lcm}\left(
1,2,\ldots,k\right)  \geq2^{k-1}$ for all positive integers $k$.

Binomial coefficients also figure in the proof that the number $\dfrac
{1}{1^{3}}+\dfrac{1}{2^{3}}+\dfrac{1}{3^{3}}+\dfrac{1}{4^{3}}+\cdots$ (also
known as $\zeta\left(  3\right)  $) is irrational. See:

\begin{itemize}
\item \href{https://arxiv.org/abs/math/0202159}{Wadim Zudilin, \textit{An
elementary proof of Apery's theorem}, arXiv:math/0202159}.
\end{itemize}

\subsection{Who started it?}

Combinatorics has been around for a long time, but only in the last 60-or-so
years has it become a rigorous discipline with a usable \textquotedblleft
language\textquotedblright, and only in the last 30-or-so years has it become
one of the central subjects of mathematics. Before that, results were scarce,
often shallow and tended to appear in the unlikeliest places. Donald Knuth's
\textit{The Art of Computer Programming} (particularly, Volumes 3 and 4A)
collects many curious morsels from history: the lists of permutations compiled
by Medieval cabbalists;
\href{http://www.ramonllull.net/sw_studies/studies_original/compbon.html}{Ramon
Llull's 13th century studies in combining virtues and vices}; the
\href{https://blogs.ams.org/visualinsight/2015/06/15/lattice-of-partitions/}{peculiar
numbering of the 52 chapters of the Tale of Genji} (not by numbers, but by
some symbols resembling set partitions); the haphazard study of permutations
in 17th century England for the purpose of
\href{https://en.wikipedia.org/wiki/Method_ringing}{ringing church bells}; the
various attempts (starting with the ancient Greeks) to classify patterns of
rhyme and rhythm. One of the first extant deep results was the Chu-Vandermonde
convolution identity, which appeared in Zhu Shijie's work in the early 14th
century. The ancient Greeks, however, seem to have known more than they have
written up (or, at least, that has survived): Plutarch refers to a computation
made by Hipparchus that (while garbled and barely understandable in his
formulation) suggests that Hipparchus knew how to set up a recursion and solve
it. For details, see:

\begin{itemize}
\item
\href{https://link.springer.com/content/pdf/10.1007/s00407-003-0067-0.pdf}{F.
Acerbi, \textit{On the Shoulders of Hipparchus: A Reappraisal of Ancient Greek
Combinatorics}, Arch. Hist. Exact Sci. 57 (2003), pp. 465--502}.
\end{itemize}

\section{Problems in recent journals}

Undergraduate and educational math journals often have problem sections. These
are organized like a contest: Authors submit problems, readers submit solutions.

Here is a selection of combinatorial problems (reasonably close to what we
have done in class so far) from \textbf{recent} journals. \textquotedblleft
Recent\textquotedblright\ means that the contest is still ongoing, so
\textbf{you can submit your solutions to the journal} (and get your name
mentioned, perhaps even your solution published; looks good on a CV when
you're an undergrad...). Please don't spoil the contest -- don't ask for help
with these on the internet. If you collaborate, do name your collaborators.

[Feel free to browse these journals, too: a lot of them let you download their
issues from the UMN network.]

\subsection{American Mathematical Monthly}

Journal homepage: \newline\url{https://www.maa.org/press/periodicals/american-mathematical-monthly}

\begin{exercise}
\label{exe.AMM.12032}\textbf{American Mathematical Monthly \#12032, proposed
by David Galante and \'{A}ngel Plaza.}

\textbf{Deadline:} 31 July 2018.

\textbf{Submit to:} \url{http://www.americanmathematicalmonthly.submittable.com/submit}

For a positive integer $n$, compute%
\[
\sum_{p=0}^{n}\sum_{k=p}^{n}\left(  -1\right)  ^{k-p}\dbinom{k}{2p}\dbinom
{n}{k}2^{n-k}.
\]

\end{exercise}

\begin{exercise}
\label{exe.AMM.12022}\textbf{American Mathematical Monthly \#12022, proposed
by Mircea Merca.}

\textbf{Deadline:} 31 June 2018.

\textbf{Submit to:} \url{http://www.americanmathematicalmonthly.submittable.com/submit}

Let $n$ be a positive integer, and let $x$ be a real number not equal to $-1$
or $1$. Prove%
\[
\sum_{k=0}^{n-1}\dfrac{\left(  1-x^{n}\right)  \left(  1-x^{n-1}\right)
\cdots\left(  1-x^{n-k}\right)  }{1-x^{k+1}}=n
\]
and%
\[
\sum_{k=0}^{n-1}\left(  -1\right)  ^{k}\dfrac{\left(  1-x^{n}\right)  \left(
1-x^{n-1}\right)  \cdots\left(  1-x^{n-k}\right)  }{1-x^{k+1}}x^{\dbinom
{n-1-k}{2}}=nx^{\dbinom{n}{2}}.
\]
[\textbf{DG:} Yes, those binomial coefficients are in the exponents, even
though they might not look like that.]
\end{exercise}

\begin{exercise}
\label{exe.AMM.12016}\textbf{American Mathematical Monthly \#12016, proposed
by Hideyuki Ohtsuka and Roberto Tauraso.}

\textbf{Deadline:} 31 May 2018.

\textbf{Submit to:} \url{http://www.americanmathematicalmonthly.submittable.com/submit}

For nonnegative integers $m$, $n$, $r$, and $s$, prove%
\[
\sum_{k=0}^{s}\dbinom{m+r}{n-k}\dbinom{r+k}{k}\dbinom{s}{k}=\sum_{k=0}%
^{r}\dbinom{m+s}{n-k}\dbinom{s+k}{k}\dbinom{r}{k}.
\]

\end{exercise}

\begin{exercise}
\label{exe.AMM.12008}\textbf{American Mathematical Monthly \#12008, proposed
by P. Korus.}

\textbf{Deadline:} 30 April 2018.

\textbf{Submit to:} \url{http://www.americanmathematicalmonthly.submittable.com/submit}

You hold in your hand a deck of $n$ cards, numbered $1$ to $n$ from top to
bottom. Shuffle them as follows. Put the top card in the deck on the bottom
and the second card on the table. Repeat this step until all the cards are on
the table.

\textbf{(a)} For which $n$ does card number $1$ end up at the top of the deck
of cards on the table?

\textbf{(b)} Shuffle the deck a second time in the same way. For which $n$
does card number $1$ end up at the top of the cards on the table?

\textbf{(c)* (Unsolved!)} Shuffle the deck a third time in the same way. For
which $n$ does card number $1$ end up at the top of the cards on the table?

\textbf{(d)* (Unsolved!)} For which $n$ does this shuffle amount to a
permutation consisting of a single cycle?

[\textbf{Remark (DG):} \textquotedblleft Cycle\textquotedblright\ refers to
the concept of a
\href{https://en.wikipedia.org/wiki/Cyclic_permutation}{cyclic permutation}.
I'm not sure if the author means an $n$-cycle, or a $k$-cycle for some smaller
value of $k$, though; it can mean either.]
\end{exercise}

\subsection{Crux Mathematicorum}

Journal homepage: \url{https://cms.math.ca/crux/}

\begin{exercise}
\label{exe.crux.4314}\textbf{Crux Mathematicorum \#4314, proposed by Michel
Bataille.}

\textbf{Deadline:} 1 July 2018.

\textbf{Submit to:} \url{https://cms.math.ca/crux/contributors}

Let $n$ be a positive integer. Evaluate in closed form%
\[
\sum_{k=1}^{n}k2^{k}\cdot\dfrac{\dbinom{n}{k}}{\dbinom{2n-1}{k}}.
\]

\end{exercise}


\end{document}