Formula Cheat Sheet
Every formula in the syllabus on one page. Print it. Read it once a week. Anything you cannot explain from memory, go and re-read that unit.
Three facts about the notation used here
x̄ (x-bar) = sample mean · μ = population mean · μ₀ = the value stated in H₀
p̂ (p-hat) = sample proportion (measured) · p₀ = proportion in H₀
σ = population standard deviation · s = sample standard deviation
Unit 1 · Relations & Functions
Cartesian product
A × B = { (a,b) : a∈A, b∈B }
|A × B| = |A| · |B|
|A × B| = |A| · |B|
Special relations
identity: (a,a) for all a∈A
universal: A × B
void: ∅ · binary: any R ⊆ A×B
universal: A × B
void: ∅ · binary: any R ⊆ A×B
Properties of R on A
reflexive: (a,a) ∈ R ∀a
symmetric: (a,b)∈R ⇒ (b,a)∈R
transitive: (a,b),(b,c)∈R ⇒ (a,c)∈R
equivalence = all three
symmetric: (a,b)∈R ⇒ (b,a)∈R
transitive: (a,b),(b,c)∈R ⇒ (a,c)∈R
equivalence = all three
Function types
injective: f(x₁)=f(x₂) ⇒ x₁=x₂
surjective: range = codomain
bijective = injective + surjective
(if |A|=|B|, one implies the other)
surjective: range = codomain
bijective = injective + surjective
(if |A|=|B|, one implies the other)
CS functions
⌊x⌋ = floor (round down)
⌈x⌉ = ceiling (round up)
AND = xy OR = x+y NOT = 1−x
exponential: aˣ, always through (0,1)
⌈x⌉ = ceiling (round up)
AND = xy OR = x+y NOT = 1−x
exponential: aˣ, always through (0,1)
Recursion
n! = n·(n−1)!, 0! = 1
F₀=0, F₁=1, Fₙ=Fₙ₋₁+Fₙ₋₂
aₙ = c₁aₙ₋₁+… → characteristic: rᵏ=c₁rᵏ⁻¹+…
distinct roots: A·r₁ⁿ+B·r₂ⁿ · repeated: (A+Bn)rⁿ
F₀=0, F₁=1, Fₙ=Fₙ₋₁+Fₙ₋₂
aₙ = c₁aₙ₋₁+… → characteristic: rᵏ=c₁rᵏ⁻¹+…
distinct roots: A·r₁ⁿ+B·r₂ⁿ · repeated: (A+Bn)rⁿ
Unit 2 · Counting, P & C
Basic principles
multiplication: n₁×n₂×…×nₖ
addition: n₁+n₂+…+nₖ (disjoint)
inclusion–exclusion: |A∪B|=|A|+|B|−|A∩B|
addition: n₁+n₂+…+nₖ (disjoint)
inclusion–exclusion: |A∪B|=|A|+|B|−|A∩B|
Pigeonhole
p > h ⇒ some hole has ≥ 2
general: h(k−1) + 1 guarantees k in one box
general: h(k−1) + 1 guarantees k in one box
Permutation — order MATTERS
ⁿP r = n!/(n−r)!
nPr = n(n−1)(n−2)…
nP2 = n(n−1) · nP1 = n
nPr = n(n−1)(n−2)…
nP2 = n(n−1) · nP1 = n
Combination — order DOESN'T
ⁿC r = n!/[r!(n−r)!]
ⁿC r = ⁿC ⁿ⁻ʳ · ⁿC 1 = n · ⁿC 0 = 1
ⁿC 2 = n(n−1)/2
ⁿC r = ⁿC ⁿ⁻ʳ · ⁿC 1 = n · ⁿC 0 = 1
ⁿC 2 = n(n−1)/2
Bridge between them
ⁿC r = ⁿP r / r! ← divide nPr by r!
if positions turn out to be identical
if positions turn out to be identical
Binomial theorem
(a+b)ⁿ = Σ ⁿC r aⁿ⁻ʳbʳ
Pascal: ⁿ⁺¹C r = ⁿC r + ⁿC r⁻¹
(r+1)ⁿ⁺¹C r+1 = (n−r)ⁿC r
Pascal: ⁿ⁺¹C r = ⁿC r + ⁿC r⁻¹
(r+1)ⁿ⁺¹C r+1 = (n−r)ⁿC r
Unit 3 · Probability
Definition & complement
P(A) = |A|/|S| (equally likely)
P(Ā) = 1 − P(A) · P(A)+P(Ā)=1
certain = 1 · impossible = 0
P(Ā) = 1 − P(A) · P(A)+P(Ā)=1
certain = 1 · impossible = 0
ADDITION law ("or")
P(A∪B) = P(A)+P(B) − P(A∩B)
mutually exclusive (P(A∩B)=0):
P(A∪B) = P(A)+P(B)
mutually exclusive (P(A∩B)=0):
P(A∪B) = P(A)+P(B)
MULTIPLICATION law ("and")
P(A∩B) = P(A)·P(B|A)
independent: P(A∩B) = P(A)·P(B)
n events: Π P(Aᵢ)
independent: P(A∩B) = P(A)·P(B)
n events: Π P(Aᵢ)
Conditional
P(A|B) = P(A∩B)/P(B)
independence test: P(A|B) = P(A)
independence test: P(A|B) = P(A)
Bayes
P(A|B) = P(B|A)·P(A) / P(B)
P(B) = P(B|A)P(A)+P(B|Ā)P(Ā)
P(B) = P(B|A)P(A)+P(B|Ā)P(Ā)
Counting bridge
P(exactly x in n trials) =
ⁿC x pˣ(1−p)ⁿ⁻ˣ ← from Units 2 + 3
ⁿC x pˣ(1−p)ⁿ⁻ˣ ← from Units 2 + 3
Unit 4 · Distributions
Normal
X ~ N(μ, σ²) (2nd number = variance)
z = (x − μ)/σ ← standardise
symmetric · area = 1 · P(X=c) = 0
68–95–99.7 within 1,2,3 σ
z = (x − μ)/σ ← standardise
symmetric · area = 1 · P(X=c) = 0
68–95–99.7 within 1,2,3 σ
z-table areas (Φ(z) = 0→z)
P(X<z) = Φ(z) + 0.5
P(0<X<z) = Φ(z) − 0.5
P(X>z) = 0.5 − Φ(z)
P(X>−z) = Φ(z) + 0.5
P(0<X<z) = Φ(z) − 0.5
P(X>z) = 0.5 − Φ(z)
P(X>−z) = Φ(z) + 0.5
Binomial
P(X=x) = ⁿC x pˣ(1−p)ⁿ⁻ˣ
μ = np · σ² = np(1−p)
σ = √[np(1−p)]
μ = np · σ² = np(1−p)
σ = √[np(1−p)]
Binomial conditions
fixed n · two outcomes · independent
· constant p
· constant p
Normal approximation
valid when np ≥ 5 AND n(1−p) ≥ 5
use μ = np, σ = √np(1−p)
continuity: a → a−0.5, b → b+0.5
use μ = np, σ = √np(1−p)
continuity: a → a−0.5, b → b+0.5
Standard error (used in Unit 5)
of x̄: σ/√n (known σ)
of x̄: s/√n (unknown σ)
of p̂: √[p₀(1−p₀)/n]
of x̄: s/√n (unknown σ)
of p̂: √[p₀(1−p₀)/n]
Unit 5 · Significance Testing
Hypotheses
H₀: μ = μ₀ or p = p₀ (has =)
H₁: μ ≠ μ₀ (2-tail) · > (1-tail R) · < (1-tail L)
H₁: μ ≠ μ₀ (2-tail) · > (1-tail R) · < (1-tail L)
Test statistics
z = (x̄ − μ₀)/(σ/√n) · σ known / n≥30
t = (x̄ − μ₀)/(s/√n) · σ unknown / n<30
z = (p̂ − p₀)/√[p₀(1−p₀)/n] · proportion
t = (x̄ − μ₀)/(s/√n) · σ unknown / n<30
z = (p̂ − p₀)/√[p₀(1−p₀)/n] · proportion
Critical values — z
| α | 1-tail | 2-tail |
| 0.10 | 1.282 | 1.645 |
| 0.05 | 1.645 | 1.96 |
| 0.025 | 1.960 | 2.241 |
| 0.01 | 2.326 | 2.576 |
| 0.005 | 2.576 | 2.807 |
| 0.001 | 3.090 | 3.291 |
Critical values — t, two-tail 0.05
| df | t | z |
| 1 | 12.71 | 1.96 |
| 2 | 4.303 | |
| 5 | 2.571 | |
| 10 | 2.228 | |
| 20 | 2.086 | |
| 30 | 2.042 | |
| ∞ | 1.960 |
Errors
Type I: reject true H₀ (prob = α)
Type II: fail to reject false H₀ (prob = β)
power = 1 − β
df = n − 1
Type II: fail to reject false H₀ (prob = β)
power = 1 − β
df = n − 1
Decision rule
|statistic| > critical → REJECT H₀
|statistic| < critical → FAIL TO REJECT
never write "accept H₀"
|statistic| < critical → FAIL TO REJECT
never write "accept H₀"
Unit 6 · Graph Theory
Core facts
G = (V, E) · |V| = order, |E| = size
path length = # of EDGES
complete Kₙ: deg = n−1, |E| = n(n−1)/2
connected ⇒ ≥ n−1 edges
path length = # of EDGES
complete Kₙ: deg = n−1, |E| = n(n−1)/2
connected ⇒ ≥ n−1 edges
Handshaking lemma
Σ deg(v) = 2|E|
⇒ degree sum is always EVEN
⇒ even number of odd-degree vertices
⇒ degree sum is always EVEN
⇒ even number of odd-degree vertices
Adjacency matrix (n×n)
aᵢⱼ = 1 if edge vᵢ→vⱼ else 0
symmetric ⇔ undirected
row sum = deg (undirected)
diag = 0 (no loops), 2 if loop
symmetric ⇔ undirected
row sum = deg (undirected)
diag = 0 (no loops), 2 if loop
Incidence matrix (n×m)
mᵢⱼ = 1 if vᵢ is an end of eⱼ
every column sums to 2 (undirected)
row sum = deg
every column sums to 2 (undirected)
row sum = deg
Directed graphs
out-degree d⁺(v) = arrows leaving
in-degree d⁻(v) = arrows entering
Σd⁺ = Σd⁻ = |E|
in-degree d⁻(v) = arrows entering
Σd⁺ = Σd⁻ = |E|
Dijkstra
pick smallest unvisited label,
permanently fix it, relax its edges
stop when all n labelled
needs non-negative weights
permanently fix it, relax its edges
stop when all n labelled
needs non-negative weights
Colouring — χ(G)
empty graph 1 · tree 2 · bipartite 2
Cₙ even 2 · Cₙ odd 3 · Kₙ n
planar ≤ 4
Cₙ even 2 · Cₙ odd 3 · Kₙ n
planar ≤ 4
Bipartite test
2-colour the graph.
success ⇔ no odd cycle ⇔ χ = 2
failure ⇒ odd cycle ⇒ χ ≥ 3
success ⇔ no odd cycle ⇔ χ = 2
failure ⇒ odd cycle ⇒ χ ≥ 3
Unit 7 · Trees
Tree = definition
connected + acyclic + undirected
|E| = |V| − 1 (exactly)
unique path between every pair
height = longest root-to-leaf path
diameter = longest path overall
|E| = |V| − 1 (exactly)
unique path between every pair
height = longest root-to-leaf path
diameter = longest path overall
Traversals
PRE = Node, Left, Right
IN = Left, Node, Right
POST = Left, Right, Node
in-order on a BST = ascending
IN = Left, Node, Right
POST = Left, Right, Node
in-order on a BST = ascending
Binary tree sizes
max nodes to depth d: 2d+1 − 1
1, 3, 7, 15, 31, 63
min height for n nodes: ⌊log₂ n⌋
in-order needs BINARY tree
1, 3, 7, 15, 31, 63
min height for n nodes: ⌊log₂ n⌋
in-order needs BINARY tree
Spanning tree
covers ALL vertices
exactly n − 1 edges
edges to delete = m − n + 1
exactly n − 1 edges
edges to delete = m − n + 1
KRUSKAL
1. sort ALL edges ascending
2. add if no cycle forms
3. stop at n − 1 edges
"cheapest from anywhere"
2. add if no cycle forms
3. stop at n − 1 edges
"cheapest from anywhere"
PRIM
1. pick any start vertex
2. add cheapest edge LEAVING the tree
3. stop at n − 1 edges
"grow one blob"
2. add cheapest edge LEAVING the tree
3. stop at n − 1 edges
"grow one blob"
The Ten Formulas That Cover 90% of Marks
If you only memorise ten lines, memorise these
1. ⁿC r = n!/[r!(n−r)!] — with nPr = n!/(n−r)! when order matters
2. P(A∪B) = P(A)+P(B)−P(A∩B) — subtract the overlap
3. P(A|B) = P(A∩B)/P(B) — the conditional
4. P(A|B) = P(B|A)P(A) / P(B) — Bayes, and split P(B) into two parts
5. P(X=x) = ⁿC x pˣ(1−p)ⁿ⁻ˣ — binomial
6. z = (x − μ)/σ — standardise anything
7. z = (x̄−μ₀)/(σ/√n) — test a mean
8. z = (p̂−p₀)/√[p₀(1−p₀)/n] — test a proportion
9. Σ deg(v) = 2|E| — handshaking, always even
10. |E| = |V| − 1 — defines a tree / spanning tree
2. P(A∪B) = P(A)+P(B)−P(A∩B) — subtract the overlap
3. P(A|B) = P(A∩B)/P(B) — the conditional
4. P(A|B) = P(B|A)P(A) / P(B) — Bayes, and split P(B) into two parts
5. P(X=x) = ⁿC x pˣ(1−p)ⁿ⁻ˣ — binomial
6. z = (x − μ)/σ — standardise anything
7. z = (x̄−μ₀)/(σ/√n) — test a mean
8. z = (p̂−p₀)/√[p₀(1−p₀)/n] — test a proportion
9. Σ deg(v) = 2|E| — handshaking, always even
10. |E| = |V| − 1 — defines a tree / spanning tree
Notice the shape
Formulas 7 and 8 are the same formula with a different numerator and denominator. 5, 7 and 8 are all "(observed − claimed) ÷ standard error". Formula 1 is a special case of dividing by r!. Formula 10 is formula 9 with n = |E|+1.
This course is far smaller than it looks. Learn the shapes, not thirty separate rules.