Pengantar Kombinatorik

KOMBINATORIK. Kombinatorik adalah suatu cabang matematika yang mempelajari pengaturan objek. Penyelesaian yang ingin diperoleh dengan kombinatorik adalah banyak cara pengaturan objek dalam suatu himpunan tertentu. Tiga buah contoh berikut sebagai ilustrasi untuk memperjelas persoalan seperti apa yang akan dipecahkan dengan kombinatorik.

Contoh Pertama :

Misalkan nomor plat mobil di negara X terdiri atas 4 angka diikuti dengan 2 huruf. Angka pertama tidak boleh 0. Berapa banyak nomor plat mobil yang dapat dibuat?

Contoh Kedua :

Dari 20 anggota Fraksi X di DPR akan dibentuk suatu komisi beranggotakan 6 orang. Berapa banyak cara memilih anggota komisi bila seorang anggota yang namanya A harus masuk di dalam komisi tersebut?

Contoh Ketiga :

Misalkan ada 5 buah angka yaitu 2, 3, 5, 6 dan 7. Dari angka-angka tersebut dibentuk sebuah bilangan yang terdiri atas 3 angka dan setiap angka hanya digunakan sekali saja. Berapa bilangan saja yang dapat dibentuk itu bernilai paling besar 500?

Cara yang paling sederhana untuk menyelesaikan persoalan semacam di atas adalah mengenumerasi (mencacah, membilang, menghitung) satu per satu semua kemungkinan jawaban. Untuk persoalan dengan banyak objek yang sedikit mengenumerasi setiap kemungkinan jawaban masih dapat dilakukan tetapi untuk persoalan dengan objek yang banyak cara enumerasi tidak sangkil (efektif). Misalnya pada contoh pertama semua kemungkinan jawabannya adalah seperti di bawah ini :

                1234 AB

                1234 AC

                2345 CA

                2345 MN

                Dst …

Mungkin kita sudah lelah sebelum usaha mengenumerasi semua kemungkinan nomor plat mobil yang dapat dibuat selesai karena nomor plat mobil yang dapat dibentuk amat sangat banyak. Di sinilah peran kombinatorik yang merupakan seni berhitung dalam menyelesaikan persoalan semacam ini dengan cepat. Kombinatorik dapat digunakan untuk menjawab persoalan semacam ini tanpa perlu mengenumerasi semua kemungkinan jawabannya. Hal ini dapat dilakukan karena di dalam kombinatorik terdapat kaidah/ aturan/ prinsip/ hukum/ kaidah dasar menghitung untuk mengetahui banyak cara pengaturan objek-objek dapat dilakukan dari suatu himpunan objek.

ANGKA adalah Lambang Bilangan. Bilangan itu Abstrak.

B. KAIDAH DASAR MENGHITUNG

Di dalam kombinatorik kita harus menghitung semua kemungkinan pengaturan objek-objek dari suatu himpunan objek. Dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatorik adalah :

1) Kaidah Perkalian (Rule of Product)

2) Kaidah Penjumlahan (Rule of Sum)

Kedua kaidah ini dapat digunakan untuk memecahkan persoalan menghitung. Kombinatorik didasarkan pada hasil yang diperoleh dari suatu percobaan/ eksperimen. Percobaan adalah proses fisik yang hasilnya dapat diamati. Contoh-contoh percobaan dan hasilnya adalah sebagai berikut.

a) Melambungkan sebuah dadu

Enam hasil percobaan yang mungkin dari pelambungan sebuah dadu adalah muncul mata dadu 1, 2, 3, 4, 5, dan 6.

b) Melambungkan koin uang Rp 100

Hasil percobaan pelambungan koin Rp 100 ada 2 kemungkinan, yaitu Muka koin yang bergambar Rumah Gadang atau muka koin yang bergambar wayang.

c) Memilih 5 orang wakil dari 100 orang mahasiswa.

Hasil yang diperoleh adalah perwakilan yang beranggotakan 5 orang mahasiswa. Kemungkinan perwakilan yang dapat dibentuk banyak sekali.

B1. Kaidah Perkalian (Rule of Product)

Apabila percobaan pertama mempunyai m hasil yang mungkin terjadi, percobaan kedua memiliki n  hasil yang mungkin terjadi sehingga bila percobaan pertama dan percobaan kedua dilakukan maka terdapat m x n hasil yang mungkin terjadi.

B1. Kaidah Penjumlahan (Rule of Sum)

Apabila percobaan pertama mempunyai m hasil yang mungkin terjadi, percobaan kedua memiliki n  hasil yang mungkin terjadi sehingga bila dilakukan hanya salah satu percobaan saja (percobaan 1 atau percobaan 2) maka terdapat m + n hasil yang mungkin terjadi.

Catatan : Perhatikanlah kata dan serta atau. Kedua kata itu adalah kata kunci untuk mengidentifikasi apakah suatu hasil percobaan diselesaikan dengan kaidah perkalian atau kaidah penjumlahan. Kaidah perkalian menyatakan bahwa kedua percobaan dilakukan secara simultan sedangkan pada kaidah penjumlahan kedua percobaan dilakukan tidak simultan.

Contoh :

Sebuah rumah makan menyiapkan 4 jenis makanan yaitu nasi goreng, roti, sate, dan sup serta 3 jenis minuman yaitu susu, kopi, dan teh. Bila setiap orang pengunjung boleh memesan 1 makanan dan 1 minuman berapakah kemungkinan pasangan makanan dan minuman yang dapat dipesan?

Perhatikan diagram pohon berikut, akar adalah awal pemilihan, cabang adalah alternatif penyelesaian dan daun adalah akhir penyelesaian.

Dengan cara yang enumerasi, maka pasangan makanan dan minuman yang dapat dipesan adalah:

  1. Nasi Goreng & Susu
  2. Nasi Goreng & Kopi
  3. Nasi Goreng & Teh
  4. Roti & Susu
  5. Roti & Kopi
  6. Roti & Teh
  7. Sate & Susu
  8. Sate & Kopi
  9. Sate & Teh
  10. Sup & Susu
  11. Sup & Kopi
  12. Sup & Teh

Semuanya ada 12 pasang makanan dan minuman yang dapat dipesan.

Dalam kombinatorik, kejadian seperti ini dipandang bahwa orang harus memilih makanan dan minuman. Ada 4 cara memilih makanan dan ada 3 cara memilih minuman, sehingga dengan menggunakan kaidah perkalian kita dapatkan banyak kemungkinan adalah 4 x 3 = 12 pilihan menu.

Contoh Kedua :

Jabatan ketua himpunan mahasiswa jurusan matematika dapat diduduki mahasiswa angkatan tahun 2011 atau angkatan tahun 2012. Jika terdapat 45 mahasiswa angkatan 2011 dan 52 mahasiswa angkatan 2012, berapa cara dapat memilih pejabat ketua himpunan?

Jabatan ketua himpunan hanya dapat diduduki seorang mahasiswa dari 2 angkatan. Ada 45 cara memilih 1 orang mahasiswa dari angkatan 2011 dan 52 cara memilih 1 orang mahasiswa dari angkatan 2012. Namun hanya 1 mahasiswa dari kedua angkatan itu yang terpilih. Dalam kombinatorik dari dua kejadian hanya salah satu dari dua kejadian dilakukan. Sehingga dengan menggunakan kaidah penjumlahan maka banyak cara memilih pejabat ketua himpunan adalah : 45 + 52 = 97 pilihan.

C. PERLUASAN KAIDAH MENGHITUNG

Kaidah perkalian dan kaidah penjumlahan di atas dapat diperluas hingga memuat lebih dari 2 percobaan. Jika N adalah dua percobaan masing-masing mempunyai P1, P2, P­3, …, Pn hasil percobaan yang mungkin terjadi dan setiap Pi, i = 1, 2, 3, …, n tidak bergantung pada percobaan sebelumnya maka hasil percobaan yang mungkin terjadi adalah :

a. P1 x P2 x P­3 x  … x Pn untuk kaidah perkalian.

b. P1 + P2 + P­3 +  … + Pn untuk kaidah penjumlahan.

Soal :

Dalam satu set kartu bridge lengkap (52 buah), berapa macam cara untuk mengambil :

  1. Sebuah hati atau sebuah daun.
  2. Sebuah hati atau sebuah As.
  3. Sebuah As atau sebuah King.
  4. Sebuah Kartu Bernomor 2 hingga 10