kombinatorika - julio.staff.ipb.ac.id · pdf filehasil susunan pemenang yang mungkin adalah p...

Learning OutcomesPencacahan

PermutasiKombinasi

Sebaran Bola dalam KeranjangKesimpulan

Kombinatorika

Julio Adisantoso

11 Pebruari 2014

Julio Adisantoso Kombinatorika


PermutasiKombinasi


Learning Outcome

Mahasiswa dapat memahami pentingnya teknik counting problemdalam Ilmu Hitung Peluang

Mahasiswa mengetahui dan memahami teknik kombinatorika

Mahasiswa dapat melakukan pencacahan objek menggunakan teoripermutasi dan kombinasi

Mahasiswa dapat membuktikan beberapa teorema kombinatorika

OutlineCounting problem

Permutasi

Kombinasi

Binomial dan multinomial



PermutasiKombinasi


Masalah Pencacahan (Counting Problem)

Contoh kasus: Ali membeli sebuah lampu pijar dari suatu toko.Sebelum membayar, lampu itu dicobanya dahulu apakah dapat menyalaatau mati. Apa saja kemungkinan yang akan terjadi?Kegiatan mencoba lampu pijar dinamakan percobaan. Setiap lampuyang akan dicoba hanya memiliki dua kemungkinan hasil, yaitu nyalaatau mati, misalkan dilambangkan sebagai A (nyala) atau M (mati).Maka hasil percobaan yang mungkin terjadi, dapat dinotasikan sebagaihimpunan P = {A, M}. Bagaimana hasil percobaan jika Ali membelidua lampu pijar?Kaidah pencacahan mencoba menemukan berapa banyaknya hasil yangmungkin muncul pada berbagai macam percobaan.



PermutasiKombinasi


Contoh

ContohPada lomba lari cepat 100m, empat orang pelari lolos ke putaran final, yaituA, B, C, dan D. Pada pertandingan itu tersedia hadiah untuk juara I dan II.Pertanyaan yang mungkin muncul, berapa macam susunan pemenang yangakan muncul di akhir pertandingan?

Solusi

Hasil susunan pemenang yang mungkin adalah P={AB, AC, AD, BA, BC,BD, CA, CB, CD, DA, DB, DC} atau sebanyak 4(4-1)=12 kemungkinan.



PermutasiKombinasi


Contoh

ContohSeseorang asal Jakarta akan melakukan perjalanan berawal di Bandung,kemudian ke Yogyakarta, dan berakhir di Surabaya. Saat ini dia harusmemutuskan jenis transportasi yang akan digunakan. Dari Jakarta keBandung, dia bisa memilih bus atau pesawat, dari Bandung ke Yogya bisamemilih bus, pesawat, atau kereta api, dan dari Yogya ke Surabaya bisamemilih naik bus atau kereta api. Berapa macam jenis transportasi yangdapat dipilih?

SolusiPeristiwa 1: Jakarta ke Bandung, ada 2 kemungkinan transportasiPeristiwa 2: Bandung ke Yogya, ada 3 kemungkinan transportasiPeristiwa 3: Yogya ke Surabaya, ada 2 kemungkinan transportasiMaka secara bersama, ada 2× 3× 2 = 12 kemungkinan transportasi.



PermutasiKombinasi


Permutasi

Penting

Tidak ada aturan yang pasti untuk menjawab pertanyaan berapa banyakhasil yang mungkin muncul dari suatu percobaan. Secara umum, bisanyadipakai salah satu atau gabungan dari pendekatan-pendekatan yang disebutpermutasi dan kombinasi

Hukum/DalilMisalkan terdapat dua percobaan. Jika percobaan 1 menghasilkan mkemungkinan kejadian, dan percobaan 2 menghasilkan n kemungkinankejadian, maka akan ada mn kemungkinan kejadian dari percobaan bersama1 dan 2. Hukum ini dapat dikembangkan untuk k percobaan, masing-masingmenghasilkan n1, n2, ..., nk kemungkinan kejadian, maka k percobaan secarabersama akan menghasilkan n1n2...nk kemungkinan kejadian.



PermutasiKombinasi


Latihan Permutasi

Contoh

Contoh 2-1. Dalam suatu kelas terdapat 3 mahasiswa laki-laki dan 2perempuan. Mereka diberi ujian dan diperingkat berdasarkan nilai ujian.Asumsikan tidak ada dua mahasiswa memperoleh nilai ujian yang sama.

1 Berapa banyak susunan peringkat berbeda yang mungkin dihasilkan?2 Jika mahasiswa laki-laki diperingkat sendiri, dan demikian juga

mahasiswa perempuan, berapa banyak susunan peringkat berbeda yangmungkin?



PermutasiKombinasi


Latihan Permutasi

Contoh

Contoh 2-2. Ali memiliki 10 buku, yaitu 4 Matematika, 3 Kimia, 2 Sejarah,dan 1 Bahasa. Ia ingin menyusun buku dimana yang sejenis mengelompokmenjadi satu. Berapa banyak susunan buku yang mungkin?

Contoh

Contoh 2-3. Berapa banyak susunan yang dapat dihasilkan dari huruf-hurufP E P P E R?Ingat, berbagai susunan dari PPP dihitung sama sebagai satu kemungkinan.Demikian pula susunan dari EE.



PermutasiKombinasi


Permutasi Majemuk

Berdasarkan Contoh 2-3, maka dapat dibuat kaidah secara umum:

Hukum/DalilJika diketahui n objek, dimana terdapat n1, n2, ..., dan nr yang sama,n1 + n2 + ... + nr = n maka banyaknya permutasi atau susunan yangberbeda sebanyak:

n!n1!n2!...nr!



PermutasiKombinasi


Latihan Permutasi

Contoh

Contoh 2-4. Berapa banyak susunan bendera yang mungkin jika terdapat 4bendera biru, 3 bendera merah, dan 2 bendera kuning?

Contoh

Contoh 2-5. Achess tournament has 10 competitors, of which 4 are Russian,3 are from the United States, 2 are from Great Britain, and 1 is from Brazil.If the tournament result lists just the nationalities of the players in the orderin which they placed, how many outcomes are possible?



PermutasiKombinasi


Kombinasi

Contoh

Contoh 2-6. Berapa banyak kemungkinan 3 objek dapat dipilih dari 5 objekA, B, C, D, dan E?

SolusiPersoalan ini sama saja dengan memilih satu per satu objek berturut-turut.Pemilihan pertama menghasilkan 5 kemungkinan, pemilihan keduamenghasilkan 4 kemungkinan, dan terakhir ada 3 kemungkinan. Makasecara bersama akan ada 5.4.3 kemungkinan. Misalkan yang terpilih adalahA, B, dan C, maka susunan yang mungkin terjadi ada 3.2.1=3!=6kemungkinan, yaitu ABC, ACB, BAC, BCA, CAB, dan CBA. Karena urutanpemilihan tidak diperhatikan, maka diperoleh banyaknya kemungkinan:

5.4.33.2.1

= 10



PermutasiKombinasi


Kaidah Pengambilan Objek

Istilah1 TERTATA

urutan diperhatikan2 TIDAK TERTATA

urutan tidak diperhatikan3 DENGAN PEMULIHAN

objek yang diambil dikembalikan lagi sebelum proses pengambilanberikutnya

4 TANPA PEMULIHANobjek yang diambil tidak dikembalikan lagi



PermutasiKombinasi


Koefisien Binomial

TeoremaKoefisien Binomial. Secara umum, jika dipilih r objek dari n objek dimanaurutan terpilih tidak diperhatikan (tidak tertata), maka diperoleh banyaknyakemungkinan:

n(n− 1)(n− 2)...(n− r + 1)r!

=n!

(n− r)!r!=(

nr

)Nilai

(nr

)disebut sebagai koefisien binomial.



PermutasiKombinasi


Latihan Kombinasi

Contoh

Contoh 2-7. Suatu panitia terdiri dari 3 orang dipilih dari 20 orang. Berapabanyak kemungkinan anggota panitia dapat terpilih?

Contoh

Contoh 2-8. Dari 5 perempuan dan 7 laki-laki, berapa lemungkinan yangterjadi jika dipilih anggota panitia yang terdiri dari 2 perempuan dan 3laki-laki? Bagaimana jika 2 dari laki-laki bermusuhan dan menolak adadalam panitia secara bersama?



PermutasiKombinasi


Teorema Binomial

Teorema

(x + y)n =n∑

k=0

(nk

)xkyn−k

BuktiGunakan induksi matematika (baca Sheldon Ross p.8).



PermutasiKombinasi


Koefisien Multinomial

TeoremaTerdapat n objek berbeda dibagi ke dalam r kelompok yang berbedamasing-masing berukuran n1, n2, ..., nr, dimana

∑ri=1 ni = n. Maka

banyaknya kemungkinan yang terjadi adalah(nn1

)(n− n1

n2

)...

(n− n1 − n2 − ...− nr−1

nr

)

=n!

n1!n2!...nr!



PermutasiKombinasi


Latihan

Contoh

Contoh 2-9. Suatu Kantor Polsek memiliki anggota 10 polisi. Jika 5 polisiadalah petugas patroli di jalan, 2 polisi pos jaga, dan 3 polisi administrasi,berapa banyak susunan yang mungkin?

Contoh

Contoh 2-10. Ada 10 orang pemain basket dibagi ke dalam tim A dan B,masing-masing 5 orang. Tim A bermain di satu liga, dan tim B bermain diliga lainnya. Berapa banyak pembagian tim yang mungkin terjadi?



PermutasiKombinasi


Sebaran Bola dalam Keranjang

TeoremaJika diketahui yi = xi + 1 untuk i = 1, 2, ..., r maka y1+y2+...+yn=n + r.Dengan demikian, diperoleh juga banyaknya kemungkinan susunan menjadi(

n + r − 1n− 1

)=(

n + r − 1r

),

r∑i=1

xi = n



PermutasiKombinasi


Latihan

Contoh

Contoh 2-11. Berapa banyak bilangan non-negatif berbeda sebagai jawabanpersamaan x1+x2=3 yang mungkin?

Contoh

Contoh 2-12. Seorang investor mempunyai uang 20 ribu dollar, inginmenginvestasikan uang tersebut ke dalam 4 jenis investasi yang berbeda.Setiap investasi harus dalam satuan seribu dollar. Jika total uang 20 ribudollar diinvestasikan semua, ada berapa kemungkinan strategi investasi yangbisa dilakukan? Bagaimana jika tidak semua uang tersebut diinvestasikan(artinya ada uang yang disimpan)?



PermutasiKombinasi


Kesimpulan

TeoremaTeorema PembilanganJika tindakan 1, 2, ..., k dilaksanakan berututan dan masing-masingtindakan dapat menimbulkan n1, n2, ..., nk peristiwa, sertatindakan-tindakan tersebut tidak berkaitan satu sama lain, maka banyaknyarangkaian peristiwa yang mungkin timbul ada n1 × n2 × ...× nk =

∏ki=1 ni.



PermutasiKombinasi


Kesimpulan

Permasalahan kombinatorial dapat dirumuskan sebagai pengambilan r objekdari n objek yang berbeda. Pengambilan dapat dilakukan dengan dua cara:

1 Tanpa pemulihan (without replacement), r ≤ n2 Dengan pemulihan (with replacement), r dapat <, =, atau > dari n

Pengambilan tanpa pemulihan maupun dengan pemulihan, dapat bersifat:1 Tidak tertata (unordered) jika urutan objek yang terambil tidak

diperhatikan2 Tertata (ordered) jika urutan objek yang terambil diperhatikan



PermutasiKombinasi


Kesimpulan

Permasalahan kombinatorial tersebut dapat disimpulkan seperti pada tabelberikut:

Urutan objek Cara pengambilan Cara pengambilanyang terambil Tanpa pemulihan Dengan pemulihanTertata Permutasi r dari Permutasi r bola yang

n objek yang berbeda berbeda ke dalam n wadahnPr = n!

(n−r)! nr

Tidak Tertata Kombinasi r objek Penempatan r bola yang samadari n objek ke dalam n wadah

nCr =(

nr

) (n + r − 1

r

)


kombinatorika - julio.staff.ipb.ac.id · pdf filehasil susunan pemenang yang mungkin adalah p...

Documents