关于计算特定码字子集大小的技术咨询

咱们来一步步拆解这个问题，先把核心逻辑理清楚：

首先明确已知条件：

• 自然数$q$，$n=2^{q$（所以$n/2=2}{q-1}$是整数，保证汉明距离$n/2$是合法的）；
• $V_i$是所有与$w_i$汉明距离恰好为$n/2$的0-1向量集合；
• $w_0$是全0向量，$w_1$是交替0/1的向量，$w_2$是每两位00/11交替的向量，以此类推，直到$w_q$是前$n/2$位0、后$n/2$位1的向量。

分情况推导 #

情况1：$i=0$（$w_0$是全0向量） #

对于全0向量$w_0$，汉明距离$d_H(v,w_0)$其实就是向量$v$中1的个数（因为只有$v$取1的位才和$w_0$不同）。我们要找所有恰好有$n/2$个1的0-1向量，这个数量就是标准的组合数：
|V_0| = \binom{2^q}{2^{q-1}}

情况2：$1 \leq i \leq q$（$w_i$包含$n/2$个0和$n/2$个1） #

先观察$w_i$的结构：不管是交替01、每两位分组交替，还是最后分成两半的$w_q$，因为$n$是2的幂，$w_i$里的0和1的数量一定是相等的——各占$n/2$个。

现在计算$V_i$的大小：我们需要找向量$v$，使得$v$与$w_i$不同的位数恰好是$n/2$。设$x$是$v$在$w_i$的0位上取1的数量（这部分是不同的位），$y$是$v$在$w_i$的1位上取0的数量（这部分也是不同的位），那么$x + y = n/2$。

$V_i$的大小就是所有满足$x+y=n/2$的组合数乘积之和：
sum_{x=0}^{n/2} \binom{n/2}{x} \times \binom{n/2}{n/2 - x}

根据范德蒙德卷积定理，这个求和式的结果等于从$2 \times (n/2)=n$个元素中选$n/2$个的组合数，也就是：
|V_i| = \binom{2^q}{2^{q-1}}

统一结论 #

不管$i$是0到$q$中的哪一个，$V_i$的大小都是相同的，等于从$2^{q$个元素中选$2}{q-1}$个的组合数：
|V_i| = \binom{2^q}{2^{q-1}}

小例子验证 #

• 当$q=1$，$n=2$：$\binom{2}{1}=2$。$V_0$是{(0,1),(1,0)}，$V_1$是{(0,0),(1,1)}，大小都是2，符合结果。
• 当$q=2$，$n=4$：$\binom{4}{2}=6$。$V_0$是所有重量为2的0-1向量（共6个），$V_1$是与(0,1,0,1)距离为2的向量（比如(0,0,1,1)、(0,1,1,0)等，共6个），完全匹配。

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