Permutation (ordered sample)

Permutation (ordered sample) is a method in combinatorics where the order matters.

The opposite is combinations, where the order does not matter.

When we draw elements, it can happen without replacement or with replacement:

Without replacement:

An element can only be used once. If you remove a ball from a bag and do not put it back, it cannot be drawn again.

With replacement:

An element can be used several times. If you remove a ball from a bag but put it back, it can be drawn again.

When we talk about permutations (ordered samples), we therefore distinguish between choosing without replacement or with replacement.

At a football tournament with 6 teams, there must be a 1st, 2nd, and 3rd place.

How many ways can the medals be distributed?

The sample is ordered because it matters which team is 1st, 2nd, and 3rd.

It is also without replacement, because a team cannot win more than one place.

$$ \large P(n,r) = \frac{n!}{(n-r)!} $$

$$ \large P(6,3) = \frac{6!}{(6-3)!} $$

$$ \large P(6,3) = \frac{6!}{3!} $$

$$ \large P(6,3) = \frac{720}{6} $$

$$ \large Permutations = 120 $$

So there are 120 possible distributions of medals.

In the medal example we only chose a subset of the teams, where $ \large r < n $.

One can also have a full permutation, where all elements are included. In that case:

$$ \large P(n,n) = n! $$

Example: All 6 teams must line up:

$$ \large 6! = 720 $$

So there are 720 possible orders.

If you have to choose a code for your bike lock with 4 digits, there are 10 possible numbers (0-9) at each choice.

You can choose $ \large 5555 $, because it is with replacement. The same digit may be used several times.

The order also matters: $ \large 1234 $ is not the same as $ \large 4321 $.

You must choose 4 digits, and there are 10 options (0-9) each time.

$$ \large Permutations\ = n^r $$

$$ \large Permutations\ = 10^4 $$

$$ \large Permutations\ = 10.000 $$

So there are 10,000 possible codes.

A permutation is an ordered sample where the order matters.

Without replacement: An element can only be used once. Example: medal distribution in sports.
With replacement: An element can be used several times. Example: pin codes.
Full permutation: All elements are included, and the number is $ \large n! $.

Permutations are used to count possible orders, and they grow very quickly in number even for small values of $ \large n $.

Formulas