4 Permutations and combinations

Now that we know the product rule, we can talk about permutations and combinations. Let us first introduce the formal definitions, then we can talk about examples.

Permutation is related to tuples, where the order of values is important. Combination, on the other hand, is related to sets, where the order of elements is not important.

Given a set $X$ , let us define $n=\vert X\vert$ for notational convenience. We can, then, express the set of all permutations as

$P(X,n) = \{(e_1,\ldots e_n)\vert e_1 \in X, e_2 \in X \setminus \{e_1\}, e_3 \in X \setminus \{e_1, e_2\}, \ldots e_n \in X \setminus \{e_1, \ldots e_{n-1}\}\}$ .

The set of all combinations, on the other hand, is

$C(X, n) = \{\{e_1,\ldots e_n\}\vert e_1 \in X, e_2 \in X \setminus \{e_1\}, e_... ... X \setminus \{e_1, e_2\}, \ldots e_n \in X \setminus \{e_1, \ldots e_{n-1}\}\}$ .

Instead of using all elements in $X$ , we can also choose to use $r$ elements, where $r < n$ . In this case, the permutation of selecting $r$ elements from $X$ is:

$P(X, r) = \{(e_1,\ldots e_r)\vert e_1 \in X, e_2 \in X \setminus \{e_1\}, e_3 \in X \setminus \{e_1, e_2\}, \ldots e_r \in X \setminus \{e_1, \ldots e_{r-1}\}\}$ .

The combination of selecting $r$ elements from $X$ (also called $n$ choose $r$ ) is as follows:

$C(X, r) = \{\{e_1,\ldots e_r\}\vert e_1 \in X, e_2 \in X \setminus \{e_1\}, e_... ... X \setminus \{e_1, e_2\}, \ldots e_r \in X \setminus \{e_1, \ldots e_{r-1}\}\}$ .

Our main interest is to compute $\vert P(X,r)\vert$ and $\vert C(X,r)\vert$ .