6.1. Perluasan Kaidah Menghitung

kaidah perkalian dan kaidah penjumlahan diatas dapat diperluas hingga mengandung lebih dari dua buah percobaan. Jika n buah pecobaan masing- masing mempunyai p_1, p₂,……, p_n  hasil percobaan yang mungkin terjadi yang dalam hal ini  setiap  p₁ 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 6.8

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:

 

Disini kita menggunkan kaidah perkalian, karena kesepuluh kotak ini harus terisi dengan jawaban B atau S (kotak 1 dan kotak 2dan kotak 3 dan …. Dan kotak 10). Jumlah kombinasi jawaban yang dapat di buat:

 

Contoh 6.10

Berapa perpustakaan 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 dan (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

Contoh 6.11

Berapa banyak bilangan ganjil antara 1000 dan 9999 (termasuk 1000 dan 9999 itu sendiri) yang (i) semua angka berbeda, dan (ii) boleng ada angka yang berulang.

Penyelesaian:

i.        Karena yang diminta bilangan ganjil, kita harus memulai dari angka satuan terlebih dahulu, baru kemudian angka ribuan, ratusan, puluhan)

Untuk posisi satuan                  :Ada 5 kemungkinan angka (yaitu 1, 3, 5, 7 dan 9)

Untuk posisi ribuan                 :Ada 8 kemungkinan angka (yaitu 1 sampai 9, kecuali yang sudah dipakai untuk angka satuanà 9 - 1 )

Untuk posisi ratusan               : ada 8 kemungkinan angka (yaitu 0 sampai 9, kecuali dua angka yang sudah dipakai untuk angka satuan dan angka ribuan à 10 - 2 )

Untuk posisi puluhan              : ada 7 kemungkinan angka (yaitu 0 sampai 9, kecuali tiga angka yang sudah dipakai untuk angka satuan, ratusan dan angka ribuanà 10 - 3 )

Banyak bilangan ganjil seluruhnya = (5)(8)(8)(7) = 2240 buah

ii.      Jika perulangan angka dibolehkan, maka untuk posisi satuan tetap ada 5 kemungkinan angka, Ribuan ada 9 kemungkinan (1 sampai 9) Ratusan ada 10 kemungkinan (0 sampai 9) Puluhan ada 10 kemungkinan (0 sampai 9).Banyak bilangan ganjil seluruhnya adalah (5)(9)(10)(10) = 4500 buah.

Contoh 6.12

Berapa nilai k sesudah kode program Pascal berikut dieksekusi?

k : = 0

for p₁ : = 1 to n₁ do

                        k : = k + 1 ;

for p₂ : = 1 to n₂ do

                        k : = k + 1 ;

.

.

for p_m : = 1 to n_m do

                        k : = k + 1 ;

Penyelesaian:

Program di atas memiliki m buah kalang (pengulangan) for. Dieksekusi sebanyak n_i kali. Nilai k selalu ditambah 1 (nilai k pada awalnya 0). Setiap kalang dilaksanakan tidak secara bersamaan, maka nilai k dihitung dgn kaidah penjumlahan.

 Jadi k = n₁ + n₂ + … +n_m.

Contoh 6.13

Berapa nilai k sesudah kode program Pascal berikut dieksekusi?

k : = 0

for p₁ : = 1 to n₁ do

             for p₂ : = 1 to n₂ do

                        .

                        .

             for p_m : = 1 to n_m do

                        k : = k + 1 ;

Penyelesaian:

Program di atas memiliki m buah kalang (pengulangan) for-do bersarang (nested). Dieksekusi sebanyak n_i kali. Nilai k selalu ditambah 1 (nilai k pada awalnya 0). Setiap kalang dilaksanakan  secara bersamaan, maka nilai k dihitung dgn kaidah perkalian.

Jadi, k = n₁ x n₂ x … x n_m.

Contoh 6.14

Salah satu terapan kombinatorial adalah bidang kriptografi. Misalnya pesan-jelas (plaintext) “informatika” dengan menggunakan algoritma kriptografi tertentu disandikan menjadi pesan-tersandi (chipertext) “%r$ht&90dt”. Melalui proses yang berkebalikan, pesan-tersandi dapat dikembalikan menjadi pesan-jelas. Algoritma kripografi DES (Data Encryption Standart) menggunakan kunci (key) untuk menyandikan pesan yang akan dikirim melalui saluran komunikasi. Panjang kunci DES adalah delapan karakter atau 64 bit. Orang yang ingin memmecahkan pesan-tersandi (chipertext) menjadi pesan-jelas (plaintext) harus mencoba seluruh kemungkinan kunci panjangnya 64 bit itu. Berapa banyak kemungkinan kunci yang harus dicoba untuk memecahkan chipertext?

Penyelesaian:

Karena ada 64 posisi pengisian bit yang masing-masing memiliki 2 kemungkinan nilai, 0 atau 1, maka jumlah kombinasi kunci yang harus dicoba adalah :

           

Contoh 6.15

Suatu bilangan dibentuk dari angka-angka 2, 3, 4, 5, 7, 8, dan 9Misalkan pengulangan angka tidak dibolehkan. Berapa banyak bilangan 4 angka yang kurang dari 5000 namun habis dibagi 5 yang dapat dibentuk dari angka-angka tersebut?

Penyelesaian:

1.      Ada 4 angka bilangan yang akan dibentuk :_ _ _ _

2.      Karena disyaratkan bilangan kelipatan 5, maka angka paling kanan hanya dapat diisi dengan angka 5 saja (satu cara)  à  _ _ _ 5

3.      Angka posisi ke 1 dapat diisi dengan 3 cara (yaitu 2, 3 dan 4) à < 5000

4.      Angka posisi ke 2 dapat diisi dengan 5 cara (2 angka lain sudah dipakai untuk posisi ke 1 dan ke-4)  7 – 2 = 5

5.      Angka posisi ke 3 dapat diisi dengan 4 cara (3 angka lain sudah dipakai untuk posisi ke 1, ke 2 dan ke 4)  7 – 3 = 4

6.      Karena seluruh posisi angka harus terisi, maka kita menggunakan kaidah perkalian, yaitu 3 x 5 x 4 x 1 = 60 buah.

Contoh 6.16

Lihatlah kembali contoh ilustrasi pada awal bab ini. sandi-lewat (password)  sistem computer  panjangnya enam sampai delapn karakter. Tiap karakter boleh berupa huruf atau angka; huruf  besar dan huruf kecil tidak dibedakan. Berapa banyak sandi lewat yang dapat dibuat?

Penyelesaian:

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

Untuk sandi lewat dengan panjang 6 karakter, jumlah kemungkinan sandi lewat adalah

                        (36)(36)(36)(36)(36)(36) = 36⁶ = 2.176.782.336

Untuk sandi lewat dengan panjang 7 karakter, jumlah kemungkinan sandi lewat adalah

                        (36)(36)(36)(36)(36)(36)(36) = 36⁷ = 78.364.164.096

Untuk sandi lewat dengan panjang 8 karakter, jumlah kemungkinan sandi lewat adalah

                        (36)(36)(36)(36)(36)(36)(36)(36) = 36⁸ = 2.821.109.907.456

Dengan menggunakan kaidah penjumlahan, jumlah seluruh sandi-lewat adalah

2.176.782.336 + 78.364.164.096 + 2.821.109.907.456 = 2.901.650.833.888 buah