德布魯因序列

德布勒蘊序列（De Bruijn sequence）， B(k, n)，是k元素構成的循環序列。所有長度為n的k元素構成序列都在它的子序列（以環狀形式）中，出現並且僅出現一次。

基本介紹

• 中文名：德布勒蘊序列
• 外文名：De Bruijn sequence
• 構造方法：歸納構造
• 序列：00010111屬於B(2,3)

舉例

序列00010111屬於B(2,3)。

注意到，00010111的所有長度為3的子序列為000,001,010,101,011,111,110,100，正好構成了的所有組合。

由下節的性質可知，B(2,3)應該有兩個D序列，因此第二個序列為序列00010111的逆序列11101000。

另外，由於D序列是循環序列，因此11101000和00011101是為一個序列。

性質

長度

德布勒蘊序列的長度為。

注意到，所有長度為n的k元素構成的序列總共有。而對於德布勒蘊序列中的每個元素，恰好構成一個以此元素開頭長度為n的子序列。所以德布勒蘊序列的長度為。

數量

德布勒蘊序列的數量為。