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

文章目录

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

参考博客 : 按照顺序看

【组合数学】生成函数简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
【组合数学】生成函数 ( 线性性质 | 乘积性质 )
【组合数学】生成函数 ( 移位性质 )
【组合数学】生成函数 ( 求和性质 )
【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )
【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 )
【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )
【组合数学】生成函数 ( 正整数拆分 | 重复有序拆分 | 不重复有序拆分 | 重复有序拆分方案数证明 )
【组合数学】指数生成函数 ( 指数生成函数概念 | 排列数指数生成函数 = 组合数普通生成函数 | 指数生成函数示例 )
【组合数学】指数生成函数 ( 指数生成函数性质 | 指数生成函数求解多重集排列 )

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

使用

1,2,3,4

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

出现次数不能超过

次 , 但必须出现 ,

出现次数不超过

次 ,

出现次数最多

次 ,

出现偶数次 ,

求上述五位数的个数 ;

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

一共有

个位置 , 使用

1,2,3,4

向这

个位置中填充 ,

选取个数分析 :

出现不超过

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

, 则可选取的个数是

1,2

出现不超过

次 , 可选取个数

0,1

出现可以达到

次 , 可选取的个数

0,1,2,3

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

0, 2, 4, 6, 8, cdots

, 这里注意一共选择

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

x^5

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

次幂数 , 没必要超过

, 选择

0,2,4

即可 ;

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

多重集

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

多重集

的

排列数组成数列

{ 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)

展开 , 其中的

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

指数生成函数写法 :

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

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

③ 分项格式 :

cfrac{x^n}{n!}

④ 分项次幂 : 选取值 ;

总共有

种元素

1,2,3,4

, 因此生成函数是

个生成函数项相乘 ;

元素对应的生成函数项 :

选取值 :

1,2

最终结果 :

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

元素对应的生成函数项 :

选取值 :

0,1

最终结果 :

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

元素对应的生成函数项 :

选取值 :

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!}

元素对应的生成函数项 :

选取值 :

0,2,4,6 , cdots

, 这里只选取

个 , 求

的次幂的

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

0 , 2, 4

即可 ,

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

最终结果 :

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 5cfrac{x^2}{2!} 18cfrac{x^3}{3!} 64cfrac{x^4}{4!} 215cfrac{x^5}{5!} cdots

后面的就不算了 , 其中

x^5

的项是

215cfrac{x^5}{5!}

, 因此题目中要求的

位数的个数是

215

个 ;

博客函数模型数学

0 人点赞