Kombinatorial Dan Peluang Diskrit
1. Teori Kombinatorial
Teori
Kombinatorial merupakan salah satu pokok bahasan Matematika Diskrit yang telah
banyak dikembangkan dan diaplikasikan dalam berbagai bidang. Kombinatorial juga
merupakan cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa
harus mengenumerasi semua kemungkinan susunannya. Dalam perkembangan
Matematika, dapat dilihat bahwa kajian kombinatorial sangat menarik bagi
sebagian orang. Salah satu contoh permasalahan yang dapat diselesaikan
dengan kombinatorial adalah menghitung banyaknya kombinasi karakter password.
Contoh
Sebuah
password panjangnya 6 sampai 8 karakter. Karakter boleh berupa huruf atau
angka. Berapa banyak kemungkinan password yang dapat dibuat?
Penyelesaian:
-
Abcdef
-
aaaade
-
a123f
-
erhtgahn
-
Yutresik
-
…
dan seterusnya…
Sangatlah
mungkin bahwa kita sudah lelah sebelum proses enumerasi selesai dilakukan. Di
sinilah peran kombinatorial, yang merupakan “seni berhitung”, menyelesaikan
persoalan semacam ini dengan cepat.
2. Prinsip Dasar Menghitung
A. Prinsip Penjumlahan (rule of sum)
Jika
suatu himpunan A terbagi kedalam himpunan bagian A1, A2, …, An, maka jumlah
unsur pada himpunan A akan sama dengan jumlah semua unsur yang ada pada setiap
himpunan bagian A1, A2, …,An. Setiap himpunan bagian A1, A2, …, An tidak
saling tumpang tindih (saling lepas).
Untuk
himpunan yang saling tumpang tindih tidak berlaku lagi prinsip penjumlahan, dan
ini harus diselesaikan dengan prinsip inklusi-eksklusi.
Misalkan,
Percobaan
1 : p
hasil
Percobaan
2 : q hasil
maka,
Percobaan 1 atau percobaan 2: p + q hasil
Contoh
Jika
Ketua kelas hanya 1 orang (pria atau wanita). Jumlah pria di kelas adalah 25
orang dan jumlah wanita adalah 15 orang.Berapa banyak cara memilih ketua kelas?
Penyelesaian:
25 + 15 = 40 cara.
B. Prinsip
Perkalian (rule of product)
Misalkan
sebuah prosedur dapat dipecah dalam dua penugasan. Penugasan pertama dapat
dilakukan dalam n1 cara, dan tugas kedua dapat dilakukan dalam n2 cara setelah
tugas pertama dilakukan.
Dengan
demikian, dalam mengerjakan prosedur tersebut ada (n1 x n2) cara. Secara tidak
langsung, pada prinsip perkalian, bisa terjadi saling tumpang tindih (tidak
saling lepas).
Misalkan,
Percobaan
1: p hasil
Percobaan 2: q hasil
maka, Percobaan 1 dan percobaan
2: p x q hasil
Contoh
Jumlah
mahasiswa laki-laki kelas 2. F adalah 31 orang sedangkan jumlah wanitanya hanya
4 orang. Untuk memilih wakil 1 orang pria dan 1 orang wanita. Berapa banyak
cara memilih 2 orang wakil tersebut?
Penyelesaian:
31 x 4 = 124 cara.
3. Prinsip Inklusi Dan Eksklusi
Misalkan A dan B sembarang himpunan, Penjumlahan
|A|+|B| menghitung banyaknya elemen A yang tidak terdapat di B dan banyakan
elemen B tidak terdapat di A dan banyaknya elemen yg terdapat di A ∩ B.
Oleh Karna itu, pengurangan banyaknya elemen yg terdapat A
∩ B dari |A|+|B| membuat banyaknya elemen A є B dihitung tepat
satu kali, Dengan demikian
|A
u B|= |A|+|B|-|A ∩ B|
Generalisasi dari hal tersebut bagi gabungan dari sejumlah
himpunan dinamakan prinsip inklusi dan eksklusi.
Contoh
Dalam sebuah kelas terdapat 29 mahasiswa yang menyukai
matematika diskrit, 17 mahasiswa menyukai aljabar linear dan 11 orang
diantaranya menyukai keduanya, Berapa mahasiswa terdapat dalam kelas tersebut ?
Penyelesaian
;
Misal: A = mahasiswa yg
menyukai matematika diskrit
B
= mahasiswa yg menyukai aljabar linear
Menurut data yg ada ;
|A|=29 ; |B|=17 ; |A ∩ B|= 11
|A u B|= |A|+|B|-|A ∩ B|
=
29 + 17 – 11 = 35
4. Permutasi
Permutasi merupakan susunan yang mungkin dibuat dengan
memperhatikan urutan. Dengan kata lain, permutasi merupakan bentuk khusus
aplikasi prinsip perkalian.
Menurut kaidah perkalian, permutasi dari n
objek adalah n(n – 1)(n – 2) … (2)(1) = n!
Rumus permutasi-r (jumlah susunan berbeda dari pemilihan r objek yang diambil
dari n objek), dilambangkan dengan P (n,r):
A. Permutasi Dengan Pengulangan
Banyaknya permutasi dari n objek dari n1 yang sama, n2 yang
sama,……, nr yang sama
Contoh
Tentukan banyaknya kata yang dapat dibentukdari kata
“DISKRIT”.
Penyelesaian:
n=7 ; n1 = 2 (huruf I
yang sama, jumlahnya = 2)
Banyaknya
kata yang dapat dibentuk dari kata“DISKRIT” = n!/n1! = 7!/2! = 2520 Kata.
5. Kombinasi
Bentuk khusus dari
permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan
diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan. Rumus kombinasi-r (jumlah
pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen),
dilambangkan dengan C(n,r) atau ( n r ) .
A.
Interpretasi
Kombinasi
a. C(n, r) = banyaknya himpunan bagian yang terdiri
atas r elemen yang dapat dibentuk dari himpunan dengan n elemen.
b. C(n, r) = cara memilih r buah elemen dari n
elemen yang ada, tetapi urutan elemen di dalam susunan hasil pemilihan tidak penting.
Contoh
Misalkan A = {1, 2, 3}
Jumlah Himpunan bagian dengan 2
elemen:
{1, 2} = {2, 1}
{1, 3} = {3,
1} 3
buah atau
{2,
3} = {3, 2}
6.
Peluang
A. Teori Peluang
Kombinatorial dan teori peluang (probability) berkaitan
sangat erat. Teori peluang banyak menggunakan konsep-konsep dalam
kombinatorial. Sebenarnya kedua bidang ini lahir dari arena judi (gambling
games) – salah satu kasusnya adalah menghitung peluang munculnya nomor lotre
tertentu. Meskipun demikian, aplikasi kombinatorial dan teori peluang saat ini
telah meluas ke berbagai bidang ilmu lain maupun dalam kehidupan nyata seperti
ilmu statistika, fisika, ekonomi, biologi, dan berbagai bidang ilmu lainnya.
B. Ruang Contoh (sample space)
Ruang Contoh dari suatu percobaan adalah himpunan semua kemungkinan
hasil percobaan yang bersangkutan.
C. Titik Contoh (sample point)
Titik Contoh adalah setiap hasil percobaan di dalam ruang
contoh. Hasil-hasil percobaan tersebut bersifat saling terpisah (mutually
exclusive) karena dari seluruh ruang contoh, hanya satu titik contoh yang
muncul.
D. Ruang Contoh Diskrit (discrete sample space)
Ruang Contoh Diskrit adalah ruang contoh yang jumlah
anggotanya terbatas. Misalkan ruang contoh dilambangkan dengan S dan
titik-titik contohnya dilambangkan dengan x1, x2, …, maka
S = { x1, x2, …, xi, … }Menyatakan ruang contoh S yang
terdiri atas titik-titik contoh x1, x2, …, xi, dan seterusnya.
E. Peluang Diskrit
Peluang
Diskrit adalah peluang terjadinya sebuah titik contoh, dan disimbolkan dengan
p(xi).
Kejadian (event)
Kejadian –disimbolkan dengan E– adalah himpunan bagian dari
ruang contoh. Misalnya pada percobaan melempar dadu, kejadian munculnya angka
ganjil adalah E = {1,3,5}, kejadian munculnya angka 1 adalah E = {1}.
Kejadian yang hanya mengandung satu titik contoh disebut
kejadian sederhana (simple event), sedangkan kejadian yang mengandung lebih
dari satu titik contoh disebut kejadian majemuk (compound event).
F. Peluang Kejadian
Peluang
Kejadian E di dalam ruang contoh S dapat diartikan sebagai jumlah peluang semua
titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa
Sebuah koin yang mempunyai sisi A dan sisi B di
lempar keatas sebanyak 4 (empat) kali.
Berapakah jumlah kemungkinan munculnya sisi A sebanyak 3(tiga) kali?
Penyelesaian:
Munculnya sisi A sebanyak 3 (tiga) kali
adalah C (4, 3) = 4
Jumlah seluruh hasil percobaan adalah
2x2x2x2 = 16,
sehingga peluang munculnya sisi A
sebanyak 3 kali adalah 4/16 = 1/4
Sumber :
https://www.academia.edu/11795682/Matdis_Kombinatorial_dan_peluang_diskrit
