Combinatorics

Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. In particular, it is concerned with "counting" the objects in those collections (enumerative combinatorics), with deciding when the criteria can be met and then constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), with finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and with finding algebraic structures these objects may have (algebraic combinatorics).

Related Topics:
Mathematics - Finite - Combinatorial design - Matroid - Extremal combinatorics - Combinatorial optimization - Algebra - Algebraic combinatorics

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Combinatorics is as much about problem solving as theory building, though it has developed powerful theoretical methods, especially since the later twentieth century. Much of combinatorics is about graphs, to whose study all types of combinatorics can contribute.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

An example of a combinatorial question is the following: What is the number of possible orderings of a deck of 52 playing cards? That number equals 52! (i.e., "fifty-two factorial"). It may seem surprising that this number, about 8.065817517094 × 1067, is so large —a little bit more than 8 followed by 67 zeros! Comparing that number to some other large numbers, it is greater than the square of Avogadro's number, 6.022 × 1023.

Related Topics:
Factorial - Large numbers - Avogadro's number

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

An example of another kind is this problem: Given a certain number n of people, is it possible to assign them to sets so that each person is in at least one set, each pair of people are in exactly one set together, every two sets have exactly one person in common, and no set contains all or all but one of the people? The answer depends on n and is only partially known to this day. See "Design theory" below for a partial answer.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Enumerative combinatorics came to prominence because counting configurations is essential to elementary probability, starting with the work of Pascal and others. Modern combinatorics began to develop in the late nineteenth century and became a distinguishable field of study in the twentieth century, partly through the publication of the systematic enumerative treatise Combinatory Analysis by Percy Alexander MacMahon in 1915 and the work of R.A. Fisher in design of experiments in the 1920s. Two of the most prominent combinatorialists of recent times were the prolific problem-raiser and problem-solver Paul Erdős, who worked mainly on extremal questions, and Gian-Carlo Rota, who helped to formalize the subject beginning in the 1960s, mostly in enumeration and algebraization. The study of how to count objects is sometimes thought of separately as the field of enumeration.

Related Topics:
Probability - Pascal - Combinatory Analysis - Percy Alexander MacMahon - R.A. Fisher - Design of experiments - 1920s - Paul Erdős - Gian-Carlo Rota - 1960s - Enumeration

~ ~ ~ ~ ~ ~ ~ ~ ~ ~