Fungsi Pembangkit

martha yunanda fungsi pembangkit, kombinatorika

Pada ulasan fungsi pembangkit ini akan direview mengenai konsep fungsi pembangkit. Adapun defenisi fungsi pembangkit sebagai berikut,

Defenisi 1

Fungsi pembangkit dari barisan bilangan real, $a_1,a_2,\ldots,a_k,\ldots$ adalah deret tak hingga,

$G(x)=a_0+a_1x+\ldots+a_kx^k+\ldots=\sum_{k=0}^\infty a_kx^k$

dari deret di atas pangkat dari variabel x adalah tanda yang menyatakan  sehingga koefisien dari $x^n$ adalah nilai dari barisan ke-n. Untuk sebuah barisan $a_n$ maka G(x) adalah fungsi pembangkitnya.

Contoh 1:

Tentukan fungsi pembangkit untuk barisan $a_k$  dengan $a_k=3$, dan $a_k=k+1$ dan $a_k =2^k adalah : 

$\sum_{k=0}^\infty 3x^k, \\ \sum_{k=0}^\infty (k+1)x^k \\ \sum_{k=0}^\infty 2^kx^k$

Pembahasan: 

Dafat didefenisikan fungsi pembangkit barisan bilangan real berhingga dari pengembangan barisan berhingga $a_0 , a_1, ... , a_n$  pada barisan tak hinggaa dengan mengatur $a_{n+1} =0 , a_{n+2}$ ,  dan seterusnya.

Fungsi pembangkit dari barisan tak berhingga $a_n$ merupakan suku banyak dengan derajat n. Sebab untuk j>n tak ada suku dengan bentuk $a_jx^j$, fungsi pembangkit bisa ditulis,

$G(x) = a_o+a_1x+...+a_nx^n$

Contoh 2;

Bagaimanakah fungsi pembangkit untuk barisan 1,1,1,1,1,1,0,0,....?

Pembahasan:

Bentuk fungsi pembangkit adalah:

$G(x)=1+x+x^2+x^3+x^4+x^5$ 

(1,1,1,1,1,1) mewakili koefisien $x^0$ hingga $x^5$ selanjutnya $x^6$ dan seterusnya koefisiennyaa adalah 0.

Jika diperhatikaan, bentuk fungsi pembangkit di atas seperti deret geometri dengan rasio x. Dengan rumus $S_n$ deret geometri, 

$S_n = \frac {a(1-r^n)}{1-r}$

a=1

r= x

n=5

maka

$G(x) = \frac {1(1-x^6)}{1-x} = \frac {1-x^6}{1-x}$

Contoh 3:

Tentukan fungsi pembangkit 2,4,1,1,1,1,....

Pembahasan:

$G(x) = 2+ 4x+x^2+x^3...$

pecahlah 2+4x menjadi 1+3x+1+x sehingga bentuknya menjadi,

$G(x) = 1+3x + 1+ x+x^2+x^3+...$

Sementara bentuk $1+x+x^2+x^3+...$ bisa diubah mengunakan $S_n$ deret geometri tak berhingga dengan rasio x. Artinya,

$G(x) = 1+3x + \frac {1}{1-x}$

Sebagai latihan bisakah anda menetukan fungsi pembangkit dari,

• 1,1,1  dimana |x|<1
• $1, a, a^2, a^3...$ dimana |ax|<1

Jawabannya adalah,

• $G(x) = \frac {1}{1-x}$
• $G(x) = \frac {1}{1-ax}$

Sederhananya, dari deret yang diberikan, angka pada barisan tersebut jadikan sebagai koefisien $x^0 , x^1 , x^2....$ Lalu cari bentuk umum fungsi tersebut.

Teorema I

Misal $p(x)=\sum_{k=0}^\infty a_kx^k$  dan $q(x)=\sum_{k=0}^\infty b_kx^k$ maka,

$p(x)+q(x)=\sum_{k=0}^\infty (a_k+b_k)x^k$

$p(x)q(x)=\sum_{k=0}^\infty (\sum_{j=0}^k a_jb_{k-j})x^k$

Contoh Penggunaan Teorema di atas bisa anda lihat pada contoh soal di bawah ini,

Contoh 1

Tentukan fungsi pembangkit dari 3,1,3,1,3,1...

Jawab:

Fungsi 3,1,3,1,3,1 bisa anda pecah menjadi: 

2,0,2,0,2,0 dan 1,1,1,1,1,1 (jika dijumlahkan ini hasilnya 3,1,3,1,3,1) 

Misalkan 2,0,2,0,2,0 adalah p(x), maka

$p(x) = 2+0.x^1+2x^2+0.x^3... = 2+2x^2+2x^4+..$

ini adalah deret geometri tak berhingga dengan rasio $x^2$ dan a=2. Dengan jumlah deret geometri tak hingga bisa anda tulis,

$p(x) = \frac {2}{1-x^2}$

Misalkan 1,1,1,1...q(x),

$q(x) = 1+x+x^2+x^3+...$

deret geometri tak hingga dengan a=1 dan rasio x, sehingga jumlahnya:

$q(x) = \frac {1}{1-x}$

Fungsi Pembangkitnya bisa ditulis,

$G(x) = p(x) + q(x) = \frac {2}{1-x^2} + \frac {1}{1-x}$

Menemukan fungsi pembangkit tidak hanya terbatas pada deret geometri saja, Bisa saja anda harus menggunakan teknik matematika lain, seperti integral ataupun turunan. Perhatikan contoh di bawah ini.

Contoh 2:

Tentukan fungsi pembangkit dari 1,2,3,4,....

Jawab:

$G(x) = 1+2x+3x^2+.4x^3+...$

Jika langsung menggunakan deret geometri anda tak akan menemukan apa apa.

Perhatikan:

$1+2x+3x^2+.4x^3+...$ adalah TURUNAN dari

$x+x^2+x^3+x^4+...$

G(x) = K'(x)

 sekarang permisalkan

$K(x) = x+x^2+x^3+x^4+...$.

Kembali pada K(x)

merupaka deret geometri tak berhingga dengan a=x dan rasio x.

$K(x) = \frac {x} {1-x}$

Turunkan (silakan baca turunan fungsi pembagian jika anda tak bisa menurunkan ini)

$K' (x) = \frac {1}{(1-x)^2}$

Karena G(x) = K'(x) maka fungsi pembangkitnya adalah,

$G(x) =\frac {1}{(1-x)^2}$

Teorema II

Misal $a_o, a_1, a_2,a_3,...$ memiliki fungsi pembangkit $f(x)$, maka untuk tiap k bilangan asli,

 $\underbrace{0,0,0,0,0}_{k},a_0,a_1,a_2,a_3,\ldots$

Bukti:

Fungsi Pembangkit

$\underbrace{0,0,0,0,0}_{k},a_0,a_1,a_2,a_3,\ldots$

adalah:

$a_0x^k+a_1x^{k+1}+a_2x^{k+2}+a_3x^{k+3}+\ldots  =x^k(a_0+a_1x+a_2x^2+a_3x^3+\ldots) \\  =x^kf(x)$

k itu lebih mudah diingat sebagai banyaknya 0.

Contoh 1:

Tentukan fungsi pembangkit 0,1,1,1,1...

Jawab:

k=1 (banyak 0)

Sementara fungsi pembangkit 1,1,1,1.. di atas adalah : $\frac {1}{1-x}$

Jadi fungsi pembangkitnya:

$G(x) = x^1 . \frac {1}{1-x} = \frac {x}{1-x}$

Contoh 2: Tentukan fungsi pembangkit 0,0,0,0,3,1,3,1,3,1...

Jawab:

k=4

Fungsi pembangkit 3,1,3,1,3,1 telah anda cari di atas 

$\frac {2}{1-x^2} + \frac {1}{1-x}$

sehingga fungsi pembangkitnya adalah

$G(x) =x^4 . \frac {2}{1-x^2} + \frac {1}{1-x} = \frac {2x^4}{1-x^2} + \frac {x^4}{1-x}$

Contoh 3:

Tentukan fungsi pembangkit dari 0,0,0,0,0,1,2,3,4...

Jawab:

k=5

Fungsi pembangkit 1,2,3,4,... $\frac {1}{(1-x)^2}$

sehingga

$G(x)=x^5 . \frac {1}{(1-x)^2} = \frac {x^5}{(1-x)^2}$
Lanjutkan Membaca: Teorema Binomial Diperluas.

Share on Facebook

Share on Twitter

Share on LinkedIn