生成函数学习笔记[干货]

概论

生成函数算是一种既简单又有用的数学方法,一般用来解决组合技术问题,而且是一种最重要的一般性处理方法.

填完坑再划

主要参考资料:<组合数学引论(中科大)>

引论

对于一个有限数列或者无限数列

$$\{ a_0,a_1,a_2,... \}$$

我们用幂级数

$$A(x) = a_0+a_1x+a_2x^2+...\\\\ =\sum_{i=0}^{\infty}a_ix^i$$

来使之为一个整体，我们相当于用这样的一个我们自己构造出来的函数去研究整个函数的性质。 而不必单个地研究.特别地,我们把$A(x)$称为该序列的生成函数,记为$G{a_n }$.

对于特殊情况比如组合数列

$$\{ \binom{n}{0}\binom{n}{1},\cdot\cdot\cdot,\binom{n}{n}\}$$

根据上述的定义,令其生成函数为$f_n(x)$,则有

$$f_n(x)=\binom{n}{0}+\binom{n}{1}x+\cdot\cdot\cdot+\binom{n}{n}x^n$$

由二项式定理不难得到

$$f_n(x)=(1+x)^n$$

那么就可以对这个玩意进行单独研究了比如我们假设要求

​

$$\sum_{i=0}^n\binom{n}{i}$$

实际上就是$x=1$的情况.代入后就是$2^n$.

或者再比如求

$$\sum_{i=1}^ni\binom{n}{i}\\\\$$

hjq瞬间用组合意义秒掉.%%%%%

这个式子,相当于在$n$个球中选出$i$个并且给之中的一个染色的数量

那么先染一个再选择显然是等价的.所以就是下面的式子了.

用二项式的话用容斥原理不难得到

$$\sum_{i=1}^ni\binom{n}{i}\\\\ =n \times 2^{n-1}$$

由恒等式

$$(1+x)^{m+n}=(1+x)^m(1+x)^n\\\\ \longrightarrow\space\binom{m+n}{r} = \sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}$$

好了上面都是玩泥巴~~

例1

丢一个栗子

假设你有一个正常的骰子（六个面的那种），且掷出每个面的概率近似认为相等（$\frac{1}{6}$）.

连续丢出两次,问掷出和为10的概率为多少？

答:你怕不是个zz吧,这么简单的问题你也敢问？

好,连续丢出十次,问掷出和为30的概率为多少？

没话说了吧

解：

用生成函数的思想来，把每一个和看作关于点数(1,2,3,4,5,6)的多项式乘积.

也就是$x+x^2+x^3+x^4+x^5+x^6$.

那么,关于第二个问题,转换为

$$(x+x^2+x^3+x^4+x^5+x^6)^{10}$$

上述这个式子中,问你$x^{30}$的系数。

还是很难做对不对,考虑化简

$$(x+x^2+x^3+x^4+x^5+x^6)^{10}\\\\ =(x(1+x+x^2+x^3+x^4+x^5))^{10}\\\\ 发现x=-1是原式因式.\\\\ 一顿大除法.\\\\ \longrightarrow\space =[(x^2+x+1)(x^2-x+1)]^{10}\times x^{10} \times (x+1)^{10}$$

好的我们头皮发麻而且发现这个式子对我们最终计算$x^{30}$的系数没有任何的卵用.

为什么？因为我们不会三项式展开，但是如果不进行因式分解项数肯定会更大我们更不会算！

考虑反过来,如果把原式写成两个二项式的商也可以.

$$(1+x+x^2+x^3+x^4+x^5)\\\\ =\frac{(1-x^6)}{1-x}\\\\ 那么原来的式子(x+x^2+x^3+x^4+x^5+x^6)^{10}\\\\ =x^{10}(1-x^6)^{10}(1-x)^{-10}\\\\扔上二项式定理\\\\ 又因为10次是偶数次,(1-x^6)写成(x^6-1)，后面的同理\\\\ \rightarrow x^{10}\times\sum_{i=0}^{10}(-1)^i\binom{10}{i}x^{6i}\times\sum_{k=0}^{\infty}\binom{10+k-1}{k}x^k$$

好了把前面的$x^{10}$扔掉后面的构造出i,k满足x的次数为20就行辣.

一共i只可能取0,1,2,3枚举就行.

答案似乎长这个样子

$$\binom{29}{20}-\binom{10}{1}\binom{23}{14}+\binom{17}{8}\binom{10}{2}-\binom{10}{3}\binom{11}{2}$$

反正我是懒得算答案了.

生成函数的性质

生成函数的形式导数

定义

$$\forall A(x)=\sum_{k=0}^{\infty}a_kx^k \in R[[x]]\\\\ 定义DA\equiv\sum_{k=1}^{\infty}ka_kx^{k-1}\\\\ 称作A(x)在R[[x]]上的形式导数.$$

形式导数的运算法则和普通导数差不多.

加法则乘法则都满足的.但是似乎没有对链导法则的定义.

生成函数主要常用性质