nLab permutation

Redirected from "permutations".
Contents

Context

Combinatorics

Group Theory

Contents

Idea

A permutation on a set XX is equivalently

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

Properties

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

References

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

For more on permutation patterns, see:

Last revised on May 3, 2022 at 22:25:44. See the history of this page for a list of all contributions to it.