nLab
permutation

Contents

Context

Combinatorics

Group Theory

Contents

Idea

Classically, a permutation on a set XX can be thought of in one of two different ways: either as a bijection from XX to itself, or as a pair of linear orderings on XX. In the case of a set that is already equipped with a natural ordering (such as a finite ordinal X={1,,n}X = \{1,\dots,n\}), these two ways of defining permutations are interchangeable, but they correspond to different abstract structures that are more salient in different contexts, and to different natural ways of comparing permutations. Typically, the definition of permutations-as-automorphisms is important in group theory, while the definition of permutations-as-linear-orders is more common in combinatorics. Both views of permutations are relevant to the theory of symmetric operads.

Definitions

Permutations as automorphisms, and conjugacy

As automorphisms σ:XX\sigma : X \to X in Set, the permutations of XX naturally form a group under composition, called 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)={1,,n}(n) = \{1,\dots,n\}, then its symmetric group is a finite group of cardinality n!n! = “nn factorial”, and one typically writes S nS_n or Σ n\Sigma_n.

Two permutations σ:XX\sigma : X \to X and τ:YY\tau : Y \to Y are said to be conjugate (written στ\sigma \cong \tau) just in case there is a bijection f:XYf : X \to Y such that σ=f 1τf\sigma = f^{-1} \tau f, or equivalently, when there is a commuting square of bijections:

X f Y σ τ X f Y \array{& X & \overset{f}\rightarrow & Y & \\ \sigma & \downarrow &&\downarrow & \tau\\ &X & \underset{f}\rightarrow& Y & \\ }

Observe that conjugacy is an equivalence relation, and that conjugacy classes of permutations of XX are in one-to-one correspondence with partitions of XX (see below).

Permutations as linear orders, and pattern containment

If XX is a set equipped with a linear ordering <\lt, then a permutation of XX is the same thing as a second (unrelated) linear ordering < σ\lt_\sigma on XX. Indeed, suppose we label the elements of XX according to the <\lt order as x 1<x 2<x_1 \lt x_2 \lt \dots, and according to the < σ\lt_\sigma order as σ 1< σσ 2< σ\sigma_1 \lt_\sigma \sigma_2 \lt_\sigma \dots. Then we can define a bijection σ:XX\sigma : X \to X as the function sending x 1σ 1x_1 \mapsto \sigma_1, x 2σ 2x_2 \mapsto \sigma_2, and so on. Conversely, any bijection σ:XX\sigma : X \to X induces a linear ordering < σ\lt_\sigma on XX by defining x< σxx \lt_\sigma x' iff σ(x)<σ(x)\sigma(x) \lt \sigma(x').

This way of viewing permutations naturally gives rise to “array notation” (or “one-line notation”), where a permutation σ:XX\sigma : X \to X is represented as the list of elements σ=(σ 1,σ 2,)\sigma = (\sigma_1,\sigma_2,\dots), and it may be contrasted with “cycle notation” (see below). Whereas cycle notation makes it easy to compare permutations for conjugacy, array notation leads to a different natural way of comparing permutations known as pattern containment.

Given two linearly ordered sets (X,< X)(X,\lt_X) and (Y,< Y)(Y,\lt_Y), a permutation (or “pattern”) σ:XX\sigma : X \to X is said to be contained in a permutation τ:YY\tau : Y \to Y (written στ\sigma \preceq \tau) just in case there exists a monotone injective function f:XYf : X \to Y such that

σ i< Xσ jτ f(i)< Yτ f(j)\sigma_i \lt_X \sigma_j \Rightarrow \tau_{f(i)} \lt_Y \tau_{f(j)}

for all i,jXi,j \in X, or in other words, if τ=(τ 1,τ 2,)\tau = (\tau_1,\tau_2,\dots) contains a subsequence of elements whose relative ordering (in YY) is the same as the relative ordering (in XX) of the sequence σ=(σ 1,σ 2,)\sigma = (\sigma_1,\sigma_2,\dots). Note that this definition of στ\sigma \preceq \tau is equivalent to asking for the existence of a commuting square:

X f Y σ τ X g Y \array{& X & \overset{f}\rightarrow & Y & \\ \sigma & \downarrow &&\downarrow & \tau\\ &X & \underset{g}\rightarrow& Y & \\ }

where ff and gg are monotone injections (each uniquely determined by the other).

Whereas conjugacy defines an equivalence relation on the permutations of a particular set XX, pattern containment defines a partial order on the permutations of arbitrary linearly ordered sets (which restricts to the discrete order on the permutations of XX).

r-permutations

In combinatorics, one sometimes also wants a slight generalisation of the notion of permutation-as-linear-order: for any natural number rr, an rr-permutation of XX is an injective function σ:(r)X\sigma : (r) \to X. An rr-permutation corresponds to a list of rr distinct elements of XX, so that for a finite set XX of cardinality n=|X|n = |X|, an nn-permutation is the same thing as an ordinary permutation of XX (it is surjective and therefore bijective, since Set is a balanced category). More generally, the number of rr-permutations of a set of cardinality nn is counted by the falling factorial n r̲=n(n1)(nr+1)n^{\underline{r}} = n(n-1)\dots(n-r+1).

Cycles and partitions

Cycle decomposition

As an element of the symmetric group S XS_X, every permutation σ:XX\sigma : X \to X generates a cyclic subgroup σ\langle \sigma \rangle, and hence inherits a group action on XX. The orbits of this action partition the set XX into a disjoint union of cycles, called the cyclic decomposition of the permutation σ\sigma.

For example, let σ\sigma be the permutation on (6)(6) defined by

σ=(11 24 35 46 53 62)\sigma = (\array{1 \mapsto 1 & 2 \mapsto 4 & 3 \mapsto 5 & 4 \mapsto 6 & 5 \mapsto 3 & 6 \mapsto 2})

The domain of the permutation is partitioned into three σ\langle\sigma\rangle-orbits

(6)={1}{2,4,6}{3,5}(6) = \{1\} \cup \{2,4,6\} \cup \{3,5\}

corresponding to the three cycles

1σ12σ4σ6σ23σ5σ31 \underset{\sigma}{\to} 1 \qquad 2 \underset{\sigma}{\to} 4 \underset{\sigma}{\to} 6 \underset{\sigma}{\to} 2 \qquad 3 \underset{\sigma}{\to} 5 \underset{\sigma}{\to} 3

We can express this more compactly by writing σ\sigma in “cycle notation”, as the composition σ=(1)(246)(35)\sigma = (1)(2\,4\,6)(3\,5), or σ=(246)(35)\sigma = (2\,4\,6)(3\,5) leaving implicit the action of the identity (1).

Conjugacy classes

Proposition

Let nn \in \mathbb{N} and Σ(n)\Sigma(n) the symmetric group on nn elements. Then the conjugacy classes of elements of Σ(n)\Sigma(n), hence of permutations of nn elements, correspond to the cycle structures: two elements are conjugate to each other precisely if they have the same number of distinct cycles of the same length, or in other words if they define the same underlying partition of nn.

Example

For the symmetric group on three elements there are three such classes:

(1 2 3) ~ (1 3 2)
(1 2)(3) ~ (1 3)(2) ~ (1)(2 3)
(1)(2)(3)
Young diagram (3) Layer 1
Young diagram (2,1) Layer 1
Young diagram (1,1,1) Layer 1

\,

\,

\,

\,

\,

\,

\,

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).

Classifying space and universal Thom space

The classifying space BΣ(n)B \Sigma(n) of the symmetric group on nn elements may be presented by Emb({1,,n}, )/Σ(n)Emb(\{1,\cdots, n\}, \mathbb{R}^\infty)/\Sigma(n), the Fadell's configuration space on nn unordered points in \mathbb{R}^\infty.

Write τ n\tau_n for the rank nn vector bundle over this which exhibits the canonical action of Σ(n)\Sigma(n) on n\mathbb{R}^n, by permutation of coordinates.

The Thom space BΣ(n) τ nB \Sigma(n)^{\tau_n} of this bundle appears as the cofficients of the spectral symmetric algebra of the “absolute spectral superpointSym 𝕊Σ𝕊Sym_{\mathbb{S}} \Sigma \mathbb{S} (see Rezk 10, slide 4).

See also (Hopkins-Mahowald-Sadofsky 94, around def. 2.8)

Whitehead tower and relation to supersymmetry

The symmetric groups and alternating groups are the first stages in a restriction of the Whitehead tower of the orthogonal group to “finite discrete ∞-groups” in the sense of homotopy type with finite homotopy groups. The homotopy fibers of the stages of the “finite Whitehead tower” are the stable homotopy groups of spheres (Epa-Ganter 16). (See also at super algebra – Abstract idea and at Platonic 2-group.)

BFivebrane(n) B 2π 3𝕊 B𝒜 n BString(n) Bπ 2𝕊 BA˜ n BSpin(n) π 1𝕊 BA n BSO(n) BS n BO(n) \array{ && && \vdots \\ && && \downarrow \\ && && \mathbf{B}Fivebrane(n) \\ && \downarrow && \downarrow \\ \mathbf{B}^2 \pi_3 \mathbb{S} &\stackrel{}{\longrightarrow} & \mathbf{B}\mathcal{A}_n &\hookrightarrow& \mathbf{B} String(n) \\ && \downarrow && \downarrow \\ \mathbf{B} \pi_2 \mathbb{S} &\longrightarrow & \mathbf{B} \tilde A_n &\hookrightarrow& \mathbf{B} Spin(n) \\ && \downarrow && \downarrow \\ \pi_1 \mathbb{S} &\longrightarrow& \mathbf{B} A_n &\hookrightarrow& \mathbf{B} SO(n) \\ && \downarrow && \downarrow \\ && \mathbf{B} S_n &\hookrightarrow& \mathbf{B} O(n) }

Notice that the squares on the right are not homotopy pullback squares. (The homotopy pullback of the string 2-group along A˜Spin(n)\tilde A \hookrightarrow Spin(n) is a BU(1)\mathbf{B}U(1)-extension of A˜\tilde A, but here we get the universal finite 2-group extension, by /24\mathbb{Z}/24 instead.

Examples

References

For the operadic structure of permutations, see Volume 1, Chapter 1 of:

For more on permutation patterns, see:

Last revised on September 13, 2018 at 04:28:47. See the history of this page for a list of all contributions to it.