Combinatorics is a branch of
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
concerning the study of finite or
countableIn mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
discreteDiscrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...
structuresIn mathematics, a structure on a set, or more generally a type, consists of additional mathematical objects that in some manner attach to the set, making it easier to visualize or work with, or endowing the collection with meaning or significance....
. Aspects of combinatorics include counting the structures of a given kind and size (
enumerative combinatoricsEnumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations...
), deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria (as in
combinatorial designsCombinatorial design theory is the part of combinatorial mathematics that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties....
and matroidIn combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
theory), finding "largest", "smallest", or "optimal" objects (
extremal combinatoricsExtremal combinatorics is a field of combinatorics, which is itself a part of mathematics. Extremal combinatorics studies how large or how small a collection of finite objects can be, if it has to satisfy certain restrictions.For example, how many people can we invite to a party where among each...
and
combinatorial optimizationIn applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
), and studying combinatorial structures arising in an
algebraAlgebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
ic context, or applying algebraic techniques to combinatorial problems (
algebraic combinatoricsAlgebraic 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....
).
Combinatorial problems arise in many areas of pure mathematics, notably in
algebraAlgebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
,
probability theoryProbability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
,
topologyTopology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
, and
geometryGeometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
, and combinatorics also has many applications in
optimizationIn mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
,
computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
,
ergodic theoryErgodic theory is a branch of mathematics that studies dynamical systems with an invariant measure and related problems. Its initial development was motivated by problems of statistical physics....
and
statistical physicsStatistical physics is the branch of physics that uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approximations, in solving physical problems. It can describe a wide variety of fields with an inherently stochastic...
. 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 theoryIn mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, which also has numerous natural connections to other areas. Combinatorics is used frequently in
computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
to obtain formulas and estimates in the
analysis of algorithmsTo analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
.
A
mathematicianA mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
who studies combinatorics is called a
combinatorialist.
History
Basic combinatorial concepts and enumerative results appeared throughout the
ancient worldAncient history is the study of the written past from the beginning of recorded human history to the Early Middle Ages. The span of recorded history is roughly 5,000 years, with Cuneiform script, the oldest discovered form of coherent writing, from the protoliterate period around the 30th century BC...
. In 6th century BCE,
physicianA physician is a health care provider who practices the profession of medicine, which is concerned with promoting, maintaining or restoring human health through the study, diagnosis, and treatment of disease, injury and other physical and mental impairments...
Sushruta asserts in
Sushruta SamhitaThe Sushruta Samhita is a Sanskrit text, attributed to one Sushruta, foundational to Ayurvedic medicine , with innovative chapters on surgery....
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
6-1 possibilities.
RomanAncient Rome was a thriving civilization that grew on the Italian Peninsula as early as the 8th century BC. Located along the Mediterranean Sea and centered on the city of Rome, it expanded to one of the largest empires in the ancient world....
historianA historian is a person who studies and writes about the past and is regarded as an authority on it. Historians are concerned with the continuous, methodical narrative and research of past events as relating to the human race; as well as the study of all history in time. If the individual is...
PlutarchPlutarch then named, on his becoming a Roman citizen, Lucius Mestrius Plutarchus , c. 46 – 120 AD, was a Greek historian, biographer, essayist, and Middle Platonist known primarily for his Parallel Lives and Moralia...
discusses an argument between
ChrysippusChrysippus of Soli was a Greek Stoic philosopher. He was a native of Soli, Cilicia, but moved to Athens as a young man, where he became a pupil of Cleanthes in the Stoic school. When Cleanthes died, around 230 BC, Chrysippus became the third head of the school...
(3rd century BCE) and
HipparchusHipparchus, the common Latinization of the Greek Hipparkhos, can mean:* Hipparchus, the ancient Greek astronomer** Hipparchic cycle, an astronomical cycle he created** Hipparchus , a lunar crater named in his honour...
(2nd century BCE) of a rather delicate enumerative problem, which was later shown to be related to
Schröder numbersIn mathematics, a Schröder number describes the number of paths from the southwest corner of an n × n grid to the northeast corner , using only single steps north, northeast, or east, that do not rise above the SW–NE diagonal.The first few Schröder numbers are-Examples:The following...
. In the
OstomachionOstomachion, also known as loculus Archimedius and also as syntomachion, is a mathematical treatise attributed to Archimedes. This work has survived fragmentarily in an Arabic version and in a copy of the original ancient Greek text made in Byzantine times...
,
ArchimedesArchimedes of Syracuse was a Greek mathematician, physicist, engineer, inventor, and astronomer. Although few details of his life are known, he is regarded as one of the leading scientists in classical antiquity. Among his advances in physics are the foundations of hydrostatics, statics and an...
(3rd century BCE)
considers a
tiling puzzleTiling puzzles are puzzles involving two-dimensional packing problems in which a number of flat shapes have to be assembled into a larger given shape without overlaps . Some tiling puzzles ask you to dissect a given shape first and then rearrange the pieces into another shape...
.
In the
Middle AgesThe Middle Ages is a periodization of European history from the 5th century to the 15th century. The Middle Ages follows the fall of the Western Roman Empire in 476 and precedes the Early Modern Era. It is the middle period of a three-period division of Western history: Classic, Medieval and Modern...
, combinatorics continued to be studied, largely outside of the European civilization. Notably, an
IndiaIndia , officially the Republic of India , is a country in South Asia. It is the seventh-largest country by geographical area, the second-most populous country with over 1.2 billion people, and the most populous democracy in the world...
n mathematician
MahaviraMahavira was a 9th-century Indian Jain mathematician from Gulbarga who asserted that the square root of a negative number did not exist. He gave the sum of a series whose terms are squares of an arithmetical progression and empirical rules for area and perimeter of an ellipse. He was patronised by...
(c. 850) provided the general formulae for the number of permutations and combinations. The philosopher and
astronomerAn astronomer is a scientist who studies celestial bodies such as planets, stars and galaxies.Historically, astronomy was more concerned with the classification and description of phenomena in the sky, while astrophysics attempted to explain these phenomena and the differences between them using...
Rabbi
Abraham ibn EzraRabbi Abraham ben Meir Ibn Ezra was born at Tudela, Navarre in 1089, and died c. 1167, apparently in Calahorra....
(c. 1140) established the symmetry of
binomial coefficientsIn mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...
, while a closed formula was obtained later by the talmudist and
mathematicianA mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
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 triangleIn mathematics, Pascal's triangle is a triangular array of the binomial coefficients in a triangle. It is named after the French mathematician, Blaise Pascal...
. Later, in Medieval England,
campanologyCampanology is the study of bells. It encompasses the physical realities of bells — how they are cast, tuned and sounded — as well as the various methods devised to perform bell-ringing....
provided examples of what is now known as Hamiltonian cycles in certain
Cayley graphsIn mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
on permutations.
During the
RenaissanceThe Renaissance was a cultural movement that spanned roughly the 14th to the 17th century, beginning in Italy in the Late Middle Ages and later spreading to the rest of Europe. The term is also used more loosely to refer to the historical era, but since the changes of the Renaissance were not...
, together with the rest of mathematics and the
sciencesScience is a systematic enterprise that builds and organizes knowledge in the form of testable explanations and predictions about the universe...
, combinatorics enjoyed a rebirth. Works of
Pascal Blaise Pascal , was a French mathematician, physicist, inventor, writer and Catholic philosopher. He was a child prodigy who was educated by his father, a tax collector in Rouen...
,
NewtonSir Isaac Newton PRS was an English physicist, mathematician, astronomer, natural philosopher, alchemist, and theologian, who has been "considered by many to be the greatest and most influential scientist who ever lived."...
, Jacob Bernoulli and Euler became foundational in the emerging field. In the modern times, the works by
J. J. SylvesterJames Joseph Sylvester was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory and combinatorics...
(late 19th century) and
Percy MacMahonPercy Alexander MacMahon was a mathematician, especially noted in connection with the partitions of numbers and enumerative combinatorics.-Early life:...
(early 20th century) laid the foundation for
enumerativeEnumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations...
and
algebraic combinatoricsAlgebraic 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....
.
Graph theoryIn mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
also enjoyed an explosion of interest at the same time, especially in connection with the four color problem.
In the second half of 20th century, combinatorics enjoyed a rapid growth, which led to establishment of dozens of new journals and conferences in the subject. 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. 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.
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 problemA mathematical problem is a problem that is amenable to being represented, analyzed, and possibly solved, with the methods of mathematics. This can be a real-world problem, such as computing the orbits of the planets in the solar system, or a problem of a more abstract nature, such as Hilbert's...
, 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. The
twelvefold wayIn combinatorics, the twelvefold way is a name given to a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number...
provides a unified framework for counting permutations, combinations and
partitionsIn mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
.
Analytic combinatorics
Analytic combinatorics concerns the enumeration of combinatorial structures using tools from
complex analysisComplex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates functions of complex numbers. It is useful in many branches of mathematics, including number theory and applied mathematics; as well as in physics,...
and
probability theoryProbability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
. In contrast with enumerative combinatorics which uses explicit combinatorial formulae and generating functions to describe the results, analytic combinatorics aims at obtaining
asymptotic formulaeIn mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...
.
Partition theory
Partition theory studies various enumeration and asymptotic problems related to integer partitions, and is closely related to q-series,
special functionsSpecial functions are particular mathematical functions which have more or less established names and notations due to their importance in mathematical analysis, functional analysis, physics, or other applications....
and
orthogonal polynomialsIn mathematics, the classical orthogonal polynomials are the most widely used orthogonal polynomials, and consist of the Hermite polynomials, the Laguerre polynomials, the Jacobi polynomials together with their special cases the ultraspherical polynomials, the Chebyshev polynomials, and the...
. Originally a part of
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
and
analysisAnalysis is the process of breaking a complex topic or substance into smaller parts to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle , though analysis as a formal concept is a relatively recent development.The word is...
, it is now considered a part of combinatorics or an independent field. It incorporates the
bijective approachIn combinatorics, bijective proof is a proof technique that finds a bijective function f : A → B between two sets A and B, thus proving that they have the same number of elements, |A| = |B|. One place the technique is useful is where we wish to know the size of A, but can find no direct way of...
and various tools in analysis,
analytic number theoryIn mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Dirichlet's introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic...
, and has connections with
statistical mechanicsStatistical mechanics or statistical thermodynamicsThe terms statistical mechanics and statistical thermodynamics are used interchangeably...
.
Graph theory
Graphs are basic objects in combinatorics. The questions range from counting (e.g., the number of graphs on
n vertices with
k edges) to structural (e.g., which graphs contain Hamiltonian cycles) to algebraic questions (e.g., given a graph G and two numbers x and y, does the
Tutte polynomialThe Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a polynomial in two variables which plays an important role in graph theory, a branch of mathematics and theoretical computer science...
T
G(x,y) have a combinatorial interpretation?). It should be noted that while there are very strong connections between graph theory and combinatorics, these two are sometimes thought of as separate subjects.
Design theory
Design theory is a study of
combinatorial designsCombinatorial design theory is the part of combinatorial mathematics that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties....
, which are collections of subsets with certain intersection properties. 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 problemKirkman's schoolgirl problem is a problem in combinatorics proposed by Thomas Kirkman in 1850 as Query VI in The Lady's and Gentleman's Diary...
proposed in 1850. The solution of the problem is a special case of a
Steiner system250px|right|thumbnail|The [[Fano plane]] is an S Steiner triple system. The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line....
, which systems play an important role in the
classification of finite simple groupsIn mathematics, the classification of the finite simple groups is a theorem stating that every finite simple group belongs to one of four categories described below. These groups can be seen as the basic building blocks of all finite groups, in much the same way as the prime numbers are the basic...
. The area has further connections to coding theory and geometric combinatorics.
Finite geometry
Finite geometry is the study of
geometric systemsGeometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
having only a finite number of points. Structures analogous to those found in continuous geometries (Euclidean plane,
real projective spaceIn mathematics, real projective space, or RPn, is the topological space of lines through 0 in Rn+1. It is a compact, smooth manifold of dimension n, and a special case of a Grassmannian.-Construction:...
, etc.) but defined combinatorially are the main items studied. This area provides a rich source of examples for
Design theoryCombinatorial design theory is the part of combinatorial mathematics that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties....
. It should not be confused with Discrete geometry (Combinatorial geometry).
Order theory
Order theory is the study of partially ordered sets, both finite and infinite. Various examples of partial orders appear in
algebraAbstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
, geometry, number theory and throughout combinatorics and graph theory. Notable classes and examples of partial orders include
latticesIn mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
and Boolean algebras.
Matroid theory
Matroid theory abstracts part of
geometryGeometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
. It studies the properties of sets (usually, finite sets) of vectors in a
vector spaceA vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
that do not depend on the particular coefficients in a
linear dependenceIn linear algebra, a family of vectors is linearly independent if none of them can be written as a linear combination of finitely many other vectors in the collection. A family of vectors which is not linearly independent is called linearly dependent...
relation. Not only the structure but also enumerative properties belong to matroid theory. Matroid theory was introduced by
Hassler WhitneyHassler Whitney was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, and characteristic classes.-Work:...
and studied as a part of the order theory. It is now an independent field of study with a number of connections with other parts of combinatorics.
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. For example, the largest triangle-free graph on
2n vertices is a
complete bipartite graphIn the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
Kn,n. Often it is too hard even to find the extremal answer
f(
n) exactly and one can only give an
asymptotic estimateIn mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...
.
Ramsey theoryRamsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
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.
Probabilistic combinatorics
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 graphIn mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
? 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 methodThe probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the...
) 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 timeIn probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution.More precisely, a fundamental result about Markov chains is that a finite state irreducible aperiodic chain has a unique stationary distribution π and,...
.
Often associated with
Paul ErdősPaul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
, who did the pioneer 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
analysis of algorithmsTo analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
in
computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, as well as classical probability,
additiveIn number theory, the specialty additive number theory studies subsets of integers and their behavior under addition. More abstractly, the field of "additive number theory" includes the study of Abelian groups and commutative semigroups with an operation of addition. Additive number theory has...
and
probabilistic number theoryProbabilistic number theory is a subfield of number theory, which explicitly uses probability to answer questions of number theory. One basic idea underlying it is that different prime numbers are, in some serious sense, like independent random variables...
, the area recently grew to become an independent field of combinatorics.
Algebraic combinatorics
Algebraic combinatorics is an area of
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
that employs methods of
abstract algebraAbstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
, notably
group theoryIn mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
and
representation theoryRepresentation theory is a branch of mathematics that studies abstract algebraic structures by representing their elements as linear transformations of vector spaces, and studiesmodules over these abstract algebraic structures...
, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in
algebraAbstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
. Within the last decade or so, algebraic combinatorics came to be seen more expansively as the area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant. One of the fastest developing subfields within algebraic combinatorics is
combinatorial commutative algebraCombinatorial commutative algebra is a relatively new, rapidly developing mathematical discipline. As the name implies, it lies at the intersection of two more established fields, commutative algebra and combinatorics, and frequently uses methods of one to address problems arising in the other...
.
Combinatorics on words
Combinatorics on words deals with
formal languagesA formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
. It arose independently within several branches of mathematics, including
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
,
group theoryIn mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
and
probabilityProbability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
. It has applications to enumerative combinatorics,
fractal analysisFractal analysis is the modelling of data by fractals.It consists of methods to assign a fractal dimension and other fractal characteristics to a signal, dataset or object which may be sound, images, molecules, networks or other data....
,
theoretical computer scienceTheoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
,
automata theoryIn theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
and
linguisticsLinguistics is the scientific study of human language. Linguistics can be broadly broken into three categories or subfields of study: language form, language meaning, and language in context....
. While many applications are new, the classical Chomsky–Schützenberger hierarchy of classes of
formal grammarsA formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
is perhaps the best known result in the field.
Geometric combinatorics
Geometric combinatorics is related to
convexConvex geometry is the branch of geometry studying convex sets, mainly in Euclidean space.Convex sets occur naturally in many areas of mathematics: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of numbers, integral geometry, linear programming,...
and
discrete geometryDiscrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles,...
, in particular
polyhedral combinatoricsPolyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher dimensional convex polytopes....
. It asks, for example, how many faces of each dimension can a
convex polytopeA convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn...
have. Metric properties of polytopes play an important role as well, e.g. the
Cauchy theoremCauchy's theorem is a theorem in geometry, named after Augustin Cauchy. It states thatconvex polytopes in three dimensions with congruent corresponding faces must be congruent to each other...
on rigidity of convex polytopes. Special polytopes are also considered, such as
permutohedraIn mathematics, the permutohedron of order n is an -dimensional polytope embedded in an n-dimensional space, the vertices of which are formed by permuting the coordinates of the vector .-History:According to , permutohedra were first studied by...
,
associahedraIn mathematics, an associahedron or Stasheff polytope Kn is a convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a word of n letters and the edges correspond to single application of the associativity rule.Initially Jim Stasheff...
and
Birkhoff polytopes. We should note that combinatorial geometry is an old fashioned name for discrete geometry.
Topological combinatorics
Combinatorial analogs of concepts and methods in
topologyTopology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
are used to study
graph coloringIn graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
,
fair divisionFair division, also known as the cake-cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received a fair amount...
,
partitionsIn mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
,
partially ordered setsIn mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
,
decision treesA decision tree is a decision support tool that uses a tree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm. Decision trees are commonly used in operations research, specifically...
,
necklace problemsThe necklace problem is a problem in recreational mathematics, solved in the early 21st century.- Formulation :Suppose that a person you are in contact with has a necklace of n beads, each of which is either black or white. You wish to identify the order in which the n beads go around the...
and
discrete Morse theory. It should not be confused with
combinatorial topologyIn mathematics, combinatorial topology was an older name for algebraic topology, dating from the time when topological invariants of spaces were regarded as derived from combinatorial decompositions such as simplicial complexes...
which is an older name for
algebraic topologyAlgebraic topology is a branch of mathematics which uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariants that classify topological spaces up to homeomorphism, though usually most classify up to homotopy equivalence.Although algebraic topology...
.
Arithmetic combinatorics
Arithmetic combinatorics arose out of the interplay between
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, combinatorics,
ergodic theoryErgodic theory is a branch of mathematics that studies dynamical systems with an invariant measure and related problems. Its initial development was motivated by problems of statistical physics....
and
harmonic analysisHarmonic analysis is the branch of mathematics that studies the representation of functions or signals as the superposition of basic waves. It investigates and generalizes the notions of Fourier series and Fourier transforms...
. It is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division).
Additive combinatorics refers to the special case when only the operations of addition and subtraction are involved. One important technique in arithmetic combinatorics is the
ergodic theoryErgodic theory is a branch of mathematics that studies dynamical systems with an invariant measure and related problems. Its initial development was motivated by problems of statistical physics....
of
dynamical systemsA dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...
.
Infinitary combinatorics
Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. It is a part of
set theorySet theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, an area of
mathematical logicMathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, but uses tools and ideas from both set theory and extremal combinatorics.
Gian-Carlo RotaGian-Carlo Rota was an Italian-born American mathematician and philosopher.-Life:Rota was born in Vigevano, Italy...
used the name
continuous combinatorics to describe
probabilityProbability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
and measure theory, since there are many analogies between
counting and
measure.
Related fields
Combinatorial optimization
Combinatorial optimizationIn applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
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 researchOperations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
,
algorithm theoryTo analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
and
computational complexity theoryComputational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
.
Coding theory
Coding theoryCoding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
started as a part of design theory with early combinatorial constructions of error-correcting codes. 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 theoryInformation theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...
.
Discrete and computational geometry
Discrete geometryDiscrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles,...
(also called combinatorial geometry) also began a part of combinatorics, with early results on
convex polytopesA convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn...
and kissing numbers. With the emergence of applications of discrete geometry to
computational geometryComputational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, 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 systemsThe mathematical disciplines of combinatorics and dynamical systems interact in a number of ways. The ergodic theory of dynamical systems has recently been used to prove combinatorial theorems about number theory which has given rise to the field of arithmetic combinatorics. Also dynamical systems...
is another emerging field. Here dynamical systems can be defined on combinatorial objects. See for example
graph dynamical systemIn mathematics, the concept of graph dynamical systems can be used to capture a wide range of processes taking place on graphs or networks. A major theme in the mathematical and computational analysis of GDSs is to relate their structural properties and the global dynamics that result.The work on...
.
Combinatorics and physics
There are increasing interactions between
combinatorics and physicsCombinatorial physics or physical combinatorics is the area of interaction between physics and combinatorics."Combinatorial Physics is an emerging area which unites combinatorial and discrete mathematical techniques applied to theoretical physics, especially Quantum Theory."."Physical combinatorics...
, particularly
statistical physicsStatistical physics is the branch of physics that uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approximations, in solving physical problems. It can describe a wide variety of fields with an inherently stochastic...
. Examples include an exact solution of the
Ising modelThe Ising model is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables called spins that can be in one of two states . The spins are arranged in a graph , and each spin interacts with its nearest neighbors...
, and a connection between the
Potts modelIn statistical mechanics, the Potts model, a generalization of the Ising model, is a model of interacting spins on a crystalline lattice. By studying the Potts model, one may gain insight into the behaviour of ferromagnets and certain other phenomena of solid state physics...
on one hand, and the
chromaticThe chromatic polynomial is a polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to attack the four color problem. It was generalised to the Tutte...
and
Tutte polynomialsThe Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a polynomial in two variables which plays an important role in graph theory, a branch of mathematics and theoretical computer science...
on the other hand.
See also
- Combinatorial biology
In biotechnology, combinatorial biology is the creation of a large number of compounds through technologies such as phage display. Similar to combinatorial chemistry, compounds are produced by biosynthesis rather than organic chemistry. This process was developed independently by Richard A....
- Combinatorial chemistry
Combinatorial chemistry involves the rapid synthesis or the computer simulation of a large number of different but structurally related molecules or materials...
- Combinatorial data analysis
Combinatorial data analysis is the study of data sets where the arrangement of objects is important. CDA can be used either to determine how well a given combinatorial construct reflects the observed data, or to search for a suitable combinatorial construct that does fit the data.-See...
- Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
- Combinatorial group theory
In mathematics, combinatorial group theory is the theory of free groups, and the concept of a presentation of a group by generators and relations...
- Phylogenetics
In biology, phylogenetics is the study of evolutionary relatedness among groups of organisms , which is discovered through molecular sequencing data and morphological data matrices...
- List of combinatorics topics
External links
- Combinatorics, a MathWorld
MathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at...
article with many references.
- Combinatorics, from a MathPages.com portal.
- The Hyperbook of Combinatorics, a collection of math articles links.
- The Two Cultures of Mathematics by W. T. Gowers, article on problem solving vs theory building