【组合数学】生成函数 ( 求和性质 )

举报
韩曙亮 发表于 2022/01/11 00:41:55 2022/01/11
【摘要】 文章目录 一、生成函数求和性质 1 ( 向前求和 )二、生成函数求和性质 2 ( 向后求和 ) 参考博客 : 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 ...



参考博客 :





一、生成函数求和性质 1 ( 向前求和 )



生成函数求和性质 1 :

b n = ∑ i = 0 n a i b_n = \sum\limits_{i=0}^{n}a_i bn=i=0nai , 则 B ( x ) = A ( x ) 1 − x B(x) = \cfrac{A(x)}{1-x} B(x)=1xA(x)


数列 a n a_n an 的生成函数是 A ( x ) A(x) A(x) , 数列 b n b_n bn 的生成函数是 B ( x ) B(x) B(x) ,

数列 a n = { a 0 , a 1 , a 2 , ⋯   } a_n = \{ a_0 , a_1, a_2 , \cdots \} an={a0,a1,a2,} , 数列 b n = { b 0 , b 1 , b 2 , ⋯   } b_n = \{ b_0 , b_1, b_2 , \cdots \} bn={b0,b1,b2,} ;

数列 a n a_n an 的生成函数 A ( x ) = a 0 + a 1 x + a 2 x 2 + ⋯ A(x) = a_0 + a_1x + a_2x^2 + \cdots A(x)=a0+a1x+a2x2+

数列 b n b_n bn 的生成函数 B ( x ) = b 0 + b 1 x + b 2 x 2 + ⋯ B(x) = b_0 + b_1x + b_2x^2 + \cdots B(x)=b0+b1x+b2x2+


b n b_n bn 数列中的第 n n n 项 , 等于 a n a_n an 数列中的前 n n n 项的和 ;


推导 b n b_n bn 数列的项 :

b 0 = a 0 b_0 = a_0 b0=a0

b 1 = a 0 + a 1 b_1 = a_0 + a_1 b1=a0+a1

b 2 = a 0 + a 1 + a 2 b_2 = a_0 + a_1 + a_2 b2=a0+a1+a2

⋮ \vdots

b n = a 0 + a 1 + a 2 + ⋯ + a n b_n = a_0 + a_1 + a_2 + \cdots + a_n bn=a0+a1+a2++an


推导生成函数的项 :

B ( x ) B(x) B(x) 中的 x 0 x^0 x0 项 ( 常数项 ) : b 0     = a 0 b_0 \ \ \ = a_0 b0   =a0

B ( x ) B(x) B(x) 中的 x 1 x^1 x1 项 ( 常数项 ) : b 1 x   = ( a 0 + a 1 ) x b_1x \ = (a_0 + a_1)x b1x =(a0+a1)x

B ( x ) B(x) B(x) 中的 x 2 x^2 x2 项 ( 常数项 ) : b 2 x 2 = ( a 0 + a 1 + a 2 ) x 2 b_2x^2 = (a_0 + a_1 + a_2)x^2 b2x2=(a0+a1+a2)x2

⋮ \vdots

B ( x ) B(x) B(x) 中的 x n x^n xn 项 ( 常数项 ) : b n x n = ( a 0 + a 1 + a 2 + ⋯ + a n ) x n b_nx^n = (a_0 + a_1 + a_2 + \cdots + a_n)x^n bnxn=(a0+a1+a2++an)xn


将上述 B ( x ) B(x) B(x) 中的各项相加 : 相加的策略是纵向相加 , 如下图所示 :

在这里插入图片描述

1 1 1 列相加 : a 0 + a 0 x + a 0 x 2 + ⋯ + a 0 x n = a 0 1 1 − x a_0 + a_0 x + a_0x^2 + \cdots + a_0x^n = a_0\cfrac{1}{1-x} a0+a0x+a0x2++a0xn=a01x1

2 2 2 列相加 : a 1 x + a 1 x 2 + ⋯ + a 1 x n = a 1 x 1 1 − x a_1 x + a_1x^2 + \cdots + a_1x^n = a_1x\cfrac{1}{1-x} a1x+a1x2++a1xn=a1x1x1

⋮ \vdots

n n n 列相加 : a n x n = a n x n 1 1 − x a_nx^n = a_nx^n\cfrac{1}{1-x} anxn=anxn1x1


最终得到 :

B ( x ) = a 0 1 1 − x + a 1 x 1 1 − x + ⋯ + a n x n 1 1 − x + ⋯ B(x) = a_0\cfrac{1}{1-x} + a_1x\cfrac{1}{1-x} + \cdots + a_nx^n\cfrac{1}{1-x} + \cdots B(x)=a01x1+a1x1x1++anxn1x1+

将其中的 1 1 − x \cfrac{1}{1-x} 1x1 提取出来 , 就可以得到 :

B ( x ) = 1 1 − x ( a 0 + a 1 x + + ⋯ + a n x n + ⋯   ) B(x) = \cfrac{1}{1-x} ( a_0 + a_1x + + \cdots + a_nx^n + \cdots ) B(x)=1x1(a0+a1x+++anxn+)

B ( x ) = 1 1 − x A ( x ) B(x) = \cfrac{1}{1-x} A(x) B(x)=1x1A(x)





二、生成函数求和性质 2 ( 向后求和 )



生成函数求和性质 2 :

b n = ∑ i = n ∞ a i b_n = \sum\limits_{i=n}^{\infty}a_i bn=i=nai , 并且 A ( 1 ) = ∑ i = n ∞ a i A(1) =\sum\limits_{i=n}^{\infty}a_i A(1)=i=nai 收敛 , 则 B ( x ) = A ( 1 ) − x A ( x ) 1 − x B(x) = \cfrac{A(1) - xA(x)}{1-x} B(x)=1xA(1)xA(x)

文章来源: hanshuliang.blog.csdn.net,作者:韩曙亮,版权归原作者所有,如需转载,请联系作者。

原文链接:hanshuliang.blog.csdn.net/article/details/109322752

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。