Combinatorics is the branch of mathematics concerned with counting: how many ways can a set of objects be arranged, selected, or combined? Despite sounding simple, careful combinatorial counting underlies probability theory, cryptography, computer algorithm analysis, and the design of efficient error-correcting codes — and some seemingly simple counting questions turn out to be extraordinarily subtle.
How many different ways can you arrange 5 books on a shelf? How many possible 5-card poker hands exist? How many different routes can you take through a city grid? These are all combinatorics questions — problems about counting the number of ways something can happen, without necessarily needing to actually list every single possibility out by hand.
A permutation counts arrangements where order matters (first place, second place, third place in a race). A combination counts selections where order doesn't matter (choosing a committee of 3 people from a group — it doesn't matter in what order you pick them). This distinction — does order matter or not? — is the single most important first question in almost any combinatorics problem.
The number of ways to arrange n distinct objects in order is n! = n×(n−1)×(n−2)×...×2×1 (with 0!=1 by convention). The number of ways to arrange just k objects chosen from n is the permutation formula:
The number of ways to choose k objects from n, without regard to order, is:
often written as "n choose k" or (n k), and known as the binomial coefficient because these same numbers appear as the coefficients when expanding (x+y)ⁿ via the binomial theorem.
The binomial coefficients form Pascal's Triangle, where each entry is the sum of the two entries diagonally above it. This same triangular pattern of numbers was independently discovered across multiple cultures — appearing in Chinese mathematics (Yang Hui, 1261 CE), Persian/Islamic mathematics (Al-Karaji, c. 1000 CE), and Indian mathematics (Piṅgala's work on Sanskrit prosody, centuries earlier) — well before Pascal's own 17th-century European treatment, from which it nonetheless popularly and conventionally takes its Western name.
If you place more than n items into n containers, at least one container must hold more than one item. This almost embarrassingly obvious-sounding statement is a surprisingly powerful proof technique: it can be used, for example, to prove that among any 367 people, at least two must share the same birthday (since there are only 366 possible birthdays including leap years) — and, in more sophisticated applications, to prove much deeper and less obvious results throughout number theory and combinatorics.
If one choice can be made in m ways, and a second, independent choice can then be made in n ways, the two choices together can be made in m×n ways. This simple multiplicative principle, applied repeatedly, underlies essentially all more complex combinatorial counting formulas.
A generating function encodes an entire infinite sequence of numbers as the coefficients of a single formal power series, converting many combinatorial counting problems into algebraic manipulations of these functions. For example, the generating function for the Fibonacci sequence is x/(1−x−x²), and extracting information from generating functions (via algebraic manipulation, partial fractions, or complex analysis techniques) is a systematic and remarkably powerful general method for solving otherwise difficult counting and recurrence relation problems.
Ramsey theory studies the surprising and counterintuitive fact that complete disorder is genuinely impossible in sufficiently large structures — some specific pattern must always eventually emerge. The classic illustrative example: among any 6 people at a party, there must always exist either 3 mutual acquaintances or 3 mutual strangers (a result relying on a specific numerical bound called a Ramsey number). Ramsey numbers grow extraordinarily rapidly and are notoriously difficult to compute exactly — the exact value of the Ramsey number R(5,5) remains unknown even today, with mathematician Paul Erdős famously joking that humanity should divert all available resources toward computing it if a sufficiently powerful hostile alien civilisation ever demanded the answer under threat, since finding R(6,6) would be even more hopelessly difficult still.
Paul Erdős pioneered an ingenious general technique (the probabilistic method) for proving that a combinatorial object with certain desired properties must exist — not by explicitly constructing such an object, but instead by showing that a randomly chosen object has a positive probability of having the desired properties. If that probability is genuinely greater than zero, at least one qualifying object must exist somewhere among all the possibilities, even though the specific proof itself gives no explicit method whatsoever for actually constructing or identifying it. This approach has become an enormously influential and widely applied general technique throughout modern combinatorics.
A particularly elegant style of combinatorial proof establishes that two sets have the same size by explicitly constructing a one-to-one correspondence (bijection) between them, rather than separately calculating and then simply comparing two numerical counts. Such bijective proofs are often considered especially satisfying and mathematically illuminating within combinatorics, since they reveal a deeper conceptual reason for why two seemingly quite different counting problems must always yield exactly the same numerical answer, rather than merely confirming a numerical coincidence through separate calculation.