（組合數學習題）遞推關系一道經典題分析與解答

文章目錄

• ​​題目​​
• ​​分析與解答​​
• ​​求解​​
• ​​程式實作(C++)​​

題目

來看下面一道題，主要用到的是組合數學中的遞推關系部分的内容。

某長度為的二進制序列，要求其中至少有連續的個出現，問：能産生多少種符合條件的序列?

分析與解答

先來一個直覺的表示：

看到這種題目自然想到要用遞推關系來解，在之前的文章（《​​（組合數學筆記）遞推關系小結及典型題分析​​》）中已經有提到一些簡單的概念與定理，大概就是通過分析題目條件，列出遞推關系式，并進行求解即可。

在本題中，這個序列要求，先設長度為的二進制序列中滿足條件的有個，則可以分為以下兩種情況：

1. 考慮長度為的序列，為已經滿足條件序列的個數，則對于下一個數（第個數），隻有和兩種選擇，是以滿足條件的序列有個。但是僅這樣考慮會有一部分沒有被考慮到，因為“”這個模式可以僅在最後一位規定好後才出現，換言之，在前面個數組成的序列中可以完全不出現“”這個模式，這就需要進行第二步的讨論；

2. 考慮前面個數組成的序列，若其中沒有出現“”，那麼為使該序列滿足題目條件，則必須在最後一位添加上之後出現“”，而隻能是下面這一種情況：

   那麼對于這種情況（末4位為“”），我們隻需考慮前面的位組成的序列即可，這個序列不考慮限制條件的話有種排列方法，但是這樣會出現前面含有“”的模式，于是在後面還要減去裡面含有“”模式的個數，而這是我們前面已經的規定好的記号，即。

綜上所述，整個遞推關系式就是：

結果中的均規定為。

求解

利用特征方程進行求解發現其根比較複雜，于是我從著名的​​整數數列線上大全​​之中尋找答案，

a(n) is the number of n-tosses having a run of 3 or more heads for a fair coin (i.e., probability is a(n)/2^n).

譯文：

a(n)是具有3個或更多正面的公平投擲的n擲次數，即機率為a(n)/2^n。

該序列的首頁：​​A050231​​，有興趣的朋友可以繼續研究，裡面還提到了Tribonacci Number，是Fibonacci Number的擴充版本。在​​這裡​​能找到這個序列的前三百位。

程式實作(C++)

這個題最初是出現在​​算法實驗題庫​​的’問題 C: 簡單的密碼’，不過從組合的觀點來看這也是一道很有意思的題。下面用C++輸出了這個序列的前30位。

#include <iostream>
using namespace std;
const int N=30;
int main()
{
    int f[N] = {0, 0, 0, 1};
    for(int n=4; n <= N; n++)
    {
        // 使用左移位計算2的n-4次幂
        f[n] = 2 * f[n - 1] + (1 << (n - 4)) - f[n - 4];
        cout<<"Length: "<<n<<", number: "<<f[n]<<"\t"<<endl;
    }
    return 0;
}      

結果：

Length: 4, number: 3
Length: 5, number: 8
Length: 6, number: 20
Length: 7, number: 47
Length: 8, number: 107
Length: 9, number: 238
Length: 10, number: 520
Length: 11, number: 1121
Length: 12, number: 2391
Length: 13, number: 5056
Length: 14, number: 10616
Length: 15, number: 22159
Length: 16, number: 46023
Length: 17, number: 95182
Length: 18, number: 196132
Length: 19, number: 402873
Length: 20, number: 825259
Length: 21, number: 1686408
Length: 22, number: 3438828
Length: 23, number: 6999071
Length: 24, number: 14221459
Length: 25, number: 28853662
Length: 26, number: 58462800
Length: 27, number: 118315137
Length: 28, number: 239186031
Length: 29, number: 483072832
Length: 30, number: 974791728