2 Sets and functions

2.10 Permutations

Definition 2.10.1.
  • A permutation of a set X is a bijection XX.

  • Sn, the symmetric group on n letters, is the set of all permutations of {1,2,,n}.

Example 2.10.1.
  • For any set X, the identity function idX:XX is a permutation.

  • The function f:{1,2,3}{1,2,3} given by f(1)=3,f(2)=2,f(3)=1 is a permutation. f is an element of S3.

  • The function g:{1,2,3,4}{1,2,3,4} given by g(1)=2,g(2)=3,g(3)=4,g(4)=1 is a permutation. g is an element of S4.

Here are some diagrams illustrating the permutations f and g:

Figure 2.12: Diagram of the permutation f from the example above.
Figure 2.13: Diagram of the permutation g from the example above.

2.10.1 Two row notation

We need a way of writing down elements of Sn. The simplest is called two row notation. To represent fSn, you write two rows of numbers. The top row is 1, 2, …, n. Then underneath each number i on the top row you write f(i):

(12nf(1)f(2)f(n))

As an example, here are the two row notations for the two permutations of the previous example.

f :(123321)
g :(12342341)

The two row notation for the identity in Sn is particularly simple:

(12n1n12n1n).

This is a simple and not-that-efficient notation (it is not feasible to write down an element of S100 this way, even if it is a very simple permutation e.g. swaps 1 and 2, leaves 3-100 alone), but it is at least concrete and simple.

2.10.2 How many permutations?

n!, pronounced n factorial, means n×(n1)××2×1.

Theorem 2.10.1.

|Sn|=n!

Proof.

We will count how many possible bottom rows of two row notations for elements of Sn there are. Because a permutation is a bijection — one-to-one and onto — this bottom row consists of the numbers 1,2,,n in some order. We just need to show that there are exactly n! different ways to order the numbers 1,2,,n.

We prove this by induction on n. For the base case n=1 we have 1!=1 and it is clear that there is only one way to order a single 1.

For the inductive step, suppose |Sn1|=(n1)!. An ordering of 1,2,,n arises in exactly one way as an ordering of 1,2,,(n1) with the number n inserted into one of n places (the first, or second, or …, or nth position). So the number of such orderings is |Sn1| (the number of ways to choose an ordering of 1,2,,(n1)) times the number of ways to insert an n, giving |Sn|=|Sn1|×n=(n1)!×n=n!. This completes the inductive step. ∎

For example, there are 2!=2 elements of S2: they are

(1212),(1221)

The first one is the identity function on {1,2}.