Monthly Archives: May 2016

What is a permutation?


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

Advertisements

Leave a comment

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.

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?

Leave a comment

Filed under Life