来去处

· · 算法·理论

给定 a_i，令：

1 &i=j=0\\ 0 &i=0,j\neq 0\\ f_{i-1,j-1}+(a_i+j)f_{i-1,j} & \mathrm{otherwise.} \end{cases}

求证：

\sum_{i=0}^n f_{n,i}x^{\underline{i}}=\prod_{i=1}^n (x+a_i)

::::info[役群兽] 考虑以下问题：给 n 个小球染色，每个小球可以染 x 种通用颜色或是 a_i 种特有颜色。显然总染色方案数等于右式。

考察将前 i 个小球染色，其中通用颜色使用了 j 种的方案数，我们可以说明其等于 f_{i,j}：

最后考虑这些等价类具体对应 x 个通用颜色中的哪些，对应系数为 x^{\underline{i}}. 故方案数也等于左式。 :::: ::::info[定本源]

\sum_{i=0}^0 f_{0,i}x^{\underline{i}}=1 &=\sum_{i=0}^n (i+a_n)f_{n-1,i}x^{\underline{i}}+(x-i+1)f_{n-1,i-1}x^{\underline{i-1}}\\ &=\sum_{i=0}^{n-1} (x-i+i+a_n)f_{n-1,i}x^{\underline{i}}\\ &=(x+a_i)\sum_{i=0}^{n-1}f_{n-1,i}x^{\underline{i}}\\ \end{aligned}

::::