阶乘进制 (Factorial Number System)

阶乘进制 (FNS) 原理介绍

阶乘进制，又称为 Lehmer 码 (Lehmer code)，是一种混合基数系统 (Mixed Radix System)，它使用阶乘作为每一位的权值（基数），而不是像传统的 进制（如十进制、二进制）那样使用 的幂作为权值。

1. 核心思想

阶乘进制的核心思想是：任何一个非负整数 都可以唯一地表示为一系列系数乘以对应阶乘之和。

2. 表示形式

一个非负整数 在阶乘进制下可以表示为：

其中，每一位 的权值（基数）是 （ 的阶乘）。

数学表达式为：

3. 系数（数字）的限制

这是阶乘进制最关键的特征之一。每一位上的系数 都有严格的取值范围，它取决于该位的权值 ：

权值 ()位的索引 ()系数 () 的取值范围

注意： 最低位 的权值是 ，其系数 只能取 (因为 )。所以，在实际表示中，阶乘进制的最低位 常常被省略或约定为 。

4. 应用：排列和 Lehmer 码

阶乘进制最著名的应用是在排列 (Permutations) 领域：

  • 对于 个元素的集合，总共有 种不同的排列方式。
  • 阶乘进制的 范围内的每一个数，都唯一对应一个 个元素的排列。这个数就是该排列的 Lehmer 码。
  • 系数 在排列中代表了在当前剩下的元素中，第 个位置的元素是第 小的元素（基于 0-索引）。

简而言之，阶乘进制提供了一种将排列和整数进行双射（一一对应）编码的方法。

阶乘进制（Factorial Number System, FNS）的严谨数学证明

我们需要证明两件事：存在性 (Existence) 和 唯一性 (Uniqueness)。

证明一：存在性 (Existence)

我们将使用除法原理 (Division Algorithm) 进行构造性证明。这个过程与我们将十进制数转换为 FNS 的过程完全一致。

设 是一个非负整数。我们从最大的阶乘项开始（即从 开始求解）。

  1. 确定上限 ： 选择最小的整数 使得 。因此，最大的非零系数对应的权值最大为 。

  2. 求解系数 ： 应用除法原理，将 除以 : 其中 是商，且 是余数。

  3. 验证约束条件 ：

    • 因为 ，所以 成立。
    • 由 的选择可知 。
    • 因为 ，所以 。
    • 因此 成立。
    • 由于 ，所以约束 成立。

  4. 递推： 重复上述过程，对余数 应用除法原理除以 ：

    • 由于 ，所以 。
    • 因此， 。
    • 由于 ，所以约束 成立。

  5. 总结： 通过不断对余数重复该过程，我们最终会得到一个零余数（即 ）。这个过程构造性地证明了对于任意非负整数 ，总存在一个满足 约束的阶乘进制表示。

证明二：唯一性 (Uniqueness)

我们将使用反证法来证明系数 是唯一的。

  1. 假设： 假设存在两个不同的 FNS 表达式来表示同一个数 ： 其中，对于所有 ，均满足 ，且对于某些 ，有 。

  2. 找出差异项： 设 是最大的索引，使得 。 将两个表达式相减： 重新整理，将 项移到左侧：

  3. 分析右侧最大值： 右侧 (RHS) 是由所有小于 的阶乘项组成。因为 ，所以 。 RHS 的绝对值最大为所有系数取到最大差值 时的和：

  4. 关键恒等式： 利用恒等式 ： 这是一个伸缩级数 (Telescoping Series)，展开后为： 因此，RHS 的绝对值最大为 ：

  5. 分析左侧最小值： 左侧 (LHS) 是 。 由于我们假设 ，所以 。 因此，LHS 的绝对值最小为：

  6. 得出矛盾： 根据等式 ，我们必须有 。然而，我们推导出： 即 。这显然是一个矛盾。

因此，最初的假设（存在两个不同的表示）是错误的。阶乘进制的表示是唯一的。

结论： 结合存在性证明（构造性算法）和唯一性证明（反证法），我们证明了任何非负整数 都可以唯一地表示为阶乘进制的形式。