Materi pembelajaran Kombinatorial

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.

1.  Percobaan

Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan. Percobaan adalah proses fisik yang hasilnya dapat diamati.

Contoh percobaan :

a.     Melempar dadu

Satu hasil percobaan yang mungkin untuk pelemparan dadu adalah muka dadu 1,2,3,4,5 atau 6

b.     Melempar koin uang Rp. 500

Hasil percobaan melempar koin Rp. 500 ada dua kemungkinan : muka koin yang bergambar Wayang atau muka koin yang bergambar Spiderman

2.  Kaidah Dasar Menghitung

Terdapat 2 kaidah dasar yang digunakan untuk memecahkan banyak masalah persoalan menghitung

1.     Kaidah Perkalian (rule of product)

Bila percobaan satu mempunyai p hasil percobaan yang mungkin terjadi (atau menghasilkan p kemungkinan jawaban), percobaan dua mempunyai q hasil percobaan yang mungkin terjadi (atau menghasilkan q kemungkinan jawaban), maka bila percobaan satu dan percobaan dua dilakukan, maka terdapat p x q hasil percobaan (atau menghasilkan p x q kemungkinan jawaban).

2.     Kaidah Penjumlahan (rule of sum)

Bila percobaan satu mempunyai p hasil percobaan yang mungkin terjadi (atau menghasilkan p kemungkinan jawaban), percobaan dua mempunyai q hasil percobaan yang mungkin terjadi (atau menghasilkan q kemungkinan jawaban), maka bila hanya satu percobaan saja dilakukan (percobaan 1 atau percobaan 2), maka terdapat p + q kemungkinan hasil percobaan (atau menghasilkan p + q kemungkinan jawaban) yang mungkin terjadi.

Contoh 1 :

Sebuah Restoran menyediakan lima jenis makanan, misalnya nasi goreng pete, pecel lele pedas, soto ayam kampung, bebek goreng tutung, sop buntut panjang. Serta tiga jenis minuman, misalnya air putih bening, teh hitam manis, kopi tubruk berat. Jika setiap orang boleh memesan satu makanan ATAU satu minuman, berapa pasangan makanan dan minuman yang dapat dipesan ?

Penyelesaian :

Dalam kombinatorial, kita memandang bahwa dalam kejadian ini orang harus memilih makanan dan minuman. Ada kemungkinan memilih makanan,  yaitu nasi nasi goreng pete, pecel lele pedas, soto ayam kampung, bebek goreng tutung, sop buntut panjang. Ada 3 kemungkinan memilih minuman, yaitu air putih bening, teh hitam manis, kopi tubruk berat, sehingga dengan menggunakan kaidah perkalian, jumlah kemungkinan pasangan makanan dan minuman yang dapat dipesan adalah 5 x 3 = 15 pasang.

Contoh 2 :

Jabatan ketua himpunan dapat diduduki oleh mahasiswa angkatan 2009 atau angkatan tahun 2010. Jika terdapat 45 orang mahasiswa angkatan 2009 dan 52 orang mahasiswa angkatan 2010, berapa cara memilih ketua himpunan ?

Penyelesaian :

Jabatan yang ditawarkan hanya ada satu, yang dapat diduduki oleh salah seorang mahasiswa dari dua angkatan yang ada. Ada 45 cara memilih satu orang mahasiswa dari angkatan 2009, dan 52 cara memilih satu orang dari angkatan 2010, namun hanya satu dari kedua angkatan itu yang terpilih (angkatan 2009 atau angkatan 2010). Dalam kombinatorial, dari kedua kejadian, hanya satu dari dua kejadian yang dilakukan, sehingga dengan menggunakan kaidah penjumlahan, jumlah cara memilih ketua himpunan tersebut sama dengan jumlah mahasiswa pada kedua angkatan, yaitu 45 + 52 = 97 cara

Contoh 3 :

Sekelompok mahasiswa terdiri atas 4 orang pria dan 3 orang wanita. Berapa jumlah cara kemungkinan memilih untuk satu orang wakil pria dan satu orang wakil wanita ?

Penyelesaian :

Ada 4 kemungkinan memilih satu wakil pria dan 3 kemungkinan memilih satu wakil wanita. Jika dua orang wakil harus dipilih, masing-masing 1 pria dan 1 wanita, maka jumlah kemungkinan perwakilan yang dapat dipilih adalah 4 x 3 = 12.

Contoh 4 :

Sekelompok mahasiswa terdiri atas 4 orang pria dan 3 orang wanita. Berapa jumlah cara memilih satu orang yang mewakili kelompok tersebut (tidak peduli pria atau wanita) ?

Penyelesaian :

Ada 4 kemungkinan memilih satu wakil pria dan 3 kemungkinan memilih satu wakil wanita. Jika hanya satu orang wakil yang harus dipilih (pria atau wanita), maka jumlah kemungkinan wakil yang dapat dipilih adalah 4 + 3 = 7.

Contoh 5 :

Kursi-kursi di dalam Ruang 203 akan diberi nomor dengan sebuah huruf diikuti dengan bilangan bulat positif yang tidak lebih dari 50 (misalnya A1, A2, … B1, B2, .. Z1, Z2, … dan seterusnya). Berapa jumlah maksimum kursi yang dapat dinomori ?

Penyelesaian :

Ada 26 kemungkinan memilih huruf alphabet untuk nomor kursi dan 50 kemungkinan bilangan bulat positif yang dapat digunakan. Huruf alphabet dan bilangan bulat keduanya harus digunakan untuk penomoran. Jumlah penomoran kursi yang dapat dibuat adalah 26 x 50 = 1300. Jadi, jumlah maksimum kursi yang dinomori adalah 1300 buah.

Contoh 6 :

Terdapat empat rute yang dapat dilalui kendaraan dari Bandung ke Cirebon, dan tiga rute dari Cirebon ke Surabaya.

(a)  Berapa banyak cara si Teguh bepergian dengan kendaraan dari Bandung ke Surabaya melalui Cirebon?

(b) Berapa banyak cara si Udin bepergian pulang-pergi dengan kendaraan dari Bandung ke Surabaya melalui Cirebon ?

Penyelesaian :

(a)  Si Teguh dari Bandung ke Surabaya harus melewati rute Bandung-Cirebon dan rute Cirebon-Surabaya. Ada 4 pilihan rute dari Bandung ke Cirebon dan 3 pilihan rute dari Cirebon ke Surabaya, sehingga jumlah pilihan rute dari Bandung ke Surabaya via Cirebon adalah 4 x 3 = 12.

(b) Ada 12 rute dari Bandung ke Surabaya via Cirebon dan 12 rute dari Surabaya ke Bandung via Cirebon. Karena perjalanan pulang-pergi (Bandung-Surabaya atau Surabaya-Bandung), maka jumlah pilihan rute seluruhnya adalah 12 + 12 = 24 cara untuk berkendaraan pulang-pergi.

3.  Perluasan Kaidah Menghitung

Kaidah perkalian dan kaidah penjumlahan di atas dapat diperluas hingga mengandung lebih dari dua buah percobaan. Jika n buah percobaan masing-masing mempunyai p1, p2, … pn hasil percobaan yang mungkin terjadi yang dalam hal ini setiap pi tidak bergantung pada pilihan sebelumnya, maka jumlah hasil percobaan yang mungkin terjadi adalah :

(a)  p1 x p2 x … x pn untuk kaidah perkalian

(b) p1 + p2 + … + pn untuk kaidah perjumlahan

Contoh 7 :

Jika ada sepuluh pertanyaan yang masing-masing bisa dijawab benar atau salah (B atau S), berapakah kemungkinan kombinasi jawaban yang dapat dibuat ?

Penyelesaian :

Andaikan 10 pertanyaan tersebut sebagai 10 buah kotak, masing-masing kotak hanya berisi 2 kemungkinan jawaban, B atau S :

            B/S     B/S     B/S     B/S     B/S     B/S     B/S     B/S     B/S     B/S

              1          2          3          4          5          6          7          8          9        10

Disini kita menggunakan kaidah perkalian, karena kesepuluh kotak ini harus terisi dengan jawaban B atau S (kotak 1 dan kotak 2 dan kotak 3 dan … dan kotak 10). Jumlah kombinasi jawaban yang dapat dibuat :

                         (2) (2) (2) (2) (2) (2) (2) (2) (2)  = 210

Contoh 8 :

(a)  Berapa banyak jumlah kata yang terdiri dari 5 huruf yang dapat dibentuk dari huruf-huruf a,b,c,d,e jika tidak boleh ada huruf yang berulang di dalam kata

(b) Berapa banyak jumlah kata yang terdiri dari 5 huruf yang dapat dibentuk dari huruf-huruf a,b,c,d,e jika pengulangan huruf diperbolehkan

(c)  Berapa banyak jumlah kata pada jawaban soal (a) yang diawali oleh huruf a ?

(d) Berapa banyak jumlah kata pada jawaban soal (a) yang tidak diawali oleh huruf a ?

Penyelesaian :

Berapa banyak jumlah kata yang terdiri dari 5 huruf yang dapat dibentuk dari huruf-huruf a,b,c,d,e jika tidak boleh ada huruf yang berulang di dalam kata

Andaikan posisi 5 huruf di dalam kata sebagai 5 buah kotak. Kotak pertama dapat diisi dengan salah satu dari 5 huruf (jadi, ada 5 cara). Kotak kedua dapat diisi dengan 4 cara (karena 1 huruf sudah dipakai untuk kotak pertama). Kotak ketiga dapat diisi dengan 3 huruf (karena 2 huruf lain sudah dipakai untuk kotak pertama dan kedua). Kota keempat dapat diisi dengan 2 cara dan kotak kelima dapat diisi dengan 1 cara.

5 cara                        4 cara                        3 cara                        2 cara                        1 cara

_____                       _____                        _____                        _____                        _____

Karena setiap kotak harus diisi dengan 1 huruf (kotak 1 dan kotak 2 dan kotak 3 dan kotak 4 dan kotak 5), maka kita menggunakan kaidah perkalian. Jumlah kata yang dapat dibentuk adalah 5 x 4 x 3 x 2 x 1 = 120 cara.

(a)  Berapa banyak jumlah kata yang terdiri dari 5 huruf yang dapat dibentuk dari huruf-huruf a,b,c,d,e jika pengulangan huruf diperbolehkan

Jika pengulangan huruf dibolehkan di dalam kata, maka setiap kotak dapat diisi dengan 5 cara. Maka jumlah kata yang dapat disusun adalah 5 x 5 x 5 x 5 x 5 = 55 = 3125 cara.

(b) Berapa banyak jumlah kata pada jawaban soal (a) yang diawali oleh huruf b ?

Kotak 1 hanya dapat diisi dengan 1 cara (yaitu huruf b). Kotak kedua 4 cara (selain huruf b), kotak ketiga 3 cara, kotak keempat 2 cara, dan kotak kelima 1 cara. Maka jumlah kata yang dapat disusun adalah 1 x 4 x 3 x 2 x 1 = 24 cara.

(c)  Berapa banyak jumlah kata pada jawaban soal (a) yang tidak diawali oleh huruf b ?

Kotak 1 hanya dapat diisi dengan 4 cara (selain huruf b). Kotak kedua 4 cara (1 huruf sudah dipakai untuk kotak pertama, tersisa 4 huruf, termasuk huruf b), kotak ketiga 3 cara, kotak keempat 2 cara, dan kotak kelima 1 cara. Maka, jumlah kata yang dapat disusun adalah 4 x 4 x 3 x 2 x 1 = 96.

Contoh 9 :

Sebuah perpustakaan memiliki 6 buah buku berbahasa Inggris, 8 buah buku berbahasa Prancis, dan 10 buah buku berbahasa Jerman. Masing-masing buku berbeda judulnya. Berapa jumlah cara memilih :

(a)  3 buah buku, masing-masing dari tiap bahasa berbeda

(b) 1 buah buku (sembarang bahasa)

Penyelesaian :

(a)  Jumlah cara memilih 3 buah buku, masing-masing dari tiap bahasa adalah (6)(8)(10) = 480 cara

(b) Jumlah cara memilih 1 buah buku (sembarang bahasa) = 6 + 8 + 10 = 24 cara