-
Beberapa anak berbaris dalam satu barisan. Sang Guru memerintahkan mereka untuk mengubah posisi barisan mereka, dengan aturan: setiap anak boleh memilih untuk tetap di posisinya semula, atau bertukar dengan orang yang berdiri tepat di depan atau tepat di belakangnya (apabila ada dan belum pernah bertukar). Jika ada 3 orang anak yang berbaris, dengan urutan awal A, B, C, maka ada 3 kemungkinan hasil setelah perintah Guru dijalankan, yaitu: tetap, berubah menjadi B,A,C, atau berubah menjadi A,C,B. Berapa kemungkinan hasil yang mungkin apabila ada 15 anak yang berbaris?
Jika hanya terdapat 1 anak, maka barisan hanya bisa tetap (1).
Jika terdapat 2 anak, maka barisan bisa tetap atau bertukar (2).
Untuk barisan dengan 3 anak, barisan bisa tetap atau 2 kali bertukar (3).
Jika jumlah anak = 4, maka barisan bisa tetap, hanya 1 anak yang bertukar (3 kemungkinan), atau 2 anak bertukar (1 kemungkinan).
Misalkan ABCD = > ABCD, (ABDC, ACBD, BACD), BADC.
Untuk barisan 5 anak:
ABCDE = > ABCDE, (ABCED, ABDCE, ACBDE, BACED), (BADCE, BACED, ACBED) = 8.
Jumlah masing-masing adalah 1, 2, 3, 5, 8,… dan terlihat pola fibonacci di mana
f(n) = f(n-1) + f(n-2).
Jika diteruskan, urutan menjadi:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987.
