Variation (combinatorics)

A variation (from Latin variatio "change" ) or ordered sample is in combinatorics a selection of objects from a set in a certain order . If objects can be selected several times, one speaks of a variation with repetition , each object may only appear once, of a variation without repetition . The determination of the number of possible variations is a standard task of counting combinatorics .

Definition of terms

A variation or ordered sample is a selection of objects from a set of objects, whereby the order of the selection plays a role. If all available objects are selected, the following applies , so instead of a variation of a permutation , the sequence does not play a role in the selection of the objects of a combination . ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k=n}$

In the case of a variation with repetition, objects can be selected multiple times, while in the case of a variation without repetition, each object may only appear once. In an urn model , a variation with repetition corresponds to a drawing of the balls with replacement and a variation without repetition corresponds to a draw without replacement.

Deviating from this, variations and combinations are sometimes summarized in the literature and a variation is then called “combination with consideration of the sequence”. In particular, in English usage, variations and permutations are combined and variations then "k-permutations" ( k-permutations called).

Variation without repetition

All 60 variations without repeating three out of five numbers

number

In a variation without repetition are from (with objects ) to be placed vacant seats, each object is only allowed to occupy a place at the most. There are possible objects for the first place, objects for the second place , and so on up to the -th place for which there are still possible objects. So overall there is ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k\leq n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle k}$ ${\displaystyle n-k+1}$

${\displaystyle n\cdot (n-1)\cdot \ldots \cdot (n-k+1)={\frac {n!}{(n-k)!}}}$

possible arrangements. The notations and , which are called falling factorials , also exist for this number . With the will faculty of designated. ${\displaystyle n^{\underline {k}}}$ ${\displaystyle (n)_{k}}$ ${\displaystyle n!}$ ${\displaystyle n}$

Quantity display

The crowd

${\displaystyle \{(x_{1},x_{2},\dotsc ,x_{k})\mid x_{i}\in \{1,2,\dotsc ,n\},x_{i}\neq x_{j}~{\text{für}}~i\neq j\}}$

is the “set of all variations without repetition of objects for the class ” and has the number of elements specified above. ${\displaystyle n}$ ${\displaystyle k}$

Examples

• If an urn with five different balls is drawn three times without replacing, different selections are possible: with the first draw five options, then only four and for the third draw only three options. ${\displaystyle 5\cdot 4\cdot 3=60}$
• If all five balls are to be selected, there is a corresponding number of total possibilities, i.e. the number of permutations of all five balls. ${\displaystyle 5\cdot 4\cdot 3\cdot 2\cdot 1=5!=120}$

Variation with repetition

All 125 variations with repetition of three out of five numbers

number

In the case of a variation with repetition, objects are selected from objects in accordance with the sequence, whereby objects can also be selected several times. Accordingly, since each of the objects can appear in each of the places of the selection, there is ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle \underbrace {n\cdot \dotsc \cdot n} _{k{\text{-mal}}}=n^{k}}$

possible arrangements.

Quantity display

The amount

${\displaystyle \{1,2,\dotsc ,n\}^{k}={\bigl \{}(x_{1},x_{2},\dotsc ,x_{k})\mid x_{i}\in \{1,2,\dotsc ,n\}{\bigl \}}}$

is the "set of all variations with repetition of objects in a class ". It is the -fold Cartesian product of the set with itself and has the number of elements given above. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \{1,2,\dotsc ,n\}}$

Examples

• If an urn with five different balls is drawn three times with replacement, then different selections are possible. ${\displaystyle 5\cdot 5\cdot 5=5^{3}=125}$
• With a four-digit PIN or a combination lock with four rings and ten digits each, there are a total of different variations (0000–9999). ${\displaystyle 10^{4}=10000}$
• In the digital technology binary numbers used consist only of two digits and . With an arrangement of such digits, different variations can arise accordingly . For example, a four-digit binary number encodes different states. ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle k}$ ${\displaystyle 2^{k}}$ ${\displaystyle 2^{4}=16}$

literature

• Martin Aigner : Discrete Mathematics . Vieweg, 2006, ISBN 3-8348-9039-1 .
• 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 .

Individual evidence

1. ^ ^{A b} Bronstein, Semendjajew: Taschenbuch der Mathematik . Harri Deutsch, 2008, ISBN 3-8171-2007-9 , pp. 810-811 .
2. ↑ Hartung, Elpelt, Klösener: Statistics: Teaching and manual of applied statistics . S. 96 .
3. ↑ Aigner: Discrete Mathematics . S. 7 .