kombinatoriklisani.staff.unja.ac.id/wp-content/uploads/sites/... · 1 kaidah perkalian kaidah...

1Pertemuan ke 3

KOMBINATORIK

Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar

Penambahan & Revisi : lisani (2019)


Referensi


Kombinatorik

Kombinatorik menitikberatkan studi tentang:

pengaturan, pola, disain, penandaan, penja-

dualan, 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)

Masalah optimasi (optimization problem).



PRINSIP PENGHITUNGAN DASAR

Dalam analisis masalah kombinatorik

dikenal dua prinsip penghitungan dasar

(basic counting principles), yaitu:

Kaidah Perkalian (Rule of Product)

Kaidah Penjumlahan (Rule of Sum).

Kaidah Perkalian1

Kaidah perkalian mengatakan bahwa:

Misalkan r percobaan dapat dilakukan. Jika percobaan ke-i memiliki ni hasil yang

mung-kin, 1 i r, maka jika semua percobaan itu dilakukan bersamaan memiliki

n1.n2.n3…..nr hasil yang mungkin.

Secara umum, dikatakan bahwa:

Misal dua percobaan dapat dilakukan. Jika satu percobaan memiliki m hasil yang mungkin

dan percobaan yang lain memiliki n hasil yg mungkin, maka jika dua percobaan tersebut

dilakukan bersamaan memiliki m.n hasil yang mungkin.


Contoh

Sebuah dadu dan sebuah uang logam dilempar scr bersamaan, mk hasil yg mungkin:

- untuk dadu, mata dadu: 1, 2, 3, 4, 5, 6, maka ada 6 hasil yg mungkin,

- untuk uang logam, gambar dan angka, maka ada 2 hasil yg mungkin.

Sehingga dgn kaidah perkalian diperoleh 6 x 2 = 12 hasil yg mungkin.

2.

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, mk ada 6 x 4 = 24 komite berbeda yg dpt dipilih..

1.



Kaidah Penjumlahan2

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.

Secara umum, dikatakan 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.

Kaidah penjumlahan mengatakan bahwa:


Contoh

Sebuah program komputer memiliki valid input berupa

string huruf atau string angka dengan panjang 4. Berapa

banyak valid input program tersebut yg mungkin?

Sebuah bola diambil 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.

3.

4.


Jawaban:

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

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

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

Sehingga dengan kaidah penjumlahan, maka banyak valid string adalah:

456976 + 10000 = 466976


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

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

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

Sehingga dengan kaidah penjumlahan, maka banyak valid string adalah:

358800 + 5840 = 364640


PERMUTASIDefinisi: (fakultet/faktorial)

Untuk sembarang bilangan bulat n 0, n faktorial yg ditulis n!, didefinisikan

sebagai:

0! = 1, n! = (n) (n-1) (n-2) ….. (3) (2) (1)

Sehingga, 10! = 10.9.8.7.6.5.4.3.2.1 = 3628800

Untuk mengatur 3 huruf : a, b dan c secara berurutan, maka hasil yang

mungkin adalah : abc, acb, bac, bca, cab, dan cba. Masing-masing urutan ini

disebut “permutasi” dari 3 obyek berbeda yaitu: a, b dan c. Jadi

banyaknya permutasi dari 3 obyek berbeda ada 6.


Contoh:

Karena ada 6 orang maka dalam antrian terdapat 6 posisi

berurutan. Untuk mengisi posisi antrian urutan pertama

sampai keenam berturut-turut ada: 6, 5, 4, 3, 2, 1 cara.

Sehingga dengan kaidah perkalian diperoleh banyaknya

kofigurasi antrian adalah 6.5.4.3.2.1 = 6! = 720.

Penyelesaian:

Sebanyak 6 orang akan membeli tiket tanda masuk

sebuah pertunjukkan secara bersa-maan. Jika hanya

tersedia sebuah loket pembelian tiket, maka berapa

konfigurasi antrian yang mungkin dapat terjadi.

5.


Profesor Amir memiliki koleksi buku yang terdiri atas:

5 buku Matematika, 4 buku Statistika, 3 buku Fisika dan

2 buku Kimia, diatur berjajar dlm sebuah rak buku

shingga buku yg memiliki subyek sama berkumpul.

Tentukan ada berapa pola aturan yang mungkin?

6.

Penyelesaian : . ………

- Untuk mengatur klpk buku Matematika ada 5! ,

- Untuk mengatur klpk buku Statistika ada 4! ,

- Untuk mengatur klpk buku Fisika ada 3! ,

- Untuk mengatur klpk buku Kimia ada 2! , dan

- Untuk mengatur subyek buku ada 4! .

Sehingga dgn kaidah perkalian diperoleh (5!) (4!) (3!) (2!) (4!)

pola aturan berbeda yg mungkin.


Tentukan ada berapa cara untuk menyusun berjajar

huruf-huruf yang terdapat dalam sebuah kata “PEPPER”!7.

Penyelesaian

Jika 3 huruf P dan 2 huruf E dapat dibedakan, mk ada

sbnyk 6! cara berbeda yg mungkin. Akan tetapi jika 3

huruf P dan 2 huruf E tidak dpt dibedakan, mk 3!

susunan huruf P dikalikan 2! susunan huruf E hanya

diwakili salah satu saja. Shingga bnyknya susunan yg

mungkin ada = = = =60.

???


8. Sebanyak 9 bola: 4 bola berwarna merah, 3 bola

berwarna putih, dan 2 bola berwarna biru dimasukkan

kedalam sebuah tabung kaca. Tentukan ada berapa pola

warna susunan bola yang mungkin!

Karena 4 bola merah, 3 bola putih dan 2 bola biru

tak dapat dibedakan, maka terdapat sebanyak

= = =

= 1260 pola warna.

Penyelesaian


Permutasi

Masalah ini identik dgn mendapatkan permutasi 3 obyek

yg diambil dari 100 obyek berbeda. Jd ada sebanyak

100 P 3 = = (100).(99).(98) = 970.200 cara.

Jawaban:

Ada berapa cara untuk memilih seorang pemenang

pertama, seorang pemenang kedua dan seorang pemenang

ketiga dari sebuah kontes yg diikuti oleh 100 kontestan?

9

Banyaknya permutasi r obyek yang diambil dari n obyek

berbeda adalah

N r =


10 Sebuah kata kunci (password) terdiri atas 6 huruf kecil.

Tentukan ada berapa kata kunci berbeda yang mungkin?

Penyelesaian

- Jika huruf-huruf dalam kata kunci tidak boleh sama, maka

ada:

- 6 P 6 = =(26).(25).(24).(23).(22).(21)katakunci.

- Jk huruf2 dlm kata kunci boleh sama, mk ada :

26 x 26 x 26 x 26 x 26 x 26 = (26)6 kata kunci.


KOMBINASI

Banyaknya kombinasi r obyek yang diambil dari n

obyek berbeda adalah =

Untuk sembarang bilangan bulat positip n dan

bilangan tak negatip r, dengan r n, maka:

Sebuah kombinasi r obyek yang dipilih dari sebuah

himpunan dengan n elemen adalah sebuah pemilihan

r elemen tak berurutan dari himpunan tersebut.


Contoh:

Sebuah team bola volley inti diseleksi dari sebanyak 10 kandidat

anggota. Berapakah banyaknya konfigurasi team inti yang

mungkin?

11

= = = 210

konfigurasi team inti.

Karena dalam team tidak dikenal urutan, maka

masalah ini identik dengan masalah menghitung

kombinasi 6 obyek yang diambil dari 10 obyek

berbeda. Jadi ada sebanyak

Penyelesaian

NEXT Logika matematikaPert ke 4

Matematika dasar

kombinatoriklisani.staff.unja.ac.id/wp-content/uploads/sites/... · 1 kaidah perkalian kaidah...

Documents