Dalam matematika, fungsi pembangkit adalah sebuah cara menyatakan suku-suku dari barisan takhingga sebagai koefisien-koefisien suatu deret pangkat formal. Deret yang dihasilkan proses ini disebut dengan fungsi pembangkit dari barisan tersebut. Berbeda dengan deret pada umumnya, deret pangkat formal tidak perlu konvergen: malahan, fungsi pembangkit sebenarnya tidak dianggap sebagai sebuah fungsi, dan "variabel" pada fungsi adalah besaran yang tidak terdefinisi. Fungsi pembangkit pertama kali diperkenalkan oleh Abraham de Moivre di tahun 1730, dalam upaya menyelesaikan permasalahan rekursi perulangan linear secara umum.[1] Deret pangkat formal dapat diperumum ke bentuk multi-"variabel", untuk mencatat informasi multidimensi dari barisan bilangan.

Terdapat berbagai tipe fungsi pembangkit, beberapa diantaranya fungsi pembangkit biasa, fungsi pembangkit eksponensial, deret Lambert, deret Bell, dan deret Dirichlet; definisi dan contoh mengenai tipe-tipe fungsi tersebut akan dijelaskan dibawah. Setiap barisan pada prinsipnya memiliki sebuah fungsi pembangkit untuk setiap tipe fungsi pembangkit (kecuali deret Lambert dan Dirichlet, yang memerlukan indeks barisan dimulai dari 1 ketimbang 0), namun tingkat kesulitan untuk menggunakan setiap tipe dapat berbeda secara signifikan. Tipe fungsi pembangkit yang paling sesuai untuk suatu konteks, jika ada, akan bergantung pada sifat dari barisan dan detail dari masalah yang dikerjakan.

Fungsi pembangkit umumnya dinyatakan dalam bentuk tertutup (ketimbang sebagai sebuah deret), lewat beberapa ekspresi yang terdefinisi bagi deret formal. Ekspresi-ekspresi ini diterapkan pada variabel—yang tak terdefinisi -- , dan dapat melibatkan operasi aritmetika, diferensiasi, komposisi fungsi dengan fungsi-fungsi pembangkit lainnya. Karena operasi-operasi ini juga terdefinisi pada fungsi, hasil yang didapatkan terlihat sebagai fungsi terhadap . Lagipula, ekspresi bentuk tertutup dapat diinterpretasi sebagai sebuah fungsi yang dapat dievaluasi pada suatu nilai , sehingga pengembangan deret fungsi tersebut menghasilkan deret formal; hal ini menjelaskan asal usul "fungsi pembangkit". Tapi interpretasi itu tidak diharuskan perlu dilakukan, karena deret formal tidak harus menghasilkan deret konvergen ketika nilai taknol disubtitusi ke . Selain itu, tidak semua ekspresi yang berlaku pada fungsi terhadap dapat digunakan (secara berarti) untuk deret formal; sebagai contoh, pangkat negatif dan pecahan dari pada fungsi tidak memiliki padanan deret formal.

Fungsi pembangkit bukan merupakan fungsi dalam artian formal, yakni sebagai sebuah pemetaan dari sebuah domain ke suatu kodomain. Fungsi pembangkit terkadang disebut sebagai deret pembangkit.[2] Fungsi pembangkit berguna untuk membantu menyelesaikan berbagai masalah pencacahan, rekursi, dan relasi pengulangan.

Definisi

sunting

Beberapa penulis memberikan definisi informal dari fungsi pembangkit:

(terj.) Fungsi pembangkit adalah alat yang agak mirip dengan sebuah tas. Ketimbang membawa banyak benda kecil secara terpisah, yang dapat membuat malu, kita menempatkan semuanya dalam sebuah tas, sehingga kita cukup membawa satu benda: tas.

(terj.) Fungsi pembangkit adalah sebuah tali jemuran tempat kita menggantungkan barisan bilangan-bilangan untuk ditampilkan.

Fungsi pembangkit biasa

sunting

Fungsi pembangkit biasa dari sebuah barisan   adalah Ketika istilah fungsi pembangkit digunakan tanpa keterangan, umumnya hal itu merujuk pada sebuah fungsi pembangkit biasa. Jika   menyatakan fungsi massa peluang dari sebuah variabel acak diskret, maka fungsi pembangkit biasa yang dihasilkan disebut dengan fungsi pembangkit peluang.

Fungsi pembangkit biasa dapat diperumum untuk barisan dengan banyak indeks. Sebagai contoh, fungsi pembangkit biasa dari barisan dua dimensi  , dengan   dan   berupa bilangan asli, adalah 

Fungsi pembangkit eksponensial

sunting

Fungsi pembangkit eksponensial dari sebuah barisan   adalah Fungsi pembangkit eksponensial umumnya lebih mudah digunakan ketimbang fungsi pembangkit biasa untuk permasalahan pencacahan kombinatorial yang melibatkan objek berlabel.[3] Keuntungan lain dari fungsi pembangkit eksponensial adalah kemudahannya membawa relasi pengulangan ke ranah persamaan diferensial. Sebagai contoh, barisan Fibonacci   yang memenuhi relasi pengulangan   memiliki fungsi pembangkit eksponensial dengan bentuk dan turunan-turunan dari fungsi tersebut memenuhi persamaan diferensial   yang analog dengan relasi pengulangan di atas. Pada fungsi pembangkit tipe ini, suku faktorial   digunakan semata-mata untuk menormalisasi efek melakukan turunan pada  .

Fungsi pembangkit Poisson

sunting

Fungsi pembangkit Poisson dari sebuah barisan   adalah 

Contoh

sunting

Contoh sederhananya, fungsi pembangkit untuk barisan   adalah

  ,

untuk   .

Catatan kaki

sunting
  1. ^ Knuth, Donald E. (1997). "§1.2.9 Generating Functions". Fundamental Algorithms. The Art of Computer Programming. 1 (edisi ke-3rd). Addison-Wesley. ISBN 0-201-89683-4. 
  2. ^ Istilah alternatif ini dapat ditemukan di E.N. Gilbert (1956), "Enumeration of Labeled graphs", Canadian Journal of Mathematics 3, p. 405–411. Istilah ini jarang digunakan sebelum tahun 2000, namun terlihat meningkat sejak tahun itu.
  3. ^ Flajolet & Sedgewick 2009, hlm. 95

Referensi

sunting

Pranala luar

sunting