What is a permutation? by Mike Kayser

Answer by Mike Kayser:

Informally:A reordering.If I have three objects arranged in a line on the table, there are 3!=6 ways to order them in that line. (Three ways to pick which one is on the left, times 2 ways to pick which one is in the middle, times exactly one way to pick the one on the right).

Formally:abijectionfrom a set to itself.

- A
bijectionin general is just a map from [math]X[/math] to [math]Y[/math] where:

(1) every element of [math]Y[/math] got mapped to by some element of [math]X[/math] (surjective), and

(2) each element of [math]Y[/math]doesn'tget mapped to by more than one element of [math]X[/math] (injective).- That's the same as saying that
everyelement of [math]Y[/math] got mapped to byone and only oneelement of [math]X[/math].- In a bijection [math]f[/math] from [math]X[/math] to [math]X[/math], you can think of [math]f(x)[/math] as meaning roughly "where do I put [math]x[/math]?" and as [math]f(x)=y[/math] as meaning "I put [math]x[/math] in [math]y[/math]'s old position."
- The bijective property we mentioned above is equivalent to ensuring that every "old position" is the "new home" for exactly one object in the set.