階乗法

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

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

意味

階乗は混合基数記数法です。右から i番目の桁の基数はiです。つまり、その桁はiより小さくなければなりません。また、（下位の桁の基数を考慮して）その値は $(i - 1)$ !（その位の値）倍されます。

基数/底	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、2番目の桁は0または1、3番目の桁は0、1、または2、というように続くことがわかります（OEISのシーケンスA124252）。階乗数法では、0! は常に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 ₁₀は、次の連続した割り算によって階乗表現に変換できます。

463÷1 = 463、余り0

463÷2＝231、余り1

231÷3 = 77、余り0

77÷4＝19、余り1

19÷5＝3、余り4

3 ÷ 6 = 0、余り 3

商がゼロになると処理は終了します。余りを逆順に読むと、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通りの順列を示しています。左反転数と右反転数（後者はしばしばLehmerコードと呼ばれる）は、特に階乗数として解釈するのに適しています。は順列の逆コレクシコグラフィー順（この表のデフォルトの順序）における位置を示し、後者は辞書式順序（どちらも0から数える）における位置を示します。 $l$ $r$ $l$

右側に省略可能な0がある列でソートすると、その列の階乗数は左側の固定列のインデックス番号と対応します。小さな列は隣接する列の反転であり、これらを使用してコレクシコグラフィック順に並べることができます。右端の列には、階乗数の桁和（表のデフォルト順序ではOEIS : A034968）が表示されます。


0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

	$\pi$		$v$			$l$	$r$		#
0	1234	4321	000 0	0 000	000 0	0 000	000 0	0 000	0
1	2134	4312	100 0	0 001	001 0	0 100	100 0	0 001	1
2	1324	4231	010 0	0 010	010 0	0 010	010 0	0 010	1
3	3124	4213	110 0	0 011	011 0	0 110	200 0	0 002	2
4	2314	4132	200 0	0 002	020 0	0 020	110 0	0 011	2
5	3214	4123	210 0	0 012	021 0	0 120	210 0	0 012	3
6	1243	3421	001 0	0 100	100 0	0 001	001 0	0 100	1
7	2143	3412	101 0	0 101	101 0	0 101	101 0	0 101	2
8	1423	3241	011 0	0 110	110 0	0 011	020 0	0 020	2
9	4123	3214	111 0	0 111	111 0	0 111	300 0	0 003	3
10	2413	3142	201 0	0 102	120 0	0 021	120 0	0 021	3
11	4213	3124	211 0	0 112	121 0	0 121	310 0	0 013	4
12	1342	2431	020 0	0 020	200 0	0 002	011 0	0 110	2
13	3142	2413	120 0	0 021	201 0	0 102	201 0	0 102	3
14	1432	2341	021 0	0 120	210 0	0 012	021 0	0 120	3
15	4132	2314	121 0	0 121	211 0	0 112	301 0	0 103	4
16	3412	2143	220 0	0 022	220 0	0 022	220 0	0 022	4
17	4312	2134	221 0	0 122	221 0	0 122	320 0	0 023	5
18	2341	1432	300 0	0 003	300 0	0 003	111 0	0 111	3
19	3241	1423	310 0	0 013	301 0	0 103	211 0	0 112	4
20	2431	1342	301 0	0 103	310 0	0 013	121 0	0 121	4
21	4231	1324	311 0	0 113	311 0	0 113	311 0	0 113	5
22	3421	1243	320 0	0 023	320 0	0 023	221 0	0 122	5
23	4321	1234	321 0	0 123	321 0	0 123	321 0	0 123	6

別の例として、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を引いた値となるため、いかなる数も複数の方法で表現することはできません。

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

これは数学的帰納法で簡単に証明できます。または、単に次のことに気付くだけで証明できます。後続の項は互いに打ち消し合い、最初の項と最後の項が残ります (テレスコーピング級数を参照)。 $\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:0 _!と表記できますが、 100000000000 _! = 1:0:0:0:0:0:0:0:0:0:0:0:0 _!とは表記できず、これは 11! = 39,916,800 ₁₀を表します。したがって、他の基数Nと同様に文字 A から Z を使って数字 10、11、12、...、35 を表すと、表現可能な最大の数は 36 × 36! − 1 になります。任意の大きな数の場合は、個々の数字を表す基数、たとえば 10 進数を選択し、それらの間に区切り記号を付ける必要があります (たとえば、各数字に、同じく 10 進数で表された基数を添え字として付けます (2 ₄ 0 ₃ 1 ₂ 0 _{1のように、この数は 2:0:1:0}_!と表記することもできます)。実際、階乗数自体は、有限の記号アルファベットのみを使用してすべての自然数を表現できるという意味で、真の数値システムではありません。

順列

整数 $0, 1, ...,$ $n$ $! - 1$ （あるいは階乗表現におけるn桁の数）と、 n個の要素を辞書式順序で並べた順列との間には、整数が階乗形式で表現されるとき、自然な写像が存在する。この写像はレーマー符号（あるいは反転表）と呼ばれている。例えば、 $n$ $= 3$ のとき、このような写像は次のようになる。

小数点	因数分解	順列
0 ₁₀	0:0:0 _!	（0,1,2）
1 ₁₀	0:1:0 _!	（0,2,1）
2 ₁₀	1:0:0 _!	（1,0,2）
3 ₁₀	1:1:0 _!	（1,2,0）
4 ₁₀	2:0:0 _!	（2,0,1）
5 ₁₀	2:1:0 _!	（2,1,0）

いずれの場合も、順列の計算は、左端の因数分解桁（ここでは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 ₁₀ 0:0:0 _! 0:0:0 _! ((0,1,2),(0,1,2)) 1 ₁₀ 0:0:0 _! 0:1:0 _! ((0,1,2),(0,2,1)) ... 5 ₁₀ 0:0:0 _! 2:1:0 _! ((0,1,2),(2,1,0)) 6 ₁₀ 0:1:0 _! 0:0:0 _! ((0,2,1),(0,1,2)) 7 ₁₀ 0:1:0 _! 0:1:0 _! ((0,2,1),(0,2,1)) ... 22 ₁₀ 1:1:0 _! 2:0:0 _! ((1,2,0),(2,0,1)) ... 34 ₁₀ 2:1:0 _! 2:0:0 _! ((2,1,0),(2,0,1)) 35 ₁₀ 2:1:0 _! 2:1:0 _! ((2,1,0),(2,1,0))

小数値

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

したがって、1 つの拡張として、常にゼロとなる 1/0! と 1/1! の箇所を省略して、代わりに 1/0!、1/1!、1/2!、1/3!、...、1/ n ! などを使用することもできます。

この方法を用いると、すべての有理数は、その「桁数」が表される有理数の分母の長さ以下となるような、終端展開を持つことになります。これは、任意の整数に階乗が存在し、したがって分母がそれ自身の階乗に割り切れる（たとえそれより小さな階乗に割り切れなくても）ことを考慮すれば証明できます。

したがって、必然的に、素数の逆数の階乗展開は、その素数の長さと正確に同じ長さ（1/1! の位が省略されている場合は1短い）を持つ。その他の項は、OEIS の A046021 列で与えられる。また、分母が素数である有理数の表現における最後の「桁」または項は、分子と素数の差に等しいことも証明できる。

10進法で4の割り切れるかどうかを調べるのに最後の2桁だけを見れば済むのと同様に、階乗数法では、任意の数の割り切れるかどうかを調べるのに有限個の桁だけを見れば済みます。つまり、階乗数法では、それぞれの数に割り切れる規則があるということです。

また、すべての有理数には、小数で 0.24999... = 0.25 = 1/4 や0.999... = 1などであるという事実に似た、終了しない等価物も存在します。これは、最後の項を 1 減らし、残りの無限個の項をその位置の基数で可能な最大の値で埋めることで作成できます。

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

$1/2=0.0\ 1_{!}$
$1/3=0.0\ 0\ 2_{!}$
$2/3=0.0\ 1\ 1_{!}$
$1/4=0.0\ 0\ 1\ 2_{!}$
$3/4=0.0\ 1\ 1\ 2_{!}$
$1/5=0.0\ 0\ 1\ 0\ 4_{!}$
$1/6=0.0\ 0\ 1_{!}$
$5/6=0.0\ 1\ 2_{!}$
$1/7=0.0\ 0\ 0\ 3\ 2\ 0\ 6_{!}$
$1/8=0.0\ 0\ 0\ 3_{!}$
$1/9=0.0\ 0\ 0\ 2\ 3\ 2_{!}$
$1/10=0.0\ 0\ 0\ 2\ 2_{!}$
$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_{!}$
$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_{!}$
$1/12\ \ =0.0\ 0\ 0\ 2_{!}$
$5/12\ \ =0.0\ 0\ 2\ 2_{!}$
$7/12\ \ =0.0\ 1\ 0\ 2_{!}$
$11/12=0.0\ 1\ 2\ 2_{!}$
$1/15=0.0\ 0\ 0\ 1\ 3_{!}$
$1/16=0.0\ 0\ 0\ 1\ 2\ 3_{!}$
$1/18=0.0\ 0\ 0\ 1\ 1\ 4_{!}$
$1/20=0.0\ 0\ 0\ 1\ 1_{!}$
$1/24=0.0\ 0\ 0\ 1_{!}$
$1/30=0.0\ 0\ 0\ 0\ 4_{!}$
$1/36=0.0\ 0\ 0\ 0\ 3\ 2_{!}$
$1/60=0.0\ 0\ 0\ 0\ 2_{!}$
$1/72=0.0\ 0\ 0\ 0\ 1\ 4_{!}$
$1/120=0.0\ 0\ 0\ 0\ 1_{!}$
$1/144=0.0\ 0\ 0\ 0\ 0\ 5_{!}$
$1/240=0.0\ 0\ 0\ 0\ 0\ 3_{!}$
$1/360=0.0\ 0\ 0\ 0\ 0\ 2_{!}$
$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..._{!}$
$e^{-1}=0.0\ 0\ 2\ 0\ 4\ 0\ 6\ 0\ 8\ 0\ A\ 0\ C\ 0\ E..._{!}$
$\sin(1)=0.0\ 1\ 2\ 0\ 0\ 5\ 6\ 0\ 0\ 9\ A\ 0\ 0\ D\ E..._{!}$
$\cos(1)=0.0\ 1\ 0\ 0\ 4\ 5\ 0\ 0\ 8\ 9\ 0\ 0\ C\ D\ 0..._{!}$
$\sinh(1)=1.0\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0..._{!}$
$\cosh(1)=1.0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1..._{!}$

参照

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

参考文献

^ Knuth, DE (1973)、「第3巻ソートと検索」、The Art of Computer Programming、Addison-Wesley、p. 12、ISBN 0-201-89685-0
^ Cantor, G. (1869)、Zeitschrift für Mathematik und Physik、vol. 14。
^ Knuth, DE (1997)、「第2巻：半数値アルゴリズム」、The Art of Computer Programming（第3版）、Addison-Wesley、p. 192、ISBN 0-201-89684-2。
^ Laisant、Charles-Ange ( 1888)、「Sur la numérationactorielle、application aux permutations」、Bulletin de la Société Mathématique de France (フランス語)、16 : 176–183。
^ 「factoradic」という用語は、McCaffrey, James (2003)「.NETでの順列の使用によるシステムセキュリティの向上」(Microsoft Developer Network)で紹介されているようです。。

Mantaci, Roberto; Rakotondrajao, Fanja (2001)、「オイラー的意味を認識する順列表現」(PDF)、Discrete Mathematics and Theoretical Computer Science、4 : 101– 108、2011年5月24日時点のオリジナル(PDF)からアーカイブ、 2005年3月27日取得。
Arndt, Jörg (2010). Matters Computational: Ideas, Algorithms, Source Code. pp. 232– 238.

外部リンク

Lehmer コード計算機順列の数字は 1 から始まるので、このページの結果と同等の結果を得るには、すべての順列の数字を頭の中で 1 ずつ減らす必要があります。
階乗法

[1] Knuth, DE (1973)、「第3巻ソートと検索」、The Art of Computer Programming、Addison-Wesley、p. 12、ISBN 0-201-89685-0

[2] Cantor, G. (1869)、Zeitschrift für Mathematik und Physik、vol. 14。

[3] Knuth, DE (1997)、「第2巻：半数値アルゴリズム」、The Art of Computer Programming（第3版）、Addison-Wesley、p. 192、ISBN 0-201-89684-2。

[4] Laisant、Charles-Ange ( 1888)、「Sur la numérationactorielle、application aux permutations」、Bulletin de la Société Mathématique de France (フランス語)、16 : 176–183。

[5] 「factoradic」という用語は、McCaffrey, James (2003)「.NETでの順列の使用によるシステムセキュリティの向上」(Microsoft Developer Network)で紹介されているようです。。