\documentclass[12pt]{amsart}
\usepackage{amsmath} \usepackage{amsthm} \usepackage{amstext}
\usepackage{amsfonts} \usepackage{graphicx} \usepackage{latexsym}
\usepackage{epsfig}
% \input epsf
\def\p{\partial} \def\O{\Omega} \def\c{\cal} \def\a{\alpha}
\def\r{\rho} \def\e{\epsilon} \def\g{\gamma} \def\d{\delta}
\def\D{\Delta} \def\t{\theta} \def\T{\Theta} \def\N{\nabla}
\def\L{\Lambda} \def\l{\lambda} \def\m{\mu} \def\f{\frac}
\def\dis{\displaystyle} \def\s{\sigma}
\newcommand{\lx}{\left} \newcommand{\rx}{\right}
\setlength{\parindent}{0in} \setlength{\parskip}{\baselineskip}
\setlength{\textheight}{9.0in} \setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0.0in} \setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}

\begin{document} %(
\baselineskip 24pt

\title{Exam 2 Cheat Sheet}
% YOUR NAME GOES HERE under Author
\maketitle

{\bf Let me know before Wednesday night if there's anything else you'd like
added to this.  -Marc}

\begin{enumerate} %( 
\item Sequences and Summations
\begin{enumerate} %( 
\item Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, $\cdots$): 

Recursive Definition
\begin{enumerate} %( 
\item {\bf Base Cases:} $f_1 = f_2 = 1$
\item {\bf Recursive definition:} $f_{n} = f_{n-1} + f_{n-2}$
\end{enumerate} %)

Closed Form Definition
\begin{displaymath} %(
f_n = \f{\lx(1+\sqrt{5}\rx)^n - \lx(1-\sqrt{5}\rx)^n}{2^n \sqrt{5}}
\end{displaymath} %)

\item Some summations: 
\begin{enumerate} %( 
\item $1 + 2 + 3 + 4 + \cdots + n = \f{n^2 + n}{2}$ 
\item $1^2 + 2^2 + 3^2 + 4^2 + \cdots + n^2 = \sum_{i=1}^n i^2 = \f{n
\lx(n+1\rx) \lx(2n+1\rx)}{6}$
\item $9 + 9^2 + 9^3 + \cdots + 9^n = \f{9^{n+1} - 9}{8}$
\end{enumerate} %)
\end{enumerate} %)

\item Recursion
\begin{enumerate} %( 
\item Kevin Bacon Actors Guild recursive definition (where $KB$ is
Kevin Bacon and $A\lx(x, y\rx)$ means that $x$ and $y$ acted in a
movie together): \\ $KBAG = \lx\{x| x = KB \vee \exists y \lx(y \in KBAG
\wedge A\lx(x, y\rx)\rx)\rx\}$ 
\item The set $MA$ of all Marc's ancestors (excluding Marc) is given by the
following definition (where $M$ is Marc and $p\lx(x, y\rx)$ means $x$
is $y$'s parent): $MA = \lx\{x| p\lx(x, M\rx) \vee \exists y \lx(y \in MA
\wedge p\lx(x, y\rx)\rx)\rx\}$
\item $N! = 1 \cdot 2 \cdot 3 \cdots N$
\begin{enumerate} %( 
\item {\bf Base Case:} $0! = 1$
\item {\bf Recursive definition:} $n! = n \cdot \lx(n-1\rx)!$
\end{enumerate} %)

\end{enumerate} %)
\item Counting, Permutations, and Combinations
\begin{enumerate} %( 
\item   Number of TLA's (Three Letter Acronyms) $= 26^3$
\item   Number of 10 digit phone numbers, excluding those that start
with 0 or 1 or have 555 as their middle 3 numbers: $= 10^{10} -
\lx(2\cdot 10^9 + 10^7 - 2\cdot 10^6\rx)$
\item   Pigeonhole principle: If there are 27 people in the class,
and 4 Starburst flavors, then at least one flavor must be the favorite
of at least $\lx\lceil\f{27}{4}\rx\rceil = 7$ people.
\item   n Pick a = $\f{n!}{\lx(n-a\rx)!}$ 
\item   n Choose a = ${n \choose a} = \f{n!}{\lx(n-a\rx)!a!}$ 
\item   Number of ways to put 9 baseball players on a field (with
assigned positions) out of a team of 20 = 20 Pick 9
\item   Number of ways to put 6 men and 4 women on a dodgeball team
(from 10 women and 12 men) where the positions don't matter $ = {10
\choose 4} {12 \choose 6}$
\item   Number of ways to match exactly 3 of 6 lotto numbers (out of 49) $= {6
\choose 3} {43 \choose 3}$
\item Number of full houses in 5 card poker $= 13 {4 \choose 3} 12 {4 \choose 2}$
\item Number of ways to get a pair of kings in 5 card poker $= {4 \choose 2} {48 \choose 3}$
\item   Binomial expansion: $\lx(A+B\rx)^n = \sum_{i=0}^n {n \choose i} A^iB^{n-i}$
\item   Pascal's identity: ${n+1 \choose k} = {n \choose k-1} + {n \choose k}$
\item   Pascal's triangle: 
\begin{verbatim}
           1
         1   1
       1   2   1
     1   3   3   1
   1   4   6   4   1
1    5  10  10   5   1
   (etc.)
\end{verbatim}
\item   Ways to arrange letters in DELETE $= \f{6!}{3!}$, SERENDIPITY
$= \f{11!}{2! 2!}$
\item   Ways to make a pack of Starburst (4 flavors, 12 Starbursts in
a pack) $= {12 + \lx(4-1\rx) \choose 4-1}$
\end{enumerate} %)
\item Probability
\begin{enumerate} %( 
\item   Prob of 2 of 27 people having same birthday = 1 - Prob of all
B-days being different $= 1 - \f{366}{366} \cdot \f{365}{366} \cdot \f{364}{366} \cdots
\f{366 - 26}{366}$ = $1 - \f{366!}{\lx(366-27\rx)! \cdot 366^{27}}
\approx 0.6258$
\item   Discrete Probability principles (where $P\lx(E\rx)$ means the
probability of event $E$).:
\begin{enumerate} %( 
\item     $0 \leq P\lx(E\rx) \leq 1$
\item     If $O$ is the set of all possible outcomes $1 = \sum_{o \in O} P\lx(o\rx)$
\item     $1 - P(E) = P(\sim E)$
\item     $P (A \vee B) = P (A) + P(B) - P (A \wedge B)$
\item     Events $A$ and $B$ are {\em independent} iff $P \lx(A \wedge B\rx) = P\lx(A\rx) P \lx(B\rx)$
\end{enumerate} %)
\item   Conditional Probability:
\begin{enumerate} %( 
\item     Bayes's law: $P(B|A) = \f{P(A|B)P(B)}{P(A)}$
c\item     $P(A \wedge B) = P(A|B)P(B)$
\item     $P(A) = P(A \wedge B) + P(A \wedge \sim B) = P(A|B)P(B) + P(A|\sim B)P(\sim B)$
\end{enumerate} %)
\item   Bernoulli Distribution: $P(rolling~ 1)$ exactly 3 times out of
10 = $P(rolling~ 1)^3 (1 - P(rolling~ 1))^7 {10 \choose 3}$
\item Some statistics
\begin{enumerate} %( 
\item   Expected value = $E\lx[X\rx] = \sum_{x \in X} P(x) x$
\item   Variance = $V\lx[X\rx] = E\lx[\lx(x - E\lx[X\rx]\rx)^2\rx] =
\sum_{x \in X} P(x) \lx(x - E\lx[X\rx]\rx)^2$
\item   Standard Deviation = $\sigma\lx[X\rx] = \sqrt{V\lx[X\rx]}$
\end{enumerate} %)
\end{enumerate} %)
\item Recurrence Relations:

If the $n$th term of a recurrence relation is defined as $a_n = c_1
a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$ (and the {\em base
cases} are defined to be $a_1 = m_1$, $a_2 = m_2$, $\cdots$, $a_k =
m_k$ (where $m_i$ is a constant)), then there will be a solution of
the form $a_n = r^n$.  The {\em characteristic equation}
for $a$ is then
\begin{displaymath} %(
r^k - c_1 r^{k-1} - c_2 r^{k-2} - c_3 r^{k-3} - ... - c_k = 0
\end{displaymath} %)

If this equation has distinct roots $r_1, \cdots r_k$, then $a_n =
\alpha_1 r_1^n + \cdots + \alpha_k r_k^n$, where $\alpha_i$ is a
constant.   We can solve for the $\alpha$s by solving the system of
linear equations given for the first $k$ $a_i$s.

\item Relations
\begin{enumerate} %( 
\item 
Relation $<$ on Natural numbers as a matrix
\begin{verbatim}
  1 2 3 4 5 ...
1 0 1 1 1 1
2 0 0 1 1 1 etc...
3 0 0 0 1 1 ...
4 0 0 0 0 1
5 0 0 0 0 0 ...
...        etc...
\end{verbatim}
\item Number of possible relations on set $S$ = $2^{\lx|S\rx|^2}$
\item {\bf reflexive} $\forall a \in S, \lx(a, a\rx) \in R$: Examples: $\leftrightarrow$, $\leq$, $=$.  Non-examples: ``Parent'', $\wedge$
\item {\bf symmetric} $\forall a, b \in S, \lx(a, b\rx) \in R \leftrightarrow \lx(b, a\rx) \in R$: Examples: ``Acted with'', ``married to'', XOR.  Non-examples: ``loves'', $\implies$
\item {\bf antisymmetric} $\forall a, b \in S, \lx(a, b\rx) \in R \wedge \lx(b, a\rx) \in R \implies a = b$: Example: $\implies$, $\leq$.  Non-example: XOR.
\item {\bf asymmetric} $\forall a, b \in S, \lx(a, b\rx) \in R \leftrightarrow \wedge \lx(b, a\rx) \in R$: Examples: ``Parent'', $<$
\item {\bf transitive} $\forall a, b, c \in S, \lx(a, b\rx) \in R \wedge \lx(b, c\rx) \in R \implies \lx(a, c\rx) \in R$: Examples: ``Ancestor'', $<$, ``Taller than''.  
Non-examples: ``beats at chess'', ``Acted with''.
\item Since Relations are sets, we can combine them with set operators ($\cup$, $-$, $\cap$).  E.g. if $R1$ is the relation between a set of students in 203 and classes offered at UMBC that contains
$\lx(s, c\rx)$ iff student $s$ has taken class $c$, and $\lx(s, c\rx) \in R2$ iff $c$ is a required course for $s$'s major, then:
\begin{enumerate} %( 
\item $\lx(s, c\rx) \in R1 \cup R2$ means that $s$ is guaranteed to have taken $c$ by the time he/she graduates.
\item $\lx(s, c\rx) \in R2 - R1$ means that $s$ needs to take $c$ yet to graduate.
\item $\lx(s, c\rx) \in R1 \cap R2$ means that $s$ has taken $c$ as a required class (as opposed to an elective).
\end{enumerate} %)
\item Composition of Relations: $\lx(a, b\rx) \in R1 \wedge (b,c) \in R2  \implies (a,c) \in R1 \circ R2$: E.g Grandparent = Parent $\circ$ Parent 
\end{enumerate} %)
\item Graphs
\begin{enumerate} %( 
\item UMBC students and UMBC classes (and the edges representing that
a student is taking a class) is a {\bf bipartite graph} because no
class is directly connected to any other class (and no student is
directly connected to another student).
\item If there's a {\bf path} from every UMBC student to every class
and every other student, then the UMBC student/class graph is not {\bf
disjoint}.
\end{enumerate} %)
\end{enumerate} %)
\end{document} %)