: find the number of bit strings that contain the string "01"
先算不包含"01"
x_1 x_2
|-------||-------|
11111...100000...0
0 <= x_1,x_2 <= n
x_1 + x_2 = n
非負整數解
H(2,n) = C(n+1,1) = n+1
再扣回去
2^n - (n+1)
跟遞迴解出來應該是一樣的
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.129.117