## Combinatorial basic functions

List of the basic functions for combinatorics.

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

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:

$$\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{\mathrm{n!}}{\mathrm{k!}\left(n-k\right)!}\phantom{\rule{1em}{0ex}}\text{mit}\phantom{\rule{0.3em}{0ex}}0\phantom{\rule{0.3em}{0ex}}\le \phantom{\rule{0.3em}{0ex}}k\phantom{\rule{0.3em}{0ex}}\le \phantom{\rule{0.3em}{0ex}}n\phantom{\rule{0.5em}{0ex}}\text{andernfalls ist}\phantom{\rule{0.3em}{0ex}}\left(\begin{array}{c}n\\ k\end{array}\right)=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)$

Addition rule:

$\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\\ \mathrm{n}\end{array}\right){a}^{0}{b}^{n}$

#### Calculator: binomial coefficient

#### Calculator: Binomial theorem

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:

$$\left(\begin{array}{c}n\\ {k}_{1},{k}_{2},\mathrm{...},{k}_{r}\end{array}\right)=\frac{\mathrm{n!}}{{k}_{1}!{k}_{2}!\mathrm{...}{k}_{r}!}$$

$\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.

$${\left({a}_{1}+{a}_{2}+...+{a}_{r}\right)}^{n}$$

$=\sum _{{k}_{1}+{k}_{2}+...+{k}_{r}=\mathrm{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}}$

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\left({P}^{k}\right)=k!$$

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\left({V}_{r}^{k}\right)=\frac{\mathrm{k!}}{\left(k-r\right)!}$$

It applies to variations with repetitions:

$$A\left({V}_{r}^{k}\right)={k}^{r}$$

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\left({C}_{r}^{k}\right)=\left(\begin{array}{c}k\\ r\end{array}\right)=\frac{\mathrm{k!}}{\mathrm{r!}\left(k-r\right)!}$$

It applies to combinations with repetitions:

$$A\left({C}_{r}^{k}\right)=\left(\begin{array}{c}k+r-1\\ r\end{array}\right)=\frac{\left(k+r-1\right)!}{\mathrm{r!}\left(k-1\right)!}$$