階乗進法

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

定義

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

桁	8	7	6	5	4	3	2	1
桁の重み	7!	6!	5!	4!	3!	2!	1!	0!
桁の重み(十進法)	5040	720	120	24	6	2	1	1
桁の仮数	7	6	5	4	3	2	1	0

ただし、最下位は常に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

=  428₁₀

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

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

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

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

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

$\sum _{i=0}^{n}{i\cdot i!}={(n+1)!}-1$$\sum _{i=0}^{n}{i\cdot i!}={(n+1)!}-1$
この恒等式は、数学的帰納法によって容易に証明することができる。

順列

整数が階乗進法で表現されている場合、整数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)

小数

この記数法の拡張として、小数を表すために小数第n位の重みを1/n!とする方法があり、これによって任意の有理数を有限小数で表現できるという特徴がある。この方法で拡張した場合、小数第1位は常に0となる。 以下に一部の変換表を示す。ただし、全て左辺は十進法である。

$1/2=0.0\ 1_{!}$$1/2=0.0\ 1_{!}$
$1/3=0.0\ 0\ 2_{!}$$1/3=0.0\ 0\ 2_{!}$
$2/3=0.0\ 1\ 1_{!}$$2/3=0.0\ 1\ 1_{!}$
$1/4=0.0\ 0\ 1\ 2_{!}$$1/4=0.0\ 0\ 1\ 2_{!}$
$3/4=0.0\ 1\ 1\ 2_{!}$$3/4=0.0\ 1\ 1\ 2_{!}$
$1/5=0.0\ 0\ 1\ 0\ 4_{!}$$1/5=0.0\ 0\ 1\ 0\ 4_{!}$
$1/6=0.0\ 0\ 1_{!}$$1/6=0.0\ 0\ 1_{!}$
$5/6=0.0\ 1\ 2_{!}$$5/6=0.0\ 1\ 2_{!}$
$1/7=0.0\ 0\ 0\ 3\ 2\ 0\ 6_{!}$$1/7=0.0\ 0\ 0\ 3\ 2\ 0\ 6_{!}$
$1/8=0.0\ 0\ 0\ 3_{!}$$1/8=0.0\ 0\ 0\ 3_{!}$
$1/9=0.0\ 0\ 0\ 2\ 3\ 2_{!}$$1/9=0.0\ 0\ 0\ 2\ 3\ 2_{!}$
$1/10=0.0\ 0\ 0\ 2\ 2_{!}$$1/10=0.0\ 0\ 0\ 2\ 2_{!}$
$1/11\ \ =0.0\ 0\ 0\ 2\ 0\ 5\ 3\ 1\ 4\ 0\ A_{!}$$1/11\ \ =0.0\ 0\ 0\ 2\ 0\ 5\ 3\ 1\ 4\ 0\ A_{!}$
$2/11\ \ =0.0\ 0\ 1\ 0\ 1\ 4\ 6\ 2\ 8\ 1\ 9_{!}$$2/11\ \ =0.0\ 0\ 1\ 0\ 1\ 4\ 6\ 2\ 8\ 1\ 9_{!}$
$9/11\ \ =0.0\ 1\ 1\ 3\ 3\ 1\ 0\ 5\ 0\ 8\ 2_{!}$$9/11\ \ =0.0\ 1\ 1\ 3\ 3\ 1\ 0\ 5\ 0\ 8\ 2_{!}$
$10/11=0.0\ 1\ 2\ 1\ 4\ 0\ 3\ 6\ 4\ 9\ 1_{!}$$10/11=0.0\ 1\ 2\ 1\ 4\ 0\ 3\ 6\ 4\ 9\ 1_{!}$
$1/12\ \ =0.0\ 0\ 0\ 2_{!}$$1/12\ \ =0.0\ 0\ 0\ 2_{!}$
$5/12\ \ =0.0\ 0\ 2\ 2_{!}$$5/12\ \ =0.0\ 0\ 2\ 2_{!}$
$7/12\ \ =0.0\ 1\ 0\ 2_{!}$$7/12\ \ =0.0\ 1\ 0\ 2_{!}$
$11/12=0.0\ 1\ 2\ 2_{!}$$11/12=0.0\ 1\ 2\ 2_{!}$
$1/15=0.0\ 0\ 0\ 1\ 3_{!}$$1/15=0.0\ 0\ 0\ 1\ 3_{!}$
$1/16=0.0\ 0\ 0\ 1\ 2\ 3_{!}$$1/16=0.0\ 0\ 0\ 1\ 2\ 3_{!}$
$1/18=0.0\ 0\ 0\ 1\ 1\ 4_{!}$$1/18=0.0\ 0\ 0\ 1\ 1\ 4_{!}$
$1/20=0.0\ 0\ 0\ 1\ 1_{!}$$1/20=0.0\ 0\ 0\ 1\ 1_{!}$
$1/24=0.0\ 0\ 0\ 1_{!}$$1/24=0.0\ 0\ 0\ 1_{!}$
$1/30=0.0\ 0\ 0\ 0\ 4_{!}$$1/30=0.0\ 0\ 0\ 0\ 4_{!}$
$1/36=0.0\ 0\ 0\ 0\ 3\ 2_{!}$$1/36=0.0\ 0\ 0\ 0\ 3\ 2_{!}$
$1/60=0.0\ 0\ 0\ 0\ 2_{!}$$1/60=0.0\ 0\ 0\ 0\ 2_{!}$
$1/72=0.0\ 0\ 0\ 0\ 1\ 4_{!}$$1/72=0.0\ 0\ 0\ 0\ 1\ 4_{!}$
$1/120=0.0\ 0\ 0\ 0\ 1_{!}$$1/120=0.0\ 0\ 0\ 0\ 1_{!}$
$1/144=0.0\ 0\ 0\ 0\ 0\ 5_{!}$$1/144=0.0\ 0\ 0\ 0\ 0\ 5_{!}$
$1/240=0.0\ 0\ 0\ 0\ 0\ 3_{!}$$1/240=0.0\ 0\ 0\ 0\ 0\ 3_{!}$
$1/360=0.0\ 0\ 0\ 0\ 0\ 2_{!}$$1/360=0.0\ 0\ 0\ 0\ 0\ 2_{!}$
$1/720=0.0\ 0\ 0\ 0\ 0\ 1_{!}$$1/720=0.0\ 0\ 0\ 0\ 0\ 1_{!}$
一部の無理数は、階乗進法に変換したときに特徴的な小数表示を持つ。例えば以下のようなものである。

$e=1\ 0.0\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\cdots _{!}$$e=1\ 0.0\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\cdots _{!}$
$e^{-1}=0.0\ 0\ 2\ 0\ 4\ 0\ 6\ 0\ 8\ 0\ A\ 0\ C\ 0\ E\cdots _{!}$$e^{-1}=0.0\ 0\ 2\ 0\ 4\ 0\ 6\ 0\ 8\ 0\ A\ 0\ C\ 0\ E\cdots _{!}$
${\displaystyle \sin($1)=0.0\ 1\ 2\ 0\ 0\ 5\ 6\ 0\ 0\ 9\ A\ 0\ 0\ D\ E\cdots _{!}} $\sin(1)=0.0\ 1\ 2\ 0\ 0\ 5\ 6\ 0\ 0\ 9\ A\ 0\ 0\ D\ E\cdots _{!}$
${\displaystyle \cos($1)=0.0\ 1\ 0\ 0\ 4\ 5\ 0\ 0\ 8\ 9\ 0\ 0\ C\ D\ 0\cdots _{!}} $\cos(1)=0.0\ 1\ 0\ 0\ 4\ 5\ 0\ 0\ 8\ 9\ 0\ 0\ C\ D\ 0\cdots _{!}$
${\displaystyle \sinh($1)=1.0\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\cdots _{!}} $\sinh(1)=1.0\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\cdots _{!}$
${\displaystyle \cosh($1)=1.0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\cdots _{!}} $\cosh(1)=1.0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\cdots _{!}$

素数階乗進法

階乗進法によく似た位取り記数法として、素数階乗進法が存在する。これは下からn桁目の重みを$p_{n-1}\#$$p_{n-1}\#$としたものである。

桁	8	7	6	5	4	3	2	1
桁の重み	(p7=17)#	(p6=13)#	(p5=11)#	(p4=7)#	(p3=5)#	(p2=3)#	(p1=2)#	(p0=1)#
桁の重み(十進法)	510510	30030	2310	210	30	6	2	1
桁の仮数	18	16	12	10	6	4	2	1

この記数法の一意性は以下の恒等式によって保証される。

$\sum _{i=0}^{n}(p_{i+1}-1)\cdot p_{i}\#=p_{n+1}\#-1$

ただし、$n\#$は素数階乗を表す。

関連項目

• 複数の底の混在する記数法
• 広義の記数法
• 位取り記数法