- Dengan menggunakan hanya simbol 0, 1 dan 2, kita ingin membentuk string sedemikian rupa hingga selisih antara satu simbol dengan simbol di sebelahnya tidak lebih dari satu. Sebagai contoh, kita dapat membentuk string 011221 dan 2211010, tetapi tidak boleh membentuk string 102. Berapakah banyaknya string seperti ini yang panjangnya tepat 10 simbol?
Jika panjang simbol adalah 1, maka kita dapat menuliskannya dengan 0, 1 ataupun 2.
Untuk 0, kita dapat menuliskan 0 ataupun 1 di kanan,
Untuk 1, kita dapat menuliskan 0, 1 ataupun 2 di kanannya, sedangkan
untuk 2, kita hanya dapat menuliskan 1 ataupun 2 setelahnya.
Jika kita misalkan f(x,y) dengan x adalah panjang simbol dan y adalah simbol paling kanan, kita dapatkan:
f(x,0) = f(x-1,0) + f(x-1,1)
f(x,1) = f(x-1,0) + f(x-1,1) + f(x-1,2)
f(x,2) = f(x-1,1) + f(x-1,2)
Artinya, kita akan menghitung banyaknya kemungkinan di sebelah kirinya dengan simbol y sesuai dengan fungsi.
Program akan berhenti mencari jika x = 1 karena jika panjang simbol adalah 1, maka f(1,y) = 1 [f(1,0) = f(1,1) =
f(1,2) = 1].
f(1,0) = 1
f(1,1) = 1
f(1,2) = 1
Untuk x = 2, jika y = 0, kita hanya perlu menjumlahkan hasil pertama dan kedua dari sebelumnya. Hasil yang sama untuk y = 2. Sedangkan jika y = 1, jumlahkan ketiganya.
f(2,0) = 2
f(2,1) = 3
f(2,2) = 2
f(3,0) = 5
f(3,1) = 7
f(3,2) = 5
f(4,0) = 12
f(4,1) = 17
f(4,2) = 12
f(5,0) = 29
f(5,1) = 41
f(5,2) = 29
f(6,0) = 70
f(6,1) = 99
f(6,2) = 70
f(7,0) = 169
f(7,1) = 239
f(7,2) = 169
f(8,0) = 408
f(8,1) = 577
f(8,2) = 408
f(9,0) = 985
f(9,1) = 1393
f(9,2) = 985
f(10,0) = 2378
f(10,1) = 3363
f(10,2) = 2378
Karena paling kanan bisa bernilai 0, 1 ataupun 2, maka kita jumlahkan ketiganya. Sehingga banyaknya string adalah 2378 + 3363 + 2378 = 8119.
