Permutations

Overview

A permutation of some $n$ objects is a (possible) rearrangement of those $n$ objects. The number of permutations is $n!$ since there are $n$ possible ways to pick the first object, $(n - 1)$ possible ways to pick the second, and so on.

Alternatively, we say a permutation of a set $A$ is a bijective function $ϕ : A \to A$ . If $A = {a_{1}, a_{2}, \dots, a_{n}}$ is finite, we may denote permutation $ϕ$ as

ϕ = (\begin{matrix} a_{1} & a_{2} & \dots & a_{n} \\ a_{i_{1}} & a_{i_{2}} & \dots & a_{i_{n}} \end{matrix}),

where $i_{1}, i_{2}, \dots, i_{n}$ is a permutation of set ${1, 2, \dots, n}$ .

Falling Factorials

If we generalize to choosing $k \leq n$ elements of $n$ objects, we can calculate the $k$ -permutation of $n$ . This is denoted as $(n)_{k}$ , sometimes called the falling factorial.

(n)_{k} = \frac{n!}{(n - k)!}

The derivation works by noting that we have $n - 0$ possible ways to pick the first object, $n - 1$ ways to pick the second, up until $n - (k - 1)$ ways to pick the last object.

Derangements

A derangement is a permutation of the elements of a set in which no element appears in its original position. That is, it is a permutation with no fixed points.

Inversions

Let $π$ be a permutation. There is an inversion of $π$ between $i$ and $j$ if $i < j$ and $π (i) > π (j)$ .