KOMBINATORIKlisani.staff.unja.ac.id/wp-content/uploads/sites/... · 1 Kaidah Perkalian Kaidah...
Transcript of 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)
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
Referensi
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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).
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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.
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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.
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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:
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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.
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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.
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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.
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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.
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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.
???
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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 =
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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.
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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.
Dosen : Lisani.S.TP.MP Teknologi Industri Pertanian Universitas JambiMatematika Dasar
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