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

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