Contoh. Teknik Menghitungdan Kombinatorial. Contoh. Combinatorics

Contoh Teknik Menghitungdan Kombinatorial

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?

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?

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

1

Combinatorics

Aturan Jumlah

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.

Contoh:

Maka banyaknya cara untuk melakukan tugasitu adalah:

t1 + t2 + ... + tn

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?

2

Combinatorics

Contoh - Aturan Kali

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 selesai Maka banyak cara untuk menyelesaikan tugas adl t1 ⋅ t2 ⋅ t3 ⋅ ... ⋅ tn

Berapa cara bisa dipilih untuk mengecat 3 kamar menggunakan 4 warna?

• 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 Berapa cara bisa dipilih untuk mengecat 3 kamar menggunakan 4 warna, jika tiap kamar berbeda warna?

Contoh – Aturan Kali Terdapat berapa cara berbeda untuk mengurutkan 9 orang?

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, shg 4 ⋅ 3 ⋅ 2 = 24 cara untuk mengecat semua kamar

Tugas:

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

3

Contoh – Aturan Kali

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?

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

Combinatorics 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.

Jika hurufnya harus berbeda? Jika huruf dan angkanya harus berbeda?

Contoh – Aturan Kali 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

4

Combinatorics

Contoh – Aturan Kali 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.

Contoh – Aturan Jumlah Jika A = {a, b, c, d, e}, B = {1, 3, 5, 7} Berapa banyak cara untuk mengambil sebuah elemen?

Contoh – Aturan Jumlah Andi punya lima lagu Indonesia, empat lagu Barat, dan tiga lagu Korea.

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

Berapa banyak pilihan yang Andi punya untuk memilih satu lagu?

5

Contoh

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

Perhatikan graf berikut. A

Berapa banyak perpaduan pakaian yang bisa dipilih dari persediaan anda diatas? (pakaian terdiri dari sepatu, sepasang kaos kaki, satu celana, dan satu kemeja)

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

B

C

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?

Contoh Dua kartu ditarik dari satu deck kartu, satu persatu. Berapa banyak keluaran yang mungkin jika a) Urutan keluaran kartu diperhatikan? b) Urutan keluaran kartu tidak diperhatikan?

6

Contoh Jika sebuah koin dilempar sebanyak 5 kali dan urutan keluarannya dicatat,

Contoh Berapa banyak bilangan bulat antara 0 dan 1,000,000 mengandung angka9?

Ada berapa banyak kemungkinan urutan keluaran ini?

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.

7



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

jika k + 1 atau lebih obyek ditampatkan dalam k kotak, maka terdapat sedikitnya satu kotak mengandung dua atau lebih obyek. 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?

8



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:

Prinsip Kandang Burung Secara Umum


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

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


9




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, maka k (N/k - 1) < N yg merupakan kontradiksi karena jumlah total obyek seharusnya adl N.



Diantara 100 orang terdapat paling tidak 100/12 = 9 orang yang mempunyai bulan kelahiran yang sama.

Di FMIPA paling tidak terdapat 500/366 = 2 orang dengan hari ulang tahun yang sama.

10

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

Prinsip Kandang Burung Secara Umum 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)

Prinsip Kandang Burung Secara Umum 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.

Prinsip Kandang Burung Secara Umum Sebuah jaringan komputer terdiri dari 6 komputer. Tiap komputer terhubung secara langsung dengan nol atau lebih komputer yang lain. Tunjukkan bahwa terdapat sedikitnya dua komputer mempunyai jumlah koneksi (hubungan) yang sama.

11



Tunjukkan bahwa jika tujuh bil bulat dipilih dari 8 bil bulat positif yang pertama, maka terdapat pasangan bil bulat yang jumlahnya sama dengan 9.

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

Apakah hal ini masih benar jika empat bil bulat dipilih?

Permutations dan Combinations Ada berapa cara dapat kita pilih r buah benda dalam koleksi yang berisi n buah benda?

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:

pilih

Pilih 4 dari 9 bola berwarna

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

12

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 Kemungkinan permutasi dari tiga bola berbeda warna:

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 Jika himpunan S = {a, b}. Apa permutasinya?

ab ba

13

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 abdc adbc dabc

acbd acdb adcb dacb

Permutasi Theorema: Banyaknya permutations dari sebuah himpunan yg terdiri dari n obyek adalah perkalian dari n(n -1) ... 1 = n

bcad bcda bdca dbca

bacd badc bdac dbac

cabd cadb cdab dcab

cbad cbda cdba dcba

Permutasi Justifikasi: 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!

14

Permutasi

r-Permutasi

Berapa banyak cara mengatur 9 regu dalam parade?

Mengatur sebuah subset dari sebuah koleksi obyek. Jika terdapat sebuah koleksi n obyek, dan kita memilij sebanyak r obyek dari n obyek, dimana 0
9 • 8 • 7 • 6 • 5 • 4 • 3 • 2 • 1 = 362880

r-Permutasi Mengambil 4 bola dari 9 bola

r-Permutasi Himpunan S = {a, b, c}. Apa saja 2-permutasi dari S?

ab ba ac ca bc cb ambil

Apa saja 3-permutasi dari S?

abc acb bca bac cab cba

15

r-Permutasi Himpunan S = {a, b, c, d}. Apa saja 2-permutasi dari S?

ab ac ad ba bc bd ca cb cd da db dc

r-Permutasi Himpunan S = {a, b, c, d}. Apa saja 3-permutasi dari S? abc acb bac bca cba cab abd adb bad bda dba dab adc acd dac dca cda cad dbc dcb bdc bcd cbd cdb

r-Permutasi Theorema: Banyaknya r-permutasi dari sebuah himpunan berisi n obyek, ditulis P(n, r) adl:

(dari {a, b, c}) (dari {a, b, d}) (dari {a, c, d}) (dari {b, c, d})

r-Permutasi Justifikasi:

Mengatur r dari n obyek kedalam urutan memerlukan sebanyak r tugas. Tugas 1 Tugas 2 … Tugas r

n! P( n, r ) = n( n-1) ... (n-r + 1) = ( n − r )!

Ambil obyek pertama (n pilihan) Ambil obyek kedua (n-1 pilihan) Ambil obyek ke-r

(n - r + 1 pilihan)

Maka dgn aturan kali:

n(n-1) ... (n-r + 1) =

n! ( n − r )!

16

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?

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?

P(8,3) = 8 • 7 • 6 = 336 permutasi yg mungkin Jadi ada 336 cara.

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 n obyek. Setiap subset yang berukuran k dari obyek (0
17

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}

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}

Apa 1-combinasi dari A?

{a} {b} {c}

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:

C ( n, k ) =

P( n, r ) n! = r! r!(n − r )!

18

Kombinasi C ( n, k ) =

P( n, r ) n! = r! r!(n − r )!

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!.

Kombinasi Brp banyak subset dgn ukuran 5 dari himpunan {1, 2, 3, ..., 10}? 10  P(10,5) 10! C (10,5) =   = = 5! 5!5! 5 =

10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅1 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅1

=

10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 30240 = = 252 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅1 120

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

 n C (n, r ) =   r Bisa dibaca n diambil r obyek.

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?

19

Kombinasi

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

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)

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

Ada berapa cara membentuk komite yang terdiri dari 7 orang?

Kombinasi Berapa banyak byte mengadung tepat empat 1? Solusi: C(8,4).

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.

20

Kombinasi

Kombinasi Solusi: 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?

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

21

Contoh. Teknik Menghitungdan Kombinatorial. Contoh. Combinatorics

Recommend Documents