无限球放入t个单元格：满单元格偶、空单元格奇的计数问题

这题用组合计数+生成函数的思路来解会非常清晰，比硬怼双重求和舒服多了。我给你一步步拆解：

1. 定义状态变量 #

每个单元格只有三种可能状态：

• 空（0个球）：设数量为$a$，要求$a$是奇数
• 半满（1个球）：数量为$c$，无奇偶限制
• 满（2个球）：数量为$b$，要求$b$是偶数

根据单元格总数$t$，必然满足$a + b + c = t$，因此$c = t - a - b$。

2. 写出初始的求和表达式 #

对于给定的$a$（奇数）和$b$（偶数），放法数的计算逻辑是：先从$t$个单元格里选$a$个空的，再从剩下的$t-a$个里选$b$个满的，剩下的自动成为半满单元格。对应的组合数是$\binom{t}{a} \times \binom{t-a}{b}$。

我们需要对所有符合条件的$a,b$求和，初始表达式为：
$$
N = \sum_{\substack{a \text{ 奇数} \ b \text{ 偶数} \ a + b \leq t}} \binom{t}{a} \binom{t-a}{b}
$$

3. 用奇偶特征函数简化求和 #

直接计算双重求和太繁琐，我们可以用奇偶特征函数来精准筛选符合条件的项：

• 筛选$a$为奇数：用$\frac{1 - (-1)^a}{2}$（当$a$为奇数时等于1，偶数时等于0）
• 筛选$b$为偶数：用$\frac{1 + (-1)^b}{2}$（当$b$为偶数时等于1，奇数时等于0）

把这两个特征函数代入求和式并展开，得到：
$$
N = \frac{1}{4} \sum_{a=0}^t \binom{t}{a} (1 - (-1)^a) \sum_{b=0}^{t-a} \binom{t-a}{b} (1 + (-1)^b)
$$

4. 计算内层求和 #

先处理内层的和$\sum_{b=0}^m \binom{m}{b}(1 + (-1)^b)$（令$m = t - a$）：

• 拆成两个独立的二项式求和：$\sum_{b=0}^m \binom{m}{b} + \sum_{b=0}^m \binom{m}{b}(-1)^b$
• 第一个和用二项式定理：$(1+1)^m = 2^m$
• 第二个和同样用二项式定理：$(1-1)^m = 0^{m$（注意：当$m=0$时$0}0=1$，否则为0）

因此内层和的结果是$2^m + 0^m$。

5. 计算外层求和并化简 #

把内层和的结果代入后，外层求和可以拆成两部分分别计算：

第一部分 #

$$
\sum_{a=0}^t \binom{t}{a}(1 - (-1)^a)2{t-a}
$$
拆成两个二项式求和：
$$
\sum_{a=0}^t \binom{t}{a}2^{t-a} - \sum_{a=0}^t \binom{t}{a}(-1)^a2{t-a}
$$
用二项式定理化简：
$$
(2+1)^t - (2-1)^t = 3^t - 1
$$

第二部分 #

$$
\sum_{a=0}^t \binom{t}{a}(1 - (-1)^a)0{t-a}
$$
只有当$t-a=0$（即$a=t$）时，$0^{t-a}=1$，其余项都是0，代入得：
$$
\binom{t}{t}(1 - (-1)^t) \times 1 = 1 - (-1)^t
$$

把两部分结果相加：
$$
(3^t - 1) + (1 - (-1)^t) = 3^t - (-1)^t
$$

最后乘以$\frac{1}{4}$，得到最终的放法数：
$$
N = \frac{3^t - (-1)^t}{4}
$$

验证小例子 #

我们用几个小的$t$值验证结果是否正确：

• $t=1$：$\frac{3 - (-1)}{4}=1$，正确（只有“空单元格”这1种符合条件的放法）
• $t=2$：$\frac{9 - 1}{4}=2$，正确（选1个空、1个半满，共2种放法）
• $t=3$：$\frac{27 + 1}{4}=7$，正确（3种“1空+2半满”、3种“1空+2满”、1种“3空”，总和7）

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