Counting combinatorics
The enumerative combinatorics is a part of combinatorics . It deals with determining the number of possible arrangements or selections
 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.
Applications
Combinatorics is an important basis for calculating with probabilities on the basis of Laplace's concept of probability .
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 Englishspeaking 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  

without replacing, without repetition 
with replacement, with repetition 

ordered sample, taking into account the sequence, d. H. Order relevant 
permutation 
Permutation without repetition (English npermutation ) 
Permutation with repetition ( ntuple ) 

variation 
Variation without repetition (English kpermutation ) 
Variation with repetition (English ktuple ) 

random sample, regardless of order, d. H. Order irrelevant 
combination 
Combination without repetition (English kcombination ) 
Combination with repetition ( kmultiset ) 
Numbers
In the following, the number of elements present and the number of selected elements or the respective numbers of elements that cannot be distinguished.
without repetition 
with repetition 


Permutations 

→ Faculty  → Multinomial  
Variations 

→ ktuple  
Combinations 

→ sets (k subsets)  → multisets 
Balls and fans
A generalization of the urn model is a model popularized by GianCarlo 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 nonempty 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 ).
Equivalent representations
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
 .
literature
 Martin Aigner : Discrete Mathematics . Vieweg, 2006, ISBN 3834890391 .
 Karl Bosch : Elementary introduction to probability theory . Vieweg, 2003, ISBN 3528772255 .
 Norbert Henze : Stochastics for beginners . Springer Spectrum, 2013, ISBN 9783658030766 , doi : 10.1007 / 9783658030773 .
 Konrad Jacobs , Dieter Jungnickel : Introduction to combinatorics . de Gruyter, 2003, ISBN 3110167271 .
 Joachim Hartung , Bärbel Elpelt, KarlHeinz Klösener: Statistics: Teaching and manual of applied statistics . Oldenbourg, 2005, ISBN 3486578901 .
Web links
 VN Sachkov: Combinatorial analysis . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . SpringerVerlag , Berlin 2002, ISBN 9781556080104 (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. 2125
Individual evidence
 ^ Richard P. Stanley : Enumerative combinatorics (Volume 1), Cambridge University Press, 2nd edition 2012, ISBN 9781107015425 , 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