長度爲k的可能二進制字符串

Question

我的一個朋友的號碼最近已問過這個問題：

你要算多少二進制字符串是可能的長度「K」的。約束條件：每個0在其左側都有一個1。

Answer 1

這個問題可以重寫： 如果沒有兩個連續的0，但第一個元素應該是1（否則約束失敗），那麼長度K的二進制序列有多少個可能。讓我們忘記第一個元素（我們可以做它，因爲它總是固定的）。 然後，我們得到了一個非常有名的任務，它聽起來像這樣：「長度爲K-1的二進制序列的數目沒有連續的0。」例如，可以找到解釋here

然後答案將是F（K + 1）其中F（K）是從（1 1 2 ...）開始的第K個斐波納契數。

Answer 2

∑ From n=0 to ⌊K/2⌋ of (K-n)Cn; n是字符串中的零的數量

這個想法是將每個0與1進行組合，並找到字符串的組合數，對於n個零將有n個分組給它們，因此字符串變爲（kn ）元素很長。不能超過^K/零，因爲沒有足夠的零到每個零的左側。
例如對於K = 13，n = 3的111111[10][10]1[10]