Combinatorics

Binomial coefficients C(n,k) satisfy a rich family of identities beyond their basic definition, discovered through algebraic manipulation, generating functions, or combinatorial (bijective) arguments. Classic examples include Pascal's rule, the symmetry identity, the sum over a row equaling 2ⁿ, Vandermonde's identity for combining two rows, and the hockey stick identity for summing a diagonal. These identities are workhorses throughout combinatorics, probability, and computer science, often turning an intractable sum into a closed form.

The multinomial theorem generalizes the binomial theorem from two terms to any number of terms. It expresses the expansion of (x₁+x₂+⋯+xₘ)ⁿ as a sum over all ways of distributing the exponent n among the m variables, weighted by multinomial coefficients that count the number of ways to arrange a multiset. It is the natural counting tool whenever objects are being placed into more than two categories, such as distributing a hand of cards among several suits or arranging a word with repeated letters.

Pólya enumeration counts distinct colorings or arrangements of objects when configurations related by a symmetry (such as rotation or reflection) are considered identical. It builds on Burnside's lemma, which computes the number of distinct colorings as the average, over all symmetries in a group, of the number of colorings fixed by that symmetry. This technique is the standard tool for counting things like distinct necklaces, dice colorings, or molecular structures up to rotational symmetry.

The Catalan numbers Cₙ form a sequence 1, 1, 2, 5, 14, 42, 132, … that counts an enormous variety of combinatorial structures: the number of valid balanced-parenthesis sequences with n pairs, the number of ways to triangulate a convex polygon with n+2 sides, the number of full binary trees with n+1 leaves, and the number of monotonic lattice paths from (0,0) to (n,n) that never rise above the diagonal. Despite the apparent diversity of these problems, they all satisfy the same recurrence and closed form, making the Catalan numbers one of the most ubiquitous sequences in combinatorics.

A derangement is a permutation of a set in which no element appears in its original position — a 'complete shuffle' with no fixed points. The number of derangements of n objects is denoted !n (the subfactorial), and it is a classic application of the inclusion-exclusion principle. Derangements answer questions like the 'hat-check problem': if n people check their hats and the hats are returned at random, in how many ways can every person get someone else's hat.

A generating function encodes an infinite sequence of numbers as the coefficients of a formal power series, turning combinatorial questions about the sequence into algebraic questions about the series. The ordinary generating function of a sequence a₀,a₁,a₂,… is the power series ∑aₙxⁿ; operations like addition, multiplication, and substitution on generating functions correspond to natural combinatorial operations (like combining or interleaving structures) on the sequences they represent. Generating functions are central to solving recurrence relations, counting combinatorial structures, and proving identities.

A partition of a positive integer n is a way of writing n as a sum of positive integers, where the order of the summands does not matter. The number of partitions of n is denoted p(n); for example p(4)=5 because 4 can be written as 4, 3+1, 2+2, 2+1+1, or 1+1+1+1. Unlike compositions (ordered sums), partitions are unordered, which makes p(n) grow much more slowly and gives it a famously irregular, hard-to-compute closed form — though generating functions provide an elegant way to encode and compute it.

Stirling numbers come in two families that count fundamentally different structures. The Stirling numbers of the second kind, S(n,k), count the number of ways to partition an n-element set into k nonempty unlabeled subsets. The (unsigned) Stirling numbers of the first kind, c(n,k), count the number of permutations of n elements that decompose into exactly k disjoint cycles. Both families satisfy Pascal-triangle-like recurrences and appear throughout combinatorics, from counting set partitions to expressing rising and falling factorials in terms of ordinary powers.

An ordinary combination C(n,k) selects k distinct elements from a set of n, with no element chosen twice. A combination WITH repetition (also called a multiset coefficient) relaxes that rule: elements may be chosen more than once, and only the final count of each type matters, not the order in which they were picked. The classic image is an ice-cream counter with n flavors, where you order k scoops but may repeat a flavor — how many distinct orders are possible? The count is given by the 'stars and bars' formula C(n+k-1, k), and the technique underlies counting integer solutions to equations, sampling with replacement, and multiset enumeration throughout combinatorics.

The twelvefold way, a name popularized by Richard Stanley, is a unifying framework that organizes twelve related enumeration problems — all variations on 'distribute n balls into k boxes' — into a single 3-by-4 table. The three rows classify the balls and boxes as distinguishable or not (balls distinguishable/boxes distinguishable, balls indistinguishable/boxes distinguishable, or balls distinguishable/boxes indistinguishable), while the four columns impose different constraints on how balls land in boxes: no constraint, at most one ball per box (injective), at least one ball per box (surjective), or exactly one ball per box in a bijective sense restricted to counting arrangements. Each of the twelve cells corresponds to a counting formula already familiar from elsewhere in combinatorics — powers, falling factorials, binomial coefficients, Stirling numbers, or partition numbers — and seeing them side by side clarifies why those formulas exist and how they relate.

Many combinatorial quantities are easier to count by relating a problem of size n to smaller instances of the same problem than by writing a direct closed-form formula. Recurrence-based counting sets up a recurrence relation — an equation expressing the n-th term of a sequence in terms of earlier terms — by carefully splitting the objects being counted into cases based on what happens to a distinguished element (often the last or first one). Classic examples include the derangement numbers D_n (permutations with no fixed points), which satisfy D_n = (n-1)(D_{n-1} + D_{n-2}), and the Catalan numbers, which satisfy a convolution recurrence C_n = sum of C_i C_{n-1-i}. Once the recurrence and base cases are established, the sequence can be computed efficiently even when no simple closed form is obvious.

A combinatorial proof establishes an identity by showing that both sides count the same collection of objects, rather than by algebraic manipulation. Two main styles exist: a double-counting proof shows a single set counted in two different ways gives both sides of the equation, while a bijective proof exhibits a one-to-one correspondence between two differently-described sets. Combinatorial proofs are prized for being often shorter and more illuminating than algebraic proofs, directly revealing why an identity is true.

The inclusion-exclusion principle is a counting technique for finding the size of a union of overlapping sets without double-counting elements that belong to more than one. For two sets it says |A∪B| = |A|+|B|-|A∩B|, subtracting off the overlap counted twice. For more sets, the pattern alternates: add the singles, subtract the pairwise intersections, add back the triple intersections, and so on. It is one of the most widely used tools in combinatorics, underlying derangement counts, sieve methods in number theory, and probability calculations involving overlapping events.

When outcomes in a sample space are equally likely, probability calculations reduce to counting problems: the probability of an event is the number of favorable outcomes divided by the total number of outcomes, both computed with combinatorial tools like permutations and combinations. This connection makes card games, dice, and lotteries natural settings for probability, since counting hands, arrangements, or outcomes directly yields exact probabilities without any calculus or continuous distributions involved.

Ramsey theory studies the conditions under which order or structure must appear within any sufficiently large system, no matter how it is arranged — informally captured by the slogan 'complete disorder is impossible.' The classic setting colors the edges of a complete graph with two colors and asks how large the graph must be to guarantee a monochromatic complete subgraph of a given size. The Ramsey number R(m,n) is the smallest N such that any 2-coloring of the edges of the complete graph on N vertices contains either a red K_m or a blue K_n. Ramsey numbers grow explosively and are notoriously difficult to compute exactly.

The probabilistic method, pioneered largely by Paul Erdős starting in the 1940s, proves that a combinatorial structure with a desired property exists by showing that a randomly constructed structure has that property with positive probability — without ever exhibiting the structure explicitly. If the probability of failure (of NOT having the desired property) is strictly less than 1, then some outcome must succeed, so an object with the property must exist. The simplest and most common version is the first-moment method: compute the expected number of 'bad events' in a random construction, and if that expectation is less than 1, some outcome has zero bad events. The technique turned Ramsey theory, graph coloring, and coding theory upside down by proving existence results that no known explicit construction could match.

A permutation is an arrangement of objects where order matters. The number of ways to arrange n distinct objects in a sequence is n! (n factorial), and the number of ways to arrange r of them out of n is denoted P(n,r) or ₙPᵣ. Permutations are the 'order matters' counterpart to combinations.

Counting principles are the basic rules for determining how many ways a sequence of choices can be made, without listing every possibility. The two foundational rules are the addition principle (for mutually exclusive choices) and the multiplication principle (for independent, sequential choices) — together they underlie all of combinatorics, including permutations and combinations.

A combination is a selection of items from a set such that the order of selection does not matter. Given three fruits — an apple, an orange, and a pear — there are three combinations of two that can be drawn: apple-pear, apple-orange, or pear-orange. More formally, a k-combination of a set S is a subset of k distinct elements of S; two combinations are identical exactly when they contain the same members, regardless of the order in which those members were chosen. If the set has n elements, the number of k-combinations, written C(n,k) or the binomial coefficient (n choose k), is n! / (k!(n-k)!). Combinations are the counting foundation for probability, the binomial theorem, and much of discrete mathematics.

The pigeonhole principle states that if n items are placed into m containers, and n > m, then at least one container must hold more than one item. For example, of three gloves, at least two must be right-handed or at least two must be left-handed, since there are three objects but only two categories of handedness. This seemingly obvious observation, a type of counting argument, can be used to prove surprising results — for instance, since the population of London exceeds the maximum number of hairs a human head can have, there must be at least two Londoners with exactly the same number of hairs on their head.

Double counting (also called counting in two ways) is a proof technique that establishes an identity by counting the same finite set — usually a set of pairs or incidences — in two different ways and observing that both counts must agree. Rather than manipulating algebraic expressions, the technique sets up a table or bipartite relation between two collections of objects, sums along rows to get one expression, sums along columns to get another, and concludes the two expressions are equal because they count exactly the same total. It is one of the cleanest tools in combinatorics for proving identities, inequalities, and structural theorems (such as the handshake lemma) without induction or generating functions.