icon-Kombinatorik 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.

Tasks of Combinatorics

How many ways there are books to be placed in a shelf? (Permutation)

On a race take part participants. How many possibilities are there for the top places in the order of the competition result? (Variation without repetitions)

How many different -letter words can be formed from an alphabet with letters? (Variation with repetitions)

How many ways are there at number lottery with numbers from numbers to choose? (Combination without repetition)

How many throws can be achieved with identical dice each with sides? (Combination with repetitions)

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

n k is called a binomial coefficient.

The binomial coefficient is defined as follows:

n k = n! k! n - k ! mit0kn andernfalls ist n k = 0

Properties of the binomial coefficients

Symmetry rule:

n k = n n-k

Addition rule:

n k + n k+1 = n+1 k+1

Binomial theorem

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

a + b n = k = 0 n n k a n - k b k = n 0 a n b 0 + n 1 a n - 1 b 1 + ... + n n a 0 b n

Calculator: binomial coefficient

n= k=

Calculator: Binomial theorem

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! mit i = 1 r ki = n

Example

12 2,3,3,4 = 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 = k1 + k2 + ... + kr = n n k1,k2,...,kr a1k1 a2k2 ... arkr

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 !