来去处

· · 算法·理论

给定 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
$$\begin{aligned} \sum{i=0}^n f{n,i}x^{\underline{i}}&=\sum_{i=0}^n ((i+an)f{n-1,i}+f_{n-1,i-1})x^{\underline{i}} \
&=\sum_{i=0}^n (i+an)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+an)f{n-1,i}x^{\underline{i}}\
&=(x+ai)\sum{i=0}^{n-1}f_{n-1,i}x^{\underline{i}}\
\end{aligned}$$
::::