% \documentclass[serif]{beamer} % Serif for Computer Modern math font.
\documentclass[serif, handout]{beamer} % Handout to ignore pause statements.

\hypersetup{colorlinks,linkcolor=,urlcolor=red}


\usefonttheme{serif} % Looks like Computer Modern for non-math text -- nice!
\setbeamertemplate{navigation symbols}{} % Suppress navigation symbols
% \usetheme{Berlin} % Displays sections on top
\usetheme{Frankfurt}  % Displays section titles on top: Fairly thin but still swallows some material at bottom of crowded slides
%\usetheme{Berkeley}

\usepackage[english]{babel}
\usepackage{amsmath} % for binom
\usepackage{amsfonts} % for \mathbb{R} The set of reals
% \usepackage{graphicx} % To include pdf files!
% \definecolor{links}{HTML}{2A1B81}
% \definecolor{links}{red}
\setbeamertemplate{footline}[frame number] 

\mode<presentation>

\title{Counting Methods for Computing Probabilities\footnote{ This slide show is an open-source document. See last slide for copyright information.}}
\subtitle{STA 256: Fall 2018}
\date{} % To suppress date

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
\frametitle{Countable set}
%\framesubtitle{} 
A set is said to be \emph{countable} if it can be placed in one-to-one correspondence with the set of natural numbers $\mathbb{N} = \{1,2,\ldots \}$. \pause

\vspace{3mm}

If the sample space $\Omega$ is countable and $A \subseteq \Omega$, \pause

\begin{displaymath}
    P(A) = \sum_{\omega \in A} P(\omega\}
\end{displaymath} \pause

\vspace{3mm}

Example: Roll a fair die. What is the probability of an odd number? \pause

\begin{displaymath}
    P(\mbox{Odd}) = \pause P\{1,3,5\} = \pause P\{1\}+P\{3\}+P\{5\}
\end{displaymath}
\end{frame}


\begin{frame}
\frametitle{If all outcomes of an experiment are equally likely,} \pause
%\framesubtitle{} 
{\Large
\begin{displaymath}
    P(A) = \frac{\mbox{Number of ways for $A$ to happen}} 
                {\mbox{Total number of outcomes}}
\end{displaymath} \pause
} % End size

\vspace{8mm}
Need to count.
\end{frame}

\begin{frame}
\frametitle{Multiplication Principle}
\framesubtitle{Also called the Fundamental Principle of Counting} \pause

If there are $p$ experiments and the first has $n_1$ outcomes, the second  has $n_2$ outcomes, etc., \pause then there are \pause
\begin{displaymath}
    n_1 \times n_2 \times \cdots \times n_p
\end{displaymath}
outcomes in all.
\end{frame}

\begin{frame}
\frametitle{Sample Question}
%\framesubtitle{} 
If there are nine horses in a race, in how many ways can they finish first, second and third? \pause
\begin{displaymath}
    9 \times 8 \times 7 = 504
\end{displaymath}
\end{frame}

\begin{frame}
\frametitle{Permutations}
\framesubtitle{Ordered subsets} \pause
The number of \emph{permutations} (ordered subsets) of $n$ objects taken $r$ at a time is
\pause
\vspace{4mm}

{\Large
\begin{eqnarray*}
     _nP_r & = & n \times (n-1) \times \cdots \times (n-r+1) \\ \pause
           & = & \frac{n!}{(n-r)!} 
\end{eqnarray*}
} % End size
\end{frame}

\begin{frame}
\frametitle{Combinations}
\framesubtitle{Unordered subsets} \pause
The number of \emph{combinations} (unordered subsets) of $n$ objects taken $r$ at a time is
\pause
\vspace{4mm}

{\Large
\begin{displaymath}
     \binom{n}{r} = \frac{n!}{r! \, (n-r)!} 
\end{displaymath}
} % End size
\end{frame}

\begin{frame}
\frametitle{Proof of $\binom{n}{r} = \frac{n!}{r! \, (n-r)!}$}
\framesubtitle{Part of Proposition B in the text, p.12}  \pause
Choose an unordered subset of $r$ items from $n$. \pause Then place them in order. \pause By the Multiplication Principle, \pause

%{\LARGE
\begin{eqnarray*}
   &  & _nP_r = \binom{n}{r} \times r! \\ \pause
   & \Rightarrow &  \frac{n!}{(n-r)!} = \binom{n}{r} \times r! \\ \pause
   & \Rightarrow &  \binom{n}{r} = \frac{n!}{r! \, (n-r)!}
\end{eqnarray*} 
 $\blacksquare$
%} % End size
\end{frame}

\begin{frame}
\frametitle{Binomial Theorem}
%\framesubtitle{} 
{\LARGE
\begin{displaymath}
    (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^kb^{n-k}
\end{displaymath} 
} % End size
\end{frame}

\begin{frame}
\frametitle{Multinomial Coefficients}
\framesubtitle{Proposition C in the text} 
The number of ways that $n$ objects can be divided into $r$ subsets with $n_i$ objects in set $i$, $i = 1, \ldots,r$ is
\vspace{2mm} \pause

{\LARGE
\begin{displaymath}
    \binom{n}{n_1~\cdots~n_r}=\frac{n!}{n_1!~\cdots~n_r!}
\end{displaymath} 
} % End size
\end{frame}

\begin{frame}
\frametitle{Multinomial Theorem}
\framesubtitle{Nice to know} 
{\LARGE
\begin{displaymath}
    (x_1 + \cdots x_r)^n = \sum_{\mathbf{n}} \binom{n}{n_1~\cdots~n_r} x_1^{n_1} \cdots x_r^{n_r}
\end{displaymath} 
} % End size
where the sum is over all non-negative integers $n_1, \ldots, n_r$ such that $\sum_{j=1}^r n_j = n$.
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{frame}
\frametitle{Copyright Information}

This slide show was prepared by  \href{http://www.utstat.toronto.edu/~brunner}{Jerry Brunner},
Department of Statistical Sciences, University of Toronto. It is licensed under a 
\href{http://creativecommons.org/licenses/by-sa/3.0/deed.en_US}
     {Creative Commons Attribution - ShareAlike 3.0 Unported License}. Use any part of it as you like and share the result freely. The \LaTeX~source code is available from the course website:

\vspace{5mm}
\href{http://www.utstat.toronto.edu/~brunner/oldclass/256f18} {\small\texttt{http://www.utstat.toronto.edu/$^\sim$brunner/oldclass/256f18}}

\end{frame}


\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$ = \{\omega \in \Omega: \}$

\begin{frame}
\frametitle{} \pause
%\framesubtitle{} 
\begin{itemize}
    \item  \pause
    \item  \pause
    \item 
\end{itemize}
\end{frame}
