Fungsi Pembangkit

Misalkan diberikan suatu barisan a_{0},a_{1},a_{2},\cdots . Apa yang bisa kita dapatkan dari barisan tersebut? Salah satunya adalah rumus umum dari barisannya. Seperti pada barisan bilangan ganjil 1,3,5,7,9\cdots , maka kita dapat menebak bahwa rumus umum dari barisan tersebut adalah a_{n}=2n+1 dengan n=0,1,2,\cdots. Namun, bagaimana jika barisan a_{0}, a_{1}, a_{2},\cdots memiliki pola yang cukup rumit sehingga tidak dapat dengan mudah kita temukan rumus umumnya?

Misalkan saja barisan bilangan Fibonacci 0,1,1,2,3,5,8,11,\cdots yang mana sangat sulit untuk kita tentukan rumus eksplisit dari barisan tersebut. Tetapi ada satu hal menarik yang masih bisa didapatkan. Perhatikan bahwa setiap suku dari barisan bilangan Fibonacci merupakan koefisien dari x^{n} dalam ekspansi deret pangkat fungsi f(x)=\frac{x}{1-x-x^{2}} yang berpusat di titik asal, yakni,

\frac{x}{1-x-x^{2}}=0.x^{0}+x^{1}+x^{2}+2x^{3}+3x^{4}+5x^{5}+8x^{6}+11x^{7}+\cdots

Jadi bentuk lain dari deret pangkat yang mana koefisien-koefisiennya merupakan barisan bilangan Fibonacci adalah fungsi f(x)=\frac{x}{1-x-x^{2}}.

fungsi pembangkit.JPG

Nah, di dalam kajian matematika diskrit, jika diberikan suatu barisan a_{0},a_{1},a_{2},\cdots, maka kita dapat mendefinisikan bentuk

G(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots

sebagai fungsi pembangkit dari barisan a_{n}. Jadi meskipun rumus umum barisan a_{n} tidak dapat ditentukan, kita masih bisa bermain dengan fungsi pembangkit dari barisan a_{n}. Bagaimana cara menentukan fungsi pembangkit dari suatu barisan? Contohnya kita gunakan barisan yang cukup sederhana, yakni 1,2,3,4,5,\cdots. Menurut definisi di atas, kita dapat tuliskan

G(x)=1+2x+3x^{2}+4x^{3}+\cdots     (1)

Untuk mengetahui bentuk dari G(x), kalikan persamaan (1) dengan x menjadi

xG(x)=x+2x^{2}+3x^{3}+4x^{4}+\cdots    (2)

Selanjutnya kurangi persamaan (1) dengan persamaan (2) sehingga diperoleh

G(x)-xG(x)=1+x+x^{2}+x^{3}+\cdots

Ruas kanan pada persamaan di atas merupakan deret geometri dengan suku awal 1 dan rasio r=x, yang mana memiliki jumlah \frac{1}{1-x}. Jadi dapat dituliskan

G(x)(1-x)=\frac{1}{1-x}

Karenanya fungsi pembangkit dari barisan 1,2,3,4,5,\cdots adalah G(x)=\frac{1}{(1-x)^{2}}. Tabel di bawah ini menyediakan beberapa fungsi pembangkit dari barisan a_{k} yang mana cukup sering digunakan.

tabel GF
Fungsi Pembangkit

Kegunaan dari fungsi pembangkit ini dapat kita temukan untuk menyelesaikan masalah relasi rekurensi, membuktikan identitas kombinatorik, dan memecahkan berbagai masalah perhitungan lainnya. Di dalam postingan selanjutnya, kita akan melihat bagaimana penerapan fungsi pembangkit untuk menentukan rumus eksplisit dari barisan bilangan Fibonacci yang telah kita singgung di awal.


Sumber Gambar

Tabel Fungsi Pembangkit [https://www.cs.sfu.ca/~ggbaker/zju/math/generating.html]

https://www.gettyimages.com/detail/illustration/cartoon-of-business-executive-generating-new-royalty-free-illustration/493270348

Iklan

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 )

Foto Google+

You are commenting using your Google+ 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 )

Connecting to %s