Discrete Math Final Review

Multiplicative Inverse of a

ā

How to find Inverse

1) Use Euclids and stop at 1

2) Rewrite in terms of 1

3) Take a’s coefficient mod m (if negative, +m)

Chinese Remainder Theorem

x = a₁M₁M̅₁+ a₂M₂M̅₂ + a₃M₃M̅₃ mod M

What is M?

m1*m2*m3

What is M_i?

other m’s multiplied

What is M̅_i?

M_i mod m_i

Fermat’s Little Theorem

a^p = a mod p

Induction

1) Basis Step: Prove p(b) is true
2) IH: p(k) is true for arbitrary k ≥ b
3) Inductive Step: Prove p(k) => p(k+1) is true

Well Ordering Principle

Every nonempty set of natural numbers has a smallest element.

Strong Induction

1) Basis Step: Prove p(b) is true

2) Strong IH: p(j) is true for b ≤ j ≤ k
3) Inductive Step: Prove p(b) ∧ p(b+1) ∧ … ∧ p(k) => p(k+1) is true

Recursive Definition

1) Basis Definition: f(0), the first element. Ex: a₀ = 0
2) Recursive Definition: defines f(n). Ex: an = a_n-1 + 1

Structural Induction

1) Basis Step: Prove the property is true for the basis element of the recursive definition.
2) IH: Assume the property holds for RHS of recursive def.

3) Inductive Step: Prove the property for a_n

Σ

Alphabet

String

Sequence of characters from Σ

Σ*

Finite String; can be defined recursively

ℓ(w) where w is a string

Length of string w

λ

Empty string “ ”, ℓ(λ) = 0, always an element of Σ*

Product Rule

A procedure contains 2 tasks. n1 ways to do 1st task, n2 ways to do 2nd task; total ways: n1 * n2

Subtraction Rule

Task can be done in n1 or n2 non-disjoint ways, total ways: n1 + n2 - # of ways in common

Sum Rule

Task can be done in n1 or n2 disjoint ways, total ways: n1 + n2

Division Rule

n ways to do a task, each equivalent to d ways, total ways: n/d

Pigeonhole Principle

Place n objects into k boxes, 1 box has at least ⌈n/k⌉

Permutations

Set of ordered arrangements of all elements of a set; n! permutations for n elements

r-permutations

Ordered arrangement of only r ≤ n elements of a set of size n.

P(n, r)

n!/(n-r)!

r-combination

Unordered selection of r elements from a set of size n.

C(n,r)

n!/(n-r)!r!

Binomial Theorem

(x+y)ⁿ = Σ r = 0 to n, C(n,r) * x^n-ry^r

Permutation with Indistinguishable Objects

n!/(n1!*n2!*…*nk!) where n1 … nk are separate indistinguishable objects

Stars and Bars

N desired → N stars, k types → k - 1 bars

Stars and Bars formula

(bars+stars)!/(bars!stars!)

Linear Recurrence Form

an = c₁a_n-1 + c₂a_n-2 + … + c_ka_n-k

Characteristic Equation

r^k = c₁r^k-1 + c₂r^k-2

General Solution for Unique Roots

a_n = α₁(root₁)ⁿ + α₂(root₂)ⁿ

Master’s Theorem for the form T(n) = aT(n/b) + cn^d

1) log_ba = d → Θ(n^dlogn)

2) log_ba > d → Θ(n^logba)

or 3) log_ba < d → Θ(n^d)

Inclusion-Exclusion

1) | A ∪ B | = |A| + |B| - |A ∩ B|
2) | A ∪ B ∪ C | = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

Derangement

A permutation where no element is left in its starting position.

Relation R

From set A → set B, a subset of A x B. Every element in A can map as to many elements in B.

Matrix Representation of Relation

row = A’s elements, col = B’s elements. If a pair exists, place a 1. Otherwise, 0.

Reflexive R: A → A

∀a ∈ A((a,a) ∈ R); every element is related to itself. Matrix diagonal = 1.

Symmetric R: A → A

∀a, b∈ A((a,b) ∈ R <=> (b,a) ∈ R); if a relates to b, then b relates to a. Mij = Mji

Asymmetric R: A → A

∀a, b∈ A((a,b) ∈ R ∧ (b,a) ∈ R => a = b); if a and b mutually relate, then a = b. If Mij = 1, then Mji = 0 if i ≠ j

Transitive R: A → A

∀a, b, c ∈ A((a,b) ∈ R ∧ (b,c) ∈ R => (a,c) ∈ R); if a relates to b and b relates to c, then a relates to c.

Composition of Relations R1: A → B and R2: B → C

R2 ∘ R1 relates A to C such that ∀x ∈ A, y ∈ B, z ∈ C ((x,y) ∈ R1 ∧ (y,z) ∈ R2 <=> (x,z) ∈ R2 ∘ R1)

Reflexive Relation Graph Representation

A loop

Symmetric Relation Graph Representation

Every edge has an anti-parallel edge

Asymmetric Relation Graph Representation

Anti-parallel edges DNE

Transitive Relation Graph Representation

If a path can be followed from point a to c, then an arrow directly from a to c is present.

Closure of a Relation with Respect to Property P

Add the least amount of elements to the current relation to satisfy P (reflexive, symm, anti-symm, transitive)

Equivalence Relation

Reflexive, transitive, and symmetric. a ~ b

Partial Ordering

Reflexible, transitive, and anti-symmetric. a ≤ b (curvy ≤)

Set Partition

Collection of disjoint subsets A₁, A₂, … A_n ⊆ S where
1) A_i ≠ Ø ∀i; all subsets are nonempty
2) A_i ∩ A_j = Ø; all subsets are disjoint from each other
3) A₁ ∪ A₂ ∪ … ∪ A_n = S; union all subsets to get the set

Graph G = (V, E)

V: set of vertices, E: set of edges

{}

Undirected edges

()

Directed edges

Multiedge

The same edge repeats

Simple Graph

A graph with NO loops or multiedges

Multigraph

Every graph that’s NOT a simple graph.

Incident

The edge {u, v} is incident to u and v

Adjacent

u and v are adjacent if {u, v} ∈ E

Neighborhood

The set of all vertices adjacent, N(a): neighborhood of a

Simple Graph Degree

deg(v) = size of neighborhood

Multigraph Degree

deg(v) = the # of edge incident. for each loop, +2

Handshaking Lemma for Undirect Graphs

Sum of the degree of all vertices = 2|E|

Directed Graph

Each edge has an orientation. (a,b) ≠ (b,a)

In-degree

Number of edges ending at v, deg^-(v)

Out-degree

Number of edges starting at v, deg⁺(v)

Total Degree of v for a Directed Graph

deg^-(v) + deg⁺(v)

Handshaking Lemma for Directed Graph

|E| = sum of in-degree = sum of out-degree

General Solution for Identical Roots

a_n = α₁(root₁)ⁿ + nα₂(root₂)ⁿ

Complete Graph K_n

Simple undirected graph with an edge between every 2 vertices.

Cycle on Vertices C_n

A cycle from the starting vertex that also ends there.

|E| for Complete Graph

n(n-1)/2 where n = number of vertices

|E| for Cycle

n where n = number of vertices

Bipartite Graph

Vertices can partition into 2 disjoint sets, V1 and V2

No odd cycles =>

Graph is bipartite

Complete Bipartite K_m,n

|V1| = m, |V2| = n, with all possible edges between V1 and V2

|E| for Complete Bipartite

m * n where m = |V1| and n = |V2|

Subgraph of G = (V,E)

H = (W,F) where W ⊆ V and F ⊆ E

Induced Subgraph

H = (W,F) such that W ⊆ V and F has all edges between vertices in W

Proper Subgraph

H ⊂ G, they are never equal.

Adjacency List

For each vertex, list their adjacent vertices.

Size of Adjacency List

|V| + 2|E|

Adjacency Matrix

Vertices in row and column. 1 f the vertices are adjacent. 0 otherwise.

Size of Adjacency Matrix

|V|²

Undirected Adjacency Matrix Characteristic

Symmetric

Directed Adjacency Matrix Characteristic

Not symmetric

Tree

Connected undirected graph with no simple cycles

Rooted Tree

1 vertex is designed as the root

m-ary Tree

Every internal vertex has at most m children

Full m-ary Tree

Every internal vertex has exactly m children

Tree of n vertices =>

n-1 edges

If A graph has n vertices and |E| ≥ n =>

The graph has a cycle

Level of vertex v

The number of edges from the root to v

Balanced m-ary Tree

Every leaf’s level = h or h-1

For a height h m-ary tree, how many leaves at most?

m^h leaves

For a height h m-ary tree, what is the relationship between h, m, and ℓ?

h ≥ ⌈log_mℓ⌉

For a height h FULL m-ary tree, what is the relationship between h, m, and ℓ?

h = ⌈log_mℓ⌉

Spanning Tree

Subgraph tree with all vertices from the original graph.

Pre-order Tree Traversal

Print as you visit