A More Efficient Algorithm for Finding the Number of Permutations of $\mathbb{ZZ}/n\mathbb{ZZ}$ with Distinct Partial Sums

技术摘要：一种寻找 $\mathbb{Z}/n\mathbb{Z}$ 中具有不同部分和的排列数量的高效算法

问题陈述
本文研究了在偶数 $n$ 的整数模 $n$ 加法群 ($\mathbb{Z}/n\mathbb{Z}$) 中，特定排列的计数问题。核心问题是计算排列 $\sigma = (\sigma_0, \sigma_1, \dots, \sigma_{n-1})$ 的数量，使得其部分和（或在该群语境下的“阶乘”）各不相同。具体而言，本文关注的是在线整数数列百科全书（OEIS）中的序列 A141599，该序列统计了 $\mathbb{Z}/2k\mathbb{Z}$ 的排列中具有不同差集的数量。

一个排列若具有不同差集，是指集合 $\{d_i \equiv \sigma_i - \sigma_{i-1} \pmod n \mid 1 \le i \le n-1\}$ 恰好包含 $\mathbb{Z}/n\mathbb{Z}$ 中所有的非零元素一次。作者指出，此类排列仅在 $n$ 为偶数时存在。计算挑战在于，总排列数 ($n!$) 呈阶乘级增长，使得暴力枚举对于较大的 $n$ 变得不可行。

方法论
作者提出了一种递归回溯算法，通过通过早期剪枝来显著改进之前的暴力枚举方法。该方法建立在三个主要支柱之上：

1. 差集与排序（Sequencings）之间的双射
   论文建立了“具有不同差集的差集”与 $\mathbb{Z}/n\mathbb{Z}$ 的“排序”之间的形式化双射（定理 1）。排序被定义为一个排列，其部分和 $s(\sigma, i) = \sum_{j=0}^i \sigma_j$ 互不相同。证明表明，一个差集 $D_\tau = (d_1, \dots, d_{n-1})$ 可以映射到一个排序 $\sigma = (0, d_1, \dots, d_{n-1})$，反之亦然。这使得作者能够直接计算排序的数量，而非直接计算差集的数量。

2. 通过乘法进行的对称性缩减
   利用引理 2，作者利用以下性质：如果 $\sigma$ 是一个排序，且 $r$ 是与 $n$ 互质的整数 ($\gcd(r, n) = 1$)，那么逐元素乘积 $(r\sigma_0, r\sigma_1, \dots, r\sigma_{n-1})$ 也是一个排序。这使得算法可以计算特定“分支”（以 $0, 1$开头的排列）的排序数量，并通过乘以欧拉函数$\phi(n/d)$ 来涵盖其他分支，而不是单独计算每一个。

3. 递归分支剪枝（算法 2）
   新算法的核心是一个构建部分排列的递归搜索。与验证完整排列的传统暴力方法不同，该算法维护了一个“部分和”的状态（partials）。

   • 剪枝逻辑： 如果向部分排列中添加新元素导致部分和已经出现过（或过早等于 0），则该分支会被立即放弃。
   • 效率： 这防止了算法去探索那些会延伸出无效部分序列的 $(n-k)!$ 个排列。例如，在 $\mathbb{Z}/20\mathbb{Z}$ 中，部分序列 $(0, 1, 19)$ 在索引 2 处产生部分和为 0，这是无效的；算法会立即丢弃整个分支，从而节省了 $17!$ 次潜在的验证调用。

主要贡献

• OEIS A141599 的新项： 利用改进后的算法，作者计算了该序列的第 10、11 和 12 项（对应 $n=20, 22, 24$）。其值为：
  • $n=20$：5,074,931,072
  • $n=22$：298,557,044,000
  • $n=24$：21,224,961,132,544
    第 10 项和第 11 项已由 Bert Dobbelaere 独立验证。
• 理论统一： 论文提供了关于差集与排序之间双射的严格证明，将 Gilbert 和 Gordon 的经典结果与当前的计算方法统一起来。
• 算法优化： 引入了基于部分和碰撞进行早期终止的递归分支搜索，这代表了目前求解该特定计数问题最高效的方法。

结果与数据分析
论文展示了数据（表 1 和表 2），对比了直至 $n=22$ 的偶数 $n$ 下排序的数量与总排列数 ($n!$) 的关系。结果表明，随着 $n$ 的增加，排序占总排列数的比例严格且迅速地下降，每一步大约下降一个数量级。对于 $n=22$，该比例约为 $2.66 \times 10^{-10}$。

这些经验证据支持了剪枝策略的有效性。由于有效的排序在所有排列的空间中极其稀疏，生成并验证完整的排列是非常低效的。这种递归方法通过立即消除无效的部分路径，与观察到的稀疏性相契合。

意义与主张
作者声称，他们的算法是目前计算序列 A141599 各项最有效的算法。他们认为，虽然时间复杂度仍然是超多项式级的（可能比指数级更糟，但优于 $O(n!)$），但剪枝技术通过避免在无效分支上浪费计算，实现了对暴力方法的“严格改进”。

论文谦虚地总结道，除非能发现新的数学变换，否则进一步改进计数算法的可能性有限。具体而言，他们指出，未来的进展可能取决于能否识别出一组完整的变换（超越目前的互质整数乘法），这些变换可以将一小组已知的排序映射到给定 $n$ 的全体排序，从而可能完全绕过穷举搜索。然而，他们在本文中并未提出此类变换，并指出当前的递归方法已是解决该定义问题的最前沿水平。