Jumat, 14 Oktober 2011

KOMBINATORIK

  • Persoalan kombinatorik bukan merupakan persoalan yang baru dalam kehidupan nyata. Banyak persoalan kombinatorik yang sederhana telah diselesaiakan dalam masyarakat. Misalkan, saat pemilihan pemain untuk tim sepak bola yang terdiri dari 11 pemain. Apabila ada 20 orang ingin membentuk suatu tim sepak bola, ada berapa kemungkinan komposisi pemain yang dapat terbentuk? Contoh lain adalah dalam menentukan sebuah password panjangnya 6 sampai 8 karakter. Karakter boleh berupa huruf atau angka. Berapa banyak kemungkinan password yang dapat dibuat ? Tetapi selain itu para ilmuwan pada berbagai bidang juga kerap menemukan sejumlah persoalan yang harus diselesaikan. Pada Bab ini, kita akan membahas tentang kombinatorik, permutasi dan apa yang terkait dengan itu. Kombinatorik merupakan cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.
  • 3.1 Prinsip Dasar Menghitung Dua prinsip dasar yang digunakan dalam menghitung (counting) yaitu aturan pejumlahan dan aturan perkalian. Prinsip Penjumlahan Jika suatu himpunan A terbagi kedalam himpunan bagian A1, A2, …, An, maka jumlah unsur pada himpunan A akan sama dengan jumlah semua unsur yang ada pada setiap himpunan bagian A1, A2, …, An. Secara tidak langsung, pada prinsip penjumlahan, setiap himpunan bagian A1, A2, …, An tidak saling tumpang tindih (saling lepas). Untuk himpunan yang saling tumpang tindih tidak berlaku lagi prinsip penjumlahan, dan ini harus diselesaikan dengan prinsip inklusi-eksklusi yang akan dibahas kemudian.
  • Contoh 1 : Seorang guru SD di daerah, mengajar murid kelas 4, kelas 5 dan kelas 6. Jika jumlah murid kelas 4 adalah 25 orang dan jumlah murid kelas 5 adalah 27 orang serta jumlah murid kelas 6 adalah 20 orang, maka jumlah murid yang diajar guru tersebut adalah 25 + 27 + 20 = 72 murid.
  • Contoh 2 : Seorang mahasiswa ingin membeli sebuah motor. Ia dihadapkan untuk memilih pada satu jenis dari tiga merk motor, Honda 3 pilihan, Suzuki 2 pilihan, dan Yamaha 2 pilihan. Dengan demikian, mahasiswa tersebut mempunyai mempunyai pilihan sebanyak 3 + 2 + 2 = 7 pilihan. Adiwijaya
  • Prinsip Perkalian Misalkan sebuah prosedur dapat dipecah dalam dua penugasan. Penugasan pertama dapat dilakukan dalam n1 cara, dan tugas kedua dapat dilakukan dalam n2 cara setelah tugas pertama dilakukan. Dengan demikian, dalam mengerjakan prosedur tersebut ada (n1 x n2) cara. Secara tidak langsung, pada prinsip perkalian, bisa terjadi saling tumpang tindih (tidak saling lepas).
  • Contoh 1 : Berapa banyak string dengan panjang tujuh yang mungkin terbentuk dari dua bit (0 dan 1)
  • Jawab : Setiap suku pada string tersebut mempunyai dua cara pemilihan, yaitu 0 atau 1. Dengan demikia, pada pemilihan string dengan panjang tujuah dapat dilakukan dengan : 2 x 2 x 2 x 2 x 2 x 2 x 2 = 27 = 128 cara.
  • Contoh 2 : Seorang guru SD di daerah, mengajar murid kelas 4, kelas 5 dan kelas 6. Misalkan, jumlah murid kelas 4 adalah 25 orang dan jumlah murid kelas 5 adalah 27 orang serta jumlah murid kelas 6 adalah 20 orang. Jika guru tersebut ingin memilih tiga orang murid dari anak didiknya, dimana seorang murid dari setiap kelas, maka guru tersebut mempunyai 25 x 27 x 20 = 13.500 cara dalam memilih susunan tiga murid tersebut.
  • Contoh 3 : Berapa banyak bilangan ganjil antara 1000 dan 9999 (termasuk 1000 dan 9999 itu sendiri) dimana (a) semua angkanya berbeda (b) boleh ada angka yang berulang.
  • Jawab :
  • (a) posisi satuan: 5 kemungkinan angka (yaitu 1, 3, 5, 7 dan 9); posisi ribuan: 8 kemungkinan angka (1 sampai 9 kecuali angka yang telah dipilih) posisi ratusan: 8 kemungkinan angka posisi puluhan: 7 kemungkinan angka maka banyak bilangan ganjil seluruhnya adalah (5)(8)(8)(7) = 2240 buah. (b) posisi satuan: 5 kemungkinan angka (yaitu 1, 3, 5, 7 dan 9); posisi ribuan: 9 kemungkinan angka (1 sampai 9) posisi ratusan: 10 kemungkinan angka (0 sampai 9) posisi puluhan: 10 kemungkinan angka (0 sampai 9)
  • maka banyak bilangan ganjil seluruhnya adalah (5)(9)(10)(10) = 4500
  • Contoh 5 : Password suatu login pada sistem komputer panjangnya lima sampai tujuh karakter. Tiap karakter boleh berupa huruf (huruf besar dan huruf kecil tidak dibedakan) atau angka. Berapa banyak password yang dapat dibuat untuk suatu login ?
  • Jawab : Banyaknya huruf alfabet adalah 26 (A – Z) dan banyak angka adalah 10 (0 – 9), jadi seluruhnya 36 karakter. Untuk password dengan panjang 5 karakter, jumlah kemungkinan password adalah (36)(36)(36)(36)(36) = 365 = 60.466.176 untuk password dengan panjang 6 karakter, jumlah kemungkinan password adalah (36)(36)(36)(36)(36)(36)(36) = 366 = 2.176.782.336 dan untuk password dengan panjang 8 karakter, jumlah kemungkinan password adalah (36)(36)(36)(36)(36)(36)(36)(36) = 367 = 78.364.164.096 Jumlah seluruh password yang mungkin adalah 60.466.176 + 2.176.782.336 + 78.364.164.096 = 80.601.412.608 buah. Jadi, untuk suatu login akan mempunyai 80.601.412.608 buah kemungkinan password.

sumber:jejak jari

2 komentar: