1.本质
生成函数的本质——处理排列组合问题的有利工具,而不是简单的\(\frac{1}{1-x}\)的指标代换
2.定义
在数学中,某个序列(an)n∈N 的母函数(又称生成函数,英语:Generating function)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。
讲的通俗一点,对于某个序列$$a_0,a_1,…,a_n$$,我想找一个函数来表示它,假设是$$G(x)=a_0+a_1x+a_2x2…a_nxn$$。这时候函数第i项的系数就表示了序列中的第i个元素。同时我们也可以看到,函数中的自变量x好像并没有什么意义,他的取值并不影响序列的表示,因此我们称这种函数为形式幂级数
3.干什么用捏
明显G(x)是多项式吧,多项式能干的事就多了,加减乘除,exp,.....
4.普通生成函数
有三种物品,分别有3,2,3个,问拿出4个进行组合 ({1123},{3211}算一种)的方案数是多少
先构造函数1,对每个物品构造一个多项式\(G1(x) = 1 + x + x^2 + x^3\)
\(G_2(x) = 1 + x + x^2\)
\(G_3(x) = 1 + x + x ^ 2 + x ^ 3\)
1 1 1 1
1 1 1
1 1 1 1
然后这时候我们就很懵了,然后嘞,这玩意儿能干啥,我们可以对\(\frac{1]{1-x}\)变形搞一搞,
同时我们还知道\(\frac{1]{1-x}\)对应的第i项系数为1,那这时候神奇的操作来了,我们可以将构造出来的函数化成类似于\(\frac{1]{1-x}\)的一系列柿子,进而求得了通解。
通项公式
1.广义二项式定理
\(\frac{1}{(1-x)^n} = \sum_{k=0}^{\infty}C_{n+k-1}^{k-1}x^k\)
举个栗子
求斐波那契数列的通项公式:
构造函数\(A(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 +.....\)
\[A(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 +..... \]\[xA(x) = x + x^2 + 2x^3 + 3x^4 + 5x^5 \]\[x^2A(X) = x^2 + x^3 + 2x^4 + 4x^5+5x^6 \]然后就有了一个小方程:
\[A - xA - x^2A = 1 \]\[A = \frac{1}{1-x-x^2} \]\[\frac{1}{1-x-x^2}\ 是个二次方程 \]配方一下
\(1-x-x^2 = (1-\phi_1x)(1-\phi_2x)\)
再解个方程
\(a(1−ϕ_2x)+b(1−ϕ_1x)=1\)
\[a = \frac{1}{\sqrt{5}} \phi_1, b = -\frac{1}{\sqrt{5}} \phi_2\ \]带回原始柿子:
\[A_n = \frac{1}{\sqrt{5}}((\frac{{1+\sqrt{5}}}{2})-(\frac{{1-\sqrt{5}}}{2})) \] 标签:phi,frac,5x,2x,sqrt,生成,函数 From: https://www.cnblogs.com/guier/p/16862787.html