A permutation is a selection of elements from a set where the order of selection matters.
Order matters means that the selections AB and BA are considered as two differents selections.
If the order does not matter such as in a lottery, the selections AB and BA would be considered as a the same selection and is known as combination
If the order would have not matter, all this selections would have been seen as a single combination 1 2 3 (because the order in the selections does not matter)
There are basically two types of permutation:
For a set of length n and a selection of length r (known as k for combination), the number of permutation <math>_nP_r \text{ (n permute r)}</math> is: <MATH> _nP_r = n_1 \times n_2 \dots \times n_r = n^r </MATH>
For a set of length n and a selection of length k, the number of permutation is: <MATH> _nP_k = \frac{n!}{(n-k)!} </MATH>
The division (n-k)! is a trick to be able to generalize the calculation with factorial
Example: if for a set of 10 element, with a selection of 3 elements, we can choose for:
In total, we have: <MATH> 10 * 9 * 8 \text{ permutations} </MATH>
To generalize with the factorial, we add the rest of the factorial serie in the dividend and divisor:
<MATH> 10 \times 9 \times 8 \times \frac{ 7 \times 5 \times 4 \times 3 \times 2 \times 1}{7 \times 5 \times 4 \times 3 \times 2 \times 1} = \frac{10!}{(10-3)!} = \frac{n!}{(n-k)!} </MATH>