生成函数GeneratingFunction
极限
\(\forall \rightarrow\)对于
\(\exists \rightarrow\)存在
极限:\(\forall \epsilon,\exists N,N>n,|a_n-A|<\epsilon\)
就是说，对于所有(任意小的非负整数)\(\epsilon\)存在\(N\),使得\(a_n\)与A的差值小于\(\epsilon\)
我们就把\(A\)叫做此序列的极限\(\lim_{n\rightarrow\infty}a_n=A\)
有限数列没有极限！
若数列中的值全部相同的也没有极限！
\(\{1,\frac{1}{2},\frac{1}{3},\frac{1}{4},...\}的极限是0\)
\(\{1,0,0,0,0,0,...\}\)的极限是0
导数
To be continued:D
泰勒公式
To be continued:D
生成函数
如何简短的表示一个序列呢？
\(\left\{1,1,1,1,1,1,1,...\right\}\)
我们以一多项式来表达，以x的指数为下标，系数为值，就可以得到
\(A=\left\{1*x^0,1*x^1,1*x^2,1*x^3,...\right\}\)
即
\(A=\left\{1,x,x^2,x^3,...\right\}\)
注意，这个序列的长度是无限的
\(\frac{1}{1-x}\)就是生成这个序列的函数,也就是说，它就是生成函数
类似的，可以得到:
\[\frac{2}{1-x}=2,2,2,2,2,2...\\ \frac{1}{1+x}=1-x+x^2-x^3...=1,-1,1,-1,...\\ \frac{1}{1-2x}=1+2x+4x^2+8x^3...=1,2,4,8,...\\ \]当然，生成函数支持加法和乘法(上面已经有例子了)
\[\frac{1}{1+x}+\frac{1}{1-x}=\frac{2}{1-x^2}\\ 1,1,1,1,...+1,-1,1,-1,...=2,0,2,0,...\\ \frac{1}{1-x^2}=1,0,1,0,...\\ \frac{x}{1-x^2}=\frac{1}{1-x}-\frac{1}{1-x^2}=0,1,0,1,...\\ \]还有
\[令A=1+3x+5x^2+7x^3+...\\ \therefore xA=1x+3x^2+...\\ \therefore (1-x)A=1+2x+2x^2+...\\ \because \frac{2}{1-x}=2+2x^2+...\\ \therefore \frac{2x}{1-x}=2x+2x^2+...\\ \therefore 1+\frac{2x}{1-x}=1+2x+2x^2+...\\ \therefore (1-x)A=1+\frac{2x}{1-x}\\ \therefore A=\frac{1+\frac{2x}{1-x}}{1-x}=\frac{1+x}{(1-x)^2}\\ \]\[令B=1+4x+9x^2+16x^3+25x^5+...\\ \therefore xB=1x+4x^2+9x^3+...\\ \therefore (1-x)B=1+3x+5x^2+...\\ \therefore (1-x)B=A=\frac{1+x}{(1-x)^2}\\ \therefore (1-x)B=\frac{1+x}{(1-x)^3} \]如何生成有限数列呢？
\[\because A=1,x,x^2,x^3,...\\ \therefore x^4A=x^4+x^5+x^6+...\\ \therefore (1-x^4)A=1+x+x^2+x^3\\ 又\because A=\frac{1}{1-x}\\ \therefore (1-x^4)\times\frac{1}{1-x}=\frac{1-x^4}{1-x}=1+x+x^2+x^3 \]如果对生成函数求导会如何？
\[(\frac{1}{1-x})'=\frac{1}{(1-x)^2}=1+2x+3x^2+4x^4+...\\ (\frac{1}{1-x})''=\frac{1}{(1-x)^3}=1+3x+6x^2+10x^4+15x^5+... \]这里旨在于告诉你很多数列均可以用生成函数表示
此外的
\[F=1+1x+2x^2+3x^3+5x^4+...\\ \therefore F=\frac{1}{1-x-x^2}\\ 对于方程1-x-x^2=0\\ 解得x_1=\frac{1+\sqrt{5}}{2},x_2=\frac{1-\sqrt{5}}{2}\\ 用配方法倒推得1-x-x^2=(1-x_1)\times(1-x_2)\\ 设F=\frac{1}{1-x-x^2}=\frac{a}{1-x_1}+\frac{b}{1-x_2}\\ ...\\ To be continued:D \]当然，普通生成函数的用处不止于此
有一些水果，求选苹果偶数个，选梨5的倍数个，橘不超过4个，桃最多一个，求选共n个水果的方案数
这咋办？还好，我们有生成函数!\
众所周知，普通生成函数的乘积就是组合数(你又知道？)
\[C=A+B=\sum_{n=0}^\infty(a_i+b_i)x_n \rightarrow 加法原则\\ C=A\times B=\sum_{n=0}^\infty\sum_{i=0}^{n}(a_i*b_{(n-i)})x_n\\ c_n=\sum_{i=0}^{n}(a_i*b_{(n-i)})x_n \rightarrow 乘法原则 \]
我们让i次项系数作为组合数故得\(i\)次项系数即为相加为i的生成函数的所有方案数
苹果的生成函数:\(1+x^2+x^4+x^6+...=\frac{1}{1-x^2}\)
梨:\(1+x^5+x^{10}+...=\frac{1}{1-x^5}\)
橘:\(1+x+x^2+x^3+x^4=\frac{1-x^5}{1-x}\)
桃:\(1+x=\frac{1-x^2}{1-x}\)
相乘求组合，\(\frac{1}{1-x^2}\times\frac{1}{1-x^5}\times\frac{1-x^5}{1-x}\times\frac{1-x^2}{1-x}=\frac{1}{(1-x)^2}\)
发现恰为\(1+2x+3x^2+4x^4+...\)所以输出n即可
6!
但是，并不是所有题目都如此凑巧，我们还得算\((1+x^2+x^4+x^6+...)\times(1+x^5+x^{10}+...)\times ...\)
所以，我们将给出一个模板，旨在于做\(\uparrow\)上面的小乘法
//这里是一个用背包装物品的模板
c1[0]=1,l1=0;
//x[i]-->物品大小
//y[i]-->物品个数
for (int i = 1; i <= n; i++)//遍历物品
{
l2 = l1 + x[i] * y[i];//预计的最高次数
memset(c2, 0, sizeof(int) * (l2 + 1));//清空
for (int j = 0; j <= y[i] && j * x[i] <= l2; j++)
//当然，如果物品无限多不需要判断j <= y[i]
for (int k = 0; k <= l1 && j * x[i] + k <= l2; k++)
c2[j * x[i] + k] += c1[k];
memcpy(c1, c2, sizeof(int) * (l2 + 1));//储存计算结果
l1 = l2;
}
//最后，c1[n]表示装满大小k的背包的方案数
其实，看到这你也能发现，它可以用背包实现，但与背包相比，生成函数可快多了
普通生成函数只能解决组合问题！！！
指数生成函数
普通生成函数只能解决组合问题!!!
但是指数生成函数可以解决排列问题:D
To be continued:D
标签：...,GeneratingFunction,+...,frac,函数,2x,生成,therefore From： https://www.cnblogs.com/ssj233/p/17364080.html