Download - Fungsi Pembangkit
FUNGSI PEMBANGKIT(Generating Function) MASYTA AFNI MILDA ST MUTMAINNA
Ihr Logo
PENDAHULUAN
Deret Kuasa Persamaan Bilangan Bulat
Your Logo
Deret KuasaDeret takhingga yang berbentuk disebut deret kuasa. = a0x0 + a1x1 + a2x2 + . . .
Pembahasan selanjutnya, hanya terkait dengan koefisienkoefisien dari xn ; dengan kata lain sebuah ekspresi formal saja.
Deret kuasa demikian disebut deret kuasa formal (formal power series).
Here comes your footer
Page 3
Your Logo
Persamaan bilangan bulat Secara umum, masalah persamaan bilangan bulat membutuhkan solusi bulat untuk X1 + X2 + . . . + Xn = r dengan batasan pada Xi.
Here comes your footer
Page 4
Your Logo
Contoh 1Masalah. Tentukan banyaknya solusi bilangan bulat untuk X1 + X2 = r, dengan 0 X1 1 dan 1 X2 2. Solusi : (dengan perhitungan satu-satu) X1 X2 Jumlah (r) 0 0 1 1 1 2 1 2 1 2 2 3Your Logo
Contoh 2Masalah. Perkalian polinomial (x0 + x1) dengan (x1 + x2) Solusi. (x0 + x1) (x1 + x2) = x0 (x1 + x2) + x1 (x1 + x2) = x0 x1 + x0 x2 + x1 x1 + x1x2 = x1 + x2 + x2 + x3 = x1 + (1 + 1) x2 + x3 = x1 + 2x2 + x3. Koefisien xr merupakan banyaknya cara agar eksponen menghasilkan jumlah r.Your Logo
Definisi Fungsi Pembangkit Misalkan ar (r = 0, 1, 2, . . .) adalah solusi untuk beberapa masalah kombinatorik. Maka fungsi pembangkit biasa untuk masalah ini adalah g(x) = a0 + a1x + a2x2 + . . . Juga dikatakan bahwa g(x) merupakan fungsi pembangkit untuk barisan a0, a1, a2 . . .
Your Logo
Contoh 3Masalah penentuan banyaknya solusi bilangan bulat untuk X1 + X2 = r, dengan 0 X1 1 dan 1 X2 2. (contoh 1) Jika ar adalah banyaknya solusi bilangan bulat, maka a0 = 0, a1 = 1, a2 = 2, a3 = 1, dan untuk r > 3, ar = 0. Oleh karena itu, fungsi pembangkit biasa untuk masalah ini adalah g(x) = 0x0 + 1x1 + 2x2 +1x3 + . . . + 0xr + . . . g(x) = x + 2x2 + x3 (polinomial yang diperoleh pada contoh 2)
Here comes your footer
Page 8
Your Logo
Pemodelan Masalah dengan Fungsi Pembangkit
Contoh 4 Masalah. Tentukan fungsi pembangkit untuk banyaknya solusi bilangan bulat dari persamaan X1 + X2 + X3 + X4 + X5 = 100, dengan Xi 0; i = 1, 2, 3, 4, 5
Your Logo
Solusi. Karena setiap variabel Xi 0, maka setiap faktor dalam fungsi pembangkit yaitu (x0 + x1 + x2 + x3 . . . ) Sehingga fungsi pembangkit dari persamaan di atas adalah g(x) = (1 + x + x2 + x3 . . .)(1 + x + x2 + x3 . . . ) (1 + x + x2 + x3 . . . )(1 + x + x2 + x3 . . .) (1 + x + x2 + x3 . . .) g(x) = (1 + x + x2 + x3 . . . )5
Here comes your footer
Page 10
Your Logo
Contoh 5Masalah. Tentukan fungsi pembangkit untuk masalah banyaknya cara menempatkan sepuluh bola yang sama ke tiga sel (kotak) yang berbeda dengan jumlah bola genap pada tiap sel.
Your Logo
Solusi. Persamaan bilangan bulat dari masalah di atas yaitu: X1 + X2 + X3 = 10, dengan Xi = 0, 2, 4, . . . Fungsi pembangkitnya adalah g(x) = (x0 + x2 + x4 + . . .)(x0 + x2 + x4 + . . .)(x0 + x2 + x4 + . . )
g(x) = (1 + x2 + x4 + . . .)3Banyak cara menempatkan sepuluh bola yang sama ke tiga kotak yang berbeda dengan jumlah bola genap pada tiap sel adalah koefisien dari x10.
Your Logo
Contoh 6Masalah. Tentukan fungsi pembangkit untuk mendapatkan banyak cara mengambil k huruf dari huruf-huruf pembentuk kata SURABAYA sedemikian hingga setiap konsonan terpilih paling sedikit satu dan setiap vokal terpilih paling banyak 10?
Your Logo
Solusi:S, R, B, Y SURABAYA U, A (x0 + x1 + x2 + . . . + x10). (x1 + x2 + x3 + x4 + x5 + . . .) .
Jadi, fungsi pembangkit untuk permasalahan di atas adalah:g(x) = (x1 + x2 + x3 + x4 + x5 + . . .)4 (x0 + x1 + x2 + . . . + x10)2 g(x) = (x + x2 + x3 + x4 + x5 + . . .)4 (1 + x + x2 + . . . + x10 ) 2Your Logo
TERIMA KASIH
Your Logo