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

韩曙亮

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

3910

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

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

文章目录

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

参考博客 : 按照顺序看

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

使用

1,2,3,4

四个数字组成五位数 , 要求

1

出现次数不能超过

2

次 , 但必须出现 ,

2

出现次数不超过

1

次 ,

3

出现次数最多

3

次 ,

4

出现偶数次 ,

求上述五位数的个数 ;

这就是一个求解多重集排列的题目 , 使用指数生成函数 ;

一共有

5

个位置 , 使用

1,2,3,4

向这

5

个位置中填充 ,

选取个数分析 :

1

出现不超过

2

次 , 不能不出现 , 也就是必须大于

0

, 则可选取的个数是

1,2

,

2

出现不超过

1

次 , 可选取个数

0,1

,

3

出现可以达到

3

次 , 可选取的个数

0,1,2,3

,

4

出现偶数次 , 可选取个数是

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

, 这里注意一共选择

5

个 , 最终求解多重集时 , 主要是看

x^5

前的次幂数 , 因此这里的可选取个数就是单个因式中的

x

次幂数 , 没必要超过

5

, 选择

0,2,4

即可 ;

按照下面的模型 , 写出指数生成函数 ;

多重集

S=\{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \}

多重集

S

的

r

排列数组成数列

\{ a_r \}

, 对应的指数生成函数是 :

G_e(x) = f_{n_1}(x) f_{n_2}(x) \cdots f_{n_k}(x)

★

其中每个生成函数项

f_{n_i}(x)

是

f_{n_i}(x) = 1 + x + \cfrac{x^2}{2!} + \cdots + \cfrac{x^{n_i}}{n_i!}

★

将

G_e(x)

展开 , 其中的

r

系数就是多重集的排列数 ; ★

指数生成函数写法 :

① 确定生成函数项个数 : 多重集元素种类个数

② 确定生成函数项中的分项个数 : 选取值个数 ;

③ 分项格式 :

\cfrac{x^n}{n!}

④ 分项次幂 : 选取值 ;

总共有

4

种元素

1,2,3,4

, 因此生成函数是

4

个生成函数项相乘 ;

1

元素对应的生成函数项 :

选取值 :

1,2

最终结果 :

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

2

元素对应的生成函数项 :

选取值 :

0,1

最终结果 :

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

3

元素对应的生成函数项 :

选取值 :

0,1,2,3

最终结果 :

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

4

元素对应的生成函数项 :

选取值 :

0,2,4,6 , \cdots

, 这里只选取

5

个 , 求

x

的次幂的

5

前的系数 , 这里只需要选取到

0 , 2, 4

即可 ,

5

以上的数完全不需要 , 可以忽略 ;

最终结果 :

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

将上述指数生成函数中四个指数生成函数项相乘 , 计算出

x^5

前的系数 , 就是多重集的排列数 ;

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

\ \ \ \ \ \ \ \ \ \ \ \,= x + 5\cfrac{x^2}{2!} + 18\cfrac{x^3}{3!} + 64\cfrac{x^4}{4!} + 215\cfrac{x^5}{5!} \cdots

后面的就不算了 , 其中

x^5

的项是

215\cfrac{x^5}{5!}

, 因此题目中要求的

5

位数的个数是

215

个 ;

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

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

博客

函数

模型

数学

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

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

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

登录后参与评论

0 条评论

热度