Discrete Mathematics

Formulas

Set theory is the universal language of mathematics. All mathematical objects—numbers, functions, structures—can be defined through sets.

Georg Cantor created set theory in the 1870s, despite opposition from conservative mathematicians. David Hilbert called his theory "a paradise from which we shall not be driven."

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\}$. Difference: $A \setminus B = \{x : x \in A,\ x \notin B\}$. Symmetric difference: $A \bigtriangleup B = (A \setminus B) \cup (B \setminus A)$. Complement: $A^c = U \setminus A...

De Morgan's Laws: $(A \cup B)^c = A^c \cap B^c$; $(A \cap B)^{\complement} = A^c \cup B^c$.

A binary relation $R$ on $A$ is a subset of $A \times A$. We write $aRb$ or $(a, b) \in R$.

Equivalence class: $[a] = \{b: b \sim a\}$. The classes form a partition of $A$ (pairwise disjoint, cover $A$).

Examples: Equality modulo $n$: $a \sim b \iff n \mid (a-b)$. Classes: $\{0, n, 2n, \ldots\}$, $\{1, n+1, 2n+1, \ldots\}$, ..., $\{n-1, 2n-1, \ldots\}$.

Partial order (poset): reflexive, antisymmetric, transitive. Example: divisibility on $\mathbb{N}$.

Formulas

A partially ordered set L is a lattice if for any two elements a, b there exist:

Examples: (2^A, ⊆) — the lattice of subsets. (ℕ, |) — the lattice under divisibility: a∨b = LCM(a,b), a∧b = GCD(a,b). Subspaces in a vector space.

A distributive complemented lattice: the distributive laws hold, $a\land(b\lor c) = (a\land b)\lor(a\land c)$, and complement $a^c$ such that $a\land a^c = 0$, $a\lor a^c = 1$.

Stone's Theorem: Every finite Boolean algebra is isomorphic to the power set algebra of some finite set. The size is a power of two.

Formulas

SDNF (perfect disjunctive normal form): disjunction of minterms. A minterm is the conjunction of all variables (with or without negations) corresponding to a row of the truth table with f=1.

SCNF (perfect conjunctive normal form): conjunction of maxterms (disjunctions for rows with f=0).

A closed class of functions is a set F closed under superposition (substitution, identification of variables).

Post's theorem: A system F of functions is complete if and only if it is not contained in any of the five classes.

Definitions

Multiset

— a collection with repetitions. The number of $k$-element submultisets of an $n$-element set: $C(n+k-1, k)$ = “stars and bars”. Interpretation: distribute $k$ indistinguishable balls into $n$ distinguishable boxes. Example: the number of solutions ...

Formulas

Sum Rule: if A and B are disjoint, $|A \cup B| = |A| + |B|$. Product Rule: sequential choices $k_1, k_2, ...$: $k_1 \cdot k_2 \cdot ...$

Arrangements $A(n, k) = \frac{n!}{(n - k)!}$ (ordered selection of $k$ out of $n$). Combinations $C(n, k) = \frac{n!}{k!(n-k)!}$ (unordered selection).

$|A_1 \cup A_2 \cup ... \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - ...$

Number of derangements (permutations with no fixed points): $ D(n) = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \approx \frac{n!}{e} $

Formulas

A sequence is defined recurrently: $a(n)$ is expressed in terms of $a(n-1), ..., a(n-k)$.

Characteristic equation: $x^2 = x + 1$. Roots: $\varphi = \frac{1+\sqrt{5}}{2}$ (golden ratio), $\psi = \frac{1-\sqrt{5}}{2}$.

1. Characteristic equation: $x^k = c_1x^{k-1} + \ldots + c_k$. 2. If the roots $x_1, ..., x_k$ are distinct: $a(n) = \alpha_1 x_1^n + \ldots + \alpha_k x_k^n$. 3. Coefficients are obtained from initial conditions.

For repeated roots $x_i$ of multiplicity $m_i$: the term $x_i^n(\alpha_0 + \alpha_1 n + \ldots + \alpha_{m_i-1} n^{m_i-1})$ appears.

Definitions

Tree

— a connected graph without cycles. Equivalent conditions (for n vertices):

Formulas

Graph G = (V, E): V is the set of vertices, E is the set of edges (pairs of vertices).

Degree of a vertex deg(v) — the number of edges incident to v. Handshaking Lemma: Σ deg(v) = 2|E| (each edge contributes 2 to the sum of degrees). Corollary: the number of vertices of odd degree is even.

Walk: a sequence of vertices v₀, v₁, ..., vₖ with edges v_{i-1}v_i. Path: a walk with no repeated vertices.

Shortest paths: Dijkstra's algorithm (non-negative weights) O((V+E)log V); Bellman–Ford (allows negatives) O(VE); Floyd–Warshall (all pairs) O(V³).

Formulas

A graph is planar if it can be drawn on the plane without any edge crossings.

Euler's formula: For a connected planar graph, $V - E + F = 2$, where $F$ is the number of faces (including the outer face).

Corollary: $E \le 3V - 6$ (for $V \ge 3$). If there are no triangles: $E \le 2V - 4$.

Graph $K_5$ (complete graph on 5 vertices): $E=10$, $3V-6=9$. Therefore, $K_5$ is non-planar.

Definitions

Eulerian path

— a route that traverses each edge exactly once.

Hamiltonian path

— a path passing through every vertex exactly once.

G(n,p)

— random graph on n vertices, each edge independently with probability p. Threshold theory: if p < (1−ε)ln(n)/n the graph is almost surely not connected, if p > (1+ε)ln(n)/n — almost surely connected. Triangle threshold: p ~ n^{−1}. Hamiltonian cycl...

Formulas

Euler's Theorem (1736): A graph has an Eulerian cycle if and only if it is connected and all vertices have even degree.

An Eulerian path (not cycle) exists ⟺ the graph is connected and exactly 2 vertices have odd degree.

The Königsberg bridges problem: seven bridges over a river — is it possible to cross each one exactly once? Four islands, all with odd degree → no.

Unlike Eulerian: there is no simple criterion! The problem of finding a Hamiltonian cycle is NP-complete.

Formulas

Combinatorics answers the question: "How many?" — how many different objects of a given type exist. This is fundamental for algorithm theory, cryptography, and statistics.

The number of surjective functions from an n-element set to an m-element set (m ≤ n): $S(n,m) = \sum_{k=0}^m (-1)^k C(m,k)(m-k)^n$.

Stirling numbers of the second kind $S(n,k)$ denote the number of ways to partition an n-element set into k non-empty subsets. Recurrence: $S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$.

A partition of a number $n$ is a way of representing $n$ as a sum of natural numbers (without regard to order).

Formulas

Number of partitions of the number n into parts 1,2,3,...: ∏ₖ₌₁^∞ 1/(1−xᵏ) = Σₙ p(n)xⁿ.

Number of partitions into odd parts = number of partitions into distinct parts (remarkable Euler’s identity).

F(n) (Fibonacci numbers) → f(x) = x/(1−x−x²) = x/((1−φx)(1−ψx)). Decomposition into partial fractions → Binet’s formula.

Saddle point method (Laplace): for the coefficient [xⁿ]f(x) at large n — asymptotics via the saddle point of f.

Extremal combinatorics: how large or small can an object with given properties be?

Turán's Theorem: The maximum number of edges in a $K_{r+1}$-free graph on $n$ vertices: $e \leq (1 - 1/r) \cdot n^2/2$. Achieved on the complete $r$-partite Turán graph $T(n, r)$.

Erdős's Distinct Distances Problem: $n$ points in the plane determine at least $c\sqrt{n}$ distinct distances.

If $n$ objects are placed into $m$ boxes and $n > m$, then some box contains at least 2 objects.

Formulas

DFA = (Q, Σ, δ, q₀, F): Q — the set of states, Σ — the alphabet, δ: Q×Σ → Q — the transition function, q₀ — the initial state, F ⊆ Q — accepting states.

Example: DFA for binary strings divisible by 3: states — residues {0, 1, 2}. q₀ = F = {0}. δ(q, 0) = 2q mod 3, δ(q, 1) = (2q+1) mod 3.

Theorem (Rabin–Scott): DFA and NFA are equivalent in recognized languages (subset construction).

Kleene’s Theorem: A language is regular ⟺ recognized by a DFA ⟺ defined by a regular expression.

Formulas

A context-free grammar G = (V, Σ, R, S): V — nonterminals, Σ — terminals, R — rules of the form A → α (A∈V, α∈(V∪Σ)*), S — start nonterminal.

Chomsky normal form: A → BC or A → a. Every CFG is equivalent to a grammar in CNF.

PDA = (Q, Σ, Γ, δ, q₀, Z₀, F): a stack (pushdown store) with alphabet Γ is added.

CFLs are closed under: union, concatenation, Kleene star. Not closed under: intersection, complement (in general).

Formulas

TM = (Q, Σ, Γ, δ, q₀, q_accept, q_reject): Q — states, Σ — input alphabet, Γ — tape alphabet (Σ ⊆ Γ), δ: Q×Γ → Q×Γ×{L,R} — transition function. Infinite tape, read/write head.

A TM is a theoretical model of a computer. The Church–Turing thesis: anything that can be computed intuitively can be computed by a Turing machine.

NP: problems whose solutions can be verified in polynomial time. Equivalently: solvable by a nondeterministic TM in polynomial time.

NP-complete problems: every problem in NP is polynomial-time reducible to them. SAT (Cook, 1971), Clique, Coloring, TSP,...