combinatorics
   HOME

TheInfoList



OR:

Combinatorics is an area of
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
primarily concerned with
counting Counting is the process of determining the number of Element (mathematics), elements of a finite set of objects, i.e., determining the size (mathematics), size of a set. The traditional way of counting consists of continually increasing a (mental ...
, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from
logic Logic is the study of correct reasoning. It includes both Mathematical logic, formal and informal logic. Formal logic is the science of Validity (logic), deductively valid inferences or of logical truths. It is a formal science investigating h ...
to
statistical physics Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the Mathematics, mathematical tools for dealing with large populations ...
and from
evolutionary biology Evolutionary biology is the subfield of biology that studies the evolution, evolutionary processes (natural selection, common descent, speciation) that produced the Biodiversity, diversity of life on Earth. It is also defined as the study of ...
to
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
. Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of
pure mathematics Pure mathematics is the study of mathematical concepts independently of any application outside mathematics. These concepts may originate in real-world concerns, and the results obtained may later turn out to be useful for practical applications, ...
, notably in
algebra Algebra () is one of the areas of mathematics, broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathem ...
,
probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
,
topology In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...
, and
geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ca ...
, as well as in its many application areas. 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 In mathematics, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph theory), vertices'' ( ...
, 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 In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a Function (mathem ...
. A
mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...
who studies combinatorics is called a '.


Definition

The full scope of combinatorics is not universally agreed upon. According to H.J. Ryser, a definition of the subject is difficult because it crosses so many mathematical subdivisions. 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. Although primarily concerned with finite systems, some combinatorial questions and techniques can be extended to an infinite (specifically,
countable In mathematics, a Set (mathematics), set is countable if either it is finite set, finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function fro ...
) but discrete setting.


History

Basic combinatorial concepts and enumerative results appeared throughout the
ancient world Ancient history is a time period from the beginning of writing and recorded human history Human history, also called world history, is the narrative of humanity's past. It is understood and studied through anthropology, archaeolog ...
. In the 6th century BCE, ancient Indian
physician A physician (American English), medical practitioner (English in the Commonwealth of Nations, Commonwealth English), medical doctor, or simply doctor, is a health professional who practices medicine, which is concerned with promoting, mai ...
Sushruta Sushruta, or ''Suśruta'' (Sanskrit: सुश्रुत, IAST: , ) was an ancient Indian physician. The ''Sushruta Samhita'' (''Sushruta's Compendium''), a treatise ascribed to him, is one of the most important surviving ancient treatises on ...
asserts in
Sushruta Samhita The ''Sushruta Samhita'' (सुश्रुतसंहिता, IAST: ''Suśrutasaṃhitā'', literally "Suśruta's Compendium") is an ancient Sanskrit text on medicine and surgery, and one of the most important such treatises on this subje ...
that 63 combinations can be made out of 6 different tastes, taken one at a time, two at a time, etc., thus computing all 26 − 1 possibilities.
Greek Greek may refer to: Greece Anything of, from, or related to Greece, a country in Southern Europe: *Greeks, an ethnic group. *Greek language, a branch of the Indo-European language family. **Proto-Greek language, the assumed last common ancestor ...
historian A 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 st ...
Plutarch Plutarch (; grc-gre, Πλούταρχος, ''Ploútarchos''; ; – after AD 119) was a Greek people, Greek Middle Platonism, Middle Platonist philosopher, historian, Biography, biographer, essayist, and priest at the Temple of Apollo (D ...
discusses an argument between
Chrysippus Chrysippus of Soli (; grc-gre, Χρύσιππος ὁ Σολεύς, ; ) was a Ancient Greece, Greek Stoicism, Stoic Philosophy, philosopher. He was a native of Soli, Cilicia, but moved to Athens as a young man, where he became a pupil of the S ...
(3rd century BCE) and
Hipparchus Hipparchus (; el, wikt:Ἵππαρχος, Ἵππαρχος, ''Hipparkhos'';  BC) was a Ancient astronomy, Greek astronomer, geographer, and mathematician. He is considered the founder of trigonometry, but is most famous for his incidenta ...
(2nd century BCE) of a rather delicate enumerative problem, which was later shown to be related to Schröder–Hipparchus numbers. Earlier, in the '' Ostomachion'',
Archimedes Archimedes of Syracuse (;; ) was a Greek mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, ...
(3rd century BCE) may have considered the number of configurations of a tiling puzzle, while combinatorial interests possibly were present in lost works by Apollonius. In the
Middle Ages In the history of Europe, the Middle Ages or medieval period lasted approximately from the late 5th to the late 15th centuries, similar to the Post-classical, post-classical period of World history (field), global history. It began with t ...
, combinatorics continued to be studied, largely outside of the European civilization. The
India India, officially the Republic of India (Hindi: ), is a country in South Asia. It is the List of countries and dependencies by area, seventh-largest country by area, the List of countries and dependencies by population, second-most populous ...
n mathematician
Mahāvīra Mahavira (Sanskrit: महावीर) also known as Vardhaman, was the 24th ''tirthankara'' (supreme preacher) of Jainism. He was the spiritual successor of the 23rd ''tirthankara'' Parshvanatha. Mahavira was born in the early part of the 6t ...
() provided formulae for the number of
permutation In mathematics, a permutation of a Set (mathematics), set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers ...
s and
combination In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...
s, and these formulas may have been familiar to Indian mathematicians as early as the 6th century CE. The
philosopher A philosopher is a person who practices or investigates philosophy Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and language. Suc ...
and
astronomer An astronomer is a scientist in the field of astronomy who focuses their studies on a specific question or field outside the scope of Earth. They observe astronomical objects such as stars, planets, natural satellite, moons, comets and galaxy, g ...
Rabbi Abraham ibn Ezra () established the symmetry of
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the ter ...
s, while a closed formula was obtained later by the talmudist and
mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...
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 mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although ot ...
. Later, in
Medieval England England in the Middle Ages concerns the history of England during the Middle Ages, medieval period, from the end of the 5th century through to the start of the Early modern Britain, Early Modern period in 1485. When England emerged from the coll ...
, campanology provided examples of what is now known as Hamiltonian cycles in certain
Cayley graph In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in m ...
s on permutations. During the
Renaissance The Renaissance ( , ) , from , with the same meanings. is a Periodization, period in History of Europe, European history marking the transition from the Middle Ages to modernity and covering the 15th and 16th centuries, characterized by an e ...
, together with the rest of mathematics and the
science Science is a systematic endeavor that Scientific method, builds and organizes knowledge in the form of Testability, testable explanations and predictions about the universe. Science may be as old as the human species, and some of the earli ...
s, combinatorics enjoyed a rebirth. Works of Pascal, Newton, Jacob Bernoulli and
Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
became foundational in the emerging field. In modern times, the works of J.J. Sylvester (late 19th century) and Percy MacMahon (early 20th century) helped lay the foundation for enumerative and
algebraic combinatorics Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorics, combinatorial contexts and, conversely, applies combinatorial techniques to pr ...
.
Graph theory In mathematics, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph theory), vertices'' ( ...
also enjoyed an increase of interest at the same time, especially in connection with the four color problem. 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. In part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, from
functional analysis Functional analysis is a branch of mathematical analysis Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, ...
to
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative intege ...
, 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.


Approaches and subfields of combinatorics


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 A mathematical problem is a problem that can be Representation (mathematics), represented, analyzed, and possibly solved, with the methods of mathematics. This can be a real-world problem, such as computing the Orbit#Planetary orbits, orbits of the ...
, many of the problems that arise in applications have a relatively simple combinatorial description.
Fibonacci numbers In mathematics, the Fibonacci numbers, commonly denoted , form a integer sequence, sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start ...
is the basic example of a problem in enumerative combinatorics. The
twelvefold way In combinatorics, the twelvefold way is 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 ...
provides a unified framework for counting permutations, combinations and partitions.


Analytic combinatorics

Analytic combinatorics concerns the enumeration of combinatorial structures using tools from
complex analysis Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates Function (mathematics), functions of complex numbers. It is helpful in many branches of mathemati ...
and
probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
. In contrast with enumerative combinatorics, which uses explicit combinatorial formulae and generating functions to describe the results, analytic combinatorics aims at obtaining asymptotic formulae.


Partition theory

Partition theory studies various enumeration and asymptotic problems related to integer partitions, and is closely related to
q-series In mathematics, mathematical area of combinatorics, the ''q''-Pochhammer symbol, also called the ''q''-shifted factorial, is the product (a;q)_n = \prod_^ (1-aq^k)=(1-a)(1-aq)(1-aq^2)\cdots(1-aq^), with (a;q)_0 = 1. It is a q-analog, ''q''-analog ...
, special functions and orthogonal polynomials. Originally a part of
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative intege ...
and
analysis Analysis (plural, : analyses) is the process of breaking a complexity, complex topic or Substance theory, substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics a ...
, it is now considered a part of combinatorics or an independent field. It incorporates the bijective approach and various tools in analysis and
analytic number theory In 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 Peter Gustav Lejeune Dirichlet's 1837 introduction of Dirich ...
and has connections with
statistical mechanics In physics Physics is the natural science that studies matter, its Elementary particle, fundamental constituents, its motion and behavior through Spacetime, space and time, and the related entities of energy and force. "Physical scien ...
. Partitions can be graphically visualized with Young diagrams or Ferrers diagrams. They occur in a number of branches of
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
physics Physics is the natural science that studies matter, its Elementary particle, fundamental constituents, its motion and behavior through Spacetime, space and time, and the related entities of energy and force. "Physical science is that depar ...
, including the study of symmetric polynomials and of the
symmetric group In abstract algebra, the symmetric group defined over any set (mathematics), set is the group (mathematics), group whose Element (mathematics), elements are all the bijections from the set to itself, and whose group operation is the function c ...
and in group representation theory in general.


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 ''T''''G''(''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.


Design theory

Design theory is a study of combinatorial designs, 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 problem proposed in 1850. 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 In mathematics, the classification of the finite simple groups is a result of group theory stating that every List of finite simple groups, finite simple group is either cyclic groups, cyclic, or alternating groups, alternating, or it belongs to ...
. The area has further connections to
coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied ...
and geometric combinatorics. Combinatorial design theory can be applied to the area of
design of experiments The design of experiments (DOE, DOX, or experimental design) is the design of any task that aims to describe and explain the variation of information under conditions that are hypothesized to reflect the variation. The term is generally associ ...
. Some of the basic theory of combinatorial designs originated in the statistician
Ronald Fisher Sir Ronald Aylmer Fisher (17 February 1890 – 29 July 1962) was a British polymath who was active as a mathematician, statistician, biologist, geneticist, and academic. For his work in statistics, he has been described as "a genius who a ...
's work on the design of biological experiments. Modern applications are also found in a wide gamut of areas including
finite geometry Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) Finite number may refer to: * A countable number less than infinity, being the cardinality of a finite set – i.e., some natural number In mathematics, th ...
, tournament scheduling, lotteries, mathematical chemistry, mathematical biology, algorithm design and analysis, networking, group testing and
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of ...
.


Finite geometry

Finite geometry is the study of geometric systems having only a finite number of points. Structures analogous to those found in continuous geometries (
Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometry, geometric setting in which two real number, real quantities are required to determine the position (geometry), position of each point (mathematics), ...
, real projective space, etc.) but defined combinatorially are the main items studied. This area provides a rich source of examples for design theory. It should not be confused with discrete geometry ( combinatorial geometry).


Order theory

Order theory is the study of
partially ordered sets In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
, both finite and infinite. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". Various examples of partial orders appear in
algebra Algebra () is one of the areas of mathematics, broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathem ...
, geometry, number theory and throughout combinatorics and graph theory. Notable classes and examples of partial orders include lattices and Boolean algebras.


Matroid theory

Matroid theory abstracts part of
geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ca ...
. It studies the properties of sets (usually, finite sets) of vectors in a
vector space In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
that do not depend on the particular coefficients in a
linear dependence In the theory of vector spaces, a set (mathematics), set of vector (mathematics), vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vec ...
relation. 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.


Extremal combinatorics

Extremal combinatorics studies how large or how small a collection of finite objects (
number A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers can ...
s, graphs, vectors, sets, etc.) can be, if it has to satisfy certain restrictions. Much of extremal combinatorics concerns classes of set systems; this is called extremal set theory. For instance, in an ''n''-element set, what is the largest number of ''k''-element
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s that can pairwise intersect one another? What is the largest number of subsets of which none contains any other? The latter question is answered by Sperner's theorem, which gave rise to much of extremal set theory. 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 graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex (graph theory), vertex of the first set is connected to every vertex of the second set..Electronic edition p ...
''Kn,n''. Often it is too hard even to find the extremal answer ''f''(''n'') exactly and one can only give an asymptotic estimate.
Ramsey theory Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...
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 In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there mu ...
.


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 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) 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 Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, as well as classical probability, additive number theory, and probabilistic number theory, the area recently grew to become an independent field of combinatorics.


Algebraic combinatorics

Algebraic combinatorics is an area of
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
that employs methods of
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathematics), fields, module (mathe ...
, notably
group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in
algebra Algebra () is one of the areas of mathematics, broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathem ...
. Algebraic combinatorics has come to be seen more expansively as an area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant. Thus the combinatorial topics may be enumerative in nature or involve
matroid In combinatorics 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 set, finite Mathematical structure, structures. It is closely relat ...
s,
polytope In elementary geometry, a polytope is a geometric object with Flat (geometry), flat sides (''Face (geometry), faces''). Polytopes are the generalization of three-dimensional polyhedron, polyhedra to any number of dimensions. Polytopes may exist ...
s,
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
s, or finite geometries. On the algebraic side, besides group and representation theory, lattice theory and
commutative algebra Commutative algebra, first known as ideal theory, is the branch of algebra that studies commutative rings, their ideal (ring theory), ideals, and module (mathematics), modules over such rings. Both algebraic geometry and algebraic number theo ...
are common.


Combinatorics on words

Combinatorics on words deals with
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (formal languages), alphabet and are well-formedness, well-formed ...
s. It arose independently within several branches of mathematics, including
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative intege ...
,
group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
and
probability Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
. It has applications to enumerative combinatorics, fractal analysis,
theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...
,
automata theory Automata theory is the study of abstract machines and automaton, automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτ ...
, and
linguistics Linguistics is the scientific study of human language. It is called a scientific study because it entails a comprehensive, systematic, objective, and precise analysis of all aspects of language, particularly its nature and structure. Linguis ...
. While many applications are new, the classical Chomsky–Schützenberger hierarchy of classes of
formal grammar In formal language, formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar d ...
s is perhaps the best-known result in the field.


Geometric combinatorics

Geometric combinatorics is related to
convex Convex or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytope, ...
and
discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study Combinatorics, combinatorial properties and constructive methods of discrete mathematics, discrete geometric objects. Most questions in discrete geometry involve fi ...
. It asks, for example, how many faces of each dimension a
convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded set, bounded convex polytope ...
can have.
Metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathema ...
properties of polytopes play an important role as well, e.g. the Cauchy theorem on the rigidity of convex polytopes. Special polytopes are also considered, such as permutohedra, associahedra and Birkhoff polytopes. Combinatorial geometry is a historical name for discrete geometry. It includes a number of subareas such as polyhedral combinatorics (the study of faces of convex polyhedra), convex geometry (the study of
convex set In geometry, a subset of a Euclidean space, or more generally an affine space over the Real number, reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set o ...
s, in particular combinatorics of their intersections), and
discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study Combinatorics, combinatorial properties and constructive methods of discrete mathematics, discrete geometric objects. Most questions in discrete geometry involve fi ...
, which in turn has many applications to
computational geometry Computational 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 ar ...
. The study of
regular polytope In mathematics, a regular polytope is a polytope whose symmetry group acts transitive group action, transitively on its flag (geometry), flags, thus giving it the highest degree of symmetry. All its elements or -faces (for all , where is the di ...
s,
Archimedean solid In geometry, an Archimedean solid is one of the 13 solids first enumerated by Archimedes. They are the convex polytope, convex Uniform polyhedron, uniform polyhedra composed of regular polygons meeting in identical vertex (geometry), vertices, e ...
s, and kissing numbers is also a part of geometric combinatorics. Special polytopes are also considered, such as the permutohedron, associahedron and Birkhoff polytope.


Topological combinatorics

Combinatorial analogs of concepts and methods in
topology In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...
are used to study
graph coloring In graph theory In mathematics, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph t ...
, fair division, partitions,
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
s,
decision tree A decision tree is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility As a topic of economics Economics () is the so ...
s, necklace problems and discrete Morse theory. It should not be confused with combinatorial topology which is an older name for
algebraic topology Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariant (mathematics), invariants that classification theorem, classify topological spaces up t ...
.


Arithmetic combinatorics

Arithmetic combinatorics arose out of the interplay between
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative intege ...
, combinatorics, ergodic theory, and
harmonic analysis Harmonic analysis is a branch of mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. Th ...
. 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. One important technique in arithmetic combinatorics is the ergodic theory of
dynamical system In mathematics, a dynamical system is a system in which a Function (mathematics), function describes the time dependence of a Point (geometry), point in an ambient space. Examples include the mathematical models that describe the swinging of a ...
s.


Infinitary combinatorics

Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. It is a part of
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, ...
, an area of
mathematical logic Mathematical logic is the study of formal logic within mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantiti ...
, but uses tools and ideas from both set theory and extremal combinatorics. Some of the things studied include continuous graphs and
trees In botany, a tree is a perennial plant with an elongated Plant stem, stem, or trunk (botany), trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondar ...
, extensions of Ramsey's theorem, and Martin's axiom. Recent developments concern combinatorics of the continuum and combinatorics on successors of singular cardinals. Gian-Carlo Rota used the name ''continuous combinatorics'' to describe geometric probability, since there are many analogies between ''counting'' and ''measure''.


Related fields


Combinatorial optimization

Combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and r ...
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 Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decis ...
, algorithm theory and
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
.


Coding theory

Coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied ...
started as a part of design theory with early combinatorial constructions of
error-correcting code In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for error control, controlling errors in data over unreliable or noisy communication channels. The ce ...
s. 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 Information theory is the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of information. The field was originally established by the works of Harry Nyquist a ...
.


Discrete and computational geometry

Discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study Combinatorics, combinatorial properties and constructive methods of discrete mathematics, discrete geometric objects. Most questions in discrete geometry involve fi ...
(also called combinatorial geometry) also began as a part of combinatorics, with early results on
convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded set, bounded convex polytope ...
s and kissing numbers. With the emergence of applications of discrete geometry to
computational geometry Computational 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 ar ...
, 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

There are increasing interactions between combinatorics and physics, particularly
statistical physics Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the Mathematics, mathematical tools for dealing with large populations ...
. Examples include an exact solution of the
Ising model The Ising model () (or Lenz-Ising model or Ising-Lenz model), named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical models in physics, mathematical model of ferromagnetism in statistical mechanics. The model consists of discr ...
, and a connection between the Potts model on one hand, and the
chromatic Diatonic and chromatic are terms in music theory that are most often used to characterize Scale (music), scales, and are also applied to musical instruments, Interval (music), intervals, Chord (music), chords, Musical note, notes, musical sty ...
and Tutte polynomials on the other hand.


See also

* Combinatorial biology * Combinatorial chemistry * Combinatorial data analysis *
Combinatorial game theory Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the players ...
* Combinatorial group theory *
Discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...
* List of combinatorics topics *
Phylogenetics In biology, phylogenetics (; from Greek language, Greek wikt:φυλή, φυλή/wikt:φῦλον, φῦλον [] "tribe, clan, race", and wikt:γενετικός, γενετικός [] "origin, source, birth") is the study of the evolutionary his ...
* Polynomial method in combinatorics


Notes


References

* Björner, Anders; and Stanley, Richard P.; (2010)
''A Combinatorial Miscellany''
* Bóna, Miklós; (2011)
''A Walk Through Combinatorics (3rd Edition)''
* Graham, Ronald L.; Groetschel, Martin; and Lovász, László; eds. (1996); ''Handbook of Combinatorics'', Volumes 1 and 2. Amsterdam, NL, and Cambridge, MA: Elsevier (North-Holland) and MIT Press. * Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997); ''Design Theory'', CRC-Press; 1st. edition (1997). . * * * Stanley, Richard P. (1997, 1999)
''Enumerative Combinatorics'', Volumes 1 and 2
Cambridge University Press Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer. Cambr ...
. * * van Lint, Jacobus H.; and Wilson, Richard M.; (2001); ''A Course in Combinatorics'', 2nd Edition, Cambridge University Press.


External links

*
Combinatorial Analysis
– an article in Encyclopædia Britannica Eleventh Edition
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 Dig ...
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.



{{Authority control