レーマー符号

数学とくに組合せ数学において、レーマー符号（レーマーふごう、）は、"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という数列に置き換えられ、次のように処理される。
formula_3
こうして、全エントリを処理し終わって得られた最後の行がレーマー符号である。
デコードはこの逆を行えばよい。右から左へ各エントリについて、それより右にある以上のエントリにを足すことを繰り返す。