from Wikipedia, the free encyclopedia

The Combinatorics is a branch of mathematics that deals with finite or countable infinite employs discrete structures and therefore the preamble discrete mathematics is attributed. Examples are graphs ( graph theory ), partially ordered sets such as associations , matroids , combinatorial designs , Latin squares , tiling , permutations of objects, partitions . The demarcation to other areas of discrete mathematics is fluid. A definition by George Pólya calls combinatorics the study of counting, the existence and construction of configurations.

Depending on the methods and objects used, a distinction is also made between sub-disciplines such as algebraic combinatorics, analytical combinatorics, geometric and topological combinatorics , probabilistic combinatorics, combinatorial game theory , and Ramsey theory . Combinatorial optimization is especially concerned with the optimization of discrete structures .

History and application

Historically, combinatorics emerged from counting problems of discrete structures as they appeared in the 17th century in the probability analysis of games of chance, for example by Blaise Pascal . This classic area of ​​combinatorics is collectively referred to as counting combinatorics (keywords: variations and combinations). A characteristic of the problems occurring in counting combinatorics was that mostly new methods had to be devised ad hoc for each individual problem. For a long time, combinatorics therefore played an outsider role in mathematics; summarizing theories of its sub-areas did not emerge until the 20th century, for example in the schools of Gian-Carlo Rota and Richard P. Stanley .

Combinatorics has numerous applications in other areas of mathematics such as geometry, probability theory, algebra, set theory and topology, in computer science (for example, coding theory ) and theoretical physics, in particular in statistical mechanics.

See also

Wiktionary: Combinatorics  - explanations of meanings, word origins, synonyms, translations
Wiktionary: combinatorial  - explanations of meanings, word origins, synonyms, translations


  • Claude Berge : Principles of Combinatorics , Academic Press 1971
  • Alan Tucker: Applied combinatorics , Wiley, 3rd edition 1995

Web links

Individual evidence

  1. George Pólya , Robert Tarjan , Donald R. Woods: Notes on introductory combinatorics , Birkhäuser 1983, foreword