Combinatorics · The art of counting

Combinatorics

Counting, arranging and connecting: the mathematics of finite things, from card shuffles and seating plans to networks, codes and the limits of computation. Wear it on button-ups and socks, with a mathematics tie to match.

Behind this page Pascal’s triangle is built row by row as you scroll: each new entry is the sum of the two above it, and odd entries are shaded dark. For the pigeonhole principle, the 16 subsets of four things are sorted by size into row 4, 1, 4, 6, 4, 1: sixteen into five holes forces at least four into one. For binomial coefficients, C(6,3) = 10 + 10 = 20. For inclusion-exclusion, row 7 summed with alternating signs is 0, and 1,854 of the 5,040 orderings of seven things move everything, close to 1/e. For generating functions, the shallow diagonals add up to the Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. For Ramsey theory, K6 has C(6,2) = 15 edges and every one of the 32,768 red-blue colorings contains a one-color triangle, while 12 colorings of K5 avoid it, so R(3,3) = 6. For the four color theorem, four regions that each touch the other three share C(4,2) = 6 borders and need four colors. Further down the rows double to 16, 32 and 128 and the odd entries number 81, 243 and 2,187, powers of three: the pattern is Sierpinski’s triangle.

Why it matters

For anyone who has double-counted on purpose

Combinatorics is the mathematics of finite arrangements: how many there are, which ones exist, and how they fit together. In 1736 Leonhard Euler showed that nobody could walk through Königsberg crossing each of its seven bridges exactly once, and graph theory grew out of a local puzzle. In 1976 Kenneth Appel and Wolfgang Haken proved that four colors are enough for any map, using a computer to check nearly two thousand configurations. It was the first major theorem whose proof no one could check entirely by hand.

Research often starts by computing the first few cases by hand, then typing the sequence into the On-Line Encyclopedia of Integer Sequences to see who got there first. It means generating functions, bijections and the pigeonhole principle, and sometimes proving that an object exists by showing that a random one works with positive probability, the method Paul Erdős made his own. It is a field of problems a child can understand: Exoo showed in 1989 that the Ramsey number R(5,5) is at least 43.

KÖNIGSBERG

Every bridge, every vertex, every square, every word: exactly once.

Graph theory began with a walk nobody could take, Euler’s 1736 proof that the seven bridges cannot each be crossed once. Hamilton’s game asks the same of vertices, and the knight’s tour asks it of a chessboard. The de Bruijn bangle answers Euler’s question in disguise: every four-bit word appears once because a graph has an Euler circuit.

  • The Seven Bridges of KönigsbergA museum relief model of the town’s land and river: limestone banks, island and wedge, blue glass water and seven white marble bridges.
  • The Icosian GameA round walnut board with the flattened dodecahedron cut in as 30 grooves, 20 ivory pegs, and one red silk cord around a Hamiltonian cycle.
  • The Knight’s TourA boxwood-and-ebony chessboard, a brass pin at every square’s center, one red silk thread wound along the tour, one ivory knight on the lower-left corner square.
  • The de Bruijn SequenceA flat bangle of 16 equal segments of ebony and ivory with fine gold seams, in the order of the sequence.
Tell me when it’s ready

Leave your email and we’ll write the day it’s ready.

FOUR COLORS SUFFICE

The 1976 postmark, and where four colors are not enough.

After Appel and Haken’s proof of 1976, the University of Illinois mathematics department postmarked its mail with the words Four Colors Suffice. The stained glass is the theorem; the torus is Heawood’s answer for a doughnut-shaped world, seven; the Petersen graph is the snark that shows why Tait’s edge version was hard; and the spindle shows that the plane itself needs at least four colors at unit distance.

  • The Four Color WindowA leaded stained-glass roundel lit from behind, 15 panes of ruby, cobalt, amber and opal-white glass, no two touching panes alike.
  • Seven Colors on a TorusA glazed stoneware torus in seven satin glazes, each region touching all six others.
  • The Petersen GraphA brass-and-enamel model: 10 ivory beads, 5 brass spokes, 4 red, 4 blue and 2 green enameled rods, three different colors at every bead.
  • The Moser SpindleEleven equal brass rods joining seven enameled balls (red, red, white, two blue, two yellow).
Tell me when it’s ready

Leave your email and we’ll write the day it’s ready.

COMPLETE DISORDER

Motzkin’s verdict on Ramsey theory: complete disorder is impossible.

Theodore Motzkin summed up Ramsey theory in four words, and these objects prove them at four sizes: ten letters in nine holes, five guests who can avoid a trio of friends or strangers when six cannot, eight beads that dodge an evenly spaced triple when nine cannot, and ten candles that must hide four in a row.

  • The Pigeonhole DeskA walnut pigeonhole cabinet, the desk organizer, with 9 holes and 10 blank envelopes, two in the center hole.
  • The Party ProblemString art on a round walnut board: five brass pins, five red silk threads around the outside, five blue forming the star.
  • Van der Waerden’s TheoremEight enamel beads on a brass rod, red, red, blue, blue, red, red, blue, blue.
  • The Erdős–Szekeres TheoremTen ivory pillar candles of ten heights on a walnut plank, the 2nd, 4th, 7th and 9th lit.
Tell me when it’s ready

Leave your email and we’ll write the day it’s ready.

36 OFFICERS

Every pair exactly once, and the one size where it cannot be done.

Euler asked in 1782 for 36 officers, six ranks from six regiments, in a square with every rank and regiment once in each row and column; Tarry proved in 1900 that it cannot be done. The others are designs that can: the Fano plane puts every pair of points on one line, a round robin meets every pair of teams once, and the Lo Shu is two orthogonal Latin squares in disguise.

  • Orthogonal Latin Squares16 painted wooden solids (sphere, cube, cone, cylinder in red, blue, yellow, white) in a 4 × 4 walnut tray.
  • The Fano PlaneA brass-and-enamel model: a triangle, its three medians and the circle through the midpoints, each line a different enamel color, seven gold beads.
  • The Round RobinA brass-and-enamel model: eight brass knobs (seven on a circle, one at the center), 28 enameled rods in seven colors, four per color.
  • The Lo Shu SquareA 3 × 3 wooden tray holding 4, 9, 2 / 3, 5, 7 / 8, 1, 6 pebbles, white in the odd cells and black in the even, as in the traditional dot diagram.
Tell me when it’s ready

Leave your email and we’ll write the day it’s ready.

THE TWELVEFOLD WAY

Choose, arrange, partition, list: counting made solid.

The twelvefold way, Gian-Carlo Rota’s idea and Joel Spencer’s name, is the table in the first chapter of Richard Stanley’s Enumerative Combinatorics, the twelve basic ways to count maps between finite sets. These four are its close kin made solid: choosing (the binomial cube), arranging with nothing in place (derangements), partitioning (Young tableaux) and listing every subset with one change at a time (the Gray code).

  • The Binomial TheoremAn exploded wooden cube of 8 painted blocks: a³ red, b³ blue, a²b slabs with red square faces and black sides, ab² bars with blue square ends and black sides.
  • DerangementsFive porcelain cups on five saucers on a round walnut tray, the same five glazes on both, no cup on its own color.
  • The Hook Length FormulaTen square maple tiles in rows of 4, 3, 2, 1 on a walnut board, the corner tile’s 7-tile hook in vermilion.
  • The Gray CodeA glass encoder disc with four concentric tracks of mirror chrome, 16 sectors, a brushed hub.
Tell me when it’s ready

Leave your email and we’ll write the day it’s ready.

Socks mix and match across every field: three pairs for $69, and two ship free in the U.S.

Crew socks · One size

Crew socks

A field of your own, from cuff to toe.

  • The pattern
  • The previewA studio mockup; photos of the finished pair are on the way.
Shop now · Regular price $26 Sale price $23.40

Leave your email and we’ll write the day this pair is ready.

Necktie · 3.5 in wide

Subject ties

A formal introduction to your field.

  • The color
  • The previewStudio render of the tie. Zoom shows the print up close.
Shop now · Regular price $36 Sale price $32.40

Leave your email and we’ll write the day this tie is ready.

The science on the shirt

What you’re wearing

Every object on the shirts, and the science behind it.

The Seven Bridges of Königsberg

KÖNIGSBERG

The Seven Bridges of Königsberg

degrees 5, 3, 3, 3: no walk

It is the first theorem of graph theory and its proof fits on a napkin; every course still opens with this map.

The Icosian Game

KÖNIGSBERG

The Icosian Game

1 of 30 Hamiltonian cycles

It is Königsberg’s partner in every first course: Euler’s walk uses every edge once, Hamilton’s every vertex, and only one of the two questions is easy.

The Knight’s Tour

KÖNIGSBERG

The Knight’s Tour

64 squares, one closed loop

Chess players, puzzle people and programmers all meet it; anyone who has written a backtracking search has tried it.

The de Bruijn Sequence

KÖNIGSBERG

The de Bruijn Sequence

every 4-bit word exactly once

Engineers build absolute position encoders and card tricks from them; theorists see the Euler circuit hiding in every shift register.

The Four Color Window

FOUR COLORS SUFFICE

The Four Color Window

four colors suffice, 1976

It was the first major theorem a computer had to help prove, in 1976, and every placemat map obeys it.

Seven Colors on a Torus

FOUR COLORS SUFFICE

Seven Colors on a Torus

each region borders six others

It is the four color theorem’s surprising cousin: on a doughnut the answer is seven, and it was settled 86 years before the plane.

The Petersen Graph

FOUR COLORS SUFFICE

The Petersen Graph

its edges need four colors

Graph theorists test every conjecture on it first; it is the counterexample on the cover of half the textbooks.

The Moser Spindle

FOUR COLORS SUFFICE

The Moser Spindle

11 equal rods, 4 colors needed

It is the first step on a question a child can state, how many colors the plane needs, and it fits in a hand.

The Pigeonhole Desk

COMPLETE DISORDER

The Pigeonhole Desk

10 letters, 9 holes

It is the proof everyone thinks is too obvious to count, until it settles something nothing else can.

The Party Problem

COMPLETE DISORDER

The Party Problem

R(3,3) = 6

It is the first Ramsey number, and the one every combinatorialist has proved at a party.

Van der Waerden’s Theorem

COMPLETE DISORDER

Van der Waerden’s Theorem

W(2,3) = 9

It is where additive combinatorics began, and its first case fits on eight beads.

The Erdős–Szekeres Theorem

COMPLETE DISORDER

The Erdős–Szekeres Theorem

any 10 heights: 4 rise or fall

A two-line proof by pigeonhole that every combinatorialist teaches, and the start of the longest increasing subsequence problem.

Orthogonal Latin Squares

36 OFFICERS

Orthogonal Latin Squares

every pair once; none for 6

Statisticians lay out field trials with them, and combinatorialists know the story of Euler’s one famous wrong guess.

The Fano Plane

36 OFFICERS

The Fano Plane

every pair on exactly one line

It is the smallest geometry, on every design theorist’s whiteboard; the circle is its seventh line, and the first exam question is why.

The Round Robin

36 OFFICERS

The Round Robin

8 teams, 7 rounds, 28 games

Every league and chess club runs one; graph theorists see a one-factorization of K₈.

The Lo Shu Square

36 OFFICERS

The Lo Shu Square

every line sums to 15

It is the oldest magic square and the cleanest double-counting argument there is.

The Binomial Theorem

THE TWELVEFOLD WAY

The Binomial Theorem

8 blocks: 1 + 3 + 3 + 1

Counting the blocks two ways, by shape and by choices, is the first double-counting proof most people ever see.

Derangements

THE TWELVEFOLD WAY

Derangements

D₅ = 44 of 120, near 1/e

It is the hat-check problem every probability course meets, solved by the oldest trick in counting.

The Hook Length Formula

THE TWELVEFOLD WAY

The Hook Length Formula

staircase of 10: 768 fillings

It is the most surprising formula in enumeration: a product of small numbers that has no business dividing n!, and always does.

The Gray Code

THE TWELVEFOLD WAY

The Gray Code

one bit changes per step

Every rotary encoder, every Karnaugh map and every engineer who has chased a glitching counter uses it.

The big ideas

What people in combinatorics carry around

The Pigeonhole Principle

Put n + 1 pigeons into n holes and some hole holds at least two. Obvious, and startlingly powerful.

Binomial Coefficients

n choose k counts ways to pick k things from n. In Pascal’s triangle each is the sum of the two above.

Inclusion–Exclusion

Count a union by adding the sets, subtracting pairwise overlaps, adding back triple overlaps, and so on. Derangements fall out neatly.

Generating Functions

Store a sequence as the coefficients of a power series, and algebra on the series does the counting for you.

Ramsey Theory

Large enough structures always contain orderly pieces. Among any six people, three are mutual acquaintances or three mutual strangers.

The Four Color Theorem

Any map in the plane can be colored with four colors so that neighbors differ. Proved in 1976, with a computer.