Selamat Datang

Kombinatorika adalah salah satu cabang ilmu komputer teoritik yang mempelajari obyek-obyek diskrit. Obyek diskrit adalah obyek yang dapat dinyatakan melalui sejumlah aturan tertentu atau obyek yang memenuhi sejumlah kriteria tertentu. Dalam Kombinatorika obyek-obyek seperti itu disebut obyek kombinatorika, yang sering disingkat sebagai obyek saja. Obyek Kombinatorika terdapat di mana-mana. Dia dapat berupa sesuatu yang nyata maupun abstrak. Sebuah sub-himpunan (dari himpunan hingga/finite), sebuah susunan angka dalam kubus ajaib (magic square) (atau yang semacamnya seperti sudoku), sebuah permutasi dari himpunan hingga bilangan bulat [n] = {1,2, …, n}, dan sebuah struktur pohon biner dengan n simpul adalah sekedar contoh populer obyek-obyek kombinatorial yang semuanya dapat dinyatakan melalui sejumlah aturan tertentu atau memenuhi sejumlah criteria tertentu.

 

Kumpulan obyek-obyek kombinatorial dinamakan kelas kombinatorial, atau singkatnya kelas saja. Misalkan N adalah himpunan bilangan bulat non-negatif; secara formal dan operasional sebuah kelas A adalah sebuah himpunan (hingga atau terhitung/countably infinite) yang di dalamnya didefinisikan sebuah fungsi ukuran (size function) f : A ® N. Fungsi tersebut member dua persyaratan sederhana berikut: ukuran setiap obyek dalam kelas kombinatorial dinyatakan sebagai bilangan bulat non-negatif sedangkan banyaknya obyek dengan ukuran tersebut adalah hingga; dengan kata lain, untuk setiap n Î N, An = {α Î A, |α| = n} adalah himpunan hingga. Sebagai contoh, bayangkan obyek-obyek untai biner dalam himpunan B = {0, 1, 00, 01, 10, 11, 000, 001, 010, …, 1001101, …}, dan B2 = {11, 01, 10, 00}. Jelas terlihat bahwa ukuran setiap obyek dalam B2 adalah bilangan bulat non-negatif (yaitu 2) sedangkan banyaknya obyek dalam kelas B2 adalah hingga (yaitu 4).

 

Bayangkan sebuah obyek dengan struktur tertentu; dalam Kombinatorika, pertanyaan pertama yang ingin dijawab adalah: mungkinkah struktur tersebut dapat dikonstruksi melalui kriteria-kriteria tertentu atau penetapan aturan-aturan tertentu? Jika mungkin, pertanyaan kedua adalah: ada berapa struktur berukuran sama yang juga dapat dikonstruksi melaui prosedur yang sama? Upaya untuk menjawab pertanyaan kedua ini diformalkan sebagai problem enumerasi atau pencacahan. Contoh hasil-hasil enumerasi adalah formula berikut: (1) an = n! yang menyatakan banyaknya cara menyusun n obyek, (2) cn,k = n!/(k!(n-k)!) yang menyatakan kombinasi k obyek dari nk obyek, (3) cn = c2n,n /(n+1) yang di antaranya mencacah banyaknya struktur pohon biner yang mempunya n simpul, (4) dan masih banyak lagi. Ketiga contoh formula pencacahan di atas adalah formula yang sangat dikenal; yang pertama adalah bilangan factorial, yang kedua koefisien binomial, dan yang ketigabilangan Catalan.

 

Jika terdapat dua kelas kombinatorial dengan kardinalitas sama, pertanyaan ketiga adalah: dapatkah dikonstruksi bijeksi alamiah (natural bijection) di antara keduanya? Upaya untuk menjawab pertanyaan ketiga ini pada gilirannya akan membawa kita ke problem pembuktian kombinatorial atau pembuktian bijektif. Pembuktian kombinatorial adalah metoda pembuktian atas sebuah pernyataan (atau kalimat matematika), biasanya berupa sebuah kesamaan kombinatorial, melalui pencacahan obyek-obyek yang dipilih secara hati-hati, dengan memperhatikan berbagai sifat dari struktur obyek tersebut. Selanjutnya dilakukan pencacahan ulang dengan cara berbeda yang tujuannya untuk mendapatkan ekspresi berbeda dari pernyataan asal. Salah satu contoh sederhana pembuktian kombinatorial adalah kesamaan koefisien binomial cn,k = cn,n-k. Di pihak lain, pembuktian bijektif adalah sebuah teknik pembuktian untuk mendapatkan fungsi bijektif antara dua himpunan atau dua kelas. R.P. Stanley, professor Advanced Mathematics MIT, mencatat tidak kurang dari 66 konfigurasi yang dapat dicacah dengan bilangan Catalan. Fakta seperti ini merupakan sumber penelitian yang tidak ada habis-habisnya dalam topik pembuktian kombinatorial dan pembuktian bijektif. Tidak jarang dalam proses pembuktian ini ditemukan berbagai sifat baru dari obyek atau bahkan teorema baru dalam kombinatorika atau matematika.

 

Kita juga akan berhadapan dengan masalah pembangkitan obyek (object generation), baik secara acak maupun secara lengkap (exhaustive) ketika kita membangun sebuah algoritma untuk membangkitkan struktur tertentu yang representative untuk tujuan tertentu atau membangkitkan seluruh struktur yang mungkin. Dekat dengan masalah pembangkitan terdapat masalah pengurutan (listing) atas obyek-obyek kombinatorial dalam sebuah kelas; dua strategi pengurutan terkenal adalah pengurutan leksikografik.(lexicographic code listing) dan pengurutan kode Gray (Garycode listing). Pengurutan leksikografik adalah pengurutan alfabetis sedangkan dua obyek beurutan di dalam urutan kode Gray mempunyai perbedaan struktur yang kecil. Seperti pada masalah kompleksitas algoritma di mana waktu minimal dan optimal yang diberikan algoritma belum tercapai, di dalam problem pengurutan inipun kondisi optimal beberapa kelas untuk mendapatkan perbedaan struktur yang kecil dan optimal juga belum tercapai. Demikianlah ranah penelitian masalah pengurutan terus berkembang.

 

Ranah penelitian terakhir dalam Kombinatorika adalah masalah optimasi (optimization problem). Beberapa contoh populer masalah optimasi adalah masalah transportasi, masalah lintasan terpendek, dan masalah perjalanan penjual (traveling salesman problem, TSP). Setiap kemungkinan konfigurasi transportasi (atau lintasan terpendek atau TSP) adalah sebuah obyek kombinatorial. Setiap konfigurasi mempunyai nilai tertentu melalui aturan-aturan yang sesuai dengan masalah yang sedang dihadapi. Setiap konfigurasi beserta nilai-nilainya dibangkitkan secara lengkap (atau acak jika cara ini memungkinkan) dengan algoritma pembangkitan yang diketahui (atau bias saja algoritma yang khusus dikonstruksi untuk masalah yang dihadapai), atau jika diperlukan menggunakan algoritma pengurutan. Berdasarkan nilai-nilai tersebut nilai optimal ditentukan.

 

Yang terakhir, kita dapat mengkaji te-tema kombinatorika yang lebih dalam. Dengan mengamati struktur dan susunan obyek-obyek kita dapat membangun teori grup untuk suatu masalah kombinatorika.