FUNGSI PEMBANGKIT DAN RELASIREKURSI
Pada bab 9 yang lalu telah dibahas eara menyelesaikan suatu relasi rekursi. Umumnya bila diberikan s~atu problema peneaeahan, maka sangat sulit untuk dapat ditentukan relasi rekursi yang memenuhi problema tersebut. Bila misalnya telah berhasil diketemukan relasi rekursi yang memenuhi problema tersebut, maka penyelesaiaan relasi rekursi tersebut biasanya sulit sekali dikerjakan. Jadi sedapat mungkin harus dieari eara lain untuk dapat menyelesaikan problema peneaeahan tanpa harus menyelesaikan suatu relasi rekursi. Pada Bab ini akan diperkenalkan suatu eara penyelesaian relasi rekursi menggunakan teknik fungsi pembangkit, yang pertama kali dijabarkan oleh Euler.
FUNGSI PEMBANGKIT Definisi 10.1 Pandang ~, aI''''' an' ... adalah barisan bilangan dengan indeks n. Fungsi pembangkit atau generating function dari barisan tersebut didefinisikan sebagai deret pangkat
Dalam membicarakan fungsi pembangkit ini masalah konvergensi deret tersebut tidak akan diperhatikan. Dalam hal ini yang diperhatikan adalah bahwa penulisan tanda Xo= I, x\, "., xn' yang diinterpretasikan sebagai penulisan tanda aljabar atau simbol yang mewakili bermaeam-maeam suku dari barisan
~
+ al"'"
an' dan seterusnya.
Karena suatu barisan yang hingga dapat dikatakan sebagai barisan yang tak hingga dengan an+\
= an+2 = ." =0, maka
semua pembicaraan pCldabab ini juga
berlaku untuk barisan yang hingga.
CONTOH Contoh 10.1 Misalkan m adalah bilangan bulat positif, maka fungsi pembangkit fm(x) untuk barisan koefisien binomial
204
adalah
dan menurut rumus binomial Newton. maka bentuk ini adalah sarna dengan (1+x)m. Lebih umum lagi bila a. suatu bilangan riil sembarang. maka fungsi pembangkit fa.(x) untuk barisan koefisien binomial ,
...
adalah fa. (x)
yang berdasarkan teorema binomial Newton dapat ditulis sebagai fa.(x)
= (1 + x)a.
Contoh 10.2 Akan dicari fungsi pembangkit gx(x) daTi barisan bilangan aQ' an' di sini an menyatakan jumlah kombinasi-n dari suatu himpunan ganda dengan k > o obyek yang berbeda. dan masing-masingobyek meinpunyai faktor pengulangan yang tak hingga. Pada pembahasan terdahulu telah dapat dihitung bahwa
205
Jadi fungsi pembangkit yang dieari adalah
dengan menggunakan teorema binomial Newton, maka dapat diperoleh bentuk
1 gk(x) =
(l-x)k
=
(l-x)"k
sebagai salah satu hal khusus, yaitu barisan bilangan 1, 1, 1, 1,..., untuk mana fungsi pembangkitnya adalah
dan fungsi pembangkit dari barisan lain yaitu I, 2, 3, ..., n adalah
Sekarang pandang suatu eontoh yang mirip dengan perl1itungan (l+x)D, yaitu eara perhitungan (a+x)3. Bentuk ini dapat ditulis sebagai (a+x)(a+x)(a+x)
untuk harga a
= aaa
+ aax + axa + axx + xaa + xax + xxa + xu
= 1, diperoleh
(1+x)(1+x)(1+x)= 111 + 11x + Ixi + Ixx + xlI + xIx + xxi + xu Hal ini membentuk suatu daftar semua eara untuk mengalikan suatu suku pada faktor yang pertama dengan suku pada faktor yang kedua dan suku lain pada faktor yang ketiga. Problema menentukan koefisien dari xr, pada ekspansi (x+1)3atau (l +X)Dpada umumnya, berubah menjadi problema menghitungjumlah eara yang berbeda untuk membentuk faktor yang terdirir dari sejumlah r dari x 206
dan sejumlah (n-r) dari 1. Jadi koefisien dari xr dalam (x+ 1)3 adalah
( ~) dan dalam (1+X)n, adalah
(;)
Yang paling penting dalam hal ini adalah menginterpretasi hasil perkalian sejumlah faktor yang masing-masing merupakansuatu polimonial dalam x. Dalam
hal .ini perkaliantersebut dilihat sebagai suatu cara untuk membentuksemua hasil perkalian yang dapat dilakukan dengan mengalikan semua suku dari tiap-tiap faktor polinomial yang ada. Bila ada sejumlah n faktor polinomial, serta setiap faktor polinomial ke-Lmengandung sejumlah ri, suku yang berbed~ maka akan dapa~ dibentuk sejumlah
hasil perkalian berbeda. Hal ini mudah dilihat untukspansi bentuk (1+x)n, yang mengandung n faktor polinomial dan masing-masing polinomial mengandung 2 suku, maka akan diperoleh 2n bentuk perkalian yang berbeda.
Contoh 10.3 Akan dihitung suatu fungsipembangkityang dibentukoleh
maka himpunan semua hasil kali yang mungkin diperoleh adalah [1] [x],
[1] [x],
[1]
[1]
[1]
[x],
[x],
[x].
[x2]
[x2]
Jadi setiap hasil perkalian akan ada 1 atau x pada 3 tempat yang pertama, dan ada satu atau x atau x2 dan tempat ke 4 dan ke 5. Salah satu hasil perkalian yang mungkin adalah Ix lx2x
207
yaitu tempat pertama diisi suku 1; tempat kedua diisi suku x, tempat ketiga diisi suku 1, keempat diisi suku x2 dan tempat kelima diisi suku x. Karena harga suku 1 dapat ditulis sebagai xfJ,maka bentuk perkalian yang mungkin dibuat dalam hal ini dapat juga dituliskan sebagai [xfJ]
[xfJ] [xfJ] [xfJ] [xfJ]
[x],
[x],
[x],
[x],
[x2]
[x2]
[x].
Persoalan untuk menentukan koefisien dari suku xl dari perkalian beberapa faktor polinomial seperti di atasdapat dinyatakan sebagai jumlah suku dari pangkat. Pada contoh di atas, pandang koefisien dari x4, yang merupakan hasil ekspansi dari
Koefisien ini merupakan jumlah dari semua perkalian yang menghasilkan faktor X4. Persoalan ini dapat pula dilihat sebagai suatu problema mencari sejumlah bilangan bulat yang memenuhi suati persamaan tertentu. Persoalan itu dapat ditulis sebagai berikut. Carilah semua bilangan bulat yang mungkin diperoleh pada persamaan
di sini e1, e2, e3, masing-masing bemilai 0 atau I, sedangkan e4 dan es masing-masing bemilai 0, 1 atau 2. Perhatikan bahwa dalam problema yang baru didefinisikan ini harga masing-masing eI merupakan pangkat atau eksponen dari setiap suku yang ada pada tiap faktor polinomial.Persoalan inijuga dapat dilihat sebagai suatu problema yang menghitung banyaknya cara untuk mengambil 4"'buahbola dari 5 jenis bola yang ada. Dalam hal ini bola jenis pertama, kedua dan ketiga hanya ada satu, sedangkan jenis bola keempat dan kelima ada dua buah. Cara pengambilan bola ini boleh berulang, dalam arti setiap jenis bola boleh tidak diambil, atau diambil sebanyak mungkin, tergantung dari jumlah bola yang ada untuk tiap jenis bola. Hanya saja kendala yang hams dipenuhi adalah jumlah keseluruhan bola yang hams diambil adalah 4. 208
Cara lain untuk melihat problema di atas adaIah banyaknya eara untuk mendistribusikan 4 buah bola yang sarna ke daIarn 5 buah kotak yang tersedia, di mana kotak pertama, k~ua dan ketiga hanya marnpu menerima maksimum satu bola, sedangkan kotak keempat dan kelima dapat menerima maksimum 2 bola. Dari pembatasan ini semua dapat disimpulkan bahwa koefisien x4 dari ekspansi.
merupakan jawab dari problema I.
el + ez + e3 + e4 + es
.dengan
= 4 p73
0 ~ el' ez' e3 ~ I, dan 0 ~ e4, es ~ 2
2.
Koefisien tersebut juga menyatakan banyaknya eara memilih 4 bola dari 5 jenis bola yang ada.
3.
Atau juga banyaknya eara mendistribus~an 4 bola yang sarna ke daIarn 5 kotak yang berbeda seperti diterangkan di atas. Dalam hal ini fungsi
dikatakan sebagai fungsi pembangkit dengan koefisien ar yang menyatakan banyaknya jawaban yang mungkin pada ketiga problema yang telah disebutkan di atas. Pada bagian ini hanya diperhatikan bagaimana earanya membentuk suatu fungsi pembangkit yang dapat memberikan jawaban pada suatu problema peneacahan. Bagian berikutnya akan dilihat bagaimana manipulasi aIjabar yang dapat dilakukan pada suatu fungsi pembangkit sehingga dapat dihitung koefisien-koefisien yang diperlukan. Pada contoh tadi diterangkan bagaimana koefisien dari ekspansi beberapa fungsi polinomial dapat digunakan untukmenjawab berbagai problema kombinatorik yang diberikan. Contoh berikut ini akan melihat problema tersebut dari arah yang berlawanan. Di sini akan dijelaskan eontoh untuk membentuk fungsi pembangkit yang memenuhi suatu problema komb!natorik tertentu. 209
Contoh 10.4 : Pandang 4 buah kotak, masing-masing berisi 3 buah bola hijau, 3 buah bola putih, 3 buah bola biru,Jian 3 buah bola merah. Akan ditentukanfungsi pem'bangkit dari ar yang menyatakan banyaknya cara untuk memilih r buah bola dari kotak tersebut. Seperti pada pembahasan soal yang baru lalu, maka pada soal ini problema yang diberikan dapat dirubah ke dalam model berikut. e I + e2 + e3 + e4
=r
' , . d1 sml 0 < _ el, e2, e3, e4 < - 3,
Dalam hal ini e I menyatakan jumlah boi-'ahijau' yang diambil, e2 menyatakan jumlah bola putih yang diambil, e3 menyatakan jumlah bola biru yang diambil, sedangkan e4 menyatakan jumlah bola merah yang diambil. Untuk problema ini fungsi pembangkit dapat dibentuk dengan memperhatikan 4 buah faktor polinornial yang masing-masing mempunyai tingkat antara 0 sampai dengan 3. Suku-suku dari faktor polinomial yang akan membentuk fungsi pembangkit adalah
[1>] [xl] [xl] [x2] , [x2] , [x3] [x3]
[xO]
[1>] [xl] [x2] , [x3]
[1>] [xl] [x2] [x3]
Dengan demikian jumlah perkalian keempat pangkat yang jumlahnya r akan merupakan jawab dari problema yang diberikan. Jadi fungsi pembangkit yang dicari adalah
Contoh
10.5
Tentukan fungsi 'pembangkit dari ar yang menyatakan jumlah cara untuk mendistribusikan r buah bola yang sarna ke dalarn 5 buah kotak yang diberikan dengan kendala sebagai berikut. Kotak pertama dan kedua masing-masing hanya dapat diisi oleh sejumlah genap bola dan maksimum akan berisi 10 bola saja, sedangkan kotak ketiga, keempat dan kelima masing-masing hanya dapat diisi oleh paling sedikit 3 bola dan paling banyak 5 bola saja. 210
Walaupun kendala yang diberikan kelihatannya sedikit rumit, tetapi eara penyelesaian dari problema ini temyata mudah sekali. Dengan menggunakan persamaan dengan jawab bilangan bulat, maka problema di atas dapat ditulis sebagai berikut: Cari jawab problema berikut dengan e) ... es adalah bilanganbulat.
di sini e) dan e2 adalah bilangan genap dan 0 ~ e)' e2 ~ 10, serta 3 ~ e3, e4, es ~ 5. Dari bentuk problema ini maka jelas bahwa fungsi pembangkit yang dieari akan berbentuk
Dalam hal ini dua faktor polinomial yang pertama berhubungan dengan dua kotak yang pertama dengan kendala yang diberikan pada kedua kotak terse"ut, sedangkan tiga faktor polinomial yang terakhir.berhubungan dengan tiga kowk yang terakhir lengkap dengan kendala yang didetinisikan padanya. Dari eontoh-eontoh ini terlihat bahwa bila problema awal sudah dituliskan kembali dalam bentuk persamaan dengan jawab s~jumlah bilangan bulat positif, maka probler.la untuk meneari fungsi pembangkit yang memenuhi problema awal tersebl't akan menjadi mudah sekali untuk diselesaikan. Dalam hal ini setiap faktor polinomial hanya akan dilihat sebagai harga dari pangkat saja. Artiny untuk setiap harga k yang diberikan oleh ej, maka faktor polinomial ke i akan mempunyai suku xk. Dalam hal ini faktor polinomial ke i memberikan semua kemungkinan dari pangkatnya untuk menjadi harga dari ej. Dengan sedikit latihan maka fungsi pembangkit dapat dengan mudah dibuat, berdasarkan problema eara pemilihan atau distribusi sejumlah bola. Tetapi konsep dasar dari fungsi pembangkit sebenamya jauh lebih rumit dari hal yang baru saja diterangkan. Penyelesaikan eara pemilihan atau distribusi bola dapat juga duseleseikan dengan menggunakan koetisien binomial. Sekarang problema ini diselesaikan hanya dengan menuliskan hasil perkalian dari sejumlah faktor polinomial saja. Dalam hal ini fungsi pembangkit tidak dapat dibuat untuk menjawab satu problema saja, misalnya untuk menjawab satu problema dengan sepuluh bola saja. Fungsi pembangkit digunakan untuk menjawab semua kemungkinan yang 211
terjadi. Beberapa problema peneaeahan yang sulit akan dipeeahkanmenjadi .
beberapaproblemakeeiluyangtidakterlalusuiit. Fungsipembangkitini dengan sendirinya telah melakukan pembagian problema ini kes dalam beberapa problema yang lebih mudah dalam satu fungsi pembangkit yang diberikan. Bagian berikut ini akan diterangkan bagaimana manipulasi aljabar dapat dilakukan pada beberapa problema yang b~rhubungan dengan fungsi pembangkit suatu problema. Oalam eara ini model dari problema peneaeahan dari pemilihan atau pendistribusian bola yang rumit tidak perlu diperhatikan.
PERHITUNGAN KOEFISIEN FUNGSI PEMBANGKIT Pada bagian ini akan dikembangkan beberapa teknik aljabar yangdapat digunakan iuntuk menghitung koefisien dari fungsi pembangkit. Semua metode ini digunakan untuk mengurangi tingkat kesulitan dari suatu fungsi pembangkit ke dalam fungsi pembangkit yang lebih sederhana yang berhubungan dengan ekspansi fungsi binomial atau multi nomial. Untuk memuadahakan perhitungan selanjutnya, maka berikut ini diberikan beberapa persamaan yang berhubungan dengan ekspansi suatu polinomial. I - xn+\
=I +x
1.
+ x2 + x3 +
... + x"
1- x Hal ini mudah ditunjukkan dengan mengalikankedua sisi dari persamaan dia tas dengan faktor (I-x). Sisi kiri akan menghasilkan I
- x"+\,
sedangkan
sisi
kanan merupakan penjumalahan dari 1 + x + x2 + x3 + ... + x" dan - x - x2 - ... - x" - x"+1 lumlah dari kedua polinomial ini adalah 1 - x"+\.
=
2.
1+x +
r
+ x3+ ... + X' + ...
I-x Hal ini dapat. ditunjukkan dengan eara yang hampir sarna dengan eara sebelumnya. Hanya saja dalam hal in. harga n dibuat menuju tak berhingga 212
atau besar sekali. Dengan demikian setiap koefisien xk di mana k > 0 akan bernilaiO.Jadi dapat disimpulkanbahwa
(~)
x +
(;) r
+
...
(;) x +... ( : )
x".
Hal ini tidak perlu diterangkan karena merupakan ekspansi binomial biasa yang sudah peIT"Ihdibicarakan sebelumnya. 4.
(1 + X")n= 1 -
(t)
X" +
(;) rm + ... + (-1)' (;) x"" +
... (_1)"
Hal ini merupakan perluasan dari bentuk binomial sebelumnya di mana harga x pada rumus sebelumnya diganti dengan bentuk (-x"'), dan dengan menggunakan rumus ekspansi binomial diperoleh
dan dibentuk terakhir ini sarna dengan bagian kanan dari persamaan di atas.
5.
(r+;-I) x+... 213
Untuk menunjukkan hal ini pandang bentuk (l-xtn = 1 ( l-x)n yang telah ditunjukan besarnya sarna dengan ( 1 + x + Xl + x3 + ... )n Persoalan ini sarna dengan penyelesaian berikut
di sini masing-ma.<;ingei ~ O. Dan problema ini sarna dengan problema mengambil r bola dari n jumlah bola.padamasing-masing jenis bola adalah tak berhingga.
Dan jawab dari problema ini adalah koefisien dari x2 di atas. 6.
Bila h(x) fix)
= f(x) g(x),
di sini
= ao + atx
+ a2Xl"+ ...
= bo + btx
+ bf- + ...
dan g(x)
maka fungsi pembangkit untuk h(x) adalah
h(x) =a{)bn+ (a,bn + anbJ)x+ (a2bo+ a,b, + aOb2)r+ ...+ (a,bo+ ...+ aob,}X +
...
Rumus ini dapat dengan mudah dibuktikan dengan mengalikan kedua polinomial yang mewakili fungsi pembangkit dari f(x) dan g(x). Dengan menggunakanrumus di atas, maka dengan mudah dapat dihitung koefisien dari bermaeam fungsi pembangkit.Hal yang harns dilakukan adalah pertama melakukan penyederhanaanbentuk fungsi pembangkitke dalarn salah satu bentuk sederhana seperti di atas. Kemudian dengan menggunakan aturan perkalian yang diberikan dapat ditebak dengan mudah koefisien dari fungsi pembangkit yang dieari. 214
Contoh 10.6 Cari koefisien dari x 16pada ekspansi
Secara umum tentukan koefisien dari r. Untuk menyelesaikan problema ini pertama-tama dikeluarkan dulu suku x2dari faktor polinomial tersebut, kemudian gunakan rumus kedua di atas. =
[x2 (I + x + x2 + ...)]5 ( x2 ) (I-x)
Dengan demikian koefisien dari x16 pada fungsi pemabangkit yang dipersoalkan akan sarna dengan koefisien dari x16 pada fungsi yang terakhir diperoleh ini maka koefisien dari xl6 akan sarna dengan koefisien x6 dari bentuk (I-x)-5. Dan dari rumus ke lima di atas diperoleh bahwa besarnya koefisien x6 ini
adalah (6+:-1 ) Secara umum besarnya koefisien xr pada fungsi pembangkit yang diberikan adalah sarna dengan koefisien[/0 dari fungsi x6 dari bentuk (1-xt5, yang hasilnya adalah P-IO)+S-l
(
(r-lO)
)
Perhatikan bentuk (x2 + x3 + ...)5 adalah fungsi pembangkit yang juga menyatakan banyaknya cara untuk mendistribusikan sebanyak r bola yang sarna ke dalam lima buaf kotak yang berbeda, di mana masing-masing kotak harns diisi minimum dua buah bola. Cara menyelesaikan problema ini adalah pertama-tama dengan mendistribusikan masing-masing dua buah bola pada tiap kotak yang tersedia, kemudian sisa dari bola yang ada yaitu (r-IO) didistribusikan sembarang pada kelima kotak yang ada. Pada pendistribusian sisa bola ini tidak ada kendala sarna sekali yagn harns 215
dipenuhi oleh masing-masing kotka, karena masing-masing kotak tersebut telah berisi minimum dua bola. Oalam hal fungsi pembangkit hal ini dilakukan dengan mengeluarkan faktor xl dari kelima faktor polinomial yang ada, sehingga sisa dari fungsi pembangkit hanya berhubungan dengan problema pendistribusian sisa dari bola (r-1O) ke dalam lima buah kotak tanpakendala apa-apa. Teknikaljabar seperti ini, yaitu menarik ke luar pangkat dari x yang tertinggi dari suatu faktor polinomial berhubungan dengan cara penyelesaian problema distribusi bola tersebut. Oalam hal ini teknik aljabar yang digunakan secara otomatis telah melakukan langkah kombinatorik yang perlu dilakukan untuk menyelesaikan problema yang permulaan diberikan.
Contoh 10.7 Misaikan dalam suatu pesta ada 20 orang dan akan dikumpulkan uang sejumlah 15.000 ribu rupiah. Oari 20 orang yang ada, maka 19 orang hanya dapat menyumbangkan uang 1000 rupiah, atau 5000 ribu rupiah atau tidak menyumbangkanuang sarna sekali, sedangkanseorang lagi dapat menyumbangkan uang sejumlah 1000 rupiah, atau 5000 rupiah atau tidak menyumbangkan sarna sekali. Akan ditentukan fungsi pembangkit yang dapat memberikan jawaban pada problema tersebut. Kita tahu bahwa banyaknya cara untuk mengumpulakan sejumlah r-ribu rupiah dari orang.orang ini dapat dinyatakan dalam fungsi pembangkit berikut
dan dalam problema ini yang kan dicari adalah koefisien dari xiS. Faktor polinomial perta'Tladari fungsi pembangkit tersebut di atas dapat dituliskan dalam bentuk ekspansi binomial seperti
Bila faktor polinomial yag pertama ini disebut f(x) dan faktor polinomial yang kedua g(x)=I+x+r.;,makajawab dari problema ini adalah koefisien dari xiS dari fungsi h(x)= f(x) g(x). Misalkan
216
ini adalah koefisien dari X pada f(x) dan br adalah koefisien dari X pada g(x). Maka dengan menggunakan rumus ke enam dapat dihitung koefisien X pada h(x) yang besamya adalah
dan karena koefisien dari faktor polinomial g(x) kebanyakan bemilai nol, kecuali bo' bl' b5. maka besaran terakhir ini akan tereduksi menjadi
dengan demikian koefisien xl5 dari h(x) adalah
G~).I
+ Cl~).1+ G~).I,
atau
Contoh
10.8
Misalkan akan didistribusikan sejumlah 25 bola yang sejenis ke dalam 7 buah kotak yang berbeda. Kotak pertama tidak dapat diisi oleh lebih dari 10 bola, sedangkan kotak lainnya dapat diisi oleh berapa bola saja. Fungsi pembangkit untuk menunjukkan banyaknya eara mendistribusikan r buah bola ke dalam 7 kotak dengan kotak pertama hanya dapat maksimum diisi oleh 10 bola adalah
(1
)6
=
(l-x )
(I-x)
217
Dengan memisalkan f(x)
= (l-xt7
dan g(x)
= (l-x-II),
maka dengan
mengekspansikanf(x) denganmmus ke lima akan dapat diperoleh
Karena yang ingin dicari adalah koefisien x25 dari h(x), maka dengan cara yang sarna seperti pada contoh sebelum ini besarnya koefisien ini dapat dihitung dengan hanya rnemperhatikan suku tidak sarna dengan O.Jadi koefisien dari x25 adalah a25bo+ al4bll =
Jawaban ini dapat diinterpretasikan juga secara kombinatorik seperti nerikut ini. Pertama-tama ke 25 bola yang ~an didistribusikan tanpa suatu kendala apapun pada ke tujuh kotak yang disediakan. Carn ini banyaknya ada(25;;-I) Kemudian angka ini masih hams dikurangkan dengan sejumlah cara mendistribusikan bola yang tidak diperkenankan, yaitu mengisi kotak pertama dengan 11 bola terlebih dahulu, lalu sisa dari bola didistribusikan pada ke tujuh kotak yang tersedia. Carn ini banyaknya ada 25-11)+7-1 (25-11)
(
)
maka hasil akhir yang diperoleh akan sma dengan hasil yang telah diperoleh sebelumnya. Dari contoh ini lagi-Iagi terlihat bahwa fungsi pembangkit secara otomatis telah memenuhi kaidah kombiantorik yang berlaku. Contoh berikut ini akan menggunakan cara yang hampir sarna dengan cara yang digunakan pada contoh sebelum ini. Tetapi khusus untuk contoh berikut ini penyelesaian dengan argumentasi kombinatorik tidak dapatdigunakan untuk menyeh~saikanproblema yang diberikan.
218
Contoh 10.9 : Misalkan akan dipilih 25 mairiandari 7 jenis mainan yang ada. Datam pemilihanini masing-masingjenis mainan hams dipilih sedikitnya2 mainan, tetapi tidaka boleh lebih dari 6 mainan.Fungsipembangkittersebutadatah
dan yang akan dieari adalah koefisien dari x25. Untuk menyelesaikan hat ini maka faktor x2 dikeluarkan dan diperoleh bentuk
Dengan demikian problema yang akan diselesaikan sekarang telah tereduksi menjadi problema meneari koefisien dari x25-14=xl I dari (1 + x + x2 + x3 + x4)]1 Bentuk yang terakhir ini dapat ditulis kembali dalam bentuk
(1 + x + x2 + x3 + x4)]7 = (1-x)
BHa dimisalkan bahwa f(x) f(x)
= (1-xt7 = 1 +
= (1-xt7
dan g(x)
= (1-xS)7, maka diperoleh
e+~-l)X + (2+~-1)x2 +...
+ ... _ (~) x35. 219
Dan seperti eontoh sebelumnya, koefisien xII dari h(x)
= f(x) g(x) dapat
dieari denganhanya memperhatikansuku-sukuyang berbentuka Inbj di mana harga bi =/ O. Hasil akhir yang diperoleh adalah
=
Sebagai eontoh terakhir akan diberikan salah satu kegunaan fungsi pembangkit untuk membuktikan suatu kesamaam binomial. Dalam al ini bagian kanan dari suatu kesamaan binomial dinyatakan sebagai fungsi pembangkit binomial biasa, sedangkan bagian kirinya dinyatakan sebagai hasil kali dari dua fungsi pembangkit yang sarna.
Contoh 10.10 : Akan ditunjukkan kebenaran dari kesamaan koefisien binomial berikut ini
Ruas kanan kesamaan di atas merupakan koefisien dari x" dari suatu fungsi pembangkit (l+x)2n, yang dapat ditulis sebagai hasil kali dari (1+x)n dengan (l+x)n', Sedangkan untuk ekspansi yang demikian koefisien x" dinyatakan oleh
Maka koefisien x" pada perkalian dua fungsi (1+x)n dapat dinyatakan dengan oleh
= (~). (:)+(;).
(n~l)+'"+(:).(;)
= (n~
220
)+
(7 r
+ ...+ (: r
Untuk hal yang terakhir ini telah digunakan kesamaan
Dari dua cara. penulisan koefisien X' dari polinomial (1+x)".(1+x)"
= (1+x)2"
Ini telah dapat dibuktikan kebenaran dari kesamaan binomial di atas.
FUNGSI PEMBANGKIT EKSPONENSIAL Fungsi pemabangkit eksponensial yang akan dibicarakan di sini banyak berhubungan dengan problema yang melibatkan penyusunan dan pendistribusian dari beberapa obyek yang berbeda. Berlaianan dengan fungsi pembangkit yang biasa, fungsi pembangkit eksponensial 'mempunyai tingkat kesulitan yang lebih tinggi. Persoalan kombinatorik yang berhubungan dengan fungsi pembangkit eksponensial ini juga lebih sulitjika dibandingkan dengan problema kombinatorik yang berhubungan dengan fungsi pembangkit biasa. Pandang suatu problema yang menghitung jumlah dari penyusunan kata-kata yang terdiri dari 4 huruf, di sini huruf tersebut dipilih dari jumlah tak hingga huruf a, b dan c. Selain itu ada kendala tamabahan yaitu bahwa kata tersebut hams mengandung paling sedikit dua huruf a. Empat huruf yang telah dipilih dan memenuhi persyaratan yang tersebut di atas tadi akan membentuk suatu himpunan. Himpunan tersebut adalah {a,a,a,a}, {a,a,a,b},{a,a,a,c}, {a.a,b,b},{a,a,b,c}, {a,a,c,c}.Sedangkan untuk setiap himp~nan tersebut, dapat dilakukan sejumlah penyususnan huruf yang berbeda. Jumlah penyusunan yang mungkin dilakukan pada setiap himpunan tersebut adalah 4!
4!
4!
4!
4!
4!
4!O!0!
3!1to!
3!0!l !
2!2!0!
2!l!l !
2!0!2!
Dengan demikian banyaknya kata yang terdiri dari 4 huruf yang memenuhi kendala tersebut di atas adalah sarna dengan jumlah keenam bilangan di atas. 221
Perhatikan banyaknya himpunan yang mengandung sejumlah 4 huruf a, b dan c, di mana jumlah dari huruf a pada himpunan tersebut adalah dua. Banyaknya himpunan tersebut dapat dinyatakan dengan persamaan berikut ini
Sepintas lalu problema ini sarna dengan problema yang dibicarakan pada bagian sebelum ini. Tetapi bila diperhatikan lebih teliti lagi, maka hal ini tidak benar. Dalam .problema ini setiap jawaban el' e2, dan e3 yang dipeolrh hanya berhubungan dengan satu himpunan yang mungkin dibuat. Sedangkan banyaknya cara penyusunan dari anggota-anggota himpunan tersebut (hal yang dipertanyakan pada problema ini adalah sejumlah 4! ( ) el !e2!e3! kata. Dalam hubungannya dengan fungsi pembangkit, maka koefisien dari .0, tidak menyatakan banyaknya semua bentuk perkalian ;xe/,;xe2,;xe3,dengan el ~ 2 dan e I + e; + e3 = 4, melainkan menyatakan semua hasil perkalian yang
berhubungandengan koefisiendari
Dalam hal yang demikian fungsi pembangkit eksponensial menghasilkan bentuk perkalian yang seperti ini. Suatu fungsi pembangkit eksponeosial g(x) dari. ar' yang menyatakan ban'yaknya susunan yang mungkin dibuat (atau distribusi obyek yang berbeda) dari r buah obyek, adalah suatu fungsi yang mempunyai ekspansi deret pangkat seperti berikut
xlx3 . r g(x) = ao + a/x + a2 - 2! + a3 - 3! +... + ar - r! +...
Fungsi pembangkit eksponensial ini dibentuk dengan cara yang sarna denga11 cara pembentukan fungsi pembangkit biasa. Setiap faktor polinomial akan mewakili satu obyek (atatJ satu kotak). Setiap faktor akan mempunyai sejumlah pangkat dari x yang mempakan piliahan dari sejumlah obyek dengan jenis yang sarna. Bedanya dengan fungsi pembangkit biasa adalah pada fungsi pembangkit eksponensial setiap pangkat dari x akan dibagi dengan rL Pada contoh yang pertama diberikan akan dibentuk suatu kata dengan 4 humf yang mengandung minimum 2 humf a. Akan ditunjukkan bahwa fungsi pembangkit eksponensial dari kata-kata yang tereiri dari r-huruf yang dipilih dari sejumlah tak berhingga humf a, b dan c dan mengandung paling tidak 2 humf a adalah
g(x} =
(
~
x2 +
+x+-+
3!
2!
2!
3!
+.)'
Dalam hal ini koefisien dari x adalah jumlah dari selumh perkalian, di sini
Hal yang paling penting di sini adlah bila xr dibagi dengan r!, dan sebagai gant;nya selumh koefisien hams dikalikan dengan r!, maka suku x akan berbentuk r!
)
r!
di sini penjumlahan dilakukan untuk setiap ei yang memenuhi syarat e I + e2 + e3
= r,
2 ~ e I' dan 0 ~ e I' e2 xr Ternyata koefisien dari ini adalah bilangan yang sedang dicari
_
r!
dan dengan demikian telah ditunjukkan bahwa fungsi pembangkit eksponensial untuk problema ini memang benar seperti yang dituliskan di atas. Dalam hal ini fungsi pembangkit eksponensial ini dapat digunakan setelah dilakukan pembagian xr dengan r! d~ mengalikan koefisien dari x dengan rL
223
Contuh 10.11: Akan ditentukan fungsi pembangkit eksponensial dari ar yang m~nyatakan banyaknya susunanr'dari n obyek yang dapat dilakukan tanpa adanya pengulangan. Karena sudah pemah diketahui sebelumnya bahwa fungsi pembangkit yang digunakan adalah (1+x)n, maka
koefisien dari
r
adalah
r!
n'
r
(n-r)
r!
dan dengan demikian n! ar =
1
(n-r)
=
P(n,r)
yaitu pennutasi dari susunan r obyek yang ada tanpa ada pengulangan.
Contoh 10.12 : Tentukan fungsi pembangkiteksponensialdari aryang menyatakanbanyaknya susunan yang berbeda.dari r obyek, yang dipilih dari 4 jenis obyek yang ada, di sini jumlah tiap jenis obyek paling sedikit dua dan paling banyak lima kali. Di sini diketahui banyaknya cara untuk mengatur r obyek dengan e1 obyek ke i adalah r!
Apabila dilakukan penjumlahan dari setiap suku yang demikian, dengan memperhatikan kendala yang diberikan, maka bilangan yang dieari adalah koefisien dari
-r
r!
224
dalam
Contoh 10.13 : Akan dieari fungsi pembangkit eksponensial yang menyatakan banyaknya eara untuk menempatkan r orang yang berbeda dalarn 3 kamar yang berbeda, di mana setiap kamar hams diisi oleh paling sedikit satu orang. Jawab dari problema ini adalah
3
(
+~
x+~ 2!
+ ...
3!
)
Set1elumdiberikan eontoh lebih lanjut,.maka berikut ini diberikan beberapa kesarnaan atau ekspansi yang sring digunakan dalarn kaitannya-dengan fungsi pembangkit eksponensial. Dengan menggunakan kesamaan yang akan diberikan ini, maka sejumlah fungsi pembangkit eksponensial dapat dituliskan dalaril bentuk rumus yang tertutup. Ekspansi fungsi pembangkit eksponensial yang sering digunakan adalah eX = 1 + x +
x?
- 2!
x3
+
- 3!
r-
+
...- r!
+ ...
Bila harga x pada persamaan ini diganti dengan nx, maka akan diperoleh bentuk
f!'X
= 1 + (nx) +
+ ...
+ 2!
3!
+ ... r!
Oalam fungsi pembangkit eksponensial ini tidak dapat dilakukan mengeluarkan pangkat yang sarna dari x, tanpa mengganti penyebut rL Hal yang sering dilakukan adalah mengurangi pangkat yang hilang atau pangkat yang rendah dari x pad eX.Misalnya faktor eksponen yang menyatakan obyek tertentu minimum 2 kali dapat dituliskan sebagai
225
il
+
-
2!
x3
+-
3!
x4
+ ... =
eX
- I-x.
4!
Dua rumus ekspansi yang juga sering digunakan adalah il 1/2(eX+ e-X)= I +
2!
x4 +-+...-+... 4!
xlr
(2r)!
dan 1
/2 (eX
-
-x
e ) = I
+
-
x3
3!
+
-
xlr+l
x5
+
5!
...
+
...
(2r+1)!
Contoh 10.14 Akan dieari banyaknya susunan dari r obyek yang bisa dibentuk dari n jenis obyek yang ada, di mana masing-masing jenis obyek jumlahnya talc berhingga. Kita tabu bahwa obyek pertama dapat dipilih salah satu dari n obyek yang ada. Demikian pula I,lntukobyek kedua, dapat dipilih dari n obyek yang ada. Jadi untok r obyek dapat disusun dalam nr cara. BHaproblemaini akandiselesaikandenganmenggunakanfungsipembangkit eksponensial, maka fungsi pembangkit eksponensial yang digunakan adalah 1+x +
- il2!
(
+
x3
- 3!
+ ...
n
)
= (eX)n =
f!"X.
X
dan koefisien-
r!
padapersamaan ini adalah nr
Contoh 10.15 Akan ditentukan banyaknya 'cara menempatkan 25 orang dalam 3 Akan ditentukan banyaknya cara menempatkan 25 orang dalam 3 kamar, di sini masing-masing kamar hams berisi paling sedikit I orang. Dari pembahasan terdahulutelah dihitungbahwa fungsi pembangkiteksponensialdari problema ini adalah 226
x2
(x +
2!
x3 3!
+
...) 3
+
= (eX-I)3
Yang akan ditentukanadalah koefisien
~r!
pada (eX-I)3.
Dengan menggunakan ekspansi binomial dapat diperoleh (eX-I)3
=
e3x
= ~ r=o
- 3e2x + 3eX - 1 xr
3r
-
- 3
r!
1
r=O
-r!
+3
Xf
r=O r! ~
- 1
xr
00
L (3r - 3.2r + 3)
=
xr
2f
r=O
dengan demikian koefisien dari
-r!
-
x25
1
adalah 325
- 3.225 + 3.
25!
Contoh 10.16 Akan ditentukan banyaknya bilangan yang terdiri dari r angka, yang dipilih dari angka 0,1,2, dan 3, di sini jumlah angka ° adalah geriap, jumlah angka 1 adalah ganjil. Fungsi pembangkit eksponensial yang dieari adalah
~
1 + !:-. + + ... 2! 4! ( )
X
(
+
~3! + ~5!
+ ...
)(
1+x +
~2! + ~3!
+
...
)
dan ini dapat ditulis sebagai 1
1/2 (eX-e'X). 1/2 (eX+e'X).eX.eX
=-4
(e2x
- eO+
(e4x
- 1)
1
= -4
Untuk harga r > 0, maka koefisien dari
x' r!
eO'- e'2X).eX.eX
ada1ah
1 4
4r.
227
METODE PENJUMLAHAN Pada bagian ini akan ditunjukkan bagaimana membentuk suatu fungsi pembangkit biasa h(x) di mana koefisien r yang dieari memenuhi suatu fungsi tertentu p(r~ yang tergantung dari r. Misalnyap(r) ;", ,2. atau p(r) = (r). Bila rumusan ini telah dapat diperoleh, maka h(x) akan digunakan untuk menghitung jumlah p(Q) + p(l) + ... + p(n), untuk setiap bilangan bulat n. Sebelum hal ini dibahas, pertama-mma akan diberikan dulu 4 aturan sederhana yang sering digunakan untuk membentuk fungsi pembangkit yang baru dari suatu fungsi ~mbangkit yang diberikan. Untuk keempataturan ini dimisalkanbahwa A(x) = LanXn,B(x) = I,bnxn, C9x) = I,C/ dan D(x) = Ld~xn. 1. Bila bn
= dan, maka B(x) = d A(x). untuk tiap konstanta
2.
Bila cn
= an + bn maka
3.
Bila cn = I, a,bn_j,maka C(x)
4.
Bila bn
C(x)
d.
= A(x) + B(x).
n i=O
= B(x) A(x).
= an_k,keeuali bj=Ountuk i < k. maka B(x) = xk A(x).
Salah satu operasi pembentukan koefisien penting lainnya adalah mengalikan setiap koefisien a, dari fungsi pembangkit g(x) dengan suatu konstanta r. Fungsi pembangkit yang baru g*(x} mempunyai koefisien a*, = ra" diperoleh dengan menurunkan g(x) terhadap variabel x dan kemudian mengalikan hasilnya dengan x. d Jadi g*(x) = x (g(x». Kebenaran akan hal ini ditunjukkan dx sebagai berikut: g(x)
= ao + atx + a~
+ ... + a,r + ....
turunan dari g(x) terhadap x adalah
228
d _ -1 ,- g(X) - a) + 2ar + ... + ra~ + ..., dx dan bila hasil penurunan ini dikalikan dengan x, maka akan diper oleh g*(x)
(:
=x
g(X))
=
a)x + 2af
+
... + ra~ + ...,
Perhatikan bahwa pada persamaan yang terakhir ini koefisien ao hHang, karena
koefisien
yang barn adalah
Oao
= O.
Bila operasi ini digabungkan dengan aturan pertama dan kedua di atas, maka koefisien xr dapat dikalikan dengan r atau konstanta dan dapat dilakukan penambahan koefisien berkali-kali. Hal ini memberikan peluang untuk membentuk suatu polinomial dalam r. Yang menjadi pertanyaan adalah pada koefisien sejenis apa operasi ini patut dilakukan? Bila tidak ada informasilainnya, maka diambil s~atu fungsi pemabngkit yang paling sederhana yaitu fungsi pembangkit dengan koefisien ar = 1, dengan fungsi pembangkit
=
I + x + x2 + x3 + ... r + ...
I-x
Contoh 10.17 : Buatlah suatu fungsi pembangkit h(x) dengan ar = 2?-. 1
Proses dimulai dengan fungsi pembangkit
-I-x
Bila dilakukan operasi penurunan dan perkalian dengan x, maka akan diperoleh x
=" Ix + 2i2 + 3x3+ ... rr + ...
229
Bila proses ini diulangi sekali lagi, maka akan diperoleh
(
d
X
x --;j;"
)=
(l-x)2
x(l +x)
(l-xf
= l2x + 22x2+ 32x3+ ... r2xr + ...
Akhirnya hasil ini dikalikan dengan 2, dan diperoleh
h(x)
=
2x(1+x) (l-x)2
Contoh 10.18 : Akan dibentuk fungsi pembangkit h(x) dengan ar = (r+l)r(r-l). Untuk ar = (r+l)r(r-l) = ,J -r, dapatdilakukanprosesseperticontohyang barn dikerjakan, yaitu dengan melakukan mencari fungsi pembangkit dengan koefisien ,J dan r, lalu melakukan proses pengurangan dua fungsi pembangkit. T~pi selain itu dapat juga dilakukan sebagai berikut. Misalkan fungsi pembangkit
mempunyai koefisien ar' di sini
ar
= 3!
r+4-1 r
( )
= 3! (r+3)! = r!3!
(r+3)! = (r+3)(r+2)(r+l)! r!
Maka ekspansi deret pangkat dari 3!.(l-x)-4 adalah 3!
= 3.2.1 + 4.3.2x + 5.4.3x2 + ... + (r+3)(r+2)(r+l)r
230
+ ...
bila hal ini dibandingkan dengan fungsi pernbangkit h(x)
= 3.2;lx2 + 4.3.2i3 + 5.4.3x4 + ... + 4 (r+l)(r-l)r + ...
rnaka jelas bahwa h(x) adalah sarna dengan 3!x2(1-x)-4
Contoh yang terakhir ini dapat diperluas untuk tiap koefisien yang melibatkan hasil kali dari suku yang rnenurun, seperti (r+l)r(r-l). Dalam hal ini fungsi pernbangkit (n-l)!(1-x)-n, rnernpunyai koefisien
ar = (n-l)!
= (r+(n-l» (n-2) ... (r+l). (r+:-l)
di sini n-l adalah jurnlah suku dalam hasil kali. Sejauh ini eontoh yang diberikan rnenunjukkaneara rnernbentukh(x) dengan rnanipulasi aljabar dari fungsi .pernbangkit. TeoreJ1laberikut ini rnudah untuk dibuktikan dan berguna untuk rnenghitungjurnlah koefisien lir untuk dari suatu fungsi pernbangkit tertentu.
Teorema 10.1 Bila h(x) adalah suatu fungsi pembangkitdengankoefisienar, h(x)
rnakah*(x)=
-I-x
adalah fungsi pernbangkit dengan koefisien
jurnlah dari ar atau * h (x)=
2 <10+ (<10+ a)x
+ (<10+ a) + ~)x
r +...
+ (L
i:::O
ar)xr
+ ... 231
Contoh 10.19 Hitung jumlah 2.12 + 2.22 + ... + 202. Fuogsi pembangkit h(x) dari ar = 2r2 telah diperoleh pada cootoh terdahulu yaitu 2x(1+x). (1-x)3 Maka meourut teorema di atas, jumlah dari at + ~ + ...+ ~ adalah koefisieo
dari Xo dalam
h(x) (I-x)
= 2x
(1 + x)(1
- x)-4
= 2x (1 - x)-4 + 2x (1 - x)-4 Koefisieo dari Xodalam 2x (1 - x)-4 adalah koefisieo xo-t dalam 2(1 - xt4, demikian pula koefisieo dari Xodalam 2x2 (1 - x)-4 adalah koefisieo xO-2dalam
2(1 - x)-4. Deogan demikian jumlahan yang dicari besamya adalah
2
(0-1) + 4 - 1 0-1
(
(0-2) + 4 - 1 0-2
) ( +2
0+2 3
0+1 3
)= ( ) ( ) 2
+2
Contoh 10.20 Hituog jumlah 3.2.1 + 4.3.2 + ... + (0+1)0(0-1). Fuogsi pembangkit h(x) uotuk ar
= (r+l)r(r-l)
telah diperoleh d!Ui cootoh
terdahulu 6x2 (1 - x):4.Meourut teorema di atas, makajumlah dari koefisieo dari Xopada h*(x) = h(x) = 6 x2 (1 - xt5. I-x
232
Koefisien ini. adalah suku Xn-2pada 6 (1
- xt5,
yang besarnya adalah
PENYELESAIAN HUBUNGAN REKURSI DENGAN FUNGSI PEMBANGKIT Pada bagian ini akan dipelajari salah satu cara lain penyelesaian suatu hubungan rekursi dengan melakukan manipulasi aljabar dari fungsi pembangkit g(x) dengan koefisien an yang memenuhi hubungan rekursi yang diminta. Kebanyakan hubungan rekursi yang melibatkan an dapat diubah kedalam suatu persamaan yang melibatkan fungsi pembangkit
Dalam cara ini persamaan yang melibatkan fungsi g(x) dapat diselesaikan secara aljabar, dan ekspresi yang diperoleh untuk g(x) diekspansikan keda1am deret pangkat untuk memperoleh ~, yang merupakan koefisien dari xn. Untuk beberapa hal manipulasi aljabar yang dilakukan pada g(x) kelihatannya agak sulit, tetapi hal ini sebenarnya dapat dilihat dari sisi yang lebih mudah setelah memisalkari variabel barn y yang menggantikan g(x). Dalam hal ini g(x) akan diperlakukan sebagai suatu variabel baku yang barn, yang disebut y. dan fungsi lain yang mengandung x, diperlakukan sebagai suatu konstanta. Misalnya persamaan fungsi berikut g(x)
= x2g(x) - 2x
dapat diselesaikan dengan menuliskan g(x) seperti berikut g(x)(1
- x2) = -2x
sehingga dapat diperoleh
233
= -2x
g(x)
(I - X2)"1.
Hal yang sarna dapat juga persamaan fungsi berikut
yang dapat diselesaikan dengan rnenggunakan rurnus kuadrat a, b, c yang biasanya digunakan untuk
ay2 + by + c
=0
dalarn . hal ini . 2 . a = (l -x ) b = -4x c = 4x2
Y
= g (x).
Dan dengan rnenggunakan rurnus kuadrat a, b, c persarnaan ini diselesaikan untuk variabel y, dan diperoleh
=
g(x)
2(1
_
x2) (4x:t 4x2)
dan akan diperoleh g(x)
=
2(x + x2) atau
Pada urnumnya bila ada lebih dari 1 jawaban g(x) yang mungkin, maka hanya ada satu fungsi pernbangkit an yang rnempunyai arti, yaitu fungsi yang rnernenuhi hubungan rekursi tersebut. 234
Contoh 10.21 Diberikan suatu hubungan rekursi an = an_I + n, dengan 30 = I. Akan dieari hubungan fungsi pernbangkit g(x), keeuali 30, akan diperoleh hubungan anxn
= an_lxn+ nxn
n ;:: I
Bila suku ini dijurnlahkan untuk tiap nilai n rnaka akan diperoleh hubungan berikut co
co
g(x)
- 30
=L. anxn = L. (an-I xn + nxn) n=1 n=1
= x faxn-I n-I
+ f nxn
n=1
n=1
x
= xg (x) +
(I
_
x2)
Perhatikan disini bahwa dalarn proses ini suku an_lxntelah ditulis kernbali dalarn bentuk xan_1xn-l,supaya pangkat dari x sesuai dengan indeks dari koefisien a. Juga pada rnanipulasi di atas telah dilakukan proses penulisan indeks baru rn = n - ~ dan rnenarnbahkan suku baru Oxoyang nilainya adalah 0, dernikian pula dengan penulisan n sebagai
(~).
Di atas juga terlihat bahwa bentuk. jurnlahan yan~ pertama adalah sarna dengan fungsi pernbangkit g(x) yang dikalikan dengan x sedangkan jurnlahan yang kedua adalah fungsi pernbangkit yang telah dapat diperoleh dari earn'yang diterangkan pada bagian terdahulu. Persarnaan terakhir ini dapat ditulis dalarn bentuk berikut setelah rnengganti 30 dengan nilai awal 1
235
g(x) - 1 = xg (x) +
x
(1 - x2)
dan dari persam~ ini faktor g(x) dapat dipindahkan kebagian kiri persamaan dan akan diperoleh bentuk (x) - xg (x)
=1+
x
atau g (x)
=
+ (1 - x)
x (1
- x)3
Telah diketahui sebelumnya bahwa koefisien.xn pada (1 - xtl adalah 1 dan dalam x adalah (1
- x)3
Dan dengan demikian fungsi g(x) dapat ditulis sebagai
dan dari sini diperoleh bahwa an = 1 +
( n:l )
Contoh 10.22 Akandiearifungsipembangkitg(x)yangkoefisiennyamemenuhihubungan rekursi ~ 236
= ail_I +
an_2dan syarat awal al
= 1 serta az = 2.
Dengan menggunakan hubungan rekursi yang diberikan, maka dapat dihitung 1 dan a1 = 1. Kemudiandengan menggpnakan syarat awal barn yaitu ~ jumlahan dari deret pahgkat seperti contoh sebelum ini akan dapat diperoleh
=
00
= x n=2 L (an_1xn+
an_2xn)
=x n=1 r an-l + xn-l + x2 n=2 i a-n-2xn-2
= x(g(x) - 30>+ x2g(x) Dengan mengganti ~ dan a1 dengan nilai 1",maka diperoleh persamaan fungsi berikut ini g(x) - 1 - X = x(g(x) 1) + x2g(x).
-
dan diperoleh g(x)
=
1 1 -X
- x2
Perhatikan disini bahwa penyebut dari g(x) dapat ditulis dalam at dan cx.z yang memenuhi
1 - X- x2 = (1
-
at x) (1 - cx.zx)
di sini
237
selanjutnya g(x) dapat ditulis sebagai
g(x)
~
=
..JS(J- ~x) Sekarang tuliskan YI = alx dan Y2 = ~x, maka akan diperoleh al
~
(1
_
y,y' = u,
hal yang sama dapat dilakukan un!uk Y2dan akhimya akan diperoleh
_
=
an
..J5
-..J5
=
_ 1
a n+I _ I
n+I
..J5
(II (l + ..J5)n+I 2
-
..J5
(I/il
- ..J5)n+I
Contoh 10.23
=
Akan diselesaikan hubungan rekursi an '+ an_I -16an_2 + 20an_3 0, untuk n 3, 4, 5, ... dengan syarat awal 30 = 0, al = 1 dan ~ = -1. Misalkan g(x) adalah fungsi pembangkit dengan koefisien yang memenuhi persamaan tersebut, maka akan diperoleh persamaan berikut
=
g(x)
- 30
~
atx - ~x2
= n=3 1
anxn
dan dengan menggunakan hubungan rekursi yang diberikan akan diperoleh 00
= n=3 I. (-an_t
238
+ 16an_2- 20an_3) xn
bila digunakan syarat awal yang diberikan e10= 0; at persamaan berikut
(I + x
= -I,
maka akan diperoleh
- 16x2+ 20x3)g(x) = x
atau g(x)
=
1+ x
- 16x2 + 20x3
dan penyebut dari g(x) dapat dituliskan sebagai 1 + x - 16x2 + 20x3 = (I
- 2x)2(1
+ 5x)
dan dari persamaan terakhir ini hams ditentukan tiga buah konstanta A, B, C yang memenuhi x
=
A
B +
1 - 2x
1 + x - 16x2 + 20x3
(I
- 2x)2
C.
+
1 + 5x
dari hal ini diperoleh persamaan bam yaitu x
= A(I - 2x)(I
x
= (A + B + C) + (3A + 5B - 4C)x + (-lOA + 4C)x2
+ 5x) + B(I + 5x) + C(I - 2x)2.
atau
dan diperoleh 3 persamaan berikut untuk tiga variabel A, B, C yaitu
A+B+C=O 3A + 5B - 4C = 1 -lOA + 4C = O. Dengan menyelesaikan persamaan linier dalam 3 variabel ini akan diperoleh A
='-
2 49
,B
=
5
7 49 ,dan C
=-
49
239
Jadi 1 g(x)
= 1+ x
- 16x3 + 20x3
=
-2149 1 - 2x
7/49
5/49
+ 1 + 5x
Sedangkan telah diketahui bahwa 1 1 - 2x 1
00
- 2x)2
(1
= L
k=O (kl)
1
2kXk
00
1 + 5x
= L (_5)kxk k=O .
Dengan demikian g(x) yang dieari adalah 00
g(x)
=L [-2149 2k + 7/49 (k+l)2k k=O
5/49 (-5)k] xk
dan jawab dari hubungan rekursi yang diberikan adalah an
= -2149 2n + 7/49 (n+1)2n - 5/49 (-5)n.
Dari hasil akhir ini terlihat bahwa jawab dari hubungan rekursi ini dapat diselesaikan dengan menggunakan teknik persamaan karakteristik, seperti dijelaskan pada bab ini. Dan kalau diperhatikan hasil akhir ini, maka akar karakteristik tersebut adalah 2, 2, dan -5. Bagaimana hubungan antara akar karakteristik ini dengan fungsi g(x) yang diperoleh ini? Bila fungsi pembangkit g(x) dapat dituliskan sebagai g(x) =
p(x) q(x)
240
dalam hal ini penyebut dari fungsi pembangkit ini q(x) dapat ditulis sebagai
maka persamaan karakteristik yang akan".dipenuhi oleh hubungan rekursi ini adalah
hal ini sebaliknya juga berlaku, dan secara lengkap dinyatakan dalam teorema berikut ini :
TEOREMA 10.2 Misalkan diberikan suatu barisan bilangan 30, ai' ..., ~, ... yang memenuhi suatu hubungan rekursi
untuk n = k, k+l, ... dan syarat awal yang ditentukan 110,aI' ..., ak_I. Persamaan karakteristik dari hubungan rekursi ini adalah
Maka fungsi pembangkit untuk barisan bilangan tersebut adalah g(x) yang dapat ditulis sebagai
g(x)
=
p(x) q(x)
tingkat dari q(x) adalah k dan tingkat dari p(x) kurang dari k, serta q(x) dapat ditulis sebagai 241
dan p(x) adalah p(x)
=ao + (al + clao)x + (az + clal
+ c2ao)x2+ ... + (ak+, +
clak_2+ ... + ck_lao)xk-I Hal ini mudah ditunjukkan karena antara penyebut dari fungsi pembangkit g(x) yaitu q(x) dan persamaan karakteristik r(x) = 0 terdapat suatu hubungan q(x)
= xkr(lIx)
dan jika akar karakteristikdari r(x) adalah a, ... ~, maka r(x)
= (x - al) ... (x - ~)
dan q(x) dapat ditulis sebagai
Demikian pula sebaliknya. Pada contoh terakhir dibicarakan, penyebut dari fungsi. pembangkit yang diperoleh adalah q(x)
= 1 + x - 16x2 + 20x3.
Kalau diperhatikan lebih teliti, koefisien dari x pada penyebut ini erat hubungannya dengan koefisien dari relasi rekursi yang diberikan yaitu
yang berlaku untukn = 3,4,5, ... Sedangkan fungsi karakteristik yang berhubungan dengan relasi rekursi ini adalah
242
r(x)
= X3 +
X2
- 16x + 20
dan dengan membandingkan r(x) dengan q(x) jelas terlihat bahwa q(x) dapat diperoleh dari r(x) dengan melakukan manipulasi aljabar berikut
q(x)
= 1 + x - 16x' + 20.' = x'r (~ )
Berikut ini akan diberikancara penyelesaiansuatu hubunganrekursi yang simultan. Dalam hal ini akan diberikan beberapa hubunganrekursi sekaligus yang hams diselesaikan.
Contoh 10.24 Dunakan pendekatan dengan fungsi pembangkit untuk menyelesaikan himpunan dari hubungan rekursi yang simultan sepertiberikut an
=
an_I + bn_1+ cn_1
bn
=
3n-1-
cn
=
3n-1 - bn-I
C
n-I
dengan syarat batas berikut ini
Perhatikan bahwa pada contoh ini diketahui ada 3 hubungan rekursi dan tiga syarat awal yang diberikan, dan hams dieari 3 buah jawaban yang berhubungan dengan an' bn dan cn. Misalkan bahwa A(x), B(x) dan C(x) adaIah fungsi pembangkit yang berhubungan dengan an' bn dan cn. Dengan menggunakan metoda penjumlahan polinomial maka dari ketiga relasi rekursi tersebut diperoleh
243
00
;::
00
L
A (x) - a_;:: \J
n=1
a xn;:: 11
-
-
L
n=1
x (1
I.
C (x) - COn. ;::
;::
n=1
an-I xn +
00
L
n=1
b n-I xn +
L
n=1
Cn-I "(n
xA (x) + xB (x) + xC (x)
B (x) - bo ;::
;::
00
L
n=1
bnxn;::
-
L
n=1
3n-lxn-
L
Cn-I xn
n=1
- 3x)"1- xC (x)
C xn;::
I 3n-lxn-
n=1
'i
n=1
b n-Ixn
x (1 -3x)" I - x B (x).
Karena diketahui syarat awal al
;::
bl
;:: Cn ;::
1, maka dengan menggunakan
hubungan rekursi yang diberikan dapat diperoleh
dan ini akan memberikan Co;:: O.Dan dengan cara yang sama dapat ditunjukkan bahwa bo ;:: 0 dan 30 ;:: 1. Dan dengan demikian akan dapat diperoleh persamaan simultan yang mengandung tiga buah fungsi yang akan dicari, A(x), B(x) dan C(x). Persamaan simultan tersebut adalah
A (x)
-1
;::
xA (x) + xB (x) + xC (x) atau
x
244
A (x)
;::
B (x)
;::
x(1 - 3x)"1- x C (x)
C (x)
;::
x(1 - 3x)"1- x B (x)
I-x
(B (x) + C (x) +
I-x
Untuk menyelesaikan persamaan di atas maka persamaan terakhir dilralilran dengan x sehingga dapat diperoleh suku xC (x) yang 'kemudian disubsimsi1can pada persamaan sebelumnya. I;)an persamaan yang dihasilkan akan hanya mengandung fungsi B(x) saja, dengan demikian diperoleh
= x (1 - 3x)-1- xC (x) =x (1 - 3xt1 - X (x(1 - 3xt1 - x B (x»
B (x)
dan ini akan menghasilkan
atau B(x)
-
(1
=
x(1
- x)
- xi)
(1
- 3x)
Ix (1 + x) (1
= - 3x)
1/4
1/4
1 - 3x
1+ X
Pada langkah terakhir ini dilakukan suatu dekomposisi pecahan yang sering dilakukan pada mata kuliah kalkulus.Dati hasil terakhir ini terlihat bahwa koefisien dari XOdalam 1~
1~ adalah 1/4 (_1)0 dan dalam
1+ x
1 - 3x
adalah 1/4 3D
Hal ini mudah ditunjukkan dengan menggunakan deret berikut
dan mengganti nilai y dengan -x dan 3x.
245
....
_ h_..
._......_..
Sarnpai disini telah diperoleh nilai bo yang merupakan koefisien dari XOpada B(x) yaitu bo
= 1/4
- (-1)0
(3°
Karena dua persarnaan yang mengandung B(x) dan C(x) adalah simetris terhadap B(x) dan C(x), maka penulisan B(x) dan C(x) pada kedua persamaan tersebut dapat saling dipertukarkan, sehingga jawaban yang diperoleh untuk C(x) adalah
sarna dengan yang diperoleh untuk B(x) yaitu
.0 =b° = 1/4
c
(3°
:
(-1)0)
-
Terakhir masih harns diselesaikan A(x) dengan menggunakan A(x) =
x
x
1- x
(B(x) + C(x) +
1- x
2x
=
I- x
1-3x-
II 2x
= (1
I
1/4 1- x
- x2
+
- 1/2x
)
x x
IIx 2
-
- x)(1 - 3x)
+
1/4)
(1/4
1 - x2
I
-x +-
x
1- x
Karena nilai (_1)0adalah 1 untuk n genap dan -I untuk n ganjil maka dari hal yang terakhir ini koefisien a.. dari faktor xr pada A(x) adalah ao = 1/4 (3° + 3)
n genap
= 1/4 (3° +
n ganjil
dan
~
246
1)
Sebagai contoh yang terakhir pada bagian ini akan dibicarakan cara penyelesaian suatu hubungan rekursi yang tidak liniet yang dapat diselesaikan dengan menggunakanfungsi pem~angkit.Contoh berikut ini adalah membicarakan suatu hubungan rekursi yang tidak linier yang menunjukkan banyaknya cara mengalikan n buah bilangan, dengan catatan urutan tidak diperhatikan. Contoh ini pemah dibicarakan pada bagian hubungan rekursi sebelum ini. Misalnya dua bilangan a dan b dapat dikalikan dalam satu cara yaitu a x. b (b x a dianggap sarna karena hanya berbeda urutan saja), sedangkan 3 bilangan a, b, c dua yaitu (a x b) xc atau a x (\:)x c), cara yang lain hanya merupakan permutasi dari kedua hasil ini. Jadi telah diperoleh bahwa ~ = 1 dan 8:3= 2, danjelasbahwaa. = 2, serta 80 = o.
Contoh 10.25 Apabila diberikan n buah bilangan dan ~ merupakan banyaknya cara mengalikan bilanr:.tll tersebut, maka akan diperoleh hubungan reku~i berikut
RuolUs hubungan rekursi ini diperoleh karena untuk mengalikan n buah bilangan dapat dikalikan dahulu i bUah bilangan disatu pihak dan n-l bilangan dilain pihak, kemudian kedua hasil perkalian ini dikalikan:Dan ini dapat dilakukan untuk nilai i = 1,2, ... n-1. Dan dengan demikian diperoleh rumus rekUsidi atas. Bila g(x) adalah fungsi pembangkit dari an maka bagian kanan dari hubungan rekursi tersebut menyatakan koefisien xn dari g (x)g(x)
= (0 + a.x
+ ~x2 +
...+ ~xn
+ ...)2
Dengan menggunakan metoda penjumlahan polinomial maka akan diperoleh persamaan fungsi pembangkit berikut ini 00
g (x) -x = L
n=2
00
anxn:-: n=2 L (a.~_. + ~~-2 + ... + an_.a.)xn= (g(x»2
247
Deogan meoyelesaikan persamaan kuadrat dari g(x) ioi diperoleh jawaban
dan kareoa syarat awal 80 = 0, maka fuogsi yang memeouhi syarat ioi adalah
Dan deogan meogguoakan rumus ekspansi binomial yang umum yaitu
ekspansi. dari ( I + y. )112
y =-4x, maka diperoleh ben~k umum koefisien binomial uotuk pangkat pecahan 112sebagai berikut
Dan dengan demikian diperoleh koefisieo dari x8 dari vi - 4x adalah
=
1/2 (-1/2) (-3/2) ... {-1/2(20-3»
(-4)8
n!
(2n - 3) o!
=
-2/0
20
(
- 2 0-1
) 20 - 2
Jadi, koefisieo dari x8 uotuk g(x) ada1ah 1/n
(
248
n-I )
