# Combinatorics

Not to be confused with Combinatoriality. Combinatorics_sentence_0

"Combinatorial" redirects here. Combinatorics_sentence_1

For combinatorial logic in computer science, see Combinatorial logic. Combinatorics_sentence_2

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. Combinatorics_sentence_3

It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics, from evolutionary biology to computer science, etc. Combinatorics_sentence_4

The full scope of combinatorics is not universally agreed upon. Combinatorics_sentence_5

According to H.J. Combinatorics_sentence_6 Ryser, a definition of the subject is difficult because it crosses so many mathematical subdivisions. Combinatorics_sentence_7

Insofar as an area can be described by the types of problems it addresses, combinatorics is involved with Combinatorics_sentence_8

Combinatorics_unordered_list_0

• the enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems,Combinatorics_item_0_0
• the existence of such structures that satisfy certain given criteria,Combinatorics_item_0_1
• the construction of these structures, perhaps in many ways, andCombinatorics_item_0_2
• optimization, finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some other optimality criterion.Combinatorics_item_0_3

Leon Mirsky has said: "combinatorics is a range of linked studies which have something in common and yet diverge widely in their objectives, their methods, and the degree of coherence they have attained." Combinatorics_sentence_9

One way to define combinatorics is, perhaps, to describe its subdivisions with their problems and techniques. Combinatorics_sentence_10

This is the approach that is used below. Combinatorics_sentence_11

However, there are also purely historical reasons for including or not including some topics under the combinatorics umbrella. Combinatorics_sentence_12

Although primarily concerned with finite systems, some combinatorial questions and techniques can be extended to an infinite (specifically, countable) but discrete setting. Combinatorics_sentence_13

Combinatorics is well known for the breadth of the problems it tackles. Combinatorics_sentence_14

Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry, as well as in its many application areas. Combinatorics_sentence_15

Many combinatorial questions have historically been considered in isolation, giving an ad hoc solution to a problem arising in some mathematical context. Combinatorics_sentence_16

In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. Combinatorics_sentence_17

One of the oldest and most accessible parts of combinatorics is graph theory, which by itself has numerous natural connections to other areas. Combinatorics_sentence_18

Combinatorics is used frequently in computer science to obtain formulas and estimates in the analysis of algorithms. Combinatorics_sentence_19

A mathematician who studies combinatorics is called a combinatorialist. Combinatorics_sentence_20

## History Combinatorics_section_0

Main article: History of combinatorics Combinatorics_sentence_21

Basic combinatorial concepts and enumerative results appeared throughout the ancient world. Combinatorics_sentence_22

In the 6th century BCE, ancient Indian physician Sushruta asserts in Sushruta Samhita that 63 combinations can be made out of 6 different tastes, taken one at a time, two at a time, etc., thus computing all 2 − 1 possibilities. Combinatorics_sentence_23

Greek historian Plutarch discusses an argument between Chrysippus (3rd century BCE) and Hipparchus (2nd century BCE) of a rather delicate enumerative problem, which was later shown to be related to Schröder–Hipparchus numbers. Combinatorics_sentence_24

In the Ostomachion, Archimedes (3rd century BCE) considers a tiling puzzle. Combinatorics_sentence_25

In the Middle Ages, combinatorics continued to be studied, largely outside of the European civilization. Combinatorics_sentence_26

The Indian mathematician Mahāvīra (c. 850) provided formulae for the number of permutations and combinations, and these formulas may have been familiar to Indian mathematicians as early as the 6th century CE. Combinatorics_sentence_27

The philosopher and astronomer Rabbi Abraham ibn Ezra (c. 1140) established the symmetry of binomial coefficients, while a closed formula was obtained later by the talmudist and mathematician Levi ben Gerson (better known as Gersonides), in 1321. Combinatorics_sentence_28

The arithmetical triangle—a graphical diagram showing relationships among the binomial coefficients—was presented by mathematicians in treatises dating as far back as the 10th century, and would eventually become known as Pascal's triangle. Combinatorics_sentence_29

Later, in Medieval England, campanology provided examples of what is now known as Hamiltonian cycles in certain Cayley graphs on permutations. Combinatorics_sentence_30

During the Renaissance, together with the rest of mathematics and the sciences, combinatorics enjoyed a rebirth. Combinatorics_sentence_31

Works of Pascal, Newton, Jacob Bernoulli and Euler became foundational in the emerging field. Combinatorics_sentence_32

In modern times, the works of J.J. Combinatorics_sentence_33 Sylvester (late 19th century) and Percy MacMahon (early 20th century) helped lay the foundation for enumerative and algebraic combinatorics. Combinatorics_sentence_34

Graph theory also enjoyed an explosion of interest at the same time, especially in connection with the four color problem. Combinatorics_sentence_35

In the second half of the 20th century, combinatorics enjoyed a rapid growth, which led to establishment of dozens of new journals and conferences in the subject. Combinatorics_sentence_36

In part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, from functional analysis to number theory, etc. Combinatorics_sentence_37

These connections shed the boundaries between combinatorics and parts of mathematics and theoretical computer science, but at the same time led to a partial fragmentation of the field. Combinatorics_sentence_38

## Approaches and subfields of combinatorics Combinatorics_section_1

### Enumerative combinatorics Combinatorics_section_2

Main article: Enumerative combinatorics Combinatorics_sentence_39

Enumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects. Combinatorics_sentence_40

Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. Combinatorics_sentence_41

Fibonacci numbers is the basic example of a problem in enumerative combinatorics. Combinatorics_sentence_42

The twelvefold way provides a unified framework for counting permutations, combinations and partitions. Combinatorics_sentence_43

### Analytic combinatorics Combinatorics_section_3

Main article: Analytic combinatorics Combinatorics_sentence_44

Analytic combinatorics concerns the enumeration of combinatorial structures using tools from complex analysis and probability theory. Combinatorics_sentence_45

In contrast with enumerative combinatorics, which uses explicit combinatorial formulae and generating functions to describe the results, analytic combinatorics aims at obtaining asymptotic formulae. Combinatorics_sentence_46

### Partition theory Combinatorics_section_4

Main article: Partition theory Combinatorics_sentence_47

Partition theory studies various enumeration and asymptotic problems related to integer partitions, and is closely related to q-series, special functions and orthogonal polynomials. Combinatorics_sentence_48

Originally a part of number theory and analysis, it is now considered a part of combinatorics or an independent field. Combinatorics_sentence_49

It incorporates the bijective approach and various tools in analysis and analytic number theory and has connections with statistical mechanics. Combinatorics_sentence_50

### Graph theory Combinatorics_section_5

Main article: Graph theory Combinatorics_sentence_51

Graphs are fundamental objects in combinatorics. Combinatorics_sentence_52

Considerations of graph theory range from enumeration (e.g., the number of graphs on n vertices with k edges) to existing structures (e.g., Hamiltonian cycles) to algebraic representations (e.g., given a graph G and two numbers x and y, does the Tutte polynomial TG(x,y) have a combinatorial interpretation?). Combinatorics_sentence_53

Although there are very strong connections between graph theory and combinatorics, they are sometimes thought of as separate subjects. Combinatorics_sentence_54

While combinatorial methods apply to many graph theory problems, the two disciplines are generally used to seek solutions to different types of problems. Combinatorics_sentence_55

### Design theory Combinatorics_section_6

Main article: Combinatorial design Combinatorics_sentence_56

Design theory is a study of combinatorial designs, which are collections of subsets with certain intersection properties. Combinatorics_sentence_57

Block designs are combinatorial designs of a special type. Combinatorics_sentence_58

This area is one of the oldest parts of combinatorics, such as in Kirkman's schoolgirl problem proposed in 1850. Combinatorics_sentence_59

The solution of the problem is a special case of a Steiner system, which systems play an important role in the classification of finite simple groups. Combinatorics_sentence_60

The area has further connections to coding theory and geometric combinatorics. Combinatorics_sentence_61

### Finite geometry Combinatorics_section_7

Main article: Finite geometry Combinatorics_sentence_62

Finite geometry is the study of geometric systems having only a finite number of points. Combinatorics_sentence_63

Structures analogous to those found in continuous geometries (Euclidean plane, real projective space, etc.) but defined combinatorially are the main items studied. Combinatorics_sentence_64

This area provides a rich source of examples for design theory. Combinatorics_sentence_65

It should not be confused with discrete geometry (combinatorial geometry). Combinatorics_sentence_66

### Order theory Combinatorics_section_8

Main article: Order theory Combinatorics_sentence_67

Order theory is the study of partially ordered sets, both finite and infinite. Combinatorics_sentence_68

Various examples of partial orders appear in algebra, geometry, number theory and throughout combinatorics and graph theory. Combinatorics_sentence_69

Notable classes and examples of partial orders include lattices and Boolean algebras. Combinatorics_sentence_70

### Matroid theory Combinatorics_section_9

Main article: Matroid theory Combinatorics_sentence_71

Matroid theory abstracts part of geometry. Combinatorics_sentence_72

It studies the properties of sets (usually, finite sets) of vectors in a vector space that do not depend on the particular coefficients in a linear dependence relation. Combinatorics_sentence_73

Not only the structure but also enumerative properties belong to matroid theory. Combinatorics_sentence_74

Matroid theory was introduced by Hassler Whitney and studied as a part of order theory. Combinatorics_sentence_75

It is now an independent field of study with a number of connections with other parts of combinatorics. Combinatorics_sentence_76

### Extremal combinatorics Combinatorics_section_10

Main article: Extremal combinatorics Combinatorics_sentence_77

Extremal combinatorics studies extremal questions on set systems. Combinatorics_sentence_78

The types of questions addressed in this case are about the largest possible graph which satisfies certain properties. Combinatorics_sentence_79

For example, the largest triangle-free graph on 2n vertices is a complete bipartite graph Kn,n. Combinatorics_sentence_80

Often it is too hard even to find the extremal answer f(n) exactly and one can only give an asymptotic estimate. Combinatorics_sentence_81

Ramsey theory is another part of extremal combinatorics. Combinatorics_sentence_82

It states that any sufficiently large configuration will contain some sort of order. Combinatorics_sentence_83

It is an advanced generalization of the pigeonhole principle. Combinatorics_sentence_84

### Probabilistic combinatorics Combinatorics_section_11

Main article: Probabilistic method Combinatorics_sentence_85

In probabilistic combinatorics, the questions are of the following type: what is the probability of a certain property for a random discrete object, such as a random graph? Combinatorics_sentence_86

For instance, what is the average number of triangles in a random graph? Combinatorics_sentence_87

Probabilistic methods are also used to determine the existence of combinatorial objects with certain prescribed properties (for which explicit examples might be difficult to find), simply by observing that the probability of randomly selecting an object with those properties is greater than 0. Combinatorics_sentence_88

This approach (often referred to as the probabilistic method) proved highly effective in applications to extremal combinatorics and graph theory. Combinatorics_sentence_89

A closely related area is the study of finite Markov chains, especially on combinatorial objects. Combinatorics_sentence_90

Here again probabilistic tools are used to estimate the mixing time. Combinatorics_sentence_91

Often associated with Paul Erdős, who did the pioneering work on the subject, probabilistic combinatorics was traditionally viewed as a set of tools to study problems in other parts of combinatorics. Combinatorics_sentence_92

However, with the growth of applications to analyze algorithms in computer science, as well as classical probability, additive number theory, and probabilistic number theory, the area recently grew to become an independent field of combinatorics. Combinatorics_sentence_93

### Algebraic combinatorics Combinatorics_section_12

Main article: Algebraic combinatorics Combinatorics_sentence_94

Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra. Combinatorics_sentence_95

Algebraic combinatorics is continuously expanding its scope, in both topics and techniques, and can be seen as the area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant. Combinatorics_sentence_96

### Combinatorics on words Combinatorics_section_13

Main article: Combinatorics on words Combinatorics_sentence_97

Combinatorics on words deals with formal languages. Combinatorics_sentence_98

It arose independently within several branches of mathematics, including number theory, group theory and probability. Combinatorics_sentence_99

It has applications to enumerative combinatorics, fractal analysis, theoretical computer science, automata theory, and linguistics. Combinatorics_sentence_100

While many applications are new, the classical Chomsky–Schützenberger hierarchy of classes of formal grammars is perhaps the best-known result in the field. Combinatorics_sentence_101

### Geometric combinatorics Combinatorics_section_14

Main article: Geometric combinatorics Combinatorics_sentence_102

Geometric combinatorics is related to convex and discrete geometry, in particular polyhedral combinatorics. Combinatorics_sentence_103

It asks, for example, how many faces of each dimension a convex polytope can have. Combinatorics_sentence_104

Metric properties of polytopes play an important role as well, e.g. the Cauchy theorem on the rigidity of convex polytopes. Combinatorics_sentence_105

Special polytopes are also considered, such as permutohedra, associahedra and Birkhoff polytopes. Combinatorics_sentence_106

Combinatorial geometry is an old fashioned name for discrete geometry. Combinatorics_sentence_107

### Topological combinatorics Combinatorics_section_15

Main article: Topological combinatorics Combinatorics_sentence_108

Combinatorial analogs of concepts and methods in topology are used to study graph coloring, fair division, partitions, partially ordered sets, decision trees, necklace problems and discrete Morse theory. Combinatorics_sentence_109

It should not be confused with combinatorial topology which is an older name for algebraic topology. Combinatorics_sentence_110

### Arithmetic combinatorics Combinatorics_section_16

Main article: Arithmetic combinatorics Combinatorics_sentence_111

Arithmetic combinatorics arose out of the interplay between number theory, combinatorics, ergodic theory, and harmonic analysis. Combinatorics_sentence_112

It is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division). Combinatorics_sentence_113

Additive number theory (sometimes also called additive combinatorics) refers to the special case when only the operations of addition and subtraction are involved. Combinatorics_sentence_114

One important technique in arithmetic combinatorics is the ergodic theory of dynamical systems. Combinatorics_sentence_115

### Infinitary combinatorics Combinatorics_section_17

Main article: Infinitary combinatorics Combinatorics_sentence_116

Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. Combinatorics_sentence_117

It is a part of set theory, an area of mathematical logic, but uses tools and ideas from both set theory and extremal combinatorics. Combinatorics_sentence_118

Gian-Carlo Rota used the name continuous combinatorics to describe geometric probability, since there are many analogies between counting and measure. Combinatorics_sentence_119

## Related fields Combinatorics_section_18

### Combinatorial optimization Combinatorics_section_19

Combinatorial optimization is the study of optimization on discrete and combinatorial objects. Combinatorics_sentence_120

It started as a part of combinatorics and graph theory, but is now viewed as a branch of applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. Combinatorics_sentence_121

### Coding theory Combinatorics_section_20

Coding theory started as a part of design theory with early combinatorial constructions of error-correcting codes. Combinatorics_sentence_122

The main idea of the subject is to design efficient and reliable methods of data transmission. Combinatorics_sentence_123

It is now a large field of study, part of information theory. Combinatorics_sentence_124

### Discrete and computational geometry Combinatorics_section_21

Discrete geometry (also called combinatorial geometry) also began as a part of combinatorics, with early results on convex polytopes and kissing numbers. Combinatorics_sentence_125

With the emergence of applications of discrete geometry to computational geometry, these two fields partially merged and became a separate field of study. Combinatorics_sentence_126

There remain many connections with geometric and topological combinatorics, which themselves can be viewed as outgrowths of the early discrete geometry. Combinatorics_sentence_127

### Combinatorics and dynamical systems Combinatorics_section_22

Combinatorial aspects of dynamical systems is another emerging field. Combinatorics_sentence_128

Here dynamical systems can be defined on combinatorial objects. Combinatorics_sentence_129

See for example graph dynamical system. Combinatorics_sentence_130

### Combinatorics and physics Combinatorics_section_23

There are increasing interactions between combinatorics and physics, particularly statistical physics. Combinatorics_sentence_131

Examples include an exact solution of the Ising model, and a connection between the Potts model on one hand, and the chromatic and Tutte polynomials on the other hand. Combinatorics_sentence_132