# What is a permutation?

What is a permutation? 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: a bijection from a set to itself.

• A bijection in 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't get mapped to by more than one element of [math]X[/math] (injective).
• That's the same as saying that every element of [math]Y[/math] got mapped to by one and only one element 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.

What is a permutation?