生成函数

#定义


生成函数即母函数,是组合数学中尤其是计数方面的一个重要理论和工具。
生成函数有普通型生成函数和指数型生成函数两种,其中普通型用的比较多。形式上说,普通型生成函数用于解决多重集的组合问题,而指数型母函数用于解决多重集的排列问题。
最早提出母函数的人是法国数学家LaplaceP.S.在其1812年出版的《概率的分析理论》中明确提出“生成函数的计算”,书中对生成函数思想奠基人——Euler L在18世纪对自然数的分解与合成的研究做了延伸与发展。生成函数的理论由此基本建立。
另外生成函数也广泛应用于编程与算法设计、分析上,运用这种数学方法往往对程序效率与速度有很大改进。

例如我们有一个数组{an}=a1,a2,a3……我们设他的生成函数为$$G(x)=a_0+a_1x+a_2x^2+a_3x^3+……=\sum^{n}_{k=0}a_kx^k$$
其中x只是形式上的变量,其实上面就是一个多项式,如果$a_n≠0$,那么这就是一个n次多项式。

##例子


我们举一个简单的例子,对于一个无穷数列{1,1,1,1,1……}的生成函数为$A(x)=1+x+x^2+x^3+……=\frac{1}{1-x}$。为了研究方便,通常假定生成函数是收敛的。即对于本例,我们假定$|x|<1$。

我们这里引入一个二项式定理:
$$(x+y)^n=\sum^{n}_{k=0}C^k_n x^ky^{n-k}$$

那么我们该如何用组合的角度来理解这个式子

#应用


甲、乙、丙分别有3,4,6个苹果,李华要拿取8个,且只能从甲、乙那里拿奇数个,从丙那里拿偶数个(包含0),请问有多少种取法?
在学过多项式之前,我们只能用组合数学来做这题,但是会非常非常的麻烦。
那么我们考虑引入多项式:$(x+x^3)(x+x^3)(1+x^2+x^4+x^6)$
其中第一个括号代表甲第二个代表乙第三个代表丙,x的幂数代表要取的个数。
那么仔细一想是不是只要将多项式展开,$x^8$的系数就是方案数。
是不是很奇妙!!!!
什么??你问怎么展开???
等比数列求和会不会,什么不会???高中会学的,自己去看……QWQ

再来一题好不啦
从苹果、香蕉、橘子和梨中拿一些水果出来(允许某种拿0个),要求苹果只能拿偶数个,香蕉的个数是5的倍数,橘子最多拿4个,梨要么不拿,要么只能拿一个。求拿n个水果的方案数。

自己根据上面的方法写出多项式并化简
最后得到:$$1+2x+3x^2+4x^3+……=\sum^{∞}_{k=0}(k+1)x^k$$
即方案数就是(n+1)种 惊不惊喜 意不意外

tips:有一些无法用数列化简的可以用求导化简(等式两边同时求导,等式仍然成立)