# 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)!}` |