Muqodimah Kombinatorika dan Kaidah Pencacahan
"Combinatorics is an art of counting without counting", terjemah:
"Kombinatorika adalah seni menghitung (berapa banyak) tanpa menghitung (satu per satu)"
Kombinatorika merupakan cabang matematika yang mempelajari tentang pengaturan objek-objek, didasarkan pada hasil yang diperoleh melalui percobaan (proses fisik yang hasilnya dapat diamati).
Solusi yang ingin dicapai dalam kombinatorika adalah jumlah cara pengaturan objek-objek tertentu dalam himpunannya.
1. Kaidah Penjumlahan
kata kunci untuk kaidah penjumlahan adalah "atau"
A. Kejadian saling asing
Misalkan kejadian A dapat dilakukan dengan m cara dan kejadian B dapat dilakukan dengan n cara, Jika kejadian A dan B kejadian yang saling asing (tidak mungkin terjadi bersamaan), maka banyaknya cara kejadian A atau B adalah m + n cara.
Ingat kembali bahwa n(A ∪ B) = n(A) + n(B) untuk A dan B yang memenuhi A ∩ B = ∅.
contoh:
Di dalam sebuah kotak terdapat 3 bola merah, 4 bola biru, dan 5 bola hitam, dengan semua bola berwarna tunggal. Berapa banyak bola yang berwarna merah atau biru?
Karena semua bola berwarna tunggal, tidak ada bola yang berwarna merah dan biru sekaligus, sehingga keduanya saling asing, banyak bola merah atau biru adalah 3 + 4 = 7.
B. Kejadian tidak saling asing
Ingat kembali bahwa n(A ∪ B) = n(A) + n(B) − n(A ∩ B).
contoh:
Ada berapa cara memilih sebuah kartu As atau kartu merah dari setumpuk kartu resmi?
Jawab:
Banyak cara memilih kartu As : 4 cara
Banyak cara memilih kartu merah : 26 cara
Tapi ada 2 kartu yang merupakan kartu As sekaligus berwarna merah, yang jika langsung dijumlahkan 4 + 26 akan ada dua kartu yang dihitung dua kali yaitu As hati dan As wajik sehingga harus dikurangi dengan 2.
Jadi banyak cara memilih kartu As atau merah adalah 4 + 26 − 2 = 28 cara
2. Kaidah Perkalian
kata kunci untuk kaidah perkalian adalah "dan"
Misalkan kejadian C dapat dipecah menjadi dua tahap A dan B, di mana A dpt terjadi sebanyak m cara dan B dapat terjadi sebanyak n cara. Dengan syarat B terjadi tanpa dipengaruhi hasil dari A, maka C dapat terjadi sebanyak m × n cara.
Misalkan ada n tempat tersedia dengan k1 adalah banyaknya cara mengisi tempat pertama, k2 adalah banyaknya cara mengisi tempat kedua, dan seterusnya hingga kn adalah banyaknya cara mengisi tempat ke-n. Maka banyaknya cara mengisi tempat adalah k1 × k2 × ⋅⋅⋅ × kn.
Cara ini disebut sebagai aturan pengisian tempat dan sering disebut dengan kaidah perkalian.
contoh:
1. Misalkan dari kota A ke kota B ada tiga bus dengan jalur berbeda, dari B ke C ada dua bus dengan jalur berbeda. Ada berapa cara kita pergi dari A ke C? 3 × 2 = 6 cara.
2. Misalkan dari kota A ke kota B ada 5 bus dengan jalur berbeda, dari B ke C ada 4 bus dengan jalur berbeda dan 3 bus dari A ke C langsung. Ada berapa cara kita pergi dari A ke C dan kembali ke A dengan syarat tidak boleh menggunakan bus yang sama lebih dari sekali?
a) Berangkat lewat B
Banyak Cara Berangkat = 5 × 4 = 20 cara
Banyak cara pulang = - lewat B: 3 × 4 =12, ATAU
- langsung ke A = 3
Banyak cara pulang= 12 + 3 =15 cara
Banyak cara pergi pulang = 20 × 15 = 300
b) Berangkat tidak lewat B, langsung ke C
Banyak cara berangkat = 3
Banyak cara pulang = - lewat B: 4 × 5 = 20, ATAU
- langsung ke A = 2
Banyak cara pulang = 20 + 2 = 22
Banyak cara pergi pulang = 3 × 22 = 66
Banyak cara perjalanan = 300 + 66 = 366 cara.
3. Faktorial (Diskrit)
Misal suatu bilangan asli n. Faktorial dari n, ditulis n!, adalah perkalian mundur dari n sampai 1.
0! = 1
1! = 1
2! = 2 × 1 = 2
3! = 3 × 2 × 1 = 6
...
n! = n × (n − 1) × (n − 2) × ... × 2 × 1
Dalam bentuk rekursif, kita dapat menuliskan:
n! = n(n − 1)! = n(n − 1)(n − 2)! = n(n − 1)(n − 2)(n − 3)!, dan seterusnya.
Secara umum, hasil faktorial dari n menyatakan banyaknya kemungkinan susunan n elemen berbeda tanpa aturan tambahan.
contoh:
Banyaknya susunan dari a, b, c, d, e, f adalah 6 × 5 × 4 × 3 × 2 × 1 = 720.
4. Faktorial (Kontinu)
Misal didefinisikan suatu fungsi
Misal dilakukan integral parsial
u = xn, du = (nxn−1)dx
v = −e−x, dv = (e−x)dx
Dikarenakan f(0) = 1 dan f(n) = n × f(n − 1), fungsi ini memenuhi definisi faktorial.
Jadi, f(n) = n!, dengan kata lain fungsi ini merupakan fungsi faktorial.
Fungsi ini dapat digunakan untuk menghitung faktorial dari bilangan berapapun, selain bilangan bulat negatif, dikarenakan f(0) = 1 dan f(n) = n × f(n − 1), apabila dimasukkan n = 0 ke bentuk reduksi
f(0) = 0 × f(0 − 1) = 0 × f(−1)
1 = 0 × f(−1), tidak ada f(−1) yang memenuhi, begitu juga semua bilangan bulat sebelumnya, dimana
f(−1) = −1 × f(−2) yang mana f(−1) tidak terdefinisikan, sehingga f(−2) dan seterusnya tidak terdefinisikan.
Df = {x ∈ ℝ | x ∉ ℤ ∨ x ≥ 0}, berikut grafik fungsinya:
Mungkin diantara Sixtyfourians ada yang mengetahui jokes ini:
"Terdapat sebanyak ½√π cara menyusun ½ objek"
lalu muncul pertanyaan: "Bagaimana menyusun objek yang tidak utuh?", tetapi ternyata dengan memasukkan n = ½ ke fungsi faktorial yang diperumum, akan diperoleh hasil ½√π.
Mula-mula gunakan rumus reduksi
misal u = r.cos(θ), v = r.sin(θ), sehingga u² + v² = r².[cos²(θ) + sin²(θ)] = r²
Daerah integrasinya terbatas di kuadran I, dimana
S = {(u, v) | u ≥ 0; v ≥ 0} = {(r, θ) | r ≥ 0; 0 ≤ θ ≤ π/2}
Contoh Soal
1. Berapa banyak bilangan ganjil antara 1000 dan 9999 jika
(1a) semua angkanya berbeda
digit terakhir dapat diisi dengan 1, 3, 5, 7, dan 9, sehingga ada 5 pilihan.
digit pertama dapat diisi dengan 1 sampai 9, ada 9 pilihan, tetapi karena sudah terambil 1 untuk digit terakhir, tersisa 8 pilihan.
digit kedua dapat diisi dengan 0 sampai 9, ada 10 pilihan, tetapi karena sudah terambil 2 untuk digit terakhir dan pertama, tersisa 8 pilihan.
digit ketiga dapat diisi dengan 0 sampai 9, ada 10 pilihan, tetapi karena sudah terambil 3 untuk digit lainnya, tersisa 7 pilihan.
|
8 |
8 |
7 |
5 |
Banyaknya adalah 8 × 8 × 7 × 5 = 2240
(1b) boleh ada angka yang berulang.
karena dibolehkan berulang, masing-masing digit memiliki kemungkinan yang utuh
|
9 |
10 |
10 |
5 |
Banyaknya adalah 9 × 10 × 10 × 5 = 4500
2. Dari angka 1, 2, 3, 4, 5, 6, 7, 8, 9
Berapa banyak bilangan genap 3-angka yang
dapat dibuat dari angka-angka tersebut?
Berapa banyak bilangan ganjil 3-angka dengan
setiap angka berbeda yang dapat dibuat dari
angka-angka tersebut?
2a. Banyak bilangan genap tiga angka
Karena tidak ada keharusan beda, dianggap boleh ada yang berulang.
|
9 |
9 |
4 |
Banyaknya adalah 9 × 9 × 4 = 324
2b. Banyak bilangan ganjil tiga angka berbeda
Ada keharusan berbeda, setiap terambil 1, pilihan berkurang 1.
8 | 7 | 5 |
Banyaknya adalah 8 × 7 × 5 = 280
3. Tersedia 6 huruf: a, b, c, d, e, f. Berapa banyak cara
penyusunan kata terdiri dari 3 huruf jika:
3a. Tidak ada huruf yang diulang
Ada keharusan berbeda, setiap terambil 1, pilihan berkurang 1.
6 | 5 | 4 |
Banyaknya adalah 6 × 5 × 4 = 120
3b. Boleh ada huruf yang berulang
Karena tidak ada keharusan beda, dianggap boleh ada yang berulang.
6 | 6 | 6 |
Banyaknya adalah 6 × 6 × 6 = 216
3c. Tidak boleh ada huruf yang diulang, tetapi huruf e
harus ada
Ada keharusan berbeda, setiap terambil 1, pilihan berkurang 1. Untuk e di awal:
1 | 5 | 4 |
Banyaknya adalah 1 × 5 × 4 = 20
Ada 3 kemungkinan posisi e, yaitu di awal, tengah, dan akhir, sehingga banyaknya adalah
20 × 3 = 60
3d. Boleh ada huruf yang berulang dan huruf e harus
ada
Karena tidak ada keharusan beda, dianggap boleh ada yang berulang. Untuk e di awal:
1 | 6 | 6 |
Banyaknya adalah 1 × 6 × 6 = 36
Ada 3 kemungkinan posisi e, yaitu di awal, tengah, dan akhir, sehingga banyaknya adalah
36 × 3 = 108
4. Tentukan banyak cara pengaturan agar 3 orang mahasiswa Jurusan Informatika (I), 4 orang mahasiswa Kimia (K), 4 orang mahasiswa Geologi (G), dan 2 orang mahasiswa Farmasi (F) dapat duduk dalam satu baris sehingga mereka dari jurusan yang sama duduk berdampingan?
|
I |
K |
G |
F |
Terdapat 4 jurusan, sehingga ada 4! = 24 kemungkinan urutan jurusan.
Di masing-masing jurusan juga terdapat pengurutan.
Ada sebanyak kemungkinan urutan 4! × 3! × 4! × 4! × 2! = 165.888
5. Ada berapa banyak faktor dari 360?
Faktorisasi prima dari 360 adalah 2³ × 3² × 5¹.
Faktor-faktor yang memungkinkan adalah hasil kali dari (2⁰, 2¹, 2², 2³), (3⁰, 3¹, 3²), dan (5⁰, 5¹)
4 | 3 | 2 |
Banyaknya adalah 4 × 3 × 2 = 24
6. Setiap pengguna suatu sistem komputer memiliki suatu password yang terdiri dari 6 sampai dengan 8 karakter, dimana setiap karakter adalah huruf besar atau angka. Setiap password harus memuat paling kurang 1 angka. Berapa banyak password yang mungkin?
terdapat 10 angka dan 26 huruf besar
* Untuk 6 karakter
adanya 1 karakter angka = 10 kemungkinan pada 6 posisi
tersisa 5 posisi, masing-masing terdapat 36 kemungkinan, ada 36⁵ kemungkinan
sehingga ada sebanyak 10 × 6 × 36⁵ kemungkinan
* Untuk 7 karakter
adanya 1 karakter angka = 10 kemungkinan pada 7 posisi
tersisa 6 posisi, masing-masing terdapat 36 kemungkinan, ada 36⁶ kemungkinan
sehingga ada sebanyak 10 × 7 × 36⁶ kemungkinan
* Untuk 8 karakter
adanya 1 karakter angka = 10 kemungkinan pada 8 posisi
tersisa 7 posisi, masing-masing terdapat 36 kemungkinan, ada 36⁷ kemungkinan
sehingga ada sebanyak 10 × 8 × 36⁷ kemungkinan
Total semua kemungkinan adalah
10 × 6 × 36⁵ + 10 × 7 × 36⁶ + 10 × 8 × 36⁷
= 3.627.970.560 + 152.374.763.520 + 6.269.133.127.680
= 6.425.135.861.760 kemungkinan
Komentar
Posting Komentar