Counting combinatorics

Number of variations and combinations of 10 elements to the k-th class and the partial derangements (fixed point free permutations) of 10 elements.
P * (10; k)  k-permutations or variations with repetition
P (10; k)  k-permutations or variations without repetition
K * (10; k)  k-combinations with repetition
K (10; k)  k-combinations without repetition
D (10; 10-k)  partial derangements
(in which only k of the 10 elements change places)

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

→ Main articles : permutation , variation (combinatorics)  and combination (combinatorics)

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 . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle k<n}$

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.

Overview of terminology

			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	${\displaystyle k=n}$	permutation	Permutation without repetition (English n-permutation )	Permutation with repetition ( n-tuple )
	${\displaystyle k<n}$	variation	Variation without repetition (English k-permutation )	Variation with repetition (English k-tuple )
random sample, regardless of order, d. H. Order irrelevant		combination	Combination without repetition (English k-combination )	Combination with repetition ( k-multiset )

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. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k_{1},\ldots ,k_{s}}$

Number of possible permutations, variations and combinations

	without repetition ${\displaystyle (a,b,c),\{a,b,c\}}$	with repetition ${\displaystyle (a,a,b),\{a,a,b\}}$
Permutations ${\displaystyle (a,b)\neq (b,a)}$	${\displaystyle ~n!~}$	${\displaystyle {\frac {(k_{1}+\ldots +k_{s})!}{k_{1}!\cdot \ldots \cdot k_{s}!}}={\frac {n!}{k_{1}!\cdot \ldots \cdot k_{s}!}}={\binom {n}{k_{1},\ldots ,k_{s}}}}$
	→ Faculty	→ Multinomial
Variations ${\displaystyle (a,b)\neq (b,a)}$	${\displaystyle {n \choose k}\cdot {k!}={\frac {n!}{\left(n-k\right)!}}}$	${\displaystyle ~n^{k}~}$
		→ k-tuple
Combinations ${\displaystyle \{a,b\}=\{b,a\}}$	${\displaystyle {n \choose k}={\frac {n!}{{\left(n-k\right)!}\cdot k!}}}$	${\displaystyle \left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={\frac {\left(n+k-1\right)!}{\left(n-1\right)!\cdot k!}}}$
	→ 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: ${\displaystyle k}$ ${\displaystyle n}$

${\displaystyle k}$ Balls	${\displaystyle n}$ subjects	Limitation to the number of balls per compartment
distinguishable?		-	Max. 1	at least 1
${\displaystyle \checkmark }$	${\displaystyle \checkmark }$	${\displaystyle n^{k}}$	${\displaystyle {\tfrac {n!}{(n-k)!}}=k!\,{\tbinom {n}{k}}}$	${\displaystyle n!\,S_{k,n}}$
${\displaystyle \times }$	${\displaystyle \checkmark }$	${\displaystyle \left(\!\!{\tbinom {n}{k}}\!\!\right)={\tbinom {k+n-1}{n-1}}}$	${\displaystyle {\tbinom {n}{k}}}$	${\displaystyle \left(\!\!{\tbinom {n}{k-n}}\!\!\right)={\tbinom {k-1}{n-1}}}$
${\displaystyle \checkmark }$	${\displaystyle \times }$	${\displaystyle \sum _{r=0}^{n}S_{k,r}}$	${\displaystyle {\begin{array}{lll}1&:&k\leq n\\0&:&k>n\end{array}}}$	${\displaystyle S_{k,n}}$
${\displaystyle \times }$	${\displaystyle \times }$	${\displaystyle \sum _{r=0}^{n}P_{k,r}=P_{k+n,n}}$	${\displaystyle {\begin{array}{lll}1&:&k\leq n\\0&:&k>n\end{array}}}$	${\displaystyle P_{k,n}}$

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 ). ${\displaystyle S_{k,n}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle P_{k,n}}$ ${\displaystyle k}$ ${\displaystyle n}$

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: ${\displaystyle (\Omega ,P)}$ ${\displaystyle k}$ ${\displaystyle n\leq k}$ ${\displaystyle E_{j}}$ ${\displaystyle j}$ ${\displaystyle j=1,\ldots ,n}$

1. No ball is assigned to a compartment in advance.
2. 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 ${\displaystyle E_{j}}$

${\displaystyle |\Omega |={\binom {n+k-1}{k}}=\sum _{j=1}^{n}{\binom {n}{j}}{\binom {k-1}{k-j}}}$.

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

${\displaystyle |\Omega |=n^{k}=\sum _{j=1}^{n}{\binom {n}{j}}\sum _{i=0}^{j-1}(-1)^{i}{\binom {j}{j-i}}(j-i)^{k}=\sum _{j=1}^{n}{\binom {n}{j}}(-1)^{j}\sum _{i=1}^{j}(-1)^{i}{\binom {j}{i}}i^{k}}$,

where the second sum is obtained by reversing the summation order (or ) from the first. ${\displaystyle i\to j-i}$

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 ${\displaystyle n=k}$ ${\displaystyle n!}$

${\displaystyle n!=\sum _{i=0}^{n-1}(-1)^{i}{\binom {n}{n-i}}(n-i)^{n}=(-1)^{n}\sum _{i=1}^{n}(-1)^{i}{\binom {n}{i}}i^{n}}$.

literature

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

Web links

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

Wikibooks: Algorithm Collection: Statistics: Binomial Coefficient  - Learning and Teaching Materials

• 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

Individual evidence

1. ^ 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 )
2. ↑ Aigner: Diskrete Mathematik , 2006, p. 10