双射进位制记数法
| 双射记数法 | |
|---|---|
| 术语名称 | 双射记数法 |
| 英语名称 | bijective numeration |
| 别名 | 双射进位制记数法, bijective positional notation |
| 基数 | |
|---|---|
| 术语名称 | 基数 |
| 英语名称 | radix |
| 别名 | base |
双射进位制记数法(bijective positional notation)指一种记数法，将符号的全部排列按类似进位制记数法的方式与正整数构成双射。这意味着双射进位制中不存在普通进位制中 1 = 01 = 001 = 0001 = …… 的现象，一般也没有对应于 0 的符号，而对应于 0 的数是空串。由于乘法原理使得每次出现下个符号前遍历低位排列的操作一定是符号数的幂，这是一种位值制记数法。也称双射进制或双射进位制。
由于缺少负数且只能表达整数，一般用于序号。
按顺序排列这一类记数法下的数字，会呈现“过×进一”的形式，直到某一位数后续的所有位都“遍历”了所有可能的符号组合后，清空这些位继续增加并向前“进”位。
定义
关于数
对自然数 [math]\displaystyle{ r }[/math] ，集合 [math]\displaystyle{ D_r = \{1,2,\cdots,r\} }[/math] 是一个含有 [math]\displaystyle{ r }[/math] 个元素的符号集，记这一字符集合上的字符串集（或描述为 Kleene 闭包） [math]\displaystyle{ D_r^* = \{d_n d_{n-1} d_{n-2} \cdots d_0 \mid n\gt =-1 \land d_i \in D_r \} }[/math] ，则这一集合与自然数集 [math]\displaystyle{ \mathbb{N} }[/math] 关于短先字典序序同构，其中元素称为双射 [math]\displaystyle{ r }[/math] 进制数。
关于记数法
在位值制记数法中，若每一个数位上的位权都是某个大于 1 自然数 [math]\displaystyle{ r }[/math] 的幂，即 [math]\displaystyle{ \cdots,r^3,r^2,r,1 }[/math] ，且每一个数位上的数字都只使用 [math]\displaystyle{ r }[/math] 个符号 [math]\displaystyle{ 1,2,\cdots,r }[/math] ，则称这一类记数法为双射进位制记数法(bijective positional notation)，对应这一 [math]\displaystyle{ r }[/math] 的具体记数法称为双射 [math]\displaystyle{ r }[/math] 进制(bijective base-[math]\displaystyle{ r }[/math] notation)，自然数 [math]\displaystyle{ r }[/math] 称为双射 [math]\displaystyle{ r }[/math] 进制中的基数(radix)/底数(base)。
记号
双射 [math]\displaystyle{ r }[/math] 进制中，通常在某一位数字上选择对应 [math]\displaystyle{ 1,2,\cdots,r }[/math] 的字符，并且按照类似平常十进制的方式书写。
整数排列为 [math]\displaystyle{ a_n a_{n-1} a_{n-2} \cdots a_0 }[/math] 的格式，用这一格式记录整数 [math]\displaystyle{ \sum_{i=0}^n a_i r^i = a_n r^n + a_{n-1} r^{n-1} + \cdots + a_0 }[/math] 。
反过来，每一位上的符号与数本身的递推关系满足：若 [math]\displaystyle{ m }[/math] 代表 [math]\displaystyle{ a_n a_{n-1} \cdots a_ 1 a_0 }[/math] ，则：
[math]\displaystyle{ \begin{aligned} m = q_0 r + a_0 &, 1 \leq a_0 \leq r, q_0 = \lceil\tfrac{m}{r}\rceil - 1 \\ q_0 = q_1 r + a_1 &, 1\leq a_1 \leq r, q_1 = \lceil\tfrac{q_0}{r}\rceil - 1 \\ q_1 = q_2 r + a_2 &, 1\leq a_2 \leq r, q_2 = \lceil\tfrac{q_1}{r}\rceil - 1 \\ \vdots \\ q_{n-1} = 0 r + a_n &, 1\leq a_n \leq r, q_{n-1} = \lceil\tfrac{q_{n-1}}{r}\rceil -1 \\ \end{aligned} }[/math]
等式的右侧都是使用最小正余数的带余除法。
| 记数系统 | |||
|---|---|---|---|
| 位值制记数法 | 进位制记数法/标准位值制记数法（进制） | 二进制、八进制、十进制、十六进制、…… | |
| 非标准位值制记数法 | 带符号进位制记数法/ 平衡记数法（平衡进制） |
平衡三进制、…… | |
| 双射记数法（双射进制） | 一进制、双射十进制、双射二十六进制、…… | ||
| 位权是幂 但基数不是自然数 （非自然数进制） |
[math]\displaystyle{ -2 }[/math] 、 [math]\displaystyle{ -4 }[/math] 、…… | ||
| [math]\displaystyle{ \sqrt{2} }[/math] 、 [math]\displaystyle{ \sqrt{3} }[/math] 、 [math]\displaystyle{ \sqrt[12]{2} }[/math] 、…… | |||
| [math]\displaystyle{ 2i }[/math] 、 [math]\displaystyle{ \sqrt[4]{2}i }[/math] 、 [math]\displaystyle{ 2\omega }[/math] 、 [math]\displaystyle{ \sqrt[3]{2}\omega }[/math] 、 [math]\displaystyle{ -1\pm i }[/math] 、…… | |||
| 位权不是幂（混合进制） | 二五混合进制、阶乘进制、…… | ||
| 其他 | [math]\displaystyle{ p }[/math]-进数 | ||
| 质数记数法、…… | |||
| 符值制记数法 | 罗马记数法、希腊记数法、…… | ||