组合数学_第5章.pdf

第五章递归关系 第五章递归关系 5.1 几个典型的递归关系实例　 5.2 常系数线性齐次递归关系的基本解法　 5.3 常系数线性非齐次递归关系的解法　 5.4 迭代法求解递归关系　 5.5 生成函数方法求解递归关系 第五章递归关系 5.1 几个典型的递归关系实例 例1(错排问题 设S={1, 2, …, n}，令D(n)为S上元素的错排 数，即n个元素都不在其自然位置上的排列数），则 D(n)=(n-1)(D(n-2)+D(n-1)), n ≥3, D(1)=0, D(2)=1 证明 对于每个错排，第一位上的数字只能取2, 3, …, n 中之一。 以第一位数字的取法可将全部错排分为n-1类: P , P , …, P ，即 2 2 n 第五章递归关系 P ={(2, i , i , …, i )|i ≠t, t=2, 3, …, n}　 2 2 3 n t P ={(3,j ,j , …,j )|j ≠t, t=2, 3, …, n}　 3 2 3 n t 　…　 P ={(n, k , k , …, k )|k ≠t, t=2, 3, …, n} n 2 3 n t 易知|P |=|P |=…=|P |都是相同的，令其为d ，于是 2 3 n n D =(n-1) ·d n n 考察 P ={(2, i , i , …, i )| i ≠t, t=2, 3, …, n} 2 2 3 n t 第五章递归关系 将P2 中的错排按第二位上的数字取1或不取1分为两类，分别 记为P21, P2x ： P ={(2, 1, i , …, i )|i ≠t, t=3, 4, …, n}　 21 3 n t P ={(2, i , i , …, i )|i ≠1, i ≠t, t=3, 4, …, n} 2x 2 3 n 2 t 显见 | P21 |=D(n-2) 　 | P |=|{(i , i , …, i )|i ≠t, t=1, 2, …, n-1}|=D(n-1) 2x 2 3 n t+1 从而dn=D(n-2)+D(n-1)，故知 D(n)=(n-1)(D(n-2)+D(n-1)), n ≥3, D(0)=0, D(2)=1 第五章递归关系 例2 （Hanoi塔问题） n个圆盘，从A柱经B柱移到C柱(参见 图5.1.1) 。 要求每次只移一个圆盘； 移动过程始终保持大盘在 下，小盘在上；中途A 、B 、C 柱均可作临时柱，最终移至C 柱，则A到C 的最少移动次数为 h(n)=2h(n-1)