Discrete Mathematics — Foundations

Job: Supply counting, discrete structures, and proof patterns used across combinatorics, graph theory, algorithms, and Boolean algebra — at research-usable density.

Core

Sets, functions, and pigeonhole

Finite cardinality \(|A|\); injections, surjections, bijections. Pigeonhole: \(f:A\to B\) with \(|A|>|B|\) \(\Rightarrow\) not injective. Strengthened: if \(|A|>k|B|\), some fiber has size \(>k\). Schröder–Bernstein: injections both ways \(\Rightarrow\) bijection (infinite sets).

Induction and well-founded recursion

Ordinary induction on \(\mathbb{N}\); strong induction; structural induction on recursively defined objects (trees, formulas, lists). Well-founded induction on well-orders / Noetherian induction. Minimal counterexample proofs are strong induction in disguise.

Relations and orders

Equivalence relations \(\Leftrightarrow\) partitions. Partial orders; total orders; well-orders. Topological sort on DAGs = linear extensions. Dilworth / Mirsky (pointer): chain/antichain decompositions in posets.

Basic counting

$$ |A\cup B|=|A|+|B|-|A\cap B|,\qquad |A\times B|=|A||B|, $$ \(k\)-permutations \(P(n,k)=n!/(n-k)!\), combinations \(C(n,k)=\binom{n}{k}\). Binomial theorem \((x+y)^n=\sum\binom{n}{k}x^ky^{n-k}\). Multinomial \(\binom{n}{n_1,\ldots,n_k}=n!/(n_1!\cdots n_k!)\).

Stars and bars: nonnegative solutions to \(x_1+\cdots+x_k=n\) number \(\binom{n+k-1}{k-1}\).

Inclusion–exclusion and Möbius

$$ \Bigl|\bigcup_{i=1}^n A_i\Bigr|=\sum|A_i|-\sum|A_i\cap A_j|+\cdots+(-1)^{n+1}|A_1\cap\cdots\cap A_n|. $$ Surjections \([n]\to[k]\): \(k!\,S(n,k)=\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^n\). Poset Möbius inversion generalizes inclusion–exclusion (incidence algebra).

Generating functions

Ordinary \(A(x)=\sum a_n x^n\) (unlabeled / combinations); exponential \(A(x)=\sum a_n x^n/n!\) (labeled). Convolution \(\leftrightarrow\) product. Rational generating functions \(\leftrightarrow\) linear recurrences with const coeffs. Catalan \(C_n=\frac1{n+1}\binom{2n}{n}\): dyck words, binary trees, noncrossing partitions — \(C(x)=(1-\sqrt{1-4x})/(2x)\).

Asymptotics

Stirling \(n!\sim\sqrt{2\pi n}\,(n/e)^n\); \(\binom{2n}{n}\sim 4^n/\sqrt{\pi n}\). Singularity analysis (Flajolet–Sedgewick): location/type of dominant singularities of \(A(x)\) \(\Rightarrow\) \([x^n]A(x)\) asymptotics.

Graphs (orientation)

\(G=(V,E)\); degree sum \(2|E|\); trees \(\Leftrightarrow\) connected \(|E|=|V|-1\); Euler circuits (all degrees even, connected); Hamilton NP-hard in general. Adjacency matrix spectrum encodes walks \(A^k_{ij}\). Planarity: Euler \(V-E+F=2\) for connected plane graphs.

Boolean algebra as free algebra on generators; DNF/CNF; SAT complexity. Propositional tautologies vs combinatorial identities (e.g. binomial via subsets).

Uniform measure on finite \(\Omega\); counting \(\Leftrightarrow\) probability when \(|\Omega|<\infty\). Linearity of expectation without independence; alteration / Lovász Local Lemma for existence (pointer to probabilistic method).

Tool Use
Pigeonhole existence of collisions / monochromatic structures
Inclusion–exclusion derangements, surjections, sieve
Double counting handshaking; combinatorial identities
Generating functions recurrences; asymptotic enumeration
Probabilistic method existence without construction

See it

Derangements. \(!n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\sim n!/e\). Inclusion–exclusion on fixed-point sets; hat-check problem. Exponential GF \(\sum !n\,x^n/n!=e^{-x}/(1-x)\).

Number of surjections: \(k!\,S(n,k)=\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^n\). Stirling second kind \(S(n,k)\) counts partitions of \([n]\) into \(k\) nonempty unlabeled blocks.

Check

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

Right side: subsets of \([n]\). Left: partition by size \(k\). Algebraically: \((1+1)^n\).

Why does ordinary induction fail for some statements true on all \(n\ge n_0\) without a correct base?

Base case is necessary: \(P(n)\Rightarrow P(n+1)\) for all \(n\) with false \(P(0)\) proves nothing. Strong induction needs all smaller instances available.

Derive the OGF for Fibonacci \(F_0=0,F_1=1,F_{n}=F_{n-1}+F_{n-2}\).

\(F(x)=\sum F_n x^n=x/(1-x-x^2)\) from the recurrence and initial conditions (standard generatingfunctionology).

Pitfalls

  • Confusing \(P(n,k)\) with \(\binom{n}{k}\); ordered vs unordered samples.
  • Generating functions are formal power series first; analytic convergence optional until singularity analysis.
  • Infinite discrete structures: cardinals vs asymptotic enumeration — different toolkits.
  • “Prove by induction” without identifying the inductive predicate precisely.
  • Graph algorithms: “connected” vs “strongly connected” (directed).

Refs

Stanley, Enumerative Combinatorics I; van Lint–Wilson; Rosen (desk ref); Flajolet–Sedgewick; Alon–Spencer (Probabilistic Method); Diestel (graphs).

Next

Combinatorics · Graph theory · Boolean algebra · Logic · Statistics