階乗進法

From Wikipedia, the free encyclopedia

組合せ数学において、階乗進法とは順列を数え上げるのに適する、複数の底が混在した位取り記数法である。

階乗進法は複数の底が混在した位取り記数法であり、下からi桁目の仮数が0からi-1、底がiとなる。

87654321
桁の重み 7!6!5!4!3!2!1!0!
桁の重み(十進法) 5040720120246211
桁の仮数 76543210

ただし、最下位は常に0となるため、省略されることもある。また、下から11桁目以降の桁には10以上の数が入るため、アルファベットが用いられる場合が多い。

以下、この記事中では階乗進法で表記されていることを表すための添字として、"!"を用いることにする。

例えば、323100!は、

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

と変換することができる。

異なる記数法への変換方法は階乗進法においても同様に適用できる。例えば、42810を階乗進法に変換するためには、以下のような操作を行えば良い。

428 ÷ 1 = 428 あまり 0
428 ÷ 2 = 214 あまり 0
214 ÷ 3 = 71 あまり 1
71 ÷ 4 = 17 あまり 3
17 ÷ 5 = 3 あまり 2
3 ÷ 6 = 0 あまり 3

この計算によって出たあまりを下からたどって、42810=323100!

また、階乗進法によって任意の整数を一意の小数として表せることは、以下の式から導かれる。

この恒等式は、数学的帰納法によって容易に証明することができる。

順列

整数が階乗進法で表現されている場合、整数0,...,n!−1(または階乗進法でn桁の数)と辞書式順序でのn個の要素の順列の間には自然な写像があり、この写像はレーマー符号と呼ばれている。たとえば n=3 の場合、写像は以下の表の通りとなる


10進法 階乗進法 順列
010 0:0:0! (0,1,2)
110 0:1:0! (0,2,1)
210 1:0:0! (1,0,2)
310 1:1:0! (1,2,0)
410 2:0:0! (2,0,1)
510 2:1:0! (2,1,0)

小数

素数階乗進法

関連項目

Related Articles

Wikiwand AI