Not to be confused with Combinatoriality.
"Combinatorial" redirects here.
For combinatorial logic in computer science, see Combinatorial logic.
The full scope of combinatorics is not universally agreed upon.
According to H.J. , a definition of the subject is difficult because it crosses so many mathematical subdivisions. Ryser
Insofar as an area can be described by the types of problems it addresses, combinatorics is involved with
- the enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems,
- the existence of such structures that satisfy certain given criteria,
- the construction of these structures, perhaps in many ways, and
- optimization, finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some other optimality criterion.
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."
One way to define combinatorics is, perhaps, to describe its subdivisions with their problems and techniques.
This is the approach that is used below.
However, there are also purely historical reasons for including or not including some topics under the combinatorics umbrella.
Combinatorics is well known for the breadth of the problems it tackles.
Many combinatorial questions have historically been considered in isolation, giving an ad hoc solution to a problem arising in some mathematical context.
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.
One of the oldest and most accessible parts of combinatorics is graph theory, which by itself has numerous natural connections to other areas.
Combinatorics is used frequently in computer science to obtain formulas and estimates in the analysis of algorithms.
A mathematician who studies combinatorics is called a combinatorialist.
Main article: History of combinatorics
Basic combinatorial concepts and enumerative results appeared throughout the ancient world.
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.
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.
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.
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.
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.
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.
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.
Approaches and subfields of combinatorics
Main article: Enumerative combinatorics
Enumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects.
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.
Fibonacci numbers is the basic example of a problem in enumerative combinatorics.
Main article: Analytic combinatorics
Main article: Partition theory
Main article: Graph theory
Graphs are fundamental objects in combinatorics.
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?).
Although there are very strong connections between graph theory and combinatorics, they are sometimes thought of as separate subjects.
While combinatorial methods apply to many graph theory problems, the two disciplines are generally used to seek solutions to different types of problems.
Main article: Combinatorial design
Block designs are combinatorial designs of a special type.
This area is one of the oldest parts of combinatorics, such as in Kirkman's schoolgirl problem proposed in 1850.
The area has further connections to coding theory and geometric combinatorics.
Main article: Finite geometry
Finite geometry is the study of geometric systems having only a finite number of points.
This area provides a rich source of examples for design theory.
It should not be confused with discrete geometry (combinatorial geometry).
Main article: Order theory
Order theory is the study of partially ordered sets, both finite and infinite.
Various examples of partial orders appear in algebra, geometry, number theory and throughout combinatorics and graph theory.
Main article: Matroid theory
Matroid theory abstracts part of geometry.
Not only the structure but also enumerative properties belong to matroid theory.
Matroid theory was introduced by Hassler Whitney and studied as a part of order theory.
It is now an independent field of study with a number of connections with other parts of combinatorics.
Main article: Extremal combinatorics
Extremal combinatorics studies extremal questions on set systems.
The types of questions addressed in this case are about the largest possible graph which satisfies certain properties.
Often it is too hard even to find the extremal answer f(n) exactly and one can only give an asymptotic estimate.
Ramsey theory is another part of extremal combinatorics.
It states that any sufficiently large configuration will contain some sort of order.
It is an advanced generalization of the pigeonhole principle.
Main article: Probabilistic method
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?
For instance, what is the average number of triangles in a random graph?
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.
This approach (often referred to as the probabilistic method) proved highly effective in applications to extremal combinatorics and graph theory.
A closely related area is the study of finite Markov chains, especially on combinatorial objects.
Here again probabilistic tools are used to estimate the mixing time.
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.
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.
Main article: Algebraic combinatorics
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.
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 on words
Main article: Combinatorics on words
Combinatorics on words deals with formal languages.
Main article: Geometric combinatorics
It asks, for example, how many faces of each dimension a convex polytope can have.
Combinatorial geometry is an old fashioned name for discrete geometry.
Main article: Topological combinatorics
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.
Main article: Arithmetic combinatorics
It is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division).
Additive number theory (sometimes also called additive combinatorics) refers to the special case when only the operations of addition and subtraction are involved.
Main article: Infinitary combinatorics
Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets.
Combinatorial optimization is the study of optimization on discrete and combinatorial objects.
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.
The main idea of the subject is to design efficient and reliable methods of data transmission.
It is now a large field of study, part of information theory.
Discrete and computational geometry
With the emergence of applications of discrete geometry to computational geometry, these two fields partially merged and became a separate field of study.
There remain many connections with geometric and topological combinatorics, which themselves can be viewed as outgrowths of the early discrete geometry.
Combinatorics and dynamical systems
Combinatorial aspects of dynamical systems is another emerging field.
Here dynamical systems can be defined on combinatorial objects.
See for example graph dynamical system.
Combinatorics and physics
Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Combinatorics.