Permutation
What is a permutation ?
A permutation is an ordered arrangement of a set of objects. More precisely, if we assume we have a set of n elements (elements may be letters, digits, objects), a permutation is any possible arrangement of these n elements. Note that order matters in a permutation.
Examples:
- {2, 3, 4, 1} is a permutation of {1, 2, 3, 4} set.
- {2, 3, 1, 4} is another permutation of {1, 2, 3, 4} set.
- {b, c, a} is a permutation of {a, b, c}.
- {c, b, a} is another permutation of {a, b, c}.
- {B, A} is not a permutation of A, B, C because we didn't keep all the elements (C is missing).
Calculation Formula
For a set of n different objects then, the number of permutations of that set is equal to,
`P_n = n!`
Example : E is a set of 3 elements which are 1, 2, 3.
The number of permutations in this set is equal to 3! = 6.
The permutations of E are :
1, 2, 3,
1, 3, 2,
2, 1, 3,
2, 3, 1,
3, 1, 2,
3, 2, 1.
How to identify a permutation ?
There are two important criteria in recognizing a permutation,
- order matters
- the whole (not a subset) of the elements is concerned
Example:
How many possible rankings in a 12 horse race ?
This is a permutation because the order (of arrival) matters and all the horses are concerned.
The number of possible rankings is 12! = 479 001 600.
Comparison of enumeration methods
| Method | Elements concerned | Order matters ? | Formula |
|---|---|---|---|
| Permutation | All elements (n) | Yes | `n!` |
| Arrangement | Subset of p elements from n | Yes | `frac {n!}{(n-p)!}` |
| Combination | Subset of p elements from n | No | `frac {n!}{p!* (n-p)!}` |