当前位置：首页 > 编程资源 > 编程问答 >内容正文

编程问答

【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★

发布时间：2025/6/17 编程问答 46 豆豆

生活随笔收集整理的这篇文章主要介绍了【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★ 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

文章目录

一、生成函数性质总结
二、生成函数与序列的对应

参考博客 :

【组合数学】生成函数简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
【组合数学】生成函数 ( 线性性质 | 乘积性质 )
【组合数学】生成函数 ( 移位性质 )
【组合数学】生成函数 ( 求和性质 )
【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )

一、生成函数性质总结

1 . 生成函数线性性质 :

乘法 : $bn=αanb_n = \alpha a_n$ , 则 $\alpha A(x)$

加法 : $c_n = a_n + b_n$ , 则 $C (x) = A (x) + B (x)$

2 . 生成函数移位性质 :

向后移位 : $\begin{cases} 0, & n < l \\\\ a_{n-l}, & n \geq l \end{cases}$ , 则 $B(x) = x^l A(x)$

向前移位 : $b_n = a_{n+1}$ , 则 $\cfrac{A(x) - \sum\limits_{n=0}^{l-1} a_nx^n }{x^l}$

3 . 生成函数乘积性质 : $cn=∑i=0naibn−ic_n = \sum\limits_{i=0}^n a_i b_{n-i}$ , 则有 $\cdot B(x)$

生成函数求和性质 :

向前求和 : $bn=∑i=0naib_n = \sum\limits_{i=0}^{n}a_i$ , 则 $\cfrac{A(x)}{1-x}$

向后求和 : $bn=∑i=n∞aib_n = \sum\limits_{i=n}^{\infty}a_i$ , 并且 $=\sum\limits_{i=n}^{\infty}a_i$ 收敛 , 则 $\cfrac{A(1) - xA(x)}{1-x}$

4 . 生成函数换元性质 : $bn=αnanb_n = \alpha^n a_n$ , 则 $\alpha x)$

5 . 生成函数求导性质 : $b_n = n a_n$ , 则 $B (x) = x A^{'} (x)$

6 . 生成函数积分性质 : $bn=ann+1b_n = \cfrac{a_n}{n+1}$ , 则 $=\cfrac{1}{x} \int^{x}_{0} A( x)dx$

二、生成函数与序列的对应

给定序列 ${a_n\}$ 或 $a_n$ 的递推方程 , 求生成函数 $G (x)$ , 需要使用级数的性质和一些重要的级数 ;

常用的生成函数取值 :

$1$ 数列相关 :

${a_n\}$ , $a_n = 1^n$ ; $A(x)=∑n=0∞xn=11−x\begin{aligned} A(x) & = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \end{aligned}$

${a_n\}$ , $a_n = (-1)^n$ ; $A(x)=∑n=0∞(−1)nxn=11+x\begin{aligned} A(x) & = \sum_{n=0}^{\infty} (-1)^n x^n = \frac{1}{1+x} \end{aligned}$

${a_n\}$ , $a_n = k^n$ , $k$ 为正整数 ; $A(x)=∑n=0∞knxn=11−kx\begin{aligned} A(x) & = \sum_{n=0}^{\infty} k^n x^n = \frac{1}{1-kx} \end{aligned}$

二项式系数相关 :

${a_n\}$ , $an=(mn)a_n = \dbinom{m}{n}$ ; $A(x)=∑n=0∞(mn)xn=(1+x)m\begin{aligned} A(x) & = \sum_{n=0}^{\infty} \dbinom{m}{n} x^n = ( 1 + x ) ^m \end{aligned}$

组合数相关 :

${a_n\}$ , $an=(m+n−1n)a_n = \dbinom{m+n-1}{n}$ , $m, n$ 为正整数 ; $A(x)=∑n=0∞(m+n−1n)xn=1(1−x)m\begin{aligned} A(x) & = \sum_{n=0}^{\infty} \dbinom{m+n-1}{n} x^n = \frac{1}{{(1-x)}^m} \end{aligned}$

${a_n\}$ , $an=(−1)n(m+n−1n)a_n = (-1)^n \dbinom{m+n-1}{n}$ , $m, n$ 为正整数 ; $A(x)=∑n=0∞(−1)n(m+n−1n)xn=1(1+x)m\begin{aligned} A(x) & = \sum_{n=0}^{\infty} (-1)^n \dbinom{m+n-1}{n} x^n = \frac{1}{{(1+x)}^m} \end{aligned}$

${a_n\}$ , $an=(n+1n)a_n = \dbinom{n+1}{n}$ , $n$ 为正整数 ;
$A(x)=∑n=0∞(n+1n)xn=∑n=0∞(n+1)xn=1(1−x)2\begin{aligned} A(x) & = \sum_{n=0}^{\infty} \dbinom{n+1}{n} x^n \\ & = \sum_{n=0}^{\infty} (n+1) x^n \\ & = \frac{1}{{(1-x)}^2} \end{aligned}$

总结

以上是生活随笔为你收集整理的【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。

上一篇：【组合数学】生成函数 ( 换元性质 |
下一篇：【组合数学】生成函数 ( 生成函数示例