順列

コーシーの2行記法^{[ 20 ] [ 21 ]}では、1行目にSの要素を、2行目に各要素の像を列挙します。例えば、関数によって与えられるS = {1, 2, 3, 4, 5, 6}の順列は次のようになります。

${\displaystyle \sigma (1)=2,\ \ \sigma (2)=6,\ \ \sigma (3)=5,\ \ \sigma (4)=4,\ \ \sigma (5)=3,\ \ \sigma (6)=1}$

次のように書くことができます

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5&6\\2&6&5&4&3&1\end{pmatrix}}.}$

Sの要素は最初の行に任意の順序で現れる可能性があるため、この順列は次のように書くこともできます。

${\displaystyle \sigma ={\begin{pmatrix}2&3&4&5&6&1\\6&5&4&3&1&2\end{pmatrix}}={\begin{pmatrix}6&5&4&3&2&1\\1&3&4&5&6&2\end{pmatrix}}.}$

Sの要素に「自然な」順序がある場合、^{[ b ]}とします。${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$そして、2行表記の最初の行にはこれを使用します。

${\displaystyle \sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.}$

この仮定の下では、最初の行を省略して、順列を1行表記で次のように書くことができる。

${\displaystyle \sigma =\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n})}$、

すなわち、Sの要素の順序付けられた配置として。^{[ 22 ] [ 23 ]}下記で説明するサイクル表記と一行表記を区別するように注意する必要がある。一般的な用法としては、一行表記では括弧やその他の囲み記号を省略し、サイクル表記では括弧を使用する。一行表記はワード表現とも呼ばれる。^{[ 24 ]}

上記の例は次のようになります。

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5&6\\2&6&5&4&3&1\end{pmatrix}}=265431.}$

（これらの項目を区切るためにカンマを使用するのは、一部の項目に2桁以上の数字が含まれる場合に限るのが一般的です。）

この簡潔な形式は、初等的な組み合わせ論やコンピュータサイエンスでよく用いられます。特に、順列を辞書式順序を用いて大きいか小さいかで比較するような用途で役立ちます。

サイクル表記は、集合Sの要素に置換を繰り返し適用する効果を表し、その軌道をサイクルと呼びます。置換はサイクルのリストとして記述されます。異なるサイクルは互いに素な要素の集合を含むため、これは「互いに素なサイクルへの分解」と呼ばれます。

順列を書き出す${\displaystyle \sigma }$サイクル表記では、次のように進めます。

1. 開き括弧の後に任意の要素xを記述します${\displaystyle S}$: ${\displaystyle (\,x}$
2. xの軌道をたどり、次の値を連続的に適用して書き留めます。${\displaystyle \sigma }$:${\displaystyle (\,x,\sigma (x),\sigma (\sigma (x)),\ldots }$
3. 値がx に戻るまで繰り返し、x を繰り返さずに括弧を閉じます。${\displaystyle (\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)}$
4. まだ書き込まれていないSの要素yについて、上記の手順を繰り返します。${\displaystyle (\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)(\,y\,\ldots \,)}$
5. Sのすべての要素が循環的に記述されるまで繰り返す。

また、1サイクルは推論できるため省略するのが一般的です。S内のどのサイクルにも現れない任意の要素xについては、暗黙のうちに次のことが仮定されます。${\displaystyle \sigma (x)=x}$[ ^{25 ]​}

1サイクルを省略するという慣例に従うと、個々のサイクルは、サイクルに含まれないすべての要素を固定する順列（長さが1より大きいサイクルが1つだけ存在する巡回順列）として解釈できます。すると、互いに素なサイクルのリストは、これらの巡回順列の合成として見なすことができます。たとえば、1行順列${\displaystyle \sigma =265431}$サイクル表記では次のように表すことができます。 $${\displaystyle \sigma =(126)(35)(4)=(126)(35)。}$$ これは構成と見なすことができる${\displaystyle \sigma =\kappa _{1}\kappa _{2}}$巡回置換の $${\displaystyle \kappa _{1}=(126)=(126)(3)(4)(5),\quad \kappa _{2}=(35)=(35)(1)(2)(4)(6).}$$ 一般的に順列は可換ではないが、互いに素なサイクルは可換である。例えば、次のようになる。 $${\displaystyle \sigma =(126)(35)=(35)(126)。}$$ また、各サイクルは異なる開始点から書き換えることができます。たとえば、 $${\displaystyle \sigma =(126)(35)=(261)(53)。}$$ したがって、与えられた順列の互いに素なサイクルは、さまざまな方法で記述することができる。

サイクル表記の便利な特徴は、各サイクル内の要素の順序を逆にすることで順列を反転できることです。たとえば、 $$\displaystyle \sigma ^{-1}=\left({\vphantom {A^{2}}}(126)(35)\right)^{-1}=(621)(53).}$$

任意の順列には、多くの組み合わせ論的文脈、特に後述するフォアタの全単射において有用な、特定のサイクル表記法が存在する。標準的なサイクル表記法は次のように定義される。

• 各サイクルにおいて、最大の要素が最初にリストされる。
• サイクルは、最初の要素の昇順にソートされ、1サイクルも除外されません。

例えば、$${\displaystyle (513)(6)(827)(94)}$$は順列です${\displaystyle S=\{1,2,\ldots ,9\}}$標準サイクル記法（ミクロス・ボーナの用語）では、^{[ 26 ]}リチャード・スタンレーはこれを標準表現と呼び、^{[ 27 ]}マーティン・アイグナーは標準形式を使用しています。^{[ 24 ]}セルゲイ・キタエフも「標準形式」という用語を使用していますが、両方の選択を逆にしています。つまり、各サイクルは最初にその最小要素をリストし、サイクルは最小要素の降順でソートされます。^{[ 28 ]}

2 つの順列の合成を表す方法は 2 つあります。最も一般的な表記法では、${\displaystyle \sigma \cdot \tau }$は、任意の要素xを にマッピングする関数です。${\displaystyle \sigma (\tau (x))}$最も右側の順列が最初に引数に適用されます。^{[ 29 ]} なぜなら、引数は関数の右側に書かれているからです。

順列の乗算に関する別の規則は、関数の左側に引数を記述することによって得られます。これにより、最も左側の順列が最初に作用します。^{[ 30 ] [ 31 ] [ 32 ]} この表記では、順列はしばしば指数として記述されるため、xに作用するσはx ^σと記述されます。すると、積は次のように定義されます。$${\displaystyle x^{\sigma \cdot \tau }=(x^{\sigma })^{\tau }}$$この記事では、最も右側の順列を最初に適用する最初の定義を使用します。

関数合成演算は群の公理を満たします。結合法則を満たします。${\displaystyle (\rho \sigma )\tau =\rho (\sigma \tau )}$、また、2 つ以上の順列の積は通常括弧なしで記述されます。合成演算には単位元(単位順列)もあります。${\displaystyle {\text{id}}}$）、そして各順列${\displaystyle \sigma }$逆数を持つ$\displaystyle \sigma ^{-1}}$（その逆関数）${\displaystyle \sigma ^{-1}\sigma =\sigma \sigma ^{-1}={\text{id}}}$。

古い文献や初等教科書では、nのk順列(部分順列、重複のないシーケンス、バリエーション、または配置と呼ばれることもある) は、 n個の集合のk個の要素からなる部分集合の順序付き配置 (リスト) を意味する。^{[ c ] [ 33 ] [ 34 ]}このようなk順列 ( k配置)の数は、${\displaystyle n}$は、次のような記号で様々に表されます。${\displaystyle P_{k}^{n}}$、 ${\displaystyle _{n}P_{k}}$、${\displaystyle ^{n}\!P_{k}}$、${\displaystyle P_{n,k}}$、${\displaystyle P(n,k)}$、 または${\displaystyle A_{n}^{k}}$[ ^{35 ]}式^{[ 36 ]で計算される。}$${\displaystyle P(n,k)=\underbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} _{k\ \mathrm {factors} },}$$

k > nの場合は 0 であり、それ以外の場合は次の値になります。 $${\displaystyle {\frac {n!}{(nk)!}}.}$$

この製品は、${\displaystyle n}$は非負整数であり、組み合わせ論以外でも重要です。ポッホハマー記号として知られています。${\displaystyle (n)_{k}}$または${\displaystyle k}$- 番目の下降階乗${\displaystyle n^{\underline {k}}}$: $${\displaystyle P(n,k)={_{n}}P_{k}=(n)_{k}=n^{\underline {k}}.}$$

この順列という用語の使い方は、部分集合を意味する組み合わせという用語と密接に関連しています。つまり、集合Sのk 組み合わせは、 Sのk個の要素からなる（順序付けされていない）部分集合です。Sのk組み合わせを考えられるすべての方法で順序付けると、S の k 順列が得られます。したがって、n個の集合のk組み合わせの数C ( n , k ) は、 nのk順列の数と次の関係にあります。 $${\displaystyle C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(nk)!\,k!}}.}$$

これらの数値は二項係数とも呼ばれ、通常は次のように表記されます。${\displaystyle {\tbinom {n}{k}}}$: $${\displaystyle C(n,k)={_{n}}C_{k}={\binom {n}{k}}.}$$

集合Sのk個の要素の順序付けられた配列で、繰り返しが許されるものをkタプルと呼びます。これらは、通常の意味での順列ではありませんが、繰り返しのある順列と呼ばれることもあります。また、アルファベットS上の単語または文字列とも呼ばれます。集合S がn個の要素を持つ場合、 S上のkタプルの数は、${\displaystyle n^{k}.}$

Mが有限多重集合である場合、多重集合順列とは、 Mの要素を順序付けた配列であり、各要素はMにおけるその重複度と正確に等しい回数だけ出現する。いくつかの文字が繰り返される単語のアナグラムは、多重集合順列の例である。^{[ d ]} Mの要素の重複度（ある順序で）が${\displaystyle m_{1}}$、${\displaystyle m_{2}}$、...、${\displaystyle m_{l}}$そしてそれらの合計（つまりMのサイズ）がnである場合、 Mの多重集合順列の数は多項係数によって与えられる：^{[ 37 ]}$${\displaystyle {n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}={\frac {\left(\sum _{i=1}^{l}{m_{i}}\right)!}{\prod _{i=1}^{l}{m_{i}!}}}.}$$ 例えば、MISSISSIPPI という単語の異なるアナグラムの数は^{[ 38 ]です。}$${\displaystyle {\frac {11!}{1!\,4!\,4!\,2!}}=34650.}$$

多重集合Mのk置換とは、 Mのk個の要素からなる列であり、各要素はMにおけるその要素の重複度(要素の繰り返し回数)以下で出現する。この場合、置換の数は生成関数によって決定できる。${\displaystyle k!}$係数の倍${\displaystyle x^{k}}$製品の中で

${\displaystyle \prod _{i=1}^{l}\sum _{j=0}^{m_{i}}{\frac {x^{j}}{j!}}}$[ ^{39 ]​}

上記の例を続けると、MISSISSIPPI の文字の多重集合の場合、結果として得られる生成関数は次のようになります。 $${\displaystyle {\begin{aligned}&(1+x)\cdot (1+x+x^{2}/2)\cdot (1+x+x^{2}/2+x^{3}/6+x^{4}/24)^{2}=\\&1+4x+{\frac {15}{2!}}x^{2}+{\frac {53}{3!}}x^{3}+{\frac {176}{4!}}x^{4}+{\frac {550}{5!}}x^{5}+{\frac {1610}{6!}}x^{6}+{\frac {4340}{7!}}x^{7}+{\frac {10430}{8!}}x^{8}+{\frac {21420}{9!}}x^{9}+{\frac {34650}{10!}}x^{10}+{\frac {34650}{11!}}x^{11}.\end{aligned}}}$$ したがって、11-順列の数は34650（上記と同じ結果）ですが、kが0から11までの範囲のk-順列の数も得られます。

順列は、配置として考えると、線形順序の配置と呼ばれることがあります。しかし、対象が円形に配置されている場合、この区別された順序は弱まります。どの要素も開始要素とみなせるため、配置には「最初の要素」はありません。異なる対象を円形に配置することを円形順列と呼びます。^{[ 40 ] [ e ]}これらは、線形配置の最後の要素を先頭に移動することによって生成される同値関係に関して、これらの対象の通常の順列の同値類として形式的に定義できます。

2つの円順列は、一方を回転させて他方に変換できる場合に同等である。以下の4つの文字に関する4つの円順列は、同等であるとみなされる。

$${\displaystyle {\begin{matrix}&1&\\4&&3\\&2&\end{matrix}}\qquad {\begin{matrix}&4&\\2&&1\\&3&\end{matrix}}\qquad {\begin{matrix}&2&\\3&&4\\&1&\end{matrix}}\qquad {\begin{matrix}&3&\\1&&2\\&4&\end{matrix}}}$$

円形の配置は反時計回りに読むため、回転によって一方を他方に合わせることはできないので、以下の2つは等価ではありません。

$${\displaystyle {\begin{matrix}&1&\\4&&3\\&2&\end{matrix}}\qquad {\begin{matrix}&1&\\3&&4\\&2&\end{matrix}}}$$

n個の要素を持つ集合には、 ( n – 1)!個の円順列が存在する。

順列のサイクル（固定点を含む）${\displaystyle \sigma }$n個の要素を持つ集合のサイクルは、その集合を分割します。したがって、これらのサイクルの長さはnの整数分割を形成し、これはサイクルタイプ(またはサイクル構造またはサイクル形状)と呼ばれます。${\displaystyle \sigma }$サイクルタイプには、固定点ごとに「1」があります。${\displaystyle \sigma }$、転置ごとに「2」、など。サイクルタイプは${\displaystyle \beta =(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)}$は${\displaystyle (3,2,2,1).}$

これはより簡潔な形式で[1 ¹ 2 ² 3 ¹ ]と書くこともできます。より正確には、一般形は次のようになります。${\displaystyle [1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]}$、 どこ${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$はそれぞれの長さのサイクルの数です。特定のサイクルタイプの順列の数は^{[ 42 ]です。}

${\displaystyle {\frac {n!}{1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}\alpha _{1}!\alpha _{2}!\dotsm \alpha _{n}!}}}$。

n個の要素を持つ集合のサイクルタイプの数は、分割関数の値に等しい。${\displaystyle p(n)}$。

ポリアのサイクル指数多項式は、順列をそのサイクルタイプごとに数える生成関数である。

一般に、サイクル記法で記述された順列の合成は、簡単に説明できるパターンには従わない。合成のサイクルは、合成されるサイクルとは異なる場合がある。ただし、順列を共役させるという特殊なケースでは、サイクルタイプは保持される。${\displaystyle \sigma }$別の順列によって${\displaystyle \pi }$つまり、製品を形成するということです。${\displaystyle \pi \sigma \pi ^{-1}}$。 ここ、${\displaystyle \pi \sigma \pi ^{-1}}$は共役です${\displaystyle \sigma }$による${\displaystyle \pi }$そしてそのサイクル表記は、サイクル表記を次のようにすることで得られる。${\displaystyle \sigma }$適用${\displaystyle \pi }$その中のすべてのエントリに対して。^{[ 43 ]}したがって、2 つの順列は、同じサイクル タイプを持つ場合にのみ共役であることがわかります。

順列の順序${\displaystyle \sigma }$は、​${\displaystyle \sigma ^{m}=\mathrm {id} }$。これは、そのサイクルの長さの最小公倍数です。たとえば、${\displaystyle \sigma =(152)(34)}$は${\displaystyle {\text{lcm}}(3,2)=6}$。

有限集合のすべての順列は、転置の積として表すことができます。^{[ 44 ]} 与えられた順列に対してそのような表現は多数存在する可能性がありますが、それらはすべて偶数個の転置を含むか、すべて奇数個の転置を含むかのどちらかです。したがって、すべての順列はこの数に応じて偶数または奇数に分類できます。

この結果は、符号を割り当てるように拡張することができ、次のように記述される。${\displaystyle \operatorname {sgn} \sigma }$それぞれの順列に対して。${\displaystyle \operatorname {sgn} \sigma =+1}$もし${\displaystyle \sigma }$は均等で${\displaystyle \operatorname {sgn} \sigma =-1}$もし${\displaystyle \sigma }$奇数です。次に、2 つの順列について${\displaystyle \sigma }$そして${\displaystyle \pi }$

${\displaystyle \operatorname {sgn} (\sigma \pi )=\operatorname {sgn} \sigma \cdot \operatorname {sgn} \pi .}$

したがって、${\displaystyle \operatorname {sgn} \left(\sigma \sigma ^{-1}\right)=+1.}$

順列の符号は、その順列行列の行列式に等しい（下記参照）。

順列行列は、各列と各行にちょうど1つの要素1を持ち、他のすべての要素が0であるn × n行列です。{1, 2, ..., n }の順列に順列行列を割り当てる方法はいくつかあります。自然なアプローチの1つは、次のように定義することです。${\displaystyle L_{\sigma }}$線形変換である${\displaystyle \mathbb {R} ^{n}}$これは標準基底を置換する${\displaystyle \{\mathbf {e} _{1},\ldots ,\mathbf {e} _{n}\}}$による${\displaystyle L_{\sigma }(\mathbf {e} _{j})=\mathbf {e} _{\sigma (j)}}$、そして定義する${\displaystyle M_{\sigma }}$その行列となる。つまり、${\displaystyle M_{\sigma }}$j^番目の列がn × 1 列ベクトルと等しい${\displaystyle \mathbf {e} _{\sigma (j)}}$: その ( i , j ) 要素は、 i = σ ( j )の場合に 1、それ以外の場合は 0 です。線形写像の合成は行列乗算によって記述されるため、この構成は置換の合成と互換性があることがわかります。 $${\displaystyle M_{\sigma }M_{\tau }=M_{\sigma \tau }.}$$ 例えば、1行順列${\displaystyle \sigma =213,\ \tau =231}$製品があります${\displaystyle \sigma \tau =132}$、対応する行列は次のとおりです。 $${\displaystyle M_{\sigma }M_{\tau }={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}=M_{\sigma \tau }.}$$

文献では、行列に置換σが関連付けられる逆の慣例もよく見られる。${\displaystyle P_{\sigma }=(M_{\sigma })^{-1}=(M_{\sigma })^{T}}$その ( i , j ) 要素は、 j = σ ( i )の場合に 1 であり、それ以外の場合は 0 です。この規約では、順列行列は順列とは逆の順序で乗算されます。つまり、${\displaystyle P_{\sigma }P_{\tau }=P_{\tau \sigma }}$この対応関係では、置換行列は標準の右側に作用する。${\displaystyle 1\times n}$行ベクトル${\displaystyle ({\bf {e}}_{i})^{T}}$:${\displaystyle ({\bf {e}}_{i})^{T}P_{\sigma }=({\bf {e}}_{\sigma (i)})^{T}}$。

右側のケイリー表は、3つの要素の順列に対するこれらの行列を示しています。

nの順列σの 上昇とは、次の値が現在の値より大きい位置i < nの任意の位置のことです。つまり、iが上昇であるのは、   ${\displaystyle \sigma (i)<\sigma (i{+}1)}$例えば、順列3452167は、1、2、5、6の位置に上昇位置を持ちます。

同様に、降下とは、 i < nの位置で、  ${\displaystyle \sigma (i)>\sigma (i{+}1)}$だから、すべてのiは${\displaystyle 1\leq i<n}$上昇か下降のどちらかです。

順列の昇順列とは、両端で延長できない、空でない連続した増加部分列のことです。これは、連続する上昇の最大列に対応します（後者は空列になることもあります。連続する2つの下降の間には、長さ 1の昇順列が存在します）。これに対し、順列の増加部分列は必ずしも連続しているとは限りません。これは、1行表記の値の一部を省略して得られる増加列です。例えば、順列2453167には、昇順列245、3、167がありますが、増加部分列は2367です。

順列にk  −  1 回の降下がある場合、それはk回の昇順の和集合でなければならない。^{[ 45 ]}

k回の上昇を伴うnの順列の数は、（定義により）オイラー数である。${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$これは、 k回の降下を伴うnの順列の数でもあります。ただし、一部の著者はオイラー数を定義しています。${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$k 回の上昇ランを持つ順列の数として、これはk − 1 回の降下に対応します。^{[ 46 ]}

順列σ ₁ σ ₂ ... σ _nの超過とは、σ _j > jとなるインデックスjのことである。不等式が厳密でない場合 (つまり、σ _j ≥ jの場合)、jは弱い超過と呼ばれる。k個の超過を持つn順列の数は、k 個の降下を持つn順列の数と一致する。^{[ 47 ]}

順列σのレコードまたは左から右への最大値は、すべてのj < iに対してσ ( j ) < σ ( i )となる要素iです。

Foataの基本全単射は、与えられた標準サイクル形式を持つ置換σを置換に変換します。${\displaystyle f(\sigma )={\hat {\sigma }}}$その一行表記では、括弧を除いた同じ要素のシーケンスが表されます。^{[ 27 ] [ 48 ]}例えば： $${\displaystyle \sigma =(513)(6)(827)(94)={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&7&5&9&1&6&8&2&4\end{pmatrix}},}$$

$${\displaystyle {\hat {\sigma }}=513682794={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\5&1&3&6&8&2&7&9&4\end{pmatrix}}.}$$

ここで、 σの各標準サイクルの最初の要素は、レコード (左から右への最大値) になります。${\displaystyle {\hat {\sigma }}}$与えられた${\displaystyle {\hat {\sigma }}}$逆変換を構築するには、そのレコードを見つけて括弧を挿入すればよい。${\displaystyle \sigma =f^{-1}({\hat {\sigma }})}$上記の例で、該当​​するレコードに下線を引く：${\displaystyle {\hat {\sigma }}={\underline {5}}\,1\,3\,{\underline {6}}\,{\underline {8}}\,2\,7\,{\underline {9}}\,4}$これにより、 σのサイクルを再構築することが可能になります。

以下の表は${\displaystyle {\hat {\sigma }}}$S = {1, 2, 3}の 6 つの順列に対するσについて、各辺の太字は全単射で使用される表記法を示しています。${\displaystyle {\hat {\sigma }}}$σの正準サイクル表記。

$${\displaystyle {\begin{array}{l|l}{\hat {\sigma }}=f(\sigma )&\sigma =f^{-1}({\hat {\sigma }})\\\hline \mathbf {123} =(\,1\,)(\,2\,)(\,3\,)&123=\mathbf {(\,1\,)(\,2\,)(\,3\,)} \\\mathbf {132} =(\,1\,)(\,3\,2\,)&132=\mathbf {(\,1\,)(\,3\,2\,)} \\\mathbf {213} =(\,2\,1\,)(\,3\,)&213=\mathbf {(\,2\,1\,)(\,3\,)} \\\mathbf {231} =(\,3\,1\,2\,)&321=\mathbf {(\,2\,)(\,3\,1\,)} \\\mathbf {312} =(\,3\,2\,1\,)&231=\mathbf {(\,3\,1\,2\,)} \\\mathbf {321} =(\,2\,)(\,3\,1\,)&312=\mathbf {(\,3\,2\,1\,)} \end{array}}}$$第一の系として、レコードがちょうどk個あるn順列 の数は、サイクルがちょうどk個あるn順列の数に等しい。この最後の数は、符号なしの第 1 種スターリング数である。${\displaystyle c(n,k)}$さらに、Foataのマッピングは、k個の弱い超過を持つn個の順列を、 k -1個の上昇を持つn個の順列に変換します。^{[ 48 ]} 例えば、(2)(31) = 321はk = 2個の弱い超過を持ち（インデックス1と2）、f (321) = 231はk -1 = 1個の上昇を持ちます（インデックス1、つまり2から3へ）。

順列σの反転とは、順列の要素の順序が逆になっている位置のペア( i , j )のことである。 ${\displaystyle i<j}$そして${\displaystyle \sigma (i)>\sigma (j)}$^{[ 50 ]}したがって、 降下とは、隣接する 2 つの位置での反転のことです。たとえば、σ = 23154では、( i , j ) = (1, 3)、(2, 3)、(4, 5) であり、ここで ( σ ( i ), σ ( j )) = (2, 1)、(3, 1)、(5, 4) です。

反転は値のペア ( σ ( i ), σ ( j )) として定義されることもあります。これは反転の数には影響しません。また、逆ペア ( σ ( j ), σ ( i )) は、逆順列σ ⁻¹に対して上記の意味で反転となります。

反転の数は、順列の要素がどの程度順不同であるかを示す重要な尺度であり、σとσ ^{−1で同じです。k}個の反転を持つ順列を正しい順序に戻す（つまり、恒等順列に変換する）には、隣接する転置を順次適用（右乗算）することで常に可能であり、 k回のそのような操作のシーケンスが必要です。さらに、隣接する転置には任意の妥当な選択で十分です。各ステップで、i をそれまでに修正された順列の降順としたときの i と i + 1 の転置を選択すれば十分です（転置によってこの特定の降順は削除されますが、他の降順が生成される場合があります）。これは、このような転置を適用すると反転の数が1 減少するためです。この数がゼロでない限り、順列は恒等順列ではないため、少なくとも 1 つの降順が存在します。バブルソートと挿入ソートは、この手順でシーケンスを正しい順序にするための特殊な例と解釈できます。ちなみに、この手順は、任意の置換σが隣接する転置の積として表せることを証明しています。これは、 σを恒等式に変換するような転置の任意のシーケンスを単純に反転させればよいからです。実際、σを恒等式に変換する隣接する転置のすべてのシーケンスを列挙することで、（反転後）σを隣接する転置の積として表す最小長のすべての式の完全なリストが得られます。 

nのk回の反転を伴う順列の数は、マホニアン数で表されます。^{[ 51 ]}これは、${\displaystyle q^{k}}$製品の拡張において

$${\displaystyle [n]_{q}!=\prod _{m=1}^{n}\sum _{i=0}^{m-1}q^{i}=1\left(1+q\right)\left(1+q+q^{2}\right)\cdots \left(1+q+q^{2}+\cdots +q^{n-1}\right),}$$

表記法${\displaystyle [n]_{q}!}$はq 階乗を表します。この展開はネックレスの研究でよく見られます。

させて${\displaystyle \sigma \in S_{n},i,j\in \{1,2,\dots ,n\}}$そのため${\displaystyle i<j}$そして${\displaystyle \sigma (i)>\sigma (j)}$この場合、逆転の重みを${\displaystyle (i,j)}$は${\displaystyle \sigma (i)-\sigma (j)}$小林（2011）は列挙式を証明した。 $${\displaystyle \sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}}$$

どこ${\displaystyle \leq }$は対称群におけるブルハット順序を表します。この次数付き半順序は、コクセター群の文脈でよく現れます。

n個のものの順列を表す方法の 1 つは、 0 ≤ N < n ! を満たす整数Nを用いることです。ただし、数値と順列を順序付き配列 (シーケンス) として表現した形式との間で変換するための便利な方法が用意されていることが前提となります。これは任意の順列を最もコンパクトに表現する方法であり、コンピュータにおいては、Nがマシン ワードに収まるほどnが小さい場合に特に有効です。32 ビット ワードの場合、これはn ≤ 12 を意味し、64 ビット ワードの場合、これはn ≤ 20 を意味します。変換は、数値のシーケンスd _n、d _{n −1}、...、d ₂、d ₁の中間形式を介して行うことができます。ここで、 d _iはiより小さい非負の整数です( d ₁は常に 0 なので省略できますが、d 1 が存在すると、その後の順列への変換の説明が容易になります)。まず最初のステップは、N を階乗数体系で表現することです。これは、n !より小さい数の場合、連続する桁の基数 (位取りまたは乗数) が( n − 1)!、( n − 2)!、...、2!、1! となるような、特定の混合基数表現です。2 番目のステップでは、この数列をレーマー符号、または (ほぼ同等に) 反転表として解釈します。        

順列σのレーマーコードでは、数値d _{n は}最初の項σ ₁の選択を表し、数値d _{n −1}は残りのn − 1個の要素の中から 2 番目の項σ ₂の選択を表し 、以下同様です。より正確には、各d _{n +1− i は}項σ _iより厳密に小さい残りの要素の数を表します。これらの残りの要素は、後の項σ _jとして必ず現れるため、数値d _{n +1− i}は、 i をより小さいインデックスとして含む反転( i , j )の数 ( i < jかつσ _i > σ _jとなる値jの数)をカウントします。σの反転表もほぼ同じですが、ここではd _{n +1− k は}、 k = σ _jが反転した順序で現れる 2 つの値のうち小さい方として現れる反転 ( i , j )の数をカウントします。 ^{[ 52 ]}         

どちらのエンコーディングも、n  × nローテ図^{[ 53 ]} (ハインリヒ・アウグスト・ローテにちなんで命名) で視覚化できます。この図では、( i , σ _i ) の点が順列のエントリを示し、( i , σ _j ) の十字が反転 ( i , j ) を示します。反転の定義により、十字は、列の点 ( j , σ _j ) と行の点 ( i , σ _i ) の両方の前に来る任意の正方形に表示されます。レーマーコードは連続する行の十字の数をリストし、反転表は連続する列の十字の数をリストします。これは、逆順列のレーマーコードであり、その逆も同様です。 

レーマーコードd _n、d _{n −1}、 ...、d ₂、d ₁を順序付き集合Sの順列に効果的に変換するには、まずSの要素を昇順に並べたリストから始め、 iが1 からnまで増加するにつれて、 σ _{i を}リスト内の他のd _{n +1− i}個の要素に先行する要素に設定し、その要素をリストから削除します。反転表d _n、d _{n −1}、 ...、d ₂、d _{1を対応する順列に変換するには、} d _1からd _nまでの数値をたどりながら、最初は空のシーケンスにSの要素を大きい順から小さい順に挿入します。反転表の数値dを使用するステップでは、 Sの要素を、すでに存在するd個の要素に先行する位置にシーケンスに挿入します。あるいは、 n個の空きスロットの行から始めて、反転表の数値とSの要素の両方を逆の順序で処理し、各ステップで、 d個の空きスロットの前の空きスロットにSの要素を配置することもできます。

連続する自然数を階乗数体系に変換すると、それらの数列は辞書式順序で生成されます(これは、混合基数数体系の場合と同様です)。さらにそれらを順列に変換すると、レーマー符号の解釈が使用されている限り、辞書式順序が保持されます (反転表を使用すると、順列を最初のエントリの値ではなくエントリ 1 の位置で比較することから始まる、異なる順序になります)。階乗数体系表現における数値の合計は順列の反転の数を示し、その合計の偶奇性は順列の符号を示します。さらに、反転表のゼロの位置は順列の左から右への最大値 (例では 6、8、9) を示し、レーマー符号のゼロの位置は右から左への最小値 (例では値 1、2、5 の 4、8、9 の位置) を示します。これにより、すべての順列におけるそのような極値の分布を計算できます。レーマーコードd _n、d _{n −1}、 ...、d ₂、d _{1を持つ順列は、} d _i ≥ d _{i +1}の場合に限り、上昇n − iを持ちます。

計算においては、与えられた値列の順列を生成する必要が生じる場合があります。最適な方法は、ランダムに選択された順列の一部が必要なのか、すべての順列が必要なのか、そして後者の場合、特定の順序付けが必要かどうかによって異なります。また、与えられた値列の要素間に等しい値が存在する可能性を考慮する必要があるかどうかも問題となります。もし考慮する必要があるならば、異なる多重集合の順列のみを生成すべきです。

nの順列を生成する明白な方法は、レーマー符号の値（おそらくnまでの整数の階乗数表現を使用）を生成し、それらを対応する順列に変換することです。しかし、後者の手順は単純ではありますが、任意の位置でシーケンスからの選択と削除をそれぞれn回行う必要があるため、効率的に実装するのは困難です。シーケンスを配列またはリンクリストとして表現する場合、どちらも（異なる理由で）変換を実行するために約n ^{2/4回の操作が必要です。n は比較的小さい場合}（特にすべての順列の生成が必要な場合）はそれほど大きな問題ではありませんが、ランダム生成と体系的生成の両方において、はるかに優れた単純な代替手段が存在することがわかっています。このため、レーマー符号から順列への変換をO ( n log n )時間で実行できる特別なデータ構造を使用することは、確かに可能ですが、有用ではないようです。

nから2までiをループし、 d i ← { 0, ..., i − 1 } のランダムな要素をループし、 a [ d i ] とa [ i − 1 ]を交換します。

iを0からn −1まで繰り返すd i +1 ← { 0, ..., i } のランダムな要素a [ i ] ← a [ d i +1 ] a [ d i +1 ] ← i

最小限の変更を加えた生成

上記のアルゴリズムの代替として、スタインハウス・ジョンソン・トロッターアルゴリズムがあり、これは、出力内の連続する2つの順列が隣接する2つの値を入れ替えることで異なるという性質を持つ、与えられたシーケンスのすべての順列の順序を生成します。この順列の順序は、17世紀のイギリスの鐘つき職人に知られており、彼らの間では「プレーンチェンジ」として知られていました。この方法の利点の1つは、1つの順列から次の順列への変化が小さいため、1つの順列あたり定数時間で実装できることです。また、出力順列を1つおきにスキップすることで、偶数順列のサブセットも簡単に生成でき、これも1つの順列あたり定数時間で実行できます。^{[ 57 ]}

スタインハウス-ジョンソン-トロッターの代替としてヒープのアルゴリズム^{[ 59 ]}があり、ロバート・セジウィックは1977年に、これは応用において最も速い順列生成アルゴリズムであると述べている^{[ 56 ] 。}

次の図は、長さのすべての順列を生成するための、前述の3つのアルゴリズムすべての出力を示しています。${\displaystyle n=4}$および文献に記載されている6つの追加アルゴリズム。

1. 辞書式順序付け。
2. シュタインハウス・ジョンソン・トロッターアルゴリズム;
3. ヒープのアルゴリズム;
4. エーリッヒのスター転置アルゴリズム：^{[ 57 ]}各ステップで、順列の最初のエントリが後のエントリと交換されます。
5. ザックスの接頭辞反転アルゴリズム：^{[ 61 ]}各ステップで、現在の順列の接頭辞を反転して次の順列を取得します。
6. 澤田-ウィリアムズのアルゴリズム: ^{[ 62 ]}各順列は、1 ポジションの巡回左シフトまたは最初の 2 つのエントリの交換のいずれかによって前の順列と異なります。
7. コーベットのアルゴリズム：^{[ 63 ]}各順列は、ある接頭辞を1つ左に巡回シフトすることによって前の順列と異なります。
8. シングルトラック順序付け: ^{[ 64 ]}各列は他の列の巡回シフトです。
9. シングルトラックグレイコード：^{[ 64 ]}各列は他の列の巡回シフトであり、さらに連続する2つの順列は1つまたは2つの転置のみが異なる。
10. 入れ子になったスワップ生成アルゴリズムは、入れ子になったサブグループに関連するステップで構成されています。${\displaystyle S_{k}\subset S_{k+1}}$各順列は、前の順列から左への転置乗算によって得られます。このアルゴリズムは、インデックスの階乗数システムと関連しています。

順列は、ターボ符号などの誤り検出訂正アルゴリズムの インターリーバコンポーネントで使用されます。たとえば、3GPP Long Term Evolution移動体通信規格ではこれらのアイデアが使用されています (3GPP 技術仕様 36.212 ^{[ 66 ]} を参照)。このようなアプリケーションでは、特定の望ましい特性を満たす順列を高速に生成するという問題が生じます。その方法の 1 つは順列多項式に基づいています。また、Unique Permutation Hashing における最適なハッシュのベースとしても使用されます。^{[ 67 ]}