KOMBINATORIAL
Kombinatorial adalah cabang
matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus
mengenumerasi semua kemungkinan susunannya.
Kaidah Dasar Menghitung
1. Kaidah Perkalian (rule of product)
Misalkan percobaan 1 mempunyai p
hasil percobaan, dan percobaan 2 mempunyai q hasil, maka bila percobaan 1 dan
percobaan 2 dilakukan akan terdapat p × q hasil percobaan.
2. Kaidah Penjumlahan (rule of sum)
Misalkan percobaan 1 mempunyai p
hasil percobaan, dan percobaan 2 mempunyai q hasil, maka bila percobaan 1 atau
percobaan 2 dilakukan (hanya salah satu percobaan saja yang
dilakukan) akan
terdapat p + q hasil percobaan.
Permutasi
Permutasi adalah jumlah urutan yang
berbeda dari pengaturan objek-objek. Permutasi merupakan bentuk khusus aplikasi
kaidah perkalian.
Misalkan jumlah
objek adalah n, maka
Urutan pertama
dipilih dari n objek,
urutan kedua
dipilih dari (n – 1) objek,
urutan kedua
dipilih dari (n – 2) objek,
…
urutan terakhir
dipilih dari 1 objek yang tersisa.
Menurut kaidah perkalian, permutasi
dari n objek adalah n(n – 1)(n – 2) … (2)(1) = n!
Rumus
permutasi-r (jumlah susunan berbeda dari pemilihan r objek yang diambil dari n
objek), dilambangkan dengan P(n,r):
Kombinasi.
Bentuk khusus dari permutasi adalah
kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada
kombinasi, urutan kemunculan diabaikan.
Rumus
kombinasi-r (jumlah pemilihan yang tidak terurut r elemen yang diambil dari n
buah elemen), dilambangkan dengan C(n,r) atau ( n r ) .
Interpretasi Kombinasi.
1. C(n, r) =
banyaknya himpunan bagian yang terdiri atas r elemen yang dapat dibentuk dari himpunan
dengan n elemen.
2. C(n, r) =
cara memilih r buah elemen dari n elemen yang ada, tetapi urutan elemen di
dalam susunan hasil pemilihan tidak penting.
Permutasi dan Kombinasi Bentuk Umum
Misalkan terdapat n buah bola yang
tidak seluruhnya berbeda warna (ada beberapa bola berwarna sama – indistinguishable).
n1 bola di
antaranya berwarna 1,
n2 bola di
antaranya berwarna 2,
…
nk bola di
antaranya berwarna k,
dan n1 + n2 + …
+ nk = n.
Berapa jumlah
cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maksimal
1 buah bola)?
Penyelesaian:
Jika n buah bola
itu kita anggap berbeda semuanya, maka jumlah cara pengaturan n buah bola ke
dalam n buah kotak adalah P(n, n) = n!
Dari pengaturan
n buah bola itu,
Terdapat n1!
cara memasukkan bola berwarna 1,
terdapat n2!
cara memasukkan bola berwarna 2,
…
terdapat nk!
cara memasukkan bola berwarna k.
Permutasi n buah
bola yang mana n1 di antaranya berwarna 1, n2 bola berwarna 2
Kombinasi dengan Pengulangan
Misalkan terdapat r buah bola yang
semua warnanya sama dan terdapat n buah kotak, serta ketentuan sebagai berikut:
1. Masing-masing
kotak hanya boleh diisi paling banyak satu buah bola.
Jumlah cara
memasukkan bola adalah C(n, r).
2. Masing-masing
kotak boleh diisi lebih dari satu buah bola (tidak ada pembatasan jumlah bola).
Teori Peluang
Kombinatorial dan teori peluang
(probability) berkaitan sangat erat. Teori peluang banyak menggunakan
konsep-konsep dalam kombinatorial. Sebenarnya kedua bidang ini lahir dari arena
judi (gambling games) – salah satu kasusnya adalah menghitung peluang munculnya
nomor lotre tertentu. Meskipun demikian, aplikasi kombinatorial dan teori
peluang saat ini telah meluas ke berbagai bidang ilmu lain maupun dalam
kehidupan nyata seperti ilmu statistika, fisika, ekonomi, biologi, dan berbagai
bidang ilmu lainnya.
Terminologi Dasar
Ruang Contoh dari suatu percobaan
adalah himpunan semua kemungkinan hasil percobaan yang bersangkutan.
Titik Contoh
(sample point)
Titik Contoh adalah setiap hasil
percobaan di dalam ruang contoh. Hasil-hasil percobaan tersebut bersifat saling
terpisah (mutually exclusive) karena dari seluruh ruang contoh, hanya satu
titik contoh yang muncul.
Misalnya pada percobaan melempar
dadu, hasil percobaan yang muncul hanya salah satu dari 6 muka dadu, tidak
mungkin muncul dua muka atau lebih, atau tidak mungkin salah satu dari enam
muka dadu tidak ada yang muncul.
Kejadian (event)
Kejadian ini dapat disimbolkan
dengan E– adalah himpunan bagian dari ruang contoh. Misalnya pada percobaan
melempar dadu, kejadian munculnya angka ganjil adalah E = {1,3,5}, kejadian
munculnya angka 1 adalah E = {1}.
Kejadian yang hanya mengandung satu
titik contoh disebut kejadian sederhana (simple
event), sedangkan kejadian yang mengandung lebih dari satu titik contoh
disebut kejadian majemuk (compound event).
Peluang Kejadian
Peluang Kejadian E di dalam ruang
contoh S dapat diartikan sebagai jumlah peluang semua titik contoh di dalam E.
Logika Permainan sudoku
Sudoku merupakan permainan angka
yang berasal dari Jepang. Permainan ini menggunakan kotak 9x9 yang di dalamnya
sudah terdapat beberapa angka petunjuk, dan kita diminta untuk melengkapi
angka-angka tersebut dengan aturan, tidak ada angka yang sama pada satu baris,
satu kolom, atau satu kotak bagian 3x3 yang ditandai garis tebal. Karena semua aturan
itu, dalam permainan Sudoku pasti kemunculan setiap angka tepat 9 kali, dari
angka yang sudah ada dari awal permainan ditambah dengan angka yang dimasukkan
pemain. Permainan ini dapat dilakukan sendirian ataupun bekerja sama dengan
orang lain.
Logika
Logika merupakan dasar dari semua
proses penalaran. Dengan logika, kita tahu apa yang benar, apa yang salah, dan
apa yang masih tergantung pada variabel lain. Tanpa logika, kita tidak dapat
melakukan proses problem solving, oleh karena itu logika merupakan kemampuan
yang sangat dasar dalam kehidupan terutama bagi para saintis dan insinyur yang
memerlukan proses berpikir sistematis. Sudoku sebagai permainan yang memerlukan
pemikiran sistematis tentunya membutuhkan logika. Oleh karena itu, pada makalah
ini akan dibahas logika bermain Sudoku yang sering kali tidak terpikirkan orang
banyak.
Notasi
Untuk mempermudah penjelasan, kita
membutuhkan notasi dan catatan kecil. Catatan kecil yang dimaksudkan adalah
penulisan kemungkinan angka pada suatu kotak. Oleh karena itu, kita akan
melihat terkadang terdapat lebih dari satu angka pada suatu kotak di gambar
contoh. Itu akan mempermudah kita
untuk memperkirakan apa isi suatu kotak.
Untuk notasi,
kita menggunakan notasi seperti berikut.
U : himpunan
universe, {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Kij :
menunjukkan kotak pada baris i, kolom j.
Pij :
menunjukkan himpunan kemungkinan angka pada baris i, kolom j.
Bi : menunjukkan
himpunan angka yang telah muncul pada baris i.
BiX :
menunjukkan himpunan kotak pada baris i yang mungkin diisi oleh angka X.
Klj :
menunjukkan himpunan angka yang telah muncul pada kolom j.
KljX :
menunjukkan himpunan kotak pada kolom j yang mungkin diisi oleh angka X.
Ktx :
menunjukkan himpunan angka yang telah muncul pada kotak x.
Komentar
Posting Komentar