レーマーコード

数学、特に組み合わせ論において、レーマー符号はn個の数の列のあらゆる順列を符号化する特定の方法である。これは順列に番号を付ける方式の一例であり、逆転表の一例でもある。

レーマーコードはDHレーマーにちなんで名付けられましたが^{[ 1 ]}、このコードは少なくとも1888年から知られていました^{[ 2 ] 。}

レーマーコードは、

${\displaystyle n!=n\times (n-1)\times \cdots \times 2\times 1}$

n個の数値のシーケンスの順列。順列σが 1, ..., nの像のシーケンス ( σ ₁ , ..., σ _n ) で指定される場合、それはn 個の数値のシーケンスによってエンコードされますが、すべての数値が一度だけ使用される必要があるため、そのようなシーケンスはすべて有効ではありません。対照的に、ここで検討するエンコードでは、最初の数値をn個の値の集合から選択し、次の数値をn − 1個の固定値の集合から選択し、これを繰り返して、単一の固定値のみが許容される最後の数値まで可能性の数を減らします。これらの集合から選択された数値のシーケンスはすべて、単一の順列をエンコードします。いくつかのエンコードを定義できますが、レーマーコードにはいくつかの追加の有用な特性があります。それはシーケンスです

${\displaystyle L(\sigma )=(L(\sigma )_{1},\ldots ,L(\sigma )_{n})\quad {\text{ただし}}\quad L(\sigma )_{i}=\#\{j>i:\sigma _{j}<\sigma _{i}\},}$

言い換えれば、項L ( σ ) _{i は、} σ iの右側にある( σ ₁ , ..., σ _n ) の項のうち、 σ _iより小さい項の数を数え、0 からn − iの間の数値となり、 n + 1 − i個の異なる値を許容します。

i < jかつσ _i > σ _jを満たすインデックスのペア ( i , j )はσの反転と呼ばれ、L ( σ ) _{i は}iを固定しjを変化させたときの反転 ( i , j )の数を数えます。したがって、L ( σ ) ₁ + L ( σ ) ₂ + … + L ( σ ) _nはσの反転の総数であり、これは置換を恒等置換に変換するために必要な隣接転置の数でもあります。レーマーコードのその他の特性としては、 2 つの順列の符号化の辞書順がそれらのシーケンス ( σ ₁、 ...、σ _n ) と同じであること、コード内の任意の値 0 が順列内の右から左への最小値 (つまり、右にある任意のσ _jよりも小さいσ _i ) を表し、 位置iの値n − iも同様に右から左への最大値を表すこと、そしてσのレーマーコードが、辞書順 (0 から始まる位置の番号付け) でのnの順列のリストにおけるその位置の階乗数システム表現と一致することなどが挙げられます。

この符号化のバリエーションは、固定されたiではなく固定されたjに対して反転 ( i , j ) を数えること、より小さいインデックスiではなく固定されたより小さい値σ _jで反転を数えること、または反転ではなく非反転を数えることによって得られます。これによって根本的に異なるタイプの符号化が生成されるわけではありませんが、符号化のいくつかの特性がそれに応じて変化します。特に、固定されたより小さい値σ _jで反転を数えると、 σの反転表が得られ、これは逆順列のレーマー符号であることがわかります。

n個のオブジェクトの異なる順列がn !通りあることを証明する通常の方法は、最初のオブジェクトはn通りの異なる方法で選択でき、次のオブジェクトはn − 1通りの異なる方法で選択でき（最初のオブジェクトと同じ数を選択することは禁止されているため）、次のオブジェクトはn − 2通りの異なる方法で選択でき（禁止されている値が 2 つあるため）、といったように選択できることを観察することです。各ステップでのこの選択の自由度を数値に変換すると、与えられた順列のレーマーコードを見つけるエンコードアルゴリズムが得られます。順列されたオブジェクトが数値であると仮定する必要はありませんが、オブジェクトの集合の全順序付けが必要です。コード番号は 0 から始まるため、各オブジェクトσ _iをエンコードするのに適切な数値は、その時点で利用可能であったオブジェクト (つまり、位置iより前に出現しないもの) の数であり、実際に選択されたオブジェクトσ _iより小さいものです。 （必然的に、このようなオブジェクトはj > iの位置で出現し、( i , j ) は反転となる。これは、この数が確かにL ( σ ) _iであることを示している。）

各オブジェクトを符号化するこの番号は、いくつかの方法で直接数えることによって見つけることができます（反転を直接数える、または、セット内で0から始まるシーケンス番号である特定のオブジェクトよりも小さいオブジェクトの総数を、その位置で利用できないオブジェクトで補正する）。インプレースではあるものの、実際にはそれほど効率的ではない別の方法は、各オブジェクトをそのシーケンス番号で表して得られる{0, 1, ... n − 1 }の順列から始め、各エントリxについて、左から右の順に、 xより大きい（まだ）すべてのエントリから1を減算することによって、その右側の項目を補正します（ xに対応するオブジェクトがもはや利用できないという事実を反映するため）。具体的には、アルファベット順に並べられた文字B、F、A、G、D、E、Cの順列に対するレーマーコードは、まずシーケンス番号1、5、0、6、3、4、2のリストを与え、これを順次変換します。

${\displaystyle {\begin{matrix}\mathbf {1} &5&0&6&3&4&2\\1&\mathbf {4} &0&5&2&3&1\\1&4&\mathbf {0} &4&2&3&1\\1&4&0&\mathbf {3} &1&2&0\\1&4&0&3&\mathbf {1} &2&0\\1&4&0&3&1&\mathbf {1} &0\\1&4&0&3&1&1&\mathbf {0} \\\end{matrix}}}$

ここで、最後の行はレーマーコードです（各行で、太字要素の右側にある大きなエントリから1を引いて次の行を形成します）。

レーマー符号を与えられた集合の順列に復号するには、後者の手順を逆にすることができます。各エントリxについて、右から左の順に、 xより大きい (現在) 項目すべてに 1 を加えることで、その右側の項目を修正します。最後に、結果として得られる {0, 1, ... n − 1 } の順列を数列として解釈します ({1, 2, ... n } の順列を求める場合は、各エントリに 1 を加えることになります)。あるいは、レーマー符号のエントリを左から右に処理し、上記のように次の要素の選択を決定する数値として解釈することもできます。これには、使用可能な要素のリストを維持し、選択された各要素をリストから削除する必要があります。この例では、{A,B,C,D,E,F,G} から要素 1 (B) を選択し、次に {A,C,D,E,F,G} から要素 4 (F) を選択し、次に {A,C,D,E,G} から要素 0 (A) を選択し、以下同様にして、シーケンス B,F,A,G,D,E,C を再構築します。

関連する構造もいくつか使用されています。そのうちの1つは、Wolfram Alphaなどで反転ベクトルと呼ばれることがよくあります。反転（離散数学）§ 反転関連ベクトルも参照してください。

• Mantaci, Roberto; Rakotondrajao, Fanja (2001)、「「オイラー的」の意味を知っている順列表現」、離散数学と理論計算機科学(4): 101–108、2004年11月16日にオリジナルからアーカイブ済み
• クヌース、ドナルド（1981）『コンピュータプログラミングの技法』第3巻、リーディング：アディソン・ウェスリー、 12～ 13 ページ