Combinatorics Tutorial
Learn Combinatorics step by step: 36 lessons in 9 chapters with examples, quizzes, diagrams and projects.
Start learning →
of lessons completed
Getting Started
- What Is Combinatorics? Meet combinatorics, the mathematics of counting. Learn the four basic questions, why counting gets hard fast, and how Python can check your answers.
- Sets and Counting Notation Learn the set language of combinatorics: elements, subsets, cardinality, union, intersection, Cartesian product and the symbols you will see in every counting formula.
- Counting by Brute Force with Python Use itertools to enumerate products, permutations, combinations and subsets, and learn when brute force is a trustworthy checker for your counting formulas.
- Bijections and Double Counting Learn two core proof ideas of counting: matching sets one-to-one with a bijection, and counting the same set in two ways, with handshake and binary string examples.
Counting Principles
- The Sum Rule Learn the sum rule of counting: when a task can be done in one of several disjoint ways, add the counts. Includes casework, common mistakes and Python checks.
- The Product Rule Learn the product rule: when a task has several independent steps, multiply the number of choices. Covers tree diagrams, dependent steps, licence plates and Python checks.
- Complement Counting and Casework Count hard sets by counting what you do not want: the complement rule, at-least-one problems, and when to split into cases. Worked examples with Python checks.
- Counting Functions, Subsets and the Division Rule Count functions between finite sets, injective maps, and subsets with the product rule, then learn the division rule for undoing overcounting. Python checks included.
Permutations and Combinations
- Permutations and Factorials Count the ways to arrange n distinct objects in order: n factorial. Learn why factorials grow so fast, how to generate permutations, and how to handle restrictions.
- Partial Permutations and Circular Arrangements Count ordered selections of k items from n with P(n,k), then arrangements around a circle and bracelets. Includes Python checks for every formula.
- Combinations and Binomial Coefficients Learn combinations, the number of ways to choose k items from n when order does not matter. Derive n choose k, its symmetry, and solve committee and hand problems.
- Pascal's Triangle and the Binomial Theorem Build Pascal's triangle, prove Pascal's rule by counting, expand (x+y)^n with the binomial theorem and discover identities such as the hockey stick and Vandermonde.
- Permutations with Repeated Items (Multinomials) Count distinct arrangements of words with repeated letters, split people into labelled groups and use multinomial coefficients, verified with Python.
- Stars and Bars (Combinations with Repetition) Count ways to distribute identical items into boxes and choose with repetition using the stars and bars method, with lower bounds and Python verification.
Inclusion-Exclusion
- Inclusion-Exclusion for Two and Three Sets Count the union of overlapping sets without double counting. Learn the two-set and three-set inclusion-exclusion formulas, Venn diagrams and worked Python examples.
- The General Inclusion-Exclusion Formula State and prove the general inclusion-exclusion formula for n sets, implement it in Python, and use it to count bounded solutions and numbers coprime to a given value.
- Derangements and the Hat-Check Problem Count permutations with no fixed points using inclusion-exclusion, the recurrence D(n) = (n-1)(D(n-1)+D(n-2)) and the 1/e limit, verified step by step in Python.
- Surjections and Euler's Totient Use inclusion-exclusion to count onto functions and to derive Euler's totient formula phi(n), with Python checks against brute force.
Recurrences and Generating Functions
- Recurrence Relations Learn how to count by building a recurrence relation: set up a_n from smaller cases, check it by brute force, and meet Tower of Hanoi, tilings and line regions.
- Solving Linear Recurrences Solve linear recurrences with constant coefficients using the characteristic equation: distinct and repeated roots, Binet's formula, sympy rsolve and matrix powers.
- Generating Functions Learn ordinary generating functions: encode a counting sequence as a power series, multiply series to combine choices, and solve dice, coin change and Fibonacci problems.
- Exponential Generating Functions Use exponential generating functions to count words and arrangements where order matters: constraints per letter, derangements, Bell numbers, verified with sympy.
Partitions and Catalan Numbers
- Integer Partitions Count integer partitions: generate every partition of n, compute p(n) with dynamic programming, and compare partitions into distinct, odd and bounded parts.
- Ferrers Diagrams and Pentagonal Numbers Draw partitions as Ferrers diagrams, flip them to get conjugates, prove partition identities by bijection, and compute p(n) fast with Euler's pentagonal number theorem.
- Catalan Numbers Learn the Catalan numbers 1, 1, 2, 5, 14, 42: derive the recurrence, use the binomial formula, count balanced parentheses and draw Dyck paths in Python.
- Catalan Structures See the Catalan numbers in lattice paths, polygon triangulations, binary trees, stack-sortable permutations and the ballot problem, with the reflection principle and code.
Pigeonhole and Ramsey
- The Pigeonhole Principle Learn the pigeonhole principle and its generalized form, then prove classic results: divisible pairs among n+1 numbers and subset sums divisible by n, checked in Python.
- Pigeonhole Applications Apply the pigeonhole principle to the ErdΕsβSzekeres monotone subsequence theorem and Dirichlet's rational approximation, with exhaustive and numeric checks in Python.
- Ramsey Theory Meet Ramsey theory: prove R(3,3)=6 by exhaustive search over edge colorings, compute Schur numbers by backtracking, and see why complete disorder is impossible.
Applications
- Burnside's Lemma Count objects up to symmetry with Burnside's lemma: necklaces, bracelets and cube colorings, with the group action explained and every count checked by brute force.
- Stirling Numbers Understand Stirling numbers: partitions of a set into blocks (second kind), permutations by cycles (first kind), surjections and Bell numbers, with recurrences and checks.
- Combinatorics in Algorithms Put counting to work in code: compute binomials modulo a prime with factorial tables and Lucas' theorem, rank and unrank permutations, next permutation and grid-path DP.
Projects and Practice
- Project: A Counting Library Build a small, tested counting library in Python: permutations, combinations, multisets, derangements, Stirling, Bell, Catalan and partitions, cross-checked by brute force.
- Project: Poker, Lottery and Birthdays Apply counting to real probabilities: count all poker hands exactly, compute lottery match odds with hypergeometric counting, and compare the birthday paradox with a simulation.
- Practice Set: Counting Problems Ten counting problems with worked formulas and brute-force checks: license plates, MISSISSIPPI, committees, stars and bars, circular seating, inclusion-exclusion and more.
- Practice Set: Advanced Counting Six advanced counting problems solved with partitions, generating functions, Stirling numbers, recurrences and Burnside, plus plots of partition and Catalan growth.