|
|
KULIAH 2
PILIHATUR DAN
GABUNGAN
( Permutations
& Combinations)
Jika kita
diberikan sebuah bekas yang mengandungi 3 jenis gula-gula, Almond, Butter dan
Cherry. Ada berapa carakah untuk anda memilih 2 jenis gula-gula dari bekas
tersebut?
Sebelum anda menjawab
soalan ini, anda perlu pastikan samada bolehkah diambil 2 gula-gula dari jenis
yang sama misalnya AA ( Almond)? Atau AB (B:Butter) atau BA ?
Secara amnya
adakah anda dibenarkan membuat pengulangan?
Adakah anda
dibenarkan mengikut susunan yang tertentu?
Jadi untuk
menjawab soalan ini:
Ada 4 kasus yang
terlibat:
Ø Pengulangan dan mengikut susunan
Ø Pengulangan dan tidak mengikut susunan
Ø Mengikut susunan dan tanpa pengulangan
Ø Tidak mengikut susunan dan tanpa
pengulangan
Kasus 1: AA , AB , BA , BB, AC , CA, CC , BC, CB
Kasus 2: AA, AB, BB, AC, CC, BC
Kasus 3: AB, BA, AC, CA, BC, CB
Kasus 4: AB, AC, BC
IDEA PEMETAAN:
Contoh 1
A
B X
X X X X X X
X X X
X
(i) (ii) (iii)
tidak 1-1 dan tidak onto 1-1 tidak onto onto tidak 1-1
Contoh 2
A
q
q-1
X X X X B X X X X
1-1 dan onto songsangan
Contoh 3
6
orang rakan ke sebuah kedai aiskrim, dimana terdapat 4 jenis perasa aiskrim
yang dijual dikedai tersebut. Terdapat jenis vanilla, tutti-frutti, chocolate
dan mint-chip. Berapakah cara yang berbeza boleh mereka pilih untuk menikmati
aiskrim tersebut?
Penyelesaian:
Jika keenam rakan tersebut tidak perlu memilih perasa aiskrim yang berbeza, maka kita benarkan pengulangan. Untuk susunan maka kita namakan rakan itu mengikut 1 hingga 6 dimana rakan 1 memilih aiskrim pertama, rakan ke-2 memilih aiskrim ke-2 dan seterusnya. Maka pemilihan ini adalah secara susunan dan pengulangan bagi 6 objek dari 4 jenis perasa aiskrim.
Contoh 4
Ada
berapa carakah untuk memilih sebuah jawatankuasa yang terdiri dari seorang
pengerusi, seorang bendahari dan seorang setiausaha dari seramai 10 orang calon?
Penyelesaian:
Jika
kita katakana bahawa orang pertama yang dipilih ialah pengerusi, orang kedua
yang dipilih ialah bendahari dan orang ketiga yang dipilih ialah setiausaha,
maka ini adalah pemilihan mengikut susunan. Jika kita tidak mahu sesiapa pun mempunyai
lebih dari satu jawatan, maka kita tidak membenarkan pengulangan berlaku. Maka
ini adalah pemilihan mengikut susunan tanpa pengulangan, 3 orang dari 10 orang
calon.
Contoh 5
Dalam
satu peperiksaan yang terdiri dari 7 soalan, setiap pelajar diwajibkan menjawab
4 soalan sahaja. Ada berapa cara pemilihan soalan yang berbeza boleh dibuat
oleh pelajar tersebut?
Penyelesaian:
Pelajar
tidak akan menjawab sesuatu soalan itu lebih dari sekali, maka tidak dibenarkan
pengulangan. Susunan soalan untuk dijawab tidak diambil kira dalam kes ini.
Maka ini adalah pemilihan tidak mengikut susunan dan tanpa pengulangan bagi 4
pemilihan dari 7.
Contoh 6
Berapakah
cara yang berbeza boleh didapati dengan membaling 3 dadu yang sekata?
Penyelesaian:
Ini
adalah pemilihan 3 nombor, iaitu dari 1 hingga 6 dijumlahkan. Oleh kerana dadu
itu sekata, maka susunan tidak diambil kira. Pengulangan bagi nombor-nombor
juga adalah dibenarkan. Maka kes ini adalah pemilihan tidak mengikut susunan
dengan pengulangan, 3 pemilihan nombor dari 6 nombor.
Pemilihan
mengikut susunan dan pengulangan
Dari
contoh di atas 6 orang rakan ke sebuah kedai aiskrim yang menjual 4 jenis
perasa aiskrim. Ada berapakah cara pemilihan mengikut susunan yang boleh
didapatinya?
Ini adalah contoh pemilihan mengikut susunan dengan pengulangan. Orang yang pertama mempunyai kemungkinan untuk memilih 4 jenis perasa yang berbeza, orang yang kedua juga mempunyai kemungkinan untuk memilih 4 jenis perasa yang berbeza, begitu juga orang yang ke-3 sehingga yang terakhir.
Dengan
menggunakan petua hasil darab bilangan susunan kemungkinan yang didapati ialah
4 x 4 x 4 x 4 x 4 x 4 =
46
Keputusan ini boleh dinyatakan secara lebih formal dalam bentuk umum seperti berikut:
Jika
pengulangan dibenarkan maka bilangan susunan pemilihan bagi k objek
untuk memilih dari satu set n objek ialah nk
Bukti:
Ada
n cara untuk memilih objek pertama. Selepas memilih objek pertama, ada n cara
juga untuk memilih objek kedua. Kita terus membuat pemilihan sehingga kesemua k
objek telah dibuat pemilihan. Maka dengan menggunakan petua hasil darab
pemilihan ini boleh didapati
n x n x … x n = nk cara.
Contoh
7
Ada
berapakah cara untuk memilih 5 digit nombor talipon?
Penyelesaian:
Ada
10 kemungkinan bagi digit nombor iaitu dari 0, 1, ………, 9 untuk setiap 5 digit
nombor talipon yang hendak dihasilkan. Maka kes kita ialah pemilihan mengikut
susunan dan pengulangan bagi 5 objek dari 10.
Maka
ada 105 nombor talipon yang
mengandungi 5 digit yang akan dipilih.
Penyelesaian
ini dengan membuat anggapan bahawa nombor 0 boleh berada dihadapan. Berapakah
cara pemilihan yang berbeza jika nombor 0 tidak dibenarkan berada disebelah
hadapan?
Contoh
8
Seorang
pembuat kunci hendak mereka sebuah kunci yang mempunyai 5 kedudukan yang
berbeza, dimana setiap satunya boleh dipotong mengikut 8 kedalaman yang
berbeza. Ada berapa jenis kunci yang
berbeza boleh dihasilkannya?
Penyelesaian:
Ini
adalah kes mengikut susunan dan pengulangan, bagi 5 objek dari 8. Maka ada 85 jenis kunci yang boleh
dihasilkannya.
Ada
berapa carakah untuk memilih seorang pengerusi, seorang bendahari dan seorang
setiausaha bagi satu jawatankuasa dari 10 orang ahli ?
Jika
orang pertama yang dipilih adalah pengerusi, dimana ada 10 cara untuk
memilihnya. Manakala jika orang kedua ialah bendahari, maka ada 9 cara untuk
memilihnya. Akhirnya ialah untuk memilih orang ketiga sebagai setiausaha, maka
ada 8 cara untuk memilihnya.
Maka
dengan menggunakan petua hasil darab ada
10 x 9 x 8 = 720 cara.
Jika
pengulangan tidak dibenarkan bilangan pemilihan mengikut susunan bagi k
objek dari satu set n objek ialah
n( n-1)(n-2) … (n – k + 2)(n – k +1 ) , dan boleh ditulis sebaga (n)k
Bukti:
Ada
n cara untuk memilih objek yang pertama, maka tinggal n-1 objek
dari semua untuk memilih pemilihan kedua. Kita teruskan pemilihan sehingga
pemilihan objek terakhir, iaitu boleh dipilih dalam n – k +1
cara. Jadi dengan menggunakan petua hasil darab pemilihan ini ialah
sebanyak
n( n – 1)(n – 2) … ( n – k +1 ) cara .
Pemilihan
cara ini di kenali sebagai pilihatur (permutation), nama ini telah diberikan
oleh Jakob Bernoulli (1654 – 1705). Bernoulli adalah seorang ahli
matematik dan fizik berbangsa Swiss. Bukunya yang terkenal, Ars
Conjectandi telah diterbitkan setelah 8 tahun beliau meninggal dunia.
Buku ialah mengenai combinatorics dan hubungannya dengan teori kebarangkalian
(probability theory).
Bentuk
seperti 4 x 3 x 2 x 1 boleh
disebut sebagai 4 faktorial, dan ditulis sebagai 4!
Bagi
integer positif n,
n! =
n(n – 1) (n – 2 ) …. (3) (2) (1)
Juga,
0! = 1
Contoh
9
Kita
boleh menggunakan notasi faktorial untuk menyatakan nilai bagi (n)k
sebagai
(n)k = 
Contoh
10
Dalam
satu pertandingan bagi memenangi hadiah bercuti ke Perancis, daya tarikan
berikut adalah dinyatakan : Jenis masakan, Cuaca, Sungai, EuroDisney, Kebun
anggur dan Kemesraan. Untuk memenangi
pertandingan tersebut anda dikehendaki memilih 4 susunan penting ciri-ciri
istimewa negara Perancis itu. Berapakah bilangan penyertaan yang perlu anda
masuk supaya anda boleh menjawab dengan tepat?
Penyelesaian:
Ini
adalah kes pemilihan mengikut susunan tanpa pengulangan 4 dari 6.
Bilangan
pernyertaan anda ialah (6)4 = 6!
/ (6 – 4)! = 360.