生成函数

题解

普通生成函数：

常用于多重集组合问题。

物品$n$种，每种数量分别为$k_1,k_2,…,k_n$个，求从中可重复地选出$m$个物品的组合方法数。

设$f_k(x)=1+x+x^2+x^3+…+x^k$

则答案即为$\prod f_{k_i}(x)$的第$m$项$[x^m]$的系数。

若$k->∞$，则$f_k(x)=\frac 1 {1-x}$（现已加入多项式全家桶）

指数型生成函数：

常用于多重集排列问题。

物品$n$种，每种数量分别为$k_1,k_2,…,k_n$个，求从中可重复地选出$m$个物品的排列方法数。

设$f_k(x)=1+{\frac {x^1} {1!}}+{\frac {x^2} {2!}}+{\frac {x^3} {3!}}+…+{\frac {x^k} {k!}}$

则答案即为$\prod f_{k_i}(x)$的第$m$项$[\frac {x^m} {m!}]$的系数。

若$k->∞$，则$f_k(x)=e^x$（现已加入多项式全家桶）