\documentclass[12pt]{article}
\usepackage{latex-macros/course}

\begin{document}
\paper{qua2}{Quiz 2 Appendix}{Appendix}
\appendix

\section{Sums \& Asymptotics}

\subsection{Summation Formulae}
\begin{align*}
\sum_{i=1}^n i = &\ \frac{n(n+1)}{2},\\
\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} & \text{(Harmonic Numbers)},\\
H_n \sim & \ln n.
\end{align*}


\subsection{Factorial}
\begin{align*}
n! \eqdef &\ n \cdot (n-1) \cdots 2 \cdot 1 = \prod_{i=1}^n i,\\
n! \sim & \left(\frac{n}{e}\right)^n \sqrt{2 \pi n} & \text{(Stirling's Formula)}.
\end{align*}

\iffalse

[The Value of an Annuity]
\[
V = \sum_{i=1}^n \frac{m}{(1+p)^{i-1}} .
\]
\fi

\subsection{Asymptotic Notations}
\begin{align*}
f = o(g) \iff &\  \lim_{x \rightarrow \infty} f(x)/g(x) = 0,\\
f \sim g \iff &\  \lim_{x \rightarrow \infty} f(x)/g(x) = 1,\\
f = O(g) \iff &\ \limsup_{x \rightarrow \infty} \abs{f(x)}/g(x) < \infty,\\
f = \Theta(g)  \iff &\ f=O(g) \land g=O(f).
\end{align*}

Equivalently,
\[
f = O(g) \iff \exists c \geq 0\, \exists x_0\, \forall x \geq x_0\
\abs{f(x)} \leq c g(x).
\]

\section{Counting}
All sets $A,B,A_i \dots$ below are assumed to be finite.  The notation
\[
f:A \to B
\]
means that $f$ is a total function from $A$ to $B$.  The set of such total
functions is
\[
[A \to B] \eqdef \set{f \suchthat f:A \to B}.
\]

\subsection{Cardinality and Functions}

\begin{align*}
f:A \to B \text{ is an injection} \iff &\ [\forall a,a' \in A\ f(a)=f(a')
\implies a = a'],\\
f:A \to B \text{ is an injection} \implies &\ \card{A} \le \card{B}.\\
f:A \to B \text{ is a surjection} \iff &\ [\forall b \in B\,\exists a \in A\ f(a)=b],\\
f:A \to B \text{ is a surjection} \implies &\ \card{A} \ge \card{B}.\\
f:A \to B \text{ is a bijection} \iff &\ f \text{ is an injection and a surjection},\\
f:A \to B \text{ is a bijection} \implies &\ \card{A} = \card{B}.\\
\card{[A\to B]} = &\ \card{B}^{\card{A}},\\
\card{\set{ f \in [A\to A] \suchthat f \text{ is an bijection}}} = &\ \card{A}!,\\
\card{\set{ f \in [A\to B] \suchthat f \text{ is an injection}}} = &\
P(\card{B},\card{A}), & (\text{for} \card{A} \le \card{B}).
\end{align*}

\subsection{Pigeonhole Principle}
If there are more pigeons than pigeonholes, then
there must be at least two pigeons in one hole.

\subsubsection{Generalized Pigeonhole Principle}
If there are $m$ pigeons and $n$ pigeonholes, then at least one hole
contains $\ceil{m/n}$ pigeons.

\subsection{Sum Rule}
\[
\card{A_1 \cup A_2 \cup \dots} = \card{A_1} + \card{A_2} + \cdots,
\]
for disjoint sets $A_1, A_2, \dots$.

\subsection{Inclusion-Exclusion Principle}
\begin{align*}
\card{A \union B} = &\ \card{A} + \card{B} - \card{A \intersect B},\\
\card{A_1 \cup A_2 \cup \cdots \cup A_n}
  = &\ \sum_{1 \leq i \leq n} \card{A_i} - \sum_{1 \leq i < j \leq n}
 \card{A_i \cap A_j}
  + \sum_{1 \leq i < j < k \leq n} \card{A_i \cap A_j \cap A_k} + \cdots\\
    &\ + (-1)^{n+1} \card{A_1 \cap A_2 \cap \cdots \cap A_n} \\
  = &\ \sum_{k=1}^n (-1)^{k+1}
    \sum_{S \subseteq \set{1,\dots,n}, \card{S} = k} \card{\lgintersect_{i \in S} A_i}\\
  = &\ \sum_{\emptyset \neq S \subseteq \set{1,\dots,n}}
      (-1)^{\card{S}+1} \card{\lgintersect_{i \in S} A_i}.
\end{align*}

\subsection{Product Rule}
\[
\card{A_1 \times A_2 \times \dots \times A_n} = \card{A_1} \cdot
        \card{A_2} \cdots \card{A_n}.
\]


\section{Permutations and Combinations}

\subsection{\emph{r}-permutations of an \emph{n}-element set}
\[
P(n, r) \eqdef \frac{n!}{(n-r)!}
\]

\subsection{Division Rule}
If $f:A \to B$ maps precisely $k$ items of
$A$ to every item of $B$, then $\card{A} =k\card{B}$.

\subsection{Binomial Coefficients}
The number of combinations of $r$ distinct elements from an $n$-element
set is
\begin{align*}
\binom{n}{r} \eqdef &\ \frac{n!}{(n-r)! \ r!}\\
\binom{n}{r} = &\ \binom{n-1}{r} + \binom{n-1}{r-1} & \text{for }1 \leq r
\leq n-1 \text{  (Pascal)}\\
(x+y)^n = &\ \sum_{k=0}^n \binom{n}{k}x^ky^{n-k} & \text{(Binomial Theorem)}
\end{align*}

\subsection{Multinomial Coefficients}
Let $r_1, r_2, \dots, r_n$ be non-negative integers.  The number of
permutations with repetition of an $n$-element set where the $i$th element
of the set is repeated exactly $r_i$ times is:
\[
\binom{(r_1 + r_2 + \dots + r_n)}{r_1\quad r_2\quad \dots\quad r_n} \eqdef
\frac{(r_1 + r_2 + \dots + r_n)!}{r_1! \quad r_2! \quad \dots \quad r_n!}.
\]

\subsubsection{Multinomial Theorem}
\[
(x_1+x_2+\cdots+x_k)^n = \sum_{n_1+n_2+\cdots+n_k = n} \binom{n}{n_1\ n_2\
\dots n_k}x_1^{n_1}x_2^{n_2}\cdots x_k^{n_k}.
\]


\subsection{Stars \& Bars}
The number of $r$-combinations with repetition from an $n$-element set
is
\[
\binom{n + r - 1}{r}.
\]

\subsection{Hall's Theorem}

\begin{definition*}
A \emph{bipartite graph}, $G = (V_1,V_2,E)$, is a simple graph whose
vertices are the disjoint union of $V_1$ and $V_2$ and whose edges go
between $V_1$ and $V_2$, \viz
\[
E \subseteq \set{ \set{v_1,v_2} \suchthat v_1 \in V_1 \text{ and } v_2 \in
V_2}.
\]
A \emph{perfect matching} in $G$ is an injection $f:V_1 \to V_2$ such that
$\set{v, f(v)} \in E$ for all $v \in V_1$.

For any set, $A$, of vertices, define the neighbor set,
\[
N(A) \eqdef \set{v \suchthat \exists a \in A\ \set{a,v} \in E}.
\]
A set $A \subseteq V_1$ is called a \emph{bottleneck} if $\card{A} >
\card{N(A)}$.
\end{definition*}

\begin{theorem*}
[Hall] A bipartite graph has a perfect matching iff it has no bottlenecks.
\end{theorem*}

\section{Probability}

\subsection{Probability Spaces}

A \emph{sample space}, $\sspace$, is a nonempty set whose elements are
called \emph{outcomes}.  The \emph{events} are subsets of
$\sspace$.

A \emph{probability space} consists of a sample space, $\sspace$, and a
\emph{probability function}, $\pr{} : \sspace \to [0,1]$ satisfying
the~\ref{sumrule} and such that:
\[
\pr{\sspace} =1.
\]

\subsection{Events}

\begin{align}
\pr{\lgunion_{n \in \naturals} A_n} = &\ \sum_{n \in \naturals} \pr{A_n}
\mbox{ for pairwise disjoint } A_n  \tag{Sum Rule}\label{sumrule}\\
\pr{A-B}  = &\  \pr{A} - \pr{A \intersect B} \tag{Difference Rule}\\
%
% \item $\pr{A \intersect B}  \le  \pr{A}, \label{ab<a}$
%
\pr{\bar{B}}  = &\  1 - \pr{B} & \tag{Complement Rule}\\
\pr{A \union B}  = &\  \pr{A} + \pr{B} - \pr{A \intersect B}
        \tag{Inclusion-Exclusion}\\
\pr{A \union B}  \leq &\ \pr{A}+ \pr{B} \tag{Boole's inequality} \\
\pr{A} \le &\ \pr{A \union B} \tag{Monotonicity}
%
%\item $\pr{\lgintersect_n A_n} \ge 1 - \sum_n \pr{\overline{A_n}}$
%
\end{align}

\subsection{Conditional Probability}
\begin{align}
\prcond{A}{B} \eqdef &\  \frac{\pr{A \intersect B}}{\pr{B}} \notag\\
\pr{A \intersect B} = &\ \prcond{A}{B} \pr{B} \tag{Product Rule}%\\
%\prcond{A}{B} = &\ \frac{\prcond{B}{A}\pr{A}}{\pr{B}} \tag{Bayes Rule}
\end{align}

\subsubsection{Law of Total Probability}
Suppose the sample space is the disjoint union of $B_0, B_1, \dots$.  Then
for all events $A$,
\begin{align*}
\pr{A} = &\ \sum_{i \in \naturals} \pr{A \intersect B_i}\\
       = &\ \sum_{i \in \naturals} \prcond{A}{B_i}\pr{B_i}.
\end{align*}


\end{document}
