teknik menghitungdan kombinatorial -...

1

Teknik Menghitungdan Kombinatorial

Contoh

� Berapa banyak pelat nomor bisa dibuat dengan mengunakan 3 huruf dan 3 angka?

� Berapa banyak pelat nomor bisa dibuat dengan menggunakan 3 huruf dan 3 angka tapi tanpa perulangan huruf?

� Berapa banyak cara mengecat 6 kamar menggunakan 4 warna cat?

Contoh

� Berapa banyak cara mengurutkan 9 orang dalam barisan?

� Berapa banyak cara mengatur quiz sehingga tidak satupun dari kalian mendapatkan soal yang sama?

� Berapa banyak fungsi berbeda yang mungkin ada antara dua himpunan terbatas A dan B?

Combinatorics

� Adl cabang dari matematika diskrit tentang cara mengetahui ukuran himpunan terbatas tanpa harus melakukan perhitungan setiap elemennya secara aktual.

2

Combinatorics� Aturan Jumlah :

� Misal sebuah tugas bisa diselesaikan setelah menyelesaikan tepat satu tugas lainnya dalam sebuah kumpulan sub-tugas saling bebas yang terbatas: sub-tugas1, sub-tugas2, ... , sub-tugasn;

� Sekarang, misal tiap tugas mempunyai beberapa cara untuk dilakukan, misal

• Sub-tugas1 bisa dilakukan sebanyak t1 cara,• Sub-tugas2 bisa dilakukan sebanyak t2 cara,• ...• Sub-tugasn bisa dilakukan sebanyak tn cara.

� Maka banyaknya cara untuk melakukan tugasitu adalah:

t1 + t2 + ... + tn

Aturan Jumlah

� 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?

� Nna 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.

Aturan Jumlah

� Contoh:� Misal salah satu dosen atau dalah satu

mahasiswa informatika harus dipilih menjadi anggota komite. Jika terdapat 4 dosen dan 16 mahasiswa, ada berapa banyak cara memilih seorang anggota komite?

Aturan Jumlah

� Contoh:� Misal mahasiswa harus mengambil sebuah mata

kuliah dari program studi lain yang merupakan bagian dari kurikulum, jika terdapat 3 mata kuliah dari prodi matematika, 4 dari prodi fisika, dan 4 dari prodi kimia. Ada berapa cara memilih satu mata kuliah?

3

Combinatorics� Aturan Kali:

� Misal sebuah tugas harus diselesaikan, dan dalam tugas tersebut terdapat sederetan n sub-tugas untuk menyelesaikan:

tugas = sub-tugas1, sub-tugas2, sub-tugas3, ..., sub-tugasn

dimana tiap sub-tugas mempunyai sebanyak tx cara untuk menyelesaikannya

• Sub-tugas1 = t1 cara,• Sub-tugas2 = t2 cara stlh sub-tugas1 selesai,• Sub-tugas3 = t3 cara stlh sub-tugas1 dan sub-tugas2

selesai, ... ,• Sub-tugasn = tn cara stlh sub-tugas1 ... sub-tugasn-1

selesaiMaka banyak cara untuk menyelesaikan tugas adl

t1 ⋅ t2 ⋅ t3 ⋅ ... ⋅ tn

� 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

Contoh - Aturan Kali

Contoh – Aturan Kali

� Berapa cara bisa dipilih untuk mengecat 3 kamar menggunakan 4 warna, jika tiap kamar berbeda warna?� tugas:

• 1 - mengecat kamar 1 - 4 cara (4 warna) • 2 - mengecat kamar 2 - 3 cara (3 warna)• 3 - mengecat kamar 3 - 2 cara (2 warna)

� Jadi t1 = 4, t2 = 3, t3 = 2, shg4 ⋅ 3 ⋅ 2 = 24 cara untuk mengecat

semua kamar


� 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

4


� Berapa banyak cara berbeda memilih 3 orang dalam sebuah grup yang terdiri dari 8 orang untuk menjadi ketua, wakil ketua, dan bendahara?

Contoh - Aturan Kali

� Jika kartu identitas mahasiswa merupakan perpaduan antara dua huruf dan tiga angka, berapa kartu identitas yang mungkin?� Jika hurufnya harus berbeda?

� Jika huruf dan angkanya harus berbeda?

� Aturan Kali:� Jika A dan B adl dua himpunan terbatas,

maka:

|A × B| = |A| ⋅ |B|� Kardinalitas dari perkalian kartesian adalah

perkalian dari kardinalitas kedua himpunan.

Combinatorics

Jika A = {a, b, c, d, e}, B = {1, 3, 5, 7}� Berapa banyak pasangan (x, y) yang

mungkin dimana x ∈ A dan y ∈ B?

� Kardinalitas A × B = |A| ⋅ |B| = 5 ⋅ 4 = 20


5

� Berapa banyak pelat nomor bisa dibuat yang mengandung 3 huruf diikuti oleh 3 angka?

26⋅26⋅26⋅10⋅10⋅10 = 17576000


� Aturan Jumlah:Jika A dan B adl dua himpunan yang terpisah, maka:

|A ∪ B| = |A| + |B|

Kardinalitas dari gabungan dua himpunan yang terpisah adalah jumlah dari kardinalitas keduanya.

Combinatorics

Contoh – Aturan Jumlah

Jika A = {a, b, c, d, e}, B = {1, 3, 5, 7}� Berapa banyak cara untuk mengambil

sebuah elemen?

|A ∪ B| = |A| + |B| = 5 + 4 = 9.

Contoh – Aturan Jumlah

� Andi punya lima lagu Indonesia, empat lagu Barat, dan tiga lagu Korea.

� Berapa banyak pilihan yang Andi punya untuk memilih satu lagu?

6

Contoh

� Seandainya anda punya 3 pasang sepatu, 6 pasang kaos kaki, 4 celana, dan 6 kemeja.

� Berapa banyak perpaduan pakaian yang bisa dipilih dari persediaan anda diatas?

(pakaian terdiri dari sepatu, sepasang kaos kaki, satu celana, dan satu kemeja)

Contoh

� Perhatikan graf berikut.

a)Berapa banyak cara untuk untuk bepergian dari A ke B, dan kembali ke A, tanpa melalui C?

b) Berapa banyak cara dari A ke C, berhenti sekali di B?

c)Berapa banyak cara dari A ke C jika hanya boleh berhenti sekali?

A B C

Contoh

� Sebuah komplek apartemen mempunyai 26 antena televisi. Tiap pasang apartemen menggunakan satu antena. Berapa banyak apartemen dalam komplek tersebut?

Contoh

� Dua kartu ditarik dari satu deck kartu, satu persatu. Berapa banyak keluaran yang mungkin jikaa) Urutan keluaran kartu diperhatikan?

b) Urutan keluaran kartu tidak diperhatikan?

7

Contoh

� Jika sebuah koin dilempar sebanyak 5 kali dan urutan keluarannya dicatat,� Ada berapa banyak kemungkinan urutan

keluaran ini?

Contoh

� Berapa banyak bilangan bulat antara 0 dan1,000,000 mengandung angka9?

Prinsip Kandang Burung

� Jika terdapat k + 1 atau lebih obyek yang ditempatkan dalam k kotak, maka paling tidak terdapat satu atau lebih kotak yang berisi dua atau lebih obyek.


� jika k + 1 atau lebih obyek ditampatkan dalam k kotak, maka terdapat sedikitnya satu kotak mengandung dua atau lebih obyek.

8





� Bukti: Misal tidak satupun dari k kotak mengandung lebih dari satu obyek. Maka banyak obyek maksimum adl k. Hal ini adl kontradiksi, krn sdh dinyatakan maka terdapat sedikitnya k + 1 obyek.


� Diantara 367 orang, terdapat paling sedikit 2 orang yang berulang tahun dihari yg sama, karena hanya terdapat 366 hari yang mungkin.

� Dalam koleksi 10 angka, terdapat paling sedikit 2 digit yang sama.

� Dalam koleksi 11 angka, terdapat paling sedikit 2 digit yang sama.


� Berapa banyak orang dalam ruang yang membuat kita yakin terdapat sedikitnya dua orang mempunyai hari ulang tahun yang sama?

9


� Apa ada dua orang di Banda Aceh yang mempunyai jumlah rambut yg sama?

� Apa ada dua orang di Informatika yang mempunyai ulang tahun yang sama?

� Apa ada dua orang di Informatika yang berulang tahun pada tanggal 14 Juli?


� Prinsip Kandang Burung Secara Umum:

Jika N obyek ditempatkan dalam kkotak, maka terdapat paling sedikit satu kotak yang mengadung paling tidak N/k obyek.

Prinsip Kandang Burung Secara Umum

� Jika N obyek ditempatkan dalam kkotak, maka terdapat paling sedikit satu kotak yang mengandung paling tidak N/k obyek.


� Jika N obyek ditempatkan dalam kkotak, maka terdapat paling sedikit satu kotak yang mengadung paling tidak N/k obyek.

10


� Jika N obyek ditempatkan dalam kkotak, maka terdapat paling sedikit satu kotak yang mengadung paling tidak N/k obyek.


� Bukti: Misal tidak terdapat satupun kotak yang mengandung lebih dari N/k - 1 obyek.Maka jumlah total dari obyek adl:

k (N/k - 1). Tapi karena N/k < (N/k + 1), kita dapatkan:

k (N/k - 1) < k (((N/k + 1) - 1) = N, makak (N/k - 1) < N

yg merupakan kontradiksi karena jumlah total obyek seharusnya adl N.


� Diantara 100 orang terdapat paling tidak100/12 = 9 orang yang mempunyai bulan kelahiran yang sama.


� Di FMIPA paling tidak terdapat500/366 = 2 orang dengan hari ulang tahun yang sama.

11


� Dalam sebuah kelas yang berisi 44siswa, berapa banyak yang akan menerima grade yang sama dalam skala {A, B, C, D, F}.


� Berapa banyak orang yang harus kita survey sdh kita yakin terdapat paling tidak 50 orang yang memilih calon gubernur yang sama?

� (Buat N/5 = 50)


� Diberikan n adl bilangan bulat positif.

� Tunjukkan bahwa sebarang himpunan yang terdiri dari n bil bulat yang berurutan terdapat tepat satu angka yang bisa dibagi oleh n.


� Sebuah jaringan komputer terdiri dari 6komputer.

� Tiap komputer terhubung secara langsung dengan nol atau lebih komputer yang lain.

� Tunjukkan bahwa terdapat sedikitnya dua komputer mempunyai jumlah koneksi (hubungan) yang sama.

12


� Tunjukkan bahwa jika tujuh bil bulat dipilih dari 8 bil bulat positif yang pertama, maka terdapat pasangan bil bulat yang jumlahnya sama dengan 9.� Apakah hal ini masih benar jika empat bil

bulat dipilih?


� Berapa jumlah mahasiswa minimum yang harus diterima Informatika sdh terdapat mahasiswa dari tiap kabupaten/kota di prov. Aceh?

Permutations dan Combinations

� Ada berapa cara dapat kita pilih r buah benda dalam koleksi yang berisi n buah benda?

pilih

Pilih 4 dari 9 bola berwarna

Permutasi dan Kombinasi� Ada berapa cara dapat kita pilih r buah benda

dalam koleksi yang berisi n buah benda?� Pernyataan diatas ambigu (membingungkan)

dalam beberapa cara:� Apalkah n buah benda tsb berbeda atau bisa

dibedakan?

� Apakah benda yg dipilih dlm bentuk himpunan(koleksi tak berurut) atau harus berupa barisan (berurut)?

� Apakah bendanya boleh sama (perulangan diperbolehkan)?

13

Permutasi dan Kombinasi

� Contoh: Menggunakan bola:� Apakah bolanya idektik atau berbeda

warna? Apakah beberapa berbeda warna, sdgkan yang lain sama?

� Apaah bola diambil tan berurutan atau berurutan?

� Apakah tiap bola dikembalikan sebelum yang selanutnya dipilih?

Permutasi

� Seleksi dari objek yang terurut.� Jika terdapat koleksi yg terdiri dari n

buah obyek, dan kita memilih semua n obyek, maka setiap kemungkinan seleksi adl permutasi dari koleksi.

� Pada kasus umum semua obyek berbeda dan perulangan tidak diperbolehkan.

Permutasi

� Kemungkinan permutasi dari tiga bola berbeda warna:

Permutasi

� Jika himpunan S = {a, b}. Apa permutasinya?

ab ba

14

Permutasi

� Jika himpunan S = {a, b, c}. Apa permutasinya?

abc acb bca bac cab cba

Permutasi

� Jika himpunan S = {a, b, c, d}. Apa permutasinya?

abcd acbd bcad bacd cabd cbad

abdc acdb bcda badc cadb cbda

adbc adcb bdca bdac cdab cdba

dabc dacb dbca dbac dcab dcba

Permutasi

� Theorema: Banyaknya permutationsdari sebuah himpunan yg terdiri dari n obyek adalah perkalian dari

n(n -1) ... 1 = n

PermutasiJustifikasi:

Mengatur n obyek dlm urutan memerlukan n tugas.Tugas 1 Pilih obyek pertama (n pilihan)Task 2 Pilih obyek kedua(n-1 pilihan)...Task n Pilih obyek terakhir (ke-n) (1 pilihan)

Maka, oleh aturan kali, banyaknya cara untuk mengatur n obyek adl:

n(n -1) ... 1 = n!

15

Permutasi

� Berapa banyak cara mengatur 9 regu dalam parade?

9 • 8 • 7 • 6 • 5 • 4 • 3 • 2 • 1 = 362880

r-Permutasi

� Mengatur sebuah subset dari sebuah koleksi obyek.

� Jika terdapat sebuah koleksi n obyek, dan kita memilij sebanyak r obyek dari n obyek, dimana 0<r≤n, maka setiap kemungkinan koleksi yang mungkin dinamakan r-permutasi.

r-Permutasi

� Mengambil 4 bola dari 9 bola

ambil

r-Permutasi

Himpunan S = {a, b, c}.

� Apa saja 2-permutasi dari S?

ab ba ac ca bc cb


abc acb bca bac cab cba

16

r-Permutasi

Himpunan S = {a, b, c, d}.


ab ac ad ba bc bd

ca cb cd da db dc

r-Permutasi

Himpunan S = {a, b, c, d}.


abc acb bac bca cba cab (dari {a, b, c})

abd adb bad bda dba dab (dari {a, b, d})

adc acd dac dca cda cad (dari {a, c, d})

dbc dcb bdc bcd cbd cdb (dari {b, c, d})

r-Permutasi

� Theorema: Banyaknya r-permutasi dari sebuah himpunan berisi n obyek, ditulisP(n, r) adl:

)!(

! )1()1()(

rn

nn-r ... n- n n, rP

−=+=

r-Permutasi

� Justifikasi:� Mengatur r dari n obyek kedalam urutan

memerlukan sebanyak r tugas.Tugas 1 Ambil obyek pertama (n pilihan)Tugas 2 Ambil obyek kedua (n-1 pilihan)

…Tugas r Ambil obyek ke-r (n - r + 1 pilihan)

� Maka dgn aturan kali:

)!(

! )1()1(

rn

nn-r ... n-n

−=+

17

r-Permutasi

Sebuah balapan kuda dgn 8 ekor kuda.

� Jika seorang petaruh memilih tiga kuda scr 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.

r-Permutasi

� Untuk menyampaikan pesan rahasia, dua kapal mempunyai tiga tiang bendera dan 10 bendera yang berbeda (satu bendera tiap tiang).� Ada aberapa cara menyampaikan pesan?

r-Permutasi

� Jika pelat nomor terdiri dari 3 huruf diikuti oleh 3 angka, dimana huruf dan angka tidak boleh berulang� Ada berapa kemungkinan pelat nomor?

Kombinasi

� Kombinasi – adl sebuah koleksi tak terurut dari obyek.

� Definisi:

� Diberikan sebuah himp.S dgn nobyek. Setiap subset yang berukuran k dari obyek(0<k≤n)adl kombinasi dgn ukuran k, atau k-kombinasi dari S.

18

Kombinasi

Himpunan A = {a, b, c}.

� Apa 2-combinasi dari A?

{a, b} {a, c} {b, c}� Apa 3-combinasi dari A?

{a, b, c}� Apa 1-combinasi dari A?

{a} {b} {c}

Kombinasi

Himpunan B = {a, b, c, d}.

� Apa 2- combinasi dari B?

{a, b} {a, c} {a,d} {b, c} {b, d} {c, d}

� Apa 3-combinasi dari B?

{a, b, c} {a, c, d} {b, c, d} {a, b, d}

Kombinasi

� Bandingkan 3-combinasi dgn 3-permutasi dari B:

3-permutasi 3-combinasi

abc acb bac bca cba cab {a, b, c}

abd adb bad bda dba dab {a, b, d}

adc acd dac dca cda cad {a, c, d}

dbc dcb bdc bcd cbd cdb {b, c, d}

Kombinasi

� Menunjukkan bahwa tiap r-combinasi mempunyai kemungkinan r-permutasi.Jadi:

� Theorema: Banyaknya r –combinasi dari n obyek berbeda adl:

)!(!

!

!

),(),(

rnr

n

r

rnPknC

−==

19

Kombinasi

� Justifikasi: Kita dapatkan banyaknya permutasi, kemudian kita bagi dengan faktor yang kita dptkan berulang. Karena tial r-kombinasi dari n obyek bisa diurutkan kedalam P(r,r) = r! cara, maka kita bagi banyaknya r-permutations dgn r!.

)!(!

!

!

),(),(

rnr

n

r

rnPknC

−==

Kombinasi

� Anka C(n,r) juga biasa dituliskan sbg:

� Bisa dibaca n diambil r obyek.

=

r

nrnC ),(

Kombinasi

� Brp banyak subset dgn ukuran 5 dari himpunan {1, 2, 3, ..., 10}?

252120

30240

12345

678910

1234512345

12345678910

!5!5

!10

!5

)5,10(5

10)5,10(

==⋅⋅⋅⋅⋅⋅⋅⋅=

⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅=

==

= P

C

Kombinasi

� Berapa banyaknya subset dgn ukuran 7 dai himpunan {1, 2, 3, ..., 10}?

� Berapa banyak subset dgn ukuran 3? � Berapa banyak subset dgn ukuran 2?

� Berapa banyak subset dgn ukuran 8?

20

Kombinasi

� Berapa banyak 5 kartu yang bisa dimabil dari deck dgn 52 kartu?

Kombinasi� Sebuah klub mempunyai anggota 5

lelaki dan 7 perempuan.� Ada berapa cara membentuk komite yang

terdiri dari 7 orang dgn aturan 3 lelaki dan 4 perempuan?

• 2 tugas – pilih lelaki, kemudian pilih perempuan.• Jadi: C(7,4) · C(5,3)

� Ada berapa cara membentuk komite yang terdiri dari 7 orang?

Kombinasi

� Ada berapa subset ukuran 2 dari himpunan {1, 2, ..., 20} yang tidak mengandung 2 angka yg berurutan?

� Solusi:� Hitung banyaknya subset yg mengandung

2 angka yg berurutan, dankurangkan dari total jumlah subset ukuran 2yg mungkin.

� Terdapat 19 subset yg mengandung 2 angka berurutan, contoh. {1,2}, {2,3}, {3,4}, ... , {19,20}.

� Maka: C(20,2) - 19.

Kombinasi

� Berapa banyak byte mengadung tepat empat 1?

� Solusi: C(8,4).

21

Kombinasi

� Sebuah klub terdiri dari 5 lelaki dan 6 perempuan.� Brp banyak cara utk membentuk komite dgn 3 org?

� Brp banyak cara utk membentuk komite yg terdiri dari 3 lelaki dan 4 perempuan?

� Brp banyak cara utk membentuk komite dgn 6 orang jika 2 perempuan menolak utk bekerjasama?

� Brp banyak cara utk membentuk komite dgn lelaki dan 3 perempuan jika 2 lelaki menolak bekerjasama?

Kombinasi� Solusi:

� C(11,3)� C(5,3)·C(6,4)� C(11,6)-C(9,4)� (C(5,4)-C(3,2))·C(6,3)

teknik menghitungdan kombinatorial -...

Documents