Combinatorics

Lore & Background

Basic combinatorial concepts and enumerative results appeared throughout the ancient world. The earliest recorded use of combinatorial techniques comes from problem 79 of the Rhind papyrus, dating to the 16th century BC, which is actually about a geometric series. Indian physician Sushruta is often credited with noting that 63 combinations can be made out of 6 different tastes, but the Sushruta Samhita does not explicitly state the formula 2^6 − 1, and the attribution is debated. Greek historian Plutarch discusses an argument between Chrysippus and Hipparchus concerning a delicate enumerative problem later related to Schröder–Hipparchus numbers. Archimedes may have considered the number of configurations of a tiling puzzle in the Ostomachion. In the Middle Ages, Indian mathematician Mahāvīra provided formulae for permutations and combinations, and Rabbi Abraham ibn Ezra established the symmetry of binomial coefficients, with a closed formula obtained by Levi ben Gerson in 1321. The arithmetical triangle, later known as Pascal's triangle, appeared in treatises as early as the 11th century. During the Renaissance, works of Pascal, Newton, Jacob Bernoulli, and Leonhard Euler became foundational. In the later twentieth century, powerful general theoretical methods were developed, making combinatorics an independent branch of mathematics.

Reader's Guide

Combinatorics is well known for the breadth of the problems it tackles, arising in pure mathematics—algebra, probability theory, topology, geometry—and in many application areas. In the later twentieth century, powerful general theoretical methods were developed, establishing combinatorics as an independent branch. Graph theory, one of its oldest and most accessible parts, has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain formulas and estimates in the analysis of algorithms. The field's growth in the second half of the 20th century led to dozens of new journals and conferences, spurred by connections to algebra, probability, functional analysis, and number theory. These connections shed boundaries between combinatorics and other fields but also led to partial fragmentation. Its subfields include enumerative combinatorics, analytic combinatorics, partition theory, graph theory, and design theory, each with distinct problems and techniques.

Did You Know?

• The earliest recorded use of combinatorial techniques comes from problem 79 of the Rhind papyrus, dating to the 16th century BC, though it is actually about a geometric series.
• Indian physician Sushruta is often credited with noting that 63 combinations can be made out of 6 different tastes, but the Sushruta Samhita does not explicitly state the formula 2^6 − 1, and the attribution is debated.
• The arithmetical triangle, later known as Pascal's triangle, was presented in treatises as early as the 11th century.
• In Medieval England, campanology provided examples of what are now known as Hamiltonian cycles in certain Cayley graphs on permutations.

Defining an Elusive Discipline

Combinatorics resists a single clean definition. As H. J. Ryser observed, the subject sprawls across so many mathematical subdivisions that pinning it down is genuinely difficult. Leon Mirsky captured this tension by describing it as a cluster of linked studies that share a common thread yet diverge sharply in their goals, methods, and internal coherence. Rather than offering a rigid boundary, it is more useful to describe combinatorics by the kinds of questions it answers. At its core, the field tackles four broad categories: counting the number of arrangements or configurations within finite systems; proving that structures meeting certain criteria actually exist; constructing those structures, sometimes in multiple ways; and optimizing, meaning identifying the best solution among many candidates according to some criterion such as maximum or minimum size. Although the primary focus is on finite structures, some techniques extend into countably infinite discrete settings. The full scope of what belongs under the combinatorics umbrella remains debated, and historical considerations sometimes influence which topics are included.

Roots in Ancient and Medieval Mathematics

The intellectual seeds of combinatorics stretch back millennia. The earliest recorded instance appears in problem 79 of the Rhind papyrus, a 16th-century BC Egyptian document dealing with a geometric series that echoes Fibonacci's later work on compositions of integers. In ancient India, the physician Sushruta calculated all 2 to the 6th power minus 1 combinations of six tastes taken one at a time, two at a time, and so on. Greek thinkers contributed as well: Plutarch recorded a dispute between Chrysippus and Hipparchus over an enumerative problem later linked to Schröder–Hipparchus numbers, and Archimedes may have explored tiling configurations in his Ostomachion puzzle. During the Middle Ages, the Indian mathematician Mahāvīra (around 850 CE) supplied formulas for permutations and combinations, possibly known in India as early as the 6th century. In the Jewish scholarly tradition, Rabbi Abraham ibn Ezra demonstrated the symmetry of binomial coefficients around 1140, and Gersonides derived a closed formula in 1321. The arithmetical triangle, later celebrated as Pascal's triangle, appeared in treatises as early as the 10th century.

Renaissance Rebirth and the Rise of a Field

The Renaissance brought combinatorics into the broader mathematical renaissance alongside physics and other sciences. The works of Pascal, Newton, Jacob Bernoulli, and Leonhard Euler became cornerstones of the emerging discipline. In the late 19th and early 20th centuries, J. J. Sylvester and Percy MacMahon laid the groundwork for what would become enumerative and algebraic combinatorics, while graph theory gained momentum through problems like the four-color conjecture. The second half of the 20th century marked a dramatic acceleration. New connections to algebra, probability, functional analysis, number theory, and theoretical computer science blurred the boundaries between combinatorics and neighboring fields. This cross-pollination spurred the creation of dozens of dedicated journals and conferences. At the same time, the rapid expansion brought a partial fragmentation, as specialized subfields developed their own vocabularies and methods. What had long been treated as a collection of isolated, ad hoc solutions to scattered problems finally coalesced into a recognized, independent branch of mathematics with its own powerful general theories.

Subfields, Tools, and Real-World Reach

Combinatorics is not a monolith; it branches into distinct subfields with different toolkits. Enumerative combinatorics, the most classical strand, focuses on counting combinatorial objects, with Fibonacci numbers serving as a canonical example and the twelvefold way providing a unified framework for permutations, combinations, and partitions. Analytic combinatorics takes a different route, employing complex analysis and probability theory to study the enumeration of structures, contrasting with the more explicit combinatorial methods of its enumerative counterpart. Graph theory, one of the oldest and most accessible parts of the subject, connects naturally to numerous other areas of mathematics. Beyond pure theory, combinatorics finds frequent use in computer science, where it supplies formulas and estimates essential to algorithm analysis. Its applications span logic, statistical physics, evolutionary biology, and beyond. Combinatorial problems also arise in algebra, topology, and geometry, underscoring the field's remarkable breadth. This wide reach is precisely what makes the subject both powerful and difficult to confine to a single definition.

Gallery