階乗番号システム

組み合わせ論において、階乗番号システム（かいじょうばんごうシステム、factorial number systemまたfactoradic）とは、置換に番号を振るための混在基数システムである。n!未満の数を階乗番号システムに変換すると、n個の数の列が得られる。この列は、置換とみなすことができる。この変換にはLeher codeを用いても、逆引きテーブル表現として行ってもよい。

一般的な混合基数システムはゲオルク・カントール.によって研究された。「階乗番号システム」という用語はドナルド・クヌース.によって使用された。

 定義 
階乗番号システムは、混合基数システムの一つである。i桁目には、0からi-1までの数を置くことができる。i桁目にjを置くことによって、jに(i-1)!を掛けた数を表現する。すなわち、i桁目の重みは(i-1)!である。
 桁 置ける数 重み表現される数 1桁目  0  0!   0 (= 0 * 0!) 2桁目  0か1  1!   0 (= 0 * 1!)か1 (= 1 * 1!) 3桁目  0,1,2のいずれか  2! 0 (= 0 * 2!), 2 (= 1 * 2!), 4 (= 3 * 2!)のいずれか 4桁目  0,1,2,3のいずれか  3! 0 (= 0 * 3!), 6 (= 1 * 3!), 12 (= 2 * 3!), 18 (= 3 * 3!)のいずれか

1桁目は常に0であり、0しか表現できない。

この記事では、階乗番号システムによる表記は下付きの "!"によって表記する。例えば341010!は 

 =3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! 
 =((((3×5 + 4)×4 + 1)×3 + 0)×2 + 1)×1 + 0
 = 463

を表現する。

逆に463を階乗番号システムに変換するには、除算を繰り返す。

 463 ÷ 1 = 463, 余り 0
 463 ÷ 2 = 231, 余り 1
 231 ÷ 3 = 77, 余り 0
 77 ÷ 4 = 19, 余り 1
 19 ÷ 5 = 3, 余り 4
 3 ÷ 6 = 0, 余り 3

 例 
 置換 
 分数 

 出典 

.

 外部リンク 
 A Lehmer code calculator 
置換を構成する数字は1から始まっていることに注意。
 Factorial number system

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