Pak Dengklek memiliki 10 pot bunga dengan tiap – tiap pot bunga ditanami jenis bunga yang unik. Pot-pot bunga tersebut diletakkan sejajar dalam satu baris. Suatu hari, Pak Dengklek memutuskan untuk mengubah susunan pot-pot bunga tersebut dengan syarat tidak boleh ada sebarang dua pot bunga yang bersebelahan pada susunan sebelumnya akan tetap bersebelahan pada susunan yang baru. Berdasarkan syarat tersebut, berapa banyak susunan pot-pot bunga baru dapat dibuat oleh Pak Dengklek.
Jawaban: ……………. {tuliskan jawaban dalam bentuk angka saja}
Misalkan ada N bunganya, dinomori dari 1 sampai N. Anggap urutan awalnya 1, 2, 3, 4, ... , N.
Maka permasalahannya menjadi: berapa banyak permutasi dimana tidak ada dua bunga dengan nomor berurutan yang bersebelahan.
Permasalahan ini dapat diselesaikan dengan dynamic programming:
misalkan F(N, K) menyatakan banyaknya permutasi bilangan 1 sampai N dimana ada tepat K buah nomor berurutan yang bersebelahan. Soal meminta kita mencari F(10, N). Contohnya, permutasi 1 4 2 3 7 5 6 dan 1 5 2 3 4 7 6 memiliki dua buah nomor berurutan yang bersebelahan.
Memikirkan transisi F(N, K) dari elemen-elemen sebelumnya cukup sulit, lebih baik kita berpikir terbalik dan mencari tahu F(N, K) akan menambahkan siapa saja di F(N+1, ...).
Anggap kita sudah menghitung F(N, K), jadi kita punya semua permutasi N elemen dengan K buah nomor berurutan yang bersebelahan. Kita sekarang ingin meletakkan bilangan N+1 agar menjadi permutasi N+1 bilangan. Ada 3 kasus:
transis siap, tinggal membuat tabelnya saja
| N\K | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 3 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 11 | 9 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 53 | 44 | 18 | 4 | 1 | 0 | 0 | 0 | 0 | 0 |
| 6 | 309 | 265 | 110 | 30 | 5 | 1 | 0 | 0 | 0 | 0 |
| 7 | 2119 | 1854 | 795 | 220 | 45 | 6 | 1 | 0 | 0 | 0 |
| 8 | 16687 | 14833 | 6489 | 1855 | 385 | 63 | 7 | 1 | 0 | 0 |
| 9 | 148329 | 133496 | 59332 | 17304 | 3710 | 616 | 84 | 8 | 1 | 0 |
| 10 | 146857 | 1334961 | 600732 | 177996 | 38934 | 6678 | 924 | 108 | 9 | 1 |
Jadi, jawabannya 1468457
Masuk untuk menulis jawaban
Galang, menurut saya itu masih salah. misal pada awalnya pot bunga dinomori 1 2 3 4 5 6, arti kata "bersebelahan" artinya misal setelah diurutkan itu jadinya 2 1 6 3 5 4 itu menurut saya tetap tidak memenuhi jawaban karena 1 dan 2 awalnya bersebelahan. karena menurut saya bersebelahan berhubungan timbal balik 1 dan 2 bersebelahan itu sama seperti 2 dan 1 bersebelahan.
Menurut saya, problem ini sama seperti problem menaruh N king di kotak chess NxN dengan tiap babris dan kolomnya hanya ada 1 king dan tidak ada king yang saling menyerang. Saya sudah menemukan solusi menggunakan kombinasi namun sengaja tidak ditulis disini.