Combinatorics Adalah cabang dari matematika diskrit tentang cara mengetahui ukuran himpunan terbatas tanpa harus melakukan perhitungan setiap elemennya secara aktual.
Teknik Menghitung (Kombinatorik) ● ● ● ●
Penjumlahan Perkalian Permutasi Kombinasi
Oleh: Ridha Ferdhiana
Aturan Jumlah Misal sebuah tugas bisa diselesaikan dalam sebuah kumpulan subtugas saling bebas yang terbatas: subtugas1, subtugas2, ... , subtugasn; Sekarang, misal tiap tugas mempunyai beberapa cara untuk dilakukan, misal • Subtugas1 bisa dilakukan sebanyak t1 cara, • Subtugas2 bisa dilakukan sebanyak t2 cara, • ... • Subtugasn bisa dilakukan sebanyak tn cara. Maka banyaknya cara untuk melakukan tugasitu adalah: t1 + t2 + ... + tn
Contoh ●
●
Anna punya lima novel, empat majalah, dan tiga buku pengetahuan umum. Berapa banyak cara bisa dilakukan Anna untuk memilih bahan bacaan sambil menunggu antrian di bank? Jawab: Anna punya tiga tugas – memilih novel, memilih majalah, atau memilih buku. Yang pertama bisa dilakukan dengan 5 cara, yang kedua, 4 cara, dan yang ketiga dengan 3 cara. Sehingga terdapat: 5 + 4 + 3 = 12 cara untuk memilih bahan bacaaan.
Buktikan:
Bukti:
Diberikan A dan B adalah himpunan terbatas n( A B)=n( A )+n(B)−n( A B)
Jika AB=∅ maka , n( A B)=n( A)+n(B) Jika A⊆B , maka n( A)≤n(B)
Tugas : Buktikan! n( ABC)=n( A)+n(B)+ n(C)−n( A B)−n( A C )−n(BC )+n( ABC)
n( AB)=n( A)+n(B− A) =n( A)+n(B)−n( A B) Soal : Dalam sebuah himpuan semesta, U, yang mempunyai anggota 100 buah, dan jika A dan B adalah himpunan bagian n ( A B c )=90 dari U dan serta , dapatkan n ( AB)=70 n(A).
Aturan Kali Misal sebuah tugas harus diselesaikan, dan dalam tugas tersebut terdapat sederetan n subtugas untuk menyelesaikan: tugas = subtugas1, subtugas2, subtugas3, ..., subtugasn dimana tiap subtugas mempunyai sebanyak tx cara untuk menyelesaikannya Subtugas1 = t1 cara, Subtugas2 = t2 cara stlh subtugas1 selesai, Subtugas3 = t3 cara stlh subtugas1 dan subtugas2 selesai, ... , Subtugasn = tn cara stlh subtugas1 ... subtugasn1 selesai Maka banyak cara untuk menyelesaikan tugas adl
t1 t2 t3 ... tn
Contoh - Aturan Kali Berapa cara bisa dipilih untuk mengecat 3 kamar menggunakan 4 warna? Tugas: • 1 mengecat kamar 1 4 cara (4 warna) • 2 mengecat kamar 2 4 cara (4 warna) • 3 mengecat kamar 3 4 cara (4 warna) Jadi terdapat t1 = 4, t2 = 4, t3 = 4, dan 4 4 4 = 64 cara untuk mengecat 3 kamar dengan 4 warna
Aturan Kali Jika A dan B adl dua himpunan terbatas, maka: |A B| = |A| |B|
Contoh – Aturan Kali Terdapat berapa cara berbeda untuk mengurutkan 9 orang? Terdapat 9 tugas – memilih orang pertama, memilih orang kedua, dst, … Tugas pertama mempunyai 9 pilihan, kedua 8 pilihan, ... dan terakhir kesembilan hanya 1 pilihan, shg terdapat: 9 8 7 6 5 4 3 2 1 = 362880
TEKNIK MENGHITUNG: PERKALIAN Banyaknya susunan bilangan positif genap yang terdiri dari 3 angka yang diambil dari angka 2, 3, 4, 5, 6, 7 dan tidak boleh lebih dari 500 adalah....
Kardinalitas dari perkalian kartesian adalah perkalian dari kardinalitas kedua himpunan. Maka n(A x B) = n(A) x n(B)
Angka-angka yang kurang dari 500, dimulai dengan angka 2,3, dan 4. Sehingga banyaknya angka adalah : 3 x 6 x 3 = 54
Contoh – Aturan Kali Berapa banyak cara berbeda memilih 3 orang dalam sebuah grup yang terdiri dari 8 orang untuk menjadi ketua, wakil ketua, dan bendahara?
TEKNIK MENGHITUNG: PERMUTASI
P n , r , P nr
Pengertian: Mengatur n buah obyek yang diambil sebanyak r buah (r≤n) dalam suatu urutan.
Jawab :
P n , r =nn−1 n−2 …n−r1=
n! n−r !
Dimana
nn−1n−2…n−r1=
Permutasi Kemungkinan permutasi dari tiga bola berbeda warna:
n n−1n−2n−r1 .n−r! n−r !
Permutasi ●
Jika himpunan S = {a, b}. Apa permutasinya?
ab ba
Permutasi
Permutasi
Jika himpunan S = {a, b, c}. Apa permutasinya?
Jika himpunan S = {a, b, c, d}. Apa permutasinya?
abc acb bca bac cab cba
TEKNIK MENGHITUNG: PERMUTASI
P n , r , P nr
SAMPEL TERURUT Pengambilan Sampel DENGAN Pengembalian
Pada kasus khusus:
P n , n=n n−1 n−2…n−r1… 3.2 .1=n !
Permutasi dengan Perulangan
Banyaknya permutasi dari n obyek dimana beberapa obyeknya adl sama. Banyaknya permutasi dari n obyek dengan obyek 1 sebanyak n1, obyek 2 sebanyak n2, ...., obyek k sebanyak nk
P n , n1 , n2 , , n k =
abcd acbd bcad bacd cabd cbad abdc acdb bcda badc cadb cbda adbc adcb bdca bdac cdab cdba dabc dacb dbca dbac dcab dcba
n! n1 ! n 2 ! n k !
n.n.n.n =nr r
Pengambilan Sampel TANPA Pengembalian
P n , n=n n−1 n−2… n−r1… 3.2 .1=n ! Pengambilan sebanyak n
P n , r =n n−1n−2…n−r1=
n! n−r !
Pengambilan sebanyak r
Permutasi Sebuah balapan kuda dengan 8 ekor kuda. ●
Jika seorang petaruh memilih tiga kuda secara acak, dan memasang taruhan pada kuda pertama, kedua, dan ketiga scr berurutan, ada berapa cara dia bisa memilih kuda?
●
P(8,3) = 8 . 7 . 6 = 336 permutasi yg mungkin
●
Jadi ada 336 cara.
Permutasi
Permutasi ●
Untuk menyampaikan pesan rahasia, dua kapal mempunyai tiga tiang bendera dan 10 bendera yang berbeda (satu bendera pada tiap tiang). – Ada berapa cara menyampaikan pesan?
Kombinasi
Jika pelat nomor terdiri dari 3 huruf diikuti oleh 3 angka, ada berapa kemungkinan pelat nomor:
Kombinasi – adalah sebuah koleksi tak terurut dari obyek.
a. Jika huruf dan angka boleh berulang?
Definisi: Diberikan sebuah himp.S dgn n obyek. Setiap subset yang berukuran k dari obyek (0 < k < n)adl kombinasi dgn ukuran k, atau k-kombinasi dari S.
b. Jika huruf dan angka tidak boleh berulang?
Kombinasi
Kombinasi
Himpunan A = {a, b, c}.
Himpunan B = {a, b, c, d}.
●
Apa 2combinasi dari A?
●
{a, b} {a, c} {a,d} {b, c} {b, d} {c, d}
{a, b} {a, c} {b, c} ●
Apa 3combinasi dari A? ●
{a, b, c} ●
Apa 2 combinasi dari B?
Apa 3combinasi dari B?
{a, b, c} {a, c, d} {b, c, d} {a, b, d}
Apa 1combinasi dari A?
{a} {b} {c}
TEKNIK MENGHITUNG: KOMBINASI
Kombinasi ●
Bandingkan 3combinasi dgn 3permutasi dari B:
3permutasi 3combinasi abc acb bac bca cba cab abd adb bad bda dba dab
{a, b, c} {a, b, d}
adc acd dac dca cda cad dbc dcb bdc bcd cbd cdb
{a, c, d} {b, c, d}
C n , r ,C nr , n r
Pengertian: Mengatur n buah obyek yang diambil sebanyak r buah (r≤n) tidak dalam urutan.
P(n ,r) n! C (n , r)= = r! r !(n−r)!
