- distinguishable or indistinguishable objects (ie “without” or “with” repetition of the same objects) and
- with or without regard to their order (i.e. “ordered” or “unordered”).
In modern combinatorics, these selections or arrangements are also viewed as maps , so that the task of combinatorics in this context can essentially be limited to counting these maps.
An amazing phenomenon of combinatorics is that often a few objects can be combined in many different ways. With the Rubik's Cube , for example, the 26 elements can be combined in around 43 trillion ways. This phenomenon is often referred to as a combinatorial explosion and is also the cause of the birthday paradox .
Permutations, variations and combinations
Definition of terms
Due to the variety of approaches, the spellings and terminology in the field of combinatorics are unfortunately often quite inconsistent. It is true that all authors agree that the exchange of the order of a set of distinguishable elements is a permutation . If, on the other hand, you only select elements from these elements whose order you then swap, many authors now refer to this as a variation , ordered sample or combination with consideration of the order , while others (especially in English-speaking countries) continue to refer to this as permutation . Finally, if one disregards their order in such a selection of elements, such a selection is now usually called a disordered sample , a combination without considering the order, or just a combination . Unless otherwise stated, combinations are usually disordered, whereas permutations and / or variations are ordered, whereby the question of whether one regards permutations as special cases of variations (or vice versa) may be answered differently from author to author .
All in all, there are first of all three (or even only two) different questions, which in turn are subdivided again according to whether or not there may be repetitions of the same elements among the selected elements. If the former is the case, one speaks of combinations, variations or permutations with repetition, otherwise those without repetition. Finally, if one imagines that the selected elements are taken from an urn or the like, then we speak of samples with or without replacement.
|Elements different in pairs||Elements can appear multiple times|
taking into account the sequence,
d. H. Order relevant
Permutation without repetition
(English n-permutation )
Permutation with repetition
( n-tuple )
Variation without repetition
(English k-permutation )
Variation with repetition
(English k-tuple )
regardless of order,
d. H. Order irrelevant
Combination without repetition
(English k-combination )
Combination with repetition
( k-multiset )
In the following, the number of elements present and the number of selected elements or the respective numbers of elements that cannot be distinguished.
|→ Faculty||→ Multinomial|
|→ sets (k subsets)||→ multisets|
Balls and fans
A generalization of the urn model is a model popularized by Gian-Carlo Rota with balls and fans, also called the Twelvefold Way ("twelve- fold way") after a suggestion by Joel Spencer . What is sought is the number of ways to distribute balls to compartments, whereby the balls and compartments are either distinguishable or indistinguishable and either no further condition applies or a maximum of one ball may come in each compartment or at least one ball must come. The following overview is obtained:
|Balls||subjects||Limitation to the number of balls per compartment|
|distinguishable?||-||Max. 1||at least 1|
It is the number of ways a -elementige amount in dividing non-empty disjoint subsets ( Stirling number of the second kind), and the number of ways the number as a sum of display positive integers without regard to the order (see partition function ).
If the number of possible events in a discrete probability space is given by one of the above combinatorial formulas, then equivalent representations can be derived for them by fully decomposing the event space. The following two models illustrate this. There are balls randomly on distributed compartments. Consider the events that compartments ,, contain at least one ball under the premise:
- No ball is assigned to a compartment in advance.
- Each ball is assigned to a compartment from the start, but can land in a different compartment.
The first case corresponds to the variant “indistinguishable balls, distinguishable compartments”. The complete decomposition of the event space into the disjoint events then gives
The second case corresponds to the variant “distinguishable balls, distinguishable compartments”. The complete decomposition of the event space analogous to the first case results in the equivalent representation
where the second sum is obtained by reversing the summation order (or ) from the first.
For the event that all compartments have at least one ball is the same as the event that all compartments have exactly one ball, and contains elements. It follows
- Martin Aigner : Discrete Mathematics . Vieweg, 2006, ISBN 3-8348-9039-1 .
- Karl Bosch : Elementary introduction to probability theory . Vieweg, 2003, ISBN 3-528-77225-5 .
- Norbert Henze : Stochastics for beginners . Springer Spectrum, 2013, ISBN 978-3-658-03076-6 , doi : 10.1007 / 978-3-658-03077-3 .
- Konrad Jacobs , Dieter Jungnickel : Introduction to combinatorics . de Gruyter, 2003, ISBN 3-11-016727-1 .
- Joachim Hartung , Bärbel Elpelt, Karl-Heinz Klösener: Statistics: Teaching and manual of applied statistics . Oldenbourg, 2005, ISBN 3-486-57890-1 .
- VN Sachkov: Combinatorial analysis . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
- Combinatorics module in the Math Prism
- Michael Stoll: Counting combinatorics (PDF; 554 kB) Lecture notes
- Recommendations for combinatorics in school (PDF) from: Stochastik in der Schule , 33, 2013, 1, pp. 21-25
- Richard P. Stanley : Enumerative combinatorics (Volume 1), Cambridge University Press, 2nd edition 2012, ISBN 978-1-107-01542-5 , pp. 79 ff. And 107 f. (English; Stanley's website for the book with the last preliminary version and errata as PDF: Enumerative Combinatorics, volume 1, second edition )
- Aigner: Diskrete Mathematik , 2006, p. 10