\documentclass[12pt]{article}
\usepackage[margin=0.8in,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!}
\answer{The first calculation worked because every string of 5
\emph{distinct} letters has exactly 120 rearrangements, so each
set is associated with exactly 120 strings. There is no such
convenient fact for multisets and strings of potentially
identical letters: the multiset \{A, A, A, A, A\} is only
assoicated with one string, AAAAA, while \{A, A, A, B, B\} has
10 associated strings (AAABB, AABAB, AABBA, ABAAB, ABABA, ABBAA,
BAAAB, BAABA, BABAA, and BBAAA), and so forth. Because the
multiset-to-string correspondence is not one-to-many with a
consistent value of ``many'', there is no easy division to get
from a count of the strings to a count of the multisets.}
\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 nonempty subsets. Describe how
these two things being counted are related, and, specifically,
how $150=6\times 25$ is relevant to the counting.}
\answer{Here both scenarios we are considering can be interpreted
as a five-balls-into-three-boxes paradigm with the restriction
that each box is nonempty (this condition corresponds in the two
cases respectively to the requirement that each letter appear
once and the requirement that each of the sets are
nonempty). The main difference, however, is that in the first
scenario the boxes are labeled (the string ``ABBAC'' is
different from ``CAACB'' because A, B, and C are distinguishable
letters), whereas in the second they are not (the partition into
the sets $\{1,4\}$, $\{2,3\}$, and $\{5\}$ is the same as the
partition into the sets $\{2,3\}$, $\{5\}$, and
$\{1,4\}$). However, if we were to consider how we can label the
boxes, we shall see that every partition admits exactly six
labelings: the boxes are already intrinsically distinguished by
their contents, so there are 3 choices as to which box to label
``A'', and then, two choices of which remaining box to label
``B'', and then only one choice for where the label ``C''
goes. Thus each partiton can be transformed into six distinct
strings: by way of illustration, we could observe that the
above-mentioned partition into $\{1,4\}$, $\{2,3\}$, and $\{5\}$
determines specifically the 6 strings ABBAC, ACCAB, BAABC,
BCCBA, CAACB, and CBBCA.
Note that this division process would \emph{not} quite work
between the 243 free strings and the 41 partitions with possibly
empty sets, because the partition into
$\{1,2,3,4,5\}$ and two empty sets only has 3 associated
strings, not 6. This occurs because there is no intrinsic
``distinguishability'' between the two empty sets.}
\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.}
\answer{There are many different possible calculations, but they all
should give the same answer when multiplied out. We might select
any of the 13 possible values for the pair, and then any of the
$\binom 42$ possibilities for the suits used in the pair. Then one
of those two suits should be chosen as the ``mini-flush'' suit, so
there is a choice from among 2 alternatives to be made
there. Finally, the values for the remaining three cards in the
mini-flush must be selected from among the 12 values not appearing
in the pair, so there are $\binom{12}3$ possible choices
there. Multiplying all these together, there are
\[13\cdot\binom 42\cdot2\cdot\binom{12}3=34320\] possible
periflushes. Since there are $\binom{52}5=2598960$ possible hands
in total, the probability of a periflush is
$\frac{34320}{2598960}\approx 1.32\%$. For reference, this is less
likely than drawing a three-of-a-kind (2.11\%) and more likely
than a straight (0.76\%).}
\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}.\]
}
\answer{One simple way to view both sides of this equation is as an
expression of the number of ways to select a $k$-person committee
which has a chairperson on that committee (or a team with a
captain, or any other group-and-distinguished-member idiom) out of
a pool of $n$ candidates. We might start by selecting a committee,
which we do by choosing $k$ people from the $n$, in any of
$\binom nk$ ways, and then follow up by appointing one of the
chosen members of the committee to be the chair: since there are
$k$ people on the committee, there are $k$ choices as to how to
sleect a chair. Thus, there are $k\binom nk$ ways to build such a
committee.
However, alternatively, we might build our committee by selecting
a chair first, from our candidate pool. Since there are $n$
candidates, there are $n$ possible ways to make this
decision. Having done so, we still have $k-1$ seats to fill on our
committee, and $n-1$ remaining candidates who could fill them. We
can thus select the non-chair members of our committee in
$\binom{n-1}{k-1}$ ways, for a total of $n\binom{n-1}{k-1}$ ways
to build the committee.
Since both $k\binom nk$ and $n\binom{n-1}{k-1}$ count the number
of ways to build this structure, we see that these two quantities
must be equal.}
\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}