Math 239 Formula Theorems

It seems Gitbook and Typora don't render markdowns exactly the same, so this looks really messed up.

[Nice PDF here](https://github.com/lauradang/wiki-notes/blob/master/Math/Math%20239%20FormulaTheorems.pdf](https://github.com/lauradang/wiki-notes/blob/master/Math/Math 239 FormulaTheorems.pdf)).

Enumeration

Sets	Cartesian Product
Unordered: $\{1, 1, 3\} = \{1, 3, 1\}$ Ordered: $\{1, 1, 3\} \ne \{1, 3, 1\}$ $$	A \cup B
Binomial Coefficient Sets	Binomial Theorem
$$S_{k,n}={\Omega \subseteq {1, 2, ..., n}:	\Omega
Bijection	Bijection Theorems
$S\rightarrow T$ 1. $f(x_1)=f(x_2) \Rightarrow x_1=x_2$ - 1-1/injective 2. $\forall y\in T, \exists x \in S, f(x)=y$ - onto/surjective	Suppose $S, T$ are finite sets and $f:S \rightarrow T$ (i) If $f$ is 1-1 $$\Rightarrow
Generating Series	Generating Series Theorems
$S$ is a set with weight function $w:S\rightarrow \{0, 1, 2, ...\}$ $\Phi_s(x)=\sum\limits_{\sigma \in S}x^{w(s)}$	$\Phi_s(x)=\sum\limits_{k\ge 0}a_kx^k$ $$
Formal Power Series	FPS Operations
$C(x)=c_0+c_1x+c_2x^2+...+\sum\limits_{k \ge 0}^\infty c_kx^k$ where $(c_0, c_1, ...)$ are rational numbers. $[x^n]C(x) = c_n$ - Coefficient of $x^n$	$A(x) = \sum\limits_{k=0}^\infty a_kx^k$, $B(x) = \sum\limits_{k=0}^\infty b_kx^k$ Addition: $A(x)+B(x)=\sum\limits_{k=0}^\infty (a_k+b_k)x^k$ Equality: $A(x)=B(x) \iff a_k=b_k$ Multiplication: $A(x)B(x) = \sum\limits_{n=0}^\infty (\sum\limits_{j=0}^n a_jb_{n-j})x^n$
Inverse/Composition of FPS (not all FPS have inverses)	Inverse/Recurrence Theorems
$A(x), B(x)$ are fps satisfying $A(x)B(x)=1$ $ightarrow \frac{1}{(1-x)^k}=\sum\limits_{k=0}^\infty x^k$ $ightarrow [x^0]A(x)B(x)=1$ - Inverse Let $A(x), B(x)$ be fps. If $b_0 = 0 \Rightarrow A(B(x)) = \sum\limits_{j=0}^\infty a_j(B(x))^j$ - Composition	$\frac{1}{(1-x)^k}=\sum\limits_{n=0}^\infty {n+k-1 \choose k-1}x^n$ - Negative Binomial Theorem Let $A(x) = \sum\limits_{j=0}^\infty a_jx^j$. $A(x)$ has inverse $\iff$ $[x^0]A(x)=a_0\ne 0$ Let $A(x), C(x)$ be fps. If $[x^0]A(x) \ne 0 \Rightarrow$ there exists fps $B(x)$ where $A(x)B(x)=C(x)$ Let $A(x), C(x)$ be fps with $a_0 \ne 0$. Let $B(x) = \frac{C(x)}{A(x)}$. $ightarrow [x^n]B(X) = b_n=\frac{1}{a_0}(c_n-\sum\limits_{j=0}^{n-1} a_{n-j}b_j)$ Let $A(x), B(x)$ be fps s.t. $[x^0]A(x) \ne 0$ and $[x^0]B(x)=0$ $ightarrow (A(B(x)))^{-1}=A^{-1}(B(x))$
Sum and Product Lemmas for Generating Series	Geometric Series
Let $S=A \cup B, A \cap B = \varnothing, w:S\rightarrow \{0, 1,...\}$ $\Phi_S(x)=\Phi_A(x)+\Phi_B(x)$ - Sum lemma Let $A, B$ be sets with weight functions: $\alpha: A\rightarrow \{0, 1, ...\}$ $\beta: B \rightarrow \{0, 1, ...\}$ $w: A \times B \rightarrow \{0, 1, ...\}$: $w((a,b))=\alpha(a)+\beta(b)$ $ightarrow \Phi_{A \times B}(x) = \Phi_A(x) \Phi_B(x)$ - Product Lemma	Geometric Series: $\sum\limits_{j=0}^\infty x^j= \frac{1}{1-x}$ - Composition of Geometric Series: $[x^0]A(x)=0 \Rightarrow \sum\limits_{j=0}^\infty (A(x))^j=\frac{1}{1-A(x)}$
Integer Composition	Ambiguous/Unambiguous Binary Strings
A composition of n is a tuple of positive integers $(a_1, a_2, ..., a_k)$ s.t. $a_1+a_2+...+a_k=n$ $k$ is the number of parts of the composition.	Let $A, B$ be sets of binary strings. $AB$ is ambiguous if: There exist $a_1, a_2 \in A$ and $b_1, b_2 \in B$ s.t. $a_1b_1=a_2b_2$ $A \cup B$ is unambiguous if $A \cap B \ne \varnothing$ Expression with several concatenation/union operations is unambiguous if 1 of the concatenations or unions is.
Unambiguous/Ambiguous Binary Strings Expressions	Unambiguous Binary String Operations
$A^k$ is ambiguous if there are distinct k-tuples and the concatenations are equal. $A^*$ is unambiguous $\iff$ 1. $A^k \cap A^j = \varnothing$ 2. $A^k$ is unambiguous for each $k \ge 0$ Unambiguous Expressions for set of all binary strings: 1. $S=\{0, 1\}^*$ 2. $S=\{0\}^*(\{1\}\{0\}^*)^*$ 3. $S=\{0\}^*(\{1\}\{1\}^*\{0\}\{0\}^*)^*\{1\}^*$	Theorem 2.6.1: $A, B$ are sets of unambiguous binary strings. (i) $\Phi_{AB}(x) = \Phi_A(x)\Phi_B(x)$ (ii) $\Phi_{A \cup B}(x) = \Phi_A(x)+\Phi_B(x)$ (iii) $\Phi_{A*}(x) = \frac{1}{1-\Phi_A(x)}$
Partial Fractions Theorems	Homogeneous Linear Recurrences
$f, g$ are polynomials where $deg(f) < deg(g)$ and $g(x)=(1-r_1x)^{e_1}...(1-r_kx)^{e_k}$ where r_1, ..., r_k \in \C, e_1, .., e_k \in \Z^+ Partial Fractions Theorem: $ightarrow \frac{f(x)}{g(x)}=\frac{c_{1,1}}{(1-r_1x)}+...$ $+\frac{c_{1,e_1}}{(1-r_1x)^{e_1}}+\frac{c_{2,1}}{(1-r_2x)}+...$ $+\frac{c_{2,e_2}}{(1-r_x)^{e_2}}+...+\frac{c_{k,1}}{(1-r_kx)}+...+\frac{c_{k,e_k}}{(1-r_kx)^{e_k}}$ Theorem 3.1.4: There exist polynomials $P_1, ..., P_k$ s.t. $deg(P_i)<e_i$ $ightarrow [x^n]\frac{f(x)}{g(x)}=P_1(n)r_1^n+P_2(n)r_2^n+...+P_k(n)r_k^n$	Theorem 3.2.1: Let $\{c_n\}_{n \ge 0}$ satisfy the linear recurrence: $c_n + q_1c_{n-1}+...+q_kc_{n-k}=0$ Define $g(x)=1+q_1x+...+q_kx^k$, $C(x)=\sum\limits_{n=0}^\infty c_nx^n$ $ightarrow$ There exists polynomial $f(x)$ s.t. $deg(f) < k$ $C(x) = \frac{f(x)}{g(x)}$
Characteristic Polynomial
$h(x)=q_k+q_{k-1}x+...+q_1x^{k-1}+x^k$ for recurrence: $c_n+q_1c_{n-1}+...+q_kc_{n-k}=0$ Theorem: Roots: r_1, r_2, ..., r_L \in \C Multiplicities: $e_1, e_2, ..., e_L \ge 1$ $ightarrow$ Then there exists polynomials $P_1, ..., P_L$ s.t. $deg(f_j) = e_j-1$ and $c_n = P_1(n)r_1^n + ... + P_L(n)r_L^n$

Graph Theory

Handshaking Lemma	Corollary 4.3.2 (# of odd degrees)
$$\sum\limits_{v \in v(G)} deg(v)=2	E(G)
Corollary 4.3.3 (Average Vertex Degree)	Isomorphic
Avg vertex degree = $$\frac{2	E(G)
Isomorphic Equivalence Relation	Complete Graphs ($K_n$)
1. A graph is isomorphic to itself (reflexive) 2. If $G_1 \cong G_2 \Rightarrow G_2 \cong G_1$ (symmetric) 3. If $G_1 \cong G_2$and $G_2 \cong G_3 \Rightarrow G_1 \cong G_3$ (transitive)	Every pair of vertices is an edge. # of edges = ${n \choose 2}$
Regular Graphs (k-regular)	Bipartite Graphs
Graph where every vertex has degree $k$. # of edges = $\frac{nk}{2}$	Graph where there exists partition of vertices $(A,B)$ s.t. each edge of G joins 1 vertex of $B$ with a vertex in $A$.
Complete Bipartite Graphs ($K_{m,n}$)	N-cube
Graph with partition (A,B) where all possible edges joining vertex in A with vertex in B. $$	A
Theorem 4.5.2 (Walk, Path)	Corollary 4.6.3 (Path Transitive)
If there is a $u,v$-walk in $G \Rightarrow$ there is a $u,v$-path in $G$.	If there exists $u,v$-path and $v,w$-path $ightarrow$ there exists $u,w$-path.
Theorem 4.6.4 (Cycle, degree)	Girth
If every vertex in $G$ has $deg \ge 2 \Rightarrow G$ has a cycle.	Length of graph's shortest cycle. If $G$ has no cycles $ightarrow$ girth = $\infty$ - Measure of graph density - High girth = lower average degree (usually)
Spanning Cycle/Hamiltonian Cycle	Connectedness
Cycle that uses every vertex in the graph	Connected if there is a $u,v$-path for any pair of vertices $u,v$.
Theorem 4.8.2 (Connectedness)	Cuts
Let $u \in V(G)$ If $u,v$-path exists for each $v \in V(G) \Rightarrow G$ is connected.	Let $x \subseteq V(G)$. Cut induced by x in $G$ is the set of all edges in $G$ with exactly 1 end in x.
Theorem 4.8.5 (Disconnectedness)	Eulerian Circuit/Tour
$G$ is disconnected $\iff$ There exists a nonempty proper subset $x$ of $V(G)$ s.t. the cut induced by $x$ is $\empty$.	Closed walk that uses every edge of $G$ exactly once. - Connected unless it has isolated vertices
Theorem 4.9.2 (Eulerian Circuit Vertices)	Bridge
$G$ is connected. $G$ has an Eulerian circuit $\iff$ every vertex in $G$ has even degree.	An edge $e$ (or cut-edge) in $G$ if $G-e$ has more components than $G$.
Lemma 4.10.2 (Bridge Component)	Theorem 4.10.3 (Bridge, Cycle)
If $e=uv$ is a bridge in $G$ and $H$ is the component containing $e$ $ightarrow$ $H-e$ has exactly 2 components (hence $G-e$ has 1 more component than $G$) Moreover, $u$ and $v$ are in different components of $H-e$. (hence in $G-e$)	An edge $e$ is a bridge of $G$ $\iff$ $e$ is not in any cyce of $G$.
Tree	Forest
Connected graph with no cycles # of edges = $n-1$ by Theorem 5.1.5 - Bipartite by Lemma 5.1.4	Graph with no cycles. # of edges = $n-k$ , with $n$ vertices and $k$ components
Lemma 5.1.4 (Tree, Bridge)	Leaf
Every edge in a tree/forest is a bridge.	Tree with vertex degree 1.
Theorem 5.1.8 (Tree Leaves)	Lemma 5.1.3 (Unique Path Tree)
Every tree with $\ge 2$ vertices has $\ge 2$ leaves.	There is a unique path between any 2 vertices in a tree.
Theorem 5.2.1 (Connectedness, Spanning tree)	Corollary 5.2.2 (Connected, tree)
$G$ is connected $\iff G$ has a spanning tree.	If $G$ is connected with $n$ vertices and $n-1$ edges $ightarrow G$ is a tree.
Corollary (Tree-Graph equivalence)	Corollary 5.2.3 (Spanning Tree, Cycle)
If any of 2 the following 3 conditions hold $ightarrow G$ is a tree: 1. $G$ is connected 2. $G$ has no cycles. 3. $G$ has $n-1$ edges.	If $T$ is a spanning tree of $G$ and $e$ is an edge in $G$ that is not in $T$ $ightarrow$ $T+e$ has exactly 1 cycle. Moreover, if $e'$ is an edge in $C$ $ightarrow$ $T+e-e'$ is a spanning tree of $G$.
Corollary 5.2.4 (Spanning Tree, Component)	Bipartite Characterization Theorem
If $T$ is a spanning tree of $G$ and $e$ is an edge in $T$ $ightarrow T-e$ has 2 components ($e$ is a bridge in T). If $e'$ is an edge in the cut induced by the vertices of 1 component $ightarrow$ $T-e+e'$ is a spanning tree of $G$.	$G$ is bipartite $\iff G$ has no odd cycles.
Minimum Spanning Tree (MST) Problem	Prim's Algorithm Theorem
Given connected graph $G$ and weight function on edges $w: E(G) \rightarrow$, find minimum spanning tree in $G$ whose total edge weight in minimized.	Prim's algorithm produces a MST.
Complement	Planar
If 2 vertices are adjacent in $G \iff$The same 2 vertices are not adjacent in $\bar{G}$.	A graph is planar $\iff$ Each component is planar
Face	Boundary
A face of a planar embedding is a connected region on the plane. 2 faces are adjacent $\iff$ The faces share $\ge$ 1 edge in their boundaries.	Subgraph of all vertices and edges that touch a face.
Boundary Walk	Handshaking Lemma for Faces
Closed walk once around the perimeter of the face boundary. Degree of face = length of boundary walk	Let $G$ be a planar graph with planar embedding where $F$ is the set of all faces. $$\sum\limits_{f \in F} deg(f)=2
Lemma L7-1	Jordan Curve Theorem
In a planar embedding, an edge $e$ is a bridge $\iff$ The 2 sides of $e$ are in the same face	Every planar embedding of a cycle separates the plane into 2 parts: 1 on the inside, 1 on the outside
Euler's Formula	Platonic
Let $G$ be a connected planar graph. Let $n$ = # of vertices in $G$. Let $m$ = # of edges in $G$. Let $s$ = # of faces in a planar embedding of $G$. $ightarrow n-m+s=2$ Note: If $G$ has $C$ components $ightarrow$ $n-m+s=1+C$ Result: All planar embeddings of a graph have the same number of faces.	A connected planar graph is platonic if it has a planar embedding where every vertex has same degree ($\ge 3$) AND every face has same degree ($\ge 3$)
Lemma 7.5.2	Lemma 7.5.1
Let $G$ be a planar graph with $n$ vertices and $m$ edges. If there is a planar embedding of $G$ where every face has degree $\ge 3$ $ightarrow m \le \frac{d(n-2)}{d-2}$	If $G$ contains a cycle $ightarrow$ In any planar embedding of $G$, every face boundary contains a cycle.
Theorem 7.5.3	Corollary 7.5.4
Let $G$ be a planar graph with $n \ge 3$ vertices $ightarrow m \le 3n-6$	$K_5$ is not planar.
Theorem 7.5.6	Corollary 7.5.7
Let $G$ be a bipartite planar graph with $\ge$ 3 vertices and $m$ edges. $ightarrow m \le 2n-4$	$K_{3,3}$ is not planar.
Edge Subdivision	Kuratowski's Theorem
Edge subdivision of $G$ is obtained by replacing each edge of $G$ with a new path of length $\ge 1$	A graph is planar $\iff$ Graph does not have an edge subdivision of $K_5$ or $K_{3,3}$ as a subgraph.
K-colouring	Theorem 7.7.2
If $C$ is a set of size $k$ ("colours") $ightarrow f:V(G) \rightarrow C$ s.t. $f(u) \ne f(v) \space \forall uv \in E(G)$ Note: A k-colouring does not need to use all $k$ colours.	$G$ is 2-colourable $\iff$ $G$ is bipartite
Theorem 7.7.3	6-Colour Theorem
$K_n$ (complete graph) is n-colourable, and not k-colourable for any $k<n$	Every planar graph is 6-colourable.
Corollary 7.5.4	5-Colour Theorem
Every planar graph has a vertex of degree $\le 5$	Every planar graph is 5-colourable.
Contraction Result L7-7	4-Colour Theorem
If $G$ is planar $ightarrow$ $G/e$ is planar.	Every planar graph is 4-colourable.
Dual Graph Results L7-8($G^*$)	Lemma 8.2.1
Key: Colouring faces is equivalent to colouring vertices of dual graph. The dual graph is planar. 1. If $G$ is connected $ightarrow (G^*)^*=G$ 2. A vertex in $G$ corresponds to a face in $G^*$ of the same degree. 3. A face in $G$ corresponds to a vertex in $G^*$ of the same degree. 4. The dual of a platonic graph is platonic. 5. If we draw a closed curve on the plane $ightarrow$ the faces are 2-colourable.	If $M$ is any matching of $G$ and $C$ is any cover in $G$ $$\Rightarrow
Lemma 8.2.2	Konig's Theorem
If $M$ is a matching of $G$ and $C$ is a cover of $G$ where $$	M
Augmenting Path Results L8-2	Lemma 8.1.1
Let $M$ be a matching. Let $P$ be an augmenting path. Let $M'$ be a new matching from P. $ightarrow M'=[M\cup (E(P)\setminus M)]\space \setminus (E(P)\cap M)$ Notes: - P is always odd length (L8-2 for proof) - P always starts and ends in different parts of the bipartition.	If a matching $M$ has an augmenting path $ightarrow$ $M$ is not a maximum.
Bipartite Matching Algorithm	Corollary L8-4
Minimum cover = $Y \cup (A \setminus X)$	A bipartite graph $G$ with $m$ edges and maximum degree $d$ has a matching of size $\ge \frac{m}{d}$
Neighbour Set ($N_G(D)$ or $N(D)$)	Hall's Theorem
Let $D \subseteq V(G)$. Neighbour set of $D$ is set of all vertices adjacent to at least 1 vertex in $D$.	A bipartite graph $G$ with bipartition $(A,B)$ has a matching that saturates all vertices in A $$\iff \space \forall \space D \subseteq A,
Corollary 8.6.2	Corollary L8-6
If $G$ is a $k$-regular bipartite graph with $k\ge 1$ $ightarrow$ $G$ has a perfect matching.	The edges of a $k$-regular bipartite graph can be partitioned into $k$ perfect matchings.