導入

　$2$ 進法があります。

• $1 \rightarrow 1$
• $2 \rightarrow 10$
• $3 \rightarrow 11$
• $4 \rightarrow 100$
• $5 \rightarrow 101$
  $\vdots$

　では、$1$ 進法ではどうなるでしょうか？

• $1 \rightarrow 0$
• $2 \rightarrow 00$
• $3 \rightarrow 000$
• $4 \rightarrow 0000$
• $5 \rightarrow 00000$
  $\vdots$

　わかりやすい！　……と思ったあなた。

　この記事では、それは違う という話をします。

　なお、普通の生活では上の認識で差し支えないので、わざわざ「いやそれは $1$ 進法ではなくてぇ……」と訂正していたら狂人だと思われるのでやめましょう。
　私は狂っているので続けます。

なぜ間違っているのか？

　いわゆる $N$ 進法（便宜上、これらの言葉を自然 $N$ 進法 と表記します）では、先頭の $0$ はいくらあっても意味がないです。よって、以下の数字はすべておなじ $1$ です。

• $1$
• $01$
• $001$
• $0001$
  $\vdots$

　同様に、以下の数字はすべておなじ $0$ （というか虚無）です

• $0$
• $00$
• $000$
• $0000$
  $\vdots$

　このように、自然 $1$ 進法ではおたがいの数を区別できません。よって、「$1$ 進法は $1$ 種類の記号で数を数える」というのは間違いです。

では何なのか？

　この問題の本質は、$0$ のほかに「空白」があって、それが先頭を満たしていることから生じます。

　実は、多くの人はこの数え方を日常的に、というか業務的な場面で良く使っているはずです。

　Excel です。

• A
  $\vdots$
• Z
• AA
  $\vdots$
• ZZ
• AAA
  $\vdots$

　このような増え方はまさにセクション冒頭で示したものです。

全単射記数

　実は、この考え方については、以前に過去記事 で触れたことがあり、このような数え方を Bijective Numeration と言います。当該記事では「全単射記数法」という和訳を採用しているので、以後、自然 $N$ 進法と区別するために、全単射 $N$ 進法と表記します。

　なお、各記数法が数える「個数」の定義については、

• 自然 $N$ 進法：非負整数 （いわゆる、$0$ を含む自然数）
• 全単射 $N$ 進法：$N$ 種類の文字を組み合わせて表現できる非空文字列

　の数であるとします。

　それぞれの要点をまとめると以下のようになります。

自然N進法

• ちょうど $D$ 桁に含まれる個数：$(N-1) \times N^{D-1}$
• $D$ 桁以下の累計個数：$N^D$ ※ $0$ を含む

全単射N進法

• ちょうど $D$ 桁に含まれる個数：$N^D$ ※ただし、$D=0$ のときは $0$
• $D$ 桁以下の累計個数：$\frac{N^{D+1}-1}{N-1}-1$

結論

　つまり、いわゆる「個数を数える方法」は、全単射 $1$ 進法であり、自然 $1$ 進法ではない、ということでした。

　Excel に馴染みがある人なら、「$A$ しかない列番号」といった方が伝わりやすいかもしれません。

　このことを、一般式からも考察しておきます。

自然1進法

　ちょうど $D$ 桁に含まれる個数は

• $(1-1) \times 1^{D-1}=0$

　となります。つまり、どの桁もひとつの数も格納できません。

　$D$ 桁以下の累計個数は、

• $1^D = 1$

　となります。

　どの桁もひとつの数も格納できないですが、その一方で、$1$ 桁以上の累計はただひとつの数（虚無？）を持つ、というやや非直感的な結果になります。

全単射1進法

　ちょうど $D$ 桁に含まれる個数は

• $1^D = 1$

　です。

　$D$ 桁以下の累計個数は、

• $\frac{1^{D+1}-1}{1-1}-1$

　ですが、これに $N=1$ を代入すると、分母が $0$ になってしまい、定義不可能になります。
　しかし、これは等比級数の和の公式が $N=1$ では使えないだけなので、愚直に考えて

• 長さ $1,2,\dots,D$ の列が 1 つずつある
• 累計個数は $\sum_{k=1}^D 1 = D$

　と考えられます。

　このことからも、「個数を数える方法」は全単射 $1$ 進法であると考えた方が適切であることがわかります。