Kombinatorial

Kombinatorial

Kombinatorial 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.

Contoh :

1.      Misalkan nomor plat mobil di kota Manchester terdiri atas 5 angka diikuti dengan 2 huruf. Angka pertama tidak boleh 0.

Berapa banyak nomor plat mobil yang dapat dibuat ?

2.      Password sistem komputer panjangnya enam sampai delapan karakter. Tiap karakter boleh berupa huruf atau angka. Huruf besar dan huruf kecil tidak dibedakan.

Berapa banyak password yang dapat dibuat ?

Cara yang paling sederhana untuk menyelesaikan persoalan semacam di atas adalah dengan mengenumerasikan semua kemungkinan jawabannya.

Mengenumerasi artinya mencacah atau menghitung (count) satu persatu setiap kemungkinan jawaban.

Untuk persoalan dengan jumlah objek sedikit, mengenumerasi setiap kemungkinan jawaban masih dapat dilakukan, tetapi untuk persoalan dengan jumlah objek yang banyak, cara enumerasi akan sangat susah dilakukan.

Misalnya untuk contoh pertama di atas, bila kita mengenumerasi semua kemungkinan jawabannya adalah seperti di bawah ini :

                12345AB

            12345AC

            12345BC

            .......

            34567MT

            34567ML

            .......

            dan seterusnya.....                                          

Mungkin kita sudah lelah sebelum usaha mengenumerasi semua kemungkinan nomor plat mobil selesai, karena nomor plat mobil yang dibentuk sangat banyak.

Disinilah peran kombinatorial, yang merupakan “seni berhitung” menyelesaikan persoalan di atas dengan cepat.

1.1.     Percobaan

Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan.

Percobaan adalah proses fisik yang hasilnya dapat diamati.

Contoh :

1.      Melempar dadu

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

2.      Melempar koin uang Rp. 1.000

Hasil percobaan melempar koin 1000 ada dua kemungkinan : muka koin yang bergambar bima atau muka koin yang bergambar spiderman.

3.      Memilih lima orang wakil dari 100 orang mahasiswa

Hasil yang diperoleh adalah perwakilan yang beranggotakan lima orang mahasiswa, Kemungkinan perwakilan yang dibentuk banyak sekali.

4.      Menyusun jumlah kata yang panjangnya 5 huruf yang dapat bentuk 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, acded, cbade, ...dan seterusnya

1.2.     Kaidah Dasar Menghitung

Dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatorial adalah kaidah perkalian (rule of product) dan kaidah penjumlahan (rule of sum).

1.      Kaidah Perkalian (rule of product)

Percobaan 1 mempunyai p hasil percobaan yang mungkin terjadi (atau menghasilkan p kemungkinan jawaban)

Percobaan 2 mempunyai q hasil percobaan yang mungkin terjadi (atau menghasilkan q kemungkinan jawaban)

Bila percobaan 1 dan percobaan 2 dilakukan, maka terdapat p x q hasil percobaan (atau menghasilkan p x q kemungkinan jawaban).

2.      Kaidah Penjumlahan (rule of sum)

Percobaan 1 mempunyai p hasil percobaan yang mungkin terjadi (atau menghasilkan p kemungkinan jawaban)

Percobaan 2 mempunyai q hasil percobaan yang mungkin terjadi (atau menghasilkan q kemungkinan jawaban)

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

Perhatikanlah kata yang digarisbawahi pada kedua di atas, dan serta atau.

Kedua kata ini adalah kata kunci untuk mengidentifikasi apakah suatu persoalan menghitung diselesaikan dengan kaidah perkalian atau penjumlahan.

Kaidah perkalian menyatakan bahwa kedua percobaan dilakukan secara simultan atau serempak

Sedangkan pada kaidah penjumlahan menyatakan bahwa kedua percobaan dilakukan tidak simultan.

Contoh 1 :

Sebuah restoran menyediakan lima jenis makanan, misalnya nasi goreng pete, roti bakar tutung, soto ayam matang, sate kambing guling dan sop kaki rusa, serta tiga jenis minuman, misalnya susu soda kental, kopi hitam tubruk, dan teh botol sosro.

Jika setiap orang boleh memesan satu makanan dan satu minuman, berapa banyak pasangan makanan dan minuman yang dapat dipesan.

Penyelesaian :

kita mengenumerasi semua kemungkinan pasangan makanan dan minuman yang dapat dipesan, yaitu;

nasi goreng pete dan susu soda kental	Roti bakar tutung dan susu soda kental	soto ayam matang dan susu soda kental	sate kambing guling dan susu soda kental	sop kaki rusa dan susu soda kental
nasi goreng pete dan kopi hitam tubruk	roti bakar tutung dan kopi hitam tubruk	soto ayam matang dan kopi hitam tubruk	sate kambing guling dan kopi hitam tubruk	sop kaki rusa dan kopi hitam tubruk
nasi goreng pete dan teh botol sosro	roti bakar tutung dan teh botol sosro	soto ayam matang dan teh botol sosro	sate kambing guling dan teh botol sosro	sop kaki rusa dan teh botol sosro

Semuanya ada 15 pasang.

Dalam kombinatorial, kita memandang bahwa dalam kejadian ini orang harus memilih makanan dan minuman.

Ada 5 kemungkinan memilih makanan, yaitu nasi goreng pete, roti bakar tutung, soto ayam matang, sate kambing guling dan sop kaki rusa.

Ada 3 kemungkinan memilih minuman, yaitu susu soda kental, kopi hitam tubruk dan teh botol sosro.

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 tahun 2011 atau angkatan tahun 2012.

Jika terdapat 45 orang mahasiswa angkatan 2011 dan 52 orang mahasiswa angkatan 2012, 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 2011, dan 52 cara memilih satu orang dari angkatan 2012, namun hanya satu dari kedua angkatan itu yang terpilih (angkatan 2011 atau angkatan 2012).

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 memilih 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 :

Misalkan himpunan A = {a, b,c, d, e} dan himpunan B = {1, 2, 3}.

Berapa banyak pasangan terurut yang dapat dibentuk antara anggota himpunan A dengan anggota himpunan B (yaitu A x B) ?

Penyelesaian :

Nyatakan pasangan terurut sebagai (a, b) yang dalam hal ini a Î A dan b Î B.

Karena anggota himpunan A yang mungkin menjadi elemen pertama pasangan ada 5 buah dan anggota himpunan B yang mungkin menjadi elemen kedua pasangan ada 3 buah, maka banyaknya pasangan yang dapat terbentuk adalah 5 x 3 = 15, yang merupakan jumlah elemen himpunan hasil operasi A x B (cartesian product)

Contoh 6 :

Kursi-kursi di dalam ruang 101 akan diberi nomor dengan sebuah huruf diikuti dengan bilangan bulat positif yang tidak lebih dari 50 (misalnya A12, B36, dan seterusnya).

Berapa jumlah maksimum kursi yang dapat dinomori ?

Penyelesaian :

Ada 26 kemungkinan memilih huruf alfabet untuk nomor kursi dan 50 kemungkinan bilangan bulat positif yang dapat digunakan. Huruf alfabet 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 7 :

Terdapat empat rute yang dapat dilalui kendaraan dari Jakarta ke Cirebon, dan tiga rute dari Cirebon ke Yogya.

(a)         Berapa banyak cara Wellbeck bepergian dengan kendaraan dari Jakarta ke Yogya melalui Cirebon ?

(b)         Berapa banyak cara Wellbeck bepergian pulang-pergi dengan kendaraan dari Jakarta ke Yogya melalui Cirebon ?

Penyelesaian :

(a)         Wellbeck dari Jakarta ke Yogya harus melewati rute Jakarta-Cirebon dan rute Cirebon-Yogya. Ada 4 piihan rute dari Jakarta ke Cirebon dan 3 pilihan rute dari Cirebon ke Yogya, sehingga jumlah pilihan rute dari Jakarta ke Yogya via Cirebon adalah 4 x 3 = 12.

(b)           Ada 12 rute dari Jakarta ke Yogya via Cirebon dan 12 rute dari Yogya ke Jakarta via Cirebon. Karena perjalanan pulang-pergi (Jakarta-Yogya dan Yogya-Jakarta), maka jumlah pilihan rute seluruhnya adalah 12 x 12 = 144 cara untuk berkendaraan pulang-pergi.

(c)            

1.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 p₁, p₂, ...., p_n,  hasil percobaan yang mungkin terjadi yang dalam hal ini setiap p_i tidak bergantung pada pilihan sebelumnya, maka jumlah hasil percobaan yang mungkin terjadi adalah :

(a)   p₁ x p₂ x .... x p_n untuk kaidah perkalian

(b)   p₁ + p₂ + .... + p_n untuk kaidah penjumlahan

Contoh 1 :

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

Di sini 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) (2)  = 2¹⁰

Contoh 2 :

(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 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.

(a)         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 huruf (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).

-         Kotak keempat dapat diisi dengan 2 huruf dan kotak kelima dapat diisi dengan 1 huruf.

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.

(b)         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 = 5⁵ = 3125

(c)         Kotak 1 hanya dapat diisi dengan 1 cara (yaitu huruf a). Kotak kedua 4 cara (selain huruf a), 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

(d)         Kotak 1 hanya dapat diisi dengan 4 cara (Selain huruf a). Kotak kedua 4 cara (1 huruf sudah dipakai untuk kotak pertama, tersisa 4 huruf, termasuk huruf a), 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 3 :

Perpustakaan STIKOM memiliki 6 buah buku berbahasa Inggris, 8 buah buku berbahasa Perancis, 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