Fungsi Pembangkit

Jadi ada ide bagaimana menyelesaikan masalah seperti masalah kombinatorik ini? Yap, judul pada catatan ini merupakan metode yang ampuh untuk menyelesaikan masalah diskrit yang berhubungan dengan barisan, khususnya yang bertipe rekursif. Ajaibnya metode ini mengubah masalah yang tadinya diskrit dan secara komputasi sulit dipecahkan, ke analisis fungsi real yang cenderung lebih mudah diserang. Dinamakan fungsi pembangkit karena fungsi ini “dibangkitkan” dari barisan yang akan dianalisis.

Biar contoh yang menjelaskan …

misalkan a(n) suatu barisan yang didefinisikan secara rekursif,

a(0) = 0 dan untuk a > 0 a(n+1) = 2a(n) + 1.

masalah kita adalah mencari rumus ekplisit barisan itu.

misalkan A(x) adalah fungsi pembankit a(n),

generating function

Persamaan terakhir diperoleh karena a(n) adalah koefisien xn A(x). Terlihat bahwa untuk mengaplikasikan fungsi pembangkit kita harus mahir mengotak-atik deret kuasa. deret kuasa yang dipakai di atas hanya deret geometri dan memang kebanyakan deret geometri lah yang kepakai.

..bersambung..

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s