For any natural number n, consider all “words” of length n consisting of the letters A and B, and denote by Pn the number of all suchwords that do not contain a four-tuple AAAA of consecutive letters A, nora triple BBB of three consecutive letters B. Find the value of the expression
這應該是用遞迴解
可是好難討論阿
不太會
3 則留言:
用遞迴, 考慮 length n-1 中最後三個 letter 共 8 種 case 然後累加起來為 P_n.
可以詳解嗎
我想了一下, 我得用雙重遞迴, 以下為沒有 AAA 或 BB 的例子, 令 a_n 是長度為 n 且合法的 words 中以 A 結尾的個數, b_n 是以 B 結尾的個數, 所以 P_n = a_n + b_n
考慮一個 valid word with length n, 若最末碼為 A, 則倒數第二碼有兩種可能, (i) 若為 A 則有 b_{n-2} 種 ( 因為倒數第三碼一定是 B )
(ii) 若為 B, 則有 b_{n-1} 種
故 a_n = b_{n-1} + b_{n-2}
若最末碼為 B, 則有 a_{n-1} 種 ( 因為倒數第二碼一定是 A
故 b_n = a_{n-1}
這樣解 a_n, b_n 就可以知道 p_n 了.
張貼留言