Presentasi 3.2

3.2. MEMODELKAN MASALAH DENGAN MENGGUNAKAN

FUNGSI PEMBANGKIT

Oleh: Kelompok 2

Any Herawati

Syaiful Hamzah N

Nurul Arfinanti

Akhmad Riyadi

Matematika Diskrit

Pada bahasan sebelumnya kita melihat bahwa beberapa permasalahan dapat ditulis dalam bentuk persamaan bilangan bulat, dan mudah ditentukan dengan menggunakan fungsi pembangkit.

xr

Contoh 3.2.1.

Carilah fungsi pembangkit dari banyaknya selesaian bulat

X1 + 2X2 + 3X3 + 4X4 = r, dengan Xi ≥ 0.

Penyelesaian:Misalkan X1 = Z1

2X2 = Z2

3X3 = Z3

4X4 = Z4,

Maka persamaan diatas dapat ditulis: Z1 + Z2 + Z3 + Z4 = r,

dengan Z1 = 0, 1, 2, 3, …

Z2 = 0, 2, 4, 6, …

Z3 = 0, 3, 6, 9, …

Z4 = 0, 4, 8, 12, …

Fungsi pembangkitnya adalah:

(1 + x + x2 + …)(1 + x2 + x4 + …) (1 + x3 + x6 + …)(1 + x4 + x8 + …)

Contoh 3.2.2.

Carilah fungsi pembangkit untuk masalah menentukan banyaknya cara mendistribusikan 10 bola identik ke dalam 3 lubang yang berbeda dengan masing-masing lubang banyak bola yang terisi adalah genap.

PENYELESAIAN

Masalah diatas sama dengan mencari banyaknya selesaian bulat dari

X1 + X2 + X3 = 10 dengan Xi = 0, 2, 4, …

Fungsi pembangkitnya adalah (1 + x2 + x4 + …)3

Banyak selesaian dari persamaan:

X1 + X2 + X3 = 10 dengan Xi = 0, 2, 4, … adalah koefisien x10 pada fungsi pembangkit.

Contoh lain (2.5.5) Masalah Galileo’s diceBerapa banyak cara melempar tiga buah dadu yang berbeda

menghasilkan jumlah mata dadu 10 ?

PENYELESAIAN

Sama dengan menyelesaikan banyaknya selesaian bulat dari

X1 + X2 + X3 = 10, dengan 1 ≤ Xi ≤ 6

Fungsi pembangkitnya adalah (x + x2 + x3 + x4 + x5 + x6)3

Banyak selesaian dari persamaan:

X1 + X2 + X3 = 10, dengan 1 ≤ Xi ≤ 6 adalah koefisien x10 pada fungsi pembangkit

Contoh 3.2.3

Carilah fungsi pembangkit dari banyaknya selesaian bulat

X1 + X2 + …+ Xn ≤ r, dengan 1 ≤ Xk ≤ 3

PENYELESAIANMasalah selesaian bulat diatas ekuivalen dengan banyaknya

selesaian bulat pada X1 + X2 + …+ Xn + Xn+1 = r, dengan 1 ≤ Xk ≤ 3

untuk 1 ≤ k ≤ n, dan Xn+1 ≥ 0

Fungsi pembangkitnya adalah (x + x2 + x3)n (1 + x + x2 + …)

= xn(1 + x + x2)n (1 + x + x2 + …)

Contoh 3.2.4

Carilah fungsi pembangkit untuk banyaknya cara memilih 5 bilangan yang berbeda dari 1, 2, …, n, dengan tidak ada dua bilangan yang berurutan.

PENYELESAIAN

Misalkan bilangan-bilangan yang dipilih adalah 1 ≤ n1 < n2 < n3 < n4 < n5 ≤ n,

dan diberikan X1 = n1, X2 = n2 – n1, X3 = n3 – n2, X4 = n4 – n3 , X5 = n5 – n4, dan X6 = n – n5 .

Tidak berurutan ekuivalent dengan Xi ≥ 2 untuk 2 ≤ i ≤ 5.

Persamaan bil. bulat yang sesuai adalah: X1 + X2 + X3 + X4 + X5 + X6 = n, dengan X1 ≥ 1, Xi ≥ 2 untuk 2 ≤ i ≤ 5, dan X6 ≥ 0

Fungsi pembangkitnya adalah:

(x + x2 + …)(x2 + x3 + …)4(1 + x + x2 + …)

Contoh 3.2.5.

Carilah fungsi pembangkit dari dua variabel x dan y sedemikian sehingga koefisien dari xrys adalah banyaknya cara mendistribusikan r bola merah yang identik dan s bola biru yang identik dengan paling banyak 3 bola biru pada masing-masing lubang. Dengan n lubang yang berbeda

PENYELESAIAN CARA I

Selama penempatan bola merah tidak mempengaruhi penempatan bola biru, kita dapat menentukan fungsi pembangkit untuk bola merah dan bola biru sendiri-sendiri, kemudian mengalikan hasilnya.

Persamaan bilangan bulat untuk bola merah

X1 + X2 + …+ Xn = r, Xi ≥ 0 → Fungsi pembangkitnya

(1 + x + x2 + …)n

Persamaan bilangan bulat untuk bola biru adalah:

Y1 + Y2 + …+ Yn = s, 0 ≤ Yi ≤ 3 → Fungsi pembangkitnya adalah

(1 + y + y2 + y3)n

Jadi Fungsi pembangkit untuk masalah diatas adalah:

(1 + x + x2 + …)n (1 + y + y2 + y3)n

CARA II

Dalam fungsi pembangkit, penjumlahan berkorespondensi dengan aturan penjumlahan, dan perkalian berkorespondensi dengan aturan perkalian.

Tiap-tiap lubang mempunyai beberapa bola merah dan paling banyak tiga bola biru yaitu (1 + x + x2 + …) (1 + y + y2 + y3).

pangkat pada x menunjukkan banyaknya bola merah, pangkat pada y menunjukkan banyaknya bola biru dan perkaliannya menunjukkan semua kemungkinan pilihan dari bola merah dan bola biru untuk sebuah lubang. Karena lubang yang tersedia sebanyak n lubang, maka fungsi pembangkitnya adalah:

[(1 + x + x2 + …) (1 + y + y2 + y3)]n = (1 + x + x2 + …)n (1 + y + y2 + y3)n

Presentasi 3.2

Documents

Transcript of Presentasi 3.2