关于n维a^b结构中各维度可达步数及对应顶点数量的通用求解问询

抱歉我不太清楚我研究的这种结构的正式名称，它们的形式是a^b——比如2^3就是我们熟悉的2x2x2立方体，也可以是更高维度的结构，比如6维的2^6（也就是2×2×2×2×2×2的超立方体）。

我现在想搞清楚的核心问题是：从这种结构的任意一个顶点出发，按每个维度上的移动步数组合来分类，每种组合对应的顶点数量是多少？这里的“步数”指的是在单个维度上从起点移动的步数，比如把起点设为坐标(0,0,...,0)，某个顶点的坐标就是(k₁,k₂,...,k_b)，其中每个k_i的取值范围是0到a-1（因为a^b结构每个维度有a个顶点，从起点到最远点需要走a-1步）。

我手动推导的两个例子： #

1. 2^3（2x2x2立方体）的情况

从起点(0,0,0)出发，统计结果完全符合帕斯卡三角的规律：

• 步数组合(0,0,0)：对应1个顶点（就是起点本身）
• 单维度走1步、其余维度走0步（比如(1,0,0)、(0,1,0)、(0,0,1)）：共3个顶点
• 两个维度走1步、剩余维度走0步（比如(1,1,0)、(1,0,1)、(0,1,1)）：共3个顶点
• 三个维度都走1步（(1,1,1)）：共1个顶点
  总数1+3+3+1=8，正好是2^3的顶点总数，没问题。

2. 3^3（3x3x3立方体）的情况

我手动统计出的结果如下（按不同步数组合分类）：

• (0,0,0)：1个顶点
• 单维度走1步、其余0步（如(1,0,0)）：3个顶点
• 单维度走2步、其余0步（如(2,0,0)）：3个顶点
• 两个维度走1步、一个维度走0步（如(1,1,0)）：6个顶点
• 一个维度走1步、一个维度走2步、一个维度走0步（如(1,2,0)）：6个顶点
  总数加起来是27，和3^3的顶点数一致。

通用解法说明 #

其实这种结构叫做b维a阶超立方体（也可以理解为b维的a×a×…×a网格顶点集），对应的顶点数量分类可以用多项式系数来计算：

假设在b个维度中，有c₀个维度的步数是0，c₁个维度的步数是1，……，c_{a-1}个维度的步数是a-1，满足c₀ + c₁ + ... + c_{a-1} = b，那么这种步数组合对应的顶点数量为：

b! / (c₀! × c₁! × ... × c_{a-1}!)

这个公式的逻辑很简单：从b个维度里，选择c₀个维度设为0步，c₁个维度设为1步……最后剩下的c_{a-1}个维度设为a-1步，所有可能的选择方式的总数就是这个多项式系数。

验证例子：

• 对于2^3，当c₀=2、c₁=1时，数量是3!/(2!×1!)=3，正好对应单维度走1步的顶点数，和我们手动统计的一致。
• 对于3^3，当c₀=1、c₁=2、c₂=0时，数量是3!/(1!×2!×0!)=6，对应两个维度走1步、一个维度走0步的顶点数，和手动统计的结果匹配。

不管是2维、3维还是更高的b维，也不管a是2、3还是其他正整数，这个公式都适用。比如6维的2^6超立方体，三个维度走1步、三个维度走0步的顶点数量就是6!/(3!×3!)=20，总数加起来就是2^6=64，完全正确。

备注：内容来源于stack exchange，提问作者Thomas B.