Kombinatorial
adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa
harus mengenumerasi semua kemungkinan susunannya. Kombinatorial dapat digunakan
untuk menjawab soal semacam ini tanpa kita perlu mengenumerai semua kemungkinan
jawabannya. Hal ini dapat dilakukan karena didalam kombinatorial terdapat
kaidah dasar menghitung. Dan kombinator digunakan pada teori peluang diskrit
untuk menghitung peluang suatu kejadian terjadi.
A. Percobaan
Kombinatorial
didasarkan pada hasil yang diperoleh dari suatu percobaan. Percobaan adala
proses fisik yang hasilnya dapat diamati
Contoh
:
1. Melempar
dadu
Enam hasil percobaan yang mungkin untuk
pelemparan dadu adalah muka dadu 1,2,3,4,5 atau 6
2. Melempar
koin uang Rp 100
Hasil percobaan melempar koin 100 ada
dua kemungkinan maka koin bergambar rumah gadang atau muka koin yang bergambar
wayang.
B. Kaidah Dasar Menghitung
Dua
kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatrorial
adalah kaidah perkalian (rule of product) dan kaidah penjumlahan (rule of sum).
-
Kaidah Perkalian (rule of product)
Percobaan
1: p hasil
Percobaan
2: q hasil maka,
Percobaan 1
dan percobaan 2: p ´ q hasil
-
Kaidah Penjumlahan (rule of sum)
Percobaan
1: p hasil
Percobaan
2: q hasil maka,
Percobaan 1
atau percobaan 2: p + q
hasil
C. Perluasan Kaidah Menghitung
Kaidah
perkalian dan penjumlahan diatas dapat diperluas sehingga mengandung lebih dari
dua buah percobaan. Jika n buah percobaan masing-masing mempunyai p1, p2, …,pn,
hasil percobaan yang mungkin terjadi dalam hal ini setiap p1 tidak bergantung
pada pilihan sebelumnya, maka jumlah hasil percobaan yang mungkin terjadi
adalah :
a. P1
x p2 x … x pn untuk kaidah perkalian.
b. P1
+ p2 + … + pn untuk kaidah penjumlahan.
D. Prinsip Inklusi-Eksklusi
Informasi
terkecil yang dapat disimpan di dalam memori computer adalah byte. Setiap byte
disusun oleh 8 bit.
Example
:
1. Setiap byte disusun oleh 8-bit. Berapa banyak
jumlah byte yang dimulai dengan ‘11’ atau berakhir dengan ‘11’?
Answer
:
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½
= 26 = 64,
½B½
= 26 = 64,
½A
Ç
B½
= 24 = 16.
maka
½A
È
B½
= ½A½
+ ½B½
– ½A
Ç
B½
= 26 + 26 –
16 = 64 + 64 – 16 = 112.
E. Permutasi
Permutasi
adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Juga merupakan
bentuk khusus aplikasi dari n objek, urutan kedua dipilih dari n-1 objek,
urutan ketiga dipilih dari n-2 objek, begitu seterusnya, dan urutan terakhir
dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian permutasi dari n
objek adalah
N(n-1)
(n-2) … (2)(1) = n!
Example :
Berapa
banyak “kata” yang terbentuk dari kata “HAPUS”?
Answer
:
Cara 1: (5)(4)(3)(2)(1) = 120 buah kata
Cara 2: P(5, 5) = 5! = 120 buah kata
Berapa
banyak cara mengurutkan nama 25 orang mahasiswa?
Answer
:
P(25, 25) = 25!
Ada juga yang dikatakan permutasi melingkar. Yaitu
penyusunan objek-objek yang megelilingi sebuah lingkaran (atau kurva tertutup
sederhana). Jumlah susunan objek yang mengelilingi lingkaran adalah (n-1)!.
F. Kombinasi
Bentuk
khusus permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan
diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan urutan acb,
bca, acb dianggap sama dan dihitung sekali.
Example :
1. Misalkan ada 2 buah bola yang warnanya sama dan ada 3
buah kotak. Setiap kotak hanya boleh berisi paling banyak 1 bola.
Jumlah cara
memasukkan bola ke dalam kotak :
2. Bila sekarang jumlah bola 3 dan jumlah kotak 10, maka
jumlah cara memasukkan bola ke dalam kotak adalah
karena ada 3! cara memasukkan bola yang warnanya sama.
Kombinasi
r elemen dari n elemen, atau
C(n, r),
adalah jumlah pemilihan yang tidak terurut r elemen yang diambil
dari n buah elemen.
Example from
Interpretasi Kombinasi :
1.
C(n, r)
= banyaknya himpunan bagian yang terdiri dari r elemen yang dapat
dibentuk dari himpunan dengan n elemen.
Misalkan
A = {1, 2, 3}
Jumlah
Himpunan bagian dengan 2 elemen:
{2, 3} = {3, 2}
G. Permutasi dan Kombinasi Bentuk Umum
Misalkan:
ada n buah bola yang tidak seluruhnya berbeda warna (jadi, ada beberapa
bola yang warnanya sama - indistinguishable). n1 bola
diantaranya berwarna 1, n2 bola diantaranya berwarna 2, nk
bola diantaranya berwarna k, dan n1 + n2 + … + nk
= n.
Berapa jumlah cara pengaturan n buah bola ke
dalam kotak-kotak tersebut (tiap kotak maks. 1 buah bola)?
Answer :
Jika
n buah bola itu kita anggap berbeda semuanya, maka jumlah cara
pengaturan n buah bola ke dalam n
buah kotak adalah
P(n, n) = n!.
Dari
pengaturan n buah bola itu,
-
ada n1! cara
memasukkan bola berwarna 1
-
ada n2! cara memasukkan bola
berwarna 2
-
ada nk! cara
memasukkan bola berwarna k
Permutasi
n buah bola yang mana n1 diantaranya berwarna 1, n2
bola berwarna 2, …, nk bola berwarna k
adalah:
Dengan cara lain :
-
Ada C(n, n1)
cara untuk menempatkan n1 buah bola yang berwarna 1.
-
Ada C(n – n1,
n2) cara untuk menempatkan n2 buah bola
berwarna 2.
-
Ada C(n – n1
– n2, n3) cara untuk menempatkan n3
buah bola berwarna 3.
-
Ada C(n – n1
– n2 – … – nk-1,
nk ) cara untuk menempatkan nk buah bola
berwarna k.
H. Kombinasi dengan Pengulangan.
Tinjau
kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola
yang semua warnanya sama dan n buah kotak.
Misalkan
terdapat r buah bola yang semua warnanya sama dan n buah kotak.
i.
Jika masing-masing kotak hanya boleh
diisi paling banyak satu buah bola, maka jumlah cara memasukkannya boal kedalam
kotak adalah C(n,r).
ii.
Jika masing-masing kotak boleh lebih dari
satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan
bola kedalam kotak adalah C(n+r-1,r)
Contoh
:
Pada
persamaan x 1
+x 2 + x 3 + x 4 =12,
x i
adalah bilangan bulat ≥0
. Berapa jumla kemungkinan solusinya?
Penyelesaian:
Analogikan
12 buah bola akan dimasukkan kedalam 4 kotak, maka:
-
Kotak 1 diisi 3 buah bola (x 1 =3)
-
Kotak 2 diisi 5 buah bola (x 2 =5)
-
Kotak
3 diisi 2 buah bola (x 3 =2)
-
Kotak 4 diisi 2 buah bola (x 4 =2)
I.
Koefisien
Binomial
Aturan untuk menjabarkan bentuk
perpangkatan x + y n
adalah
·
Suku pertama x n ,
sedangkan suku terakhir adalah y n
·
Pada setiap suku berikutnya, pangkat x
berkurang satu sedangkan pangkat y bertambah satu. Untuk setiap suku, jumlah
pangkat x dan y adalah n.
·
Koefisien untuk x n - k y k ,
yaitu suku ke- (k+1) adalah C(n,k).
Bilangan C(n,k) disebut koefisien binomial.
Aturan
di atas dapat di simpulkan bahwa:
J.
Prinsip
Sarang Merpati
Jika
n+1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit
terdapat satu kotak yang berisi dua atau lebih objek.
Prinsip
sarang merpati dikemukakan oleh G.Lejeune Dirichlet,seorang matematikawan Jerman,
sehingga kadang-kadang dinamakan juga prinsip kotak Dirichlet, karena Dirichlet
sering menggunakan prinsip ini dalam pekerjaannya.
example
:
Misalkan
terdapat banyak bola merah,bola putih,dan bola biru di dalam sebuah
kotak.Berapa paling sedikit jumlah bola yang diambil dari kotak (tanpa melihat
kedalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil?
answer:
Jika
setiap warna dianggap sebagai sarang merpati, maka n=3 karena itu orang
mengambil paling sedikit n+1=4 bola (merpati),maka dapat dipastikan sepasang
bola yang berwarna sama ikut terambil.Jika hanya diambil 3 buah, maka ada
kemungkinan ketiga bola itu berbeda warna satu sama lain.jadi, 4 buah bola
adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjamin terambil
sepasang bola yang berwarna sama.
K.
Peluang
Diskrit
Peluang
diskrit mempunyai sifat sebagai berikut:
a. 0≤ p ( x i )≤1,
yaitu peluang adalah bilangan tidak
negatif dan selalu lebih kecil atau sama dengan 1.
b. i =1 | S | p ( x i ) =1
, yaitu jumlah peluang semua titik contoh
di dalam ruang contoh S adalah 1.
Contoh:
Pada
pelemparan dadu, S={1,2,3,4,5,6}. Peluang munculnya setiap angka adalah sama
yaitu 1/6.
Kejadian (event)→
disimbolkan dengan E- adalah himpunan
bagian dari ruang. Peluang kejadian E di dalam ruang contoh S adalah
P(E)=|E|/|S|. Peluang kejadian E juga diartikan sebagai jumlah peluang semua
titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa:
Konsep-konsep
pada teori himpunan:
·
P
A ∩ B = x i ∈ A ∩ B p ( x i )
·
P
A ∪ B = x i ∈ A ∪ B p ( x i )
·
P
A - B = x i ∈ A - B p ( x i )
·
P
A ⨁ B = x i ∈ A ⨁ B p ( x i )
·
P ( A )=1- P ( A )
0 komentar:
Posting Komentar