※ 引述《kb2011 (ming)》之銘言：
: Consider the collection of strings of length 10,
: Ci E {0, 1, 2, 3} for all i = 1~10
: How many of these strings have even weight?
: (C1+C2+C3+...+C10 mod 2 = 0)
: 答案是 2^10[C(10,0)+C(10,2)+C(10,4)+...+C(10,10)]
: 不知道怎麼算出來的, 請幫個忙 @@?
遞回算 求a(n)
先假設字串長度為n (n=10
Case1:最後一位元填0 or 2 則前n-1長的字串weight為偶數
↓
__...... __ __ __ __ 方法數:2*[a(n-1)]
|← n-1 →| 乘2是因為可填0or2
Case2:最後一位元填1 or 3 則前n-1長的字串weight為奇數
↓
__...... __ __ __ __ 方法數:2*[4^(n-1)-a(n-1)]
--------------
意思是長度n-1的字串個數減掉偶數和方法數
乘2是因為可填1or3
Case1+Case2
a(n)=2*[a(n-1)]+2*[4^(n-1)-a(n-1)]
=2*4^(n-1)
題目n是10
=2*4^9
=2^19
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.34.83.238