【组合数学】指数生成函数 ( 指数生成函数求解多重集排列示例 2 )

韩曙亮

发布于 2023-03-28 18:43:37

4200

发布于 2023-03-28 18:43:37

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

文章目录

一、指数生成函数求解多重集排列示例 2

参考博客 : 按照顺序看

一、指数生成函数求解多重集排列示例 2

使用白色红色蓝色涂色

n

个格子 , 白色的涂色个数是偶数 , 求涂色方案个数

这是一个排列问题 , 当不同的方格涂色交换之后 , 就变成了不同的方案 ,

红色 , 蓝色涂色 , 没有限制 , 涂色个数可以是

0, 1,2,3,4,\cdots

白色涂色 , 涂色个数是偶数个 , 涂色个数是

0, 2, 4, 6, 8 , \cdots

红色 , 蓝色涂色个数

0, 1,2,3,4,\cdots

序列 , 对应的生成函数项为 :

\cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} \cdots = 1 + x + \cfrac{x^2}{2!} + \cdots

白色涂色个数

0, 2, 4, 6, 8 , \cdots

序列 , 对应的生成函数项为 :

\cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} \cdots = 1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots

上述涂色方案个数的指数生成函数是 :

G_e(x) = (1 + x + \cfrac{x^2}{2!} + \cdots) (1 + x + \cfrac{x^2}{2!} + \cdots) (1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots)

其中

1 + x + \cfrac{x^2}{2!} + \cdots

可以写成

e^x

形式 ;

其中

1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots

可以写成如下形式 :

1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots = \cfrac{1}{2}(e^x + e^{-x})

e^x + e^{-x}

相加 , 奇次幂符号相反 , 直接约掉 , 偶数次幂变为原来的两倍, 因此在外面乘以

\cfrac{1}{2}

;

将上述

e^x

和

\cfrac{1}{2}(e^x + e^{-x})

替换到指数生成函数中 ;

G_e(x) = (1 + x + \cfrac{x^2}{2!} + \cdots) (1 + x + \cfrac{x^2}{2!} + \cdots) (1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots)

\ \ \ \ \ \ \ \ \ \ \ \, =\cfrac{1}{2}(e^x + e^{-x})(e^x )(e^x)

\ \ \ \ \ \ \ \ \ \ \ \, =\cfrac{1}{2}e^{3x} + \cfrac{1}{2}e^{x}

将

\cfrac{1}{2}e^{x}

展开后为

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

将

\cfrac{1}{2}e^{3x}

展开后为

\cfrac{1}{2}(1 + 3x + \cfrac{(3x)^2}{2!} + \cdots)=\cfrac{1}{2}\sum\limits_{n=0}^\infty \cfrac{3^nx^n}{n!}

\ \ \ \ \ \ \ \ \ \ \ \, =\cfrac{1}{2}\sum\limits_{n=0}^\infty \cfrac{3^nx^n}{n!} + \cfrac{1}{2}\sum\limits_{n=0}^\infty \cfrac{x^n}{n!}

\ \ \ \ \ \ \ \ \ \ \ \, =\sum\limits_{n=0}^\infty \cfrac{3^n + 1}{2} \cdot \cfrac{x^n}{n!}

\cfrac{x^n}{n!}

前的系数是

\cfrac{3^n + 1}{2}

因此白色红色蓝色涂色

n

个格子 , 白色是偶数的情况下 , 涂色方案有

\cfrac{3^n + 1}{2}

种 ;

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

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

博客

函数

模型

数学

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

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

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

登录后参与评论

0 条评论

热度