全単射記数法

全単射記法とは、すべての非負整数を有限の数字列を使用して正確に 1 つの方法で表すことができる記法です。この名前は、この場合、非負整数の集合と有限の記号集合 (「数字」) を使用した有限の文字列の集合の間に存在する 全単射(つまり、1 対 1 の対応) を指します。

一般的な十進法などの一般的な記数法のほとんどは、複数の数字列で同じ正の整数を表すことができるため、一対一ではありません。特に、先頭にゼロを追加しても表される値は変わらないため、「1」、「01」、「001」はすべて数字の1 を表します。最初の数だけが一般的ですが、他の数も可能であるという事実は、十進法が一対一ではないことを意味します。ただし、数字が 1 つだけの単進法は一対一です。

全単射のk進法は、全単射の位置表記法です。これは、集合 {1, 2, ..., k } (ただしk ≥ 1) の数字の文字列を使用して、各正の整数をエンコードします。文字列内の数字の位置によって、その値がkの累乗の倍数として定義されます。Smullyan (1961) はこの表記法をk進数と呼んでいますが、 p進数と混同しないでください。全単射数は、通常の整数を非ゼロの数字の有限文字列で表すシステムですが、p進数は、整数をサブセットとして含む数学値のシステムであり、任意の数値表現で数字の無限シーケンスが必要になる場合があります。

k を基数とする全単射記数法では、数字セット {1, 2, ..., k } ( k ≥ 1) を使用して、次のようにすべての非負整数を一意に表します。

• 整数ゼロは空の文字列で表されます。
• 空でない数字列で表される整数

1 ₁ −1 ... 1 0_​​​​

は

a _n k ⁿ + a _{n −1} k ^{n −1} + ... + a ₁ k ¹ + a ₀ k ⁰。

• 整数m > 0を表す数字列は

1 ₁ −1 ... 1 0_​​​​

どこ

${\displaystyle {\begin{aligned}a_{0}&=m-q_{0}k,&q_{0}&=f\left({\frac {m}{k}}\right)&\\a_{1}&=q_{0}-q_{1}k,&q_{1}&=f\left({\frac {q_{0}}{k}}\right)&\\a_{2}&=q_{1}-q_{2}k,&q_{2}&=f\left({\frac {q_{1}}{k}}\right)&\\&\,\,\,\vdots &&\,\,\,\vdots \\a_{n}&=q_{n-1}-0k,&q_{n}&=f\left({\frac {q_{n-1}}{k}}\right)=0\end{aligned}}}$

そして

${\displaystyle f(x)=\lceil x\rceil -1,}$

${\displaystyle \lceil x\rceil }$x以上の最小の整数(天井関数) です。

対照的に、標準的な位置表記法は、同様の再帰アルゴリズムで定義することができ、

${\displaystyle f(x)=\lfloor x\rfloor ,}$

基数 の場合、単射基数記数法は、標準基数記数法と同様に、無限数の数字（ただし、 は左無限の数字列 として表される）を使用することで、負の整数に拡張できる。これは、オイラー和${\displaystyle k>1}$${\displaystyle k}$${\displaystyle b}$${\displaystyle d_{k-1}}$${\displaystyle f(d_{k-1})=k-1}$${\displaystyle \ldots d_{k-1}d_{k-1}d_{k-1}={\overline {d_{k-1}}}}$

${\displaystyle g({\overline {d_{k-1}}})=\sum _{i=0}^{\infty }f(d_{k-1})k^{i}=-{\frac {k-1}{k-1}}=-1}$

つまり

${\displaystyle g({\overline {d_{k-1}}}d_{k})=f(d_{k})\sum _{i=1}^{\infty }f(d_{k-1})k^{i}=1+\sum _{i=0}^{\infty }f(d_{k-1})k^{i}=0}$

また、すべての正の数は全単射の記数法で表され、数字の表現はで表されます。を基数とする負の数は で表され、 を基数とする負の数は で表されます。これは、符号付き数字表現において、数字の表現を持つすべての整数が で表され、 となるのと似ています。この表現はもはや全単射ではありません。左無限の数字列の集合全体が-進整数を表すのに使用され、整数 はその部分集合にすぎないからです。 ${\displaystyle n}$${\displaystyle d}$${\displaystyle {\overline {d_{k-1}}}d_{k}d}$${\displaystyle k>2}$${\displaystyle n<-1}$${\displaystyle {\overline {d_{k-1}}}d_{i}d}$${\displaystyle i<k-1}$${\displaystyle k=2}$${\displaystyle n<-1}$${\displaystyle {\overline {d_{k}}}d}$${\displaystyle n}$${\displaystyle d}$${\displaystyle {\overline {d_{0}}}d}$${\displaystyle f(d_{0})=0}$${\displaystyle k}$

与えられた基数に対して、 ${\displaystyle k\geq 2}$

• 非負整数nを表すk進数の全単射の桁数は

  ${\displaystyle \lfloor \log _{k}((n+1)(k-1))\rfloor }$, ^[1]通常のk進数とは対照的に、k = 1（つまり単進数）の場合、桁数はnになります。${\displaystyle \lceil \log _{k}(n+1)\rceil }$
  

• 長さのkを底とする全単射の数値で表現できる最小の非負整数は、 ${\displaystyle \ell \geq 0}$

  ${\displaystyle \mathrm {min} (\ell )={\frac {k^{\ell }-1}{k-1}}}$;

• 長さのkを底とする全単射の数値で表現できる最大の非負整数は、 ${\displaystyle \ell \geq 0}$

  ${\displaystyle \mathrm {max} (\ell )={\frac {k^{\ell +1}-k}{k-1}}}$、またはと同等です。${\displaystyle \mathrm {max} (\ell )=k\times \mathrm {min} (\ell )}$${\displaystyle \mathrm {max} (\ell )=\mathrm {min} (\ell +1)-1}$

• 非負整数nに対するkを底とする全単射の数値と通常のk を底とする数値は、通常の数値に数字0が含まれていない場合に限り同一である(または、同等に、全単射の数値が空の文字列でも数字k も含まれていない場合)。

与えられた基数に対して、 ${\displaystyle k\geq 1}$

• 長さのkを底とする単射な数が存在する。^[2]${\displaystyle k^{\ell }}$${\displaystyle \ell \geq 0}$
• 表現される整数の自然順序で並べられた、kを底とする全単射の数値のリストは、自動的にshortlex 順序(それぞれの長さ内で最短が最初、辞書式) になります。したがって、空の文字列を表すために λ を使用すると、1、2、3、8、10、12、および 16 を底とする数値は次のようになります (通常の表現は比較のためにリストされています)。

34152 (5 を底とする全単射) = 3×5 ⁴ + 4×5 ³ + 1×5 ² + 5×5 ¹ + 2×1 = 2427 (10 進数)。

119A (10進法で、「A」は数字の10を表す) = 1×10 ³ + 1×10 ² + 9×10 ¹ + 10×1 = 1200 (10進数)。

26 個を超える要素を持つ典型的なアルファベット順リストは、A、B、C...X、Y、Z、AA、AB、AC...ZX、ZY、ZZ、AAA、AAB、AAC... の順序を使用して、全単射になります。

全単射の 10 進法は、0を表す数字を使用しない10進位取り記数法です。代わりに、 Aのように 10 を表す数字を使用します。

従来の10 進数と同様に、各桁の位置は 10 の累乗を表します。たとえば、123 は「100、プラス 2 つの 10、プラス 3 つの単位」です。従来の 10 進数で非ゼロの数字のみで表されているすべての正の整数(123 など) は、10 進法の単射システムでも同じ表現になります。ゼロを使用するものは書き直す必要があります。たとえば、10 は A になり、従来の 20 は 1A になり、従来の 100 は 9A になり、従来の 101 は A1 になり、従来の 302 は 2A2 になり、従来の 1000 は 99A になり、従来の 1110 は AAA になり、従来の 2010 は 19AA になります。

このシステムでの加算と乗算は、桁が 9 を超えたときではなく 10 を超えたときに繰り上がりが発生する点を除けば、従来の 10 進法と基本的に同じです。したがって、643 + 759 を計算するには、12 の単位 (右側に 2 を書き、10 の位に 1 を繰り上げる)、10 の 10 (100 の位に繰り上がる必要なしに A を書く)、13 の 100 (3 を書き、1000 の位に 1 を繰り上げる)、および 1000 (1 を書く) があり、結果は従来の 1402 ではなく 13A2 になります。

全単射の 26 進数システムでは、ラテン アルファベットの文字「A」から「Z」を使用して、1から26までの26 桁の値を表すことができます。(A=1、B=2、C=3、...、Z=26)

この表記法を選択すると、数字の順序 (1 から始まる) は A、B、C、...、X、Y、Z、AA、AB、AC、...、AX、AY、AZ、BA、BB、BC、... となります。

各桁の位置は 26 の累乗を表します。たとえば、数字 WI は、10 進数で 23 × 26 ¹ + 9 × 26 ^{0 = 607 という値を表します。}

Microsoft Excelを含む多くのスプレッドシートでは、このシステムを使用してスプレッドシートの列にラベルを割り当てます。ラベルは、A、B、C、...、Z、AA、AB、...、AZ、BA、...、ZZ、AAAなどで始まります。たとえば、Excel 2013では、最大16384列（バイナリコードでは2の¹⁴乗）があり、AからXFDまでラベル付けされます。^[3]マルウェアの亜種もこのシステムを使用して命名されています。たとえば、最初に広く普及したMicrosoft WordマクロウイルスであるConceptは、正式にはWM/Concept.A、26番目の亜種はWM/Concept.Z、27番目の亜種はWM/Concept.AA、というように命名されています。このシステムの亜種は、変光星に名前を付けるために使用されています。^[4]これは、文字を使用して体系的に命名する必要があるすべての問題に適用でき、可能な限り短い文字列を使用します。

すべての非負整数は、一対一の基数k ( k ≥ 1) で一意の表現を持つという事実は、「フォーク定理」と呼ばれ、何度も再発見されています。初期の例としては、 k = 10 の場合の Foster (1947)、およびすべてのk ≥ 1の場合の Smullyan (1961) と Böhm (1964)があります。Smullyan はこのシステムを使用して、論理システム内の記号列のGödel 番号付けを提供します。Böhm は、これらの表現を使用して、プログラミング言語P′′で計算を実行します。 Knuth (1969) はk = 10の特殊なケースについて言及しており、Salomaa (1973) はk ≥ 2 のケースについて論じています。Forslund (1995) は別の再発見のようで、古代の記数法がk を基数とする一対一の記数法を使用していたとしても、このシステムが一般に知られていないため、考古学的文書ではそのように認識されない可能性があるという仮説を立てています。

• Böhm, C. (1964 年 7 月)、「チューリングマシンのファミリーと関連するプログラミング言語について」、ICC Bulletin、3 : 191。
• フォルスルンド、ロバート R. (1995)、「既存の位置数体系に対する論理的代替案」、サウスウェスト純粋応用数学ジャーナル、1 : 27–29、MR  1386376、S2CID  19010664。
• フォスター、JE (1947)、「ゼロ記号のない数体系」、数学雑誌、21 (1): 39–41、doi :10.2307/3029479、JSTOR  3029479。
• Knuth, DE (1969)、『コンピュータプログラミングの技法』第 2 巻: 半数値アルゴリズム(第 1 版)、Addison-Wesley、演習 4.1-24 の解答、p. 195（10 進数の単射について説明します。）
• サロマ、A.（1973）、形式言語、アカデミックプレス、注9.1、pp.90-91（すべてのk ≥ 2に対して、k の全単射基数について説明します。）
• Smullyan, R. (1961)、「9. 辞書式順序; 整数の n 進表現」、形式システムの理論、数学研究年報、第 47 巻、プリンストン大学出版、pp. 34-36。