Contoh Hubungan Rekurensi: Codeword Enumeration

Jika sebelumnya telah dipaparkan pola kekerabatan rekurensi wacana Menara Hanoi dan Kelinci Fibonacci, akan diuraikan pula di halaman ini Contoh lain dari Relasi Rekurensi berikutnya yakni Codeword Enumeration.

Kasus:
Suatu sistem komputer mengidentifikasi sebuah string dengan digit desimal. String dinyatakan valid jikalau string tersebut memuat digit 0 sebanyak bilangan genap. Sebagai contoh, string 1230407869 (banyak 0 dua) yakni valid sedangkan string 120987045608 tidak valid (banyak 0 tiga). Misalkan $a_n$ yakni banyaknya codeword dengan digit yang valid, temukanlah kekerabatan rekurensi untuk $a_n$


Solusi:
Jika n=1, maka $a_1=9$,  Sebab dari 10 string satu-digit, hanya satu yaitu string 0 yang tidak valid. Relasi rekurensi untuk barisan ini sanggup diperoleh dengan memandang bagaimana string n-digit yang valid sanggup dibangun dari string n−1-digit. Ada dua cara untuk membentuk string n-digit yang valid dari string sebelumnya.

Pertama, sebuah string n-digit yang valid sanggup diperoleh dengan menambahkan string n−1 digit yang valid dengan angka selain 0. Penambahan ini sanggup dilakukan dengan 9 cara. Sehingga dengan cara ini, string n-digit yang valid sanggup dibuat dalam $9a_{n−1}$ cara.

Kedua, sebuah string n digit yang valid sanggup diperoleh dengan menambahkan 0 ke string dengan panjang n−1 yang tidak valid.(Ini menghasilkan sebuah string yang memuat digit 0 sebanyak bilangan genap alasannya string yang tidak valid dengan panjang n−1 memuat digit 0 sebanyak bilangan ganjil.) Banyaknya cara dengan jalan ini sanggup dilakukan sebanyak string n−1-digit yang tidak valid. Karena ada $10^{n−1}$ string digit desimal dengan panjang n−1, dan $a_{n−1}$ yakni valid, artinya  ada $10^{n−1}−a_{n−1}$ string n-digit yang valid yang dibangun dengan cara kedua.

Berdasarkan aturan penjumlahan, banyaknya string yang valid dengan panjang n adalah

\begin{align*} a_n &= 9a_{n-1} + (10^{n-1} - a_{n-1})\\ &= 8a_{n-1} + 10^{n-1} \end{align*}

Berbagi :