为 \(X\) 为仅取非负整数的随机变量，那么 \(X\) 的生成函数 \(F_X(x)=\sum_{k\geqslant 0}P_k x^k\)。
- \(F_X(1)=1\)。
证明：显然。注意反过来说若满足 \(F_X(1)=1\) 的生成函数都是某个随机变量的概率生成函数。
- \(E(X)=G'_X(1)\)，同理可以推出 \(E(x^\underline {a})=G^{(a)}_X(1)\)。所以有方差 \(D(X)=E(X^2)-E(X)^2=G'_X(1)+G''_X(1)-G'_X(1)^2\)。
证明：\(G'_X(1)=(\sum_{k\geqslant 0}P_kx^k)'=\sum_{k\geqslant 0}P_kx^{k-1}k=\sum_{k\geqslant 0}P_kk=E(X)\)。
- \(P(X+Y=n)=\sum_{k=0}^n PX_kPY_{n-k}\)，这是一个卷积，所以 \(F_{X+Y}=F_X*F_Y\)。
[CTSC2006]歌唱王国
一个想法是在 AC 自动机上跑矩阵乘法，但是 T 飞。而且也做不了。
然后你发现就是一个高斯消元，但是还是过不了。
令 \(F(x)\) 为刚好某天达成匹配的概率期望函数，\(G(x)\) 为某天还没达成匹配的概率期望函数。
\(F(x)+G(x)=xG(x)+1\)。（1）这个式子可以理解成新加一个元素的概率。
\(G(x)*(\frac 1 m x)^L=\sum_{i=1}^L a_i F(x)*(\frac 1 m x)^{L-i}\)。（2）注意 \(F(x)\) 是第一次达成匹配 就很好理解了。
将（1）求导并代入 \(x=1\)，得 \(F'(x)+G'(x)=xG'(x)+G(x)\Rightarrow F'(1)=G(1)\)。
将其代入（2）并令 \(x=1\)，得 \(G(1)*(\frac 1 m)^L=\sum_{i=1}^La_i F(1)*(\frac 1 m)^{L-i}=\sum_{i=1}^L a_i m^i\)。线性即可解决。