11.4 生成函数及其应用

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【定义11.4.1】牛顿二项式系数。r为实数,n为整数,定义

例如 ,,。当r是非负整数时,它与普通组合数一致;一般实数上参数时,它是代数推广,不能一概解释为“从r个元素中选n个”。

【定理11.4.1】牛顿二项式定理的标准形式为

对实数α及实数z,1+z>0保证实幂有定义。若写成 ,实数情形应要求y>0且|x/y|<1;不能只写后一个条件而忽略负底数的非整数幂。α为非负整数时,级数截断为多项式,得到通常二项式定理。

当m为正整数,,所以

特别地,,。当α=1/2,有

作为解析级数,上述非截断展开在|z|<1使用;作为形式幂级数,则逐项比较系数,不要求给变量代入数值。

【定义11.4.2】序列a₀,a₁,…的普通生成函数为 。记 。形式幂级数的乘法用卷积定义:,每个系数只涉及有限次运算。常数项非零的级数可求乘法逆;微分、零常数积分也可按系数定义。序列与生成函数一一对应。

例如 的生成函数是 ; 的生成函数是 。从序列求函数常用几何级数及微积分,从函数求通项常用多项式除法、部分分式及系数提取。

【例11.4.1】(1) ,则 。(2) 。逐项积分得 ,再求导得 。零下限使积分常数确定。(例完)

【例11.4.2】,故 ,即a₀=2,a₁=7,其余n≥2有aₙ=2ⁿ⁺¹。多项式余项3x只修改一次项,不能把3加到所有系数上。(例完)

【例11.4.3】求 (n≥2)。设 ,卷积给出H²=H−x,即

两个代数根中,只取常数项为0者;另一个根常数项为1,不符合H的定义。前五项为1,1,2,5,14。用牛顿二项式展开平方根即可逐项得到上述系数。(例完)

【栈输出与括号匹配】n个不同元素按固定顺序入栈,把入栈记左括号、出栈记右括号,合法操作对应每个前缀左括号不少于右括号的平衡括号串。例如(1(2(3))(4))对应依次入1、入2、入3、出3、出2、入4、出4、出1,输出3,2,4,1。

设n对括号的合法配对数为Tₙ。最左左括号的匹配右括号内部有k对,后面有n−1−k对,故 。置 ,有T=1+xT²。取常数项为1的分支,

分子常数项为0,可以在形式级数中除以x。空栈操作也算一种,T₀=1。固定互异输入的栈输出排列与上述操作序列一一对应,因此输出排列数也是Tₙ。

【注11.4.1】生成函数解递推的四步:设序列的生成函数;按正确下标范围求和建立函数方程;求出符合常数项或初值的函数分支;展开并提取系数。初值项若没有先拆出,很容易出现一位下标偏移。

【多重集组合与不定方程】 的r组合对应 的非负整数解,故其个数为

每一因子的指数记录该类选择数,乘积的总指数记录总数。相同类别的不同副本不再另行区分。

【例11.4.4】 的10组合数是 。也可用余量u=3−x₁、v=4−x₂、w=5−x₃,得到u+v+w=2,所有上界自动满足,故有 组;对应选择数为(1,4,5)、(2,3,5)、(2,4,4)、(3,2,5)、(3,3,4)、(3,4,3)。(例完)

无限库存时,。有上下界 时,用 ;若某lᵢ<0,则需允许有限负幂,或先平移变量至非负范围。加权方程 ,pᵢ为正整数,非负变量的生成函数为 ;若兼有边界,则为 。一般上下界仍能用容斥给出有限和,不能将“没有统一简单闭式”误说成“不存在一般表达方法”。

【例11.4.5】求第一象限 内(含边界)的整点数。令aᵣ为x+2y=r的非负整数解数,则

故 ,再求和得

n=0时退化为原点,结果仍为1。(例完)

【整数拆分】正整数N写为正整数之和。是否计顺序、是否允许相同部分重复,是两个独立条件。N=3时:有序不重复为(3)、(1,2)、(2,1);无序不重复为3、2+1;有序可重复另加(1,1,1),共4种;无序可重复为3、2+1、1+1+1,共3种。这对应表11.4.1的四种类型。

给定允许部分大小a₁,…,aₖ,无序且每种最多一次的生成函数为 ;允许重复为 。指数记录总和,不记录书写顺序。

【例11.4.6】二进制表示的唯一性。只用1,2,4,8,…作不同部分,生成函数为 。有限乘积满足

任意固定n的系数在M足够大后恒为1,故每个非负整数均有唯一的有限二进制表示;正整数对应非空选择,0对应空选择。这是形式级数中逐个系数稳定的论证,不是无条件处理无穷乘积的数值极限。(例完)

【例11.4.7】将N无序、可重复地分成至多r个正部分。Ferrers图把部分从大到小画为列高,沿y=x作镜像即转置点的横纵坐标,得到共轭拆分。例如列高(6,5,3,2)共16点,转置后列高为(4,4,3,2,2,1),仍为16点。

6532
图11.4.1(a) 16=6+5+3+2的Ferrers点图,四列高度依次6、5、3、2
443221
图11.4.1(b) 横纵坐标转置后的共轭点图,六列高度依次4、4、3、2、2、1

原图列数≤r,当且仅当共轭图每列高度≤r。共轭操作可逆,故所求数为 。这是“至多r个部分”,不是“恰好r个”。沿y=x转置也不是在纸面内绕该直线旋转180度。(例完)

【例11.4.8】pᵣ(n)表示n无序拆成恰好r个正部分的数。固定r≥1,n趋于无穷时

证明:每个无序方案有至多r!个不同排序,覆盖全部有序正整数解,故 。另一方面,将降序排列的 变为 ,得到严格降序正整数,和为 ;每组有r!个不同排序,并单射进入该总和的全部有序正整数解,故

两端都渐近于 ,夹逼得到结论。严格递减的像并未覆盖所有有序正解,只是其中一个子集;不能将上界写成错误的等号。r=3为Θ(n²),r=7为Θ(n⁶)。固定r这一条件不能省略。(例完)

【定理11.4.2及推论11.4.1】N拆成恰好r个有序正部分(1≤r≤N)的方法数为 。取前r−1个部分和 ,相当于从1到N−1选r−1个分隔位置。对r求和得到所有可重复有序拆分数 。

有序且不重复时,先枚举无序的不同部分集合,每个含k个部分的集合贡献k!个顺序。可借助二元多项式 ,总数为 ;这样不会因不同方案的部分数不同而误乘一个统一阶乘。