Kombinatorial - Matematika Diskrit TI 16-B

Definisi
Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.



Kaidah Dasar Menghitung
Kaidah perkalian (rule of product)
Percobaan 1: p hasil
Percobaan 2: q hasil
  Percobaan 1 dan percobaan 2: p  q hasil

Kaidah penjumlahan (rule of sum)
Percobaan 1: p hasil
Percobaan 2: q hasil
  Percobaan 1 atau percobaan 2: p + q hasil

Contoh 1. Ketua angkatan IF 2002 hanya 1 orang (pria atau wanita, tidak bias gender). Jumlah pria IF2002 = 65 orang dan jumlah wanita = 15 orang. Berapa banyak cara memilih ketua angkatan?

Penyelesaian: 65 + 15 = 80 cara.


Contoh 2. Dua orang perwakilan IF2002 mendatangai Bapak Dosen untuk protes nilai ujian. Wakil yang dipilih 1 orang pria dan 1 orang wanita. Berapa banyak cara memilih 2 orang wakil tesrebut?

Penyelesaian: 65 x 15 =  975 cara.

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

Contoh 3. Bit biner hanya 0 dan 1. Berapa banyak string biner yang dapat dibentuk jika:
(a) panjang string 5 bit
(b) panjang string 8 bit (= 1 byte)
Penyelesaian:
(a) 2 x 2 x 2 x 2 x 2 = 25 = 32 buah
(b) 28 = 256 buah

Contoh 4. Berapa banyak bilangan ganjil antara 1000 dan 9999 (termasuk 1000 dan 9999 itu sendiri) yang
(a) semua angkanya berbeda
(b) boleh ada angka yang berulang.

Penyelesaian:
(a) posisi satuan:   5 kemungkinan angka (1, 3, 5, 7, 9)
posisi ribuan:   8 kemungkinan angka
posisi ratusan:  8 kemungkinan angka
posisi puluhan: 7 kemungkinan angka
Banyak bilangan ganjil seluruhnya = (5)(8)(8)(7) = 2240 buah.

b) posisi satuan:   5 kemungkinan angka (yaitu 1, 3, 5, 7 dan 9);
posisi ribuan:   9 kemungkinan angka (1 sampai 9)
posisi ratusan:  10 kemungkinan angka (0 sampai 9)
posisi puluhan: 10 kemungkinan angka (0 sampai 9)
  Banyak bilangan ganjil seluruhnya = (5)(9)(10)(10) = 4500

Contoh 5. Sandi-lewat (password) sistem komputer  panjangnya 6 sampai 8 karakter. Tiap karakter boleh berupa huruf atau angka; huruf besar dan huruf kecil tidak dibedakan. Berapa banyak sandi-lewat  yang dapat dibuat?
Penyelesaian:
Jumlah karakter password = 26 (A-Z) + 10 (0-9) = 36 karakter.

Jumlah kemungkinan sandi-lewat dengan panjang 6 karakter: (36)(36)(36)(36)(36)(36) = 366  = 2.176.782.336

Jumlah kemungkinan sandi-lewat dengan panjang 7 karakter: (36)(36)(36)(36)(36)(36)(36) = 367  = 78.364.164.096

umlah kemungkinan sandi-lewat dengan panjang 8 karakter: (36)(36)(36)(36)(36)(36)(36)(36) = 368 = 2.821.109.907.456

Jumlah seluruh sandi-lewat  (kaidah penjumlahan) adalah
  2.176.782.336 + 78.364.164.096 +  2.821.109.907.456 = 2.901.650.833.888 buah.

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’

maka

A È B = himpunan byte yang berawal dengan ‘11’ atau berakhir dengan ‘11’

         ½A½ = 2⁶ = 64,  ½B½ = 2⁶ = 64,    ½A Ç B½ = 2⁴ = 16.

maka

½A È B½ = ½A½ + ½B½ – ½A Ç B½

      = 2⁶ + 2⁶ – 16   = 64 + 64 – 16 = 112.

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!

Contoh 6. Berapa banyak “kata” yang terbentuk dari kata “HAPUS”?
Penyelesaian:
Cara 1: (5)(4)(3)(2)(1) = 120 buah kata
Cara 2: P(5, 5) = 5! = 120 buah kata

Contoh 7. Berapa banyak cara mengurutkan nama 25 orang mahasiswa?
Penyelesaian: P(25, 25) = 25!

Definisi 2. Permutasi r dari n elemen adalah jumlah kemungkinan urutan r buah elemen yang dipilih dari n buah elemen, dengan r  n, yang dalam hal ini, pada setiap kemungkinan urutan tidak ada elemen yang sama.

Contoh 8. Berapakah jumlah kemungkinan membentuk 3 angka dari 5 angka berikut: 1, 2, 3, 4 , 5, jika:
(a) tidak boleh ada pengulangan angka, dan
(b) boleh ada pengulangan angka.

Penyelesaian:
(a) Dengan kaidah perkalian: (5)(4)(3) = 120 buah
Dengan rumus permutasi P(5, 3) = 5!/(5 – 3)! = 120
(b) Tidak dapat diselesaikan dengan rumus permutasi.
Dengan kiadah perkalian:  (5)(5)(5) = 53 = 125.  

Contoh 9. Kode buku di sebuah perpustakaan panjangnya 7 karakter, terdiri dari 4 huruf berbeda dan diikuti dengan 3 angka yang berbeda pula?
Penyelesaian: P(26, 4)  P(10,3) = 258.336.000

SUMBER