Skip to content

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.

7 chapters · 26 sectionsEN · 繁 · 简
My course notes

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.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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.1

    Quantifiers, induction and counterexamples

    Translate precise statements, negate quantifiers, and justify ordinary and strong induction through least counterexamples.

  2. 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

  1. 2.1

    Bijections, inclusion–exclusion and surjections

    Choose the correct counting model, prove inclusion–exclusion, and count derangements and surjections.

  2. 2.2

    Monotone subsequences and the pigeonhole principle

    Use paired subsequence lengths to prove a sharp finite bound.

  3. 2.3

    Dependency graphs and the local lemma

    Prove the finite local lemma and apply it to sparse-overlap constraints.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. 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

  1. 3.1

    Recurrences and formal generating functions

    Derive recurrence relations from combinatorial decompositions and solve them with formal power series.

  2. 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

  1. 4.1

    Euclidean invariants and binary exponentiation

    Prove correctness and termination of two integer algorithms, keeping arithmetic-operation counts distinct from bit complexity.

  2. 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

  1. 5.1

    Trees and breadth-first search

    Prove tree characterizations and shortest-path correctness of breadth-first search on finite unweighted graphs.

  2. 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.

  3. 5.3

    Vertex coloring and greedy bounds

    Use proper colorings to model conflicts, prove a greedy bound and recognize bipartite graphs.

  4. 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.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

  1. 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.

  2. 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.

  3. 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

  1. 8.1

    Greedy choice, exchange and interval scheduling

    Prove earliest-finish interval scheduling by exchange and a stays-ahead invariant.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details