北京大学：离散数学（一）：22.1-2

1 第二十二章组合计数方法 ? 22.1 递推方程的公式解法 ? 22.2 递推方程的其他解法 ? 22.3 生成函数的定义及其性质 ? 22.4 生成函数的应用 ? 22.5 指数生成函数及其应用 ? 22.6 高级计数 2 22.1 递推方程的公式解法 ?递推方程的定义 ?递推方程的实例 ?常系数线性递推方程的求解 ?常系数线性递推方程定义 ?公式解法 ?递推方程在计数问题中的应用 3 递推方程的定义 设序列a 0 , a 1 , …, a n , …, 简记为{a n }, 一个把a n 与某些个a i （i<n）联系起来的等式 叫做关于序列 {a n } 的递推方程 当给定递推方程和适当的初值就唯一确定了序列. 例：Fibonacci数列：1，1，2，3，5，8，… ， Fibonacci数列的递推方程 f n = f n-1 + f n-2 初值 f 0 = 1，f 1 = 1 阶乘计算数列： 1，2，6，24，5！，…, 递推方程 F(n) = nF(n-1) 初值 F(1) = 1 4 例1 一个编码系统用8进制数字对信息编码，一个码是有效的 当且仅当含有偶数个7, 求n位长的有效码字有多少个？ 解 设所求有效码字为a n 个 a n = 7a n-1 + 8 n-1 ? a n-1 a n = 6a n-1 + 8 n-1 , a 1 =7 解得 a n =(6 n +8 n )/2 递推方程的实例 5 例2 Hanoi塔 问题 T(n) = 2 T(n-1) + 1，T(1) = 1 解得 T(n) = 2 n ?1 1秒移1个，64个盘子要多少时间？（5000亿年） 思考：是否存在更好的解法？ Reve难题：Hanoi塔变种，柱子个数增加，允许盘子相等. 递推方程的实例（续） 6 例3 哪种排序算法在最坏情况下复杂度比较低？ 插入排序、归并排序 插入排序 W(n) = W(n ?1) + n ?1 W(1) = 0 解得 W(n) = O(n 2 ). 归并排序，不妨设n = 2 k . W(n) = 2W(n/2) + n－1 W(1) = 0 解得 W(n) = O(nlogn) 递推方程的实例（续） 7 常系数线性齐次递推方程的定义 ? ? ? =?=== =??????? ?1210 21 )1(,...,)2(,)1(,)0( 0)(...)2()1()( k k bkHbHbHbH knHanHanHanH 其中a 1 ,a 2 ,…,a k 为常数，a k ≠ 0 称为k阶常系数线性齐次递推方程 b 0 , b 1 , …, b k-1 为k个初值 实例：Fibonacci数列的递推方程 常系数线性齐次递推方程求解 8 常系数线性齐次递推方程的公式解法 ?特征方程、特征根 ?递推方程的解与特征根的关系 ?解的线性性质 ?无重根下通解的结构 ?求解实例 ?有重根下通解结构 ?求解实例 9 特征方程与特征根 ? ? ? =?=== =??????? ?1210 21 )1(,...,)2(,)1(,)0( 0)(...)2()1()( k k bkHbHbHbH knHanHanHanH 特征方程 x k ?a 1 x k-1 ? … ? a k = 0， 特征方程的根称为递推方程的特征根 实例 递推方程 f n = f n-1 + f n-2 特征方程 x 2 ?x?1= 0 特征根 2 51 , 2 51 ?+ 10 定理1 q是非零复数，则q n 是递推方程的解 ? q是它的特征根 证： q n 是递推方程的解 ? q n ?a 1 q n-1 ? a 2 q n-2 ? …? a k q n-k = 0 ? q n-k (q k ?a 1 q k-1 ? a 2 q k-2 ? …? a k ) = 0 ? q k ? a 1 q k-1 ? a 2 q k-2 ? … ? a k = 0 ? q是它的特征根 递推方程解与特征根的关系 11 定理2 h 1 (n)和h 2 (n)是递推方程的解， c 1 ,c 2 为任意常数， 则c 1 h 1 (n)+c 2 h 2 (n)是递推方程的解. 证明 将c 1 h 1 (n)+c 2 h 2 (n)代入递推方程左边， 化简后等于0 推论：若q 1 ,q 2 ,…,q k 是递推方程的特征根， 则c 1 q 1 n +c 2 q 2 n +…+c k q k n 是递推方程的解， 其中c 1 , c 2 , …, c k 是任意常数. 解的线性性质 12 通解定义： 若对递推方程的每个解h(n)都存在一组常数c 1 ’, c 2 ’, …, c k ’ 使得h(n)=c 1 ’q 1 n +c 2 ’q 2 n +…+c k ’q k n 成立， 则称c 1 q 1 n +c 2 q 2 n +…+c k q k n 为通解. 定理3 设q 1 , q 2 , … , q k 是递推方程不等的特征根， 则H(n)= c 1 q 1 n +c 2 q 2 n +…+c k q k n 为通解. 无重根下通解的结构 13 定理的证明 证： H(n)是解. 设h(n)是递推方程的任意解， h(0), h(1), …, h(k-1)由初值b 0 , b 1 , … , b k-1 唯一确定. ? ? ? ? ? ? ? =+++ =+++ =+++ ? ??? 1 11 22 1 11 12211 021 '...'' ... '...'' '...'' k k kk kk kk k bqcqcqc bqcqcqc bccc 系数行列式 0)( 1 ≠? ∏ ≤<≤ kji ji qq 当q i ≠ q j 时 方程组有唯一解 14 例4 Fibonnaci数列，特征根为 2 51 , 2 51 ?+ ， 通解为 nn n ccf ? ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? ? + = 2 51 2 51 21 带入初值 f 0 =1, f 1 =1, 得 ? ? ? ? ? = ? ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? ? + =+ 1 2 51 2 51 1 21 21 cc cc 解得 2 51 5 1 , 2 51 5 1 21 ? ?= + = cc 11 2 51 5 1 2 51 5 1 ++ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? + = nn n f 求解实例 15 例5 H(n) ?4H(n?1) + 4H(n?2) = 0 H(0) = 0, H(1) = 1 特征方程 x 2 ?4x+4 = 0 通解 H(n) = c 1 2 n + c 2 2 n = c2 n 代入初值得： c2 n ? 4c2 n-1 + 4c2 n-2 = 0 c?2c + c = 0, c无解. 问题：两个解线性相关. 观察：n2 n 是解，且与2 n 线形无关 有重根下求解中的问题 16 定理4 若q是递推方程的e重特征根，则 q n ,nq n , …, n e-1 q n 是递推方程的线性无关的解 定理5 设q 1 , q 2 , … , q t 是递推方程的不相等的特征根， 且q i 的重数为e i ，令 n i e ieiii qncnccnH i i )...()( 1 21 ? +++= 那么通解 ∑ = = t i i nHnH 1 )()( 证明：请阅读教材 有重根下的通解结构 17 例6 H(n) + H(n-1) - 3H(n-2) - 5H(n-3) - 2H(n-4) = 0 H(0) = 1, H(1) = 0, H(2) = 1, H(3) = 2 特征方程 x 4 + x 3 ? 3x 2 ? 5x ?2 = 0 , 特征根-1,-1,-1,2, 通解为 nn cncnccnH 21 4 2 321 +?++= ))(()( ? ? ? ? ? ? ? =+??? =+++ =+??? =+ 2893 1442 02 1 4321 4321 4321 41 cccc cccc cccc cc 解得 9 2 ,0, 3 1 , 9 7 4321 ==?== cccc 解为 nnn nnH 2 9 2 )1( 3 1 )1( 9 7 )( +???= 求解实例 18 常系数线性非齐次递推方程求解 ?递推方程的标准型 ?通解结构 ?特解的求法 ?多项式函数 ?指数函数 ?组合形式 19 递推方程的标准型及通解 .0)(,0,),()(...)1()( 1 ≠≠≥=????? nfaknnfknHanHanH kk 定理6 设)(nH是对应齐次方程的通解，H * (n)是一个特解，则 )(*)()( nHnHnH += 是递推方程的通解. 证（1）H(n)是解，代入验证. （2）设h(n)是解，证明h(n)为一个齐次解与特解H * (n)之和. 0)](*)([ ...)]1(*)1([)](*)([ )()(*...)1(*)(*) )()(...)1()( 1 1 1 =???? ?????? =?????? =????? knHknha nHnhanHnh nfknHanHanH nfknhanhanh k k k h(n)-H * (n)是齐次解，即h(n)是一个齐次解与H * (n)之和. 20 f(n)为n的t次多项式，一般H * (n)也为n的t次多项式 例7 a n + 5a n-1 + 6a n-2 = 3n 2 设 a n * = P 1 n 2 + P 2 n + P 3 , 代入得 P 1 n 2 +P 2 n+P 3 +5[P 1 (n-1) 2 +P 2 (n-1)+P 3 ]+6[P 1 (n-2) 2 +P 2 (n-2)+P 3 ]=3n 2 ? ? ? ? ? =+ =+ = 0 12P 17P-29P 0 12 34- 3 12 321 21 1 PP P 288 115 24 17 4 1 288 115 , 24 17 , 4 1 2 * 321 ++= === nna PPP n ， 通解为 288 115 24 17 4 1 )3()2( 2 21 +++?+?= nncca nn n 特解的求法 21 例8 Hanoi塔 T(n) = 2 T(n-1)+1 T * (n) = P P = 2 P + 1 , P = -1 T(n) = c 2 n –1, 代入初值 T(1)=1, 得c=1, 解为 T(n) = 2 n –1. 例9 H(n)- H(n-1) = 7n 设特解P 1 n+P 2 不行，应设n 2 次项, 因为特征根是1. 设H * (n) = P 1 n 2 + P 2 n, 代入 解得 P 1 = P 2 = 7/2, 通解为 H(n) = c?1 n + 7 2 n(n+1) = c + 7 2 n(n+1) 实例 22 f(n)为指数函数 β n ，若β不是特征根，则特解为 H * (n) = Pβ n 例10 通信编码问题 a n = 6a n-1 + 8 n-1 , a 1 =7 a * n = P 8 n-1 , 代入得P = 4 通解 a n =c?6 n + 4?8 n-1 代入初值得 a n =(6 n +8 n )/2 特解的求法（续） 23 若β是e重特征根，则特解为Pn e β n 例11 H(n)– 5H(n-1) + 6H(n-2) = 2 n ， H * (n) = Pn2 n , 代入得 Pn2 n – 5P(n-1)2 n-1 + 6P(n-2)2 n-2 = 2 n 解得 P = -2 H * (n) = -n2 n+1 特解的求法（续） 24 例12 组合形式 a n - 2a n-1 = n+3 n a 0 = 0 设特解为a n * = P 1 n + P 2 + P 3 3 n ，代入 (P 1 n+P 2 +P 3 3 n )- 2[P 1 (n-1)+P 2 +P 3 3 n-1 ] = n+3 n -P 1 n+(2P 1 -P 2 )+P 3 3 n-1 = n+3 n P 1 = -1, P 2 = -2, P 3 = 3 a n = c2 n –n-2 + 3 n+1 解得 c = –1，a n = –2 n –n–2 + 3 n+1 特解的求法（续） 25 22.2 递推方程的其他解法 ?换元法 ?迭代归纳法--递归树 ?差消法 ?尝试法 ?应用实例 26 思想：通过换元转化成常系数线性递推方程 例1 0 2 12 0 2 1 2 > ? ? ? ? ? = += ? n nn a a aa 令 , 2 nn ab = 代入得 b n = 2 b n-1 + 1，b 0 = 4 解得 125,125 ??=??= n n n n ab 换元法 27 例2 归并排序 T(n) = 2 T( n/2 ) + n-1 , n = 2 k T(2) = 1 解 H(k)= 2 H(k-1) + 2 k - 1 H(1) = 1 令H * (k) = P 1 k2 k + P 2 , 解得P 1 =P 2 =1, H * (k) = k2 k + 1 通解 H(k) = C 2 k + k2 k + 1, 代入初值，得C = -1, H(k) = - 2 k + k2 k +1, T(n) = n log n– n + 1 换元法—归并排序 28 例3 计数a 1 , a 2 , … , a n 相乘（可交换）的方法数 h(n) = (4n-6) h(n-1) h(1) = 1 )!1( )!22( 24...)42)(22( )!22( 2 ]13...)52)(32[(2 )1(26...)104)(64( ... )2()104)(64( )1()64()( 1 1 ? ? = ??? ? = ???= ????= = ???= ??= ? ? n n nn n nn hnn nhnn nhnnh n n 用归纳法验证. 迭代归纳法 29 例4 错位排列问题 错位排列：{1,2,…,n}的排列a 1 a 2 …a n , a i ≠i, i=1,2,…,n， n个元素的错位排列数记作D n 将错位排列按首元素2,3,…,n分类：有n-1类， 第一位为2的类： 第二位为1： 方法数为D n-2 第二位不是1：方法数为D n-1 递推方程： D n = (n-1)(D n-1 +D n-2 ) D 1 = 0, D 2 = 1 迭代归纳法—错位排列 30 解：D n = (n-1)(D n-1 + D n-2 ) ] ! )(... !! [! )()(...)(...)( )(...)(...)( ... )()())(())(( )()()( ,)( )(][)( ...])([ n n nnn nnDnn nnnDnnn nDnnD DnDD DD DnDnDD n nn nnn n nn nn n nn nn nnnn 1 1 2 1 1 1 1 11141 13121 111121 111 01 121 1 13 2 1 12 3 1 2 11 2 12 2 211 ?+?+?= ?+?++??+ ??+?= = ?+?+??+??= ?+?+?= =?+= ?=??= =???=? ? ?? ? ? ? ? ?? ??? 迭代归纳法—错位排列 31 例5 归并排序 T(n) = 2T(n/2) + n-1， n=2 k T(2) = 1 递归树有k层，总数为 nk– (1 + 2 + … + 2 k-1 ) = nk– (2 k –1) = nlog n– n + 1 迭代归纳法—递归树 32 T(n)= 2 T(n/2) + n-1 = 2 [2 T(n/4) + n/2–1] + n-1 = 2 2 T(n/2 2 ) + n-2 + n-1 = … = 2 k-1 T(n/2 k-1 ) + n-2 k-2 + … + n-2 + n-1 = 2 k-1 T(2) + n(k-1)–(1 + 2 + … + 2 k-2 ) = 2 k-1 + n(k-1)– (2 k-1 –1) = nk– n + 1 = nlog n– n + 1 迭代归纳法—归并排序 33 例6 快速排序 算法 快速排序 Quicksort 输入：数组A[p..r] 输出：排好序的数组A Quicksort(A,p,r) 1. if p<r 2. then q←Partition(A,p,r) 3. A[p]?A[q] 4. Quicksort(A,p,q-1) 5. Quicksort(A,q+1,r) 差消法—快速排序 34 ? ? ? ? ? = ≥++= ∑ ? = 0)1( 2,1)( 2 )( 1 1 T nniT n nT n i )log()( )(log 3 1 ... 1 1 1 2 2 )1( 3 2 ... 2 1 2 1 2)1( 1 )( 2)1()1()( 2)1(2)1()1()( )1()1()(2)1()1( )(2)( 2 1 2 2 1 1 nnOnT nO nn T nnnn nT n nT nnTnnnT nnTnTnnnT nniTnTn nniTnnT n i n i = = ? ? ? ? ? ? +++ + = ++++ + = + + ? = + +?+= +?=??? ?+?+=?? ++= ∑ ∑ ? = ? = 平均情况下复杂度分析 35 )(log2ln)1ln(ln 1 3 1 ... 1 1 1 1 2 1 2 nOnx dx xnn n n =?+== ≤+++ + + + ∫ 积分近似 36 例7 1)( 2 )( 1 1 ++= ∑ ? = niT n nT n i (1) T(n)=C, 左边=O(1)， 右边= 1 2 21)1( 2 ++?=++? n n C CnnC n =O(n) (2) T(n)=cn, 左边=cn, 1)1(1)1( 1 2 )1)(11(2 1 2 1 1 +?+=++?= ++ ??+ = ++= ∑ ? = cncnnc n nn n c nci n n i 右边 尝试法—快速排序 37 (3) T(n)=cn 2 , 左边=cn 2 )( 3 2 1)]( 3 [ 2 1 2 22 31 1 2 nOn c nnO cn n nci n n i +=+++=++= ∑ ? = 右边 (4) T(n)=cnlogn , 左边=cnlogn )(log) 2ln2 1(log 1)]log( 2ln4 log 2 [ 2 1log 2 22 1 1 nOn c ncn nnnO n n n n c nii n c n i +?+= +++?= ++= ∑ ? = 右边 尝试法—快速排序 38 )log( 2ln4 log 2 ) 4 4 2ln 2 4 ( 2ln 1 ) 4 ln 2 ( 2ln 1 ] 4 ln 2 [ 2ln 1 ln 2ln log 22 22 2 22 22 nnO n n n n n n x x x xdx x xdxx n nn +?= ?? ?= ?= = ∫∫ 积分近似 39 n为输入规模，n/b为子问题输入规模， a为子问题个数，d(n)为分解及综合的代价 )/( )()/(... )/()/()/( ...)()/()/()( 1)1( ),()/()( 1 0 2211 22 i k i ik kkkkkk k bndaa ndbnad bnabndabnTa ndbnadbnTanT T bnndbnaTnT ∑ ? = ???? += ++ +++= =++= = =+= an k bb naa loglog == 分治算法 40 (1) d(n)=c ? ? ? ? ? ===+ ≠== ? ? + = 1)(log)( 1)()( 1 1 )( log anOkcOkca anOaO a a ca nT k ak k k b 二分检索 W(n) = W(n/2) + 1 a = 1, b = 2, d(n) = c W(n) = O(logn) a ki k i ik b nabndaanT log 1 0 ),/()( =+= ∑ ? = 分治与递归算法—二分检索 41 (2) d(n)=cn ? ? ? ? ? ? ? >= ? ? += ? ? + ==+ <= ? ? + = +=+= ∑∑ ? = ? = banO ba ba ca ba ba cna bannOcnkn banO ba ba cnn b a cna b cn aanT a kk k k k k a k i ik i k i ik b b )( 1/1/ 1)/( )log( )( 1/ 1)/( )()( log log 1 1 1 1 归并排序 W(n) = 2W(n/2) + n?1 a = 2, b = 2, d(n) = O(n), W(n)= O(nlogn) 分治与递归算法—二分归并 42 作业 ?复习要点 公式法 换元法 迭代归纳法 理解差消与尝试法 会应用递推方程解决组合计数问题 ?书面作业 习题二十二，3, 6, 8, 10, 11, 12,