レーマー符号
レーマー符号は、n 個の数の置換が
n ! = n × ( n − 1 ) × ⋯ × 2 × 1 {\displaystyle n!=n\times (n-1)\times \cdots \times 2\times 1}
個存在するという事実を利用している。置換 σ は 1, ..., n の像の列 (σ1, ..., σn) によって表すなら、n 個の数の並びによって符号化されることになる。しかし、こうした並びには置換を表さないもの(同じ数を二度使ったもの)も含まれている。ここで考察する符号は、先頭の数を n 個の数から選び、次の数は n − 1 個の数から選び、そうしていって、最後の数はたった1個の数から選んでできるものである。
レーマー符号は、次の列である。
L ( σ ) = ( L ( σ ) 1 , ...
Mantaci, Roberto (2001), “A permutation representation that knows what "Eulerian" means”, Discrete Mathematics and Theoretical Computer Science (4): 101–108, http://www.dmtcs.org/volumes/abstracts/pspapers/dm040203.ps
Knuth, Donald (1981), The art of computer programming, 3, Reading: Addison-Wesley, pp. 12–13
表示
編集