Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.
Sebuah sandi-lewat (password) panjangnya 6 sampai 8 karakter.
Karakterboleh berupa huruf atau angka. Berapa banyak kemungkinan sandi-leawt
yang dapat dibuat?
abcdef
aaaade
a123fr
… erhtgahn
yutresik
…
????
Kaidah Dasar Menghitung
1. Kaidah perkalian (rule of product)
Misalkan,
Percobaan 1: p hasil
Percobaan 2: q hasil
maka,
Percobaan 1 dan percobaan 2: p q hasil
2. Kaidah penjumlahan (rule of sum)
Misalkan,
Percobaan 1: p hasil
Percobaan 2: q hasil
maka,
Percobaan 1 atau percobaan 2: p + q hasil
Perluasan Kaidah Dasar Menghitung
Misalkan ada n percobaan, masing-masing dg pi hasil
1. Kaidah perkalian (rule of product)
p1 x p2 x …x pn hasil
2. Kaidah penjumlahan (rule of sum)
p1 + p2 +…+ pn hasil
Prinsip Inklusi-Eksklusi
Setiap byte disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan ‘11’ atau berakhir dengan ‘11’?
Penyelesaian:
Misalkan
A = himpunan byte yang dimulai dengan ‘11’,
B = himpunan byte yang diakhiri dengan ‘11’
A /\ B = himpunan byte yang berawal dan berakhir dengan ‘11’
Permutasi
Definisi: Permutasi adalah jumlah urutan berbeda dari pengaturan objek objek.
Permutasi merupakan bentuk khusus aplikasi kaidah perkalian.
Misalkan jumlah objek adalah n, maka
urutan pertama dipilih dari n objek,
urutan kedua dipilih dari n – 1 objek,
urutan ketiga dipilih dari n – 2 objek,
…
urutan terakhir dipilih dari 1 objek yang tersisa.
Menurut kaidah perkalian, permutasi dari n objek adalah
n(n – 1) (n – 2)…(2)(1) = n!
Kombinasi (Combination)
Bentuk khusus dari permutasi adalah kombinasi. Jika pada permutasi
urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan.
Misalkan ada 2 buah bola yang warnanya sama 3 buah kotak. Setiap
kotak hanya boleh berisi paling banyak 1 bola.
EmoticonEmoticon