BAB IIFUNGSI PEMBANGKIT

A. Deret Kuasa

Deret tak hingga yang berbentuk ∑n=0

∞

an xn

disebut deret kuasa. Bila terdapat bilangan

positif R sedemikian sehingga deret kuasa ini konvergenuntuk setiap x dengan |x|<R , maka

R disebut radius kekonvergenan. Ada kalanya suatu deret kuasa tidak konvergen untuk

semua nilai x( x≠0 )dan dikatakan deret tersebut divergen. Dalam tulisan ini, pembahasan

tidak difokuskan pada kekonvergenan deret kuasa tersebut, melainkan lebih pada koefisien-

koefisien dari xn

. Dalam hal ini, bentuk ∑n=0

∞

an xn

dipandang sebagai ekspresi formal saja.

Deret kuasa yang demikian disebut sebagai deret kuasa formal.

Dalam Kalkulus, telah dikenalbahwa deret Taylor fungsif ( x )di sekitar x = 0

mempunyai bentuk sebagai berikut.

f ( x )= ∑n=0

∞ 1n !

f (n)(0 )xn

= f (0)+ f ' (0 )x+ 1

2!f \( 0 \) x rSup { size 8{2} } + { {1} over {3!} } f ' ' ' \( 0 \) x rSup { size 8{3} } + . . . . } {¿

Dengan formula tersebut, diperoleh hasil-hasil sebagai berikut.

1. e x= ∑n=0

∞ 1n !

xn

= 1+x+ 1

2 !x2

+

13!

x3

+ ………...untuk |x| < 1

2.

11−x =

∑n=0

∞

xn

= 1+x+x2+x3+. .. .…………..untuk |x| < 1

3.

1

(1−x )2 =

∑n=1

∞

nxn−1

= 1+2 x+3 x2+4 x3+. . ..… untuk |x| < 1

4.

1

1−x2=1+x2+x4+x6+x8+.. . .

5. Teorema Binomial

Untuk setiap bilangan real u, bilangan bulat nonnegatif k, dan |x| < 1, berlaku:

17

(1+x )u=

∑k=0

∞(u ¿ )¿¿

¿¿¿, dengan

(u ¿ ) ¿¿

¿¿ =

{u(u−1 )(u−2 ). . .(u−k+1)k !

, jika k>0¿ ¿¿¿

B. Definisi Fungsi Pembangkit

Misal (an )=(a0 , a1 , a2 ,. .. . )adalah suatu barisan (fungsi numerik diskret). Fungsi

Pembangkit Biasa (FPB) dari barisan (an )didefinisikan sebagai berikut.

∑n=0

∞

an xn

= a0+a1 x+a2 x2+a3 x3+. .. . ..….……………………………...….....(2.1)

Fungsi Pembangkit Eksponensial (FPE) dari an didefinisikan sebagai berikut.

∑n=0

∞an

xn

n! = a0+a1 x+a2

x2

2!+a3

x3

3!+. ..

…………………………………….…(2.2)

Perhatikan bahwa ex= 1+x +

x2

2! +

x3

3! + …. adalah Fungsi Pembangkit Biasa (FPB)

dari barisan (1, 1,

12! ,

13! , ….) atau Fungsi Pembangkit Eksponensial (FPE) dari barisan (1, 1,

1, 1, ….)

Jika diketahui suatu barisan, maka dapat ditentukan fungsi pembangkit dari barisan

tersebut dalam bentuk sesederhana mungkin.Perhatikan contoh berikut.

Contoh 2.1

Tentukan bentuk sederhana fungsi pembangkit biasa (FPB) dari barisan-barisan berikut.

a. (0, 0,

12! ,

13! , ….)

b. (0, 2, 4, 6, …., 2n, ….)

Jawab

a. Fungsi pembangkit biasa (FPB) dari barisan yang dimaksud adalah

A(x) =

12!

x2

+

13!

x3

+ ….

= (1 + x +

12!

x2

+

13!

x3

+ ….) – x – 1

= ex−x−1

b. Fungsi pembangkit biasa (FPB) yang dimaksud adalah

18

A(x) = 2 x+4 x2+6 x3+ .. .+2 nxn+. .. .

= 2 x (1+2 x+3 x2+.. .+nxn−1+.. . . )

=

2x

(1−x )2

C. Operasi Fungsi Pembangkit

Penjumlahan, pengurangan, maupun perkalian dua fungsi pembangkit atau lebih, dapat

dilakukan dengan cara yang sama seperti halnya menjumlah, mengurangkan, ataupun

mengalikan dua polinomial atau lebih.

Misal diketahui A(x) = ∑n=0

∞

an xn

dan B(x) = ∑n=0

∞

bn xn

.

A(x) ± B(x) = ∑n=0

∞

(an±bn )xn

dan

A(x) B(x) = ∑n=0

∞(∑

k=0

n

an bn−k )xn

Apabila(an) ,(bn) ,dan(cn )adalah barisan yangmemenuhicn = ∑k=0

∞

ak bn−k, maka (cn )

disebut konvolusi dari(an)dan (bn) , yang ditulis(cn )= (an)* (bn)

Contoh 2.2Tentukan barisan(fungsi numerik) yang bersesuaian dengan fungsi pembangkit biasaberikut.

P( x )= x5+x6

1−x

Jawab

Misal P( x )= x5+x6

1−x = ( x5+x6 ) (1+x+ x2+x3+. .. )

= x5+x6+2 x7+.2 x8+. . ..

Jadi, barisan yang bersesuaian adalah (0, 0, 0, 0, 0, 1, 1, 0, 0, ….).

Dapat juga diselesaikan dengan cara sebagai berikut.

P( x )= x5+x6

1−x = ( x5+x6 )(1−x )−1

= ∑n=0

∞

cn xn

.

19

Perhatikan bahwax5+x6adalah fungsi pembangkit biasa dari barisan (an)= (0, 0, 0, 0,

0, 1, 1, 0, 0, ….). Sedangkan (1−x )−1adalah fungsi pembangkit biasa dari barisan (bn) = (1,

1, 1, …, 1, …). Karena b i =1,untuk setiap i, maka cn = ∑k=0

n

ak bn−k=∑k=0

∞

ak. Jadi, barisan yang

bersesuaian adalah (cn ) = (0, 0, 0, 0, 0, 1, 2, 2, …, 2, ….).

D. Fungsi Pembangkit untuk Kombinasi

Misal terdapat tiga macam objek: a, b, dan c. Diperbolehkan memilih

sebanyak 0, 1, atau 2 objek a

sebanyak 0 atau 1 objek b, dan

sebanyak 0 atau 1 objek c.

Berapakahbanyaknya cara memilih k objek?Untuk menjawab pertanyaan ini akan

diterapkan fungsi pembangkit. Misal ak adalah banyaknya cara memilih k objek. Akan

dicoba menghitung fungsi pembangkit biasa A(x) = ∑k=0

∞

ak xk

. Karena objek a dapat dipilih 0,

1, atau 2 kali; dan objek b dapat dipilih 0 atau 1 kali; dan objek c dapat dipilih 0 atau 1 kali,

maka ekspresi yang digunakan adalah:

[ (ax )0+(ax )1+( ax )2 ][ (bx )0+(bx )1 ][ (cx )0+(cx )1 ]……….……..…………... (2.3)

Perhatikan bahwa(ax )1mengindikasikan objek a terpilih satu kali; (ax )2

mengindikasikan objek a terpilih dua kali; demikian pula (bx )0mengindikasikan objek b

tidak terpilih, dan seterusnya. Selanjutnya, ekspresi (2.3) dapat disederhanakan menjadi

sebagai berikut.

(1+ax+a2 x2 )(1+bx )(1+cx )atau

1+( a+b+c )x+(ab+bc+ac+a2) x2+(abc+a2b+a2 c )x3+a2bcx 4

……...…. (2.4)

Perhatikan bahwa koefisien x3

dalam (2.4) memberikan semua kemungkinan memilih

3 objek (dengan syarat yang diperbolehkan), yaitu: a, b, dan c; atau a, a, dan b; atau a, a,

dan c. Demikian pula koefisien dari x2

memberikan semua kemungkinan memilih dua objek

yaitu: a dan b; atau b dan c; atau a dan c; atau a dan a. Hal yang sama berlaku untuk

koefisien-koefisien lainnya. Jika a, b, dan c (dalam (2.4) masing-masing disubtitusi dengan 1,

diperoleh ekspresi 1+3 x+4 x2+3 x3+x 4. Jelaslah bahwa koefisien x

k dalam ekspresi ini

20

menyatakan banyaknya cara memilih k objek )( ka dengan syarat yang diperbolehkan.

Misalnya terdapat 4 cara memilih 2 objek; terdapat 3 cara memilih 1 objek; dan hanya satu

cara memilih 4 objek. Perhatikan bahwa ka = 0, untuk k > 4. Selanjutnya ekspresi

A(x) = 1+3 x+4 x2+3 x3+x 4

= (1+x+ x2)(1+x )(1+x )

disebut fungsi pembangkit dari permasalahan menentukan banyaknya cara memilih k objek

dari 3 macam objek, dengan syarat objek pertama (objek a) paling banyak dapat dipilih 2

kali; objek kedua (objek b) paling banyak dapat dipilih 1 kali; dan objek ketiga (objek c)

paling banyak dapat dipilih 1 kali.

Secara umum diperoleh teorema sebagai berikut.

Contoh2.3

Tentukan fungsi pembangkit untuk banyaknya cara memilih r objek dari n objek jika tidak

diperbolehkan terdapat pengulangan.

Jawab

Terdapat n objek. Karena tidak boleh terdapat pengulangan, maka tiap objek hanya dapat

dipilih 0 atau 1 kali. Sehingga fungsi pembangkit yang dimaksud adalah sebagai berikut.

A(x) = (1 + x)(1 + x) (1 + x) ..... (1 + x) …….(sebanyak n faktor)

= (1+x )n=

∑r=0

n(n¿ )¿¿

¿¿¿ …………………....(Teorema binomial)

Perhatikan bahwa koefisien xrdalam A(x), yaitu

(n ¿ ) ¿¿

¿¿, menyatakan banyaknya cara

memilih r objek dari n objek yang ada jika tidak diperbolehkan terdapat pengulangan.

Misal terdapat p tipe objek; dan terdapat n1 objek tipe 1, n2 objek tipe 2, …, n p objek

tipe p. Misalak menyatakan banyaknya cara mengambil k objek dengan syarat

diperbolehkan mengambil sembarang banyak objek tiap tipe. Fungsi pembangkit

untuk ak adalah A(x) = ∑k=0

∞

ak xk

,dengan

A(x) = (1+x+ x2+.. .+xn1)(1+x+x2+. ..+x

n2). . .(1+x+x2+. . .+ xnp)

Bilangan ak diberikan oleh koefisien xk

dalam A(x).

21

Contoh2.4

Tentukan banyaknya cara memilih r objek dari n objek yang diketahui jikaboleh terdapat

pengulangan

Jawab

Misal t r menyatakan banyak cara memilih r objek. Karena ada n macam objek dan tiap objek

dapat dipilih berulang (tanpa batas), maka fungsi pembangkit untuk t r adalah:

A(x) = (1+x+ x2+.. . .)(1+x+ x2+.. . .)(1+x+ x2+.. .) ……………… (n faktor)

= (1+x+ x2+.. .)n

Karena untuk |x|<1 ,

11−x = 1+x+x2+. .. . , maka

A(x) = ( 11−x )

n

= (1−x )−n

= ∑r=0

∞(−n ¿ ) ¿¿

¿¿¿

Untuk r > 0, koefisien xr

dalam A(x) adalah

(−n ¿ ) ¿¿

¿¿=

(−n )(−n−1) .. .(−n−r+1)r !

(−1 )r

=

(−1)r [n(n+1 )(n+2) .. .(n+r−1) ]r !

(−1 )r

=

n(n+1 ). ..( n+r−1 )r !

=

(n+r−1)(n+r−2 ). ..( n+1)nr !

=

(n+r−1)(n+r−2 ). ..( n+1)n(n−1) !r !( n−1 )!

=

(n+r−1)!r !(n−1)!

=

(n+r−1 ¿ )¿¿

¿¿

22

Untuk r = 0, koefisien dari xrdalam A(x) adalah

(−n ¿ ) ¿¿

¿¿(−1 )0 =

(n+0−1 ¿ ) ¿¿

¿¿. Sehingga, untuk r

≥ 0, berlaku

(−n ¿ ) ¿¿

¿¿(−1)r

=

(n+r−1 ¿ )¿¿

¿¿. Dengan demikian, jelaslah bahwa

Jadi, banyaknya cara memilih r objek dari n objek jika pengulangan diperbolehkan

samadengan koefisien xrdalam A(x), yaitu

(n+r−1 ¿ )¿¿

¿¿.

Sebelum membicarakan contoh selanjutnya, perlu diingat bahwa untuk x 1 dan n

bilangan cacah berlaku identitas sebagai berikut.

Contoh 2.5

Tentukan banyaknya caramemilih k huruf dari huruf-huruf pembentuk kata SURABAYA

sedemikian sehingga setiap konsonan terpilih paling sedikit satu dan setiap vokal terpilih

paling banyak 10.

Jawab

Perhatikan bahwa kata SURABAYA terdapat 6 huruf yang berbeda: yaitu:

Konsonan: S, R, B, Y

Vokal : U dan A.

Karena setiap konsonan terpilih paling sedikit satu, maka setiap konsonan tersebut

berasosiasi dengan faktor ( x+ x2+x3+x4+x5+. .. )dalam fungsi pembangkit. Selanjutnya,

karena setiap vokal dapat dipilih sebanyak-banyaknya 10, maka setiap vokal tersebut

berasosiasi dengan sebuah faktor (1+x+ x2+.. .+x10) . Dengan demikian, fungsi pembangkit

dari permasalahan di atas adalah:

A(x) =( x+ x2+x3+x4+x5+. .. )4 (1+x+x2+.. .+x10)2

= ( 1

1−x−1)

4 ( 1−x11

1−x )2

= x4 (1−x11 )2 (1−x )−6

= ( x4−2 x15+x26 )(1−x )−6

(1−x )−n =

∑r=0

∞(n+r−1¿ ) ¿¿

¿¿¿

1−xn+1

1−x = 1+x+x2+x3 .. . .+ xn

23

= ( x4−2 x15+x26 )∑r=0

∞(6+r−1¿ )¿¿

¿¿¿

= ∑r=0

∞(6+r−1¿ )¿¿

¿¿¿

Banyaknya cara yang dimaksud samadengan koefisien xk

dalam A(x) , yaitu

=

{0 ; jika k<4 ¿¿¿

¿¿Dari contoh-contoh di atas, kita lihat bahwa fungsi pembangkit tidak tergantung dari

banyaknya objek yang diambil. Fungsi pembangkit biasa dapat digunakan untuk

memecahkan masalah pendistribusian (penempatan) objek-objek yang identik ke dalam sel-

sel (kotak-kotak) yang berbeda.

Contoh2.6

Tentukan banyaknya cara menempatkan 60 objek yang identik ke dalam 4 sel (kotak) yang

berbeda sedemikian sehingga setiap kotak mendapat paling sedikit 1 objek.

Jawab

Karena terdapat 4 kotak dan tiap kotak terdapat paling sedikit satu objek, maka fungsi

pembangkit untuk permasalahan ini adalah:

A(x)=( x+ x2+x3+. .. )4

= x4 (1+x+ x2+.. .)4

= x4 ( 1

1−x )4

= x4∑r=0

∞(4+r−1 ¿ ) ¿¿

¿¿¿= ∑r=0

∞(3+r ¿ ) ¿¿

¿¿¿ =

∑r=4

∞(r−1¿ )¿¿

¿¿¿

Jadi, banyaknya cara menempatkan 60 objek yang identik ke dalam 4 kotak yang

berbeda sedemikian hingga tiap kotak mendapat paling sedikit satu objek samadengan

koefisien x60

dalam A(x), yaitu

(56+3 ¿ ) ¿¿

¿¿ =

(59 ¿ ) ¿¿

¿¿ = 32.509.

24

Fungsi Pembangkit Biasa (FPB) juga dapat digunakan untuk menentukan banyaknya

penyelesaian (solusi) bulat dari suatu persamaan linier dengan beberapa peubah.

Contoh2.7

Tentukan banyaknya solusi bulat dari persamaan berikut.

x1+x2+x3+ x4+x5=100 , x i≥0 , i {1, 2, 3, 4, 5}

Jawab

Perhatikan bahwa (0, 0, 0, 25, 75), (0, 5, 20, 5, 70), dan (2, 3, 7, 28, 60) masing-masing

adalah solusi bulat dari persamaan tersebut.Karena dalam persamaan itu terdapat 5 peubah,

maka fungsi pembangkit dari permasalahan itu memuat 5 faktor. Selanjutnya, karena setiap

peubahx i 0, maka setiap faktor dari kelima faktor dalam fungsi pembangkit tersebut adalah

(1+x+ x2+x3+. .. .) . Sehingga fungsi pembangkit dari permasalahan di atas adalah

A(x) = (1+x+ x2+x3+. .. .)5

= ( 1

1−x )5

= ∑r=0

∞(5+r−1 ¿ ) ¿¿

¿¿¿

Banyaknya solusi bulat yang dimaksud samadengan koefisien x100

dalam A(x), yaitu

(5+100−1¿ )¿¿

¿¿

E. Fungsi Pembangkit untuk Permutasi

Fungsi pembangkit biasa memberikan pendekatan yang mudah dan sistematis untuk

memecahkan masalah-masalah umum yang melibatkan “pengambilan” atau pendistribusian

objek-objek yang identik ke dalam sel-sel (tempat-tempat) yang berbeda. Pada bagian ini

akan diterapkan teknik serupa untuk memecahkan masalah-masalah umum yang melibatkan

“penjajaran” (arrangement) atau pendistribusian objek-objek berbeda ke dalam sel-sel

(tempat-tempat) yang berbeda. Untuk maksud tersebut, diperlukan teoremaberikut ini.

Teorema 1

Jika terdapat k 1objek tipe satu,k 2objek tipe dua, … dan k nobjek tipe n, maka banyaknya

cara “menjajar” objek-objek ini adalah

25

(∑i=1

n

k i)!k1 !k 2 ! .. .kn !

Bukti

Jika semua objek berbeda, maka akan terdapat (∑

i=1

n

k i)! jajaran. Tetapi objek-objek ini tidak

semuanya berbeda, sehingga bilangan ini terlalu besar. Pikirkan sebuah jajaran dari ∑i=1

n

k i

objek yang berbeda. Jika digantik iobjek tipe i yang berbeda dengan k i objek yang identik,

maka k i ! jajaran akan sama. Karena 1≤i≤n , bilangan total penjajaran harus dibagi dengan

k 1! k2 ! . .. k n ! .Misalnya, banyaknya cara “menjajar” (banyaknya permutasi) dari unsur-unsur

{a, a, a, b, b} adalah

5!3! 2! = 10; yaitu: aaabb, aabab, abaab, baaab, babaa, bbaaa, aabba,

abbaa, ababa, baaba.

Selanjutnya akan ditinjau permasalahan berikut.Sebuah kata sandi dibentuk dari tiga

huruf yang berbeda, yaitu a, b, dan c. Barisan yang terdiri dari lima atau kurang huruf-huruf

membentuk sebuah “kata sandi”. Kata sandi yang dibentuk terdiri dari paling banyak satu b,

paling banyak satu c, dan sampai tiga a. Ada berapa kata sandi dengan panjang k yang dapat

dibentuk?

Dalam hal ini yang dimaksud dengan panjang suatu kata sandi adalah banyaknya huruf

dalam kata sandi tersebut. Perhatikan bahwa “urutan” huruf-huruf dalam kata sandi

diperhatikan.Sehingga kita lebih tertarik dengan perhitungan permutasi daripada kombinasi,

banyaknya cara untuk mendapatkan k huruf bila diperkenankan mengambil paling banyak

satu b, paling banyak satu c, dan paling banyak tiga a. Untuk itu, fungsi pembangkit dari

permasalahan menentukan banyak cara memilih k huruf (dengan syarat yang ditentukan)

adalah:

(1+ax+a2 x2+a3 x3 )(1+bx )(1+cx ) atau

1+( a+b+c )x+(a2+ab+ac+bc ) x2+(a3+abc+a2b+a2 c )x3

+

(a2 bc+a3b+a3 c )x4+a3bcx5

……………………………………....….. (2.5)

Koefisienxkdalam persamaan (2.5) menginformasikan semua cara yang mungkin untuk

mendapatkan k huruf. Misalnya 4 huruf dapat diperoleh sebagai berikut.

26

a, a, b, dan c

a, a, a, dan b;

atau

a, a, a, dan c.

Menurut Teorema 1, bila dipilih a, a, b, dan c, maka akan terdapat

4 !2! 1 ! 1 ! = 12 permutasi

yang bersesuaian, yaitu:

aabc, aacb, abac, abca, acba, bcaa, baac, baca, cbaa, caab, caba. …….

Bila dipilih a, a, a, dan b; maka terdapat

4 !3! 1! = 4 permutasi yang bersesuaian, yaitu

aaab, aaba, abaa, dan baaa

Perhatikan bahwa untuk a, a, a, dan c; terdapat

4 !3! 1! = 4 permutasi yang bersesuaian, yaitu:

aaac, aaca, acaa, dan caaa

Dengan demikian banyak cara untuk mendapatkan kata sandi dengan panjang 4 diberikan

oleh:

4 !2! 1 ! 1 ! a2bc +

4 !3! 1! a3b +

4 !3! 1! a3c ……………….………………….(2.6)

Untuk a = b = c = 1, akan memberikan perhitungan yang tepat untuk menentukan

banyak kata sandi dengan panjang 4.

Sebenarnya untuk mendapatkan (2.6) dan koefisien-koefisien yang lain,

dapatdigunakan

(ak )k

k ! sebagai ganti dari (ak )kuntuk memperoleh fungsi pembangkit dari

permasalahan menentukan banyaknya kata sandi dengan panjang k yang dapat dibentuk.

Dengan demikian fungsi pembangkitnya menjadi

[1+ ax1!

+ a2 x2

2 !+ a3 x3

3 ! ][1+ bx1 ! ] [1+ ax

1 ! ],yang sama dengan

1 +( a

1!+ b

1 !+ c

1 ! ) x +

( a2

2!+ ab

1 ! 1!+ ac

1 ! 1!+ bc

1 ! 1! ) x2

+ ( a3

3 !+ abc

1 ! 1 ! 1!+ a2b

2 ! 1!+ a2 c

2 ! 1 ! ) x3

+

( a2 bc2! 1! 1 !

+ a3 b3! 1!

+ a3 c3 ! 1! ) x4

+

a3 bc3! 1! 1 !

x 5

…………………………………….….... (2.7)

Ternyata skema ini belum merupakan skema yang memuaskan, karena koefisien x4

dalam (2.7) belum identik dengan koefisien x4

dalam (2.6). Akan tetapi skema ini sesuai,

27

bila hal ini dipikirkan sebagai Fungsi Pembangkit Eksponensial (FPE) dengan

memperhatikan koefisien dari

xk

k ! . Perhatikan bahwa ekspresi (2.7) sama dengan

1+1 !( a

1!+ b

1 !+ c

1 ! ) x1! +

2 !( a2

2 !+ ab

1 ! 1 !+ ac

1 ! 1 !+ bc

1 ! 1 ! ) x2

2 ! +3!( a3

3 !+ abc

1 ! 1 ! 1!+ a2b

2 ! 1!+ a2 c

2 ! 1 ! ) x3

3 ! +4!

( a2 bc2! 1! 1 !

+ a3 b3! 1!

+ a3 c3 ! 1! ) x4

4 ! + 5 !( a3 bc

3 ! 1 ! 1! ) x5

5 ! ………..………………………...… (2.8)

Terlihat bahwa koefisien x4

dalam (2.6) samadengan koefisien

x4

4 ! dalam (2.8). Jika a,

b, dan c dalam (2.8) masing-masing disubtitusikan dengan 1 diperoleh fungsi pembangkit

dari permasalahan di atas, sebagai berikut.

1+1 !( 1

1!+ 1

1 !+ 1

1 !) x1! +

( 2!2!

+ 2 !1 ! 1!

+ 2 !1 ! 1!

+ 2 !1 ! 1! ) x2

2 ! +( 3 !

3 !+ 3 !

1 ! 1 ! 1!+ 3 !

2 ! 1!+ 3 !

2 ! 1 !) x3

3 ! +

( 4 !2! 1! 1 !

+ 4 !3! 1!

+ 4 !3 ! 1! ) x4

4 ! + ( 5!

3 ! 1! 1! ) x5

5 ! ………..………..…………………...… (2.9)

= (1 +

x1!

+ x2

2!+ x3

3 !)(1+ x

1!)(1+ x

1 !)

Koefisien

xk

k ! dalam fungsi pembangkit ini menyatakan banyaknya kata sandi dengan

panjang k yang dapat dibentuk dengan aturan yang telah ditetapkan. Misalnya, terdapat

( 4 !2! 1! 1 !

+ 4 !3! 1!

+ 4 !3 ! 1! ) = 20 kata sandi dengan panjang 4, terdapat

( 3 !3 !

+ 3 !1 ! 1 ! 1!

+ 3 !2 ! 1!

+ 3 !2 ! 1 !) =

13 kata sandi dengan panjang 3, dan seterusnya.

Sebagai perluasan dari uraian di atas, diperoleh teorema berikut ini.

Teorema 2

Misal terdapat p macam (tipe) objek dengan ni objek tipe i untuk 1 i p. Banyaknya

permutasi dengan panjang k dengan paling banyak ni objek tipe i samadengan koefisien

xk

k ! dalam fungsi pembangkit eksponensial berikut.

P(x) = (1+x+ x2

2!+. ..+ xn

n1 ! )(1+x+ x2

2!+. ..+ xn

n2 ! )…

(1+x+ x2

2!+. ..+ xn

np ! )28

Proporsi berikut, penting dalam pemecahan permasalahan yang melibatkan fungsi

pembangkit eksponensial

Teorema3

1.(1+x+ x2

2!+ x3

3 !+ .. ..)n

= 1 + nx +

n2 x2

2 ! +

n3 x 33 ! + ….

2.

ex+e−x

2 = 1 +

x2

2! +

x4

4 ! +

x6

6 ! +….

3.

ex−e−x

2 = x +

x3

3! +

x5

5! +

x7

7 ! +….

Definisi

Barisan kuartener adalah barisan yang suku-sukunya hanya menggunakan angka-angka 0, 1,

2, 3. Barisan kuartener r-angka adalah barisan kuartener dengan panjang r. Misalnya 1200323

atau 3101121 adalah barisan kuartener 7-angka. Barisan binair adalah barisan yang suku-

sukunya hanya menggunakan angka 0 atau 1. Barisan binair r-angka adalah barisan binair

dengan panjang r. Misalnya, 101001 atau 100111 adalah barisan binair 6-angka.

Contoh2.8

a. Berapakah banyaknya barisan kuartener r-angka yang memuat paling sedikit: satu 1, satu

2, dan satu 3?

b. Berapakah banyaknya barisan binair r-angka yang memuat 0 sebanyak banyak bilangan

genap dan 1 sebanyak genap.

Jawab

a. Terdapat 4 angka yang berbeda, yaitu 0, 1, 2, dan 3. Angka 0 bisa muncul 0 kali, 1 kali, 2

kali, dan seterusnya; sedangkan untuk setiap angka 1, 2, atau 3 dapat muncul paling

sedikit sekali dan urutan angka dalam suatu barisan diperhatikan, maka untuk menjawab

permasalahan di atas kita gunakan fungsi pembangkit eksponensial (FPE) sebagai

berikut.

P(x) = (1+x+ x2

2!+ x3

3 !+ .. ..)(x+ x2

2+ x3

3 !+.. . .)3

= ex ( ex−1 )3 = e

x ( e3 x−3 e2 x+3 e x−1 )

= e4 x−3e3 x+3 e2 x−ex

29

= ∑r=0

∞ (4 x )r

r !−3∑

r=0

∞ (3 x )r

r !+3∑

r=0

∞(2x )r−∑

r=0

∞ xr

r !

Banyaknya barisan yang dimaksud samadengan koefisien dari

xr

r ! dalam P(x), yaitu

4r−3 . 3r+3 .2r−1 atau 4r−3r+1+3 . 2r−1 .

b. Dalam hal ini ada dua angka yang berbeda yaitu 0 dan 1. Karena 0 dan 1 muncul

sebanyak bilangan genap untuk setiap barisan, maka fungsi pembangkit dari persoalan

tersebut adalah;

P(x) = (1+ x2

2+ x4

4 !+ x6

6 !+. . ..)2

= ( ex+e−x

2 )2

=

e2 x+e−2 x+24

=

12 ( e2 x+e−2 x

2 )+12

=

12 (1 +

(2 x )2

2 ! +

(2 x )4

4 ! +

(2 x )6

6 ! +….)+

12

= 1+2

x2

2 !+23 x4

4 !+25 x6

6 !+. .. .

Banyaknya barisan yang dimaksud samadengan koefisien

xr

r ! dalam P(x), yaitu

{0 , bila r ganjil ¿ {1 , bila r=0 ¿ ¿¿¿Fungsi Pembangkit Eksponensial ((FPE) dapat digunakan untuk memecahkan masalah

pendistribusian objek-objek yang berbeda ke dalam sel-sel (tempat-tempat) yang berbeda.

Contoh2.9

Tentukan banyaknya cara menempatkan n orang ke dalam 100 kamar sedemikian sehingga

setiap kamar berisi paling sedikit satu dan paling banyak dua orang .

30

Jawab

Masalah ini akan diselesaikan dengan menggunakan Fungsi Pembangkit Eksponensial.

Fungsi pembangkit yang bersesuaian dengan masalah di atas adalah sebagai berikut.

Misal P(x) = (x+ x2

2! )100

= x100(1+ x

2 )100

= x100

∑t=0

100(100¿ )¿¿

¿¿¿

= ∑t=0

100(100¿ )¿¿

¿¿¿

= ∑t=0

100(100¿ )¿¿

¿¿¿

= ∑

n=100

200( 100 ¿ )¿¿

¿¿¿

Banyaknya cara yang dimaksud adalah koefisien

xn

n ! , yaitu

( 100 ¿ )¿¿

¿¿atau

( 100 ¿ )¿¿

¿¿

Latihan Soal

31

1. TentukanFungsi Pembangkit Biasa (FPB) dalam bentuk paling sederhana dari masing-

masing fungsi numerik berikut ini.

a. (1 , −2 , 3 , −4 , 5 , −6 , .. .. ) e. (0 x 50 , 1 x51 , 2 x52 , . . ., rx 5r , .. . . )

b.(1 ,

23

,39

,4

27, .. . ,

(r+1 )3r

, .. ..)f.

(0 , 0 , 0 , 0 ,12

, 1 ,32

, 2 ,52

, 3 , . . ..)c. (1, 1, 2, 2, 3, 3, 4, 4, ….) g. (0, 1, 0, 1, 0, 1, ….)

d. (0 x1 , 1 x 2 , 2 x 3 , 3x 4 ,. .. .) h. (0, 1, 0, 2, 0, 3, 0, 4, ….)

2. Tentukan Fungsi Pembangkit Biasa dari fungsi numerik (ar ) dengan ar didefinisikan

sebagai berikut.

a. ar=¿ {2r ; jika r genap ¿ ¿¿¿

b.ar=3 r−4

3. Tentukan Fungsi Pembangkit Eksponensial dari fungsi numerik berikut ini.

a. (3, 3, 3, 3, ….)d. an=3n

b. (0, 1, 0, 1, 0, 1, ….)

e. an=

n+1n !

4. Tentukan barisan (fungsi numerik) yang bersesuaian dengan Fungsi Pembangkit

Eksponensial berikut.

a. A( x )=5+5 x+5 x2+5 x3+ .. ..

b.A( x )= 1

1−4 x

c. A( x )=ex+e4 x

5. Tentukan barisan (fungsi numerik) yang bersesuaian dengan fungsi-fungsi pembangkit

biasa berikut ini.

a. A(x) =

1

1−x3A(x) = 1 +

11−x

b. A(x) =

1

x2−6 x+5 A(x) =

c. A(x) =

7 x2

(1−2 x )(1+3 x ) A(x) =

11−3 x

+ 4 x3

1−x

d. A(x) =

1+x2

4−4 x−x2P(x) =

1+ x+x2−x3

1−x

32

6. Tentukan banyaknya cara mengambil 100 huruf dari huruf-huruf pembentuk kata

KOMBINATORIK sedemikian hingga setiap konsonan terpilih paling banyak 20.

7. Tentukan banyaknya solusi bulat dari persamaan berikut.

x1+x 2+x3+x4=80 , 1≤x i≤30 , ∀ i ∈ {1,2,3,4}

8. Tentukan banyaknya barisan ternair n-angka yang memuat angka “0” sebanyak ganjil dan

angka “1” sebanyak genap.

9. Tentukan banyaknya barisan biner n-angka yang memuat angka “1” paling sedikit dua.

10. Tentukan banyaknya barisan ternair n-angka yang memuat angka “0”, “1”, dan “2”

masing-masing sebanyak ganjil

33