階乗数システム

組み合わせ論において、階乗数システム（階乗とも呼ばれる）は、順列の番号付けに適した混合基数数体系である。階乗は基数としてではなく、桁の位取りとして機能するが、階乗基数とも呼ばれる。n !未満の数を階乗表現に変換することで、 n桁の数字列が得られ、それをレーマー符号または反転表^{[ 1 ]}表現として用いるか、 n要素の順列に直接変換することができる。前者の場合、整数からn要素の順列への結果の写像は、それらを辞書式順序でリストする。一般的な混合基数システムは、ゲオルク・カントールによって研究された。^{[ 2 ]}

「階乗数システム」という用語はクヌースによって使用されており^{[ 3 ]}、 フランス語の同義語「numération factorielle」は1888年に初めて使用された^{[ 4 ]。}階乗と混合基数を組み合わせた「factoradic」という用語は、より新しいものと思われる^{[ 5 ] 。}

階乗数システムは混合基数数システムです。右からi番目の桁は基数がiであり、これはその桁が厳密にiより小さくなければならないことを意味し、(下位桁の基数を考慮すると)その値は( i − 1) ! (その位の値) で乗算されます。  

このことから、一番右の桁は常に0、2番目の桁は0または1、3番目の桁は0、1または2、といった具合になることがわかる（OEISのシーケンスA124252）。階乗数体系は、0!の位が常に0であるため、省略して定義されることもある（OEISのシーケンスA007623）。

この記事では、階乗の表現は添え字「!」で示されます。また、いくつかの例では、数字がコロンで区切られています。たとえば、3:4:1:0:1:0 _!は、

= 3×5!  +  4×4!  +  1×3!  +  0×2!  +  1×1!  +  0×0! 

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

=  463 ₁₀。

（位取りは基数から1を引いた数の階乗なので、6桁の因数分解数の場合、式は5!から始まります。）

混合基数系の一般的な性質は、階乗系にも適用されます。例えば、数を基数（1、2、3、…）で繰り返し割り、余りを桁として取り、整数商を0になるまで続けることで、右から左に桁を生成する階乗表現に変換できます。

例えば、463 ₁₀は、以下の連続した除算によって階乗表現に変換できます。

商がゼロになると処理は終了します。余りを逆から読むと 3:4:1:0:1:0 _!となります。

原則として、このシステムは有理数を表すように拡張できますが、定義されていない位の値 (−1)!、(−2)! などの自然な拡張ではなく、小数点以下の基数n = 0、1、2、3、4 などの対称的な選択を使用できます。ここでも、0 と 1 の位は常にゼロなので省略できます。したがって、対応する位の値は 1/1、1/1、1/2、1/6、1/24、...、1/ n ! などとなります。

以下のソート可能な表は、異なる反転関連ベクトルを持つ 4 つの要素の 24 通りの順列を示しています。左反転と右反転の回数${\displaystyle l}$そして${\displaystyle r}$（後者はしばしばレーマーコードと呼ばれる）は、特に階乗数として解釈されるのに適している。${\displaystyle l}$は順列の逆連語順（この表のデフォルトの順序）での位置を示し、後者は辞書順での位置を示します（どちらも0から数えます）。

右側に省略可能な 0 がある列でソートすると、その列の階乗の数値が、左側の固定列のインデックス番号に対応します。小さな列は隣接する列の鏡像であり、それらを辞書式順序に並べるために使用できます。一番右の列には、階乗の数値の桁の合計が表示されます (表のデフォルト順序ではOEIS : A034968 )。 

別の例として、6桁で表せる最大の数は543210 _{!で、これは}10進数で719に相当します。

5×5！ +4×4！ +3x3! +2×2！ +1×1! +0×0!。

_{明らかに、5:4:3:2:1:0 !}の次の階乗表現は1:0:0:0:0:0:0 _!であり、これは 6!  =  720 ₁₀を表し、これは基数 7 の桁の位の値です。したがって、前述の数とその合計式は次のようになります。

6! − 1。

階乗数システムは、使用できる「桁数」に制約があるものの、各自然数に対して一意の表現方法を提供します。連続する階乗にその指数を掛け合わせた和は常に次の階乗から1を引いた値になるため、同じ数を複数の方法で表現することはできません。

${\displaystyle \sum _{i=0}^{n}{i\cdot i!}={(n+1)!}-1.}$

これは数学的帰納法で簡単に証明できます。あるいは、単に次のことに気づけば証明できます。${\displaystyle \forall i,i\cdot i!=(i+1-1)\cdot i!=(i+1)!-i!}$: 後続の項は互いに打ち消し合い、最初と最後の項が残ります (望遠鏡級数を参照)。

しかし、アラビア数字を使用して数字を記述する場合（上記の例のように添え字を含めない場合）、9 より大きい「桁」を持つ数では、単純な連結では曖昧になります。そのような最小の例は、10  ×  10!  =  36,288,000 ₁₀という数で、これは A0000000000 _! =10:0:0:0:0:0:0:0:0:0:0 _!と書くことができますが、100000000000 _! = 1:0:0:0:0:0:0:0:0:0:0:0 _!とは書けません。これは 11! = 39,916,800 _{10を表します。したがって、他の基数}Nと同様に、文字 A～Z を使用して数字 10、11、12、...、35 を表すと、表現可能な最大の数は 36  ×  36!になります。  −  1. 任意のより大きな数を表すには、個々の桁を表す基数（例えば十進数）を選択し、桁間に区切り記号を付ける必要があります（例えば、各桁に基数を添え字として付けることで、これも十進数で表されます。例えば、2 ₄ 0 ₃ 1 ₂ 0 _{1のように。この数は 2:0:1:0 !}とも書けます）。実際、階乗数システム自体は、有限の記号のアルファベットのみを使用してすべての自然数を表すという意味では、真の意味での数体系ではありません。

整数0, 1, ..., n ! − 1 (または同等に、階乗表現でn桁の数) と、 n個の要素の辞書順の順列の間には、整数が階乗形式で表現されている場合、自然なマッピングが存在します。このマッピングは、レーマー符号(または反転表)と呼ばれています。たとえば、n = 3の場合、このようなマッピングは次のようになります。       

いずれの場合も、順列の計算は、左端の素数（ここでは 0、1、または 2）を最初の順列の数字として使用し、次にそれを選択肢のリスト（0、1、および 2）から削除することによって行われます。この新しい選択肢のリストは 0 から始まるインデックスを持つと考え、各素数を使用して残りの要素から選択します。2 番目の素数が「0」の場合、リストの最初の要素が 2 番目の順列の数字として選択され、その後リストから削除されます。同様に、2 番目の素数が「1」の場合、2 番目の要素が選択され、その後削除されます。最後の素数は常に「0」であり、リストには要素が 1 つしか残っていないため、それが最後の順列の数字として選択されます。

より長い例を挙げると、そのプロセスがより明確になるかもしれません。0から6までの数字の2982番目の順列を求めたいとしましょう。2982という数は、素因数分解すると4:0:4:1:0:0:0 _!となり、この数は、減少していく順序付き数字の集合をインデックス付けし、各ターンでその集合から各数字を選択することによって、(4,0,6,2,1,3,5)という数字を順番に選び出します。

 4:0:4:1:0:0:0 ! ─► (4,0,6,2,1,3,5) 階乗: 4 : 0 : 4 : 1 : 0 : 0 : 0 ! ├─┬─┬─┬─┐ │ ├─┬─┬─┬─┐ ├─┐ │ │ │ セット: (0,1,2,3,4,5,6) ─► (0,1,2,3,5,6) ─► (1,2,3,5,6) ─► (1,2,3,5) ─► (1,3,5) ─► (3,5) ─► (5) │ │ │ │ │ │ │ 順列: (4, 0, 6, 2, 1, 3, 5)

2 つの置換群の直積の自然な指標は、2 つの素因数分解数を 2 つの添え字 "!" で連結したものです。

 連結 小数階素因数分解順列ペア 0 10 0:0:0 ! 0:0:0 ! ((0,1,2),(0,1,2)) 1 10 0:0:0 ! 0:1:0 ! ((0,1,2),(0,2,1)) ... 5 10 0:0:0 ! 2:1:0 ! ((0,1,2),(2,1,0)) 6 10 0:1:0 ! 0:0:0 ! ((0,2,1),(0,1,2)) 7 10 0:1:0 ! 0:1:0 ! ((0,2,1),(0,2,1)) ... 22 10 1:1:0 ! 2:0:0 ! ((1,2,0),(2,0,1)) ... 34 10 2:1:0 ! 2:0:0 ! ((2,1,0),(2,0,1)) 35 10 2:1:0 ! 2:1:0 ! ((2,1,0),(2,1,0))

正負両方の整数nに対して位の値が基数ⁿである単一基数システムとは異なり、階乗数の基数は負の位の値に拡張することはできません。なぜなら、それらは (−1)!、(−2)! などとなり、これらの値は定義されないからです (階乗を参照)。

したがって、考えられる拡張の1つは、代わりに1/0!、1/1!、1/2!、1/3!、...、1/ n !などを使用することであり、常にゼロである1/0!と1/1!の位は省略できる可能性があります。

この方法によれば、すべての有理数は有限展開を持ち、その桁数は、表される有理数の分母以下になります。これは、任意の整数には階乗が存在するため、分母はそれより小さい階乗を割り切れない場合でも、自身の階乗を割り切れるという事実を考慮すれば証明できます。

したがって、必然的に、素数の逆数の因数分解の長さは、その素数と全く同じになります（1/1! の位を省略すれば、1 減算されます）。その他の項は、 OEIS のA046021という数列で示されています。また、分母が素数である有理数の表現の最後の「桁」または項は、分子と分母の差に等しいことも証明できます。

10進数で4の割り算を判定する際に下2桁だけを見ればよいのと同様に、階乗数体系では任意の数の割り算を判定する際に有限桁の数字だけを見ればよい。つまり、各数に対して割り算の規則が存在する。

また、すべての有理数には、10進数で0.24999... = 0.25 = 1/ 4、0.999... = 1などとなるのと同様に、無限に続く等価な数も存在します。これは、最後の項を1減らし、残りの無限個の項をその位置の基数で可能な最大値で埋めることによって作成できます。

以下の例では、位取りを区切るためにスペースを使用しています。位取りは小数で表されます。左側の有理数も小数です。

• ${\displaystyle 1/2=0.0\ 1_{!}}$
• ${\displaystyle 1/3=0.0\ 0\ 2_{!}}$
• ${\displaystyle 2/3=0.0\ 1\ 1_{!}}$
• ${\displaystyle 1/4=0.0\ 0\ 1\ 2_{!}}$
• ${\displaystyle 3/4=0.0\ 1\ 1\ 2_{!}}$
• ${\displaystyle 1/5=0.0\ 0\ 1\ 0\ 4_{!}}$
• ${\displaystyle 1/6=0.0\ 0\ 1_{!}}$
• ${\displaystyle 5/6=0.0\ 1\ 2_{!}}$
• ${\displaystyle 1/7=0.0\ 0\ 0\ 3\ 2\ 0\ 6_{!}}$
• ${\displaystyle 1/8=0.0\ 0\ 0\ 3_{!}}$
• ${\displaystyle 1/9=0.0\ 0\ 0\ 2\ 3\ 2_{!}}$
• ${\displaystyle 1/10=0.0\ 0\ 0\ 2\ 2_{!}}$
• ${\displaystyle 1/11\ \ =0.0\ 0\ 0\ 2\ 0\ 5\ 3\ 1\ 4\ 0\ A_{!}}$
• ${\displaystyle 2/11\ \ =0.0\ 0\ 1\ 0\ 1\ 4\ 6\ 2\ 8\ 1\ 9_{!}}$
• ${\displaystyle 9/11\ \ =0.0\ 1\ 1\ 3\ 3\ 1\ 0\ 5\ 0\ 8\ 2_{!}}$
• ${\displaystyle 10/11=0.0\ 1\ 2\ 1\ 4\ 0\ 3\ 6\ 4\ 9\ 1_{!}}$
• ${\displaystyle 1/12\ \ =0.0\ 0\ 0\ 2_{!}}$
• ${\displaystyle 5/12\ \ =0.0\ 0\ 2\ 2_{!}}$
• ${\displaystyle 7/12\ \ =0.0\ 1\ 0\ 2_{!}}$
• ${\displaystyle 11/12=0.0\ 1\ 2\ 2_{!}}$
• ${\displaystyle 1/15=0.0\ 0\ 0\ 1\ 3_{!}}$
• ${\displaystyle 1/16=0.0\ 0\ 0\ 1\ 2\ 3_{!}}$
• ${\displaystyle 1/18=0.0\ 0\ 0\ 1\ 1\ 4_{!}}$
• ${\displaystyle 1/20=0.0\ 0\ 0\ 1\ 1_{!}}$
• ${\displaystyle 1/24=0.0\ 0\ 0\ 1_{!}}$
• ${\displaystyle 1/30=0.0\ 0\ 0\ 0\ 4_{!}}$
• ${\displaystyle 1/36=0.0\ 0\ 0\ 0\ 3\ 2_{!}}$
• ${\displaystyle 1/60=0.0\ 0\ 0\ 0\ 2_{!}}$
• ${\displaystyle 1/72=0.0\ 0\ 0\ 0\ 1\ 4_{!}}$
• ${\displaystyle 1/120=0.0\ 0\ 0\ 0\ 1_{!}}$
• ${\displaystyle 1/144=0.0\ 0\ 0\ 0\ 0\ 5_{!}}$
• ${\displaystyle 1/240=0.0\ 0\ 0\ 0\ 0\ 3_{!}}$
• ${\displaystyle 1/360=0.0\ 0\ 0\ 0\ 0\ 2_{!}}$
• ${\displaystyle 1/720=0.0\ 0\ 0\ 0\ 0\ 1_{!}}$

また、この方法でパターン化された表現を持つ定数も少数存在します。

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

• 組み合わせ数体系（組み合わせ数とも呼ばれる）
• 無限整数とは、階乗数体系において無限の数字列として表すことができる整数のことである。
• スタインハウス・ジョンソン・トロッターアルゴリズムは、階乗数体系のグレイコードを生成するアルゴリズムである。

• Mantaci, Roberto; Rakotondrajao, Fanja (2001)、「「オイラー的」の意味を知っている順列表現」（PDF）、離散数学と理論計算機科学、4：101–108 、 2011年5月24日にオリジナル（PDF）からアーカイブ、2005年3月27日に取得。
• Arndt, Jörg (2010). Matters Computational: Ideas, Algorithms, Source Code . pp. 232–238 . 

• レーマーコード計算機。順列の桁は1から始まるので、このページと同じ結果を得るには、すべての順列の桁を暗算で1減らしてください。
• 階乗数システム