レーマー符号

数学とくに組合せ数学において、レーマー符号（レーマーふごう、）は、n 個の数のすべての置換を符号化する方法の一つである。レーマー符号という名前はに由来するが、この符号は少なくとも1888年には知られていた。

 符号 
レーマー符号は、n 個の数の置換が

個存在するという事実を利用している。置換 σ は 1, …, n の像の列 (σ1, …, σn) によって表すなら、n 個の数の並びによって符号化されることになる。しかし、こうした並びには置換を表さないもの（同じ数を二度使ったもの）も含まれている。ここで考察する符号は、先頭の数を n 個の数から選び、次の数は  個の数から選び、そうしていって、最後の数はたった1個の数から選んでできるものである。

レーマー符号は、次の列である。

記号 L(σ)i は、σi+1, …, σn のうち σi より小さいものの個数である。

 かつ  である添字の組   を σ の逆転と呼び、L(σ)iは、逆転(i,j)がいくつあるかを表す（iは固定しiを変化させる）。このことから は σ に逆転がいくつ現れるかを表していることが分かる。これは、恒等順列に変換するために必要な隣接互換の数と等しい。位置 iの値が0であればそこから右での最小であり（すなわちはその右にあるどのよりも小さい）、位置 iでの値はそこから右での最大である。

 符号化と復号 

符号化はそれぞれの位置ごとに逆転を数えることで行える。

また、次のような方法でインプレースに行うこともできる（ただし、現実的には単純に数える以上に効率的であるわけではない）。

この方法では、まず各要素を昇順にソートしたときのから始まるインデックスへと置き換える。そして左から右へ順に、各エントリについて、それより右でかつより大きいエントリからを引くことを繰り返す。
たとえば、B, F, A, G, D, E, Cは1, 5, 0, 6, 3, 4, 2という数列に置き換えられ、次のように処理される。

こうして、全エントリを処理し終わって得られた最後の行がレーマー符号である。
デコードはこの逆を行えばよい。右から左へ各エントリについて、それより右にある以上のエントリにを足すことを繰り返す。

 関連項目 
階乗進法

 出典 

 関連文献 

Category:組合せ論
Category:順列
Category:数学に関する記事