4.2 Combinations

Recall that ordering is not important in a combination. This is because of the definition:

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

In other words, each element in $C(X,r)$ is a set, not a tuple.

Note that there are several notations for $\vert C(X,r)\vert$ . The most common one is ${n}\choose{r}$ , but some people also use $_n C_r$ .

We can start with $_nP_r$ to compute $n\choose r$ . Each element (as a set) of $C(X,r)$ is a set of $r$ elements. Using the permutation computations, there are $_r P_r = r!$ permutations (as $r$ -tuples) in $P(X,r)$ corresponding to each element in $C(X,r)$ .

Consequently,

$${n \choose r} = \frac{ _n P_r}{r!}$$ (6)

$$= \frac{ \frac{n!}{(n-r)!}}{r!}$$ (7)

$$= \frac{n!}{r!(n-r)!}$$ (8)