# Monthly Archives: May 2016

## 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?

Filed under Life

## 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 X X to Y Y where:  (1) every element of Y Y got mapped to by some element of X X (surjective), and  (2) each element of Y Y doesn't get mapped to by more than one element of X X (injective). •That's the same as saying that every element of Y Y got mapped to by one and only one element of X X. •In a bijection f f from X X to X X, you can think of f(x) f(x) as meaning roughly "where do I put x x?" and as f(x)=y f(x)=y as meaning "I put x x in y y'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.

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?