My first Magazine pemrograman-kompetitif-dasar | Page 29

2.5 Kombinatorika
aturan perkalian dalam permasalahan ini, karena antara perjalanan dari kota A menuju kota C
melalui kota B dengan tanpa melalui kota B merupakan 2 proses yang berbeda. Oleh karena itu,
kita dapat menggunakan aturan penjumlahan.
Misalkan suatu proses dapat dibagi menjadi N himpunan proses berbeda yaitu H 1 , H 2 , H 3 ,
..., H N dengan setiap himpunannya saling lepas (tidak beririsan). Menurut aturan penjumlahan,
banyak cara yang berbeda untuk menyelesaikan proses tersebut adalah |H 1 | + |H 2 | + |H 3 | + ... +
|H N | dengan |H i | merupakan banyaknya cara berbeda untuk menyelesaikan proses ke-i.
Kita akan mencoba mencari banyaknya cara menuju kota C dari kota A menggunakan aturan
perkalian. Proses perjalanan dari kota A menuju kota C dapat kita bagi menjadi 2 himpunan
proses yang berbeda, yaitu:
• Dari kota A menuju kota C melalui kota B, yang dapat kita dapatkan dengan aturan perkalian
seperti yang dibahas pada permasalahan sebelumnya, yaitu 6 cara berbeda, dan
• Dari kota A langsung menuju kota C, yang mana terdapat 1 cara, yaitu melalui jalur e 6 .
Dengan aturan penjumlahan, banyak cara berbeda dari kota A menuju kota C adalah 6 + 1 = 7
cara berbeda.
Untuk aturan penjumlahan, hati-hati apabila terdapat irisan dari himpunan proses tersebut.
Ketika terdapat irisan, maka solusi yang kita dapatkan dengan aturan penjumlahan menjadi tidak
tepat, karena ada solusi yang terhitung lebih dari sekali. Agar solusi tersebut menjadi tepat,
gunakan Prinsip Inklusi-Eksklusi pada teori himpunan.
2.5.2
Permutasi
Permutasi adalah pemilihan urutan beberapa elemen dari suatu himpunan. Untuk menyele-
saikan soal-soal permutasi, dibutuhkan pemahaman konsep faktorial.
Sebagai pengingat, faktorial dari N, atau dinotasikan sebagai N!, merupakan hasil perkalian
dari semua bilangan asli kurang dari atau sama dengan N. Fungsi faktorial dirumuskan sebagai
berikut:
N! = N × (N − 1) × (N − 2) × ... × 3 × 2 × 1
Dengan 0! = 1.
Contoh: 5! = 5 × 4 × 3 × 2 × 1 = 120.
Sebelum masuk ke permutasi, kita perlu mengetahui tentang aturan pembagian yang
terkadang disebut juga sebagai redundansi. Menurut aturan pembagian, apabila terdapat K
susunan cara berbeda yang kita anggap merupakan 1 cara yang sama, maka kita dapat membagi
total keseluruhan cara dengan K, sehingga K cara tersebut dianggap sama sebagai 1 cara.
Sebagai contoh, banyak kata berbeda yang disusun dari huruf-huruf penyusun "TOKI" adalah
4! (menggunakan aturan perkalian). Apabila kita ganti soal tersebut, yaitu kata berbeda yang
disusun dari huruf-huruf penyusun "BACA", solusi 4! merupakan solusi yang salah. Sebab,
terdapat 2 buah huruf ’A’. Sebagai contoh: BA 1 CA 2 dan BA 2 CA 1 pada dasarnya merupakan kata
yang sama. Terdapat 2! cara berbeda tetapi yang kita anggap sama, yaitu penggunaan A 1 A 2 dan
A 2 A 1 . Sehingga menurut aturan pembagian, banyak kata berbeda yang dapat kita bentuk dari
huruf-huruf penyusun kata "BACA" adalah:
4! 24
=
= 12
2!
2
19