KOMBINATORIK DASAR

KOMBINATORIK DASAR

Disusun Untuk Memenuhi Tugas Mata Kuliah Matematika Diskret

yang Dibina Oleh Prof. Drs. Purwanto, Ph.D

Oleh:

HARYANTI

IIM FATIMAH

RIKZA MUQTADA

PROGRAM PASCASARJANA PENDIDIKAN MATEMATIKA

UNIVERSITAS NEGERI MALANG

2017

KOMBINATORIK DASAR

2.1 Pengantar

Kita telah melihat pentingnya perhitungan dalam analisis algoritma, secara khusus, kita menganalisis sebuah pemilahan algoritma dengan menghitung banyaknya perbandingan yang digunakan. Pada bab ini kita akan mengenalkan kombinatorik yaitu teori perhitungan. Kombinatorik sering disebut seni menghitung tanpa menghitung karena kita mencoba sedapat mungkin, untuk menghitung obyek dalam himpunan tanpa mendaftar semua obyek yang akan dihitung. Penalaran kombinatorial melibatkan ide tentang korespondensi satu-satu. Pada  bacaan sebelumnya kita menghitung kumpulan dari himpunan bagian dari himpunan n-elemen dengan menetapkan korespondensi satu-satu antara himpunan ini dengan himpunan barisan biner n-digit.

Contoh 2.1.1

              Gambar 2-1 berisi contoh dari pohon biner lengkap.

 

             

              Ini adalah sebuah gambar dari sebuah pohon keluarga (family tree) dimana setiap induk hanya memiliki dua anak dan semua induk tanpa anak adalah anggota dari generasi yang sama. Gambar itu disusun  dari simpul-simpul (vertices) yang dihubungkan dengan segmen garis atau edges. Simpul paling atas dinamakan akar (root). Simpul-simpul sisanya disusun menjadi generasi atau level. Simpul-simpul pada level ke-k yang dihubungkan ke akar melalui jalur (path) dengan k sisi. Akar berada di level 0. Simpul pada level teratas dinamakan daun (leaves). Dapat dikatakan bahwa x₂ adalah anak dari x₁. Kata pohon mengacu pada cabang perrtumbuhan. Kata biner menunjukkan bahwa setiap puncak mempunyai 2 anak, dan kata “lengkap” menunjukkan semua titik yang bukan daun mempunyai 2 anak dan semua daun berada di level yang sama. Ketinggian/kedalaman pohon adalah level dari sebarang daun. Pada gambar,  x₄ adalah daun dan tinggi pohonnya adalah 2.

              Berapa banyak jalur (path) dari akar ke daun pada pohon biner lengkap dengan tinggi r? Satu kemungkinan adalah kita menulis semua path, tetapi hal ini akan membosankan bahkan untuk  untuk pohon yang  kecil. Pendekatan yang lebih baik adalah menandai path dari akar ke bagian daun tertentu yang ditunjukkan dengan “mengambil cabang kiri” dan “mengambil cabang kanan” dan seterusnya. Barisan menghasilkan  path dalam pohon dari akar ke beberapa daun. Terdapat korespondensi satu-satu antara kumpulan path dan himpunan barisan biner r-digit (0 diambil dari cabang kiri dan 1 diambil dari cabang kanan).

              Barisan r-digit digambarkan sebagai sampel r obyek (1 untuk masing-masing digit) dari {0,1}, obyek pertama berkorespondensi dengan digit pertama, dan kita boleh mengulang obyek (0 atau 1). Pertanyaan umum yang muncul : Berapa banyak sampel dari r obyek dapat diambil dari{ x_1,  x_2,  x_3, ..., x_n} dimana urutan diperhatikan dan boleh berulang?

              Yang sangat berhubungan dengan masalah perhitungan adalah pertanyaan banyaknya kejadian yang terjadi. Kenyataannya, sebagian besar tugas awal dalam kombinatorik diangkat dari tes masalah/kejadian acak. Hubungan menjadi jelas saat kita mengingat cara menghitung peluang P(A), dimana A adalah kejadian. Maka kita:

1. Menghitung  bilangan T, banyaknya semua kemungkinan.

2. Menghitung N(A), banyaknya hasil yang mungkin dalam A.

3. Himpunan

Contoh 2.1.2:

Masalah :    Berapa peluang sebuah pengundian dua dadu berbeda (satu merah dan satu hijau) menghasilkan jumlah kurang dari 5?

Solusi :

            Ini adalah masalah di dunia nyata. Kita mencoba menghasilkan model matematika yang sesuai. Himpunan jumlah yang mungkin adalah: {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. Sedangkan kejadiannya adalah {2,3,4}. Menurut definisi, peluang dari kejadian ini adalah . Ini adalah hasil matematika, tetapi tidak bermakna apa-apa di dunia nyata. Andai kita membeli sepasang dadu, mengundi mereka jutaan kali dan mengamati semua hasilnya maka peluang jumlah kedua dadu kurang dari 5 tidak mendekati   . Apa yang dapat kita simpulkan? Mungkin kita mengundi dadu berapa kali pun tidak cukup. Sehingga kita dapat menyimpulkan model yang salah, manakah yang lebih baik?

            Jelasnya, untuk mendapatkan jumlah 2 tidak sama seperti mendapatkan jumlah 3, disini hanya ada 1 cara untuk mengundi dadu berjumlah 2, dan 2 cara untuk mengundi dadu berjumlah 3. Ini menghasilkan himpunan dari pasangan terurut dari muka-muka pada dadu. Elemen pertama dari pasangan terurut adalah permukaan dadu merah, sedang elemen kedua dari pasangan berurut adalah permukaan dadu hijau.

            {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6),

             (2,1), (2,2), (2,3), (2,4), (2,5), (2,6),

             (3,1), (3,2), (3,3), (3,4), (3,5), (3,6),

             (4,1), (4,2), (4,3), (4,4), (4,5), (4,6),

             (5,1), (5,2), (5,3), (5,4), (5,5), (5,6),

             (6,1), (6,2), (6,3), (6,4), (6,5), (6,6)}  

            Kejadian kita adalah himpunan bagian dari pasangan berurutan tersebut, dimana jumlah dadu adalah kurang dari 5.

            {(1,1), (1,2), (1,3)

              (2,1), (2,2)

              (3,1)}

Pada kasus ini peluangnya adalah  dan ini terbukti melalui percobaan.

            Ilustrasi kedua menggambarkan dua poin. Pertama, saat menemui pertanyaan tentang peluang, kita harus memilih model yang logis. Kedua, satu teknik untuk menghitung bilangan adalah dengan mendaftarnya.

Contoh: 2.1.3

Masalah: Sebuah tim baseball terdiri dari 25 pemain. Tunjukkan bahwa banyaknya 9 orang disusun berjajar sama dengan banyaknya sampel dari 9 obyek yang diambil dari {1, 2, 3, 4, ..., 25} dimana urutan diperhatikan dan tidak boleh berulang.

Solusi:      Barisan didapat dengan mendaftar 9 pemain berbeda dari 25 anggota tim.

                

                 Problem umum adalah: Berapa banyak sampel r obyek dari {x₁,  x₂, x₃, ..., x_n}dengan syarat urutan harus diperhatikan dan tidak boleh berulang?

Contoh: 2.1.4

Masalah:  Tunjukkan bahwa banyaknya jalan 10  blok dari stasiun ke kantor pada gambar 2-2 adalah sama artinya dengan banyaknya himpunan bagian dengan 3 elemen yang diambil dari {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} dimana urutan tidak diperhatikan dan tidak boleh berulang.

    

STASIUN

                                                                                                KANTOR

                                            Gambar 2-2

Solusi:      Beberapa jalan membutuhkan 7 blok mendatar (across=A) dan 3 blok menurun (down=D). Akibatnya, banyaknya jalan sama dengan banyaknya barisan 10 huruf yang terdiri dari 7A dan 3D.

                 Problem umum adalah: Berapa banyak sampel r obyek dari {x₁,  x₂, x₃, ..., x_n} dengan syarat urutan tidak diperhatikan dan tidak boleh berulang?

Contoh: 2.1.5

Masalah:  Tunjukkan bahwa banyaknya domino (ingat domino dibuat dari 2 sisi, masing-masing mempunyai 0 sampai 6 titik) sama dengan banyaknya sampel 2 obyek yang diambil dari {0, 1, 2, 3, 4, 5, 6} dimana urutan tidak diperhatikan dan boleh berulang.

Solusi:      Domino memiliki dua sisi. Urutan tidak diperhatikan dan boleh ada pengulangan.

Permasalahan ini kita bagi menjadi dua kasus:

1.      Kita menghitung semua pasangan sisi domino yang mungkin:

{(0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6)

  (1,0), (1,1), (1,2), (1,3), (1,4), (1,5), (1,6),

         (2,0), (2,1), (2,2), (2,3), (2,4), (2,5), (2,6),

  (3,0), (3,1), (3,2), (3,3), (3,4), (3,5), (3,6),

  (4,0), (4,1), (4,2), (4,3), (4,4), (4,5), (4,6),

(5,0), (5,1), (5,2), (5,3), (5,4), (5,5), (5,6),

(6,0), (6,1), (6,2), (6,3), (6,4), (6,5), (6,6)} 

2.      Pada domino tidak memperhatikan urutan karena domino bisa diputar, maka kita hilangkan unsur yang sama:

{(0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6)

            (1,1), (1,2), (1,3), (1,4), (1,5), (1,6),

                         (2,2), (2,3), (2,4), (2,5), (2,6),

                                     (3,3), (3,4), (3,5), (3,6),

                                                 (4,4), (4,5), (4,6),

                                                             (5,5), (5,6),

                                                                         (6,6)} 

                 Berarti kita menemukan bahwa banyaknya domino dengan kondisi tersebut adalah 28. Nampak bahwa sama saja dengan kita menyusun  banyaknya sampel 2 obyek yang diambil dari {0, 1, 2, 3, 4, 5, 6} dimana urutan tidak diperhatikan dan boleh berulang.

            Problem umum adalah: Berapa banyak sampel r obyek dari {x₁,  x₂, x₃, ..., x_n} dengan syarat urutan tidak diperhatikan dan boleh ada pengulangan?

Contoh lain:

Masalah:  Sebuah bilangan diambil acak dari {1, 2, 3, ..., 10.000}.

a.       Berapa peluang bahwa terambil bilangan yang habis dibagi 4?

b.      Berapa peluang bahwa terambil bilangan yang habis dibagi 8?

Solusi :  a.  Bilangan yang habis dibagi 4 adalah {4, 8, 12, ..., 10.000}

                    Banyaknya bilangan yang habis dibagi 4 =     = 2.500.

Banyaknya semua kemungkinan dalam pengambilan acak tersebut =      10.000.

                    Jadi peluang =  

b.    Bilangan yang habis dibagi 8 adalah {8, 16, 24, ..., 10.000}

                    Banyaknya bilangan yang habis dibagi 8 =     = 1.250.

Banyaknya semua kemungkinan dalam pengambilan acak tersebut =       10.000.

Jadi peluang =