Combinatorics is an area of

^{6} − 1 possibilities.

_{''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.

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

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

''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

Combinatorial Analysis

– an article in Encyclopædia Britannica Eleventh Edition

Combinatorics

a

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

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 theancient 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 2Greek
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 broadmathematical 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 fromcomplex 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 toq-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''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 theclassification 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 ofpartially 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 ofgeometry
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 ...

''KRamsey 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 incomputer 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 ofmathematics
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 withformal 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 toconvex
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 intopology
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 betweenharmonic 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 ofset 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, particularlystatistical 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