Combinatorics

This article covers a field of mathematics. For the classic area of ​​combinatorics, see counting combinatorics .

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

literature

• Joseph PS Kung, Gian-Carlo Rota , Catherine H. Yan: Combinatorics: The Rota Way . Cambridge University Press , Cambridge (et al.) 2009, ISBN 978-0-521-73794-4 .

• Konrad Jacobs , Dieter Jungnickel : Introduction to combinatorics . 2nd Edition. de Gruyter, Berlin, New York 2004, ISBN 3-11-016727-1 .

• Ronald Graham , Martin Grötschel , László Lovász (editors): Handbook of combinatorics , 2 volumes, Elsevier / North Holland and MIT Press 1995

• Jacobus van Lint , Richard M. Wilson : A Course in Combinatorics , Cambridge University Press, 2nd edition 2001

• Claude Berge : Principles of Combinatorics , Academic Press 1971

• Alan Tucker: Applied combinatorics , Wiley, 3rd edition 1995

• Martin Aigner , Günter M. Ziegler : The BOOK of Evidence , Springer 2002

• VN Sachkov: combinatorial analysis . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).

Web links

• Andreas Brinken: Introduction to combinatorics - school materials on combinatorics (PDF; 444 kB)
• Anders Björner , Richard P. Stanley : A combinatorial miscellany (PDF; 838 kB)

Individual evidence

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