考生物时闲得无聊推的qwq..
$$\left( \text{考生物时无聊推的}.. \right) \\\text{设}S_2\left( n,k \right) \text{表示把}n\text{个元素划分成}k\text{个集合的方案数}\\\text{则有}\\m^n=\sum_{0\le i\le m}{\left( \begin{array}{c} m\\ i\\\end{array} \right) S_2\left( n,i \right) i!}\\\text{解释：枚举不为空的集合的数量，乘上把}n\text{个元素划分成}i\text{个集合的方案数，再乘上集合的数量（因为集合有序）}\\\text{设}f\left( m \right) =m^n,g\left( i \right) =S_2\left( n,i \right) i!\\\text{则有}f\left( m \right) =\sum_{0\le i\le m}{\left( \begin{array}{c} m\\ i\\\end{array} \right) g\left( i \right)}\\\text{二项式反演可得}\\g\left( m \right) =\sum_{0\le i\le m}{\left( \begin{array}{c} m\\ i\\\end{array} \right) \left( -1 \right) ^{m-i}f\left( i \right)}\\\text{代入}\\S_2\left( n,m \right) \times m!=\sum_{0\le i\le m}{\left( \begin{array}{c} m\\ i\\\end{array} \right) \times \left( -1 \right) ^{m-i}\times i^n}\\\text{整理一下}\\S_2\left( n,m \right) =\frac{1}{m!}\sum_{0\le i\le m}{\left( \begin{array}{c} m\\ i\\\end{array} \right) \times \left( -1 \right) ^{m-i}\times i^n}\\\text{这是斯特林数的通项}\\\text{再整理一下，展开}\left( \begin{array}{c} m\\ i\\\end{array} \right) \\S_2\left( n,m \right) =\frac{1}{m!}\sum_{0\le i\le m}{\frac{m!}{i!\times \left( m-i \right) !}\times \left( -1 \right) ^{m-i}\times i^n}\\=\sum_{0\le i\le m}{\frac{i^n\times \left( -1 \right) ^{m-i}}{i!\times \left( m-i \right) !}}\\\text{然后发现这个式子可以卷积}…\\\text{设}A\left( x \right) =\sum_{0\le i\le m}{x^iS_2\left( n,i \right) =\sum_{0\le i\le m}{x^i\sum_{0\le j\le i}{\frac{j^n}{j!}\times \frac{\left( -1 \right) ^{i-j}}{\left( i-j \right) !}}}}\\\text{构造两个}m\text{次多项式}\\B\left( x \right) =\sum_{0\le i\le m}{\frac{i^n}{i!}x^i}\\C\left( x \right) =\sum_{0\le i\le m}{\frac{\left( -1 \right) ^i}{i!}x^i}\\B\left( x \right) C\left( x \right) \text{的}i\text{次项前的系数即为}S_2\left( n,i \right) $$
发表回复