📌 Set Theory

Union:

\( A \cup B = \{ x : x \in A \text{ or } x \in B \} \)

Intersection:

\( A \cap B = \{ x : x \in A \text{ and } x \in B \} \)

Complement:

\( A' = \{ x : x \notin A \} \)

Difference:

\( A \setminus B = \{ x : x \in A \text{ and } x \notin B \} \)

Cartesian Product:

\( A \times B = \{ (a, b) : a \in A, b \in B \} \)

Cardinality of Union (Inclusion-exclusion):

\( |A \cup B| = |A| + |B| - |A \cap B| \)

Three-Set Inclusion-Exclusion:

\( |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \)

Power Set Size:

\( |\mathcal{P}(A)| = 2^{|A|} \)

Subset Relation:

\( A \subseteq B \) if \( \forall x (x \in A \implies x \in B) \)

De Morgan’s Laws:

\( (A \cup B)' = A' \cap B' \)

\( (A \cap B)' = A' \cup B' \)

📌 Logic

Negation:

\( \neg P \) (not \( P \))

Conjunction:

\( P \land Q \) (P and Q)

Disjunction:

\( P \lor Q \) (P or Q)

Implication:

\( P \to Q \) (if P then Q, \( \neg P \lor Q \))

Biconditional:

\( P \leftrightarrow Q \) (P if and only if Q, \( (P \to Q) \land (Q \to P) \))

De Morgan’s Laws for Logic:

\( \neg (P \land Q) \equiv \neg P \lor \neg Q \)

\( \neg (P \lor Q) \equiv \neg P \land \neg Q \)

Distributive Laws:

\( P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R) \)

\( P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R) \)

Tautology Example:

\( P \lor \neg P \equiv \text{True} \)

Contradiction Example:

\( P \land \neg P \equiv \text{False} \)

📌 Combinatorics

Factorial:

\( n! = n \cdot (n-1) \cdot \ldots \cdot 1 \)

Permutations:

\( P(n, k) = \frac{n!}{(n-k)!} \)

Combinations:

\( \binom{n}{k} = \frac{n!}{k!(n-k)!} \)

Binomial Theorem:

\( (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k \)

Pascal’s Identity:

\( \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \)

Sum of Binomial Coefficients:

\( \sum_{k=0}^{n} \binom{n}{k} = 2^n \)

Alternating Binomial Sum:

\( \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \)

Multinomial Theorem:

\( (x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1 + k_2 + \cdots + k_m = n} \frac{n!}{k_1! k_2! \cdots k_m!} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m} \)

Permutations with Repetition:

\( \frac{n!}{n_1! n_2! \cdots n_k!} \) (where \( n_1 + n_2 + \cdots + n_k = n \))

Stirling Number (2nd Kind):

\( S(n, k) \) = number of ways to partition \( n \) objects into \( k \) non-empty subsets

Bell Number:

\( B_n = \sum_{k=0}^{n} S(n, k) \) (total partitions of \( n \)-set)

📌 Discrete Probability

Probability of Event:

\( P(A) = \frac{|A|}{|S|} \) (where \( S \) is sample space)

Complement Rule:

\( P(A') = 1 - P(A) \)

Union (Inclusion-exclusion):

\( P(A \cup B) = P(A) + P(B) - P(A \cap B) \)

Conditional Probability:

\( P(A|B) = \frac{P(A \cap B)}{P(B)} \), \( P(B) > 0 \)

Bayes’ Theorem:

\( P(A|B) = \frac{P(B|A) P(A)}{P(B)} \)

Independence:

\( P(A \cap B) = P(A) P(B) \) if \( A \) and \( B \) are independent

Expected Value (Discrete):

\( E(X) = \sum x_i P(X = x_i) \)

Variance (Discrete):

\( Var(X) = E(X^2) - [E(X)]^2 \)

Binomial Probability:

\( P(X = k) = \binom{n}{k} p^k (1-p)^{n-k} \)

Binomial Expected Value:

\( E(X) = np \)

Binomial Variance:

\( Var(X) = np(1-p) \)

📌 Graph Theory

Degree of a Vertex:

\( \deg(v) = \) number of edges incident to \( v \)

Handshaking Lemma:

\( \sum_{v \in V} \deg(v) = 2 |E| \)

Number of Edges in Complete Graph:

\( |E| = \frac{n(n-1)}{2} \) for \( K_n \)

Euler’s Formula (Planar Graph):

\( V - E + F = 2 \) (where \( F \) is number of faces)

Chromatic Number:

\( \chi(G) = \) minimum \( k \) such that \( G \) is \( k \)-colorable

Number of Spanning Trees (Complete Graph):

\( n^{n-2} \) (Cayley’s Formula)

Adjacency Matrix Element:

\( A_{ij} = 1 \) if edge exists, 0 otherwise

Paths of Length \( k \) (Matrix):

\( (A^k)_{ij} = \) number of walks of length \( k \) from \( v_i \) to \( v_j \)

Max Edges in Bipartite Graph:

\( |E| \leq mn \) for \( K_{m,n} \)

Matching Number:

\( \nu(G) = \) size of maximum matching

Vertex Cover Number:

\( \tau(G) = \) size of minimum vertex cover

📌 Recurrence Relations

First-Order Linear Recurrence:

\( a_n = r a_{n-1} + c \), solution: \( a_n = r^n a_0 + c \frac{r^n - 1}{r - 1} \) (\( r \neq 1 \))

Second-Order Homogeneous:

\( a_n = r_1 a_{n-1} + r_2 a_{n-2} \), roots \( \lambda_1, \lambda_2 \): \( a_n = A \lambda_1^n + B \lambda_2^n \)

Repeated Roots:

\( a_n = (A + Bn) \lambda^n \) if \( \lambda_1 = \lambda_2 = \lambda \)

Fibonacci Recurrence:

\( F_n = F_{n-1} + F_{n-2} \), \( F_0 = 0, F_1 = 1 \)

Binet’s Formula:

\( F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}} \), \( \phi = \frac{1 + \sqrt{5}}{2} \)

Characteristic Equation:

\( r^2 - r_1 r - r_2 = 0 \) for \( a_n = r_1 a_{n-1} + r_2 a_{n-2} \)

Nonhomogeneous Solution:

\( a_n = a_n^{(h)} + a_n^{(p)} \) (homogeneous + particular)

Linear Recurrence with Constant:

\( a_n = a_{n-1} + k \), solution: \( a_n = a_0 + nk \)

Tower of Hanoi:

\( T_n = 2 T_{n-1} + 1 \), \( T_n = 2^n - 1 \)

Catalan Recurrence:

\( C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k} \), \( C_0 = 1 \)

📌 Generating Functions

Ordinary Generating Function:

\( G(x) = \sum_{n=0}^{\infty} a_n x^n \)

Geometric Series:

\( \sum_{n=0}^{\infty} r^n x^n = \frac{1}{1 - rx} \), \( |rx| < 1 \)

Arithmetic Series:

\( \sum_{n=0}^{\infty} n x^n = \frac{x}{(1-x)^2} \), \( |x| < 1 \)

Fibonacci Generating Function:

\( G(x) = \frac{x}{1 - x - x^2} \)

Convolution:

\( [x^n] (G(x) H(x)) = \sum_{k=0}^{n} a_k b_{n-k} \)

Exponential Generating Function:

\( E(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} \)

Permutations (Exponential):

\( E(x) = e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!} \)

Catalan Generating Function:

\( C(x) = \frac{1 - \sqrt{1 - 4x}}{2x} \), \( C_n = \frac{1}{n+1} \binom{2n}{n} \)

Partition Generating Function:

\( P(x) = \prod_{k=1}^{\infty} \frac{1}{1 - x^k} \)

Derivative Rule:

\( [x^n] G'(x) = (n+1) a_{n+1} \)

📌 Boolean Algebra

Identity Laws:

\( A \land 1 = A \), \( A \lor 0 = A \)

Complement Laws:

\( A \land \neg A = 0 \), \( A \lor \neg A = 1 \)

Idempotent Laws:

\( A \land A = A \), \( A \lor A = A \)

Absorption Laws:

\( A \land (A \lor B) = A \), \( A \lor (A \land B) = A \)

Distributive Laws:

\( A \land (B \lor C) = (A \land B) \lor (A \land C) \)

\( A \lor (B \land C) = (A \lor B) \land (A \lor C) \)

De Morgan’s Laws:

\( \neg (A \land B) = \neg A \lor \neg B \)

\( \neg (A \lor B) = \neg A \land \neg B \)

Associative Laws:

\( (A \land B) \land C = A \land (B \land C) \)

\( (A \lor B) \lor C = A \lor (B \lor C) \)

📌 Algorithms and Complexity

Time Complexity (Linear):

\( O(n) \) for linear search

Time Complexity (Binary Search):

\( O(\log n) \)

Time Complexity (Bubble Sort):

\( O(n^2) \)

Time Complexity (Merge Sort):

\( O(n \log n) \)

Master Theorem:

\( T(n) = a T(n/b) + f(n) \), then \( T(n) = O(n^{\log_b a}) \) if \( f(n) = O(n^c), c < \log_b a \)

Space Complexity (Recursion):

\( O(\log n) \) for balanced binary recursion

Euclidean Algorithm (GCD):

\( \gcd(a, b) = \gcd(b, a \mod b) \), \( O(\log \min(a, b)) \)

Fast Exponentiation:

\( a^n = (a^{n/2})^2 \) if \( n \) even, \( a \cdot a^{n-1} \) if odd, \( O(\log n) \)

Knapsack Problem (Dynamic Programming):

\( V[i, w] = \max(V[i-1, w], v_i + V[i-1, w - w_i]) \)

Shortest Path (Dijkstra):

\( O(|V|^2) \) or \( O(|E| + |V| \log |V|) \) with heap