多项式与生成函数
1 普通生成函数
1.1 定义
\(F(x)=\sum_{n\geq0}a_nx^n\)。
例如:
- 序列 \(<1,2,3>\) 的生成函数为 \(1+2x+3x^2\);
- 序列 \(<1,2,4,\dots>\) 的生成函数为 \(\sum_{n\geq}2^nx^n\)。
1.2 加减运算
\(F(x)\pm G(x)=\sum_{n\geq0}(a_n+b_n)x^n\)。
即 \(F(x)\pm G(x)\) 是序列 \(<a_n+b_n>\) 的生成函数。
1.3 乘法运算(卷积)
\(F(x)G(x)=\sum_{i\geq0}a_ix^i\sum_{j\geq0}b_jx^j=\sum_{n\geq0}x^n\sum_{i=0}^n a_ib_{n-i}\)。
即 \(F(x)G(x)\) 为序列 \(\sum_{i=0}^na_ib_{n-i}\) 的生成函数。
2 指数生成函数
2.1 定义
\(F(x)=\sum_{n\geq0}a_n\frac{x^n}{n!}\)。
例如:
- 序列 \(<1,1,1,\dots>\) 的指数生成函数为 \(F(x)=\sum_{n\geq0}\frac{x^n}{n!}=e^x\)。
- 序列 \(<1,p,p^2,\dots>\) 的指数生成函数为 \(F(x)=\sum_{n\geq0}p^n\frac{x^n}{n!}=e^{px}\)。
2.2 加减运算
\(F(x)+G(x)=\sum_{n\geq0}(a_n+b_n)\frac{x^n}{n!}\)。
即 \(F(x)+G(x)\) 是序列 \(<a_n+b_n>\) 的生成函数。
2.3 乘法运算
\(F(x)G(x)=\sum_{i\geq0}a_i\frac{x^i}{i!}\sum_{j\geq0}a_j\frac{x^j}{j!}=\sum_{n\geq0}x^n\sum_{i=0}^n\frac{a_ib_{n-i}}{i!(n-i)!}=\sum_{n\geq0}\frac{x^n}{n!}\sum_{i=0}^{n}C_n^ia_ib_{n-i}\)。
即 \(F(x)G(x)\) 是序列 \(<C_n^ia_ib_{n-i}>\) 的指数生成函数。
3 生成函数的应用
3.1 泰勒展开式
-
\(\frac{1}{1-x}=\sum_{n=0}^{\infty} x^n\);
-
\(\frac{1}{1-x^k}=\sum_{n=0}^{\infty}x^{nk}\);
-
\(\frac{1}{(1-x)^2}=\sum_{n=1}^{\infty}nx^{n-1}\),本式可由 (1) 式两边求导得到
-
\(e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!}\);
-
\(\frac{1-x^{n+1}}{1-x}=\sum_{i=0}^nx^i\)。
3.2 广义二项式定理
\(\frac{1}{(1-x)^n}=\sum_{i=0}^{\infty}C_{n+i-1}^i x^i\)。
标签:frac,函数,多项式,sum,生成,geq0,序列 From: https://www.cnblogs.com/WhileTrueRP/p/18353707/duo_xiang_shi_yu_sheng_cheng_han_shu