为何严格递增索引的三层嵌套for循环迭代次数为四面体数

你的三层嵌套循环本质是统计满足0 ≤ i < j < k < N的三元组总个数，计数结果对应组合数与四面体数的等价性，具体逻辑如下：

• 循环的约束天然排除了重复计数：j从i+1起始保证j > i，k从j+1起始保证k > j，所有被计数的三元组都是从0到N-1这N个整数中选出的、无重复、严格递增的三个数，不存在顺序不同导致的重复统计。
• 这类「从m个元素中选t个不区分顺序的不同元素」的计数问题，对应数学上的组合数，计算公式为：

  C(m, t) = m! / (t! * (m - t)!)
  

  这里选3个元素，即t=3，代入后得到：

  C(N, 3) = N * (N-1) * (N-2) / (3*2*1) = N(N-1)(N-2)/6
  

• 四面体数的本质是三角形数的累加：三维空间中堆正四面体时，每层球的数量是二维的三角形数（对应从若干元素选2个的组合数），把所有层的数量累加，就得到四面体数，标准公式为Tet(n) = n(n+1)(n+2)/6，对应底面每条边有n个球的四面体总球数。

关于n = N-2的偏移来源 #

把组合数公式和四面体数公式做变量代换就能直接得到对应关系：
令n = N-2，代入组合数公式：

C(N,3) = N(N-1)(N-2)/6 = (n+2)(n+1)n/6 = Tet(n) = Tet(N-2)

这个偏移来自索引的取值边界：
要凑出满足i<j<k的三元组，最小的合法取值是i=0、j=1、k=2，对应N=3时刚好只有1组，代入四面体数公式得Tet(3-2)=Tet(1)=1，和你运行得到的第一个结果一致；N=4时总共有4组，对应Tet(4-2)=Tet(2)=4，和你列出的序列1、4、10、20……完全匹配。

你可以用小值快速验证：

• N=5时，C(5,3)=10，对应Tet(3)=345/6=10
• N=6时，C(6,3)=20，对应Tet(4)=456/6=20
  所有结果和你运行得到的counter值完全一致。

内容的提问来源于stack exchange，提问作者Yang Wu