HOME

TheInfoList




Combinatorics is an area of
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of
finite Finite is the opposite of Infinity, infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected ...
structures A structure is an arrangement and organization of interrelated elements in a material object or system A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified whole. A sy ...
. It is closely related to many other areas of mathematics and has many applications ranging from
logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents statements and ar ...

logic
to
statistical physics Statistical physics is a branch of physics Physics (from grc, φυσική (ἐπιστήμη), physikḗ (epistḗmē), knowledge of nature, from ''phýsis'' 'nature'), , is the natural science that studies matter, its Motion (physics), ...
and from
evolutionary biology Evolutionary biology is the subfield of biology Biology is the natural science that studies life and living organisms, including their anatomy, physical structure, Biochemistry, chemical processes, Molecular biology, molecular interacti ...
to
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of computation, automation, a ...
. 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 Leonid Mirsky (19 December 1918 Russia Russia (russian: link=no, Россия, , ), or the Russian Federation, is a country spanning Eastern Europe and Northern Asia. It is the List of countries and dependencies by area, largest country in ...
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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
) but
discrete Discrete in science is the opposite of :wikt:continuous, continuous: something that is separate; distinct; individual. Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory *Discrete device, an electronic c ...
setting. 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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, struc ...
, notably in
algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In its most ge ...

algebra
,
probability theory Probability theory is the branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are containe ...
,
topology In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities ...

topology
, and
geometry Geometry (from the grc, γεωμετρία; ' "earth", ' "measurement") is, with , one of the oldest branches of . It is concerned with properties of space that are related with distance, shape, size, and relative position of figures. A mat ...

geometry
, 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 Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gen ...
, 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 Graphs of functions commonly used in the analysis of algorithms, showing the number of operations ''N'' versus input size ''n'' for each function In computer science Computer science deals with the theoretical foundations of information, al ...
. A
mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces ...

mathematician
who studies combinatorics is called a '.


History

Basic combinatorial concepts and enumerative results appeared throughout the
ancient world Ancient history is the aggregate of past eventsWordNet Search – 3.0
"History"
from t ...

ancient world
. 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 professional who practices medicine, which is concerned with promoting, maintainin ...

physician
Sushruta Sushruta, or ''Suśruta'' (Sanskrit Sanskrit (, attributively , ''saṃskṛta-'', nominalization, nominally , ''saṃskṛtam'') is a classical language of South Asia belonging to the Indo-Aryan languages, Indo-Aryan branch of the Indo-Eu ...

Sushruta
asserts in
Sushruta Samhita The ''Sushruta Samhita'' (सुश्रुतसंहिता, IAST The International Alphabet of Sanskrit Transliteration (IAST) is a transliteration scheme that allows the lossless romanisation of Brahmic family, Indic scripts as employ ...
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#REDIRECT Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its population is approximately 10.7 million as of ...
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 stu ...
Plutarch Plutarch (; grc-gre, Πλούταρχος, ''Ploútarchos''; ; AD 46 – after AD 119) was a Greek Middle Platonist Middle Platonism is the modern name given to a stage in the development of Platonic philosophy, lasting from about 90 BC&nbs ...

Plutarch
discusses an argument between
Chrysippus Chrysippus of Soli (; grc-gre, Χρύσιππος ὁ Σολεύς, ; ) was a Greek Stoic philosopher A philosopher is someone who practices philosophy. The term ''philosopher'' comes from the grc, φιλόσοφος, , translit=philosop ...

Chrysippus
(3rd century BCE) and
Hipparchus Hipparchus of Nicaea (; el, Ἵππαρχος, ''Hipparkhos'';  BC) was a Greek astronomer, geographer, and mathematician. He is considered the founder of trigonometry, but is most famous for his incidental discovery of precession of the ...
(2nd century BCE) of a rather delicate enumerative problem, which was later shown to be related to
Schröder–Hipparchus number In combinatorics Combinatorics is an area of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, c ...
s. Earlier, in the ''
Ostomachion {{original research, section, date=October 2013} ''Ostomachion'', also known as ''loculus Archimedius'' (Archimedes' box in Latin language, Latin) and also as ''syntomachion'', is a mathematical treatise attributed to Archimedes. This work has ...

Ostomachion
'',
Archimedes Archimedes of Syracuse (; grc, ; ; ) was a Greek#REDIRECT Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Eu ...

Archimedes
(3rd century BCE) may have considered the number of configurations of a
tiling puzzle Tiling puzzles are puzzle A puzzle is a game A game is a structured form of play Play most commonly refers to: * Play (activity), an activity done for enjoyment * Play (theatre), a work of drama Play may refer also to: Computers and ...
, while combinatorial interests possibly were present in lost works by Apollonius. In the
Middle Ages In the history of Europe The history of Europe concerns itself with the discovery and collection, the study, organization and presentation and the interpretation of past events and affairs of the people of Europe since the beginning of ...
, combinatorics continued to be studied, largely outside of the European civilization. The
India India, officially the Republic of India (Hindi Hindi (Devanagari: , हिंदी, ISO 15919, ISO: ), or more precisely Modern Standard Hindi (Devanagari: , ISO 15919, ISO: ), is an Indo-Aryan language spoken chiefly in Hindi Belt, ...

India
n mathematician
Mahāvīra Mahavira (Sanskrit Sanskrit (, attributively , ''saṃskṛta-'', nominalization, nominally , ''saṃskṛtam'') is a classical language of South Asia belonging to the Indo-Aryan languages, Indo-Aryan branch of the Indo-European languages. ...
(c. 850) provided formulae for the number of
permutation In , a permutation of a is, loosely speaking, an arrangement of its members into a or , or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order o ...

permutation
s and
combination In mathematics, a combination is a selection of items from a collection, 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 three combinations of t ...

combination
s, and these formulas may have been familiar to Indian mathematicians as early as the 6th century CE. The
philosopher A philosopher is someone who practices philosophy Philosophy (from , ) is the study of general and fundamental questions, such as those about Metaphysics, existence, reason, Epistemology, knowledge, Ethics, values, Philosophy of mind, mi ...

philosopher
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 ...

astronomer
Rabbi Abraham ibn Ezra (c. 1140) established the symmetry of
binomial coefficient In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s, while a closed formula was obtained later by the
talmudist The Talmud (; he, תַּלְמוּד ''Tálmūḏ'') is the central text of Rabbinic Judaism and the primary source of Jewish religious law (''halakha'') and Jewish theology. Until the advent of modernity, in nearly all Jewish communities, the ...
and
mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces ...

mathematician
Levi ben Gerson Levi ben Gershon (1288 – 1344), better known by his Graecized name as Gersonides, or by his Latinized name Magister Leo Hebraeus, or in Hebrew Hebrew (, , or ) is a Northwest Semitic languages, Northwest Semitic language of the Afroasia ...

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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
. Later, in
Medieval England England in the Middle Ages concerns the history of England The British Isles became inhabited more than 800,000 years ago, as the discovery of stone tools and footprints at Happisburgh in Norfolk has indicated.; "Earliest footprints outside ...
,
campanology Campanology (from Late Latin Late Latin ( la, Latinitas serior) is the scholarly name for the written Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was ori ...
provided examples of what is now known as
Hamiltonian cycle In the mathematical Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities ...
s in certain
Cayley graph on two generators ''a'' and ''b'' In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a Graph (discrete mathematics), graph that encodes the abstract structure of a group (mathemati ...

Cayley graph
s on permutations. During the
Renaissance The Renaissance ( , ) , from , with the same meanings. is a period Period may refer to: Common uses * Era, a length or span of time * Full stop (or period), a punctuation mark Arts, entertainment, and media * Period (music), a concept in ...

Renaissance
, together with the rest of mathematics and the
science Science () is a systematic enterprise that builds and organizes knowledge Knowledge is a familiarity or awareness, of someone or something, such as facts A fact is something that is truth, true. The usual test for a statement of ...

science
s, combinatorics enjoyed a rebirth. Works of
Pascal Pascal, Pascal's or PASCAL may refer to: People and fictional characters * Pascal (given name), including a list of people with the name * Pascal (surname), including a list of people and fictional characters with the name ** Blaise Pascal, French ...

Pascal
,
Newton Newton most commonly refers to: * Isaac Newton (1642–1726/1727), English scientist * Newton (unit), SI unit of force named after Isaac Newton Newton may also refer to: Arts and entertainment * Newton (film), ''Newton'' (film), a 2017 Indian fil ...

Newton
,
Jacob Bernoulli Jacob Bernoulli (also known as James or Jacques; – 16 August 1705) was one of the many prominent mathematicians A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Ancient Greek, Greek: ) inclu ...
and
Euler Leonhard Euler ( ; ; 15 April 170718 September 1783) was a Swiss mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ) ...

Euler
became foundational in the emerging field. In modern times, the works of
J.J. Sylvester
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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (m ...
.
Graph theory In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gen ...
also enjoyed an increase of interest at the same time, especially in connection with the
four color problem In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into wikt:contiguity, contiguous regions, producing a figure called a ''map'', no more than four colors are required to color the r ...
. 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 Limit (mathematics), limits and related theories, such as Derivative, differentiation, Integral, integration, Measure (mathematics), ...
to
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen ...

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


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 is amenable to being represented, analyzed, and possibly solved, with the methods of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), ...
, 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 sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F_0=0,\quad F_1= 1, and F_n=F_ + F_ for . Th ...

Fibonacci numbers
is the basic example of a problem in enumerative combinatorics. The
twelvefold way In combinatorics Combinatorics is an area of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, ...
provides a unified framework for counting
permutations In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
,
combinations In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
and
partitions
partitions
.


Analytic combinatorics

Analytic combinatorics ''Analytic Combinatorics'' is a book on the mathematics of combinatorial enumeration, using generating functions and complex analysis to understand the growth rates of the numbers of combinatorial objects. It was written by Philippe Flajolet and Rob ...
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 Analysis is the branch of mathematics dealing with Limit (mathematics), limits and related theories, such as Der ...
and
probability theory Probability theory is the branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are containe ...
. In contrast with enumerative combinatorics, which uses explicit combinatorial formulae and
generating functions In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
to describe the results, analytic combinatorics aims at obtaining asymptotic formulae.


Partition theory

Partition theory studies various enumeration and asymptotic problems related to
integer partition 300px, Partitions of ''n'' with biggest addend ''k'' In number theory and combinatorics Combinatorics is an area of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mat ...
s, and is closely related to
q-series In mathematics, in the area of combinatorics, a ''q''-Pochhammer symbol, also called a ''q''-shifted factorial, is a q-analog, ''q''-analog of the Pochhammer symbol. It is defined as :(a;q)_n = \prod_^ (1-aq^k)=(1-a)(1-aq)(1-aq^2)\cdots(1-aq^) w ...
,
special functions Special functions are particular function (mathematics), mathematical functions that have more or less established names and notations due to their importance in mathematical analysis, functional analysis, geometry, physics, or other applications. ...
and
orthogonal polynomials In mathematics, an orthogonal polynomial sequence is a family of polynomials such that any two different polynomials in the sequence are orthogonality, orthogonal to each other under some inner product. The most widely used orthogonal polynomials ...
. Originally a part of
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen ...

number theory
and
analysis Analysis is the process of breaking a complex topic or substance Substance may refer to: * Substance (Jainism), a term in Jain ontology to denote the base or owner of attributes * Chemical substance, a material with a definite chemical composit ...

analysis
, 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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
and has connections with
statistical mechanics In physics Physics is the that studies , its , its and behavior through , and the related entities of and . "Physical science is that department of knowledge which relates to the order of nature, or, in other words, to the regular ...
.


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 . The red line shows the intersection with the plane y=0, equivalent to the chromatic polynomial. The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial In mathematics ...
''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 design Combinatorial design theory is the part of combinatorial mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and c ...
s, which are collections of subsets with certain
intersection The line (purple) in two points (red). The disk (yellow) intersects the line in the line segment between the two red points. In mathematics, the intersection of two or more objects is another, usually "smaller" object. Intuitively, the inter ...

intersection
properties.
Block design In combinatorial mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, ...
s are combinatorial designs of a special type. This area is one of the oldest parts of combinatorics, such as in
Kirkman's schoolgirl problem Kirkman's schoolgirl problem is a problem in combinatorics proposed by Rev. Thomas Penyngton Kirkman in 1850 as Query VI in ''The Lady's and Gentleman's Diary'' (pg.48). The problem states: Fifteen young ladies in a school walk out three abreast ...
proposed in 1850. The solution of the problem is a special case of a
Steiner system 250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line. In Combinatorics, combinatorial mathematics, a Steiner system (named after Jak ...
, which systems play an important role in the
classification of finite simple groups In mathematics, the classification of the finite simple groups is a theorem stating that every List of finite simple groups, finite simple group is either cyclic groups, cyclic, or alternating groups, alternating, or it belongs to a broad infinite ...
. 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.


Finite geometry

Finite geometry is the study of
geometric systems
geometric systems
having only a finite number of points. Structures analogous to those found in continuous geometries (
Euclidean plane In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
,
real projective spaceIn mathematics, real projective space, or RP''n'' or \mathbb_n(\mathbb), is the topological space of lines passing through the origin 0 in R''n''+1. It is a compact space, compact, smooth manifold of dimension ''n'', and is a special case Gr(1, R''n' ...
, etc.) but defined combinatorially are the main items studied. This area provides a rich source of examples for
design theory Design theory is a subfield of design research Design research was originally constituted as primarily research into the process of design, developing from work in design methodsDesign methods are procedures, techniques, aids, or tools for desi ...
. It should not be confused with discrete geometry (
combinatorial geometry Image:Unit disk graph.svg, A collection of circles and the corresponding unit disk graph Discrete geometry and combinatorial geometry are branches of geometry that study Combinatorics, combinatorial properties and constructive methods of discrete ...
).


Order theory

Order theory is the study of
partially ordered sets 250px, The set of all subsets of a three-element set , ordered by inclusion. Distinct sets on the same horizontal level are incomparable with each other. Some other pairs, such as and , are also incomparable. In mathematics, especially order the ...
, both finite and infinite. Various examples of partial orders appear in
algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In its most ge ...
, geometry, number theory and throughout combinatorics and graph theory. Notable classes and examples of partial orders include lattices and
Boolean algebras In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic Logic (from Ancient Greek, Greek: grc, wi ...
.


Matroid theory

Matroid theory abstracts part of
geometry Geometry (from the grc, γεωμετρία; ' "earth", ' "measurement") is, with , one of the oldest branches of . It is concerned with properties of space that are related with distance, shape, size, and relative position of figures. A mat ...

geometry
. It studies the properties of sets (usually, finite sets) of vectors in a
vector space In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
that do not depend on the particular coefficients in a
linear dependence In the theory of vector spaces, a set of vectors is said to be if at least one of the vectors in the set can be defined as a linear combinationIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics ...
relation. Not only the structure but also enumerative properties belong to matroid theory. Matroid theory was introduced by
Hassler Whitney Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersion (mathematics), immersions, characteristic classes, and ...
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 extremal questions on
set system In 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 ...
s. The types of questions addressed in this case are about the largest possible graph which satisfies certain properties. For example, the largest
triangle-free graphIn the mathematical area of 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 ...
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 pa ...
''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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related s ...
is another part of extremal combinatorics. It states that any
sufficiently large In the mathematical Mathematics (from Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its population i ...
configuration will contain some sort of order. It is an advanced generalization of the
pigeonhole principle In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
.


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 In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
? For instance, what is the average number of triangles in a random graph? Probabilistic methods are also used to determine the existence of combinatorial objects with certain prescribed properties (for which explicit examples might be difficult to find), simply by observing that the probability of randomly selecting an object with those properties is greater than 0. This approach (often referred to as ''the''
probabilistic method The probabilistic method is a nonconstructive method, primarily used in combinatorics Combinatorics is an area of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathema ...
) proved highly effective in applications to extremal combinatorics and graph theory. A closely related area is the study of finite
Markov chains A Markov chain is a stochastic model In 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 ...
, especially on combinatorial objects. Here again probabilistic tools are used to estimate the mixing time. Often associated with
Paul Erdős Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a renowned Hungarian mathematician In this page we keep the names in Hungarian order (family name first). {{compact ToC , short1, side=yes A * Alexits György (1899–1 ...

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 deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of computation, automation, a ...
, as well as classical probability,
additive number theory Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition. More abstractly, the field of additive number theory includes the study of abelian groups and commutative semigro ...
, 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 (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
that employs methods of
abstract algebra In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathema ...
, notably
group theory In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ...
and
representation theory Representation theory is a branch of mathematics that studies abstract algebra, abstract algebraic structures by ''representing'' their element (set theory), elements as linear transformations of vector spaces, and studies Module (mathematics), ...
, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in
algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In its most ge ...
. Algebraic combinatorics is continuously expanding its scope, in both topics and techniques, and can be seen as the area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant.


Combinatorics on words

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 (computer science), alphabet and are well-formedness, well-formed a ...
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 devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen ...

number theory
,
group theory In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ...
and
probability Probability is the branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained ...

probability
. It has applications to enumerative combinatorics,
fractal analysis Fractal analysis is assessing fractal characteristics of data. It consists of several methods to assign a fractal dimension and other fractal characteristics to a dataset which may be a theoretical dataset, or a pattern or signal extracted from ph ...
,
theoretical computer science Theoretical computer science (TCS) is a subset of general computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for the ...

theoretical computer science
,
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'' (the plural of ''automaton'') com ...

automata theory
, and
linguistics Linguistics is the scientific study of language A language is a structured system of communication Communication (from Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo ...

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


Geometric combinatorics

Geometric combinatorics is related to Convex geometry, convex and discrete geometry, in particular polyhedral combinatorics. It asks, for example, how many faces of each dimension a convex polytope can have. Metric geometry, Metric properties of polytopes play an important role as well, e.g. the Cauchy's theorem (geometry), Cauchy theorem on the rigidity of convex polytopes. Special polytopes are also considered, such as permutohedron, permutohedra, associahedron, associahedra and Birkhoff polytopes. Combinatorial geometry is a historical name for discrete geometry.


Topological combinatorics

Combinatorial analogs of concepts and methods in
topology In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities ...

topology
are used to study graph coloring, fair division, partition of a set, partitions, partially ordered sets, decision trees, necklace problems and discrete Morse theory. It should not be confused with combinatorial topology which is an older name for algebraic topology.


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 devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen ...

number theory
, combinatorics, ergodic theory, and harmonic analysis. 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 systems.


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, an area of mathematical logic, but uses tools and ideas from both set theory and extremal combinatorics. Gian-Carlo Rota used the name ''continuous combinatorics''''Continuous and profinite combinatorics''
/ref> to describe geometric probability, since there are many analogies between ''counting'' and ''measure''.


Related fields


Combinatorial optimization

Combinatorial optimization is the study of optimization on discrete and combinatorial objects. It started as a part of combinatorics and graph theory, but is now viewed as a branch of applied mathematics and computer science, related to operations research, Analysis of algorithms, algorithm theory and computational complexity theory.


Coding theory

Coding theory started as a part of design theory with early combinatorial constructions of error-correcting codes. The main idea of the subject is to design efficient and reliable methods of data transmission. It is now a large field of study, part of information theory.


Discrete and computational geometry

Discrete geometry (also called combinatorial geometry) also began as a part of combinatorics, with early results on convex polytopes and kissing numbers. With the emergence of applications of discrete geometry to computational geometry, these two fields partially merged and became a separate field of study. There remain many connections with geometric and topological combinatorics, which themselves can be viewed as outgrowths of the early discrete geometry.


Combinatorics and dynamical systems

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 Physics (from grc, φυσική (ἐπιστήμη), physikḗ (epistḗmē), knowledge of nature, from ''phýsis'' 'nature'), , is the natural science that studies matter, its Motion (physics), ...
. Examples include an exact solution of the Ising model, and a connection between the Potts model on one hand, and the chromatic polynomial, chromatic and
Tutte polynomial . The red line shows the intersection with the plane y=0, equivalent to the chromatic polynomial. The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial In mathematics ...
s on the other hand.


See also

* Combinatorial biology * Combinatorial chemistry * Combinatorial data analysis * Combinatorial game theory * Combinatorial group theory * List of combinatorics topics * Phylogenetics * 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). . * * * Richard P. Stanley, Stanley, Richard P. (1997, 1999)
''Enumerative Combinatorics'', Volumes 1 and 2
Cambridge University Press. * 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 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 Combinatorics,