Let d and k be two non-negative integers, where k > d >= 0. A dk-binary sequence is a binary sequence that satisfies the following two constraints：
(a) d constraint：two 1's are separated by a run of consecutive 0 of length at least d
(b) k constraint：any run of consecutive 0's is of length at most k.
for example, 010010001001 is a dk-binary sequence of length 12 width d=0 and k=3. Let n indicate the length of dk-binary sequence
(47) Given n=6, d=0, k=6, then how many dk-binary sequences are there? a.8 b.16 c.32 d.64 e.128
(48) Given n=10, d=4, k=5, then how many dk-binary sequences are there? a.8 b.6 c.12 d.10 e.11
(49) Given n=14, d=1, k=14, then how many dk-binary sequences are there? a.81 b.160 c.821 d.987 e.1024
(47)我當場有想出來，就2^6答案d，(48)好像推不大出來，但答案是e(49)剛剛想出來，就不能連續1，Fibonacci number 答案d
想請問48怎麼推導會比較好？
6 則留言:
(48) 令所求為 a_n, 則 a_1 = 2
當 n<=10, 分成以下兩種case討論:
(1) 若最後一個 bit 為 0, 則前 n-1 個 bit 總共有 a_(n-1) 種, 再扣掉前 n-1 個 bit 是以 5 個 0 做為結尾的狀況 (總共只有 1 種), 所以這裡總數是 a_(n-1)-1
(2) 若最後一個 bit 為 1, 則前 n-1 個 bit 會以 10000 或者是 100000 結尾, 再前面都只能補 0, 總共 2 種可能
所以 a_n = (a_(n-1) -1) + 2 = a_(n-1)+1
=> a_10 = 11
謝謝助教的解答，每次我遇到這種要討論很多狀況的…就會變的很弱，感覺好像有缺了哪裡，或好像有重複…我也有試著這樣去分析…但算出來就是錯的…
組合的問題難免會這樣, 因為很不容易驗證, 所以真的不太好掌握, 但多多練習在經驗上還是有幫助的, 原則上還是先從小例子開始討論, 熟悉一下問題本身, 討論時記得先掌握兩個最基本的概念, 就是case要互斥, 且聯集要是所有的可能
就快要結束了, 要堅持到最後喔!
還好…原來這算難的~~我會堅持下去的，謝謝助教
張貼留言