Discrete Math

Finite counting, recurrence thinking, graph structure, discrete probability, and number-theoretic tools for CS, theory, and mathematical modeling.
Modified

April 26, 2026

Keywords

discrete math, combinatorics, recurrence, graphs, modular arithmetic

1 Why This Module Matters

Discrete math is where the site learns to reason cleanly about finite structure.

This is the part of the foundation stack where questions start looking like:

  • how many objects are possible?
  • how fast does a recurrence grow?
  • what structure does a graph force?
  • what happens when probability lives on a finite set?
  • how do divisibility and modular arithmetic constrain a problem?

Without this layer, a large part of algorithms, theoretical CS, coding theory, combinatorial probability, and many proof-heavy pages feel like isolated tricks instead of one connected toolkit.

Prerequisites Proofs and Logic are the strongest live prerequisites, especially for precise statement reading and structured case analysis.

Unlocks Algorithms, graph reasoning, finite probability, asymptotics, information theory, and later stochastic-process viewpoints

Research Use Combinatorial arguments, asymptotic counting, graph structure, collision and hashing intuition, modular constraints

2 First Pass Through This Module

The first-pass spine is:

  1. Counting and Combinatorics
  2. Recurrences and Asymptotics
  3. Graphs and Trees
  4. Discrete Probability Bridge
  5. Number Theory Basics

This now gives the module a complete first-pass spine through finite counting, asymptotic growth, graph structure, finite probability, and modular reasoning.

3 How To Use This Module

The best opening path is:

  1. start with Counting and Combinatorics
  2. continue to Recurrences and Asymptotics
  3. continue to Graphs and Trees
  4. continue to Discrete Probability Bridge
  5. finish with Number Theory Basics
  6. keep Proofs and Logic nearby for case splits, negation, and exact statement structure
  7. move into Probability once the counting language turns into random variables and distributions

The design goal is to make finite structure feel organized before the module branches into recurrences, graphs, discrete probability, and modular arithmetic.

4 Core Concepts

  • Counting and Combinatorics: the opening page that builds sum and product rules, permutations, combinations, pigeonhole intuition, and inclusion-exclusion habits.
  • Recurrences and Asymptotics: the second live page that builds recursive definitions, growth rates, and the first algorithmic asymptotic lens.
  • Graphs and Trees: the third live page that builds vertices, edges, paths, cycles, trees, and connectivity.
  • Discrete Probability Bridge: the fourth live page that turns counting into finite probability modeling through sample spaces, indicators, and expectation.
  • Number Theory Basics: the closing first-pass page for divisibility, primes, gcd, Euclid, and modular arithmetic.

5 After This First Pass

The strongest adjacent live next moves are:

6 Applications

6.1 Algorithms And Case Analysis

Discrete math gives the language for finite search spaces, recursion patterns, and counting-based bounds.

6.2 Finite Probability And Randomized Reasoning

Many probability arguments on finite spaces begin as counting arguments in disguise.

6.3 Theoretical CS And Information

Graphs, asymptotics, counting, and modular reasoning keep reappearing in coding, communication, randomized algorithms, and combinatorial proofs.

7 Go Deeper By Topic

7.1 Counting And Combinatorics

Start with Counting and Combinatorics.

If you want one strong reinforcement path after that page:

  • revisit Statements and Quantifiers
  • then work a few finite counting problems where you must decide whether order matters, whether repetition is allowed, and whether complement counting is cleaner

7.2 Recurrences And Asymptotics

Continue to Recurrences and Asymptotics.

If you want one strong reinforcement path after that page:

  • revisit Induction
  • then solve one recurrence by repeated expansion and explain the asymptotic growth class in words, not only symbols

7.3 Graphs And Trees

Continue to Graphs and Trees.

If you want one strong reinforcement path after that page:

  • revisit Sets, Functions, Relations
  • then take one small graph and explicitly list its degrees, a path between two vertices, whether a cycle exists, and whether a spanning tree is already present

7.4 Discrete Probability Bridge

Continue to Discrete Probability Bridge.

If you want one strong reinforcement path after that page:

  • revisit Counting and Combinatorics
  • then solve one finite probability problem twice: once by raw case counting, and once by indicators plus linearity of expectation

7.5 Number Theory Basics

Finish with Number Theory Basics.

If you want one strong reinforcement path after that page:

  • revisit Induction
  • then compute one gcd by Euclid and solve one small congruence to connect divisibility and modular arithmetic in the same exercise

8 Optional Deeper Reading After First Pass

Now that the full discrete-math first-pass spine is live, the best deeper pass is through official course materials:

9 Sources and Further Reading

Sources checked online on 2026-04-25:

  • MIT 6.1200J course page
  • MIT 6.042J course page
  • Stanford CS103 course page
  • Stanford CS103 counting lecture
  • MIT 6.1200J lecture 08
  • CMU 15-151 course page
Back to top