生成函数

可表示为$F(x)=\sum _n{a}_n{k}_n(x)$，对于不同类型的生成函数，有不同的核函数$k_n(x)$。

普通生成函数：$k_n(x)=x^n$。

指数生成函数：$k_n(x)=\frac{x^n}{n!}$。

迪利克雷生成函数：$k_n(x)=\frac{1}{n^x}$。

普通生成函数

封闭形式

在运用生成函数的过程中，我们不会一直使用形式幂级数的形式，而会适时地转化为封闭形式以更好地化简。

对于$<1,1,1,\cdots >$的普通生成函数$F(x)=\sum _{0\le n}{x}^n$，$F(x)x+1=F(x)$，$F(x)=\frac{1}{1-x}$

一些函数的封闭形式化简

$<1,p,p^2,p^3,p^4,\cdots >$

$F(x)=\sum _{n\ge 0}{p}^n{x}^n,F(x)px+x=F(x),F(x)=\frac{x}{1-px}$

$<0,1,1,1,1,\cdots >$

$F(x)=\sum _{n\ge 1}{x}^n,xF(x)+x=F(x),F(x)=\frac{x}{1-x}$

$<1,0,1,0,1,\cdots >$

$F(x)=\sum _{n\ge 0}{x}^{2n},F(x)x^2+1=F(x),F(x)=\frac{1}{1-x^2}$

$<1,2,3,4,5,\cdots >$

$F(x)=\sum _{n\ge 0}(n+1)x^n,F(x)-xF(x)=\sum _{n\ge 0}{x}^n=\frac{1}{1-x},F(x)=\frac{1}{(1-x{)}^2}$

$a_n={(}_n^m)(m是常数，n\ge 0)$

$F(x)=\sum _{n\ge 0}{C}_m^n{x}^n,二项式定理有F(x)=(1+x{)}^m$

$a_n={(}_n^{n+m})(m是常数，n\ge 0)$

$F(x)=\sum _{n\ge 0}{C}_{n+m}^n{x}^n,F(x)=\frac{1}{(1-x{)}^{m+1}}$

斐波那契数列生成函数

$$\begin{gathered} F(x)=a_0+a_{1}x+a_2{x}^2+\dots \\ xF(x)=a_{0}x+a_1{x}^2+a_2{x}^3+\dots \\ {x}^{2}F(x)=a_0{x}^2+a_1{x}^3+a_2{x}^4+\dots \\ F(x)=xF(x)+x^{2}F(x)+a_0 \\ F(x)=\frac{1}{1-x-x^2} \\ 求解1-x-x^2=(1-ax)(1-bx)，得到a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2} \\ F(x)=\frac{1}{1-x-x^2}=\frac{A}{1-ax}+\frac{B}{1-bx} \\ 解得A=\frac{1}{\sqrt{n}}a,B=-\frac{1}{\sqrt{5}}b \\ 有F(x)=\frac{a}{\sqrt{5}}\frac{1}{1-ax}-\frac{b}{\sqrt{5}}\frac{B}{1-bx} \\ 由\sum _{n\ge 0}{C}_{n+m}^n{x}^n=\frac{1}{(1-x{)}^{m+1}} \\ 可解得斐波那契生成函数的第n项系数，a_n=\frac{a}{\sqrt{5}}{a}^n-\frac{b}{\sqrt{5}}{b}^n \\ {a}_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^{n+1}-(\frac{1-\sqrt{5}}{2}{)}^{n+1}) \end{gathered}$$

一道生成函数模板题

由题意可列出式子
$$\begin{gathered} \sum _{n\ge 0}{x}^{6n}=\frac{1}{1-x^6} \\ \sum _{n\ge 0}^9{x}^n=\frac{x^{10}-1}{x-1} \\ \sum _{n\ge 0}^5{x}^n=\frac{x^6-1}{x-1} \\ \sum _{n\ge 0}{x}^{4n}=\frac{1}{1-x^4} \\ \sum _{n\ge 0}^7=\frac{x^8-1}{x-1} \\ \sum _{n\ge 0}{x}^{2n}=\frac{1}{1-x^2} \\ \sum _{n\ge 0}^1{x}^n=\frac{x^2-1}{x-1} \\ \sum _{n\ge 0}{x}^{8n}=\frac{1}{1-x^8} \\ \sum _{n\ge 0}{x}^{10n}=\frac{1}{1-x^{10}} \\ \sum _{n\ge 0}^3=\frac{x^4-1}{x-1} \\ 全部乘起来得到\frac{1}{(1-x{)}^5} \\ 得到第n项为C_{n+4}^n=C_{n+4}^4 \end{gathered}$$

#3027. [Ceoi2004]Sweet

题目就是要我们求：
$$\begin{gathered} F(x)=\prod _{i=1}^n\frac{1-x^{m_i+1}}{1-x} \\ F(x)(1-x{)}^n=\prod _{i=1}^{n}1-x^{m_i+1} \end{gathered}$$
只需要暴力展开左右两边，枚举系数即可求得，

最后

以上就是故意蓝天为你收集整理的生成函数简单入门生成函数的全部内容，希望文章能够帮你解决生成函数简单入门生成函数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。