A set is a well-defined collection of distinct objects called elements. Example: $A = \{1, 2, 3, 4\}$ — the set of positive integers less than 5.

The power set is the set of all subsets of $A$. If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$. For $|A| = 4$: $|\mathcal{P}(A)| = 2^4 = 16$.

$|A \cup B| = |A| + |B| - |A \cap B|$. We add both and subtract the overlap counted twice.

A binary relation that is reflexive ($a \sim a$), symmetric ($a \sim b \Rightarrow b \sim a$), and transitive ($a \sim b, b \sim c \Rightarrow a \sim c$).

A partition of $A$ is a collection of non-empty, pairwise-disjoint subsets whose union is $A$. Every equivalence relation creates a partition.

A set in bijection with $\mathbb{N}$ (countably infinite). Examples: $\mathbb{N}, \mathbb{Z}, \mathbb{Q}$. Note: $\mathbb{R}$ is uncountable.

For any set $A$, $|A| < |\mathcal{P}(A)|$. No set is in bijection with its own power set; hence $\mathbb{R}$ is uncountable.

A relation that is reflexive, antisymmetric ($a \le b, b \le a \Rightarrow a = b$) and transitive. Example: divisibility on $\mathbb{N}$.

$^8P_3 = \dfrac{8!}{(8-3)!} = 8 \cdot 7 \cdot 6 = 336$.

$\binom{10}{3} = \dfrac{10!}{3! \, 7!} = \dfrac{10 \cdot 9 \cdot 8}{6} = 120$.

Letters: S×3, T×3, A×1, I×2, C×1 (total 10). Arrangements $= \dfrac{10!}{3! \, 3! \, 2!} = 50{,}400$.

Circular arrangements $= (8 - 1)! = 7! = 5040$. Fix one person and arrange the rest.

$A \cup B = \{1, 2, 3, 4, 5\}$. $A \cap B = \{3\}$.

$(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$. The complement of union = intersection of complements.

$A \times B = \{(a, b) : a \in A, b \in B\}$ — set of all ordered pairs. $|A \times B| = |A| \cdot |B|$.

A relation $R$ on $A$ is reflexive if $a R a$ for every $a \in A$. Example: $\le$ on $\mathbb{R}$ (every number is $\le$ itself).

$a R b \Rightarrow b R a$ for all $a, b$. Example: "is a sibling of" — if A is sibling of B, then B is sibling of A.

$a R b$ and $b R c \Rightarrow a R c$. Example: "is taller than" — if A is taller than B and B taller than C, then A is taller than C.

If (i) $P(1)$ is true and (ii) $P(k) \Rightarrow P(k+1)$ for all $k \ge 1$, then $P(n)$ is true for all natural numbers $n$.

$\binom{5}{3} = \dfrac{5!}{3! \, 2!} = 10$ such subsets.

$^n P_n = \dfrac{n!}{(n - n)!} = \dfrac{n!}{0!} = n!$ — the number of ways to arrange all $n$ distinct objects.

$^n C_0 = 1$ (empty selection) and $^n C_n = 1$ (the full set). Both equal 1.

$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$. Choosing $r$ from $n$ = choosing $(r-1)$ that include a fixed element + $r$ that exclude it.

$\binom{n}{r} = \dfrac{n!}{r! (n-r)!} = \dfrac{n!}{(n-r)! r!} = \binom{n}{n-r}$. Picking $r$ to include = picking $(n-r)$ to exclude.

$= 2^n$. (By Binomial theorem with $x = y = 1$.) This equals the total number of subsets of an $n$-element set.

11 letters: E×3, N×3, G×2, I×2, R×1. Arrangements $= \dfrac{11!}{3! \, 3! \, 2! \, 2!} = \dfrac{39{,}916{,}800}{144} = 277{,}200$.

Arrange 5 boys: $5! = 120$. This creates 6 gaps (before, between, after). Choose 4 of 6 gaps for the girls and arrange them: $\binom{6}{4} \cdot 4! = 15 \cdot 24 = 360$. Total $= 120 \times 360 = 43{,}200$.

Pick 4 of 5 digits and arrange: $^5 P_4 = \dfrac{5!}{1!} = 120$ four-digit numbers.

Each of the 4 positions has 26 choices independently: $26^4 = 456{,}976$ words.

$\binom{15}{11} = \binom{15}{4} = \dfrac{15 \cdot 14 \cdot 13 \cdot 12}{4!} = \dfrac{32{,}760}{24} = 1365$ ways.

Two specific books are pre-selected. Choose remaining 2 from the other 8: $\binom{8}{2} = 28$ ways.

Necklace arrangements (rotations + reflections equivalent): $\dfrac{(n - 1)!}{2} = \dfrac{4!}{2} = 12$ arrangements.

"EQUATION" has 8 letters, 5 vowels (E, U, A, I, O) and 3 consonants (Q, T, N). Treat the 5 vowels as one block: 4 units to arrange = $4!$. Vowels inside the block: $5!$. Total $= 4! \times 5! = 24 \times 120 = 2880$.

Stars and bars: $\binom{n + k - 1}{k - 1} = \binom{10 + 3 - 1}{3 - 1} = \binom{12}{2} = 66$ ways.

Total committees of 5 from 14: $\binom{14}{5} = 2002$. Subtract committees with fewer than 2 women — i.e., 0 women or 1 woman:

• 0 women: $\binom{8}{5} = 56$.
• 1 woman: $\binom{6}{1} \binom{8}{4} = 6 \cdot 70 = 420$.

Answer $= 2002 - 56 - 420 = 1526$ ways.

A graph $G = (V, E)$ with no self-loops and no multiple edges between the same pair of vertices.

A graph that allows multiple edges between the same pair of vertices, but typically no self-loops.

$\sum_{v \in V} \deg(v) = 2|E|$. Each edge contributes 1 to the degree of each endpoint, so the sum is twice the edge count.

$|E| = \binom{n}{2} = \dfrac{n(n-1)}{2}$ — every pair of vertices joined.

$|E| = m \cdot n$ — every vertex on the left joined to every vertex on the right.

A closed walk that uses every edge exactly once. A connected graph has one iff every vertex has even degree (Euler's theorem).

A cycle that visits every vertex of the graph exactly once. Finding one is NP-complete in general.

A path is a sequence of distinct vertices joined by edges; first and last differ. A cycle is a closed path (first vertex = last vertex).

$V - E + F = 2$, where $F$ counts all faces including the unbounded outer face.

For simple planar graphs $E \le 3V - 6$. For $K_5$: $V = 5, E = 10$, but $3(5) - 6 = 9 < 10$. So $K_5$ cannot be planar.

A subgraph of a connected graph $G$ that is a tree and includes every vertex of $G$. It has $|V| - 1$ edges.

Exactly $n - 1$. A tree is connected and acyclic, with this minimum number of edges to connect all vertices.

For $n$ vertices, the $n \times n$ matrix $A$ where $A_{ij} = 1$ if $(v_i, v_j) \in E$ and 0 otherwise. Symmetric for undirected graphs.

The number of walks of length exactly $k$ from vertex $v_i$ to vertex $v_j$.

A graph where each edge has a direction (ordered pair). Each vertex has separate in-degree and out-degree.

In-degree of a vertex = number of edges coming into it. Out-degree = number of edges going out from it.

A graph is connected if there is a path between every pair of vertices. Otherwise, it splits into connected components.

A graph whose vertex set splits into two disjoint subsets $V_1, V_2$ such that every edge connects $V_1$ to $V_2$. No odd cycles.

A vertex whose removal disconnects the graph (or increases the number of components).

An edge whose removal disconnects the graph (or increases components). Removing it breaks a connected graph.

The rank is the number of linearly independent rows (equivalently, columns). It equals the dimension of the column space.

For an $m \times n$ matrix $A$: $\text{rank}(A) + \text{nullity}(A) = n$.

Diagonal matrix — eigenvalues are the diagonal entries: $\lambda_1 = 2, \lambda_2 = 3$.

A non-zero vector $v$ such that $A v = \lambda v$ for some scalar $\lambda$ (the eigenvalue). $A$ only stretches $v$ — doesn't rotate it.

Trace = sum of diagonal entries: $\text{tr}(A) = \sum_i a_{ii}$. Equals the sum of all eigenvalues.

A square matrix with $\det(A) = 0$ — it has no inverse, its columns are linearly dependent, and 0 is an eigenvalue.

Any real $m \times n$ matrix can be written $A = U \Sigma V^T$, where $U$ and $V$ are orthogonal and $\Sigma$ is diagonal with non-negative singular values.

A square matrix $Q$ with $Q^T Q = I$ — its columns (and rows) form an orthonormal set. $\det Q = \pm 1$.

$\cos\theta = \dfrac{x \cdot y}{\|x\| \, \|y\|}$ — measures the angle between two vectors. Used in text and embedding similarity.

The set $\{x \in \mathbb{R}^n : w^T x + b = 0\}$ for some non-zero $w$. It's an $(n-1)$-dimensional flat. In 2D it's a line; in 3D a plane.

$N(A) = \{x : A x = 0\}$ — the set of vectors mapped to zero. Its dimension is the nullity.

Vectors $v_1, \dots, v_k$ are linearly independent if $c_1 v_1 + \dots + c_k v_k = 0$ implies all $c_i = 0$.

Every square matrix satisfies its own characteristic equation: if $p(\lambda) = \det(\lambda I - A)$, then $p(A) = 0$.

$\det = (1)(4) - (2)(3) = 4 - 6 = -2$.

A square matrix with 1's on the diagonal and 0's elsewhere; $I_n$ acts as identity for matrix multiplication: $A I = I A = A$.

For square $A$ with $\det A \ne 0$, the inverse $A^{-1}$ satisfies $A A^{-1} = A^{-1} A = I$. For $2 \times 2$: $A^{-1} = \dfrac{1}{\det A}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$.

A square matrix with $A^T = A$, i.e., $a_{ij} = a_{ji}$. Always has real eigenvalues and orthogonal eigenvectors.

A symmetric matrix $A$ with $x^T A x > 0$ for all non-zero $x$. All eigenvalues positive.

$|x \cdot y| \le \|x\| \, \|y\|$ — the inner product is bounded by the product of norms.

Dropping a perpendicular from a vector onto a subspace. For vector $u$ onto $v$: $\text{proj}_v u = \dfrac{u \cdot v}{v \cdot v} \, v$.

The vector $\vec{OP}$ from origin $O$ to a point $P$. For $P(x, y, z)$, $\vec{OP} = \langle x, y, z \rangle$.

$\|\vec{v}\| = \sqrt{9 + 16 + 144} = \sqrt{169} = 13$.

$(1)(4) + (2)(5) + (3)(6) = 4 + 10 + 18 = 32$.

$\vec{a} \times \vec{b} = \begin{vmatrix} \hat i & \hat j & \hat k \\ a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \end{vmatrix}$. Magnitude = $\|\vec{a}\|\|\vec{b}\|\sin\theta$ = area of parallelogram.

$\vec{r}(t) = \vec{A} + t(\vec{B} - \vec{A})$ for $t \in \mathbb{R}$. Direction = $\vec{B} - \vec{A}$.

$\vec{n} \cdot (\vec{r} - \vec{r}_0) = 0$, where $\vec{n}$ is the normal and $\vec{r}_0$ is a point on the plane.

For plane $ax + by + cz + d = 0$ and point $P_0(x_0, y_0, z_0)$: $d = \dfrac{|a x_0 + b y_0 + c z_0 + d|}{\sqrt{a^2 + b^2 + c^2}}$.

For line through $A$ with direction $\vec{d}$ and point $P$: $d = \dfrac{\|\vec{AP} \times \vec{d}\|}{\|\vec{d}\|}$.

$(x - h)^2 + (y - k)^2 + (z - l)^2 = r^2$ — sphere of radius $r$ centred at $(h, k, l)$.

$x = r \cos\theta$, $y = r \sin\theta$, $z = z$.

$x = \rho \sin\phi \cos\theta$, $y = \rho \sin\phi \sin\theta$, $z = \rho \cos\phi$.

$\cos\theta = \dfrac{\vec{a} \cdot \vec{b}}{\|\vec{a}\| \, \|\vec{b}\|}$. Take $\arccos$ for the angle.

$\text{proj}_{\vec{v}} \vec{u} = \dfrac{\vec{u} \cdot \vec{v}}{\vec{v} \cdot \vec{v}} \, \vec{v}$.

$[\vec{a}, \vec{b}, \vec{c}] = \vec{a} \cdot (\vec{b} \times \vec{c})$ — a scalar equal to the (signed) volume of the parallelepiped with edges $\vec{a}, \vec{b}, \vec{c}$.

$V = |\vec{a} \cdot (\vec{b} \times \vec{c})|$ — absolute value of the scalar triple product.

Find two edge vectors from one point, compute their cross product (gives normal $\vec{n}$), then use $\vec{n} \cdot (\vec{r} - \vec{r}_0) = 0$.

$x = x_0 + a t, \; y = y_0 + b t, \; z = z_0 + c t$, where $(x_0, y_0, z_0)$ is a point on the line and $(a, b, c)$ its direction.

$d = \dfrac{|d_1 - d_2|}{\sqrt{a^2 + b^2 + c^2}}$.

$\|(3, 4, 0)\| = 5$. Unit vector $= (3/5, 4/5, 0)$.

$\|(2,1,2)\| = 3$. Direction cosines: $(2/3, 1/3, 2/3)$.

(i) $P(A) \ge 0$. (ii) $P(\Omega) = 1$. (iii) For disjoint events, $P(\bigcup A_i) = \sum P(A_i)$.

$P(A \mid B) = \dfrac{P(A \cap B)}{P(B)}$ for $P(B) > 0$. "Probability of $A$ given $B$ has occurred."

$P(A \mid B) = \dfrac{P(B \mid A) \, P(A)}{P(B)}$. Inverts conditioning using prior and likelihood.

$A$ and $B$ are independent iff $P(A \cap B) = P(A) \, P(B)$. Knowing $B$ doesn't change $P(A)$.

A function $X: \Omega \to \mathbb{R}$ taking countably many values, described by PMF $p(x) = P(X = x)$ with $\sum p(x) = 1$.

A function taking values in an interval, described by PDF $f(x) \ge 0$ with $\int f = 1$. Probabilities = $\int_a^b f(x) dx$.

$P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}, \; k = 0, 1, \dots, n$. Mean = $np$, variance = $np(1-p)$.

$f(x) = \dfrac{1}{\sigma \sqrt{2\pi}} \exp\!\left(-\dfrac{(x - \mu)^2}{2 \sigma^2}\right)$ for $x \in \mathbb{R}$.

Mean $= E[X] = p$. Variance $= E[X^2] - (E[X])^2 = p - p^2 = p(1-p)$.

$E[X] = E[E[X \mid Y]]$. Average the conditional means over $Y$.

$\text{Cov}(X, Y) = E[(X - \mu_X)(Y - \mu_Y)] = E[XY] - E[X] E[Y]$. Measures linear co-movement.

$P(X = k) = \dfrac{e^{-\lambda} \lambda^k}{k!}, \; k = 0, 1, 2, \dots$ Mean = variance = $\lambda$.

$f(x) = \dfrac{1}{b - a}$ for $x \in [a, b]$, else 0. Mean = $(a+b)/2$, variance = $(b-a)^2/12$.

$f(x) = \lambda e^{-\lambda x}$ for $x \ge 0$. Mean = $1/\lambda$, variance = $1/\lambda^2$.

For any random variable with finite variance: $P(|X - \mu| \ge k \sigma) \le \dfrac{1}{k^2}$.

$F(x) = P(X \le x)$. Non-decreasing, right-continuous, $F(-\infty) = 0, F(\infty) = 1$.

Mean = $\lambda$, variance = $\lambda$. The Poisson is the only standard distribution where mean = variance.

Mean = $\dfrac{a+b}{2}$. Variance = $\dfrac{(b-a)^2}{12}$.

If $\{B_1, \dots, B_n\}$ partitions $\Omega$, then $P(A) = \sum_i P(A \mid B_i) P(B_i)$.

$\rho = \dfrac{\text{Cov}(X, Y)}{\sigma_X \sigma_Y} \in [-1, 1]$. Measures the strength of linear association.

Statement. For three finite sets $A, B, C$: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$

Proof. Take any element $x \in A \cup B \cup C$, suppose it lies in exactly $k$ of the three sets.

• LHS counts $x$ once.
• RHS counts $x$: $\binom{k}{1}$ singletons − $\binom{k}{2}$ pair-intersections + $\binom{k}{3}$ triple.

For $k = 1, 2, 3$: net = $1 - 0 + 0 = 1$; $2 - 1 + 0 = 1$; $3 - 3 + 1 = 1$. So each element counted once on both sides. ∎

Application. Let $A_k$ = multiples of $k$ in $\{1, \dots, 500\}$, so $|A_k| = \lfloor 500/k \rfloor$.

• $|A_3| = 166, \; |A_5| = 100, \; |A_7| = 71$.
• $|A_3 \cap A_5| = \lfloor 500/15 \rfloor = 33$.
• $|A_3 \cap A_7| = \lfloor 500/21 \rfloor = 23$.
• $|A_5 \cap A_7| = \lfloor 500/35 \rfloor = 14$.
• $|A_3 \cap A_5 \cap A_7| = \lfloor 500/105 \rfloor = 4$.

$|A_3 \cup A_5 \cup A_7| = 166 + 100 + 71 - 33 - 23 - 14 + 4 = 271$.

So 271 integers in 1–500 are divisible by 3, 5 or 7.

Definition. A relation $\sim$ on $A$ that is reflexive, symmetric, and transitive. For $a \in A$, the equivalence class $[a] = \{x : x \sim a\}$.

Theorem. The equivalence classes of $\sim$ form a partition of $A$.

Proof.

1. Non-empty. Reflexivity: $a \in [a]$, so $[a] \ne \emptyset$.
2. Cover. Each $a \in [a]$, so $\bigcup_a [a] = A$.
3. Disjoint or equal. Suppose $[a] \cap [b] \ne \emptyset$, pick $c$ in both. Then $c \sim a$ and $c \sim b$. Symmetry gives $a \sim c$, transitivity $a \sim b$. For any $x \in [a]$: $x \sim a \sim b$, so $x \in [b]$. So $[a] \subseteq [b]$. By symmetry $[a] = [b]$. ∎

Verification with $\sim$ on $\mathbb{Z}$, $a \sim b \iff 4 \mid (a - b)$.

• Reflexive: $a - a = 0$, divisible by 4. ✓
• Symmetric: $4 \mid (a - b) \Rightarrow 4 \mid (b - a)$. ✓
• Transitive: $4 \mid (a-b)$ and $4 \mid (b-c) \Rightarrow 4 \mid (a-c)$. ✓

The four classes are $[0], [1], [2], [3]$ — residue classes mod 4 — and they partition $\mathbb{Z}$.

Principle. If $P(n_0)$ is true (base case) and $P(k) \Rightarrow P(k+1)$ (induction step), then $P(n)$ is true for all $n \ge n_0$.

Part 1. Prove $\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$.

Base $n = 1$: LHS = 1, RHS = $1 \cdot 2 / 2 = 1$. ✓

Step. Assume $\sum_{i=1}^{k} i = k(k+1)/2$. Then $\sum_{i=1}^{k+1} i = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2} = \dfrac{(k+1)(k+2)}{2}$. ∎

Part 2. Prove $3 \mid (n^3 + 2n)$ for $n \ge 1$.

Base $n = 1$: $1 + 2 = 3$, divisible by 3. ✓

Step. Assume $3 \mid (k^3 + 2k)$, i.e., $k^3 + 2k = 3m$ for some integer $m$. Then $(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2 = (k^3 + 2k) + 3k^2 + 3k + 3 = 3m + 3(k^2 + k + 1)$ — divisible by 3. ∎

(i) Choose 4 of 10 men and 3 of 8 women: $\binom{10}{4} \cdot \binom{8}{3} = 210 \cdot 56 = 11{,}760$ ways.

(ii) "MATHEMATICS" has 11 letters: M×2, A×2, T×2, H, E, I, C, S. Arrangements $= \dfrac{11!}{2! \, 2! \, 2!} = \dfrac{39{,}916{,}800}{8} = 4{,}989{,}600$.

(iii) Treat the 2 specific persons as a single block: 5 units to arrange = $5! = 120$. The 2 within the block can swap: $2! = 2$. Total $= 5! \times 2! = 120 \times 2 = 240$ ways.

Theorem. A connected graph has an Eulerian circuit iff every vertex has even degree.

Proof. (⇒) If an Eulerian circuit exists, every time the walk enters a vertex it must leave by another edge. Edges at each vertex pair up, so every degree is even.

(⇐) Suppose connected and all even degree. Start a trail at any vertex $v_0$. The even-degree condition ensures that whenever we reach a vertex, an unused outgoing edge exists. The trail must return to $v_0$, forming a circuit $C_0$.

If $C_0$ uses all edges, done. Otherwise, by connectivity, some vertex on $C_0$ has unused edges; build another circuit and splice in. Repeat until all edges used. ∎

Verify $K_6$. $K_6$: every vertex has degree $5$ (odd!). So $K_6$ does NOT have an Eulerian circuit. (Only $K_n$ with $n$ odd does — degree $n - 1$ even.)

Hamiltonian. Visit vertices in cyclic order $v_1 \to v_2 \to \dots \to v_6 \to v_1$. Every consecutive pair is joined (complete graph). So $K_6$ DOES have a Hamiltonian circuit. Every $K_n$ with $n \ge 3$ is Hamiltonian.