Matematika Diskrit Kombinatorial

TI Politala Matdis 1C

A.    Definisi Kombinatorial

Kombinatorial (combinatorial) adalah cabang matematika yang mempelajari pengaturan objek-objek. Solusi yang ingin kita peroleh dengan kombinatorial ini adalah jumlah cara pengaturan objek-objek tertentu di dalam himpunannya. Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan. Percobaan adalah proses fisik yang hasilnya dapat diamati.

Contoh percobaan : 

a)      Melempar dadu : Enam hasil percobaan yang mungkin untuk pelemparan dadu adalah muka dadu 1,2,3,4,5 atau 6

b)      Melempar koin uang : koin uang Rp. 500 Hasil percobaan melempar koin Rp. 500 ada dua kemungkinan  muka koin yang bergambar wayang atau muka koin yang bergambar spiderman

c)      Memilih lima orang wakil dari 100 orang mahasiswa
Hasil yang diperoleh adalah perwakilan yang beranggotakan lima orang mahasiswa. Kemungkinan perwakilan yang dapat dibentuk banyak sekali.

d)      Menyusun jumlah kata yang panjangnya 5 huruf yang dapat dibentuk dari huruf-huruf a,b,c,d,e, tidak boleh ada huruf yang berulang di dalam kata.
Hasil yang diperoleh adalah kata yang disusun oleh huruf-huruf tersebut, misalnya abcde, abced, dan seterusnya.

B.     Kaidah Pencacahan

Kaidah Pencacahan Terdapat dua kaidah pencacahan, yaitu kaidah penjumlahan dan kaidah perkalian.

1.      Kaidah penjumlahan Kaidah penjumlahan menganut prinsip umum bahwa keseluruhan sama dengan jumlah dari bagian-bagiannya. Secara umum, kaidah penjumlahan dijelaskan sebagai berikut. Jika pekerjaan pertama dapat dilakukan dalam m cara dan pekerjaan kedua dapat dilakukan dalam n cara, dan kedua pekerjaan tersebut tidak dapat dilakukan secara simultan, maka untuk menyelesaikan kedua pekerjaan tersebut dapat dilakukan dalam m + n cara. Secara umum dirumuskan sebagai berikut. Jika Ei (i = 1, 2, 3, ..., k) adalah k pekerjaan sedemikian sehingga tidak pekerjaan-pekerjaan yang dapat dilakukan atau terjadi secara simultan dan jika Ei dapat dilakukan dalam ni cara, maka untuk melakukan pekerjaanpekerjaan tersebut terdapat n1 + n2 + n3 + ... + nk.  

Contoh 1 : Untuk bepergian ke Cirebon dari Yogya dapat melalui jalur Purwokerto, jalur semarang, atau melalui jalur Temanggung. Dengan menggunakan kaidah penjumlahan, dapat ditentukan bahwa terdapat tiga cara bepergian dari Yogya ke Cirebon.  

Contoh 2 : Suatu perpustakaan memiliki koleksi 40 buku sosiologi dan 50 buku antropologi. Dengan menggunakan kaidah penjumlahan dapat ditentukan banyaknya kemungkinan bagi siswa dalam memilih sebuah buku dari kedua jenis buku tersebut tanpa memperhatikan jenis buku, yaitu 40 + 50 = 90 cara.

2.      Kaidah Perkalian Untuk memahami kaidah perkalian, perhatikan ilustrasi sebagai berikut. Pak Budi bermaksud membeli sepeda motor. Saat ini di pasaran terdapat 4 merek sepeda motor yang terkenal, yakni Scorpio, Alfa, Mercury, dan Jossa. Tersedia 3 jenis kapasitas silinder untuk masing-masing sepeda motor tersebut, yaitu 100 cc, 110 cc, dan 125 cc. Masing-masing sepeda motor menyediakan 2 macam pilihan warna, yakni hitam dan merah. Berapa macam pilihan yang dapat dipilih Pak Budi dalam membeli sepeda motor? Untuk menggambarkan berbagai pilihan yang dapat dipilih Pak Budi, perhatikan alur berpikir sebagai berikut. Mula-mula Pak Budi menentukan merek sepeda motor yang akan ia beli, karena hal ini akan mempengaruhi harga sepeda motor. Dalam hal ini Pak Budi dapat memilih salah satu dari 4 merek sepeda motor yang tersedia. Jelasnya, Pak Budi mempunyai 4 pilihan. Setelah menentukan merek, Pak Budi harus menentukan kapasitas silinder, karena hal inipun mempengaruhi harga sepeda motor. Dalam hal ini, pak Budi dapat memilih 3 kapasitas silinder yang tersedia. Jelasnya Pak Budi mempunyai 3 macam pilihan. Terakhir, Pak Budi harus memilih salah satu dari dua warna yang tersedia. Jelasnya, Pak Budi mempunyai 2 pilihan. Ketika Pak Budi memilih merek sepeda motor, pikirannya bercabang 4. Ketika memilih kapasitas silinder, pikiran Pak Budi bercabang 3, dan sewaktu harus memilih warna, pikiran pak Budi bercabang 2. Jadi banyaknya semua pilihan adalah 4 x 3 x 2 = 24. Ketika Pak Budi menentukan banyaknya pilihan, sesungguhnya ia telah menggunakan kaidah perkalian, yang secara umum dijelaskan sebagai berikut.

Jika kegiatan pertama dapat dikerjakan dengan 1 n cara yang berbeda, kegiatan kedua dapat dilakukan dengan 2 n cara yang berbeda, kegiatan ketiga dapat dikerjakan dengan 3 n cara yang berbeda, dan seterusnya.... kegiatan ke-k dapat dikerjakan dengan k n cara berbeda, maka banyaknya cara untuk melakukan semua kegiatan tersebut secara berurutan adalah: k n x n x n x ... x n 

C.     Notasi Faktorial

Suatu perkalian bilangan asli berturut-turut dari 1 sampai n atau dari n sampai 1 disebut n faktorial yang dinotasikan dengan n!, yaitu: n! = n(n -1)(n - 2)(n - 3) ... (1) = (1)(2)...(n - 2)(n -1)n Berdasarkan definisi tersebut, maka n! = n (n-1)(n-2)(n-3) ... (1) = n (n-1)! dan 1! = 1 (0)! = 1. Akibatnya harus didefinisikan bahwa 0! = 1.

D.    Permutasi

Dari 5 orang yang bersedia menjadi pengurus suatu organisasi kampus, yakni Ali, Budi, Cici, Dini, dan Endro, hanya akan dipilih 2 orang yang akan menempati posisi (jabatan) sebagai ketua dan wakil ketua. Banyaknya semua cara yang mungkin dalam menyusun permutasi tersebut dapat ditentukan dengan penggunakan kaidah perkalian sebagai berikut. Jabatan Ketua Wakil Ketua Banyak Cara 5 4 Jadi, banyaknya cara dimaksud adalah 5 x 4 = 20 cara.

E.     Kombinasi

Kata kombinasi lebih sering dijumpai dalam kehidupan sehari-hari daripada kata permutasi. Perhatikan contoh berikut. Dari 5 pengurus harian Himpunan Mahasiswa Jurusan Matematika, yakni Anto, Badrun, Candra, Dini, dan Endro akan ditentukan 2 orang yang akan mewakili organisasi itu untuk mengikuti pertemuan organisasi-organisasi mahasiswa tingkat nasional. Ada berapa kemungkinan susunan wakil organisasi itu? Beberapa susunan wakil pengurus untuk mengikuti pertemuan tersebut adalah sebagai berikut. 

Anto – Candra 

Candra – Anto 

Badrun – Dini 

Dini – Badrun