\documentclass[oneside,12pt]{article}   
\usepackage{latex-macros/course}
\setlength{\topmargin}{0.5in}
\setlength{\headsep}{1cm}
%\showsolutions             
%\hidesolutions             

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% exampreamble %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document} 
%\quiz{3}                      

\newpage
\appendix

\section{Appendix}

\subsection{Combinatorics}

\iffalse
\subsubsection{Summation}
\begin{eqnarray*}
\sum_{i=0}^{n} i^2 & = & \frac{n(n+1)(2n+1)}{6}\\
\sum_{i=0}^{n} x^i & = & \frac{1- x^{n+1}}{1 - x}\\
\sum_{i=0}^{\infty} x^i & = & \frac{1}{1-x}\\
\sum_{i=1}^{n} i x^i & = & \frac{x - (n+1)x^{n+1} + n x^{n+2}}{(1 - x)^2}\\
\sum_{i=1}^{\infty} i x^i & = & \frac{x}{(1-x)^2}\\
\sum_{i=1}^\infty{i^2x^i} & = & \frac{x(1+x)}{(1-x)^3}\\
e^x & = & 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots\\
1 + x & \leq & e^x\\
H_n & \eqdef & \sum_{i=1}^n \frac{1}{i} \quad\quad \text{(Harmonic Numbers)}\\
H_n &\sim& \ln n
\end{eqnarray*}
\fi

\subsubsection{Counting}
Given a set of $n$ elements:
\begin{itemize}
\item number of $r$-permutations without repetition:
\[P(n, r) \eqdef n (n-1) \ldots (n-r+1) = \frac{n!}{(n-r)!}\]

\item $r$-combinations without repetition:
\[C(n,r) \eqdef \binom{n}{r} = \frac{n!}{(n-r)! \ r!}\]

\item $r$-permutations with unlimited repetition ($r$ distinct balls, $n$ distinct
bins):
\[
n^r
\]

\item $r$-combinations with repetition ($r$ identical balls, $n$ distinct
bins):
\[\binom{n+r-1}{r}\]

\item permutations with limited repetition:
\[\binom{n}{r_1, r_2, \ldots, r_k} \eqdef\frac{n!}{r_1!\ r_2! \ldots r_k!}\]
where $r_1 + r_2 + \cdots + r_k = n$.
\end{itemize}

\subsubsection{Binomial Identity}
\[\binom{n}{m} = \binom{n}{n-m}\]

\subsubsection{Multinomial Theorem}
\[(x_1 + x_2 + \ldots + x_k)^n =
	\sum_{r_1 + r_2 + \ldots + r_k = n} \binom{n}{r_1, r_2, \ldots, r_k}
	x^{r_1} x^{r_2} \ldots x^{r_k}\]

\subsubsection{Inclusion-Exclusion}
\[|A_1 \cup \ldots \cup A_n| = \sum_{k=1}^n
(-1)^{k+1} \left( \sum_{S \subseteq \{1,\ldots,n\}, |S| = k} | \bigcap_{i
\in S} A_i |\right)\]

\iffalse
\subsubsection{Stirling's Approximation}
\[
n! = \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n e^{a_n}
\]
where
\[
1/(12n+1) \leq a_n \leq 1/(12n).
\]
\fi

\subsection{Events}

\begin{align}
\pr{\lgunion_{n \in \naturals} A_n} & = \sum_{n \in \naturals} \pr{A_n}
\quad \mbox{for pairwise disjoint $A_n$} \tag{Sum Rule}\\
\pr{A-B}  & =  \pr{A} - \pr{A \intersect B} \tag{Difference Rule} \\
\pr{\bar{B}}  & =  1 - \pr{B} \label{1-b} \tag{Complement Rule}\\
\pr{A \union B}  & = \pr{A} + \pr{B} - \pr{A \intersect B} \tag{Inclusion-Exclusion}\\
\pr{A \union B} & \le \pr{A}+ \pr{B} \tag{Boole's inequality} \\
\pr{A} & \le \pr{B}, \quad\text{ for } A \subseteq B \tag{Monotonicity}\\
\pr{A \intersect B} & \le  \pr{A}, \notag\\
\pr{A} & \le \pr{A \union B} \notag\\
\prcond{A}{B} {\pr{B}}  & =  \pr{A \intersect B}\tag{Product Rule}\\
\prcond{A}{B} & = \frac{\prcond{B}{A}\pr{A}}{\pr{B}} \tag{Bayes Rule}
\end{align}

\begin{lemma*}[Law of Total Probability]
Let $B_0, B_1, \ldots$ be disjoint events whose union is the
entire sample space.  Then for all events $A$,
\begin{align}
\pr{A} &= \sum_{i \in \naturals} \pr{A \cap B_i}, \notag\\
\pr{A} &= \sum_{i \in \naturals} \pr{A | B_i}\pr{B_i}. \tag{conditional form}
\end{align}
\end{lemma*}

\subsection{Independence}
\begin{definition*}
Events $A$ and $B$ are \emph{independent} iff
\[
\pr{A \intersect B} = \pr{A}\pr{B}.
\]

Events $A_0,A_1,A_2,\dots$ are \emph{mutually independent} iff for all
subsets $J \subseteq \naturals$,
\[
\pr{\lgintersect_{i\in J} A_i} = \prod_{i \in J} \pr{A_i}.
\]

Events $A_0,A_1,A_2,\dots$ are \emph{$k$-wise independent} iff $\set{A_i
\suchthat i\in J}$ are mutually independent for all subsets $J \subset
\naturals$ with $\card{J} = k$.
\end{definition*}

\end{document}



