MATH3250
Discrete Mathematics
Proof methods, counting, recurrences and generating functions, integer algorithms, graph methods, partial orders and algorithm design, with proofs, worked examples and solved exercises.
Your progress
0/ 26 sections marked complete
Next section: 1.1 Quantifiers, induction and counterexamples
Completion marks are saved in this browser.
This course in the web
In the MATH3250 notes
- Theorem cards
- 77
- Definitions
- 39
- Counterexamples
- 27
- Concept lenses
- 25
- Histories of ideas
- 1
- Proof X-rays
- 27
Sections with a history of an idea
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 26 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 77 · Definitions 39 · Counterexamples 27 · Concept lenses 25 · Histories of ideas 1 · Proof X-rays 27
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 26 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 1 · 2 sections
Proof methods
Translate precise statements, negate quantifiers, and justify ordinary and strong induction through least counterexamples.
Theorems 5 · Definitions 3Counterexamples 2Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Quantifiers, induction and counterexamples
Translate precise statements, negate quantifiers, and justify ordinary and strong induction through least counterexamples.
- 1.2
Relations, equivalence classes and well-defined maps
Prove the correspondence between equivalence relations and partitions, understand function fibers, and test whether a formula descends to equivalence classes.
Chapter 2 · 11 sections
Counting
Choose the correct counting model, prove inclusion–exclusion, and count derangements and surjections.
Theorems 37 · Definitions 15Counterexamples 13Lenses 11Proof X-rays 11
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Bijections, inclusion–exclusion and surjections
Choose the correct counting model, prove inclusion–exclusion, and count derangements and surjections.
- 2.2
Monotone subsequences and the pigeonhole principle
Use paired subsequence lengths to prove a sharp finite bound.
- 2.3
Dependency graphs and the local lemma
Prove the finite local lemma and apply it to sparse-overlap constraints.
- 2.4
Counting choices, cases and fibers
A foundational supplement on sum and product rules and fiber-counting, with methods related to unit 2.1.
- 2.5
Binomial Coefficients and Combinatorial Identities
Subset-counting definitions of binomial coefficients, the factorial formula, symmetry, Pascal's rule, the binomial theorem in commutative rings, and identities proved by bijections and double counting.
- 2.6
The Pigeonhole Principle and Monotone Subsequences
Prove sharp occupancy bounds, find divisible consecutive sums through prefix residues, and derive the sharp increasing-or-decreasing subsequence theorem by endpoint labels.
- 2.7
Set partitions, Stirling numbers and Bell totals
Count partitions and permutation cycles, prove their recurrences and generating functions, and explain the inverse Stirling changes between powers and falling factorials.
- 2.8
Reflection, ballot paths and Catalan structures
Prove weak and strict ballot counts by an invertible reflection, derive the Catalan closed form and formal quadratic generating function, and construct ordered-tree and polygon-triangulation bijections.
- 2.9
Integer partitions, Ferrers conjugation and Durfee squares
Prove partition conjugation, formal generating products, odd/distinct-part equivalence and Durfee decomposition, with exact-part restrictions and a justified coefficient-table algorithm.
- 2.10
Group actions, necklaces and primitive periods
Prove orbit counting by stabilizers, derive rotation and reflection formulas, and connect primitive word periods to Möbius inversion without dividing by a nonuniform orbit size.
- 2.11
Ramsey numbers and their basic bounds
Prove Ramsey's theorem for two colors by induction, derive the binomial upper bound, determine R(3,3)=6, and prove a counting lower bound for diagonal Ramsey numbers.
Chapter 3 · 2 sections
Recurrences and generating functions
Derive recurrence relations from combinatorial decompositions and solve them with formal power series.
Theorems 5 · Definitions 3Counterexamples 2Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Recurrences and formal generating functions
Derive recurrence relations from combinatorial decompositions and solve them with formal power series.
- 3.6
Dynamic programming: choices, order and reconstruction
Derive exact 0–1 knapsack and minimum-coin recurrences, prove their evaluation orders and recover solutions.
Chapter 4 · 2 sections
Integer algorithms
Prove correctness and termination of two integer algorithms, keeping arithmetic-operation counts distinct from bit complexity.
Theorems 5 · Definitions 3Counterexamples 2Lenses 2History 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Euclidean invariants and binary exponentiation
Prove correctness and termination of two integer algorithms, keeping arithmetic-operation counts distinct from bit complexity.
- 4.2
Linear congruences and compatible remainder systems
Prove complete linear-congruence solution classes, a constructive noncoprime CRT merge and the pairwise compatibility criterion, with exact representatives, periods and modulus-one boundaries.
Chapter 5 · 5 sections
Graph methods
Prove tree characterizations and shortest-path correctness of breadth-first search on finite unweighted graphs.
Theorems 14 · Definitions 8Counterexamples 4Lenses 5Proof X-rays 6
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Trees and breadth-first search
Prove tree characterizations and shortest-path correctness of breadth-first search on finite unweighted graphs.
- 5.2
Euler trails and universal cyclic words
Prove directed Euler trail criteria and a linear graph-operation splice algorithm, then construct optimal universal cyclic and linear words through overlap graphs with exact boundary and output-size conditions.
- 5.3
Vertex coloring and greedy bounds
Use proper colorings to model conflicts, prove a greedy bound and recognize bipartite graphs.
- 5.4
Minimum spanning forests and greedy exchange
Prove cut and cycle exchange rules, Kruskal and Prim, and an independently checkable optimality condition.
- 5.5
Nonnegative shortest paths and distance certificates
Prove Dijkstra's label-setting rule, recover shortest paths, and verify distances independently with edge inequalities and an acyclic predecessor certificate.
Chapter 6 · 3 sections
Partial orders
Organize a finite partial order, invert sums over its lower sets, and derive Boolean and divisor inversion from one incidence-algebra argument.
Theorems 8 · Definitions 6Counterexamples 3Lenses 3Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Partial orders, linear extensions and Möbius inversion
Organize a finite partial order, invert sums over its lower sets, and derive Boolean and divisor inversion from one incidence-algebra argument.
- 6.2
Chains, antichains and Dilworth's theorem
Prove finite chain–antichain partition theorems through bipartite matching, construct optimal certificates, and distinguish the comparison graph from a Hasse diagram.
- 6.3
Sperner's theorem, the LYM inequality and subset shadows
Count maximal Boolean chains to prove the LYM inequality and Sperner's sharp antichain bound, then analyze shadows and equality at the middle levels.
Chapter 8 · 1 section
Algorithm design
Prove safe algorithmic choices using exchange and invariants.
Theorems 3 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Greedy choice, exchange and interval scheduling
Prove earliest-finish interval scheduling by exchange and a stays-ahead invariant.