\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}
