kombinatorika

(Moch. Lutfianto)

Bahasan kombinatorik menitik beratkan tentang: pengaturan, pola, disain, penandaan, penjadualan, koneksi dan konfigurasi. Analisis masalah kombinatorik berdasarkan atas pemahaman tentang: prinsip dasar penghitungan, permutasi dan kombinasi. Ada 3 masalah kombinatorik dasar, yaitu: masalah eksistensi (existence problem), masalah penghitungan (counting problem) dan masalah optimasi (optimization problem).

2.1 PRINSIP PENGHITUNGAN DASAR

Dalam analisis masalah kombinatorik dikenal dua prinsip penghitungan dasar (basic counting principles), yaitu: Kaidah Perkalian (Rule of Product) dan Kaidah Penjumlahan (Rule of Sum).

2.1.1  Kaidah Perkalian

 Kaidah perkalian mengatakan bahwa:

Misal dua percobaan dapat dilakukan. Jika satu percobaan memiliki m hasil yang mungkin dan percobaan yang lain memiliki n hasil yang mungkin, maka jika dua percobaan tersebut dilakukan bersamaan memiliki  m.n  hasil yang mungkin.

Secara umum, dikatakan bahwa:

Misalkan  r percobaan dapat dilakukan. Jika percobaan ke-i memiliki ni hasil yang mung-kin, 1ir, maka jika semua percobaan itu dilakukan bersamaan memiliki n1.n2.n3…..nr hasil yang mungkin.

Contoh-1:

Sebuah komite yang terdiri atas 2 orang masing-masing mewakili mahasiswa yunior dan senior akan dipilih. Jika calon dari yunior ada 6 orang dan calon dari senior ada 4 orang, maka ada  6 x 4 = 24  komite berbeda yang dapat dipilih..

 Contoh2:

Sebuah dadu dan sebuah uang logam dilempar secara bersamaan, maka hasil yang mungkin: – untuk dadu, mata dadu: 1, 2, 3, 4, 5, 6, maka ada 6 hasil yang mungkin,

– untuk uang logam, gambar dan angka,  maka ada 2 hasil yang mungkin.

Sehingga dengan kaidah perkalian diperoleh  6 x 2 = 12  hasil yang mungkin.

 2.1.2        Kaidah Penjumlahan

Kaidah penjumlahan mengatakan bahwa:

Misal dua percobaan dapat dilakukan. Jika satu percobaan memiliki m hasil yang mungkin dan percobaan yang lain memiliki n hasil yang mungkin, maka ada m+n hasil yang mungkin jika tepat satu percobaan dilakukan.

Secara umum, dikatakan bahwa:

Misalkan r percobaan dapat dilakukan. Jika percobaan ke-i memiliki ni hasil yang mungkin, maka ada n1+n2+n3+…+nr hasil yang mungkin jika tepat satu percobaan dilakukan.

 Contoh-3:

Sebuah bola diambil dari sebuah mangkuk yang berisi 4 bola merah dan sebuah kaleng yang berisi 6 bola putih yang masing-masing bernomor, maka hasil yang mungkin adalah:   untuk mangkuk ada 4 hasil dan untuk kaleng ada 6 hasil sehingga dengan kaidah penjumlahan hasil yang mungkin ada 4 + 6 = 10.

 Contoh4:.

Sebuah program komputer memiliki valid input berupa string huruf atau string angka dengan panjang 4. Berapa banyak valid input program tersebut yang mungkin?

Jawaban:

– Jika huruf atau angka dalam sebuah string boleh sama, maka:

String huruf ada sebanyak : 26 . 26 . 26. .26 =  (26)4 = 456.976

String angka ada sebanyak: 10 . 10 . 10 . 10  =  (10)4 = 10.000

Sehingga dengan kaidah penjumlahan, maka banyak valid string adalah:

456.976 + 10.000 = 466.976

– Jika huruf atau angka dalam sebuah string tidak boleh sama, maka:

String huruf ada sebanyak : 26 . 25 . 24 . 23 =  358.800

String angka ada sebanyak: 10 . 9 . 8 . 7       = 5.840

Sehingga dengan kaidah penjumlahan, maka banyak valid string adalah:

358.800 + 5.840 =  364.640