Combinatorics is the art of counting: how many arrangements, selections or structures meet a condition, and whether one exists at all. In computing it tells you how big a search space is, how many cases a test needs, and how an algorithm's work grows. It also gives the tools behind hashing, coding and probability.
Key concepts
- Counting principles: the rules of sum and product, permutations and combinations, and binomial coefficients.
- Inclusion-exclusion: counting a union by adding and subtracting overlaps.
- Pigeonhole principle: with more items than boxes, some box holds two; it proves existence without construction.
- Recurrences and generating functions: counting problems turned into equations on sequences.
- Double counting and bijections: counting one set in two ways, or matching it to a set that is easier to count.
Vocabulary
- Permutation and combination: an ordered or an unordered selection of items.
- Binomial coefficient: the number of ways to choose k items from n.
- Catalan numbers: a sequence counting balanced brackets, binary trees and many other structures.
- Partition: a way to split a set, or write a number as a sum.
What to study, in order
- Permutations, combinations and the binomial theorem, with small examples checked by brute force.
- Write a program that enumerates all subsets or permutations, and compare its count with the formula.
- Use inclusion-exclusion and the pigeonhole principle on puzzles.
- Solve counting problems with recurrences and dynamic programming.
- Meet generating functions and use them to solve a recurrence in closed form.
Related tags
#discrete-math #probability #graph-theory #algorithms #puzzles