CHAPTER 8 Advanced Counting Techniques
Banyak problem counting yang tidak dapat dipecahkan dengan menggunakan hanya aturan dasar, kombinasi, permutasi, dan aturan sarang merpati. Misalnya:
Ada berapa banyak string biner dengan panjang n yang tidak memuat 2 angka nol berurutan? Untuk memecahkan ini, misalkan an = banyaknya string tsb panjang n. Dapat ditunjukkan kemudian bhw an+1 = an + an-1. Dengan memecahkan persamaan ini kita dapat mencari an.
Relasi Recurrence Definisi. Relasi Recurrence untuk barisan {an} adalah persamaan yang menyatakan an dalam salah satu atau lebih bentuk a0, a1, …, an-1 untuk semua n dengan n n0 dimana n0 bilangan bulat nonnegatif. Barisan {an} tersebut dikatakan sebagai solusi dari relasi recurrence ini bila an memenuhi relasi recurrence.
8.1 APPLICATIONS OF RECURRENCE RELATIONS
Contoh 1 Misalkan seseorang menabung Rp. 100,000 di bank dengan bunga 12% per tahun. Berapa banyak uangnya setelah 30 tahun?
Solusi. Misal Pn menyatakan banyaknya uang dalam tabungan setelah n tahun. Maka, Pn = Pn-1 + 0.12 Pn-1 = (1.12) Pn-1, dengan P0 = 100,000. Dengan pendekatan iteratif: P1 = (1.12)P0 P2 = (1.12)P1 = (1.12)2 P0 P3 = (1.12)P2 = (1.12)3 P0
Pn = (1.12)Pn-1 = (1.12)n P0
Contoh 2 Sepasang kelinci ditaruh di suatu pulau. Pasangan kelinci ini tidak akan beranak sampai berumur 2 bulan. Setelah berumur 2 bulan, setiap sepasang menghasilkan sepasang yg lain setiap bulannya. Tentukan relasi recurrence dari jumlah pasangan setelah n bulan, bila tidak ada kelinci yg mati. Solusi. Misalkan fn: jumlah pasangan kelinci setelah n bulan. Maka, f1 = 1, f2 = 1. Untuk mencari fn, tambahkan jumlah pasangan pada bulan sebelumnya, fn-1, dengan jumlah pasangan yang baru lahir, fn-2. Jadi, fn = fn-1 + fn-2.
Menara Hanoi Merupakan sebuah puzzle populer yang ditemukan oleh seorang matematikawan Perancis Edouard Lucas pada abad 19. Terdapat menara dengan 3 tiang untuk meletakkan sejumlah disk berukuran berbeda. Awalnya semua disk terletak secara terurut pada tiang pertama dengan disk terbesar paling bawah Aturan: Satu disk dapat dipindahkan setiap waktu dari satu tiang ke tiang lain selama disk tsb tidak berada di atas disk yang lebih kecil. Tujuan: Memindahkan semua disk ke tiang kedua dengan disk terbesar di urutan paling bawah.
Menara Hanoi (2) • Misalkan Hn: banyaknya langkah yg diperlukan untuk memindahkan n disk dalam masalah menara Hanoi. • Kita mulai dengan n disk pada tiang 1. Kita dapat memindahkan n-1 disk paling atas dengan mengikuti aturan ke tiang 3 dalam Hn-1 langkah. • Kemudian, dengan menggunakan 1 langkah kita bisa memindahkan disk terbesar ke tiang 2. • Selanjutnya, pindahkan n-1 disk dari tiang 3 ke tiang 2, dengan mengikuti aturan dalam Hn-1 langkah. Sehingga kita telah memecahkan puzzle dengan banyak langkah: Hn = 2Hn-1 + 1 dan H1 = 1.
Menara Hanoi (3) • Untuk mencari solusinya, dilakukan proses iteratif: Hn = 2Hn-1 + 1 = 2(2Hn-2 + 1)+1 = 22Hn-2 + 2 +1 = 22(2Hn-3 +1) + 2 +1 = 23Hn-3 + 22 + 2 +1 : = 2n-1H1 + 2n-2 + 2n-3 + … + 2 +1 = 2n-1 + 2n-2 + 2n-3 + … + 2 +1 (deret geometri) = 2n - 1
• Jadi, untuk memindahkan 64 disk diperlukan langkah sebanyak: 264 - 1 = 18,446,744,073,709,551,615.
Variasi Menara Hanoi Terdapat banyak variasi dari masalah Menara Hanoi. Yang tertua dan paling menarik adalah Reve’s puzzle (Henry Dudeney, 1907). Reve’s puzzle: Sama seperti masalah Menara Hanoi namun menggunakan 4 tiang.
• Hingga kini belum ditemukan jumlah langkah minimum untuk puzzle dengan n disk. • Conjecture: sama dengan jumlah langkah dalam algoritma Frame dan Stewart (1939).
Contoh 3 Ada berapa banyak string biner dengan panjang n yang tidak memuat 2 angka nol berurutan? Misalkan an string biner dengan panjang n yang tidak memuat 2 angka nol berurutan. Tentukan relasi recurrence untuk an. Solusi. Periksa: a1 = 2 dan a2 = 3. Ada dua cara mendapatkan string biner dengan panjang n yang tidak memuat 2 angka nol berurutan: string biner dengan panjang n-1 yang tidak memuat 2 angka nol berurutan
1
an-1
string biner dengan panjang n-2 yang tidak memuat 2 angka nol berurutan
10
an-2 an = an-1 + an-2
Contoh 4 (Enumerasi Katakode) Suatu string desimal merupakan katakode yang valid dalam suatu sistem komputer jika string tersebut memuat sejumlah genap digit 0. Contoh. 1230550821 valid dan 120028790 tidak valid. Misalkan an banyaknya katakode valid dengan panjang n. Tentukan relasi recurrence untuk an. Solusi. Periksa: a1 = 9. Ada dua cara mendapatkan katakode valid panjang n: Menambahkan 1 digit selain ‘0’ pada katakode valid panjang n-1
9an-1
Menambahkan 1 digit ‘0’ pada katakode tak valid panjang n-1
10n-1 - an-1 an = 8an-1 + 10n-1
Soal (Bilangan Catalan) Cn adalah banyaknya cara untuk mengelompokkan perkalian n+1 bilangan x0 . x1 . x2 … xn, untuk menentukan urutan perkalian. Tentukan relasi recurrence untuk Cn.
8.2 SOLVING LINEAR RECURRENCE RELATIONS
Relasi recurrence linear homogen berderajat k dengan koefisien konstan Bentuk umum: an = c1 an-1 + c2 an-2 + … + ck an-k, dengan c1, c2, …, ck bilangan real dan ck 0. Contoh 1. 1. Pn = (1.12)Pn-1 2. fn = fn-1 + fn-2 3. Hn = 2Hn-1 + 1 4. an = an-1 + (an-2)2 5. Tn = nTn-2
homogen linear berderajat 1 homogen linear berderajat 2 linear tapi tak homogen tak linear koefisien tak konstan
Hanya mengkaji relasi linear dengan koefisien konstan!
Mencari solusi Langkah dasar dalam memecahkan relasi recurrence homogen linear adalah mencari solusi dalam bentuk an = rn dengan r konstan. an = rn adalah solusi dari an = c1 an-1 + c2 an-2 + … + ck an-k jika dan hanya jika rn = c1 rn-1 +c2 rn-2 + … + ck rn-k. Bila kedua ruas dibagi dengan rn-k diperoleh: rk - c1 rk-1 - c2 rk-2 - … - ck-1 r - ck = 0. Persamaan ini disebut persamaan karakteristik dari relasi recurrence. Solusi dari persamaan ini disebut akar karakteristik.
Solusi relasi recurrence homogen orde 2 dengan akar berbeda Teorema 1 Misalkan c1, c2 bilangan real dan r2 - c1r - c2 = 0 mempunyai dua akar berbeda r1 dan r2. Maka semua solusi dari relasi recurrence an = c1 an-1 + c2 an-2 berbentuk an = 1r1n + 2r2n, n=0,1,2,… dengan 1 dan 2 konstan. Bukti. Lihat di buku!
Contoh 2 Carilah solusi dari an = an-1 + 2an-2 dengan a0 = 2 dan a1 =7. Solusi. Persamaan karakteristiknya r2 - r - 2 = 0, mempunyai akar r = 2 dan r = -1. Menurut Teorema 1, solusi relasi recurrence berbentuk an= 1 2n + 2 (-1)n . Karena a0= 2 dan a1= 7, diperoleh an = 32n - (-1)n .
Soal 1 Tentukan formula eksplisit dari bilangan Fibonacci. Ingat bahwa bilangan Fibonacci fn memenuhi relasi fn = fn-1 + fn-2 dan kondisi awal f0=1, f1=1
Solusi relasi recurrence homogen orde 2 dengan akar tunggal Teorema 2 Misalkan c1, c2 bilangan real dengan c2 0 dan r2 - c1r - c2 = 0 mempunyai hanya satu akar r0. Maka semua solusi dari relasi recurrence an = c1 an-1 + c2 an-2 berbentuk an = 1 r0n + 2 nr0n, n=0,1,2,… dengan 1 dan 2 konstan. Bukti. Latihan!
Soal 2 Tentukan solusi dari relasi recurrence an = 6an-1- 9an-2 dengan kondisi awal a0 = 1 dan a1 = 6.
Solusi relasi recurrence homogen orde n dengan akar berbeda Teorema 3 Misalkan c1, c2, …, ck bilangan real dan persamaan karakteristik rk - c1 rk-1 - c2 rk-2 - … - ck-1 r - ck = 0 mempunyai k akar r1, r2, …, rk yang berbeda. Maka, solusi relasi recurrence an = c1an-1 + c2an-2 + … + ckan-k selalu berbentuk an = 1r1n + 2r2n + … + krkn , n=0,1,2,… dengan i , i=0,1,…,k konstan.
Contoh 3 Tentukan solusi dari relasi recurrence an = 6an-1 – 11an-2 + 6an-3 dengan kondisi awal a0=2, a1=5 dan a2=15. Solusi. Persamaan karakteristiknya r3 - 6r2 + 11r - 6 = 0. Jadi akar-akarnya r=1, r=2 dan r=3. Dengan demikian, solusinya berbentuk an = 11n + 22n + k3n . Dari kondisi awalnya diperoleh an = 1 - 2n + 2 3n .
Solusi relasi recurrence homogen orde k Teorema 4 Misal c1, c2, …, ck bilangan real dan persamaan karakteristik rk - c1 rk-1 - c2 rk-2 - … - ck-1 r - ck = 0 mempunyai t akar r1, r2, … , rt berbeda dengan multiplisitas m1, m2, … , mt (m1+ m2 + … + mt = k). Maka solusi relasi recurrence
an = c1 an-1 + c2 an-2 + … + ck an-k selalu berbentuk an = (1,0 + 1,1n + … + 1,m1-1 nm1-1)r1n
+ (2,0 + 2,1n + … + 2,m2-1 nm2-1)r2n + … + (t,0 + t,1n + … + t,mt-1 nmt-1)rtn
Contoh 4 Tentukan solusi dari relasi recurrence an = -3an-1 - 3an-2 - an-3 dengan kondisi awal a0 = 1, a1 = -2 dan a2 = -1. Solusi. Persamaan karakteristiknya r3 + 3r2 + 3r +1 = 0. Jadi akarnya r = -1 dgn multiplisitas 3. Dengan demikian, solusinya berbentuk an = 1,0 (-1)n + 1,1 n (-1)n + 1,2 n2 (-1)n . Dengan memandang kondisi awalnya diperoleh a = (1 +3n-2n2) (-1)n.
Relasi recurrence tak homogen linear dengan koefisien konstan Contoh 5.
an = 3an-2 + 5n
Secara umum, an = c1 an-1 + c2 an-2 + … + ck an-k + F(n) dengan ci , i=0,1,2,… konstan dan F(n) fungsi tak nol. an = c1an-1+c2an-2+ … + ck an-k disebut relasi recurrence homogen yang berkaitan.
Contoh 6. an = an-1 + 2n an = an-1 + an-2 + an-3 + n!
Teorema 5 Jika {an(p)} adalah solusi khusus dari relasi recurrence tak homogen linear dengan koefisien konstan an = c1an-1 + c2an-2 + … + ckan-k + F(n) maka setiap solusi berbentuk {an(p) + an(h)}, dengan {an(h)} solusi relasi recurrence homogen yang berkaitan an = c1an-1 + c2an-2 + … + ckan-k.
Contoh 7 Tentukan semua solusi dari relasi recurrence an = 3an-1 + 2n.
Solusi. Karena F(n) = 2n adalah polinom berderajat satu, maka kita coba polinom berderajat satu pn = cn + d, dengan c dan d konstan untuk mendapatkan solusi khusus. Didapat, pn = 3pn-1 + 2n cn+d = 3(c(n-1)+d) + 2n (-2c-2)n + (3c-2d) = 0 Sehingga c = -1 dan d = -3/2. Jadi, solusi khususnya an(p) = -n - 3/2.
Contoh 7 (2) Solusi homogen dari relasi homogen yang berkaitan, an = 3an-1 adalah an(h) = 3n, dengan konstan. Menurut Teorema 5, solusi umum dari an = 3an-1 + 2n adalah an = an(p) + an(h) = -n - 3/2 + 3n. Jika diketahui a1 = 3, maka solusi menjadi an = -n - 3/2 + (11/6) 3n.
Contoh 8 Tentukan semua solusi dari relasi recurrence: an = 5an-1 - 6an-2 + 7n. Solusi. Solusi homogennya adalah an(h) = 13n + 22n. Karena F(n) = 7n, solusi khusus yg perlu dicoba adalah an(p) = c 7n. Maka, c 7n = 5c 7n-1 – 6c 7n-2 + 7n. Diperoleh c = 49/20. Jadi, solusi umumnya: an = 13n + 22n + 49/20 7n.
Teorema 6 Misalkan {an} memenuhi relasi recurrence tak homogen linear an = c1an-1 + c2an-2 + … + ckan-k + F(n) dengan ci , i=1,2,…,k bilangan real dan F(n) = (btnt + bt-1nt-1 + … + b1n + b0) sn dengan bi , i=0,1,…,t dan s bilangan real. Jika s bukan akar dari persamaan karakteristik relasi recurrence homogen yang berkaitan, maka terdapat solusi khusus yang berbentuk (ptnt + pt-1nt-1 + … + p1n + p0) sn Jika s akar dari persamaan karakteristik dengan multiplisitas m, maka terdapat solusi khusus yang berbentuk F(n) = nm (ptnt + pt-1nt-1 + … + p1n + p0) sn
Contoh 9 Carilah solusi khusus dari relasi recurrence an = 6an-1 - 9an-2 + F(n) bila 1. F(n) = 3n, 2. F(n) = n 3n, 3. F(n) = n2 2n, dan 4. F(n) = (n2+1) 3n Solusi. Solusi homogennya adalah an(h) = 13n + 2n3n. Dan solusi khususnya adalah 1. an(p) = p0 n2 3n. 2. an(p) = n2 (p1n+p0)3n. 3. an(p) = (p2n2+p1n+p0)2n. 4. an(p) = n2(p2n2+p1n+p0)3n.
Contoh 10 – Menara Hanoi Tentukan solusi dari relasi recurrence Hn = 2Hn-1 + 1, H1 = 1, dan H2 = 3 Solusi. Relasi homogen yang berkaitan adalah Hn = 2Hn-1 dan solusi homogennya Hn(h) = 2n. Karena F(n) = 1 = 1n, maka solusi khususnya adalah Hn(p) = p0 1n = p0. Sehingga solusi umumnya adalah Hn = 2n + p0 Dengan memandang H1 = 1 dan H2 = 3 diperoleh =1 dan p0= -1. Jadi, Hn = 2n - 1
Soal 3 • Ada berapa cara untuk menutup suatu papan persegi panjang berukuran 2 x n dengan menggunakan papan-papan kecil yang berukuran 1 x 2 dan 2 x 2.
• Misalkan an adalah jumlah n bilangan bulat positif pertama. Berikan formula eksplisit dari an.
