\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts,graphicx,amsthm,html}
\usepackage{epsdice}

\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{example}{Example}

\begin{document}

\title{General Mathematics and Computational Science I}
\author{Combinatorics and Probability}
\date{Marcel Oliver}
\maketitle

\begin{abstract}
Problems in probability theory often hinge on combinatorics.  This
note will introduce the notion of empirical probability as the
relative frequency of the occurrence of certain events---its
computation thus requires careful and often nontrivial counting.  We
will illustrate the concept with elementary examples.  This note is
not meant to give a complete and thorough overview of discrete
probability theory.
\end{abstract}

\begin{problem} \label{p1}
Players A and~B each toss a die.  Player B wins if he scores higher
than~A, otherwise he loses.  Is this a fair game?
\end{problem}

Let's count the the number of possible pairs of scores where player B
wins.  If A throws a \epsdice{6}, B~loses.  If A throws a \epsdice{5},
there is exactly one possibility for B to win; if B throws a
\epsdice{4}, there are $2$ possibilities for B to win, and so on.
Thus, the total number of ways for B to win is
\begin{equation}
  0 + 1 + 2 + 3 + 4 + 5 = 15 \,.
\end{equation}
We could count the number of possibilities for A to win the same way;
the following argument, however, is simpler.  There are $6 \cdot 6 =
36$ possible ways the two (ordered!)\ dice can fall.  Thus, the total
number of ways for A to win is
\begin{equation}
  36 -15 = 21 \,.
\end{equation}
We conclude that the game is $\tfrac{21}{15}=\tfrac75$ in A's favor;
the game is not fair.
\bigskip

In the language of probability theory, the above can be formalized as
follows.  We speak of a \emph{trial} each time an experiment, such as
the tossing of dice, is performed.  A possible result of a trial is
called an \emph{outcome}.  It is always assumed that trials are
\emph{independent}, i.e.\ that the outcome of one trial does not
depend on any past trials.  The set of all possible outcomes is called
the \emph{sample space}, usually denoted $S$.  Outcomes can be grouped
into \emph{events}, which formally are subsets $A \subseteq S$.
Finally, the \emph{probability} of an event $A$ occurring is the
relative frequency of that event in a large number of trials.
Assuming that every outcome is equally likely, it is given by
\begin{equation}
  P(A) = \frac{n_A}{n_S}
       = \frac{\text{number of outcomes in } A}%
              {\text{total number of possible outcomes}} \,.
\end{equation}

\begin{example}
In Problem~\ref{p1}, the sample space is the set of ordered tuples of
scores, 
\begin{equation}
  S = \{ \{ \epsdice{1} \, \epsdice{1} \},
         \{ \epsdice{1} \, \epsdice{2} \}, \dots,
         \{ \epsdice{1} \, \epsdice{6} \},
         \{ \epsdice{2} \, \epsdice{1} \}, \dots,
         \{ \epsdice{6} \, \epsdice{6} \} \} \,.
\end{equation}
We assign the first die in each tuple to player A, the second to
player~B.  Then the event ``player A wins'' is the set
\begin{equation}
  A = \{ \{ \epsdice{1} \, \epsdice{1} \},
         \{ \epsdice{2} \, \epsdice{1} \}, 
         \{ \epsdice{2} \, \epsdice{2} \},
         \{ \epsdice{3} \, \epsdice{1} \},
         \{ \epsdice{3} \, \epsdice{2} \},
         \{ \epsdice{3} \, \epsdice{3} \}, \dots,
         \{ \epsdice{6} \, \epsdice{6} \} \} \,,
\end{equation}
so that
\begin{equation}
  P(A) = \frac{n_A}{n_S} = \frac{21}{36} = \frac7{12} \,.
\end{equation}
\end{example}

In the game of Yahtzee (or Yacht), five dice are tossed.  Players
score by obtaining special patterns, such as the \emph{Yahtzee} (five
of the same kind, e.g.\ $\epsdice{5} \, \epsdice{5} \, \epsdice{5} \,
\epsdice{5} \, \epsdice{5}$), \emph{full house} (two and three of the
same kind but not a Yahtzee; e.g.\ $\epsdice{2} \, \epsdice{2} \,
\epsdice{4} \, \epsdice{4} \, \epsdice{4}$), \emph{small straight}
(four in a row, e.g.\ $\epsdice{2} \, \epsdice{2} \, \epsdice{3} \,
\epsdice{4} \, \epsdice{5}$) or \emph{large straight} (five in a row,
e.g.\ $\epsdice{1} \, \epsdice{2} \, \epsdice{3} \, \epsdice{4} \,
\epsdice{5}$).  The actual rules of the game allow players to twice
repeat tossing a select subset of dice.  In the following, however, we
disregard the option to repeat; for details on the mathematics of this
game, see \cite{Y}.

\begin{problem}
Find the probability of throwing a Yahtzee.
\end{problem}

The total number of possible outcomes is $6^5$, as each of the five
dice can independently score one of six values.  Note that in this
count the dice are ordered, whereas the scoring rules disregard order.
The number of possible Yahtzees is $6$, one for each of the scores
$\epsdice{1}, \dots, \epsdice{6}$.  We conclude that that
\begin{equation}
  P(\text{Yahtzee}) 
  = \frac{6}{6^5} = \frac{1}{6^4} = \frac1{1296} \,. 
\end{equation}

\begin{problem}
Find the probability of throwing a full house.
\end{problem}

The set of unordered full houses has $6$ (for the first number kind)
times $5$ (for the second number kind which must be different from the
first) members.  Since our sample space consists of \emph{ordered}
$5$-tuples, we must multiply this number by the number of ways a full
house can be realized with five ordered dice, i.e., by the number of
$5$-term binary sequences containing three $1$s and two $0$s.  We
obtain
\begin{equation}
  P(\text{full house}) 
  = \frac{5 \cdot 6}{6^5} \, \frac{5!}{2! \, 3!}
  = \frac{25}{648} \,.
\end{equation}

\begin{problem}
What is the probability that within a group of $n$ people at least two
have the same birthday?
\end{problem}

It is often easier to count the number of possibilities in which an
event does \emph{not} occur; this is the case here.  Ignoring leap
years, the total number of ways $n$ ordered people can have their
birthdays is $365^n$.  The number of ways these birthdays can fall
without coinciding is counted as follows.  The first person can be
born on any of the $365$ days of the year, the second on any of the
remaining $364$, the third on any of the remaining $363$, and so on.
We find that
\begin{equation}
  P(\text{birthdays all different})
  = \frac{365 \cdot 364 \cdot \dots \cdot (365-n+1)}{365^n}
  = \frac{365!}{365^n \, (365 - n)!} \,,
\end{equation}
and therefore
\begin{equation}
  P(\text{at least two birthdays coincide})
  = 1 -  P(\text{birthdays all different}) \,.
\end{equation}
For our class of $20$ students, this expression evaluates to
approximately $0.41$.

\begin{problem}
\emph{(Hat check problem.)} 12 men leave their hat with the hat check.
They lose their tickets so that the hats get returned at random.  What
is the probability that nobody obtains his own hat?
\end{problem}

Consider the problem for $n$ hats.  If $w_n$ denotes that number of
ways that $n$ hats can be returned to $n$ men without any getting his
own (such permutations are called \emph{derangements}), a careful
count (how?) leads to the two-term recurrence
\begin{equation}
  w_{n+1} = n \, w_n + n \, w_{n-1} \,,
\end{equation}
which implies that
\begin{equation}
  w_n = n \, w_{n-1} + (-1)^n \,.
  \label{e.oneterm}
\end{equation}
The one-term recurrence \eqref{e.oneterm} can be proved by induction
(what are the starting values $w_1$ and $w_2$?); there is also a very
elegant derivation using generating functions \cite{W} which, however,
goes far beyond what we discussed in this class.  Letting $p_n =
w_n/n!$ denote the associated probabilities, we conclude that
\begin{equation}
  p_n = \frac1{2!} - \frac1{3!} + \dots + \frac{(-1)^n}{n!} \,.
\end{equation}
A detailed discussion of this problem, and much more, can be found
in~\cite{G}.


\begin{thebibliography}{9}

\bibitem{G}
  C.M. Grinstead and J.L. Snell, \textit{Introduction to Probability},
  AMS, 1997. \\
  \htmladdnormallink{\small{http:/\!/www.dartmouth.edu/\~{}\!chance/teaching\_aids/books\_articles/probability\_book/book.html}}{http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/book.html}

\bibitem{Y}
  E.W. Weisstein, \textit{Yahtzee}. {From} MathWorld, Wolfram
  Research. \\
  \htmladdnormallink{\small{http:/\!/mathworld.wolfram.com/Yahtzee.html}}{http://mathworld.wolfram.com/Yahtzee.html}

\bibitem{W}
  H.S. Wilf, \emph{Generatingfunctionology},
  Academic Press, 1994. \\
  \htmladdnormallink{\small{http:/\!/www.math.upenn.edu/\~{}\!wilf/DownldGF.html}}{http://www.math.upenn.edu/~wilf/DownldGF.html}

\end{thebibliography}

\end{document}
