順列

数学では、集合の順列は次の 2 つの異なる意味のいずれかを意味します。

• メンバーを連続的または直線的な順序で配置すること、または
• 順序付けられた集合の線形順序を変更する行為またはプロセス。^[1]

最初の意味の例は、集合 {1, 2, 3} の 6 つの順列 (順序) です。組で書くと、(1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、(3, 2, 1) となります。文字がすべて異なる単語のアナグラムも順列です。元の単語では文字がすでに順序付けられており、アナグラムでは文字が順序付けられます。有限集合の順列の研究は、組合せ論と群論の重要なトピックです。

順列は数学のほぼすべての分野と科学の多くの他の分野で使用されています。コンピューター サイエンスでは、ソート アルゴリズムの分析に使用され、量子物理学では粒子の状態を記述するために使用され、生物学ではRNA配列を記述するために使用されています。

n 個の異なるオブジェクトの順列の数はn の 階乗であり、通常はn !と表記され、これはn以下のすべての正の整数の積を意味します。

2番目の意味によれば、集合 Sの順列はSからそれ自身への全単射として定義される。 ^{[2] [3]}つまり、それはSからSへの関数であり、そのすべての要素は像値としてちょうど1回出現する。このような関数は、Sの各要素iを対応する に置き換えるSの要素の並べ替えに等しい。例えば、順列(3, 1, 2)は次のように定義される 関数によって記述される。${\displaystyle \sigma :S\to S}$${\displaystyle \sigma (i)}$${\displaystyle \sigma}$

${\displaystyle \sigma (1)=3,\quad \sigma (2)=1,\quad \sigma (3)=2}$。

集合のすべての順列の集合は、集合の対称群と呼ばれる群を形成します。群演算は関数の合成（1 つの並べ替えを次々に実行する）であり、その結果、別の関数（並べ替え）が生成されます。順列の特性は、並べ替えられる要素の性質には依存せず、その数だけに依存するため、標準集合が考慮されることがよくあります。 ${\displaystyle S=\{1,2,\ldots ,n\}}$

初等組合せ論では、k順列または部分順列は、集合から選択されたk個の異なる要素の順序付けられた配置です。 k が集合のサイズに等しい場合、これらは前述の意味での順列です。

六十四卦と呼ばれる順列のようなものは、紀元前 1000 年頃にはすでに中国の易経(ピンイン: 易経) で使用されていました。

ギリシャでは、プルタルコスはカルケドンのクセノクラテス（紀元前396-314年）がギリシャ語で可能な音節の数を発見したと書いている。これは順列と組み合わせの難しい問題を解こうとした記録上最初の試みだったと思われる。^[4]

アラブの数学者で暗号学者のアル＝ハリール（717-786）は『暗号文の書』を著した。この本には、順列と組み合わせを初めて使用し、母音の有無にかかわらずすべてのアラビア語の単語を列挙している。^[5]

n 個の物体の順列の数を決定する規則は、西暦 1150 年頃にインド文化で知られていました。インドの数学者バースカラ 2 世の著作「リラヴァティ」には、次のように翻訳される一節があります。

1から始まり1ずつ増加し、桁数まで続く等差数列の乗算の積は、特定の数字を持つ数のバリエーションになります。^[6]

1677 年、ファビアン・ステッドマンは、チェンジ リンギングにおける鐘の順列の数を説明する際に階乗について説明しました。2 つの鐘から始め、「まず、2 つの鐘は 2 通りの方法で変化することが認められなければならない」と述べ、1 2 と 2 1 を示してこれを説明しています。 ^[7] 次に、3 つの鐘では「3 つの鐘から 3 倍の 2 つの数字が生成される」と説明し、これもまた図解されています。彼の説明には、「3 を捨てれば 1.2 が残り、2 を捨てれば 1.3 が残り、1 を捨てれば 2.3 が残る」という内容が含まれています。^[8] 次に、4 つの鐘に移り、捨てる議論を繰り返し、3 つの鐘が 4 つの異なるセットになることを示しました。実質的に、これは再帰的なプロセスです。彼は 5 つの鐘で「捨てる」方法を使用し続け、結果として生じる 120 通りの組み合わせを表にまとめています。^[9] この時点で、彼はあきらめて次のように述べています。

これらの方法の性質は、1つの数の変化がすべてのより小さな数の変化を包含し、... 1つの数の変化の完全な音は、すべてのより小さな数の変化の完全な音を1つの全体に統合することによって形成されるように見えるというものである。^[10]

ステッドマンは順列の考察を広げ、アルファベットの文字の順列の数と20頭の馬小屋の馬の順列の数を考察している。^[11]

一見無関係な数学の問題が順列を利用して研究された最初の事例は、1770年頃に発生しました。ジョゼフ・ルイ・ラグランジュが多項式方程式の研究において、方程式の根の順列の特性がそれを解く可能性に関連していることを観察したのです。この一連の研究は最終的に、エヴァリスト・ガロアの研究を通じてガロア理論につながり、ガロア理論は、根号によって多項式方程式（未知数が1つ）を解くことに関して何が可能で何が不可能であるかを完全に説明しています。現代数学では、問題を理解するためにそれに関連する特定の順列を研究する必要がある、同様の状況が数多くあります。

順列は、第二次世界大戦中にナチスドイツが使用した暗号装置であるエニグマ暗号の解読において重要な役割を果たした。特に、順列の重要な特性の1つである、2つの順列が同じサイクルタイプを持つ場合に正確に共役であるという特性は、暗号学者マリアン・レイェフスキによって1932年から1933年にかけてドイツのエニグマ暗号を解読するために使用された。^{[12] [13]}

数学のテキストでは、順列を表すのに小文字のギリシャ文字を使用するのが通例です。一般的には、またはが使用されます。^[14]${\displaystyle \alpha,\beta,\gamma}$${\displaystyle \sigma,\tau,\rho,\pi}$

順列は、集合Sからそれ自身への全単射(可逆なマッピング、1 対 1 の全射関数)として定義できます。

${\displaystyle \sigma :S\ {\stackrel {\sim }{\longrightarrow }}\ S.}$

恒等置換は、すべての元に対して によって定義され、数、^[a]、、または単一の 1 サイクル (x) によって表すことができます。^{[15] [16]} n個の元 を持つ集合のすべての置換の集合は対称群 を形成し、ここで群演算は関数 の合成です。したがって、群 内の2 つの置換とに対して、それらの積は次のように定義されます。${\displaystyle \sigma (x)=x}$${\displaystyle x\in S}$${\displaystyle 1}$${\displaystyle {\text{id}}={\text{id}}_{S}}$ ${\displaystyle S_{n}}$${\displaystyle \sigma}$${\displaystyle \tau}$${\displaystyle S_{n}}$${\displaystyle \pi =\sigma \tau }$

${\displaystyle \pi (i)=\sigma (\tau (i)).}$

合成は通常、ドットやその他の記号なしで記述されます。一般に、2つの順列の合成は可換ではありません。${\displaystyle \tau \sigma \neq \sigma \tau .}$

集合からそれ自身への一対一の関係である順列は、集合の並べ替えを実行する関数であり、能動順列または置換と呼ばれます。古い観点では、順列はSのすべての要素の順序付けられた配置またはリストであり、受動順列と呼ばれます。^[17]この定義によれば、§ 1行表記のすべての順列は受動的です。この意味は、能動変換と受動変換などにおける受動（つまりエイリアス）の使用方法とは微妙に異なります。 ^{[18] [19]}では、すべての順列は受動的な解釈が可能であるとみなされます（1行表記、2行表記などに関係なく）。

順列は、集合Sに作用する巡回群の軌道である1 つ以上の互いに素なサイクルに分解できます。サイクルは、順列を要素 に繰り返し適用することによって見つかります。ここで、 と仮定します。k 個の要素からなるサイクルはkサイクルと呼ばれます。(以下の § サイクル表記法を参照してください。) ${\displaystyle \sigma }$${\displaystyle \langle \sigma \rangle =\{1,\sigma ,\sigma ^{2},\ldots \}}$ ${\displaystyle x,\sigma (x),\sigma (\sigma (x)),\ldots ,\sigma ^{k-1}(x)}$${\displaystyle \sigma ^{k}(x)=x}$

順列の不動点とは、その要素xがそれ自身に取られ、つまり1 サイクルを形成することです。不動点のない順列は、混同と呼ばれます。2 つの要素 (単一の 2 サイクル) を交換し、他の要素を固定したままにする順列は、転置と呼ばれます。 ${\displaystyle \sigma }$${\displaystyle \sigma (x)=x}$${\displaystyle (\,x\,)}$

順列を便利に表現するために、いくつかの表記法が広く使用されています。サイクル表記法は簡潔で順列の構造を明確に示すため、よく使用されます。この記事では、特に指定がない限り、サイクル表記法を使用します。

コーシーの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]とすると、2行表記の最初の行にこれを使用します。 ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$

${\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]} 1行表記と以下に説明する循環表記を区別するように注意する必要がある。一般的な用法では、1行表記では括弧やその他の囲み記号を省略し、循環表記では括弧を使用する。1行表記は単語表現とも呼ばれる。^[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については、暗黙的に と仮定します。[ 25 ^]${\displaystyle \sigma (x)=x}$

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)(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サイクルは省略されない。

例えば、

(513)(6)(827)(94)

は、標準サイクル表記法におけるS = {1, 2, . . . , 9}の順列である。 ^[26]

リチャード・スタンレーはこれを順列の「標準表現」と呼び、^[27]マーティン・アイグナーは「標準形式」を使用している。^[24] セルゲイ・キタエフも「標準形式」という用語を使用しているが、両方の選択が逆になっている。つまり、各サイクルは最小要素を最初にリストし、サイクルは最小要素の降順でソートされている。^[28]

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

順列を掛け合わせるための別のルールは、関数の左側に引数を書くことから来ており、最も左の順列が最初に作用する。^{[30] [31] [32]} この表記では、順列は指数として書かれることが多いため、xに作用するσはx ^σと書かれ、その積はによって定義される。この記事では、右端の順列が最初に適用される最初の定義を使用する。 ${\displaystyle x^{\sigma \cdot \tau }=(x^{\sigma })^{\tau }}$

関数合成演算は、群の公理を満たします。これは結合的であり、 を意味し、3 つ以上の順列の積は通常括弧なしで記述されます。合成演算には恒等元 (恒等順列) もあり、各順列には を持つ逆順列(逆関数)があります。 ${\displaystyle (\rho \sigma )\tau =\rho (\sigma \tau )}$${\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配置）の数は、、、、、、 などの記号でさまざまに表され、^[35]次の式で計算されます。[ ³⁶ ]${\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}}$

${\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!}{(n-k)!}}.}$

積は、が非負の整数である という仮定なしに明確に定義され、組合せ論以外でも重要である。これはポッホハマー記号または- 番目の階乗降乗として知られている。${\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!}{(n-k)!\,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の要素の多重度（ある順序で）が、、 ... であり、それらの合計（つまり、Mのサイズ）がnである場合、 Mの多重集合順列の数は多項式係数で与えられる。^[37]${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle m_{l}}$

${\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内でのその多重度(要素の繰り返し数)以下の回数だけ出現します。

順列は、配置として考えた場合、線形に順序付けられた配置と呼ばれることがあります。ただし、オブジェクトが円形に配置されている場合は、この区別された順序は弱まります。配置には「最初の要素」はなく、どの要素も開始点と見なすことができます。異なるオブジェクトを円形に配置することを、円順列と呼びます。^{[39] [e]}これらは、線形配置の最後の要素をその前に移動することによって生成される同値関係に対して、これらのオブジェクトの通常の順列の同値類として正式に定義できます。

2 つの円順列は、一方を他方に回転できる場合、同等です。次の 4 つの文字の円順列は、同じであると見なされます。

     1 4 2 3
   4 3 2 1 3 4 1 2
     2 3 1 4

円形の配置は反時計回りに読む必要があるため、次の 2 つは回転しても一方が他方に近づくことができないため同等ではありません。

     1 1
   4 3 3 4
     2 2

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

n 個の異なるオブジェクトの順列の数はn ! です。

k個の互いに素な閉路を持つn順列の数は第一種符号なしスターリング数であり、またはと表記される。^[40]${\displaystyle c(n,k)}$${\displaystyle [{\begin{smallmatrix}n\\k\end{smallmatrix}}]}$

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

これはより簡潔な形で[1 ¹ 2 ² 3 ¹ ]と書くこともできる。より正確には、一般形は であり、それぞれの長さのサイクルの数である。与えられたサイクルタイプの順列の数は^{[41]である。}${\displaystyle [1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]}$${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$

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

n個の要素を持つ集合のサイクルタイプの数は、パーティション関数 の値に等しくなります。 ${\displaystyle p(n)}$

Polyaのサイクル インデックス多項式は、順列をサイクル タイプごとにカウントする生成関数です。

一般に、サイクル表記法で書かれた合成順列は、簡単に説明できるパターンには従いません。合成のサイクルは、合成されるサイクルと異なる場合があります。ただし、サイクル型は、順列を別の順列で共役する特殊なケース、つまり積 を形成する場合には保存されます。ここで、は によるの共役であり、そのサイクル表記法は、 のサイクル表記を取り、 をそのすべての要素に適用することで取得できます。^[42]したがって、2つの順列が同じサイクル型を持つ場合、それらは正確に共役です。 ${\displaystyle \sigma }$${\displaystyle \pi }$${\displaystyle \pi \sigma \pi ^{-1}}$${\displaystyle \pi \sigma \pi ^{-1}}$${\displaystyle \sigma }$${\displaystyle \pi }$${\displaystyle \sigma }$${\displaystyle \pi }$

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

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

この結果は、各順列に符号（ と書く）を割り当てるように拡張することができます。が偶数の場合、 が奇数の場合です。すると、2つの順列と${\displaystyle \operatorname {sgn} \sigma }$${\displaystyle \operatorname {sgn} \sigma =+1}$${\displaystyle \sigma }$${\displaystyle \operatorname {sgn} \sigma =-1}$${\displaystyle \sigma }$${\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 つは、 をの線形変換として定義し、その標準基底を で置換し、 をその行列として定義することです。つまり、のj^番目の列は n × 1 列ベクトルに等しくなります。つまり、その ( i , j ) 要素は、 i = σ ( j )の場合は 1 になり、それ以外の場合は 0 になります。線形マッピングの合成は行列の乗算によって記述されるため、この構成は順列の合成と互換性があります。${\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 }}$${\displaystyle \mathbf {e} _{\sigma (j)}}$

${\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 }.}$$

文献では、逆の規則も一般的です。この規則では、置換σは、 ( i , j ) 要素がj = σ ( i )の場合は 1 、それ以外の場合は 0 である行列に関連付けられます。この規則では、置換行列は置換とは逆の順序で乗算されます 。つまり、 です。この対応では、置換行列は標準の行ベクトルの右側に作用します。${\displaystyle P_{\sigma }=(M_{\sigma })^{-1}=(M_{\sigma })^{T}}$${\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 つの要素の順列に対するこれらの行列を示しています。

いくつかのアプリケーションでは、並べ替えられるセットの要素が互いに比較されます。これには、任意の 2 つの要素を比較できるように、セットS が全順序を持っていることが必要です。通常の ≤ 関係を持つセット {1, 2, ..., n } は、これらのアプリケーションで最も頻繁に使用されるセットです。

順列をシーケンスとして 1 行表記で記述すると、順列のいくつかのプロパティがSの全順序に直接関係します。 ${\displaystyle \sigma =\sigma (1)\sigma (2)\cdots \sigma (n)}$

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

同様に、下降はの場合の位置i  <  nなので、 の場合のすべてのiは上昇か下降のいずれかです。 ${\displaystyle \sigma (i)>\sigma (i{+}1)}$${\displaystyle 1\leq i<n}$

順列の昇順連は、どちらの端にも拡張できない、空でない増加する連続部分列です。これは、連続する上昇の最大シーケンスに対応します (後者は空である可能性があります。2 つの連続する下降の間には、長さ 1 の昇順連が存在します)。対照的に、順列の増加部分列は必ずしも連続しているわけではありません。これは、1 行表記の値の一部を省略することによって得られる増加シーケンスです。たとえば、順列 2453167 には、昇順連 245、3、および 167 がありますが、増加部分列 2367 があります。

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

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

順列σ ₁ σ ₂ ... σ _nの超過は、σ _j > jとなるインデックスjです。不等式が厳密でない場合（つまり、σ _j ≥ j）、j は弱い超過と呼ばれます。k回の超過を伴うn順列の数は、k回の降下を伴うn順列の数と一致する。^[46]

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

フォアタの基本的一対一変換は、与えられた標準サイクル形式を持つ順列を、括弧を取り除いた同じ要素の列を持つ一行表記の順列に変換する。^{[27] [47]}例えば：${\displaystyle \sigma }$${\displaystyle f(\sigma )={\hat {\sigma }}}$

${\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 \sigma }$${\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 \sigma }$

次の表は、S = {1, 2, 3}の 6 つの順列についてと を示しています。各辺の太字のテキストは、全単射で使用される表記を示しています。 については 1 行表記、 については 標準サイクル表記です。 ${\displaystyle {\hat {\sigma }}}$${\displaystyle \sigma }$${\displaystyle {\hat {\sigma }}}$${\displaystyle \sigma }$

最初の系として、ちょうどk 個のレコードを持つn順列の数は、ちょうどk個のサイクルを持つn順列の数に等しい。この最後の数は、第一種の符号なしスターリング数である。さらに、Foata のマッピングは、k 個の弱い超過を持つn順列を、 k − 1個の上昇を持つn順列に変換する。^[47] たとえば、(2)(31) = 321にはk = 2 個の弱い超過 (インデックス 1 と 2) があるが、f (321) = 231にはk − 1 = 1 個の上昇 (インデックス 1、つまり 2 から 3 へ) がある。${\displaystyle c(n,k)}$

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

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

反転の数は、順列の要素が順序どおりでない度合いを測る重要な尺度です。これは、 σとσ ^{−1について同じです。} k個の反転を持つ順列を順序どおりにする (つまり、恒等順列に変換する) には、隣接する転置 を(右乗算で) 連続して適用することにより、常に可能であり、k回のこのような操作のシーケンスが必要です。さらに、隣接する転置については、任意の合理的な選択が機能します。各ステップで、iとi + 1の転置を選択すれば十分です。ここで、 i は、これまでに修正された順列の降下です (そのため、転置により、この特定の降下が削除されますが、他の降下が作成される場合があります)。これは、このような転置を適用すると、反転の数が 1 減少するためです。この数が 0 でない限り、順列は恒等ではないため、少なくとも 1 つの降下があります。バブル ソートと挿入ソートは、シーケンスを順序付けるこの手順の特定のインスタンスとして解釈できます。ちなみに、この手順は、任意の順列σ が隣接する転置の積として記述できることを証明します。これは、 σ を恒等転置に変換する任意の転置シーケンスを単純に反転できるためです。実際、 σ を恒等転置に変換するすべての隣接する転置シーケンスを列挙すると、（反転後に）σ を隣接する転置の積として 記述する最小の長さのすべての式の完全なリストが得られます。

nのk回の反転を伴う順列の数はマホーニアン数で表される。^[50]これは積の展開における の係数である。${\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),}$$

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

かつ となるようなものとする。この場合、反転の重みはであるとする。小林（2011）は列挙公式を証明した。 ${\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)}$$${\displaystyle \sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}}$$

ここで、 は対称群におけるBruhat 順序を表します。この次数付き半順序は、 Coxeter 群のコンテキストでよく現れます。 ${\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 であるため省略できますが、これがあると、その後の順列への変換が記述しやすくなります)。最初のステップは、単にN を階乗数システムで表現することです。これは、特定の混合基数表現であり、 n !未満の数の場合、連続する桁の基数 (位の値または乗算係数) は( n − 1)!、( n − 2)!、...、2!、1! です。2 番目のステップでは、このシーケンスをLehmer コードとして、または (ほぼ同等に) 反転表として解釈します。

順列 σのLehmer コードでは、数値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 は}反転 ( i、j )の数を数えます。ここでk  =  σ _jは逆順に現れる 2 つの値のうち小さい方として現れます。^[51]

両方のエンコードは、n× n の ローテ図^[52]（ハインリッヒ・アウグスト・ローテにちなんで名付けられた）で視覚化することができ、そこでは（i、σi _）の点は順列のエントリを示し、（i、σj）の十字は反転（i、j）を示す。反転の定義により、その列の点（j、σj ）_の前であり、かつその行の点（i、σi _{）の前にある正方形には十字が表示される。レーマーコードは}連続する行の十字の数をリストし、反転表は連続する列の十字の数をリストする。これは逆順列のレーマーコードであり、その逆も同様である。

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

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

コンピューティングでは、与えられた値のシーケンスの順列を生成する必要がある場合があります。これを行うのに最適な方法は、ランダムに選択された順列が必要なのか、すべての順列が必要なのか、後者の場合は特定の順序付けが必要かどうかによって異なります。もう 1 つの問題は、与えられたシーケンス内のエントリ間の可能な等式を考慮する必要があるかどうかです。そうである場合、シーケンスの異なるマルチセット順列のみを生成する必要があります。

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

与えられたn値のシーケンスのランダムな順列を生成する場合、ランダムに選択されたnの順列をシーケンスに適用するか、シーケンスの異なる順列 (多重集合) のセットからランダムな要素を選択するかは関係ありません。これは、値が繰り返される場合、同じ順列シーケンスになるnの異なる順列が多数存在する可能性があるとしても、各可能な結果に対してそのような順列の数は同じであるためです。nの数の増加によりn が大きいと実行不可能になる体系的な生成とは異なり、ランダム生成では nが小さいと想定する必要はありません。

ランダムな順列を生成するための基本的な考え方は、0 ≤ d _i < i ( d ₁は常に 0 なので省略可能) を満たすn ! 個の整数シーケンスd ₁、d ₂、...、d _nの 1 つをランダムに生成し、それを全単射対応によって順列に変換することです。後者の対応については、(逆) シーケンスを Lehmer コードとして解釈することができ、これにより、1938 年にRonald FisherとFrank Yatesによって初めて公開された生成方法が得られます。^[53] 当時はコンピュータ実装は問題ではありませんでしたが、この方法では、Lehmer コードから順列に効率的に変換する上で上記で概説したような困難さがあります。これは、別の全単射対応を使用することで解決できます。つまり、d _{i を}使用してシーケンスの残りのi個の要素から要素を選択した後 ( iの値が減少するため)、要素を削除してさらに要素を 1 つ下げてシーケンスを圧縮するのではなく、その要素を残りの最後の要素と交換します。したがって、選択のために残っている要素は、元のシーケンスと同じ順序で発生しない場合でも、各時点で連続した範囲を形成します。整数のシーケンスから順列へのマッピングは多少複雑ですが、即時帰納法によって、各順列を正確に 1 つの方法で生成することが分かります。選択された要素が最後に残った要素である場合、スワップ操作は省略できます。これは、条件のテストを正当化するほど頻繁には発生しませんが、すべての順列を生成できることを保証するために、最後の要素は選択の候補に含まれていなければなりません。

ランダムな順列を生成するためのアルゴリズムは、擬似コードで次のように記述できます。 a[0], a[1], ..., a[n − 1]

 iが nから 2までの範囲で、 d i ← { 0, ..., i − 1 }
    のランダムな要素を実行し、a [ d i ] とa [ i − 1]
を入れ替える。 
     

これは次のように 配列の初期化と組み合わせることができます。a[i] = i

 i が0からn −1まで の場合、d i +1 ← { 0, ..., i }
    のランダムな要素a [ i ] ← a [ d i +1 ]
     a [ d i +1 ] ← i を実行します。
    

d _{i +1} = iの場合、最初の割り当てでは初期化されていない値がコピーされますが、2 番目の割り当てでは正しい値iで上書きされます。

しかし、フィッシャー・イェーツ法は本質的に順次アルゴリズムであり、「分割統治」手順で並列に同じ結果を達成できるため、順列を生成するための最速のアルゴリズムではありません。^[54]

与えられたシーケンスのすべての順列を体系的に生成する方法は多数ある。^[55] 古典的で単純かつ柔軟なアルゴリズムの 1 つは、辞書式順序で次の順列が存在する場合にそれを見つけることに基づいている。このアルゴリズムは重複した値を扱うことができ、その場合には各異なる多重集合順列を 1 回ずつ生成する。通常の順列の場合でも、辞書式順序で (おそらく階乗数システムを使用して) Lehmer コードの値を生成し、それを順列に変換するよりもはるかに効率的である。このアルゴリズムは、シーケンスを (弱く)昇順(辞書式に最小の順列を与える) でソートすることから始め、順列が見つかる限り次の順列に進むことを繰り返します。この方法は 14 世紀インドのNarayana Panditaにまで遡り、頻繁に再発見されている。^[56]

次のアルゴリズムは、指定された順列の後に辞書式で次の順列を生成します。指定された順列をその場で変更します。

1. a [ k ] < a [ k + 1]となる最大のインデックスkを見つけます。そのようなインデックスが存在しない場合は、順列は最後の順列になります。
2. a [ k ] < a [ l ]となる、kより大きい最大のインデックスl を見つけます。
3. a [ k ]の値とa [ l ] の値を交換します。
4. a [ k + 1] から最後の要素a [ n ] までのシーケンスを逆にします。

たとえば、シーケンス [1, 2, 3, 4] (昇順) が与えられ、インデックスが0 ベースである場合、手順は次のようになります。

1. インデックスk = 2 です。これは、3 が[ k + 1] である4より小さい最大のインデックスであるという条件を満たすインデックスに配置されているためです。
2. インデックスl = 3 です。これは、条件a [ k ] < a [ l ]を満たすために、シーケンス内で 3 より大きい値は 4 のみであるためです。
3. a [2]とa [3]の値が入れ替わり、新しいシーケンス[1, 2, 4, 3]が形成されます。
4. kインデックスa [2] から最後の要素までのシーケンスは逆になります。このインデックスの後には 1 つの値 (3) しかないため、このインスタンスではシーケンスは変更されません。したがって、初期状態の辞書式後続は並べ替えられます: [1, 2, 4, 3]。

このアルゴリズムに従うと、次の辞書順の順列は [1, 3, 2, 4] となり、24 番目の順列は [4, 3, 2, 1] になります。この時点ではa [ k ] < a [ k + 1] は存在せず、これが最後の順列であることを示します。

この方法では、最初のソートを除いて、シーケンス全体にわたって償却される順列ごとに約3回の比較と1.5回のスワップが使用されます。^[57]

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

スタインハウス・ジョンソン・トロッターの代替としてヒープアルゴリズム^[58]があり、これは1977年にロバート・セジウィックによってアプリケーションにおける順列生成の最速アルゴリズムと評された。^[55]

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

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

スワップ（転置、2サイクル）の明示的なシーケンスがここで説明されており、各スワップは（左側で）前のチェーンに適用され、新しい順列を提供します。これにより、すべての順列をそれぞれ1回だけ取得できます。^[64]このカウント/生成手順には、ステップごとに示される追加の構造（ネストされていると呼びます）があります。 を完全に取得した後、以下で説明するコセットの代表を適切に選択することにより、のコセットによる取得を続けます。それぞれが順番に生成されるため、最後の要素があることに注意してください。したがって、スワップによって生成した後、 の次の順列は、何らかの についてで ある必要があります。次に、生成されたすべてのスワップ が繰り返され、コセット 全体を生成し、そのコセット の最後の順列に到達します。次のスワップでは、順列を別のコセット の代表に移動する必要があります。 ${\displaystyle (pq)}$${\displaystyle S_{k-1}}$${\displaystyle S_{k}\backslash S_{k-1}}$${\displaystyle S_{k-1}\tau _{i}}$${\displaystyle S_{k-1}}$${\displaystyle S_{k}}$${\displaystyle \tau _{i}}$${\displaystyle S_{m}}$ ${\displaystyle \lambda _{m}\in S_{m}}$${\displaystyle S_{k-1}}$${\displaystyle S_{k}\backslash S_{k-1}}$${\displaystyle \tau _{1}=(p_{1}k)\lambda _{k-1}}$${\displaystyle 1\leq p_{1}<k}$${\displaystyle S_{k-1}}$${\displaystyle S_{k-1}\tau _{1}}$${\displaystyle \lambda _{k-1}\tau _{1}}$${\displaystyle \tau _{2}=(p_{2}k)\lambda _{k-1}\tau _{1}}$

同じように続けると、の剰余類に対する 剰余類代表が得られます。順序付けられた集合( ) は剰余類の始まりの集合と呼ばれます。これらの代表のうち 2 つが同じ剰余類に属するのは 、 の 場合、つまり の場合に限ります。結論として、順列はすべて異なる剰余類の代表であるためには、任意の に対して の場合に限ります (繰り返し条件なし)。特に、生成された順列がすべて異なるために、値が異なる必要はありません。その過程で が得られ、これが再帰手順を提供します。 ${\displaystyle \tau _{j}=(p_{j}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{i}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{1}k)\lambda _{k-1}}$${\displaystyle S_{k-1}}$${\displaystyle S_{k}}$${\displaystyle (p_{1},\ldots ,p_{k-1})}$${\displaystyle 0\leq p_{i}<k}$${\displaystyle \tau _{j}(\tau _{i})^{-1}=(p_{j}k)\lambda _{k-1}(p_{j-1}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{i+1}k)=\varkappa _{ij}\in S_{k-1}}$${\displaystyle \varkappa _{ij}(k)=k}$${\displaystyle \tau _{i}\in S_{k}-S_{k-1}}$${\displaystyle k>j>i\geq 1}$${\displaystyle (\lambda _{k-1})^{j-i}p_{i}\neq p_{j}}$${\displaystyle p_{i}}$${\displaystyle \lambda _{k}=\lambda _{k-1}(p_{k-1}k)\lambda _{k-1}(p_{k-2}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{1}k)\lambda _{k-1}}$

例: 明らかに、の場合、 が成り立ちます。 を構築するには、重複なしの条件を満たす剰余類の始まりの 2 つの可能性しかありません。選択により が導かれます。の生成を続けるには、適切な剰余類の始まり (重複なしの条件を満たす) が必要です。便利な選択 があり、 が導かれます 。次に、剰余類の始まり (重複なしの条件を満たす) の便利な選択を構築するには が成り立ち、 が導かれます。 ${\displaystyle \lambda _{2}}$${\displaystyle \lambda _{2}=(12)}$${\displaystyle \lambda _{3}}$${\displaystyle p_{1}=p_{2}=1}$${\displaystyle \lambda _{3}=\lambda _{2}(13)\lambda _{2}(13)\lambda _{2}=(13)}$${\displaystyle S_{4}}$${\displaystyle p_{1}=1,p_{2}=2,p_{3}=3}$${\displaystyle \lambda _{4}=(13)(1234)(13)=(1432)}$${\displaystyle \lambda _{5}}$${\displaystyle p_{1}=p_{2}=p_{3}=p_{4}=1}$${\displaystyle \lambda _{5}=(15)}$

上記の例から、における の剰余類の始まりを次のように選択して、同様の方法で に帰納的に進むことができます。偶数の場合、すべての剰余類の始まりが 1 に等しくなるように選択し、奇数の場合、剰余類の始まりが に等しくなるように選択します。このような選択により、「最後の」順列は奇数の場合で、 偶数の場合( ) になります。これらの明示的な式を使用すると、最小限の計算で、カウント/生成ステップで特定のインデックスの順列を簡単に計算できます。これには、インデックスを階乗基数で記述すると便利です。たとえば、インデックスの順列は で、最終的に になります。 ${\displaystyle k}$${\displaystyle S_{k}}$${\displaystyle S_{k+1}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle (1,2,\dots ,k)}$${\displaystyle \lambda _{k}=(1k)}$${\displaystyle k}$${\displaystyle \lambda _{k}=(1k_{-})(12\cdots k)(1k_{-})}$${\displaystyle k}$${\displaystyle k_{-}=k-1}$${\displaystyle 699=5(5!)+4(4!)+1(2!)+1(1!)}$${\displaystyle \sigma =\lambda _{2}(13)\lambda _{2}(15)\lambda _{4}(15)\lambda _{4}(15)\lambda _{4}(15)\lambda _{4}(56)\lambda _{5}(46)\lambda _{5}(36)\lambda _{5}(26)\lambda _{5}(16)\lambda _{5}=}$ ${\displaystyle \lambda _{2}(13)\lambda _{2}((15)\lambda _{4})^{4}(\lambda _{5})^{-1}\lambda _{6}=(23)(14325)^{-1}(15)(15)(123456)(15)=}$${\displaystyle (23)(15234)(123456)(15)}$${\displaystyle \sigma =(1653)(24)}$

スワップ順列による乗算は計算時間が短く、新しく生成された順列ごとにこのようなスワップ乗算が 1 回だけ必要なので、この生成手順は非常に効率的です。さらに、簡単な式があるため、それぞれの最後の順列があると、 スワップごとに行うのではなく、サブグループのブロックで実行できるため、予想よりも少ない手順で特定のインデックスを持つ順列に直接移動して、さらに時間を節約できます。 ${\displaystyle S_{k}}$

順列は、ターボコードなどのエラー検出および訂正アルゴリズムのインターリーバーコンポーネント で使用され、たとえば3GPP Long Term Evolution モバイル通信規格ではこれらのアイデアが使用されています（3GPP技術仕様36.212 ^[65]を参照）。このようなアプリケーションでは、特定の望ましい特性を満たす順列を高速に生成するという問題が生じます。方法の1つは、順列多項式に基づいています。また、ユニーク順列ハッシュにおける最適なハッシュの基礎としても使用されます。^[66]

• ボガート、ケネス P. (1990)、Introductory Combinatorics (第 2 版)、ハーコート ブレイス ジョバノビッチ、ISBN 978-0-15-541576-8
• Bóna、Miklós (2004)、順列の組み合わせ、Chapman Hall-CRC、ISBN 978-1-58488-434-7
• ボナ、ミクロス（2012）、順列の組み合わせ論（第2版）、CRC Press、ISBN 978-1-4398-5051-0
• Brualdi, Richard A. (2010)、Introductory Combinatorics (第 5 版)、Prentice-Hall、ISBN 978-0-13-602040-0
• キャメロン、ピーター J. (1994)、組合せ論: トピック、テクニック、アルゴリズム、ケンブリッジ大学出版局、ISBN 978-0-521-45761-3
• カーマイケル、ロバート・D. (1956) [1937]、有限順序群論入門、ドーバー、ISBN 978-0-486-60300-1
• フレイリー、ジョン B. (1976)、抽象代数入門(第 2 版)、Reading: Addison-Wesley、ISBN 0-201-01984-1
• ガースタイン、ラリー J. (1987)、離散数学と代数構造、WH フリーマン アンド カンパニー、ISBN 978-0-7167-1804-8
• ホール、マーシャル・ジュニア（1959）『群論』マクミラン
• ハンフリーズ、JF（1996）、群論講座、オックスフォード大学出版局、ISBN 978-0-19-853459-4
• クヌース、ドナルド (1973)、「ソートと検索」、『コンピュータプログラミングの芸術』第 3 巻 この本では、演習 5.1.1–7 (p. 19) で、反転表のバリエーションC ₁、...、C _nとして、Lehmer コード (その名前は使用していません)が他の 2 つのバリエーションとともに説明されています。
• クヌース、ドナルド(2005)、「すべてのタプルと順列の生成」、『The Art of Computer Programming』第 4 巻、Addison–Wesley、ISBN 978-0-201-85393-3第2巻、初版。
• マッコイ、ニール H. (1968)、現代代数学入門、改訂版、ボストン：アリン＆ベーコン、LCCN  68015225
• ネリング、エヴァー・D.（1970）、線形代数と行列理論（第2版）、ニューヨーク：ワイリー、LCCN  76091646
• ロットマン、ジョセフ・J.（2002）、Advanced Modern Algebra、Prentice-Hall、ISBN 978-0-13-087868-7
• ステッドマン、ファビアン（1677）、カンパナロジア、ロンドン 出版者は「WS」と記されており、ウィリアム・スミスである可能性があり、この「献辞」が宛てられた 大学青年協会の代理人として活動していた可能性がある。引用符では、元の長い「S」が現代の短い「s」に置き換えられている。
• ウスペンスキー、ジェームズ（1937）、数学的確率入門、マグロウヒル
• ウェブスター第7版大学用新辞典、スプリングフィールド：G. & C. メリアム社、1969年

• ビッグス、ノーマン L. (2002)、離散数学(第 2 版)、オックスフォード大学出版局、ISBN 978-0-19-850717-8
• フォアタ、ドミニク。 Schutzenberger、Marcel-Paul (1970)、Théorie Géométrique des Polynômes Eulériens、Lecture Notes in Mathematics、vol. 138、ベルリン、ハイデルベルク: Springer-Verlag、ISBN 978-3-540-04927-2リンクは、Springer-Verlag 社によって最初に出版されたテキストの、無料で入手可能な再入力 (LaTeX 化) および改訂版へのリンクです。
• クヌース、ドナルド（1998）、ソートと検索、コンピュータプログラミングの芸術、第3巻（第2版）、アディソン・ウェズレー、ISBN 978-0-201-89685-5セクション5.1: 順列の組み合わせ特性、pp. 11–72。
• セジウィック、ロバート(1977)。「順列生成法」。ACM コンピューティング調査。9 (2): 137–164。doi : 10.1145 /356689.356692。S2CID 12139332。
• 小林正人 (2011). 「Bruhat 順序の順列の下のビグラスマン順列の列挙」.秩序. 1 : 131–137.

• 「順列」、数学百科事典、EMS Press、2001 [1994]