Fungsi Pembangkit Fungsi Pembangkit ((Generating FunctionsGenerating Functions))

Fungsi pembangkitFungsi pembangkitFungsi pembangkit digunakan untuk merepresentasikan barisan secara efisien dengan mengkodekan unsur barisan sebagai koefisien dalam deret pangkat suatu variabel x .

Fungsi pembangkit dapat digunakan untuk: memecahkan berbagai masalah

counting, memecahkan relasi recurrence, dan membuktikan identitas kombinatorik.

Definisi dan contohDefinisi dan contohDefinisi. Fungsi pembangkit (generating function) untuk barisan bilangan real: a0, a1, …, ak, … adalah deret pangkat tak hingga:

.......)(0

10

k

kk

kk xaxaxaaxG

Contoh 1. a. Fungsi pembangkit dari barisan {an} dengan ak = 5

adalah

0

)3(k

kxk

k

k

k x

0

3

0

5k

kx

b. Fungsi pembangkit dari barisan {an} dengan ak = k+3 adalah

c. Fungsi pembangkit dari barisan {an} dengan ak = 3k adalah

Contoh 2Contoh 2

Tentukan fungsi pembangkit dari barisan

1, 1, 1, 1, 1, 1  

Solusi.

Fungsi pembangkit dari barisan 1,1,1,1,1,1 adalah:

1 + x + x2 + x3 + x4 + x5

1

16

x

x

ContohContoh

Contoh 3. Fungsi pembangkit dari barisan

1, 1, 1, 1, …adalah

1 + x + x2 + x3 + … Contoh 4. Fungsi pembangkit dari barisan

1, a, a2, a3, …adalah

1 + ax + a2x2 + a3x3 + …

1||jika,1

1

x

x

1||jika,1

1

ax

ax

Teorema 1Teorema 1

Contoh 5. Misal f(x) = 1/(1-x)2. Tentukan koefisien a0, a1, … dalam ekspansi f(x) = akxk.Solusi.

.)1(1)1(

1

)1(

1

)1(

1

00 02

k

k

k

kk

j

xkxxxx

Jadi, ak = k+1.

.)()(

dan)()()(

Maka,.)(dan)(Misal

0 0

0

00

k

kk

j jkj

k

k kk

k

k kk

k k

xbaxgxf

xbaxgxf

xbxgxaxf

Koefisien Binomial DiperluasKoefisien Binomial DiperluasMisalkan u bilangan real dan k bilangan bulat tak negatif. Maka koefisien binomial diperluas didefinisikan sebagai: 

.0jika,1

,0jika,!

)1)...(1(

k

kk

kuuu

k

u

Contoh 6. Tentukan nilai dari:a.

5

2/1

.4!3

)4)(3)(2(

3

2

3

2

.!5

)42/1)(32/1)(22/1)(12/1)(2/1(

5

2/1

b.

Teorema Binomial DiperluasTeorema Binomial Diperluas

Teorema 2. Misal x bilangan real dengan |x| < 1 dan

u bilangan real. Maka,

.)1(

0

k

ku xk

ux

Catatan.Jika u bilangan bulat positif maka Teorema Binomial Diperluas menjadi Teorema Binomial.

Contoh 7Contoh 7Tentukan fungsi pembangkit untuk

(1+x)-n dan (1-x)-n, dengan n bilangan bulat positif.

Solusi.

k

k

kn

k

kn

xkknCx

xk

nx

),1()1()1( Maka,

.)1(2,TeoremaMenurut

0

0

0

),1()1(

:xdgnxmenggantiDengan

k

kn xkknCx

Soal 1Soal 1

Tentukan koefisien x10 dalam deret pangkat fungsi-fungsi berikut ini:

a. 1/(1+x)2

b. 1/(1-2x)

c. x4/(1-3x)3

 

Masalah Counting dan Fungsi PembangkitMasalah Counting dan Fungsi PembangkitContoh 8. Tentukan banyaknya solusi dari n1 + n2 + n3 = 17, bila n1, n2 dan n3 bilangan bulat taknegatif dengan 2 n1 5, 3 n2 6 dan 4 n3 7.Solusi.Banyaknya solusi dinyatakan oleh koefisien x17 dalam ekspansi:

(x2+x3+x4+x5) (x3+x4+x5+x6) (x4+x5+x6+x7).Setiap bentuk x17 dalam perkalian ini didapat dengan mengalikan

xn1 pada faktor pertama dengan xn2 pd faktor kedua dan xn3 pada faktor ketiga

yang memenuhi: n1 + n2 + n3 = 17.Bila dihitung, didapat koefisien x17 adalah 3. Jadi, ada tepat 3 solusi.

Contoh 9Contoh 9

Ada berapa cara untuk membagikan 8 kue yang identik kepada 3 anak jika setiap anak menerima sedikitnya 2 kue dan tidak lebih dari 4 kue?

Solusi.Misalkan cn: banyaknya cara membagikan n kue.Karena setiap anak menerima sedikitnya 2 kue dan tidak lebih dari 4 kue, maka untuk setiap anak ada suatu faktor yang berbentuk:

(x2 + x3 + x4)dalam fungsi pembangkit barisan {cn}. Karena ada 3 anak maka fungsi pembangkitnya adalah:

(x2 + x3 + x4)3.Cara untuk membagikan 8 kue adalah koefisien dari x8, yakni 6. Jadi, ada 6 cara untuk membagikan 8 kue kepada 3 anak tadi.

Gunakan fungsi pembangkit untuk menentukan banyaknya cara mendistribusikan 25 donat identik kepada 4 polisi sehingga setiap polisi mendapatkan sedikitnya 3 dan tidak lebih dari 7 donat.

Soal 2Soal 2

Gunakan fungsi pembangkit untuk menentukan banyaknya cara memilih pecahan mata uang bernilai Rp. 100, Rp. 500 dan Rp. 1000 jika kita ingin membayar suatu barang yang bernilai Rp. r, apabila: a. urutan pemilihan diperhatikan atau b. tidak diperhatikan.

Contoh.Untuk membayar Rp. 600, ada 2 cara bila urutan tidak diperhatikan, yaitu (Rp. 100, Rp. 100, Rp. 100, Rp. 100, Rp. 100, Rp. 100) atau (Rp. 100, Rp. 500) dan ada 3 cara bila urutan diperhatikan, yaitu(Rp. 100, Rp. 100, Rp. 100, Rp. 100, Rp. 100, Rp. 100), (Rp. 100, Rp. 500), atau (Rp. 500, Rp. 100)

Contoh 10Contoh 10

b. Jika urutan pemilihan tidak diperhatikan. Karena masing-masing pecahan dapat dipergunakan berkali-kali, maka

• faktor yang merepresentasikan penggunaan Rp. 100 adalah

1 + x + x2 + x3 + …,• faktor yang merepresentasikan penggunaan Rp. 500

adalah 1 + x5 + x10 + …,

• faktor yang merepresentasikan penggunaan Rp. 1000 adalah

1 + x10 + x20 + … Jadi, banyaknya cara pemilihan pecahan mata uang untuk membayar seharga Rp. r adalah koefisien dari xr/100 dalam fungsi pembangkit

(1 + x + x2 + x3 + …) (1 + x5 + x10 + …) ( 1 + x10 + x20 + …)

Contoh 10…Contoh 10…

a. Jika urutan pemilihan diperhatikan.Banyaknya cara untuk menggunakan tepat n pecahan untuk membayar seharga Rp. r adalah koefisien xr/100 dalam

(x + x5 + x10)n

Karena kita dapat menggunakan berapa pun jumlah pecahan, maka banyaknya cara pemilihan pecahan mata uang untuk membayar seharga Rp. r adalah koefisien dari xr/100 dalam

1 + (x + x5 + x10) + (x + x5 + x10)2 + …

Contoh 10…Contoh 10…

5252 1

1

)(1

1

xxxxxx

Gunakan fungsi pembangkit untuk menentukan banyaknya cara untuk menukar uang $100 dengan menggunakan pecahan:a) $10, $20 dan $50b) $5, $10, $20 dan $50c) $5, $10, $20 dan $50; bila setiap pecahan digunakan sedikitnya sekali.d) $5, $10 dan $20; bila setiap pecahan digunakan sedikitnya sekali tapi tidak lebih dari 4 kali. 

Soal 3Soal 3

Contoh 11Contoh 11Gunakan fungsi pembangkit untuk menghitung banyaknya cara memilih r obyek dari n jenis benda berbeda jika kita harus memilih sedikitnya satu obyek dari setiap jenisnya.Solusi. Misalkan ar: banyaknya cara memilih r obyek dari n jenis benda bila dari setiap jenis terpilih sedikitnya satu objek. Karena kita perlu memilih sedikitnya satu obyek dari setiap jenis, maka setiap jenis menyumbangkan faktor

(x + x2 + x3 + …)pada fungsi pembangkit. Akibatnya, fungsi pembangkit G(x) dari barisan {ar} adalah

G(x) = (x+x2 + x3 + …)n

= xn(1+x+x2 + x3 + …)n = xn / (1-x)n .

Dengan menggunakan Teorema Binomial Diperluas:

nr

r

nt

t

r

rn

rr

r

rn

r

rn

nnn

n

xnrrC

xnttCxrrnC

xrrnCxxr

nx

xxx

xxG

.),1(

),1(),1(

)1)(,1()1()(

)1.()1(

)(

0

00

Jadi, ada C(r-1,r-n) cara memilih.

Contoh 11…Contoh 11…

Fungsi Pembangkit dan Solusi Relasi Fungsi Pembangkit dan Solusi Relasi RecurrenceRecurrence Contoh 12. Cari solusi relasi recurrence ak = 3ak-1 untuk k = 1, 2, 3, … dengan kondisi awal a0 = 2.Solusi. Misal G(x): fungsi pembangkit untuk barisan {ak}, Maka,

.32Jadi,

.32)( maka1

2Karena,

.31

2)(Jadi,

.2)3(

3)(3)(

.)(

00

110

1 10

1 11

0

kk

k

k

k

k

kk

kkk k

k

k kk

k k

k

k kk

k k

a

xxGxaax

xxG

xaaa

xaxaxxGxG

xaxaxxG

k

k k xaxG

0)(

Fungsi Pembangkit dan Pembuktian Fungsi Pembangkit dan Pembuktian IdentitasIdentitasContoh 13.Gunakan fungsi pembangkit untuk membuktikan:

bulat.nbila),,2(),(0

2 nnCknCn

k

Solusi. C(2n,n) adalah koefisien xn dlm ekspansi (1+x)2n. Akan tetapi, (1+x)2n = [(1+x)n]2.

= [C(n,0)+C(n,1)x+ … + C(n,n)xn]2.Koefisien dari xn dlm ekspansi ini: C(n,0)C(n,n) + C(n,1)C(n,n-1) + … + C(n,n)C(n,0). Ini sama dgn C(n,k)2, krn C(n,n-k) = C(n,k). Karena C(2n,n) dan C(n,k)2 menyatakan koefisien xn dlm (1+x)2n maka haruslah

.),2(),(0

2 nnCknCn

k