Combination (combinatorics)

A combination (from Latin combinatio 'summary' ) or disordered sample is in combinatorics a selection of objects from a given basic set which (in contrast to permutation ) does not have to contain all objects of the basic set and in which (in contrast to permutation and variation ) the order is not taken into account. If objects can be selected several times, one speaks of a combination with repetition . If, on the other hand, each object is only allowed to appear exactly once, one speaks of a combination without repetition . The determination of the number of possible combinations is a standard task of counting combinatorics .

Definition of terms

A combination or disordered sample is a selection of objects from a set of objects for which the order of selection does not matter. If the order is nevertheless to play a role, one speaks of a variation instead of a combination. Deviating from this, combinations and variations are sometimes also summarized in the literature and a variation is then called “combination with consideration of the sequence”. ${\displaystyle k}$ ${\displaystyle n}$

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

Combination without repetition

All 10 combinations without repeating three out of five objects

number

Unrepentant selection problems can be investigated in two ways. In the classical case, one starts out from a variation without repetition for which it in from be selected elements are options. Now, however, the selected elements can themselves be arranged in different ways. If these different arrangements are all irrelevant, i.e. should always count as the same selection of elements, we have to divide the result once more and only get it ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle {\tfrac {n!}{(n-k)!}}}$ ${\displaystyle k}$ ${\displaystyle k!}$ ${\displaystyle k!}$

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

Possibilities, the number of which is also known as the binomial coefficient .

A second approach, which is used in particular for the evaluation of Bernoulli experiments, regards the combination without repetition as an arrangement problem. The number of possible selections can then be determined by determining the number of mutually distinguishable arrangements of selected and unselected objects, whereby these themselves should no longer be distinguishable from one another, i.e. the entire initial set is only "selected" in the two object classes ( e.g. black ball with white number) and "not selected" (e.g. white ball with black number). If one now examines how many different arrangements of these black and white balls there are, whereby only their color should play a role, the above formula results according to the formula for the number of permutations of elements, each of which cannot be differentiated by class. Whether it is the number of selected objects and the number of unselected objects or vice versa is irrelevant for the result; which of the two subsets of the initial set is of interest has no influence on the number of possible divisions. ${\displaystyle k}$ ${\displaystyle n-k}$

Quantity display

The amount

${\displaystyle {\bigl \{}(x_{1},x_{2},\ldots ,x_{n})\mid x_{i}\in \{0,1\},x_{1}+\ldots +x_{n}=k{\bigr \}}}$

is the "set of all combinations without repetition of objects for the class " and has the number of elements specified above. An alternative representation of this crowd is ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle {\bigl \{}(z_{1},z_{2},\ldots ,z_{k})\mid 1\leq z_{1}<z_{2}<\dotsb <z_{k-1}<z_{k}\leq n{\bigr \}}}$.

Examples

lotto

If you want to choose from objects without repetition and without considering the order, as is the case, for example, with the drawing of the lottery numbers , there is ${\displaystyle 49}$ ${\displaystyle 6}$

${\displaystyle {\binom {49}{6}}={\frac {49!}{6!\,(49-6)!}}=13.983.816}$

possible choices. With the lottery, the order does not matter, for example, whether first the one and then the one or first the one and then the one is drawn, does not matter for the winning numbers and the determination of the lottery winner. The number of possible solutions is calculated from the number of balls that can be drawn first and then . However, since the order does not matter, it must be taken into account that the product includes solutions of equal value. With three numbers drawn is the number of possibilities , but because the order of drawing of the balls does not matter, the product has to be divided by the number of possible drawing orders . ${\displaystyle 9}$ ${\displaystyle 17}$ ${\displaystyle 17}$ ${\displaystyle 9}$ ${\displaystyle 49}$ ${\displaystyle 48}$ ${\displaystyle 49\cdot 48}$ ${\displaystyle 2=1\cdot 2=2!}$ ${\displaystyle 49\cdot 48\cdot 47}$ ${\displaystyle 6=1\cdot 2\cdot 3=3!}$

Number of ways

Wall painting with the multiple hidden lettering "Deo gracias"

The mural in the Wismar Holy Spirit Church shows the letter "D" in the middle and an "S" at the bottom right. If you only take steps to the right or down, the text “DEOGRACIAS” always results. You take a total of nine steps, five of which you have to take one step to the right and four times one step down. Therefore there is

${\displaystyle {9 \choose 5}={\frac {9!}{5!\,4!}}=126}$

Options. But you can also go to the other corners with the same result: five times to the right and four times upwards or left and down or left and up. Overall, this results in possibilities. This task is commonly referred to as the Manhattan Problem , named after the New York neighborhood with its regular street layout. ${\displaystyle 126\cdot 4=504}$

Combination with repetition

All 35 combinations with repetition of three out of five objects

number

Should elements be selected from a set of elements , whereby their order should still be irrelevant, but they can now also be repeated, such as B. is possible when pulling with replacement, the following formula results for the number of possibilities (see multi-set ): ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle {\frac {(n+k-1)!}{(n-1)!\,k!}}={n+k-1 \choose k}={n+k-1 \choose n-1}=\left(\!\!{n \choose k}\!\!\right)}$

This can be seen when each result of selected elements from possible elements is represented by a sequence of symbols, with symbols (“N”) representing the elements of the selected set and symbols (“K”) representing the selected elements. The sequence always begins with an N symbol; the number of K symbols before the second N symbol corresponds to the frequency with which the first of the elements was drawn, the number of K symbols between the second and third N symbols corresponds to the second of the elements, and so on. Da except for the first "N" all symbols can be freely combined, the number of combinations and thus the number of possible moves corresponds to the given formula. ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n+k}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n}$

For example, when selecting 3 out of 5 elements (“1”, “2”, “3”, “4”, “5”) with replacement, the result “1, 3, 3” corresponds to the symbol sequence “NKNNKKNN”, the result “5, 5, 5” of the series “NNNNNKKK”. There are possible combinations. ${\displaystyle {n+k-1 \choose k}={7 \choose 3}=35}$

Quantity display

The amount

${\displaystyle {\bigl \{}(x_{1},x_{2},\ldots ,x_{n})\mid x_{i}\in \{0,1,\ldots ,k\},x_{1}+\ldots +x_{n}=k{\bigr \}}}$

is the “set of all combinations with repetition of things for the class ” and has the number of elements given above. Here is the number of occurrences of the -th element of the sample. An alternative representation of this crowd is ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$

${\displaystyle {\bigl \{}(z_{1},z_{2},\ldots ,z_{k})\mid 1\leq z_{1}\leq z_{2}\leq \dotsb \leq z_{k-1}\leq z_{k}\leq n{\bigr \}}}$.

Examples

Bijection between combinations with repetition of three out of five objects (right) and combinations without repetition of three out of seven objects (left)

Gummy Bear Oracle

One application of this is the so-called gummy bear oracle , in which one selects bears from a bag of gummy bears in different colors. So there is ${\displaystyle k=5}$ ${\displaystyle n=5}$

${\displaystyle \left(\!\!{5 \choose 5}\!\!\right)={\binom {9}{5}}={\frac {9!}{5!\,4!}}=126}$

different combinations. There are five combinations in which all bears have the same color, combinations with two different colors, with three colors, with four colors and one with all five colors. If the sequence were important when dragging, one would be dealing with a “variation with repetition”, that is, with possibilities. When asked about the number of options for selecting four pens from a stock of pens in six different colors, the same number comes up ( mastermind without considering the arrangement). On the other hand, there are possibilities with the “right” mastermind (taking into account the arrangement) . ${\displaystyle 40}$ ${\displaystyle 60}$ ${\displaystyle 20}$ ${\displaystyle 5^{5}=3125}$ ${\displaystyle 126}$ ${\displaystyle 6^{4}=1296}$

urn

A ball is drawn three times from an urn with five numbered balls and put back again each time. So you can always choose from five balls for all three draws. If you don't take into account the order of the numbers drawn, there is ${\displaystyle (n=5)}$ ${\displaystyle (k=3)}$

${\displaystyle \left(\!\!{5 \choose 3}\!\!\right)={\binom {7}{3}}={\frac {7!}{4!\,3!}}=35}$

different combinations. These combinations with repetition of five things for class three, i.e. three-element multisets with elements from the initial set , correspond exactly to the combinations without repetition of seven things for class three, i.e. the number of three-element subsets of a total of seven-element initial set . (The existence of a bijection can be used to prove the formula for the number of combinations with replacement.) ${\displaystyle 35}$ ${\displaystyle \{1,2,3,4,5\}}$ ${\displaystyle 35}$

cube

The use of several identical objects, such as dice with one to six eyes , is the same as replacing . How many different throws are possible with three dice? In principle, different throws are possible if one throws one dice after the other and observes the order. If, on the other hand, you throw all three dice at the same time, then no more order can be meaningfully defined. Since if all three dice are thrown at the same time, for example, the throw is no longer distinguishable from or no longer, there is only ${\displaystyle 6^{3}=216}$ ${\displaystyle 1-1-2}$ ${\displaystyle 1-2-1}$ ${\displaystyle 2-1-1}$

${\displaystyle \left(\!\!{6 \choose 3}\!\!\right)={\binom {8}{3}}={\frac {8!}{5!\,3!}}=56}$

different (distinguishable) litters. Not to be confused with the sum of the eyes, this can only have different values ​​(from to ). ${\displaystyle 16}$ ${\displaystyle 3}$ ${\displaystyle 18}$

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 .

Web links

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

Commons : Combinations with repetition  - collection of images, videos and audio files

• VM Mikheev: Combination . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
• kfgauss70: Combinations with repeated elements . In: PlanetMath . (English)
• Eric W. Weisstein : Combination . In: MathWorld (English).

Individual evidence

1. ↑ Hartung, Elpelt, Klösener: Statistics: Teaching and manual of applied statistics . S. 96 .
2. ^ Bronstein, Semendjajew: Taschenbuch der Mathematik . Harri Deutsch, 2008, ISBN 3-8171-2007-9 , pp. 810-811 .
3. ^ Manhattan Problem