Advanced Combinatorics: Counting, Structure, and Existence

1. Fundamental Counting Principles

All of combinatorics rests on two basic rules and their powerful generalization through inclusion-exclusion.

The Multiplication Rule

If a procedure consists of k steps, and step i can be performed in n(i) ways regardless of how earlier steps were performed, then the total number of ways to complete the procedure is n(1) times n(2) times ... times n(k).

The Addition Rule

If a task can be done in n(1) ways OR n(2) ways (with no overlap), the total number of ways is n(1) + n(2). More generally, if the tasks are mutually exclusive, the counts add. This is the finite version of countable additivity for probability.

Inclusion-Exclusion Principle

When tasks or outcomes overlap, simply adding overcounts the intersections. Inclusion-exclusion corrects for this systematically. For sets A(1), A(2), ..., A(n):

Pigeonhole Principle

If more than n objects are placed into n pigeonholes, at least one pigeonhole contains more than one object. The generalized version states that if kn + 1 objects are placed into n boxes, some box contains at least k + 1 objects. Despite its simplicity, the pigeonhole principle underlies deep results in number theory and combinatorics.

2. Permutations and Combinations

Without Repetition

A permutation selects and orders r items from n distinct items. A combination selects r items without regard to order.

With Repetition

Multinomial Coefficients

When n objects are divided into groups of sizes k(1), k(2), ..., k(m) with k(1) + k(2) + ... + k(m) = n, the number of arrangements is the multinomial coefficient:

Circular Permutations

When n distinct objects are arranged in a circle, one position is considered fixed to eliminate rotational equivalences, giving (n-1)! distinct arrangements. If the circle can also be flipped (necklaces), the count becomes (n-1)!/2.

3. Generating Functions

Generating functions transform sequences into formal power series, converting combinatorial problems into algebraic ones. They are one of the most powerful and versatile tools in advanced combinatorics.

Ordinary Generating Functions (OGF)

The OGF of a sequence a(0), a(1), a(2), ... is the formal power series G(x) = a(0) + a(1)x + a(2)x^2 + a(3)x^3 + ... The key is that x is a formal variable — convergence is secondary to algebraic manipulation.

Exponential Generating Functions (EGF)

For labeled structures (where the identity of elements matters), use the EGF: G(x) = sum a(n) * x^n / n!. The EGF of the all-ones sequence is e^x. Products of EGFs correspond to labeled combinatorial constructions (sequences, sets, permutations).

Operations on Generating Functions

Solving Recurrences with Generating Functions

The standard approach: multiply both sides of the recurrence by x^n, sum over all valid n, recognize the resulting expressions as the GF or its derivatives/shifts, then solve for G(x) algebraically. Finally, use partial fractions to extract coefficients.

4. Recurrence Relations

Linear Recurrences with Constant Coefficients

A linear recurrence of order k has the form: a(n) = c(1)*a(n-1) + c(2)*a(n-2) + ... + c(k)*a(n-k). The general solution is determined by the characteristic equation obtained by substituting a(n) = r^n.

Divide-and-Conquer Recurrences

Algorithms that split problems into b subproblems of size n/b with f(n) work at each level satisfy T(n) = a*T(n/b) + f(n). The master theorem resolves these in closed form.

Catalan Numbers

The Catalan numbers C(n) = C(2n, n) / (n+1) satisfy the recurrence C(n) = sum from k=0 to n-1 of C(k)*C(n-1-k), with C(0)=1. They count: triangulations of a convex polygon, balanced parenthesizations, rooted binary trees, monotone lattice paths below the diagonal, and dozens of other structures. The GF satisfies C(x) = 1 + x*C(x)^2, giving C(x) = (1 - sqrt(1-4x)) / (2x).

5. Graph Theory Combinatorics

Counting Trees

A tree on n labeled vertices has exactly n-1 edges and is connected and acyclic. Cayley's formula gives the total number of labeled trees on n vertices as n^(n-2). This is one of the most elegant results in combinatorics.

Prüfer Sequences

Prüfer's encoding establishes a bijection between labeled trees on n vertices and sequences of length n-2 from the set (1, 2, ..., n). This bijection directly proves Cayley's formula.

Spanning Trees and Kirchhoff's Matrix Tree Theorem

The number of spanning trees of a graph G equals any cofactor of the Laplacian matrix L = D - A, where D is the degree matrix and A is the adjacency matrix. Equivalently, it equals (1/n) times the product of non-zero eigenvalues of L. For the complete graph K(n), all eigenvalues are n (with multiplicity n-1), confirming n^(n-2) spanning trees via Cayley.

Euler Characteristic and Planar Graphs

For a connected planar graph with V vertices, E edges, and F faces (including the outer face): V - E + F = 2. This Euler characteristic equation constrains the structure of planar graphs: any simple planar graph satisfies E is at most 3V - 6, and any triangle-free planar graph satisfies E is at most 2V - 4.

6. Ramsey Theory

Ramsey theory is the study of unavoidable order: in any sufficiently large structure, some regular substructure must appear. The unifying theme is: "complete disorder is impossible."

Graph Ramsey Numbers

The Ramsey number R(s,t) is the minimum n such that every 2-coloring of the edges of K(n) contains a red K(s) or a blue K(t). The fundamental fact, proved by Ramsey in 1930, is that R(s,t) is always finite. The diagonal numbers R(k,k) are extremely difficult to compute.

Van der Waerden's Theorem

For any positive integers r and k, there exists a number W(r,k) such that any r-coloring of the integers (1, 2, ..., W(r,k)) contains a monochromatic arithmetic progression of length k. Van der Waerden's theorem was proved in 1927 and is the prototypical result of combinatorial number theory. The bounds on W(r,k) are notoriously difficult: W(2,3) = 9, W(2,4) = 35, W(3,3) = 27.

Hales-Jewett Theorem

The Hales-Jewett theorem is a multidimensional generalization of Van der Waerden. For any alphabet of size t and any number of colors r, there exists a dimension n such that any r-coloring of the t^n cells of an n-dimensional t^n hypercube contains a monochromatic combinatorial line. It implies Van der Waerden and is a foundational result in topological dynamics and ergodic theory.

7. Extremal Combinatorics

Extremal combinatorics asks: how large or small can a combinatorial structure be, subject to given constraints? The answer often reveals deep structural properties of the extremal configurations.

Turán's Theorem

The maximum number of edges in an n-vertex K(r+1)-free graph is achieved by the Turán graph T(n,r): divide n vertices into r parts as equally as possible and connect every pair of vertices in different parts (complete r-partite graph).

Kruskal-Katona Theorem

The Kruskal-Katona theorem characterizes which families of sets can occur as k-element subsets: given a family F of k-element subsets of (1,...,n), the shadow (all (k-1)-element subsets of members of F) has size at least as large as the shadow of the first |F| k-element subsets in the colexicographic order. It is the key tool in proving the Frankl-Wilson theorem and many other results.

Bollobás Set-Pairs Inequality

Let (A(1), B(1)), ..., (A(m), B(m)) be pairs of finite sets such that A(i) intersects B(j) if and only if i = j (cross-intersection condition). Then: sum from i=1 to m of C(|A(i)| + |B(i)|, |A(i)|)^(-1) is at most 1. This elegant inequality generalizes Dilworth's theorem and has applications throughout extremal set theory.

Erdős-Ko-Rado Theorem

For n is at least 2k, the maximum size of an intersecting family of k-element subsets of an n-element set is C(n-1, k-1). The unique extremal family (for n > 2k) consists of all k-element sets containing a fixed element — a "star." This theorem is central to extremal set theory and has numerous generalizations.

8. The Probabilistic Method

Pioneered by Erdős, the probabilistic method proves existence of combinatorial objects by analyzing random structures. If a random object has a desired property with positive probability, then such an object must exist — even without an explicit construction.

First Moment Method (Union Bound)

If X counts the number of "bad" events and E[X] is less than 1, then Pr[X = 0] is greater than 0, so a good configuration exists. More precisely, Pr[at least one bad event] is at most E[X] by linearity of expectation and the union bound.

Second Moment Method

The Paley-Zygmund inequality states: Pr[X > 0] is at least (E[X])^2 / E[X^2]. So if E[X^2] = Theta(E[X]^2), then X is positive with positive constant probability. This is used to show that not only does X have positive expectation but it is actually positive with high probability. Computing E[X^2] requires understanding covariances between indicators.

Lovász Local Lemma (LLL)

The LLL handles cases where bad events are individually unlikely but not fully independent. Let A(1), ..., A(n) be bad events. Suppose each event A(i) is independent of all but at most d other events, and Pr[A(i)] is at most p for all i. If ep(d+1) is at most 1 (where e is Euler's number), then Pr[none of the A(i) occur] is greater than 0.

9. Algebraic Combinatorics

Burnside's Lemma

Burnside's lemma (properly the Cauchy-Frobenius lemma) counts distinct objects under a symmetry group G acting on a set X of configurations. The number of distinct orbits (equivalence classes under symmetry) is:

Polya Enumeration Theorem

Polya's theorem generalizes Burnside by tracking not just the count of distinct colorings but the distribution by color inventory. For a group G acting on positions, the cycle index Z(G; x(1), x(2), ...) is:

Symmetric Functions

The ring of symmetric functions is spanned by several important bases: monomial symmetric functions m(lambda), elementary symmetric functions e(k) = sum of products of k distinct variables, complete homogeneous functions h(k) = sum of monomials of degree k, and Schur functions s(lambda). These bases are related by the involution omega that swaps e(k) and h(k) and transforms one Schur function into another.

10. Combinatorial Designs

Combinatorial design theory studies arrangements of elements into subsets with highly regular intersection properties. These structures appear in coding theory, statistics, cryptography, and tournament scheduling.

Block Designs: (v, k, lambda)-Designs

A (v, k, lambda)-design (also called a balanced incomplete block design or BIBD) consists of a set V of v points and a collection B of k-element subsets (blocks) such that every 2-element subset of V appears in exactly lambda blocks.

Steiner Systems

A Steiner system S(t, k, n) is a collection of k-element subsets of an n-element set such that every t-element subset appears in exactly one block. The most famous: S(2,3,n) are Steiner triple systems (every pair in exactly one triple), which exist iff n is congruent to 1 or 3 (mod 6). The Steiner system S(5, 6, 12) is related to the Mathieu group M(12).

Latin Squares

An n times n Latin square is an n times n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. Latin squares are equivalent to Cayley tables of quasigroups.

Finite Geometries

A projective plane of order n has n^2 + n + 1 points and n^2 + n + 1 lines, with n + 1 points on each line and n + 1 lines through each point. Any two points lie on exactly one line, and any two lines meet in exactly one point. Projective planes of prime power order are constructed from finite fields GF(q). Whether non-prime-power orders exist is open (the order 10 case was ruled out by a massive computer search in 1989).

11. Partition Theory

A partition of an integer n is a way of writing n as an unordered sum of positive integers. Partition theory connects combinatorics with number theory, representation theory, and statistical mechanics.

Partition Counting and Generating Functions

Let p(n) denote the number of partitions of n. Euler's remarkable product formula gives the generating function:

Conjugate Partitions and Ferrers Diagrams

A partition can be visualized as a Ferrers diagram (or Young diagram): rows of dots where row i has lambda(i) dots. The conjugate partition is obtained by transposing the diagram (reflecting across the main diagonal). The number of partitions of n into at most k parts equals the number of partitions of n into parts of size at most k.

Young Tableaux

A Standard Young Tableau (SYT) of shape lambda is a filling of the Young diagram with numbers 1, 2, ..., n such that entries increase left-to-right in each row and top-to-bottom in each column. A Semistandard Young Tableau (SSYT) allows repeated entries with entries weakly increasing in rows and strictly increasing in columns.

Hook Length Formula

The number of standard Young tableaux of shape lambda, where lambda is a partition of n, is given by the hook length formula:

RSK Correspondence

The Robinson-Schensted-Knuth (RSK) correspondence is a bijection between permutations of (1,...,n) and pairs of standard Young tableaux of the same shape. It maps the permutation's cycle structure to the shape of the tableaux and has profound implications: the number of permutations of n with longest increasing subsequence of length at most k equals the number of pairs of SYT with at most k rows.

Practice Problems with Solutions

Exam Tips and Common Pitfalls

Quick Reference

Related Topics

Frequently Asked Questions