(Discrete) Probability is essentially about counting. Counting the number of ways an outcome from a random experiment can happen. We need some tricks to help us. 😃

Permutations

A permutation of a set is an ordering of the set. If you have N elements in a set and you change the order you have another permutation.

Example 1.
Consider the set $A=\{ 1,2,3 \}$. We can re-arrange the items in a set to form the following permutations
$$\begin{array}{cc} (1,3,2) & (1,3,2) \\ (2,1,3) & (2,3,1) \\ (3,1,2) & (3,2,1) \\ \end{array}$$
We have $3! = 3*2*1 = 6$ permutations (see next example for why this is the case)

The symbol $N!$ (factorial) means $N(N-1)…1$

Combinations

A combination of a set, $A$, is a subset of $A$, and unlike permutations above the order does not matter. An example will make this clearer.

Example 4.
Let’s suppose $A=\{ 1,2,3 \}$. Then the following sets are all the combinations of $A$
$$\begin{array}{cc} \{1,2\} & \{2,3\} & \{3,1\} \\ \{1\} & \{2\} & \{3\}\\ \{1,2,3\} & \emptyset & \\ \end{array}$$
You will notice there are 8 of them as each element in $A$ can be chosen or not chosen for the combination ( 2 choices) and there are three elements in $A$ all together so there are in total $2^3 =8$ combinations.

To be more specific, subsets of size K are called K-combinations. Note that the sets $\{1,2\}$ and $\{2,1\}$ are the same 2-combination (subset) as changing the order of the elements does not create a new combination.

Lets concentrate on creating a K-combination of a set of N (distinct) elements. Note we don’t actually have to bother with the word distinct because by definition a mathematical set contains distinct elements.

Example 5.
K-combinations of an N-set
Suppose $A=\{ 1,2,3,4 \}$ write down all the possible 3-combinations.
$$\begin{array}{cccc} \{1,2,3\}&\{2,3,4\}&\{3,4,1\},&\{4,1,2\} \end{array}$$
If we wanted to create all the permutations of subsets of $A$ of size 3 we would have 4 choices for the first item, 3 choices for the second item and 2 choices for the third item i.e. 4*3*2 permutations in total. Each one of those sets above has 3! permutations as in example 1 since they contain 3 elements so that we know the number of combinations is $\frac{4*3*2}{3!}$ or $\frac{4!}{(4-3)!3!}$. In general the number of K-combinations from a set of size N is $$\frac{N}{(N-K)!K!}$$

$\frac{N}{(N-K)!K!}$ is such an important formula it has its own notation.

$$C(N,K) = \frac{N}{(N-K)!K!}$$

$C(N,K)$ is sometimes also written as $\binom{N}{K}$ and pronounced “N choose K”.