FUNGSI PEMBANGKIT UNTUK KOMBINASI

OLEH :DWI OKTAVIANA, M.Pd

Fungsi Pembangkit untuk Kombinasi

Misalkan terdapat 3 macam obyek : a, b, dan c. Kita diperkenankan memilih : 0, 1, atau 2 obyek a, 0 atau 1 obyek b, dan 0 atau 1 obyek c. Pertanyaan yang muncul ialah : ada berapa cara memilih k obyek ?

Untuk menjawab pertanyaan ini, akan diterapkan fungsi pembangkit. Misalkan menyatakan banyaknya cara memilih k obyek. Kita coba menghitung fungsi pembangkit biasa . Karena obyek a dapat dipilih 0, 1, atau 2 kali, obyek b dapat dipilih 0 atau 1 kali

t k

0

)(n

k

k xtxP

Dan obyek c dapat dipilih 0 atau 1 kali, maka ekspresi yang dipakai adalah :

Perhatikan bahwa, mengindikasikan bahwa obyek a terpilih satu kali, mengindikasikan bahwa obyek a terpilih dua kali, demikian pula

cxcxbxbxaxaxax

1010210

ax 1

ax 2

bx 0

mengindikasikan kemungkinan obyek b tidak terpilih, dsb. Selanjutnya dapat disederhanakan menjadi :

yang sama dengan

xaxaaxa bccbabcacbcabxcba4232222

1

cxbxax xa 11122

Perhatikanlah koefisien memberikan semua kemungkinan memilih 3 obyek yaitu a, b, dan c atau a, a, dan b, atau a, a, dan c. Demikian pula koefisien dari memberikan semua kemungkinan memilih 4 obyek yaitu a dan b, atau b dan c, atau a dan c, atau a dan a.

x3

x2

Hal yang sama berlaku untuk koefisien-koefisien yang lain. Jadi, jika a, b, dan c masing-masing disubstitusi dengan 1, maka diperoleh , maka jelas koefisien menyatakan banyaknya cara memilih k obyek ( ) dengan syarat yang diperkenankan.

xxxx432

3431

xk

t k

Misalnya terdapat 4 cara memilih 2 obyek, terdapat 3 cara memilih 1 obyek, dan hanya satu cara memilih 4 obyek. Perhatikan bahwa = 0 untuk k>4, maka :

t k

xxxxxP432

3431)(

xxx x 1112

disebut fungsi pembangkit dari permasalahan menentukan banyaknya cara memilih k obyek dari 3 macam obyek, dimana obyek pertama (obyek a) bisa dipilih sebanyak-banyaknya 2, obyek kedua (obyek b) bisa dipilih sebanyak-banyaknya 1, dan obyek ketiga (obyek c) bisa dipilih tidak lebih dari 1.

Secara Umum Diperoleh :Misalkan terdapat p tipe obyek dan terdapat obyek tipe 1, obyek tipe 2 . . . . . obyek tipe p. Misal menyatakan banyaknya cara mengambil k obyek dimana dibolehkan mengambil sembarang banyak obyek tiap tipe.

n1 n2np t k

Fungsi pembangkit untuk adalah , dimana :

Bilangan diberikan oleh koefisien dalam P(x).

t k

xxxxxx nxnxnxxP p ...1......1...1)(222

21

t k xk

xtk

kxP )(

Contoh :Tentukan fungsi pembangkit untuk banyaknya cara memilih r obyek dari n obyek dimana pengulangan tidak diperkenankan ?Penyelesaian :Terdapat n obyek.

Karena pengulangan tidak diperkenankan, maka tiap obyek dapat dipilih 0 atau 1 kali saja sehingga fungsi pembangkit yang dimaksud adalah :

n faktor (teorema binomial)

xxxxxP 1...111)(

xx rn

r

n

r

n

01

Contoh 2 :Tentukan banyaknya cara memilih r obyek dari n macam obyek dimana pengulangan diperkenankan ?Penyelesaian :Misal menyatakan banyak cara memilih r obyek.

t r

Karena ada n macam obyek dan tiap obyek dapat dipilih berulang (tanpa batas), maka fungsi pembangkit untuk t, ialah :

n faktor

xxxxxx nxnxnxxP p ...1......1...1)(222

21

...1 2 xxn

Karena, untuk |x| < 1, maka :

(teorema binomial)

...11

1 2 xxx

x

n

xP11

)(

x n 1

n

r

rr

xr

n

01

Untuk r > 0 koefisien dalam P(x) adalah :

xr

11!

1...1

rr

r

rnnn

r

n

!

1...1

r

rnnn

!

1...21

r

nnrnrn

r

rn

nr

rn 1

!1!

!1

Untuk r=0 koefisien dari dalam P(x) ialahSehingga untuk r ≥ 0

Dengan demikian :

xr

0

10

01

0 nn

r

rn

r

n r 11

n

r

r

xr

rnxP

0

1)(

Jadi, banyaknya cara memilih r obyek dari n macam obyek dimana pengulangan diperkenankan sama dengan koefisien dalam P(x) yaitu

xr

r

rnt r

1

Perlu diingat bahwa untuk x ≠ 1 dan n bilangan cacah berlaku identitas berikut:1. 2. 3.

xxxx nn

xx

...11

1 321

xxxx nrn

n

n

r

nnx

n

......

211

21

xxxxxnmnrmrmmn

n

n

r

nnnm

111 ......

211

2

Contoh Soal :1.Tentukan koefisien pada2. Berapa banyaknya cara untuk

memilih 25 mainan dari 7 tipe mainan dimana tiap tipe antara 2 dan 6 !

3.Berapa banyak cara untuk mendapatkan jumlah 15 dari 7 dadu berbeda yang ditos!

x16 ...432 5

xxx

Penyelesaian :1.Ubah bentuk

menjadi ...432 5

xxx

...1 22 5

xxx

...1 2 510 xxx

xxx

x

111

5

10

5

10 1

Karena berarti mencari koefisien pada sama dengan mencari koefisien pada yaitu Jadi, koefisien pada adalah 210.

xxx61016

.

x16 ...1 2 5

xx

x1 5

1

2106

10

6

165

x16 ...1 2 5

xx

2.Fungsi pembangkit yang dapat dibentuk Ditanya : mencari koefisien pada

Ubah bentuk menjadi

xxxxx 65432 7

x25

xxxxx 65432 7

xxxxx 65432 7

xxxxxxxxxx 432265432 177

Berarti tinggal mencari koefisien pada dengan menggunakan identitas diperoleh

Misalkan dan maka diperoleh :

xxxxx 4321714

x11 xxxx 4321

7

xxxx

xxxx 5.5

432 1111

177

7

7

xxf 1

7)( xxg 5)( 1

7

Untuk mencari koefisien pada kita

hanya membutuhkan bentuk sbb :

...17

...2

172

1

1711)(

27

1

xxx r

r

rxxf

xxxxxrr

rxg

3551057

7

7...

7...

2

7

1

715)( 11

x11

)().()( xgxfxh

2

7.

1

171

1

7.

6

1761.

11

171110156011 bababa

Hasil terakhir ini merupakan koefisien dari .

2

7

1

7

1

7

6

12

11

17

x11

TERIMA KASIH