从分糖果到组合恒等式：用动态规划和Python验证多项式系数

在算法面试中，我们经常会遇到类似"分糖果"这样的组合问题：假设有n颗不同的糖果要分给t个小朋友，其中第i个小朋友固定得到ni颗糖果（满足n1+n2+...+nt=n），问有多少种不同的分配方案？这个问题看似简单，却与组合数学中一个强大的工具——多项式系数密切相关。

1. 问题引入与动态规划解法

让我们从一个具体的例子开始：有5颗不同颜色的糖果（红、黄、蓝、绿、紫）要分给3个小朋友，分配数量分别为2、2、1。如何计算所有可能的分配方式？

1.1 直观理解问题

想象我们逐个分配糖果：

1. 从5颗中选2颗给第一个小朋友：C(5,2)=10种选择
2. 从剩下的3颗中选2颗给第二个小朋友：C(3,2)=3种选择
3. 最后1颗给第三个小朋友：C(1,1)=1种选择

根据乘法原理，总方案数为10×3×1=30种。这个计算过程可以抽象为：

总方案数 = C(n,n1) × C(n-n1,n2) × ... × C(n-n1-...-n(t-1),nt)

1.2 动态规划视角

我们可以用动态规划(DP)来建模这个问题。定义dp[i][j]表示前i个小朋友分配前j颗糖果的方案数。状态转移方程为：

dp[i][j] = sum(dp[i-1][j-k] * C(j,k) for k in range(ni_min, ni_max+1))

其中ni_min和ni_max是第i个小朋友可能获得的糖果数的最小和最大值。

对于固定分配数量n1,n2,...,nt的情况，递推关系简化为：

dp[i][j] = dp[i-1][j-ni] * C(j,ni)

1.3 多项式系数的出现

有趣的是，这个DP解法最终会收敛到多项式系数的表达式：

方案总数 = n! / (n1! × n2! × ... × nt!)

这正是多项式系数(n choose n1,n2,...,nt)的定义。它同时表示：

• 多重集的全排列数
• 多项式展开中项的系数
• 不同球放入不同盒子的方案数

2. 多项式系数的递推关系

2.1 递推式的发现

通过观察分糖果问题的DP解法，我们可以发现多项式系数满足以下递推关系：

(n choose n1,n2,...,nt) = 
  (n-1 choose n1-1,n2,...,nt) +
  (n-1 choose n1,n2-1,...,nt) +
  ... +
  (n-1 choose n1,n2,...,nt-1)

这个关系的组合意义很直观：固定某颗特定糖果的归属，考虑它分给每个小朋友的情况，然后将这些子问题相加。

2.2 与二项式系数的类比

当t=2时，多项式系数退化为二项式系数，递推关系变为：

C(n,k) = C(n-1,k-1) + C(n-1,k)

这正是帕斯卡三角形中的经典递推关系。因此，多项式系数的递推可以看作是二项式系数递推的多维推广。

2.3 递推关系的证明

我们可以用组合意义直接证明这个递推关系：

1. 选定一颗特定的糖果（比如红色那颗）
2. 如果它分给第一个小朋友，剩下n-1颗糖果需要分给小朋友，其中第一个小朋友还差n1-1颗
3. 同理，如果它分给第二个小朋友，第一个小朋友仍需n1颗，第二个差n2-1颗
4. 将所有可能性相加即得总方案数

3. Python实现与验证

3.1 递归实现递推关系

我们可以直接用Python实现这个递推关系：

from math import factorial
from functools import lru_cache

def multinomial(n, *ks):
    if any(k < 0 for k in ks):
        return 0
    if sum(ks) != n:
        return 0
    if n == 0:  # 所有k都为0
        return 1
    # 递推关系实现
    total = 0
    for i in range(len(ks)):
        if ks[i] == 0:
            continue
        new_ks = list(ks)
        new_ks[i] -= 1
        total += multinomial(n-1, *new_ks)
    return total

3.2 阶乘公式实现

作为对比，我们也可以用阶乘公式直接计算：

def multinomial_direct(n, *ks):
    if sum(ks) != n:
        return 0
    numerator = factorial(n)
    denominator = 1
    for k in ks:
        denominator *= factorial(k)
    return numerator // denominator

3.3 验证恒等式

我们可以验证递推关系与直接计算的结果是否一致：

def test_multinomial():
    test_cases = [
        (5, [2, 2, 1]),
        (7, [3, 2, 2]),
        (4, [1, 1, 1, 1]),
        (6, [3, 3]),
        (0, [0, 0, 0])
    ]
    
    for n, ks in test_cases:
        recursive = multinomial(n, *ks)
        direct = multinomial_direct(n, *ks)
        assert recursive == direct, f"Failed for n={n}, ks={ks}: {recursive} != {direct}"
    print("All tests passed!")

test_multinomial()

4. 应用与扩展

4.1 实际应用场景

多项式系数在多个领域有重要应用：

• 概率论 ：多项分布的概率计算
• 统计学 ：列联表分析
• 计算机科学 ：负载均衡问题
• 自然语言处理 ：n-gram语言模型

4.2 性能优化

对于大规模计算，我们可以使用动态规划加上记忆化来优化递归实现：

from functools import lru_cache

@lru_cache(maxsize=None)
def multinomial_memo(n, *ks):
    ks = tuple(sorted(ks))  # 标准化参数以增加缓存命中率
    if sum(ks) != n:
        return 0
    if n == 0:
        return 1
    total = 0
    for i in range(len(ks)):
        if ks[i] == 0:
            continue
        new_ks = list(ks)
        new_ks[i] -= 1
        total += multinomial_memo(n-1, *new_ks)
    return total

4.3 生成函数视角

从生成函数角度看，多项式系数是展开(x1 + x2 + ... + xt)^n时x1^n1 x2^n2 ... xt^nt项的系数。这解释了为什么它同时表示分配方案数：

from sympy import expand, symbols

def show_generating_function(t, n):
    x = symbols(f'x1:{t+1}')
    expr = sum(x[i] for i in range(1, t+1))**n
    expanded = expand(expr)
    print(f"Generating function for t={t}, n={n}:")
    print(expanded)

show_generating_function(3, 4)

5. 常见误区与注意事项

5.1 边界条件处理

实现时需要注意几种边界情况：

• 所有ni都为0时（只有当n=0时才有效）
• 某些ni为负数时（应立即返回0）
• 总和Σni ≠ n时（方案数为0）

5.2 计算效率比较

对于不同的参数规模，各种实现方法的效率不同：

• 小规模（n<20）：递归实现足够
• 中等规模（20≤n<100）：记忆化递归
• 大规模（n≥100）：阶乘公式配合对数计算避免溢出

5.3 数值稳定性

直接计算阶乘时，大数的阶乘可能导致整数溢出。可以采用对数空间计算：

from math import log10, exp

def log_multinomial(n, *ks):
    if sum(ks) != n:
        return float('-inf')
    total = 0.0
    # 计算log(n!)
    for i in range(1, n+1):
        total += log10(i)
    # 减去log(ks[i]!)
    for k in ks:
        term = 0.0
        for i in range(1, k+1):
            term += log10(i)
        total -= term
    return total

在实际项目中，我发现对于n>1000的情况，对数计算方法既能避免溢出，又能保持足够的精度。而递归实现在n=30左右就会开始变慢，这时记忆化技术就变得非常必要。