Chapter 6 Advanced Counting Techniques Discrete Mathematics Chapter 6 Advanced Counting Techniques 大葉大學 資訊工程系 黃鈴玲

6.1 Recurrence Relations(遞迴關係) Example 1. 令 {an} 表示一個滿足 遞迴式 an=an-1-an-2 的數列，其中n=2,3,…， 假設初始條件 a0=3及 a1=5，問a2, a3及a4為多少？ Sol a2 = a1-a0 = 2 a3 = a2-a1 = -3 a4 = a3-a2 = -5 Q1: Applications ? Q2: Are there better ways for computing the terms of {an}?

Exercise 6.1 1. 數列的遞迴關係和初始條件定義如下，求出序列的前五項。 (a) an = 6an-1, a0 = 2 (c) an = an-1 + 3an-2 , a0 = 1, a1 = 2 (e) an = an-1 + an-3 , a0 = 1, a1 = 2, a2 = 0

※Modeling with Recurrence Relations 我們可以使用遞迴關係式來為很多計數問題建立模型 Example 3. Compound Interest (複利) 假設某人在一個銀行帳戶存款10000元 ，並每年產生 11% 的複利，30年後，帳戶裡有多少錢？ Sol : 令 Pn 表示n年後帳戶裡的總金額 遞迴式： Pn=Pn-1 + 0.11Pn-1=1.11  Pn-1, 初始條件： P0=10000 Pn=1.11Pn-1=1.112Pn-2=1.113Pn-3 =… =1.11n  P0 ∴ P30=1.1130  P0 =228922.97

Exercise 6.1 12. 假設2002年的世界總人口數為62億，並以每年 1.3%的速率增加。 (a) 求出2002 年後，第 n 年人口總數的遞迴關係， (b) 求出2002 年後，第 n 年人口總數的明確公式。

Example 5. (The Tower of Hanoi)(河內塔) 遊戲由三根柱子及一些圓盤構成，一開始圓盤都在左邊的柱子，越下面的圓盤越大。要將 n 個圓盤都移動到中間的柱子，一次只能移動一個圓盤，可暫時借用右邊的柱子，但須永遠保持越下面的圓盤越大。令Hn表示移動n個圓盤所需的最少移動次數， 求Hn。 peg 1 peg 2 peg 3 H4 moves

1個圓盤 peg 1 peg 2 peg 3 H1 =1 2個圓盤 peg 1 peg 2 peg 3 H2 =3

3個圓盤 將上面兩個圓盤移到peg 3， 將第三個圓盤移到peg 2， 將上面兩個圓盤移到peg 2。 3步 H3 =3+1+3=7 1步 3步 H3 = 2H2 +1 peg 1 peg 2 peg 3 Sol : {Hn}的遞迴關係式為： Hn=2Hn-1+1, (n-1個 disk 先從peg 1→peg 3, 第 n 個 disk 從 peg 1→peg 2, n-1個 disk 再從 peg 3→peg 2) 初始條件：H1=1

上例中 Hn=2Hn-1+1, H1=1 ∴Hn=2Hn-1+1 =2(2Hn-2+1)+1 =22Hn-2+2+1 =22(2Hn-3+1)+2+1 =23Hn-3+(22+2+1) : =2n-1H1+(2n-2+2n-3+…+1) =2n-1+2n-2+…+1 = =2n-1

Example 6. 找出「長度為 n 且不含兩個連續0的位元字串數」的遞迴關係式及初始條件。長度為5的此種字串有幾個？ Sol : 令 an 表示長度為 n 且不含兩個連續0的位元字串數 n-2 n-1 n 1 2 n-3 … ∴遞迴式： an = an-1+an-2, n  3 初始條件： a1=2 (string : 0,1) a2=3 (string : 01,10,11) 1 an-1 種 an-2 種 1 由遞迴式可算出 a3=a2+a1=5 a4=a3+a2=8 a5=a4+a3=13

Example 7. (Codeword enumeration)(編碼的計數) 一個電腦系統將包含偶數個零的十進位字串視為 合法的編碼。令 an 代表長度為 n 的合法字串數， 找出an 的遞迴關係。 Sol : ∴ 遞迴關係式： an = 9an-1 + (10n-1-an-1) = 8an-1 + 10n-1, n  2 初始條件： a1 = 9 n-1 n 1 2 3 … an-1 種 1~9 10n-1 - an-1 種

Exercise 6.1 23. (a) 求出包含兩個連續0且長度為n的位元字串個 數的遞迴關係。 (b) 初始條件為何？ (c) 包含兩個連續0且長度為5的位元字串共有幾個？ 25. (a) 求出不包含三個連續0且長度為n的位元字串 個數的遞迴關係。 (b) 初始條件為何？ (c) 不包含三個連續0且長度為5的位元字串共有幾個？

(跳過) 6.2 解線性遞迴關係式 (部分) 求解二次遞迴關係式 an = c1an-1 + c2an-2， 其中 c1及c2為常數。

已知遞迴關係式 an = an-1 + 2an-2 (當n2) ，初始條件為 a0=2 及 a1=7，求 an 的通解。 Sol : (跳過) Example 3. 已知遞迴關係式 an = an-1 + 2an-2 (當n2) ，初始條件為 a0=2 及 a1=7，求 an 的通解。 Sol :  特徵方程式 (將遞迴式中an代入r2 ， an-1代入r ， an-2代入1)： r2 – r - 2=0  特徵方程式的根為：r1= 2 and r2 = -1  兩相異根，故通解的公式為： an= a1 r1n +a2  r2n = a12n +a2 (-1)n  用初始條件解a1及a2： ∵a0 = a1+a2 = 2, a1=2a1-a2=7 ∴a1 = 3, a2 = -1  an = 32n - (-1)n 驗算：a2 = a1 + 2a0 =11 a2= 322 - 1 =11

已知遞迴關係式 an= 6an-1 - 9an-2 (當n2) ，初始條件為a0=1及a1=6，求 an 的通解。 Sol : (跳過) Example 5. 已知遞迴關係式 an= 6an-1 - 9an-2 (當n2) ，初始條件為a0=1及a1=6，求 an 的通解。 Sol :  特徵方程式 (將遞迴式中an代入r2 ， an-1代入r ， an-2代入1)： r2 - 6r + 9 = 0  特徵方程式的二重根為： r = 3  二重根，故通解的公式為： an = a1．rn +a2．n．rn = a1．3n +a2．n．3n  用初始條件解a1及a2： ∵a0 = a1 = 1, a1 = 3a1 + 3a2 = 6 ∴ a1 = 1 and a2 = 1  an = 3n + n．3n 驗算：a2 = 6a1 - 9a0 =27 a2= 32 +2  32 =27

(跳過) Exercise 6.2 3(c) 已知遞迴關係式 an = 5an-1 - 6an-2 (當n2)，初始條件為 a0=1 及 a1=0，求 an 的通解。 (d) 已知遞迴關係式 an = 4an-1 - 4an-2 (當n2)，初始條件為 a0=6 及 a1=8，求 an 的通解。

6.5 Inclusion-Exclusion 排容原理 A,B,C,D : sets (1). |A∪B| = |A| + |B| - |A∩B| (2). |A∪B∪C| = |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C| + |A∩B∩C| A B C |A|+|B|+|C| 時 各部分被計算的次數 1 2 1 2 1 3 2 1 -|AB|-|AC|-|BC|後 1 2 1 1 +|ABC|後 (3). |A∪B∪C∪D | = ?

Theorem 1. A1, A2, …, An : sets |A1∪A2∪…∪An | = |A1|+|A2|+…+|An| -|A1∩A2|-|A1∩A3|-…-|An-1∩An| +|A1∩A2∩A3 |+|A1∩A2∩A4 |+…+| An-2∩ An-1∩An| … +(-1)n|A1∩A2∩ …∩An |

Exercise 6.6 17. 有四個集合，分別包含50,60,70和80個元素，若任兩個集合都有5個共同元素，任三個集合有1個共同元素，四個集合沒有共同元素。問此四個集合的聯集有幾個元素？