Fungsi Pembangkit

download Fungsi Pembangkit

of 15

  • date post

    07-Jul-2015
  • Category

    Documents

  • view

    1.474
  • download

    0

Embed Size (px)

Transcript of 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