生成函数：

也称为母函数，是一种形式幂级数。

一般生成函数OGF：

数列 $\{a_i\}$ 对应的一般生成函数为： $$ A(x)=\sum_{i\geqslant 0}a_ix^i $$ 生成函数可以有无穷项，一般在用生成函数作为组合计数的工具时不需要考虑其是否收敛。

一些常见的OGF：

| 数列 | OGF | 通项公式 | | :-------------------------------------------------------- | :---------------------- | ---------------------- | | $1,0,0,0,0,0,0\dots$ | $1$ | $a_i=[i=1]$ | | $0,\dots,0,1,0,0,\dots$ | $x^k$ | $a_i=[i=k]$ | | $1,1,1,1,1,1,1,\dots$ | $\frac 1{1-x}$ | $a_i=1$ | | $1,2,3,4,5,6,7$ | $\frac{1}{(1-x)^2}$ | $a_i=i$ | | $1,k,k^2,k^3,\dots$ | $\frac 1{1-kx}$ | $a_i=k^i$ | | $1,-1,1,-1,1,-1,1,\dots$ | $\frac 1{1+x}$ | $a_i=(-1)^i$ | | $1,0,\dots,0,1,0,\dots,$ | $\frac 1{1-x^k}$ | $a_i=[i=kp],p\in N$ | | $\binom n0,\binom n1,\binom n2,\binom n3,\binom n4,\dots$ | $(1+x)^n$ | $a_i=\binom n i$ | | $1,1,\dots,1,0,0,0\dots$ | $\frac{1-x^{k+1}}{1-x}$ | $a_i=[i\leqslant k]$ | | $1,\binom c 1,\binom {c+1} 2,\binom {c+2} 3,\dots$ | $\frac 1{(1-x)^c}$ | $a_i=\binom{c+i-1}{i}$ | | $1,\binom{m+1}m,\binom{m+2}m,\binom{m+3}m,\dots$ | $\frac 1{(1-x)^{m+1}}$ | $a_i=\binom{m+i}m$ |

一些不常见的OGF：

数列	OGF	通项公式
$0,1,\frac 1 2,\frac 1 3,\dots$	$-\ln(1-x)$或$\ln{\frac 1{1-x}}$	$a_i=\frac 1 i$
$0,1,-\frac 1 2,\frac 1 3,-\frac 1 4,\dots$	$\ln(1+x)$	$a_i=(-1)^{i+1}\frac 1 i$
$1,1,\frac 1 2,\frac 1 6,\frac 1{24},\dots$	$e^x$	$a_i=\frac 1{i!}$

一些OGF的运算：

$$ \begin{align} \alpha F(x)+\beta G(x)&=\sum_{i\geqslant 0}(\alpha f_i+\beta g_i)x^i&线性变换\\ x^mF(x)&=\sum_{i\geqslant m}f_{i-m}x^i&右移\\ \frac{F(x)-\sum_{i=0}^{m-1}f_ix^i}{x^m}&=\sum_{i\geqslant 0}f_{i+m}x^i&左移\\ F(cx)&=\sum_{i\geqslant 0}f_ic^ix_i&乘常数幂\\ F'(x)&=\sum_{i\geqslant 0}(i+1)f_{i+1}x^i&求导\\ xF'(x)&=\sum_{i\geqslant 0}if_ix^i&乘i\\ \int^x_0G(t)dt&=\sum_{i\geqslant 1}\frac 1 if_{i-1}x^i&积分\\ F(x)G(x)&=\sum_{i\geqslant 0}(\sum_{j=0}^if_jg_{i-j})x^i&卷积\\ \frac 1{1-x}F(x)&=\sum_{i\geqslant 0}(\sum_{j=0}^if_j)x^i&前缀和\\ \frac{G(x)+G(-x)}2&=\sum_{i\geqslant 0}[i是偶数]g_ix^i&提取偶数项\\ \frac{G(x)-G(-x)}2&=\sum_{i\geqslant 0}[i是奇数]g_ix^i&提取奇数项 \end{align} $$

一些使用OGF的例子：

斐波那契数：

$$ f(n)= \begin{cases} 1,&n=1\\ f(n-1)+f(n-2),&n>1 \end{cases} $$

那么我们可以得到一个更一般的递推式： $f(n)=f(n-1)+f(n-2)+[n=1]$ 。

设 $f(n)$ 的生成函数为 $F(x)$ ，那么有： $$ \begin{align} F(x)&=\sum_{i\geqslant 0}f_ix^i\\ &=\sum_{i\geqslant 1}f_{i-1}x^i+\sum_{i\geqslant 2}f_{i-2}x_i+x\\ &=xF(x)+x^2F(x)+x \end{align} $$ 可以解得： $$ F(x)=\frac x{1-x-x^2} $$ 这样我们就得到了斐波那契数的生成函数。

然后运用高中数学知识，我们可以裂项： $$ \begin{align} F(x)&=\frac x{(\frac{1+\sqrt5}2-x)(\frac{1-\sqrt 5}2-x)}\\ &=\frac 1{\sqrt 5}\frac {(1-\frac{1+\sqrt5}2x)-(1-\frac{1-\sqrt 5}2x)}{(1-\frac{1+\sqrt5}2x)(1-\frac{1-\sqrt 5}2x)}\\ &=\frac 1{\sqrt 5}(\frac 1{1-\frac{1+\sqrt 5}2x}-\frac 1{1-\frac{1-\sqrt 5}2x})\\ \end{align} $$ 设 $a=\frac{1+\sqrt 5}2,b=\frac{1-\sqrt 5}2$ ，根据 $\frac 1{1-cx}=\sum_i c^ix^i$ 可得： $$ F(x)=\frac1{\sqrt5}(\sum_{i\geqslant 0}a^i+\sum_{i\geqslant 0}b^i)x^i $$ 于是我们就得到了斐波那契数的封闭形式： $f_i=\frac1{\sqrt5}(a^i+b^i)$ 。

施罗德数：

又称超级卡特兰数，表示从 $(0,0)$ 走到 $(n,n)$ 只能向上，向右或者向右上走，不能越过直线 $y=x$ 的方案数，一个比较容易理解的卷积递推式为： $$ f_i=f_{i-1}+\sum_{k=0}^{i-1}f_{k}\times f_{i-1-k}+[i=0] $$ 前边那一项意为上一次从 $(n-1,n-1)$ 走过来，后面那一项意为从 $(n,n-1)$ 走过来，后面那一项实际上枚举的是在哪一步最后一次走到直线 $y=x$ 上，那他下一步一定只能向右走，于是走到 $(n,n-1)$ 又是一个施罗德数。

这个显然可以用分治 $+FFT$ 来 $O(n\log n)$ 的计算，但是这样还不够优秀。

考虑施罗德数的生成函数： $$ \begin{align} F(x)&=\sum_{i\geqslant 0}(f_ix^i)\\ &=\sum_{i>0}f_{i-1}x^i+\sum_{i>0}(\sum_{k=0}^{i-1}f_k\times f_{i-1-k})x^i+1\\ &=x\sum_{i\geqslant0}f_ix^i+x\sum_{i\geqslant 0}(\sum_{k=0}^if_k\times f_{i-k})x^i+1\\ &=xF(x)+xF(x)^2+1 \end{align} $$

我们可以得到施罗德数的生成函数为 $F(x)=\frac{1-x+\sqrt{1-6x+x^2}}{2x}$ ，虽然这个生成函数对于求解没有什么用。

设 $G(x)=\sqrt{1-6x+x^2}$ ，先考虑怎么求 $G(x)$ ，首先考虑如何处理 $A(x)=B(x)^k$ ，两边求导可得： $$ \begin{align} A(x)&=B(x)^k\\ A'(x)&=kB(x)^{k-1}B'(x)\\ A'(x)B(x)&=kB(x)^kB'(x)\\ A'(x)B(x)&=kA(x)B'(x)\\ \end{align} $$ 于是： $$ \begin{align} G(x)&=(1-6x+x^2)^{\frac 1 2}\\ G'(x)(1-6x+x^2)&=\frac 1 2G(x)(2x-6)\\ G'(x)(1-6x+x^2)&=G(x)(x-3)\\ \sum_{i\geqslant 0}(i+1)g_{i+1}x^i-6\sum_{i\geqslant 0}ig_ix^i+\sum_{i\geqslant0}(i-1)g_{i-1}x^i&=\sum_{i\geqslant0}g_{i-1}x^i-3\sum_{i\geqslant 0}g_ix^i\\ \sum_{i\geqslant 0}\biggl((i+1)g_{i+1}-6ig_i+(i-1)g_{i-1}-g_{i-1}+3g_i\biggr)x^i&=0\\ (i+1)g_{i+1}-6ig_i+(i-1)g_{i-1}-g_{i-1}+3g_i&=0 \end{align} $$ 于是我们可以列出一些方程： $$ \begin{align} &g_0=G(0)=1\\ &(0+1)g_{0+1}-6\times0\times g_0+(0-1)g_{0-1}-g_{0-1}+3g_0=0\\ &\Rightarrow g_1+3g_0=0\Rightarrow g_1=-3\\ &(1+1)g_{1+1}-6\times1\times g_1+(1-1)g_{1-1}-g_{1-1}+3g_1=0\\ &\Rightarrow 2g_2-6g_1-g_0+3g_1=0\Rightarrow g_2=-4 \end{align} $$ 其他情况： $$ ig_i+(9-6i)g_{i-1}+(i-3)g_{i-2}=0\Rightarrow g_i=\frac{(6i-9)g_{i-1}+(3-i)g_{i-2}}i $$ 由于 $2xF(x)=1-x+G(x)$ ，和上面一样我们也可以列出一些方程，具体操作就不展开了，最后可以得到： $$ f_i= \begin{cases} 1,&i=0\\ -\frac{g_{n+1}}2,&i>0 \end{cases} $$ 于是就可以 $O(n)$ 求了。

默慈金数：

默慈金数表示在一个 $n$ 个点的圆上画出彼此不相交的弦的方案数，或者从 $(0,0)$ 走到 $(n,0)$ 每次只能走 $(1,0),(1,-1),(1,1)$ 并且不能走到 $y=0$ 之下的方案数。

一个卷积递推公式为： $$ f_i=f_{i-1}+\sum_{k=0}^{i-2}f_kf_{i-2-k} $$ 大概原因就是尝试往一个圆中新加一个点，前一项就是这个点不往外连边的方案数，后一项就是枚举他和谁连边，显然分开后两边还是一个默慈金数，但是注意上界是 $i-2$ 。

还是用刚才的方法，构造出一个关于生成函数的方程，然后把根式拿出来特殊处理，然后得出一个 $G$ 的递推式最后可以得到： $$ \begin{align} g_n&=\frac{(2n-3)g_{n-1}+(3n-9)g_{n-2}}n\\ f_n&=-\frac{g_{n+2}}2 \end{align} $$

卡特兰数：

$$ f_n=\sum_{i=0}^{n-1}f_if_{n-1-i} $$

生成函数为： $$ F(x)=1+xF^2(x)\\ F(x)=\frac{1-\sqrt{1-4x}}{2x} $$ 我们可以 $\sqrt{1-4x}$ 应用广义二项式定理： $$ \sqrt{1-4x}=\sum_{i\geqslant 0}\binom{\frac 1 2}i(-4x)^i $$ 其中： $$ \binom{\frac12}i=\frac{\frac12(\frac12-1)\dots(\frac12-i+1)}{i!}=\frac{(-1)^{n-1}1\times 3\dots\times (2i-3)}{2^ii!}=\frac{(-1)^{i-1}(2i-2)!}{2^{2i-1}i!(i-1)!} $$ 也就是说： $$ \sqrt{1-4x}=-2\sum_{i\geqslant0}\frac{(2i-2)!}{i!(i-1)!}x^i\\ \Rightarrow F(x)=\frac{1-\sqrt{1-4x}}{2x}=\sum_{i\geqslant0}\frac{(2i)!}{(i+1)!i!}x^i $$ 显然是卡特兰数生成函数。

背包计数问题：

有一些物品，每种物品满足选取的个数满足某种条件或者体积不同，求共选取了 $n$ 个物品或总体积为 $n$ 的方案数。

列出每种物品的关于个数/体积的生成函数，然后把所有生成函数乘起来即可。

指数生成函数EGF：

数列 $\{a_i\}$ 对应的生成函数为： $$ A(x)=\sum_{i\geqslant 0}\frac{a_i}{i!}x^i $$

一些常见的EGF：

数列	EGF	通项公式
$1,1,1,1,1,\dots$	$e^x$	$a_i=1$
$0,1,2,3,\dots$	$xe^x$	$a_i=i$
$1,c,c^2,c^3,\dots$	$e^{cx}$	$a_i=x^i$

EGF的运算：

$$ \begin{align} \alpha A(x)+\beta B(x)&=\sum_{i\geqslant 0}(\alpha a_i+\beta b_i)\frac{x^i}{i!}&线性变换\\ x^mF(x)&=\sum_{i\geqslant 0}[i\geqslant m]n^{\underline m}f_{i-m}\frac{x^i}{i!}\\ \frac{F(x)-\sum_{i=0}^{m-1}f_ix^i}{x^m}&=\sum_{i\geqslant 0}\frac1{(n+m)^{\underline m}}f_{n+m}\frac{x^n}{n!}\\ F(cx)&=\sum_{i\geqslant 0}c^if_i\frac{x^i}{i!}&乘常数幂\\ F'(x)&=\sum_{i\geqslant 0}f_{n+1}\frac{x^n}{x!}&求导/左移\\ \int_0^xF(t)\text dt&=\sum_{i>0}f_{n-1}\frac{x^n}{n!}&积分/右移\\ F(x)G(x)&=\sum_{i\geqslant 0}\sum_{j=0}^i\Bigl(\binom ijf_ig_{i-j}\Bigr)\frac{x^n}{n!}&二项卷积 \end{align} $$

一些使用EGF的例子：

一个常见操作：一个集合 $S$ 是由组合对象 $A$ 组成的，那么由于集合的元素间是无序的，因此 $$ S=\sum_{i\geqslant0}\frac{A^i}{i!}=e^A $$

贝尔数：

贝尔数 $B(n)$ ，把大小为 $n$ 的集合划分成若干非空不相交子集的方案数。

枚举第一个元素所在的自己大小 $i$ ，可以得到： $$ B(n)=[n=0]+\sum_{i=1}^n\binom{n-1}{i-1}B(n-i) $$ 于是有： $$ F(x)=1+\int_0^xe^tF(t)\text dt $$ 两边求导： $$ \begin{align} F'(x)&=e^xF(x)\\ \frac{\text dF}{\text dx}&=e^xF(x)\\ \frac{\text dF}F&=e^x\text dx\\ \int\frac{\text dF}F&=\int e^x\text dx=e^x+C\\ \because&\ \text d(\ln x)=\frac{\text dx}x\\ \therefore&\ \ln(F)=e^x+C\\ F&=e^{e^x+C}\\ 把F(0)&=1代入得：\\ F(x)&=e^{e^x-1} \end{align} $$ 这个也可以这样理解： $g(x)=e^x-1$ 表示的是 $n$ 个数分成一个集合的方案数，因为 $a_i=[i\ne0]$ ，那么 $g^c(x)$ 就是划分成 $c$ 个集合的生成函数，由于 $c$ 个集合互不区分因此还要乘上 $\frac1{i!}$ ，那么有： $$ B(x)=\sum_{i\geqslant 0}\frac{g^i(x)}{i!}=e^{e^x-1} $$

EGF与无向图/无向连通图：

设 $G(x)$ 是简单无向图的 $EGF$ ，我们可以枚举每条边存不存在： $$ G(x)=\sum_{i\geqslant 0}2^{\binom i2}\frac{x^i}{i!} $$ 设 $C$ 是简单无向连通图的 $EGF$ ，假如说他的生成函数是： $$ C(x)=\sum_{i\geqslant 1}c_n\frac{x^n}{n!} $$ 我们可以枚举联通块的个数， $k$ 个联通块的简单无向连通图的生成函数是 $\frac{C(x)^k}{k!}$ ，

那么有： $$ G(x)=\sum_{i\geqslant 0}\frac{C(x)^k}{k!}=e^{C(x)} $$ 那么： $$ C(x)=\ln G(x) $$ 于是就可以求 $C$ 了。

EGF与置换：

$k-$ 轮换的数量有 $(k-1)!$ 个，因此所有轮换的 $EGF$ 为： $$ F(x)=\sum_{i\geqslant 0}\frac{(k-1)!}{k!}x^k=\sum_{i\geqslant 0}\frac{x^k}k=\ln(\frac1{1-x}) $$ 仿照上例，所有置换的 $EGF$ 为： $$ G(x)=\sum_{i\geqslant 0}\frac{F(x)^i}{i!}=e^{F(x)}=e^{\ln(\frac1{1-x})}=\frac1{1-x}=\{1,1,1,1,\dots\} $$ 因此： $g_i=i!$ （显然）。

EGF与背包：

有 $\sum a_i$ 种物品，其中体积为 $i$ 的物品有 $a_i$ 种，每种物品有无限个，求背包方案数： $$ \begin{align} \prod_{i=1}^n(1+x^i+x^{2i}+\cdots)^{a_i}&=\prod_{i=1}^n(\frac{1}{1-x^i})^{a_i}\\ &=\exp\Bigl(\sum_{i=1}^na_i\ln(\frac1{1-x^i})\Bigr)\\ &=\exp\Bigl(\sum_{i=1}^na_i\sum_{j\geqslant 0}\frac{x^{ij}}j\Bigr) \end{align} $$ 对于每一个 $i$ ，后面那部分只有 $n/j$ 项是有用的，于是可以 $O(n\log n)$ 求，加上前面的 $\exp$ 还是 $O(n\log n)$ 。

伯努利数：

伯努利数是自然数幂和转为多项式的一部分系数，具体来说，设： $$ S_m(n)=1^m+2^m+\cdots+n^m $$ 那么有： $$ S_m(n)=\frac1{m+1}\sum_{k=0}^m(-1)^k\binom{m+1}kB_kn^{m+1-k} $$ 伯努利数满足： $$ \sum_{k=0}^m\binom{m+1}kB_k=[m=0] $$ 也就是说： $$ B_m=\frac{[m=0]-\sum_{k=0}^{m-1}\binom{m+1}kB_k}{m+1} $$ 如果我们能预处理出伯努利数，就可以在 $O(k)$ 的时间复杂度内求某一个次幂的自然数幂和。

伯努利数的EGF为： $$ \frac{x}{e^x-1}=\sum_{i\geqslant 0}B_i\frac{x^i}{i!} $$ 证明的话： $$ \begin{align} B(x)\times \frac{e^x-1}x&=\frac{\sum_{i\geqslant 0}B_i\frac{x^i}{i!}\times \sum_{i>0}\frac{x^i}{i!}}x\\ &=\frac{\sum_{i\geqslant 0}(\sum_{j=0}^{i-1}\binom ijB_j)\frac{x^i}{i!}}x\\ &=\frac{\sum_{i\geqslant 1}(\sum_{j=0}^{i-1}\binom ijB_j)\frac{x^i}{i!}}x\\ &=\sum_{i\geqslant 1}(\sum_{j=0}^{i-1}\binom ijB_j)\frac{x^{i-1}}{i!}\\ &=\sum_{i\geqslant 0}(\sum_{j=0}^i\binom {i+1}jB_j)\frac{x^i}{(i+1)!}\\ &=\sum_{i\geqslant 0}(\sum_{j=0}^i\binom {i+1}jB_j)\frac{x^i}{(i+1)!}\\ &=\sum_{i\geqslant 0}(\frac{[i=0]}{i+1})\frac{x^i}{i!}\\ &=1 \end{align} $$ 因此伯努利数可以用多项式求逆来 $O(n\log n)$ 预处理。

一个更加简洁的 $O(n^2)$ 递推式为： $$ B_n+[n=1]=\sum_{k=0}^n\binom nkB_k $$ 考虑一个更加奇怪的生成函数： $$ \begin{align} S(x,n)&=\sum_{i\geqslant 0}S_i(n)\frac{x^i}{i!}\\ &=\sum_{i\geqslant 0}(\sum_{j=1}^nj^i)\frac{x^i}{i!}\\ &=\sum_{j=1}^n(\sum_{i\geqslant 0}j^i\frac{x^i}{i!})\\ &=\sum_{j=1}^ne^{jx} \end{align} $$ 故： $$ S(x,n)=\frac{e^{nx}-1}{e^x-1} $$ 更加一般的公式是： $$ S_{m-1}(n)=\frac1m(B_m(n)-B_m(0)) $$ 其中： $$ B_m(k)=\sum_{i=0}^m\binom miB_ik^{m-i} $$ 也就是： $$ [x^m](B(x)\times e^{kx}) $$ 关于伯努利数的 $O(n\log n)$ 预处理：

首先我们知道： $$ \sum_{i\geqslant 0}B_i\frac{x^i}{i!}=\frac x{e^x-1} $$ 我们还知道： $$ e^x=\sum_{i\geqslant 0}\frac{x^i}{i!} $$ 那么我们要计算的就是： $$ \frac x{\sum_{i\geqslant 0}\frac{x^i}{i!}-1}=\frac x{\sum_{i\geqslant 1}\frac{x^i}{i!}-1} $$ 会发现分母 $[x^0]f(x)=0$ 求不了逆，于是我们上下同时除掉一个 $x$ ： $$ \frac1{\sum_{i\geqslant 0}\frac{x^i}{(i+1)!}} $$ 这样就可以求逆预处理了。

广义指数函数

完全图的生成树个数是 $n^{n-2}$ ，虽然说如果用 $prufer$ 序列的话这个结论非常显然，但是我们还是尝试用EGF解决它。

先设 $n$ 个点的无向完全图有 $t_n$ 棵生成树，生成函数为 $T(x)$ ，根据以往的经验我们考虑给一个 $n-1$ 个点的图新加一个点，假设原来有 $m$ 棵树，若每个树有 $p_i$ 个点，那么可以得到一个递推式： $$ \begin{align} t_n&=\sum_{m>0}\frac1{m!}\sum_{p_1+p_2+\cdots+p_m=n-1}\binom{n-1}{p_1,p_2,\dots,p_m}\prod_{i=1}^m(p_i\times t_{p_i})\\ \frac{t_n}{(n-1)!}&=\sum_{m>0}\frac1{m!}\sum_{p_1+p_2+\cdots+p_m=n-1}\prod_{i=1}^m(\frac{p_i\times t_i}{p_i!})\\ 设g_n&=nt_n\\ \frac{g_n}{n!}&=\sum_{m>0}\frac1{m!}\sum_{p_1+p_2+\cdots+p_m=n-1}\prod_{i=1}^m\frac{g_i}{p_i!}\\ \frac{g_n}{n!}&=\sum_{m>0}\frac1{m!}[x^{n-1}]G(x)^m\\ G(x)&=\sum_{n\geqslant 1}\sum_{m>0}\frac{[x^{n-1}]G(x)^m}{m!}\\ G(x)&=\sum_{n\geqslant 0}\sum_{m>0}\frac{x[x^n]G(x)^m}{m!}\\ G(x)&=xe^{G(x)} \end{align} $$ 为了求解这个问题，我们还要引入一个前置知识：广义指数级数 $\mathcal E_t(x)​$ 。 $$ \mathcal E_t(x)=\sum_{k\geqslant0}(tk+1)^{k-1}\frac{x^k}{k!} $$ 他满足： $$ \begin{align} &\mathcal E_t(x)^{-t}\ln\mathcal E_t(x)=x\\ &\mathcal E_0(x)=e^x\\ &\mathcal E_t(x)^r=\sum_{i\geqslant 0}r\frac{(tk+r)^{k-1}}{k!}x^k\\ &\frac{\mathcal E_t(x)^r}{1-xt\mathcal E_t(x)^t}=\sum_{i\geqslant 0}\frac{(tk+r)^k}{k!}x^k\\ &\mathcal E_1(x)=e^{x\mathcal E_1(x)} \end{align} $$ 观察最后一个式子就可以发现 $G(x)=x\mathcal E_1(x)$ 。

而我们知道： $$ \mathcal E_1(x)=\sum_{i\geqslant 0}\frac{(n+1)^{n-1}}{n!}x^n $$ 于是 $t_n=\frac{g_n}n=\frac1n\times n\times n^{n-2}=n^{n-2}$ 。

生成函数形Polya定理：

回到那个经典的例子：一个 $2\times 2$ 的网格，旋转同构算一种，问有多少种本质不同的黑白染色的方案。

根据polya定理 $ans=\frac1{|G|}[m^{c(a_1)}+m^{c(a_2)}+\cdots+m^{c(a_g)}]$ ，不难得到 $ans=\frac14[2^2+2^1+2^4+2^1]=6$ 。

但是这样只能得到方案数而不能得到具体的方案，因此我们可以引入母函数形Polya定理： $$ F(m_1,m_2,\dots,m_p)=\frac1{|G|}[\sum_{g=1}^{|G|}\prod_i(m_1^i+m_2^i+\cdots+m_p^i)^{cnt_g[i]}] $$ 其中 $cnt_g[i]$ 表示置换 $g$ 中长度为 $i$ 的循环节个数，还用那个例子： $$ \begin{align} F(b,w)&=\frac14[(b^2+w^2)^2+(b^4+w^4)^1+(b^2+w^2)^2+(b+w)^4]\\ &=b^4+b^3w+2b^2w^2+bw^3+w^4 \end{align} $$ 也就是说的 $6$ 种方案中有 $1$ 种全是黑色，一种有三个黑色，两种有两个黑色，一种有一个黑色，一种没有黑色。

概率生成函数：

把普通生成函数每一项的系数改为某一离散随机变量取值为 $i$ 的概率，用公式表达就是： $$ A(x)=\sum_{i\geqslant 0}P(x=i)x^i $$

性质1：

$$ A(1)=\sum_{i\geqslant 0}P(x=i)=1 $$

性质2：

$$ 随机变量取值的期望E(x)=F'(1)=\sum_{i\geqslant 0}iP(x=i) $$

性质3

$$ 随机变量的取值方差V(x)=F''(1)+F'(1)-(F'(1))^2 $$

卷积运算的含义是前后两部分都是概率。