【组合数学】指数生成函数 ( 指数生成函数概念 | 排列数指数生成函数 = 组合数普通生成函数 | 指数生成函数示例 )

韩曙亮

发布于 2023-03-28 18:42:35

1K0

发布于 2023-03-28 18:42:35

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

参考博客 : 按照顺序看

一、指数生成函数

多重集的组合数 , 使用生成函数进行计算 ;

多重集的排列数 , 使用指数生成函数进行计算 ;

序列

\{ a_n \}

, 其通项公式是

a_n

,

\{ a_n \}

的一般生成函数是

G(x) = \sum\limits_{n=0}^{\infty}a_n x^n

,

\{ a_n \}

的指数生成函数是

G_e(x) = \sum\limits_{n=0}^{\infty}a_n \cfrac{x^n}{n!}

\ \ \ \,

★ ( 重点公式 )

\{ a_n \}

的指数生成函数是在一般生成函数的基础上除以了

n!

;

二、排列数指数生成函数 = 组合数普通生成函数

排列数 :

P(n,r) = \cfrac{n!}{(n-r)!}

,

n

个元素中取

r

个元素 , 不允许重复的排列数 ;

组合数 :

C(n,r) = \cfrac{n!}{r!(n-r)!}

,

n

个元素中取

r

个元素 , 不允许重复的组合数 ;

组合数对应的生成函数是

G(x) = \sum\limits_{n=0}^{\infty}\dbinom{m}{n} x^n

, 收敛后是

(1+x)^n

排列数对应的生成函数是

G(x) = \sum\limits_{n=0}^{\infty}P(m, n) x^n

, 根据

n! C(m,n) = P(m, n)

, 该排列数的生成函数 , 每一项都除以

n!

, 就可以得到对应的组合数的生成函数 ;

排列计数对应的指数生成函数是

G_e(x) = \sum\limits_{n=0}^{\infty}P(m, n) \cfrac{x^n}{n!}

, 根据根据

C(m,n) =\cfrac{ P(m, n)}{n!}

, 可以得出如下结论 :

排列计数的指数生成函数

=

组合计数的普通生成函数

三、指数生成函数示例

数列

b_n=1

, 求

\{ b_n \}

的指数生成函数 ;

数列是

\{1, 1 ,1 , \cdots\}

普通生成函数

G(x) = 1 + x + x^2 + \cdots = \sum\limits_{n=0}^{\infty}x^n

指数生成函数

G_e(x) = \sum\limits_{n=0}^{\infty}\cfrac{x^n}{n!}=e^x

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-30，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度