Suatu sistem komputer mengidentifikasi sebuah string dengan digit desimal. String dinyatakan valid jika string tersebut memuat digit 0 sebanyak bilangan genap. Sebagai contoh, string 1230407869 (banyak 0 dua) adalah valid sedangkan string 120987045608 tidak valid (banyak 0 tiga). Misalkan $a_n$ adalah banyaknya codeword dengan digit yang valid, temukanlah relasi 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 dapat diperoleh dengan memandang bagaimana string n-digit yang valid dapat 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 dapat diperoleh dengan menambahkan string n−1 digit yang valid dengan angka selain 0. Penambahan ini dapat dilakukan dengan 9 cara. Sehingga dengan cara ini, string n-digit yang valid dapat dibentuk dalam $9a_{n−1}$ cara.
Kedua, sebuah string n digit yang valid dapat diperoleh dengan menambahkan 0 ke string dengan panjang n−1 yang tidak valid.(Ini menghasilkan sebuah string yang memuat digit 0 sebanyak bilangan genap karena string yang tidak valid dengan panjang n−1 memuat digit 0 sebanyak bilangan ganjil.) Banyaknya cara dengan jalan ini dapat 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}$ adalah 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*}
Jadilah Komentator Pertama untuk "Contoh Relasi Rekurensi: Codeword Enumeration"
Post a Comment