Combinatorics Online

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.

Tasks of Combinatorics

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

$(\begin{matrix} n \\ k \end{matrix})$ is called a binomial coefficient.

The binomial coefficient is defined as follows:

$(\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! (n - k)!} mit 0 \leq k \leq n andernfalls ist (\begin{matrix} n \\ k \end{matrix}) = 0$

Properties of the binomial coefficients

Symmetry rule:

$(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n \\ n - k \end{matrix})$

Addition rule:

$(\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ k + 1 \end{matrix}) = (\begin{matrix} n + 1 \\ k + 1 \end{matrix})$

Binomial theorem

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

${(a + b)}^{n} = \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) a^{n - k} b^{k} = (\begin{matrix} n \\ 0 \end{matrix}) a^{n} b^{0} + (\begin{matrix} n \\ 1 \end{matrix}) a^{n - 1} b^{1} + ... + (\begin{matrix} n \\ n \end{matrix}) a^{0} b^{n}$

Calculator: binomial coefficient

Calculator: Binomial theorem

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 k_i for which the sum is equal to n.

The polynomial coefficients are defined as follows:

$(\begin{matrix} n \\ k_{1}, k_{2}, ..., k_{r} \end{matrix}) = \frac{n!}{k_{1}! k_{2}! ... k_{r}!}$

$mit \sum_{i = 1}^{r} k_{i} = n$

Example:

$(\begin{matrix} 12 \\ 2, 3, 3, 4 \end{matrix}) = \frac{12!}{2! 3! 3! 4!} = 277200$

Polynomial theorem

For all r-tuples of real numbers a ₁, a ₂, ..., 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.

${(a_{1} + a_{2} + ... + a_{r})}^{n} = \sum_{k_{1} + k_{2} + ... + k_{r} = n}^{} (\begin{matrix} n \\ k_{1}, k_{2}, ..., k_{r} \end{matrix}) {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 (P^{k}) = 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 (V_{r}^{k}) = \frac{k!}{(k - r)!}$

It applies to variations with repetitions:

$A (V_{r}^{k}) = 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 (C_{r}^{k}) = (\begin{matrix} k \\ r \end{matrix}) = \frac{k!}{r! (k - r)!}$

It applies to combinations with repetitions:

$A (C_{r}^{k}) = (\begin{matrix} k + r - 1 \\ r \end{matrix}) = \frac{(k + r - 1)!}{r! (k - 1)!}$