- Ada berapa himpunan bagian dari {1,2,…,9} sedemikian sehingga tidak ada 2 anggota yang berurutan? (misal himpunan {1,4,5} dilarang karena memiliki dua anggota 4 dan 5, sementara 4 dan 5 adalah 2 bilangan yang berurutan, sedangkan himpunan {2,4,8} boleh) {tuliskan dalam bentuk angka}
Banyaknya himpunan bagian dari:
{} hanya 1.
{1} ada 2, yaitu {} dan {1}.
{1,2} = 3, yaitu {}, {1}, {2}.
{1,2,3} = 5, yaitu {}, {1}, {2}, {3}, {1,3}.
{1,2,3,4} = 8, yaitu {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}.
Banyaknya himpunan bagian tersebut memiliki pola 1, 2, 3, 5, 8 yang mana merupakan bilangan fibonacci.
Hal ini bisa terjadi karena jika bilangan terbesar yang valid adalah n, maka kita dapat mengambil
n yang selanjutnya kita bisa mengambil n-2 ataupun tidak mengambil n dan langsung n-1.
Dengan demikian
f(n) = f(n-1) + f(n-2).
f(0) = 1
f(1) = 2
f(2) dst = 3,5,8,13,21,34,55,89. Sehingga untuk himpunan bagian dengan bilangan terbesar 9 adalah 89.
OSP Komputer Kujawab.
