階乗進法のソースを表示

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

== 定義 ==
階乗進法は複数の底が混在した[[位取り記数法]]であり、下から''i''桁目の仮数が0から''i''-1、底が''i''となる。 
{| class="wikitable" style="text-align:right;"
|-
! {{rh}} | 桁                     
|    8  ||   7  ||   6 ||  5  ||  4 ||  3 ||  2 || 1
|-
! {{rh}} | 桁の重み               
|   7!  ||  6!  ||  5! ||  4! || 3! || 2! || 1! || 0!
|-
! {{rh}} | 桁の重み(十進法)   
| 5040 || 720 || 120 || 24 || 6 ||  2 ||  1 || 1
|-
! {{rh}} | 桁の仮数     
|    7  ||   6  ||   5 ||  4  ||  3 ||  2 ||  1 || 0
|}
ただし、最下位は常に0となるため、省略されることもある。また、下から11桁目以降の桁には10以上の数が入るため、アルファベットが用いられる場合が多い。

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

例えば、323100<sub>!</sub>は、

: 323100<sub>!</sub>
: {{=}} 3×5!&nbsp;+&nbsp;2×4!&nbsp;+&nbsp;3×3!&nbsp;+&nbsp;1×2!&nbsp;+&nbsp;0×1!&nbsp;+&nbsp;0×0!&nbsp;
: {{=}} ((((3×5&nbsp;+&nbsp;2)×4&nbsp;+&nbsp;3)×3&nbsp;+&nbsp;1)×2&nbsp;+&nbsp;0)×1&nbsp;+&nbsp;0
: {{=}} &nbsp;428<sub>10</sub>

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

異なる記数法への変換方法は階乗進法においても同様に適用できる。例えば、428<sub>10</sub>を階乗進法に変換するためには、以下のような操作を行えば良い。
{| style="text-align:right;"
|
: 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<sub>10</sub>=323100<sub>!</sub>

また、階乗進法によって任意の整数を一意の小数として表せることは、以下の式から導かれる。
:<math> \sum_{i=0}^n {i\cdot i!} = {(n+1)!} - 1</math>
この恒等式は、[[数学的帰納法]]によって容易に証明することができる。

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


{| class="wikitable"
|-
!scope="col"| 10進法
!scope="col"| 階乗進法
!scope="col"| 順列
|-
|0<sub>10</sub>
|0:0:0<sub>!</sub>
|(0,1,2)
|-
|1<sub>10</sub>
|0:1:0<sub>!</sub>
|(0,2,1)
|-
|2<sub>10</sub>
|1:0:0<sub>!</sub>
|(1,0,2)
|-
|3<sub>10</sub>
|1:1:0<sub>!</sub>
|(1,2,0)
|-
|4<sub>10</sub>
|2:0:0<sub>!</sub>
|(2,0,1)
|-
|5<sub>10</sub>
|2:1:0<sub>!</sub>
|(2,1,0)
|}

== 小数 ==
この記数法の拡張として、小数を表すために小数第''n''位の重みを{{math|{{sfrac|''1''|''n''!}}}}とする方法があり、これによって任意の有理数を有限小数で表現できるという特徴がある。この方法で拡張した場合、小数第1位は常に0となる。
以下に一部の変換表を示す。ただし、全て左辺は十進法である。
: <math>1/2 = 0.0\ 1_!</math>
: <math>1/3 = 0.0\ 0\ 2_!</math>
: <math>2/3 = 0.0\ 1\ 1_!</math>
: <math>1/4 = 0.0\ 0\ 1\ 2_!</math>
: <math>3/4 = 0.0\ 1\ 1\ 2_!</math>
: <math>1/5 = 0.0\ 0\ 1\ 0\ 4_!</math>
: <math>1/6 = 0.0\ 0\ 1_!</math>
: <math>5/6 = 0.0\ 1\ 2_!</math>
: <math>1/7 = 0.0\ 0\ 0\ 3\ 2\ 0\ 6_!</math>
: <math>1/8 = 0.0\ 0\ 0\ 3_!</math>
: <math>1/9 = 0.0\ 0\ 0\ 2\ 3\ 2_!</math>
: <math>1/10 = 0.0\ 0\ 0\ 2\ 2_!</math>
: <math>1/11 \ \ = 0.0\ 0\ 0\ 2\ 0\ 5\ 3\ 1\ 4\ 0\ A_!</math>
: <math>2/11 \ \ = 0.0\ 0\ 1\ 0\ 1\ 4\ 6\ 2\ 8\ 1\ 9_!</math>
: <math>9/11 \ \ = 0.0\ 1\ 1\ 3\ 3\ 1\ 0\ 5\ 0\ 8\ 2_!</math>
: <math>10/11 = 0.0\ 1\ 2\ 1\ 4\ 0\ 3\ 6\ 4\ 9 \ 1_!</math>
: <math>1/12 \ \ = 0.0\ 0\ 0\ 2_!</math>
: <math>5/12 \ \ = 0.0\ 0\ 2\ 2_!</math>
: <math>7/12 \ \ = 0.0\ 1\ 0\ 2_!</math>
: <math>11/12 = 0.0\ 1\ 2\ 2_!</math>
: <math>1/15 = 0.0\ 0\ 0\ 1\ 3_!</math>
: <math>1/16 = 0.0\ 0\ 0\ 1\ 2\ 3_!</math>
: <math>1/18 = 0.0\ 0\ 0\ 1\ 1\ 4_!</math>
: <math>1/20 = 0.0\ 0\ 0\ 1\ 1_!</math>
: <math>1/24 = 0.0\ 0\ 0\ 1_!</math>
: <math>1/30 = 0.0\ 0\ 0\ 0\ 4_!</math>
: <math>1/36 = 0.0\ 0\ 0\ 0\ 3\ 2_!</math>
: <math>1/60 = 0.0\ 0\ 0\ 0\ 2_!</math>
: <math>1/72 = 0.0\ 0\ 0\ 0\ 1\ 4_!</math>
: <math>1/120 = 0.0\ 0\ 0\ 0\ 1_!</math>
: <math>1/144 = 0.0\ 0\ 0\ 0\ 0\ 5_!</math>
: <math>1/240 = 0.0\ 0\ 0\ 0\ 0\ 3_!</math>
: <math>1/360 = 0.0\ 0\ 0\ 0\ 0\ 2_!</math>
: <math>1/720 = 0.0\ 0\ 0\ 0\ 0\ 1_!</math>

一部の無理数は、階乗進法に変換したときに特徴的な小数表示を持つ。例えば以下のようなものである。

: <math>e = 1\ 0.0\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\cdots_!</math>
: <math>e^{-1} = 0.0\ 0\ 2\ 0\ 4\ 0\ 6\ 0\ 8\ 0\ A\ 0\ C\ 0\ E\cdots_!</math>
: <math>\sin(1) = 0.0\ 1\ 2\ 0\ 0\ 5\ 6\ 0\ 0\ 9\ A\ 0\ 0\ D\ E\cdots_!</math>
: <math>\cos(1) = 0.0\ 1\ 0\ 0\ 4\ 5\ 0\ 0\ 8\ 9\ 0\ 0\ C\ D\ 0\cdots_!</math>
: <math>\sinh(1) = 1.0\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\cdots_!</math>
: <math>\cosh(1) = 1.0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\cdots_!</math>

== 素数階乗進法 ==
階乗進法によく似た位取り記数法として、素数階乗進法が存在する。これは下から''n''桁目の重みを<math>p_{n-1}\#</math>としたものである。
{| class="wikitable" style="text-align:right;"
|-
! {{rh}} | 桁                     
|    8  ||   7  ||   6 ||  5  ||  4 ||  3 ||  2 || 1
|-
! {{rh}} | 桁の重み               
| (p<sub>7</sub>=17)# || (p<sub>6</sub>=13)# || (p<sub>5</sub>=11)# || (p<sub>4</sub>=7)# || (p<sub>3</sub>=5)# || (p<sub>2</sub>=3)# || (p<sub>1</sub>=2)# || (p<sub>0</sub>=1)#
|-
! {{rh}} | 桁の重み(十進法)   
| 510510 || 30030 || 2310 || 210 || 30 ||  6 ||  2 ||  1
|-
! {{rh}} | 桁の仮数     
|     18 ||    16 ||   12 ||  10 ||  6 ||  4 ||  2 ||  1
|}
この記数法の一意性は以下の恒等式によって保証される。
: <math> \sum_{i=0}^{n} (p_{i+1} - 1) \cdot p_i\# = p_{n+1}\# - 1 </math>
ただし、<math>n\#</math>は[[素数階乗]]を表す。

== 関連項目 ==
*[[広義の記数法#複数の底の混在|複数の底の混在する記数法]]
*[[広義の記数法]]
*[[位取り記数法]]

{{DEFAULTSORT:かいしようしんほう}}
[[Category:組合せ論]]
[[Category:数の表現]]
[[Category:数学に関する記事]]
[[Category:数学の表記法]]
[[Category:広義の記数法]]