nLab
permutation

Contents

Idea

A permutation is an automorphism in Set. More explicitly, a permutation of a set XX is an invertible function from XX to itself.

Definition

The group of permutations of XX (that is the automorphism group of XX in SetSet) is the symmetric group (or permutation group) on XX. This group may be denoted S XS_X, Σ X\Sigma_X, or X!X!. When XX is the finite set [n][n] with nn elements, one typically writes S nS_n or Σ n\Sigma_n; note that this group has n!n! elements.

In combinatorics, one often wants a slight generalisation. Given a natural number rr, an rr-permutation from XX is an injective function from [r][r] to XX, that is a list of rr distinct elements of XX. Then an nn-permutation from [n][n] is the same as a permutation of [n][n]. (That an injective function from XX to itself must be invertible characterises XX as a Dedekind-finite set.)

Concrete representations

Via string diagrams

Via cycle decompositions

Properties

Relation to the field with one element

One may regard the symmetric group S nS_n as the general linear group in dimension nn on the field with one element GL(n,𝔽 1)GL(n,\mathbb{F}_1).

Revised on August 9, 2013 13:39:32 by Urs Schreiber (82.113.98.165)