【组合数学】指数生成函数 ( 指数生成函数性质 | 指数生成函数求解多重集排列 )

文章目录

一、指数生成函数性质
二、指数生成函数求解多重集排列

参考博客 : 按照顺序看

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

一、指数生成函数性质

两个数列

{a_n} , {b_n}

对应的指数生成函数分别是

A_e(x) , B_e(x)

将上述两个指数生成函数相乘 , 看做一个函数 , 可以展开成另外一个数列的级数形式 ,

A_e(x) cdot B_e(x) = sumlimits_{n=0}^{infty} c_n cfrac{x^n}{n!}

其中 ,

c_n =sumlimits_{k=0}^{infty}dbinom{n}{k}a_kb_{n-k}

( 代入即可求出该结果 )

二、指数生成函数求解多重集排列

多重集

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^r}{r!}

的系数就是多重集的排列数 , 特别注意如果不是

cfrac{x^r}{r!}

形式 , 需要强制转化成上述性质 , 一定要除以

; ★★★★★

选取问题参考 :

元集

, 从

集合中选取

个元素 ;

根据元素是否允许重复 , 选取过程是否有序 , 将选取问题分为四个子类型 :

	元素不重复	元素可以重复
有序选取	集合排列 P ( n , r ) P(n,r) P(n,r)	多重集排列
无序选取	集合组合 C ( n , r ) C(n,r) C(n,r)	多重集组合

P(n,r)

多重集排列无序选取集合组合

C(n,r)

多重集组合

选取问题中 :

不可重复的元素 , 有序的选取 , 对应 集合的排列 ;

P(n,r) = dfrac{n!}{(n-r)!}

不可重复的元素 , 无序的选取 , 对应 集合的组合 ;

C(n,r) = dfrac{P(n,r)}{r!} = dfrac{n!}{r!(n-r)!}

可重复的元素 , 有序的选取 , 对应 多重集的排列 ;

全排列 = cfrac{n!}{n_1! n_2! cdots n_k!}

, 非全排列

k^r , rleq n_i

可重复的元素 , 无序的选取 , 对应 多重集的组合 ;

N= C(k r - 1, r)

博客函数集合模型数学

0 人点赞