Contoh Relasi Rekurensi: Codeword Enumeration

martha yunanda kombinatorika

Jika sebelumnya telah dipaparkan contoh relasi rekurensi tentang Menara Hanoi dan Kelinci Fibonacci, akan diuraikan pula di halaman ini Contoh lain dari Relasi Rekurensi berikutnya adalah Codeword Enumeration.

Kasus:
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