\documentclass[12pt]{article}
\usepackage[margin=1in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath}
\usepackage{tikz}
\usepackage{substr}
\IfSubStringInString{\detokenize{solution}}{\jobname}{%
% Solutions
\newcommand\qfill{}
\newcommand\qpage{}
\newcommand\qonly[1]{}
\newcommand\answer[1]{#1}
\newcommand\question[1]{{\em #1}}
\newcommand\rubric[1]{}
}
{%
\newcommand\qfill{\vfill}
\newcommand\qpage{\newpage}
\newcommand\qonly[1]{#1}
\newcommand\answer[1]{}
\newcommand\question[1]{#1}
\newcommand\rubric[1]{}
}
\pagestyle{fancy}
\lhead{MATH 387-01}
\chead{Problem Set \#1\answer{ solutions}}
\rhead{\qonly{Name: \framebox{\phantom{Your name goes here}}}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due September 7, 2017}}
\begin{document}
\qonly{Show all your work, and explain why you use the arithmetic
operations you use in reaching an answer.}
\begin{enumerate}
\item {\bf (20 points)} \question{Answer the following questions about
counting strings, sets, and partitions.}
\begin{enumerate}
\item {\bf (10 points)} \question{Recall that the number of strings
of 5 distinct letters chosen from an alphabet of 7 is
$\frac{7!}{2!}=2520$. We divide this by $120$ to get the number
of sets of 5 distinct letters ($21$).
We also know that there are $7^5=16807$ strings of 5 freely
chosen letters chosen from an alphabet of 7. Why can't we use a
similar procedure to the one above to get the number of
multisets of 5 letters from these 7 (of which there are 462, for
reference). Describe the failure of this method in terms of the
objects being investigated; the fact that $7^5$ isn't divisible
by 120 isn't enough justification!}
\item {\bf (10 points)} \question{There are, as seen in class, 150
strings of length 5 using the letters A, B, and C, and using
each letter at least once. There are 25 ways to partition the
set $\{1,2,3,4,5\}$ into three subsets (possibly including empty
sets). Describe how these two things being counted are related,
and, specifically, how $150=6\times 25$ is relevant to the
counting.}
\end{enumerate}
\item {\bf (10 points)} \question{In some alien variant of poker
played with a standard deck of cards, a \emph{periflush} is a hand
of five cards where two cards have the same number, and the other
three cards are all of the same suit as each other and one of
those two cards: for instance,
$4\heartsuit\;4\clubsuit\;\text{J}\heartsuit\;3\heartsuit\;
7\heartsuit$ is a periflush since the fours form a pair, and the
other three cards together with one element of the pair are all of
the same suit, while
$9\spadesuit\;9\heartsuit\;3\heartsuit\;\text{Q}\spadesuit\;
\text{A}\heartsuit$ is not, since the non-pair cards are not all
of the same suit. What is the probability that, drawing five cards
at random, you draw a periflush? Recall that a standard poker deck
consists of 52 distinct cards, with 13 different numbers and 4
different suits.}
\item {\bf (10 points)} \question{Prove \emph{combinatorially} that,
for any integers $k$ and $n$ with $0\leq k\leq n$,
\[k\binom nk=n\binom{n-1}{k-1}.\]
}
\end{enumerate}
\vfill
\begin{center}
\fbox{
\begin{minipage}{6in}
Musica est exercitium arithmeticae occultum nescientis se
numerare animi.\answer{ [Music is an arithmetical exercise of
the soul, which is unaware that it is counting.]}
\hfill ---Gottfried Leibniz
\end{minipage}
}
\end{center}
\end{document}