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)

Suppose an object is constructed through $r$ successive stages. If every partial construction reaching stage $i$ can be extended in exactly $n_i$ ways, then the number of complete constructions is

$$N=\prod _{i=1}^r{n}_i=n_1{n}_2\cdots n_r.$$

The choices at a later stage may depend on earlier choices; only the number $n_i$ of available choices must be the same for every partial construction at that stage.

For fixed finite choice sets $S_1,\dots ,S_r$, this is equivalently the cardinality of their Cartesian product:

$$|S_1\times \cdots \times S_r|=\prod _{i=1}^r|S_i|.$$

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 repetition chooses all $n$ occurrences in a multiset and places them in order. Order matters, so $AAB$ and $ABA$ are different arrangements. Equal copies are nevertheless indistinguishable, so swapping the two copies of $A$ within $AAB$ does not create a new arrangement. Each distinct element must occur with its fixed multiplicity.

Let a multiset contain $k$ distinct elements $a_1,\dots ,a_k$ with multiplicities $n_1,\dots ,n_k$, where

$$n_1+\cdots +n_k=n.$$

Such a permutation is an ordered tuple of length $n$ containing exactly $n_i$ copies of each $a_i$. The number of distinct such permutations is the multinomial coefficient

$$\left(\genfrac{}{}{0ex}{}{n}{n_1,\dots ,n_k}\right)=\frac{n!}{n_1!\cdots n_k!}.$$

Link to original

Permutation without Repetition

Definition

Permutation without Repetition

A permutation without repetition chooses all $n$ distinct elements and places them in order. Order matters, and every element is used exactly once.

For a finite set $X$ with $|X|=n$, it is an ordered tuple $(x_1,\dots ,x_n)$ in which every element of $X$ occurs exactly once.

Equivalently, the position map

$$\pi :\{1,\dots ,n\}\to X,\pi (i)=x_i,$$

is bijective.

Link to original

Variation with Repetition

Definition

Variation with Repetition

A variation with repetition chooses $k$ elements from $n$ available elements and places them in order. Order matters, and the same element may be chosen more than once.

For a finite set $X$ with $|X|=n$, it is an ordered tuple

$$(x_1,\dots ,x_k),x_i\in X.$$

Equivalently, the tuple defines an unrestricted position map

$$v:\{1,\dots ,k\}\to X,v(i)=x_i.$$

Unlike a variation without repetition, this map need not be injective. The number of variations with repetition is

$$n^k.$$

Link to original

Variation without Repetition

Definition

Variation without Repetition

A variation without repetition chooses $k$ different elements from $n$ available elements and places them in order. Order matters, so $(a,b)$ and $(b,a)$ are different selections, and no element may occur twice.

For a finite set $X$ with $|X|=n$, it is an ordered tuple

$$(x_1,\dots ,x_k),x_i\in X,i\ne j⟹x_i\ne x_j.$$

Equivalently, the tuple defines an injective position map

$$v:\{1,\dots ,k\}\to X,v(i)=x_i.$$

The number of such ordered selections is

$$V(n,k)=n(n-1)\cdots (n-k+1)=\frac{n!}{(n-k)!},0\le k\le n.$$

This generalises a permutation without repetition: a variation may use any $k\le n$ elements, while a permutation is the special case $k=n$, in which every element is used.

Link to original

Combination with Repetition

Definition

Combination with Repetition

A combination with repetition chooses $k$ elements from $n$ available elements without placing them in order. Order does not matter, and the same element may be chosen more than once. Thus choosing $a,a,b$ gives the same combination as choosing $b,a,a$.

For a finite set $X=\{x_1,\dots ,x_n\}$, such a combination is a multiset of size $k$. It is determined by the multiplicities

$$(m_1,\dots ,m_n),m_i\ge 0,m_1+\cdots +m_n=k,$$

where $m_i$ records how many copies of $x_i$ were chosen. The number of combinations with repetition is

$$C_{\mathrm{rep}}(n,k)=\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+k-1}{n-1}\right).$$

The construction can be pictured as filling $k$ slots, one selection at a time. At every selection all $n$ elements remain available, so an earlier choice never removes anything. Once the last slot is filled, the order of the slots is discarded and only the multiplicities remain:

Link to original

Combination without Repetition

Definition

Combination without Repetition

A combination without repetition chooses $k$ different elements from $n$ available elements without placing them in order. Order does not matter, so choosing $a$ then $b$ gives the same combination as choosing $b$ then $a$, and no element may be chosen twice.

For a finite set $X$ with $|X|=n$, a combination of size $k$ is a subset

$$S\subseteq X,|S|=k.$$

The number of such combinations is the binomial coefficient

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

Link to original