Combinatorics

Combinatorics

Combinatorics is the study of the compilation of countably many objects. This is generally the number of possibilities for a certain composition in the foreground, as it can be derived a statement about the probability of a particular compilation. One differentiates by the compilations between permutations, variations and combinations of objects.

Combinatorial basic functions

List of the basic functions for combinatorics.

Faculty

The function f(n) = n! with f(0) = 1 and f(n) = n ⋅ f(n-1) is called n-Faculty.

Example: 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120

Binomial Coefficient

The defined for all natural numbers function

$\left(\begin{array}{c}n\\ k\end{array}\right)$ is called a binomial coefficient.

The binomial coefficient is defined as follows:

$n k = n! k! n - k ! mit0≤k≤n andernfalls ist n k = 0$

Properties of the binomial coefficients

Symmetry rule:

$\left(\begin{array}{c}n\\ k\end{array}\right)=\left(\begin{array}{c}n\\ n-k\end{array}\right)$

$\left(\begin{array}{c}n\\ k\end{array}\right)+\left(\begin{array}{c}n\\ k+1\end{array}\right)=\left(\begin{array}{c}n+1\\ k+1\end{array}\right)$

Binomial theorem

For all real numbers a and b and all natural numbers n holds the binomial theorem:

${\left(a+b\right)}^{n}=\sum _{k=0}^{n}\left(\begin{array}{c}n\\ k\end{array}\right){a}^{n-k}{b}^{k}$

$=\left(\begin{array}{c}n\\ 0\end{array}\right){a}^{n}{b}^{0}+\left(\begin{array}{c}n\\ 1\end{array}\right){a}^{n-1}{b}^{1}+...+\left(\begin{array}{c}n\\ n\end{array}\right){a}^{0}{b}^{n}$

n= k=

n=

Polynomial coefficients

The binomial coefficients are a special case of the more general polynomial coefficients. The polynomial coefficients are defined for all natural n and all r-tuples of natural ki for which the sum is equal to n.

The polynomial coefficients are defined as follows:

$n k1,k2,...,kr = n! k1! k2! ... kr!$

$\phantom{\rule{1em}{0ex}}\text{mit}\phantom{\rule{0.3em}{0ex}}\sum _{i=1}^{r}{k}_{i}=n$

Example

$\left(\begin{array}{c}12\\ 2,3,3,4\end{array}\right)=\frac{12!}{2!3!3!4!}=277200$

Polynomial theorem

For all r-tuples of real numbers a 1 , a 2 , ..., a r and all natural numbers n we have the polynomial theorem. Here the sum of all the combinations of r-tuples is to be formed for which the sum is equal to n.

$a1 + a2 + ... + ar n$

$=\sum _{{k}_{1}+{k}_{2}+...+{k}_{r}=n}^{}\left(\begin{array}{c}n\\ {k}_{1},{k}_{2},\mathrm{...},{k}_{r}\end{array}\right){{a}_{1}}^{{k}_{1}}{{a}_{2}}^{{k}_{2}}...{{a}_{r}}^{{k}_{r}}$

Permutations

As a permutation P k is called the sequence of k elements considering the position of the elements in the series. A question of combinatorics is how many orders A of k elements are possible.

It is:

$A Pk = k!$

Variations

As a variation V k r without repetition is called the ordered selection of r elements from a set of k elements. The difference to combinations is the considering of the order of the elements. For example, if participate in a tournament k teams is the number of possible first three places a variation without repetitions as each team can only occupy a place and position in the top three is relevant.

It applies to variations without repetitions:

$A Vrk = k! k - r !$

It applies to variations with repetitions:

$A Vrk = k r$

Combinations

As a combination of C k r is defined as the selection of r elements from a set of k elements. In contrast to the variations, the order does not matter. For example, the lottery numbers are a combination without repetition, because the drawn numbers will not back down.

It applies to combinations without repetitions:

$A Crk = k r = k! r! k - r !$

It applies to combinations with repetitions:

$A Crk = k+r-1 r = k+r-1! r! k - 1 !$