11.5 指数生成函数及其应用
本章目录 · 1 节
本章导读
【定义11.5.1】序列 的指数生成函数为
普通生成函数直接以aₙ作xⁿ的系数;指数生成函数中xⁿ的普通系数是aₙ/n!,因此取答案应使用 。漏乘阶乘会把排列数错当成组合数。
【例11.5.1】给定m个不同元素的n排列数 ,规定n>m时为0。则
同一个函数 既是组合数 的普通生成函数,又是排列数 的指数生成函数,两种系数约定不同。有限m时不应在n>m处书写负整数阶乘。(例完)
【例11.5.2】若所有n都有bₙ=1,指数生成函数为 。若改用普通生成函数,则是1/(1−x),两者不能互换。(例完)
【定理11.5.1】多重集 的r排列数记为Aᵣ,则
证明:从第i因子选xᵐⁱ/mᵢ!,总次数r要求 。相应乘积为 ,前一系数正是这些重复次数下的不同排列数。对一切合法次数向量求和,即得到Aᵣ。相同字母的各副本不标号,但排列中的位置有区别。
【受限次数的因子】允许第i类出现次数属于集合Lᵢ时,替换为 。次数不限用eˣ;只能偶数次用 ;只能奇数次用 ;必须至少一次用eˣ−1。只求长度≤r的系数时,可将每个因子截断到r次,不影响所求答案。
【例11.5.3】由数字1、2、3、4组成五位数,要求1出现1或2次,2出现0或1次,3出现0到3次,4出现偶数次。因为没有0,所有长度5的串均为五位数。对应
展开到五次得 ,故N=215。按4的出现次数独立校验。
准确分组为:4出现0次时,(1,2,3)的次数向量为(1,1,3)、(2,0,3)、(2,1,2),贡献20+10+30=60;4出现2次时,向量为(1,0,2)、(1,1,1)、(2,0,1)、(2,1,0),贡献30+60+30+30=150;4出现4次时,向量为(1,0,0),贡献5。合计60+150+5=215。(例完)
【例11.5.4】字母A、B、C、D、E、F构成长n串,要求A与B出现次数之和为偶数。A、B的次数要么同偶、要么同奇,其余四类不限,所以
因此 ,n=0时为1,n=1时为4(只允许C、D、E、F)。也可按A或B所占的偶数位置数计数,得 ,用二项式定理取偶数项即为同一结果。“A与B总次数为偶数”不等同于“A和B各自都只能出现偶数次”,后一条件会漏掉同奇情况。(例完)
【应用步骤】先明确计数对象是否区分位置;每类出现次数能否为0、有无上下界及奇偶限制;写出各类的指数因子后相乘;最后取r次系数并乘r!。例如库存上界为2并不表示必须出现2次,应使用1+x+x²/2!;若必须出现1或2次,则要去掉常数项。若任务是不计顺序的选择,应回到普通生成函数,不应套指数生成函数的排列计数。
