Why combinatorics: counting, structure and existence

Combinatorics is the mathematics of finite arrangements. It asks how many ways something can be done, whether it can be done at all, and what the best possible way is. A first course in discrete mathematics, such as MATH-260, introduces the basic tools: the sum and product rules, permutations and binomial coefficients, the pigeonhole principle, recurrences and the vocabulary of graphs. This course goes further. It develops generating functions, the full principle of inclusion and exclusion, Stirling, Bell and Catalan numbers, integer partitions, and then the structural theory of graphs: connectivity, planarity, coloring, matchings, network flows and Ramsey theory. Along the way it meets some of the most celebrated results and open problems in modern mathematics.

The subject is old. Indian mathematicians counted poetic rhythms and combinations of tastes more than two thousand years ago; Pascal and Fermat founded probability on counting in 1654; Euler solved the Königsberg bridge problem in 1736, which is usually taken as the birth of graph theory. But combinatorics became a central branch of mathematics only in the twentieth century, driven by computing, by operations research, and by the realization that finite structures hide deep patterns. Today it supplies the mathematics behind network design, scheduling, error-correcting codes, the analysis of algorithms and statistical physics.

Three kinds of question

Most combinatorial problems fall into one of three types. Enumerative questions ask how many: how many ways are there to tile a chessboard with dominoes, how many partitions does the number 100 have, how many proper colorings of a graph use \(k\) colors? Existence questions ask whether: is there a route crossing every bridge exactly once, can a graph be drawn in the plane without crossings, can every worker be given a job they are qualified for? Extremal questions ask how large or small: what is the largest flow a network can carry, how many vertices guarantee a monochromatic triangle, what is the fewest number of colors a map needs?

The three types are closely linked. Counting can prove existence: if the number of objects with a property is positive, one exists. This is the heart of the probabilistic method in lesson 12. Existence results often come with an algorithm that constructs the object, as for matchings in lesson 10 and flows in lesson 11. And extremal results are usually proved in two halves, a construction showing the bound can be reached and an argument showing it cannot be beaten. The theorem that a maximum flow equals a minimum cut, for instance, is exactly such a matched pair.

Double counting

The simplest powerful idea in combinatorics is to count the same set in two different ways and equate the answers. If a finite set of pairs \(P \subseteq A \times B\) is given, then \[\sum_{a \in A} |\{b : (a, b) \in P\}| = |P| = \sum_{b \in B} |\{a : (a, b) \in P\}|.\] Counting by rows and by columns of a 0–1 table gives the same total. MATH-260 used this to prove the handshake lemma: summing degrees counts each edge twice, so \(\sum_v \deg v = 2|E|\), and the number of odd-degree vertices is even.

Example: the committee identity. Count pairs (committee, chair) where the committee is a \(k\)-element subset of an \(n\)-person club and the chair is a member of it. Choosing the committee first gives \(\binom{n}{k} \cdot k\). Choosing the chair first, then the other \(k - 1\) members from the remaining \(n - 1\) people, gives \(n\binom{n-1}{k-1}\). Therefore \(k\binom{n}{k} = n\binom{n-1}{k-1}\). Summing over \(k\) gives \(\sum_k k\binom{n}{k} = n2^{n-1}\), since the right-hand side counts a chair together with any subset of the others.

Example: counting incidences in a design. Suppose a tournament schedule has \(b\) games, each involving 3 of \(v\) teams, and every team plays in exactly \(r\) games. Counting (team, game) pairs gives \(3b = vr\). With \(v = 7\) and every pair of teams meeting in exactly one game, each team meets 6 others, two per game, so \(r = 3\) and \(b = 7\). This is the Fano plane, the smallest example of a block design, and double counting forces its parameters before anyone draws it.

Invariants and impossibility

To prove that something cannot be done, look for a quantity that every allowed move preserves. The classic example is the mutilated chessboard. Remove two diagonally opposite corners from an \(8 \times 8\) board. Can the remaining 62 squares be covered by 31 dominoes, each covering two adjacent squares?

Each domino covers one dark and one light square, whatever its position. So any set of 31 dominoes covers 31 dark and 31 light squares. But the two removed corners have the same shade, so the mutilated board has 32 squares of one shade and 30 of the other. No tiling exists. Trying cases by hand would be hopeless; the invariant settles the question in two lines. Ralph Gomory later showed the converse: removing any one dark and one light square leaves a board that can always be tiled, by following a Hamilton cycle through the board.

Invariants appear throughout this course. Parity of degrees decides Euler tours in lesson 7; the count \(V - E + F\) is invariant over plane drawings in lesson 8; and in lesson 10 the size of a vertex cover bounds every matching. Whenever a problem says prove this is impossible, the first question is what stays the same.

The pigeonhole principle, sharpened

The pigeonhole principle says that if more than \(n\) objects are put into \(n\) boxes, some box holds at least two. The general form: if \(N\) objects are put into \(n\) boxes, some box holds at least \(\lceil N/n \rceil\) objects. Its power lies in choosing the boxes cleverly. A striking application is the Erdős–Szekeres theorem of 1935, one of the first results of Ramsey theory.

Theorem (Erdős–Szekeres). Every sequence of \(rs + 1\) distinct real numbers contains an increasing subsequence of length \(r + 1\) or a decreasing subsequence of length \(s + 1\).

Proof. Let the sequence be \(a_1, \ldots, a_{rs+1}\). For each position \(i\) let \(x_i\) be the length of the longest increasing subsequence ending at \(a_i\), and \(y_i\) the length of the longest decreasing subsequence ending at \(a_i\). Suppose, for contradiction, that \(x_i \le r\) and \(y_i \le s\) for every \(i\). Then the pairs \((x_i, y_i)\) take at most \(rs\) values, so by pigeonhole two positions \(i < j\) have the same pair. But if \(a_i < a_j\), appending \(a_j\) to the longest increasing subsequence ending at \(a_i\) gives \(x_j \ge x_i + 1\); and if \(a_i > a_j\), similarly \(y_j \ge y_i + 1\). Either way the pairs differ, a contradiction.

The bound is sharp. The sequence \(3, 2, 1, 6, 5, 4, 9, 8, 7\) has \(rs = 9\) terms with \(r = s = 3\), and its longest increasing subsequence has length 3 (one term from each block) and its longest decreasing subsequence has length 3 (one block). So \(rs\) terms are not enough. Such a construction showing a bound is best possible is the other half of every extremal theorem.

Bijections

A bijection between two sets proves they have the same size without computing either. MATH-260 met the classic example: the number of lattice paths from \((0, 0)\) to \((m, n)\) using unit steps right and up equals \(\binom{m+n}{m}\), because a path is determined by which of its \(m + n\) steps go right. Lesson 2 builds a whole family of bijections around the Catalan numbers, and lesson 6 uses Ferrers diagrams to prove partition identities by reflecting pictures.

A bijective proof often explains more than a calculation. The identity \(\binom{n}{k} = \binom{n}{n-k}\) is immediate from the bijection sending a subset to its complement. The identity \(2^n = \sum_k \binom{n}{k}\) says that subsets of an \(n\)-set can be sorted by size. Richard Stanley's books list hundreds of sets counted by the Catalan numbers, each with bijections to the others; finding such bijections remains an active research area.

What this course covers

The first half develops enumeration. Lesson 2 studies bijections, multisets, compositions, Stirling numbers and Catalan numbers. Lesson 3 proves the general principle of inclusion and exclusion and applies it to derangements, surjections and Euler's phi function. Lessons 4 and 5 introduce ordinary and exponential generating functions, which turn counting problems into algebra. Lesson 6 studies integer partitions, Euler's pentagonal number theorem and the asymptotic growth of counting sequences.

The second half develops graph theory. Lesson 7 covers connectivity, Euler tours and Hamilton cycles; lesson 8 planar graphs, Euler's formula and Kuratowski's theorem; lesson 9 coloring, Brooks' theorem, the four color theorem and chromatic polynomials; lesson 10 matchings, Hall's and König's theorems and the stable marriage problem; lesson 11 network flows and Menger's theorem; and lesson 12 Ramsey theory and the probabilistic method. Every lesson includes runnable Python, because experiment is part of how combinatorics is done.

Experiments by computer

The program counts domino tilings of rectangles by a column-by-column method, confirms the parity argument for the mutilated board by brute force on a small case, and tests the Erdős–Szekeres theorem on random sequences and on the extremal example.

import random
from functools import lru_cache

def tilings(rows, cols):
    """Count domino tilings of a rows x cols board, filling one column at a time."""
    @lru_cache(maxsize=None)
    def fill(col, mask):
        if col == cols:
            return 1 if mask == 0 else 0
        total = 0
        def place(r, cur, nxt):
            nonlocal total
            if r == rows:
                total += fill(col + 1, nxt)
                return
            if cur >> r & 1:
                place(r + 1, cur, nxt)
                return
            place(r + 1, cur, nxt | 1 << r)          # horizontal domino sticks into next column
            if r + 1 < rows and not cur >> (r + 1) & 1:
                place(r + 2, cur, nxt)                # vertical domino in this column
        place(0, mask, 0)
        return total
    return fill(0, 0)

print("2 x n boards:", [tilings(2, n) for n in range(1, 11)])
print("8 x 8 board:", tilings(8, 8))

def can_tile(cells):
    cells = set(cells)
    if not cells:
        return True
    r, c = min(cells)
    for d in [(0, 1), (1, 0)]:
        other = (r + d[0], c + d[1])
        if other in cells and can_tile(cells - {(r, c), other}):
            return True
    return False

board = [(r, c) for r in range(4) for c in range(4)]
print("4 x 4 minus opposite corners tileable?", can_tile([x for x in board if x not in [(0, 0), (3, 3)]]))
print("4 x 4 minus (0,0) and (0,1) tileable?", can_tile([x for x in board if x not in [(0, 0), (0, 1)]]))

def longest(seq, up=True):
    best = []
    for i, a in enumerate(seq):
        best.append(1 + max([best[j] for j in range(i) if (seq[j] < a) == up] or [0]))
    return max(best)

random.seed(460)
r = s = 4
ok = True
for trial in range(2000):
    seq = random.sample(range(1000), r * s + 1)
    if longest(seq) <= r and longest(seq, False) <= s:
        ok = False
print("Erdos-Szekeres holds on 2000 random sequences of length 17:", ok)
extreme = [3, 2, 1, 6, 5, 4, 9, 8, 7]
print("extremal example:", extreme, "longest up", longest(extreme), "longest down", longest(extreme, False))

2 x n boards: [1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
8 x 8 board: 12988816
4 x 4 minus opposite corners tileable? False
4 x 4 minus (0,0) and (0,1) tileable? True
Erdos-Szekeres holds on 2000 random sequences of length 17: True
extremal example: [3, 2, 1, 6, 5, 4, 9, 8, 7] longest up 3 longest down 3

The \(2 \times n\) counts are the Fibonacci numbers, as MATH-260 showed by a recurrence. The full chessboard has 12,988,816 tilings, a number first computed in 1961 by Temperley and Fisher and independently by Kasteleyn, who found an exact product formula using determinants. The small brute-force check agrees with the parity argument: removing two squares of the same shade makes tiling impossible, while removing an adjacent pair leaves a tileable board.