反転（離散数学）

コンピュータサイエンスと離散数学において、シーケンス内の反転とは、自然な順序から外れた要素のペアのことです。

を順列とする。とのとき、と の間にはの反転が存在する。 反転は、場所^{[1] [2]}または要素^{[3] [4] [5]}のいずれかを含む順序付きペアで示される。${\displaystyle \pi}$${\displaystyle \pi}$${\displaystyle i}$${\displaystyle j}$${\displaystyle i<j}$${\displaystyle \pi (i)>\pi (j)}$${\displaystyle (i,j)}$${\displaystyle {\bigl (}\pi (i),\pi (j){\bigr )}}$

反転集合はすべての反転の集合である。位置ベース表記法を使用した順列の反転集合は、各順序付きペアの2つの要素を交換した要素ベース表記法を使用した逆順列の反転集合と同じである。同様に、要素ベース表記法を使用した順列の反転集合は、各順序付きペアの2つの要素を交換した位置ベース表記法を使用した逆順列の反転集合と同じである。^[6]

反転は通常順列に対して定義されますが、シーケンスに対しても定義されることがあります。をシーケンス（または多重集合順列^[7]）と
します。 かつの場合、場所のペア^{[7] [8]}または要素のペア^[9]のいずれかが の反転と呼ばれます。 ${\displaystyle S}$${\displaystyle i<j}$${\displaystyle S(i)>S(j)}$${\displaystyle (i,j)}$${\displaystyle {\bigl (}S(i),S(j){\bigr )}}$${\displaystyle S}$

シーケンスの場合、異なる場所のペアが同じ値のペアを持つ可能性があるため、要素ベースの定義による反転は一意ではありません。

シーケンスの反転数 ^[10]は、反転セットの濃度です。これは、順列^{[5]またはシーケンス[9]}のソート度（事前ソート度と呼ばれることもあります）の一般的な尺度です。反転数は0から0までです。順列とその逆は、同じ反転数を持ちます。 ${\displaystyle {\mathtt {inv}}(X)}$${\displaystyle X=\langle x_{1},\dots ,x_{n}\rangle }$${\displaystyle {\frac {n(n-1)}{2}}}$

たとえば、シーケンスは順序付けられているためです。また、が偶数の場合（各ペアが反転であるため）。この最後の例は、直感的に「ほぼソートされている」セットでも、反転の数が 2 乗になる可能性があることを示しています。 ${\displaystyle {\mathtt {inv}}(\langle 1,2,\dots ,n\rangle )=0}$${\displaystyle n=2m}$${\displaystyle {\mathtt {inv}}(\langle m+1,m+2,\dots ,2m,1,2,\dots ,m\rangle )=m^{2}}$${\displaystyle (1\leq i\leq m<j\leq 2m)}$

反転数とは、順列の矢印図における交差の数、^[6]順列の恒等順列からのケンドールタウ距離、および以下に定義される各反転関連ベクトルの合計です。

ソート度の他の尺度には、完全にソートされたシーケンスを生成するためにシーケンスから削除できる要素の最小数、シーケンス内のソートされた「ラン」の数と長さ、スピアマンのフットルール（各要素のソート位置からの距離の合計）、およびシーケンスをソートするために必要な最小の交換数などがあります。^[11]標準的な比較ソートアルゴリズムは、時間O( n log n )で反転数を計算するように適応できます。^[12]

順列の反転を一意に決定するベクトルに凝縮する 3 つの類似したベクトルが使用されています。これらは反転ベクトルまたはLehmer コードと呼ばれることがよくあります。(ソースの一覧はここにあります。)

この記事では、 Wolframのように反転ベクトル（）という用語を使用します。^[13]残りの2つのベクトルは、左反転ベクトルと右反転ベクトルと呼ばれることもありますが、反転ベクトルとの混同を避けるために、この記事では 左反転カウント（）、右反転カウント（）と呼びます。階乗として解釈すると、左反転カウントは逆コレクシコグラフィック順列を与え、^[14]右反転カウントは辞書式インデックスを与えます。 ${\displaystyle v}$${\displaystyle l}$${\displaystyle r}$

反転ベクトル：${\displaystyle v}$要素ベースの定義
では、小さい方（右）の成分が である反転の数です。^[3]${\displaystyle v(i)}$${\displaystyle i}$

${\displaystyle v(i)}$内の要素の数は以前より大きくなります。${\displaystyle \pi}$${\displaystyle i}$${\displaystyle i}$

${\displaystyle v(i)~~=~~\#\{k\mid k>i~\land ~\pi ^{-1}(k)<\pi ^{-1}(i)\}}$

左反転数:${\displaystyle l}$場所ベースの定義
では、 は、大きい方(右) の要素が である反転の数です。 ${\displaystyle l(i)}$${\displaystyle i}$

${\displaystyle l(i)}$内の要素の数は以前より大きくなります。${\displaystyle \pi}$${\displaystyle \pi (i)}$${\displaystyle \pi (i)}$

${\displaystyle l(i)~~=~~\#\left\{k\mid k<i~\land ~\pi (k)>\pi (i)\right\}}$

右反転カウント、Lehmer コードとも呼ばれます。${\displaystyle r}$場所ベースの定義
では、 は小さい方(左) の要素が である反転の数です。 ${\displaystyle r(i)}$${\displaystyle i}$

${\displaystyle r(i)}$内の要素の数はより後の方が少ないです。${\displaystyle \pi}$${\displaystyle \pi (i)}$${\displaystyle \pi (i)}$

${\displaystyle r(i)~~=~~\#\{k\mid k>i~\land ~\pi (k)<\pi (i)\}}$

と は両方とも、ローテ図を使って見つけることができます。ローテ図は、1 が点で表され、右と下に点があるすべての位置に反転 (多くの場合、十字で表されます) がある順列行列です。 はローテ図の行 の反転の合計であり、 は列 の反転の合計です。逆の順列行列は転置であるため、順列 はその逆の順列 であり、その逆も同様です。 ${\displaystyle v}$${\displaystyle r}$${\displaystyle r(i)}$${\displaystyle i}$${\displaystyle v(i)}$${\displaystyle i}$${\displaystyle v}$${\displaystyle r}$

次のソート可能な表は、4 つの要素 ( 列) の 24 通りの順列を、その場所に基づく反転セット ( pb 列)、反転関連ベクトル ( 、、列)、および反転番号 ( # 列) とともに示しています。(小さい活字で見出しのない列は、隣の列を反映しており、コレクシコグラフィック順序でソートするために使用できます。) ${\displaystyle \pi }$${\displaystyle v}$${\displaystyle l}$${\displaystyle r}$

と は常に同じ数字を持ち、 とは両方とも位置ベースの反転セットに関連していることがわかります。 の非自明な要素は、示されている三角形の下降対角線の和であり、 の非自明な要素は昇順対角線の和です。 (下降対角線のペアは右の要素 2、3、4 を共有し、昇順対角線のペアは左の要素 1、2、3 を共有します。) ${\displaystyle v}$${\displaystyle l}$${\displaystyle l}$${\displaystyle r}$${\displaystyle l}$${\displaystyle r}$

テーブルのデフォルトの順序は、逆 colex order by です。これは、 colex order by と同じです。 Lex order by は、lex order by と同じです。 ${\displaystyle \pi }$${\displaystyle l}$${\displaystyle \pi }$${\displaystyle r}$

n個の項目の順列の集合には、順列の弱い順序と呼ばれる部分順序の構造を与えることができ、格子を形成します。

部分集合関係によって順序付けられた反転集合のハッセ図は、パーミュトヘドロンの骨格を形成します。

場所ベースの定義を使用して各反転セットに順列が割り当てられると、順列の順序は順列多面体の順序になります。この順序では、エッジは連続する値を持つ 2 つの要素の交換に対応します。これが順列の弱い順序です。恒等順列はその最小値であり、恒等順列を反転して形成される順列はその最大値です。

要素ベースの定義を使用して各反転セットに順列が割り当てられた場合、順列の結果の順序はケイリー グラフの順序になります。ここで、エッジは連続する場所にある 2 つの要素の交換に対応します。対称群のこのケイリー グラフは、その順列化面体に似ていますが、各順列がその逆順列に置き換えられています。

Wikiversity には、逆行列 (離散数学)に関する学習リソースがあります。

• 階乗数法
• 順列グラフ
• 転置、単純な転置、転置、並べ替え
• ダメラウ・レーベンシュタイン距離
• 順列の偶奇性

OEISのシーケンス:

• 階乗基数表現に関連するシーケンス
• 階乗数: A007623 および A108731
• 反転番号: A034968
• 2進数として解釈される有限順列の反転集合: A211362 (関連順列: A211363)
• 反転ベクトルに 0 と 1 のみが含まれる有限順列: A059590 (反転セット: A211364)
• n個の要素とk 個の反転の順列の数。マホーニアン数: A008302 (その行の最大値。ケンドール・マン数: A000140)
• n 個のエッジとn 個のノードを持つ接続されたラベル付きグラフの数: A057500