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.

Contoh :
Misalkan nomor plat mobil di Negara X terdiri atas 5 angka diikuti dengan 2 huruf. Angka pertama tidak boleh 0. Berapa banyak nomor plat mobil yang dapat dibuat?
Password sistem komputer panjangnya enam sampai delapan karakter. Tiap karakter boleh berupa huruf atau angka; huruf besar dan kecil tidak dibedakan. Berapa banyak password yang dapat dibuat?

Untuk menyelesaikan persoalan di atas yaitu dengan mengenumerasi semua kemungkinan jawabannya.

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

Untuk persoalan dengan objek sedikit, mengenumerasi setiap kemungkinan jawaban masih dapat dilakukan, tetapi untuk persoalan dengan jumlah objek yang banyak, cara enumerasi jelas imposible bangeut…untuk dilakukan.

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

12345AB
12345AC
12345BC
….
34567MC
34567MK
….
dan seterusnya…

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

Disinilah dibutuhkan seorang penolong yang namanya kombinatorial, yang merupakan “seni berhitung”, menyelesaikan persoalan semacam ini dengan cepat.

Kombinatorial dapat digunakan untuk menjawab persoalan semacam ini tanpa perlu kita mengenumerasi semua kemungkinan jawabannya.


Percobaan

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

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

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

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.

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.



Kaidah Dasar Menghitung

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

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

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

Kursi-kursi di dalam ruang aula 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.
Berapa banyak cara si Teguh bepergian dengan kendaraan dari Bandung ke Surabaya melalui Cirebon?
Berapa banyak cara si Udin bepergian pulang-pergi dengan kendaraan dari Bandung ke Surabaya melalui Cirebon ?

Penyelesaian :

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.

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.


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 :

p1 x p2 x … x pn untuk kaidah perkalian
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) (2) = 210




Contoh 8 :

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

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

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

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.

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.
Berapa banyak jumlah kata pada jawaban soal (a) yang diawali oleh huruf a ?

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

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

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), kota 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 :
3 buah buku, masing-masing dari tiap bahasa berbeda
1 buah buku (sembarang bahasa)

Penyelesaian :

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


Contoh 10 :

Password pada 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 ?

Penyelesaian :

Banyaknya huruf alphabet adalah 26 (A-Z) dan banyak angka desimal adalah 10 (0-9), jadi seluruhnya 36 karakter. Masing-masing huruf atau angka dapat menjadi pilihan untuk posisi karakter di dalam password.

Untuk password dengan panjang 6 karakter, jumlah kemungkinan password adalah :

(36) (36) (36) (36) (36) (36) = 366 = 2.176.782.336

Untuk password dengan panjang 7 karakter, jumlah kemungkinan password adalah :

(36) (36) (36) (36) (36) (36) (36) = 367 = 78.364.164.096

Untuk password dengan panjang 8 karakter, jumlah kemungkinan password adalah :

(36) (36) (36) (36) (36) (36) (36) (36) = 368 = 2.821.109.907.456

Dengan menggunakan kaidah penjumlahan, jumlah seluruh password adalah
+ 78.364.164.096 + 2.821.109.907.456 = 2.901.650.833.888 cara


Permutasi

Langsung aja ya ke contoh :

Misalkan ada tiga buah bola yang berbeda warnanya, yaitu merah (m), biru (b) dan putih (p). Kita akan memasukkan ketiga buah bola itu ke dalam tiga buah kotak, masing-masing kotak 1 buah bola. Berapa jumlah urutan berbeda yang mungkin dibuat dari penempatan bola ke dalam kotak-kotak tersebut ?

Penyelesaian :

Kemungkinan urutan berbeda dari penempatan bola ke dalam tiga buah kotak ada enam buah, yaitu mbp, mpb, bmp, bpm, pmb, dan pbm. Semua urutan berbeda tersebut dinamakan Permutasi.

Permutasi adalah jumlah urutan berbeda dari pengaturan objek-objek.

Menurut kaidah perkalian, permutasi dari n objek adalah :

N(n-1)(n-2) … (2)(1) = n!

Sekarang misalkan ada enam buah bola yang berbeda warnanya, yaitu merah (m), biru (b), putih (p), hijau (h), kuning (k), dan jingga (j). Kita akan memasukkan keenam buah bola itu ke dalam tiga buah kotak, masing-masing kotak hanya boleh diisi 1 buah bola. Berapa jumlah urutan berbeda yang mungkin dibuat dari penempatan bola ke dalam kotak-kotak tersebut ?

Perhitungannya adalah sebagai berikut :

Kotak 1 dapat diisi oleh salah satu dari 6 bola (ada 6 pilihan);
Kotak 2 dapat diisi oleh salah satu dari 5 bola (ada 5 pilihan);
Kotak 3 dapat diisi oleh salah satu dari 4 bola (ada 4 pilihan).

Menurut kaidah perkalian, jumlah urutan berbeda dari penempatan bola = (6)(5)(4) = 120 buah

Dan kalau menurut kaidah perkalian, ada sebanyak

N(n-1)(n-2) … (n-(r-1))

buah susunan berbeda dari penyusunan r objek yang dipilih dari n objek. Jumlah susunan berbeda dari pemilihan r objek yang diambil dari n objek disebut permutasi-r, dilambangkan dengan P(n,r), yaitu :

P(n,r) = n(n-1)(n-2) … (n-(r-1)) = n!/(n-r)!


Maka dari rumus di atas, jumlah cara memasukkan 6 buah bola yang berbeda warnanya ke dalam 3 buah kotak adalah P(6,3) = 6! / (6-3)! = 120 cara.


Contoh 11 :

Berapa banyak “kata” yang terbentuk dari kata “PERSIB” ?

Penyelesaian :

Anggap setiap huruf di dalam kata “PERSIB” sebagai bola yang berbeda warnanya, dan 6 buah kotak yang akan diisi dengan 1 bola pada setiap kotak.
Cara 1: (6)(5)(4)(3)(2)(1) = 720 buah kata
Cara 2: P(6,6) = 6! = 720 buah kata



Contoh 12 :

Berapa banyak cara mengurutkan nama 25 orang mahasiswa ?

Penyelesaian :

Analogikan dengan mengisi 25 kotak dengan 25 bola berbeda, setiap kotak diisi dengan 1 bola. So…jumlah cara pengurutan nama mahasiswa sama dengan jumlah susunan 25 bola ke dalam 25 kotak, yaitu P(25,25) = 25! ….berapa yach..


Contoh 13 :

Tiga buah ujian dilakukan dalam suatu periode enam hari (senin sampai sabtu). Berapa banyak pengaturan jadual yang dapat dilakukan sehingga tidak ada dua ujian atau lebih yang dilakukan pada hari yang sama.

Penyelesaian :

Cara 1 (dengan kaidah perkalian) : sama seperti menempatkan 3 bola (ujian) berbeda ke dalam enam kotak (hari).
Ujian pertama dapat ditempatkan pada salah satu dari enam hari
Ujian kedua dapat ditempatkan pada salah satu dari lima hari
Ujian ketiga dapat ditempatkan pada salah satu dari empat hari
Maka jumlah pengaturan jadual ujian = (6)(5)(4) = 120 cara pengaturan

Cara 2 (dengan rumus permutasi) : P(6,3) = 6! / (6-3)! = 120 cara pengaturan












Contoh 14 :

Sebuah bioskop mempunyai jajaran kursi yang disusun per baris. Tiap baris terdiri dari 6 tempat kursi. Jika dua orang akan duduk, berapa banyak pengaturan tempat duduk yang mungkin pada suatu baris ?

Penyelesaian :

Orang pertama mempunyai 6 pilihan kursi, dan orang kedua mempunyai 5 pilihan kursi. Jadi jumlah pengaturan tempat duduk = (6)(5) = 30 atau P(6,2) = 6! / 4! = (6)(5) = 30 cara


Contoh 15 :

Berapa banyak kata yang dapat dibentuk yang terdiri dari 4 huruf berbeda dan diikuti dengan 3 angka yang berbeda pula ?

Penyelesaian :

Ada P(26,4) cara mengisi posisi 4 huruf dan P(10,3) cara untuk mengisi posisi 3 buah angka. Karena kata disusun oleh 4 huruf dan 3 angka, maka jumlah kata yang dapat dibuat adalah P(26,4) x P(10,3) = 258.336.000


Permutasi Melingkar

Langsung juga ya..ke contoh :

Misalkan ada 10 orang yang duduk pada satu barisan kursi yang terdiri dari 10 kursi. Menurut rumus permutasi, ada sebanyak P(10,10) = 10! cara pengaturan tempat duduk bagi 10 orang tersebut.

Sekarang, misalkan mereka teh..disuruh duduk mengelilingi meja melingkar. Berapa banyak cara pengaturan tempat duduk bagi mereka tersebut ?

Penyelesaian :

Satu orang dapat duduk pada tempat duduk dimana saja. Sembilan orang lainnya dapat duduk dalam 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 9! Cara.

Meskipun orang pertama dapat memilih tempat duduk dimana saja, namun susunan tempat duduk yang dihasilkan oleh 9 orang lainnya tetap sama. Ini dinamakan Permutasi Melingkar.

Definisi Permutasi Melingkar :

Permutasi Melingkar dari n objek adalah penyusunan objek-objek yang mengelilingi sebuah lingkaran (atau kurva tertutup sederhana). Jumlah susunan objek yang mengelilingi lingkaran adalah (n-1)!

Pembuktian permutasi melingkar cukup sederhana : objek pertama dapat ditempatkan dimana saja dalam lingkaran dengan 1 cara. Sisa n-1 objek lainnya dapat diatur searah jarum jam dengan P(n-1, n-1) = (n-1)! cara.

Malcolm Baldridge National Quality

ABSTRAK

Teknologi Informasi (TI) memiliki peranan penting bagi perusahaan sebagai salah satu faktor dalam mencapai tujuan perusahaan. Peran TI akan optimal jika penerapan TI dikelola dengan baik. Pengelolaan yang baik dapat dipastikan dengan menilai kesesuaian antara penerapan TI dengan kebutuhan bisnis perusahaan. Untuk mewujudkan kesesuaian tersebut, kita dapat menerapkan Information Technology (IT) Governance.
Pengelolaan teknologi informasi adalah suatu langkah dalam memastikan secara terus menerus adanya control objective dari pemanfaatan teknologi informasi di perusahaan.
Terdapat beberapa standar dalam peningkatan kualitas mutu total, salah satu diantaranya yaitu standar Malcolm Baldridge National Quality (MBNQ).
Analisis dalam penelitian ini mengacu kepada standar COBIT (Control Objectives for Information and related Technology). COBIT framework sebagai perangkat yang sangat baik dalam mengontrol informasi TI dan resiko-resiko terkait TI.
Penerapan standar MBNQ dengan menggunakan pengukuran COBIT pada domain Acquisition and Implementation (AI) dan Monitoring (M) diharapkan menghasilkan kebijakan pengelolaan teknologi informasi guna memaksimalkan pemanfaatan teknologi informasi di institusi/organisasi.
Pengintegrasian IT Governance menggunakan pengukuran COBIT dengan framework MBNQ menghasilkan suatu model keterhubungan elemen dasar framework MBNQ dalam aktifitas TI organisasi khususnya pendidikan yang sekaligus dapat dibuatkan pencapaian mutu kualitas pendidikan. Pencapaian mutu kualitas pendidikan tersebut mengambil studi kasus di ITB.
Hasil dari pencapaian mutu kualitas pendidikan dijadikan acuan bagi pemetaan antara proses-proses TI dalam domain COBIT dengan tujuh kriteria layanan TI framework MBNQ.
Hasil penelitian berupa usulan kebijakan pengelolaan teknologi informasi di lingkungan ITB yang pada penerapannya harus dilakukan secara bertahap disesuaikan dengan kondisi yang ada pada organisasi ITB.
Kebijakan IT Governance yang diusulkan di ITB adalah untuk memperbaiki atau menyempurnakan kondisi yang ada agar dapat mencapai target tingkat kematangan yang diinginkan.
Kata Kunci : IT Governance, COBIT, Framework MBNQ, Kebijakan Pengelolaan Teknologi Informasi, Studi Kasus.