习题11
本章目录 · 1 节
本章导读
【习题11】共34组。斐波那契数沿用 ;普通生成函数用xⁿ的系数,指数生成函数用xⁿ/n!的系数。计数涉及空对象、是否标号及时间上界时,先说明约定。
【11.1】雄蜂第n代祖先位置数。按雄只有母亲、雌有父母的理想模型,令Mₙ、Fₙ为第n代雄、雌位置数,则 ,故 。A₀=A₁=1,所以Aₙ=fₙ。统计的是每代位置,不是各代总和;共同祖先重现时,不同个体数未必等于位置数。
【11.2】交错和 。S₀=1;n≥1时
验证n=1为0。若n时成立,则 ,归纳得证。n=0不能直接使用尚未定义的f₋₁。
【11.3】(1) (n≥1)。先证明加法公式 (p,q≥1):固定p,对q归纳,q=1时由递推成立,下一项由前两项相加得到。取p=q=n即得。(2) n≥2时,。若要扩展到n=1,需先补定义f₋₁=0。
【11.4】卡西尼恒等式为 (n≥0)。令左端为Dₙ,则利用递推可得Dₙ₊₁=−Dₙ;D₀=1,所以n偶数时为1,n奇数时为−1。仅写±1会遗漏题目要求的奇偶判定。
【11.5】卢卡斯序列L₀=2,L₁=1,Lₙ=Lₙ₋₁+Lₙ₋₂。因 ,有 。故题求差恒为2,n≥0。
【11.6】求解五个递推方程,各自从题给初值起算。
(1) 。根3、4,设c3ⁿ+d4ⁿ,初值给c+d=4、3c+4d=6,故 。
(2) 。根−3为二重,常数特解3/16,故 。
(3) 。齐次根1、2,特解−n,得到 。
(4) 。根2、5,试P3ⁿ得P=−9/2,再代初值:
(5) 。令bₙ=aₙ/n!,则bₙ−bₙ₋₁=1、b₀=2,故 。
【11.7】已知 有解Hₙ=3ⁿ+4ⁿ+2。代入后3ⁿ、4ⁿ的系数分别为0,常数项为6,所以多项式 在3、4处为0。写为K(x−3)(x−4),由2(C₀+C₁+C₂)=6得6K=3。故 。
【11.8】n条简单闭曲线,两两横截相交于两点,无三条共点。第1条把平面分成2区;第n条(n≥2)有2(n−1)个不同交点,被分成同样多的弧段,每段增加一区。故R₀=1、R₁=2、Rₙ=Rₙ₋₁+2(n−1),得到 (n≥1)。若允许曲线自交或相切,仅有原题的交点数描述不足以保证此式,应加上这些通常的画图条件。
【11.9】双汉诺塔有n对等大的圆盘,同大小允许叠放,仍不允许大盘压在小盘上。算法:把较小的n−1对由A移到B,把最大的两个盘依次由A移到C,再把B上的n−1对移到C。T₀=0,,故 。每步移动一个盘,不能把一对盘算成一次移动;本题要求的是所设算法的次数。
【11.10】黄金矩形。设AB=1、AC=φ=(1+√5)/2,左侧去掉单位正方形ABFE后,余矩形短边为φ−1、长边为1。因φ²=φ+1,,所以余矩形转过90度后与原矩形相似。每次都从长边方向切掉一个最大正方形,余矩形的长短比仍为φ,归纳即得所有后续矩形相似。
【11.11】投资有先后年度,每年选择a花1单位,或选择b、c之一花2单位。令aₙ为恰好花完n单位的年度序列数,空序列a₀=1,a₁=1;按最后一次投资得 。特征根2、−1,故 。若不区分年度顺序,计数模型会变成另一个不定方程问题,不能使用本答案。
【11.12】长度n的01串不含11。n≥2时末位0对应任意n−1位合法串,末尾01对应任意n−2位合法串,故c₀=1、c₁=2、cₙ=cₙ₋₁+cₙ₋₂,答案cₙ=fₙ₊₁。也可逐位交换0、1,转为正文不含00的同构问题。
【11.13】每秒距离依次为1,2,4,…,若沿正方向直线运动,第t秒末 ,t≥0。若沿负方向则为4−2ᵗ。原题只给距离而未给运动方向,若允许中途任意转向,位置不能唯一确定;不能把路程条件直接当作带符号位移条件。
【11.14】1×n格用红蓝二色,不允许相邻红。以蓝为0、红为1,对应11.12,故方案数为fₙ₊₁,n=0时为空涂色1种。
【11.15】两种信号分别耗时2μs、3μs。先令cₙ统计总时长恰为nμs的信号串,允许空串,c₀=1、c₁=0、c₂=1,n≥3有 。初值也可统一为c₀=1、负下标cₙ=0,再从n=1递推。
c₀到c₁₂依次为1,0,1,1,1,2,2,3,4,5,7,9,12。故恰好12μs为12种;若“12μs内”按不超过12μs理解,且不计空信息,则是 种。若连空串也允许则为48种。三种口径应分开,不能在相同答案中混用。
【11.16】。与几何级数相乘得a₀=1,a₁=2,n≥2时aₙ=1;也可写A=1+x+x/(1−x)。
【11.17】A(x)=1+3x+2x²,cₙ=5ⁿ,故C(x)=1/(1−5x)。由AB=C得
从而 。前几项1,2,17,70。原题cₙ是5ⁿ,不是常数5。
【11.18】普通生成函数:(1) ;(2) ;(3) 。
【11.19】普通生成函数的十条运算法则。l为非负整数,各式在形式级数意义下逐个比较系数;第7条额外使用收敛总和。
(1) bₙ=αaₙ,逐项数乘得B=αA。
(2) cₙ=aₙ+bₙ,逐项相加得C=A+B。
(3) cₙ=Σᵢ₌₀ⁿaᵢbₙ₋ᵢ,由Cauchy乘积得C=AB;每个固定系数的求和都是有限的。
(4) bₙ在n<l时为0、n≥l时为aₙ₋ₗ,则 ,即右移补0。
(5) bₙ=aₙ₊ₗ,先减去前l项再除以xˡ,,l=0时前面的和为空和0。
(6) bₙ=Σᵢ₌₀ⁿaᵢ,由与1/(1−x)卷积得B=A/(1−x)。
(7) ,且收敛。b₀=A(1),n≥1有bₙ−bₙ₋₁=−aₙ₋₁,故 。总和不收敛时不能用A(1)作常数代入。
(8) bₙ=αⁿaₙ,直接换元得B(x)=A(αx)。
(9) bₙ=naₙ,逐项微分得B(x)=xA′(x)。
(10) bₙ=aₙ/(n+1),零常数积分得 ,分子最低次为x,除以x后仍为普通形式级数。
【11.20】a₀=2、aₙ=3aₙ₋₁。对n≥1乘xⁿ求和得A−2=3xA,因此A=2/(1−3x),aₙ=2·3ⁿ。
【11.21】四种元素库存无限,n组合的普通生成函数:(1)各类出现奇数次,;(2)a₁不出现,a₂至多一次,a₃、a₄不限,;(3)每类至少10次,。
【11.22】3元、4元、20元邮票恰好贴满r元。(1)不计次序,。(2)排成一行计次序,一个位置可贡献x³、x⁴、x²⁰,任意长度串的生成函数为 。常数项1为空串;对r>0的答案没有影响。
【11.23】n为奇数,将同样苹果分给三个不同孩子,第一、二人的数不同。若“恰好分给3个孩子”表示每人至少1个,则n≥3时总数 ;第一、二人同为t的方案中1≤t≤(n−1)/2,共(n−1)/2种。因此
n=1时不可能每人都有,答案0。若允许某个孩子分到0个,总数 ,相等数的t从0到(n−1)/2,共(n+1)/2种,此时答案变为(n+1)²/2。两种条件不能省略。
【11.24】A耗时1μs,B、C各耗时2μs。令aₙ统计恰好nμs,先包含空串以建立初值a₀=1、a₁=1,则 。对n≥1这是恰好用时的非空信息数。若按题中“nμs内”表示不超过n,则非空串总数为
n=0时此式为0,符合不考虑空串的要求。
【11.25】整数边三角形周长为2n+1,n≥1。先按全等视为同一个三角形,不区分边的命名。设三边a≤b≤c,则三角不等式等价于每边≤n。令u=n−a、v=n−b、w=n−c,得到u≥v≥w≥0且u+v+w=n−1,反向也必给出正整数边。因此答案为n−1的至多三个部分的拆分数:
具体可计算 :减去最小部分w后,剩余有序两部分由较小者0到⌊(n−1−3w)/2⌋确定。按n−1除以6的余数分别化简即可得闭式。若将AB、BC、CA视为有标签的三条边,则要数所有有序非负三元解,答案为 ,不能对所有无标签方案一律乘6,因为等腰、等边有重复。
【11.26】指数生成函数:(1)aₙ=n!,则 ;(2)aₙ=2ⁿn!,则 ;(3)aₙ=(−1)ⁿ,则 。
【11.27】两个指数生成函数的乘积满足
因为乘积中 。与普通生成函数卷积相比,这里多了二项式系数,反映n个有编号位置在两类中的分配。
【11.28】红、绿各出现偶数次,蓝、橙不限。指数生成函数为 。n≥1时方案数 ;n=0时为1,不是把常数项1丢掉后得到的3/4。
【11.29】n位数由1、3、5、7、9组成,1和3各出现偶数次,其他三类不限。指数生成函数 ,故n≥1时共有 个。首位没有0,无须再减去前导0;n=0作为空串计数为1,但不称为零位整数。
【11.30】字母表大小n>1,指定不同a、b均出现,长度k>1。由容斥,答案 :扣去不含a及不含b的串,再加回两者均不含者。n=2时最后一项为0。
【11.31】证明 (n≥1)。先取正整数x=m:n个不同球放入m个有编号盒,按使用的非空盒数k分类,左边mⁿ,右边先分k块再单射编号,因而相等。两端是次数≤n的多项式,在无穷多个正整数上相等,所以对任意实数或复数x也相等。n=0时若扩展求和至k=0,空降阶乘为1,恒等式仍成立。
【11.32】5项不同任务分给4个不同的人,每人至少一项。只有一人得到2项,其余每人1项,故 。等价于 。
【11.33】n=2ᵏ、k≥1个互异数同时求最大最小。算法MaxMin:n=2时比较一次返回(min,max);否则分为相等的两半,递归各得(min₁,max₁)、(min₂,max₂),再比较min₁与min₂、max₁与max₂,返回较小的最小值和较大的最大值。比较次数 ,故 。每个二元叶需一次比较,n/2个叶之间的n/2−1个内部结点各需两次,总数同为n/2+2(n/2−1)。这里的次数不依赖输入具体次序。
【11.34】归并计逆序。递归函数返回“有序数组、逆序数”;长度≤1时返回原数组、0。两半返回L、Iₗ和R、Iᵣ后,用双指针i、j归并,置I=Iₗ+Iᵣ;若L[i]≤R[j],输出L[i],i加1;否则输出R[j],并将len(L)−i加到I,j加1。任一半耗尽后直接追加另一半。相等值不构成严格逆序,故应放在≤分支。
例中L=(1,4,5)、R=(2,3,6),取右侧2、3时分别增加2,共4个跨半逆序。对排列263451,算法得到8,与直接枚举的(2,1)、(6,3)、(6,4)、(6,5)、(6,1)、(3,1)、(4,1)、(5,1)一致。
若仅计元素之间的关键字比较,n=2ᵏ时最坏次数满足W(1)=0、W(n)=2W(n/2)+n−1,故 。具体输入可能提前耗尽一半,实际比较次数可能更少,不能把这个最坏值称为每次运行都相等的次数。统计逆序只在归并时增加常数次算术操作,整体时间仍为Θ(n log n),普通临时归并数组空间为O(n)。
