Matdis_fungsi_pembangkit_ea.docx

Kelompok 3: Ismail marzuki (5113001) Siti nurrosyidah (5113003) Adhellia rizqi damayanti (5113007) Generating Function [Fungsi Pembangkit] (lanjutan...) Definisi 9.1 Pandang 𝑎0 , 𝑎1 , … , 𝑎𝑛 , … adalah barisan bilangan dengan indek n. Fungsi pembangkit atau generating function dari barisan tersebut didefinisikan sebagai deret pangkat 𝑓(𝑥) = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ Untuk memudahkan perhitungan Koefisien Fungsi Pembangkit, berikut ini diberikan beberapa persamaan yang berhubungan dengan ekspansi suatu polinomial 1.

2.

3. 4.

5.

1−𝑥 𝑛+1

= 1 + 𝑥 + 𝑥2 + 𝑥3 + ⋯ + 𝑥𝑛 Hal ini ditunjukkan dengan mengalikan kedua sisi dari persamaan dengan faktor (1-x). Sisi kiri akan menghasilkan 1-xn+1, sedangkan sisi kanan merupakan penjumlahan dari 1 + 𝑥 + 𝑥 2 + 𝑥 3 + ⋯ + 𝑥 𝑛 dan -𝑥 − 𝑥 2 − ⋯ − 𝑥 𝑛 − 𝑥 𝑛+1. Jumlah dari kedua polinomial ini adalah 1-xn+1 1 = 1 + 𝑥 + 𝑥2 + 𝑥3 + ⋯ + 𝑥𝑛 + ⋯ 1−𝑥 Hal ini dapat ditunjukkan dengan cara yang hampir sama dengan cara sebelumnya. Hanya saja dalamhal ini harga n dibuat menuju tak berhingga. Dengan demikian setiap koefisien xk dimana k>0 akan bernilai 0. Jadi dapat disimpulkan bahwa (1 + 𝑥)(1 + 𝑥 + 𝑥2 + 𝑥3 + ⋯ (1 + 𝑥)𝑛 = 1 + (𝑛1)𝑥 + (𝑛2)𝑥 2 + ⋯ (𝑛𝑟)𝑥 𝑟 + ⋯ + (𝑛𝑛)𝑥 𝑛 (teorema binomial) (1 + 𝑥 𝑚 )𝑛 = 1 − (𝑛1)𝑥 𝑚 + (𝑛2)𝑥 2𝑚 + ⋯ + (−1)(𝑛𝑟)𝑥 𝑟𝑚 + ⋯ + (−1)𝑛 (𝑛𝑛)𝑥 𝑛𝑚 Hal ini merupakan perluasan dari bentuk binomial sebelumnya dimana harga x diganti dengan bentuk (-xm), dan dengan menggunakan rumus expansi binomial diperoleh 𝑛 𝑛 𝑛 (1 + (𝑥 𝑚 ))𝑛 = 1 + ( ) (−𝑥 𝑚 ) + ( ) (−𝑥)𝑚 )2 + ⋯ + ( ) ((−𝑥 𝑚 ))𝑟 + ⋯ 1 2 𝑟 𝑛 𝑚 𝑛 + ( ) ((−𝑥 )) 𝑛 1 1+𝑛−1 = 1 + ( 1 )𝑥 + (2+𝑛−1 )𝑥 2 + ⋯ + (𝑟+𝑛−1 )𝑥 𝑟 + ⋯ 2 𝑟 (1−𝑥)𝑛 1−𝑥

6. 𝑏𝑖𝑙𝑎 ℎ(𝑥) = 𝑓(𝑥). 𝑔(𝑥), 𝑑𝑖𝑠𝑖𝑛𝑖 𝑓(𝑥) = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ 𝑑𝑎𝑛 𝑔(𝑥) = 𝑏0 + 𝑏1 𝑥 + 𝑏2 𝑥 2 + ⋯ 𝑚𝑎𝑘𝑎 𝑓𝑢𝑛𝑔𝑠𝑖 𝑝𝑒𝑚𝑏𝑎𝑛𝑔𝑘𝑖𝑡 𝑢𝑛𝑡𝑢𝑘 ℎ(𝑥) 𝑎𝑑𝑎𝑙𝑎ℎ ℎ(𝑥) = 𝑎0 𝑏0 + (𝑎1 𝑏0 + 𝑎0 𝑏1 )𝑥 + (𝑎2 𝑏0 + 𝑎1 𝑏1 + 𝑎0 𝑏2 )𝑥 2 + ⋯ + (𝑎𝑟 𝑏0 + ⋯ + 𝑎0 𝑏𝑟 )𝑥 𝑟 + ⋯  Contoh 1 Misalkan m adalah bilangan bulat positif, maka fungsi pembangkit fm(x) untuk barisan koefisien binomial (𝑚 ), (𝑚 ), … (𝑚 )adalah .. 0 1 𝑚 𝑓𝑚 (𝑥) = (𝑚 ) + (𝑚 )𝑥 + (𝑚 )𝑥 2 + ⋯ (𝑚 )𝑥 𝑚 , dan berdasarkan teorema binomial dapat ditulis 0 1 2 𝑚 sebagai 𝑓𝑚 (𝑥) = (1 + 𝑥)𝑚 

Contoh 2

Pandang 4 buah kotak, masing-masing berisi 3 buah bola hijau, 3 bola putih, 3 bola biru, dan 3 bole merah. Akan ditentukan fungsi pembangkir dari ar yang menyatkan banyaknya cara untuk memilih r buah bola dari kotak tersebut, Kita modelkan soal diatas dengan model sebagai berikut : 𝑒1 + 𝑒2 + 𝑒3 + 𝑒4 = 𝑟, 𝑑𝑖𝑠𝑖𝑛𝑖 0 ≤ 𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 ≥ 3 fungsi pembangkit dapat dibentuk dengan memperhatikan 4 buah faktor polinomial yang masing-masing mempunyai tingkat antara 0 sampai dengan 3. Suku-sukudari faktor polinomial yang akan membentuk fungsi pembangkit adalah

Kelompok 3: Ismail marzuki (5113001) Siti nurrosyidah (5113003) Adhellia rizqi damayanti (5113007) [𝑥 0 ] [𝑥 0 ] [𝑥 0 ] [𝑥 0 ] [𝑥1 ] [𝑥1 ] [𝑥1 ] [𝑥1 ] [𝑥 2 ] [𝑥 2 ] [𝑥 2 ] [𝑥 2 ] [𝑥 3 ] [𝑥 3 ] [𝑥 3 ] [𝑥 3 ] Dengan demikian jumlah perkalian keepat pangkat yang jumlahnya r merupakan jawaban dari problema tsb. Jadi fungsi pembangkit yang dicari adalah (𝑥 0 + 𝑥1 + 𝑥 2 + 𝑥 3 )4 = (1 + 𝑥1 + 𝑥 2 + 𝑥 3 )4 

Contoh 3

Tentukan fungsi pembangkit dari ar yang menyatakan jumlah cara untuk mendistribusikan r buah bola yang sama ke dalam 5 buah kotak yang diberikan dengan kedala 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 masingmasing hanya dapat diisi leh paling sedikit 3 bola dan paling banyak 5 bola saja. Dengan menggunakan persamaan dengan jawab bilangan bulat, maka dapat ditulis sebagai berikut : cara jawab problema berikut dengan 𝑒1 + 𝑒2 + 𝑒3 + 𝑒4 + 𝑒5 = 𝑟, 𝑑𝑖𝑠𝑖𝑛𝑖 𝑒1 𝑑𝑎𝑛 𝑒2 𝑎𝑑𝑎𝑙𝑎ℎ 𝑏𝑖𝑙. 𝑔𝑒𝑛𝑎𝑝 𝑑𝑎𝑛 0 ≤ 𝑒1 , 𝑒2 ≤ 10 𝑠𝑒𝑟𝑡𝑎 3 ≤ 𝑒3 , 𝑒4 , 𝑒5 ≤ 5 Maka jelas bahwa fungsi pembangkit yang dicari akan berbentuk 𝑔(𝑥) = (1 + 𝑥 2 + 𝑥 4 + 𝑥 6 + 𝑥 8 +𝑥10 )2 × (𝑥 3 + 𝑥 4 + 𝑥 5 )4 

Contoh 4

Cari koefisien dari x16 pada ekspansi (𝑥 2 + 𝑥 3 + ⋯ )5 Secara umum tentukan koefien dari xx. Untuk menyelesaikan problema ini, keluarkan dulu suku x2 dari faktor polinomial. Kemudia gunakan rumus kedia diatas (𝑥 2 + 𝑥 3 + ⋯ )5 = [𝑥 2 (1 + 𝑥 + 𝑥 2 + ⋯ )]5 (𝑥 2 ) 1 . 5 = 𝑥10 (1 − 𝑥) (1 − 𝑥)5 Dengan demikian koefisien dari x16 pada fungsi pembangkit akan sama degnan koefisien dari x16 pada fungsi yang terakhir diperoleh ini maka koefisien dari x16 sama dengan koefisien x6 dari bentuk (1 − 𝑥)5 . Dan dari rumus kelima diatas diperoleh bahwa besarnya koefisien x6 ini adalah (6+5−1 ). 6 Secara umum besarnya koefisien xx pada fungsi pembangkit yang diberikan adalah sama dengan koefisien xx-10 dari fungsi x6 dari bentuk (1 − 𝑥)5 yang hasilnya adalah ((𝑝−10)+5−1 ). (𝑟−10)