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.

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:** 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?

### Like this:

Like Loading...

*Related*