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?

Advertisements

Leave a comment

Filed under Life

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s