Untai biner hindar 11

Kelas untai biner (binary words) bukanlah kelas yang asing dalam kombinatorika. Ia adalah kelas untai yang simbolnya terdiri dari 0 atau 1, semisal 0010, 1110100110, dan sebagainya. Himpunan untai biner ${s_1} \ldots {s_n}$ memiliki kardinalitas $2^n$ (karena setiap ${s_i}$ dapat bernilai 0 atau 1). Sebagai contoh, terdapat ${2^3} = 8$ untai biner dengan panjang 3, yaitu 000, 001, 010, 011, 100, 101, 110, dan 111.

Bagaimana dengan kelas untai biner hindar 11? Nama kelas ini, yang dalam bahasa Inggrisnya disebut binary words avoiding two consecutive ones, terdengar tidak familiar. Dari istilahnya, dapat diketahui bahwa ia adalah kelas untai biner yang tidak memuat dua simbol ‘1’ secara berurutan. Sebagai contoh, 0010100, 101001010 adalah untai biner hindar 11, sedangkan 110111000 bukan. Tabel berikut adalah himpunan untai biner dengan panjang $n$, untuk $n = 1,2,...,5$, yang diperoleh dengan cara menuliskan semua untai biner dengan panjang $n$ tertentu, dan mencoret untai yang memuat '11'. Di baris paling bawah adalah kardinalitasnya untuk setiap $n$.

Jika diperhatikan kardinalitasnya, membentuk pola barisan apakah ia? Barisan Fibonacci! Berdasarkan pola ini, anda tentu dapat mengetahui kardinalitas kelas di atas untuk n=6,7, dan seterusnya. Salah satu kajian algoritmis tentang kelas ini diberikan oleh Vajnovszki (2001)