Combinatorics

combinatorics

Definition

Combinatorics

Combinatorics is a branch of discrete mathematics that deals with combinations of objects to a finite set in accordance with certain constraints.

Rules

Combinatorics is based on the following rules:

Sum Rule

Let $A$ and $B$ be two finite sets, then:

$$A\cap B\ne \varnothing ⟹|A\cup B|=|A|+|B|$$

Product Rule

Definition

Product Rule ( Combinatorics)

If there are $n$ ways to perform action 1 followed by $m$ ways to perform action $2$, then there are $n\times m$ ways to perform action $1$ followed by action $2$.

Let $S_1$ and $S_2$ be two finite sets, then:

$$|S_1\times S_2|=|S_1|\cdot |S_2|$$

Link to original

Equality Rule

If there exists a bijective relation between two finite sets $A,B$, then $A$ has as many elements as $B$:

$$\exists f:A\to B\text{with f bijective}⟹|A|=|B|$$

Counting

	Permutations	Variations	Combinations
without repetition	$n!$	$\frac{n!}{(n-k)!}$	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$
with repetition	$\frac{n!}{n_1!n_2!\dots n_k!}$	$n^k$	$\left(\genfrac{}{}{0ex}{}{n-1+k}{k}\right)$

Permutation with Repetition

Definition

Permutation with Repetition

A permutation with repetitions is an ordered rearrangement of $n$ elements consisting of $k$ distinct elements.

All possible permutations of a $n$-tuple can be counted using:

$$\frac{n!}{n_1!n_2!\dots n_k!}$$

where $n_i$ is the number of repetitions of the same element, by the product rule.

Link to original

Permutation without Repetition

Definition

Permutation without Repetition

A permutation without repetition is an ordered rearrangement of distinct elements.

All possible rearrangements of a $n$-tuple can be counted using:

$$n!=n(n-1)(n-2)\dots 3\cdot 2\cdot 1$$

by the product rule.

Example: The tuple $(1,2,3)$ can be rearranged as:

$$(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$$

Link to original

Variation with Repetition

Definition

Variation with Repetition

A variation with repetition is an ordered repeated selection of $k$ elements out of $n$.

All possible permutations of a set of length $n$ can be counted using:

$$n^k$$

by the product rule.

Link to original

Variation without Repetition

Definition

Variation without Repetition

A variation without repetition are ordered selections of $k$ different elements out of $n$.

All possible variations of a set of length $n$ can be counted using:

$$n(n-1)\dots (n-k+2)(n-k+1)=\frac{n!}{(n-k)!}=k!\left(\genfrac{}{}{0ex}{}{n}{k}\right)$$

by the product rule.

Link to original

Combination with Repetition

Definition

Combination with Repetition

A combination with repetition is an unordered repeated selection of $k$ elements out of $n$ or size $k$ multi-sets of elements from a set of size $n$.

All possible combinations can be counted using:

$$\left(\genfrac{}{}{0ex}{}{n-1+k}{k}\right)$$

Link to original

Combination without Repetition

Definition

Combination without Repetition

A combination without repetition is an unordered selection of $k$ elements out of $n$ elements or a subset of size $k$ from a set of size $n$.

All possible combinations of a set of length $n$ can be counted using the binomial coefficient:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$$

by the product rule.

Link to original