Untai biner hindar 11

Kelas untai biner (binary words) bukanlah kelas yang asing dalam kombinatorika. Ia adalah kelas untai yang simbolnya terdiri dari 0 atau 1, semisal 0010, 1110100110, dan sebagainya. Himpunan untai biner ${s_1} \ldots {s_n}$ memiliki kardinalitas $2^n$ (karena setiap ${s_i}$ dapat bernilai 0 atau 1). Sebagai contoh, terdapat ${2^3} = 8$ untai biner dengan panjang 3, yaitu 000, 001, 010, 011, 100, 101, 110, dan 111.

Bagaimana dengan kelas untai biner hindar 11? Nama kelas ini, yang dalam bahasa Inggrisnya disebut binary words avoiding two consecutive ones, terdengar tidak familiar. Dari istilahnya, dapat diketahui bahwa ia adalah kelas untai biner yang tidak memuat dua simbol ‘1’ secara berurutan. Sebagai contoh, 0010100, 101001010 adalah untai biner hindar 11, sedangkan 110111000 bukan. Tabel berikut adalah himpunan untai biner dengan panjang $n$, untuk $n = 1,2,...,5$, yang diperoleh dengan cara menuliskan semua untai biner dengan panjang $n$ tertentu, dan mencoret untai yang memuat '11'. Di baris paling bawah adalah kardinalitasnya untuk setiap $n$.

Jika diperhatikan kardinalitasnya, membentuk pola barisan apakah ia? Barisan Fibonacci! Berdasarkan pola ini, anda tentu dapat mengetahui kardinalitas kelas di atas untuk n=6,7, dan seterusnya. Salah satu kajian algoritmis tentang kelas ini diberikan oleh Vajnovszki (2001)

Kombinatorika Enumeratif

Hal menarik dan menjadi tantangan dalam kombinatorika adalah: berapakah kardinalitas (banyaknya anggota) untuk suatu himpunan objek kombinatorial? Ini adalah kajian mendasar dari kombinatorika enumeratif. Sebagai contoh: terdapat 120 permutasi himpunan {H,I,J,K,L}. Dengan kata lain, 210 adalah kardinalitas dari permutasi himpunan {H,I,J,K,L}. Terdapat 210 cara untuk memilih 4 sukarelawan dari 10 orang yang ada. Umumnya siswa sekolah menengah dapat memahami konsep kardinalitas dalam permutasi dan kombinasi, dan memecahkan variasi dari masalah-masalah tersebut, sebagaimana contoh berikut ini:

Berapakah banyak plat nomor kendaraan yang dapat dibentuk, jika plat nomor tersebut diawali dengan huruf B, diikuti empat angka (tidak diawali angka 0), dan diakhiri dengan tiga huruf?

Pertanyaan yang sama, namun jika angkanya hanya terdiri dari tiga angka?

Pertanyaan yang sama, namun jika diakhiri dengan dua huruf?

Terdapat beberapa cara untuk menemukan kardinalitas dari himpunan objek kombinatorial. Cara pertama adalah dengan menggunakan formula eksplisit. Cara ini bersifat "straightforward", langsung memperoleh hasil dengan sekali jalan. Contohnya, kardinalitas dari permutasi $n$ objek diberikan oleh formula $n!$ (dibaca: n faktorial). Contoh: $5!=5\times 4\times 3\times 2\times 1=120$, dan $10!=10\times 9\times\ldots\times 2\times 1=3.628.800$. Banyaknya himpunan bagian dari himpunan $n$ objek adalah $2^n$. Misalnya, himpunan dengan 3 anggota $\{a,b,c\}$ memiliki $2^3$ himpunan bagian, yaitu: $\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}, \{a,b,c\}$ dan $\{\}$ (himpunan kosong) (demikian pula kardinalitas untai biner dengan panjang $n$).

Cara kedua adalah dengan menggunakan formula rekurensi.  Kardinalitas dari untai biner dengan panjang $n$ yang tidak memuat simbol '11' (dua angka 1 yang berurutan) diberikan oleh $f(n) = f(n - 1) + f(n - 2)$, di mana f$(1) = f(2) = 1$ (baca artikel ini). Pastinya anda mengenal bahwa $f(n)$ adalah suku ke $n$ dari barisan Fibonacci. (Sekedar diingat, pola barisan Fibonacci adalah 1,1,2,3,5,8,13, dst. Suku berikutnya adalah jumlah dari dua suku sebelumnya). Perhatikan bahwa $f(n)$ adalah fungsi rekurensi. Berbeda dengan fungsi eksplisit, fungsi rekurensi tidak bersifat straightforward, karena perlu beberapa tahap untuk mengevaluasi nilai fungsi pada $n$ tertentu. Sebagai contoh: untuk menghitung $f(5)$ dilakukan dengan cara berikut:

$$\begin{array}{l} f(5) = f(4) + f(3)\\  = (f(3) + f(2)) + (f(2) + f(1))\\  = ((f(2) + f(1)) + f(2)) + (f(2) + f(1))\\  = ((1 + 1) + 1) + (1 + 1)\\  = 5 \end{array}$$

Cara ketiga adalah dengan menggunakan formula asimtotis  $f(n) \sim g(n)$, yang secara naif berarti $g(n)$ semakin mendekati $f(n)$ untuk nilai $n$ yang cukup besar. Secara matematis berlaku  $\lim \limits_{x \to \infty } \frac{{f(n)}}{{g(n)}} = 1$. Misalnya, ada berapa banyak permutasi 20 objek? Menghitung 20! secara eksak adalah pekerjaan yang "boros" bagi komputer.  Selain itu mungkin perlu ditinjau kembali, apakah dibutuhkan hasil yang eksak atau cukup dengan aproksimasi saja? Jika hanya membutuhkan aproksimasi, maka n! dapat didekati oleh $\sqrt {2\pi n} {\left( {\frac{n}{e}} \right)^n}$. Untuk $n=20$, formula asimtotis ini memberikan hasil $2,4228 \times {10^{18}}$, sedangkan hasil eksaknya adalah  $2.432.902.008.176.640.000$.

Cara keempat adalah dengan menggunakan fungsi pembangkit (generating function). Ekspansi dari fungsi pembangkit mensimulasikan semua objek pada kelas tersebut. Setiap suku merepresentasikan sebuah kemungkinan objek yang dapat dibentuk, dan koefisien untuk suku tersebut merepresentasikan ada berapa cara membentuk objek tersebut. Jadi, yang diinginkan dari fungsi pembangkit adalah koefisien-koefisien pada suku-sukunya, dan bukan nilai fungsi tersebut.  Sebagai contoh, diberikan himpunan {q,r,s,t,u}. Ada berapakah subhimpunan tiga anggota yang dapat dibentuk? Atau pertanyaan matematisnya: ada berapa banyak 3-subhimpunan dari {q,r,s,t,u}? Karena himpunannya hanya terdiri dari 5 elemen, kita dapat menuliskan semua kemungkinannya yaitu: {q,r,s}, {q,r,t}, {q,r,u}, {q,s,t}, {q,s,u}, {q,t,u}, {r,s,t}, {r,s,u}, {r,t,u}, {s,t,u}. Terdapat 10 kemungkinan subhimpunan, dan itulah jawaban dari masalah ini.

Sekarang kita cari pemecahannya dengan menggunakan fungsi pembangkit. Fungsi pembangkit dari masalah ini diberikan oleh ${(x + y)^5}$. Namun ini bukan jawaban dari permasalahan ini, karena jawabannya terdapat pada koefisien dari ekspansi fungsi pembangkit. Mengapa demikian?  Misalkan x melambangkan sebuah "elemen anggota subhimpunan", dan y melambangkan sebuah "elemen bukan anggota subhimpunan". Oleh karena itu, ekspresi ${x^m}{y^n}$ melambangkan "terdapat $m$ elemen anggota subhimpunan", dan "terdapat $n$ elemen bukan anggota subhimpunan" (dalam masalah ini, $m+n=5$). Karena subhimpunan yang dimaksud terdiri atas tiga elemen, maka subhimpunan ini direpresentasikan sebagai ${x^3}{y^2}$, dan ini dapat berarti: $xxxyy$, $xxyxy$, $xxyyx$, $xyxxy$,  $xyxyx$, $xyyxx$, $yxxxy$, $yxxyx$, $yxyxx$, $yyxxx$. Terdapat 10 kemungkinan. Namun mencacah dengan cara ini tentu sangat merepotkan. Cara yang lebih efisien adalah cukup dengan mengekspansi ${(x + y)^5}$, dan jawabannya ada pada koefisien untuk suku ${x^3}{y^2}$. Ekspansi dari ${(x + y)^5}$ adalah ${x^5} + 5{x^4}y + 10{x^3}{y^2} + 10{x^2}{y^3} + 5x{y^4} + {y^5}$, dan koefisien dari suku ${x^3}{y^2}$ adalah 10, yang merupakan jawaban dari masalah ini.

Permutasi dan Kombinasi

Terdapat demikian banyaknya kelas kombinatorial. Berdasarkan konteks pengkajiannya, kelas kombinatorial disajikan dalam representasi tertentu, antara lain dalam bentuk graf, diagram, matriks, ataupun untai/barisan (string/words/sequences). Contohnya, permutasi dan kombinasi umumnya direpresentasikan dalam bentuk barisan, dan mereka merupakan kelas yang sangat familiar bagi para pelajar sekolah menengah. Namun, tentunya kelas-kelas kombinatorial tidak hanya itu. Berikut disajikan beberapa kelas kombinatorial yang cukup familiar.

Permutasi

Misalkan di sebuah taman terdapat  sebuah bangku panjang yang dapat memuat 3 orang. Pada saat yang bersamaan, ada tiga orang, sebut saja A, B, dan C, yang ingin duduk di bangku tersebut. Ada berapakah kemungkinan urutan duduk dari ketiga orang itu pada bangku tersebut?

Ketiga orang tersebut dapat duduk dalam enam kemungkinan urutan: ABC, ACB, BAC, BCA, CAB, dan CBA. Nah, setiap kemungkinan urutan itu disebut sebagai permutasi, atau lengkapnya permutasi dari himpunan $\{A,B,C\}$. Dalam hal ini, permutasi memiliki kardinalitas 6.  Ilustrasi berikut menggambarkan keenam kemungkinan tersebut:

6 kemungkinan posisi duduk untuk A, B, dan C.

Bagaimana jika ada empat orang yang ingin duduk? Tentu satu orang tidak mendapat tempat, sehingga ia harus berdiri. Jika si D yang berdiri, maka A, B, dan C memiliki enam cara untuk duduk. Demikian pula jika si A yang berdiri, maka B,C, dan D memiliki enam cara untuk duduk. Sama halnya jika, B atau C yang berdiri, maka ketiga orang lainnya memiliki enam cara untuk duduk. Jadi, jawaban dari persoalan ini adalah: terdapat 24 susunan duduk untuk tiga orang dari empat orang yang ada. Persoalan ini dapat dikatakan sebagai permutasi 3 dari 4, dan dinotasikan sebagai $P(4,3)$ (notasi lainnya adalah $_4P_3$, $P_4^3$, dan $P_{4,3}$ ).

Masih meneruskan persoalan di atas, bagaimana jika ada lima orang yang ingin duduk? Jawabannya adalah permutasi 3 dari 5, atau $P(5,3)=60$. Jika enam orang? Jawabannya adalah $P(6,3)=120$. Pertanyaan yang lebih umum: bagaimana jika terdapat $n$ orang? Jawabannya adalah $P(n,3)$.

Nah, bagaimana kalau kapasitas bangkunya yang ditambah. Misalkan kita ganti bangkunya dengan yang lebih besar sehingga mampu memuat empat orang. Jika ada empat orang yang ingin duduk, maka jawabannya adalah permutasi 4 dari 4 (dalam hal ini cukup disebut sebagai permutasi-4), dinotasikan sebagai $P_4$. Jika ada lima orang? Jawabannya adalah $P(5,4)=120$.

Sekarang, kita bicara secara umum: jika sebuah bangku dapat memuat $k$ orang dari $n$ orang yang ada, terdapat berapa kemungkinan susunan duduk $k$ orang tersebut pada bangku? Tapi tunggu dulu. Sebelum dijawab, kita harus menyadari bahwa masalah ini tentu tidak hanya untuk bangku taman. Oleh karena itu, kita dapat mengajukan pertanyaan yang lebih umum, yaitu: ada berapa cara untuk mengurut $k$ objek dari $n$ objek yang tersedia? Jawabannya adalah $P(n,k)=\frac{n!}{(n-k)!}$.

Kombinasi

Sebuah klub olahraga futsal memiliki anggota 12 orang anggota.  Pada suatu kompetisi, sang pelatih akan memilih 5 orang di antara mereka untuk membentuk sebuah tim bertanding. Anggaplah semua anggota memiliki skill yang sama, sehingga setiap orang memiliki kesempatan yang sama untuk dipilih. Ada berapa kemungkinankah tim bertanding yang dapat dibentuk?
Dalam permasalahan ini, urutan pemilihan tidaklah penting. Tim yang beranggotakan si A, B, C, D, dan E, adalah sama dengan tim yang beranggotakan si C, E, D, B, dan A. Nah, karena urutan pemain tidak penting, maka masalah ini disebut masalah kombinasi. Setiap kemungkinan tim yang dapat dibentuk disebut kombinasi 5 orang dari 12 orang, atau singkatnya, kombinasi 5 dari 12, dan dinotasikan sebagai $C(12,5)$.
Secara umum, $C(n,k)=\frac{n!}{k!(n-k)!}$, sehingga $C(12,5)=792$. Jadi, terdapat 792 kemungkinan tim yang dapat dibentuk.

Sekilas tentang kombinatorika

Kombinatorika secara umum dikatakan sebagai "matematika pencacahan"; lebih lengkapnya, ia adalah matematika tentang pencacahan (enumerasi), eksistensi, konstruksi, dan optimisasi berkenaan dengan himpunan hingga yang memenuhi konfigurasi tertentu. 

Himpunan-himpunan yang memiliki konfigurasi sama tersebut membentuk suatu "kelas kombinatorial", yaitu kumpulan objek sejenis yang mengemban sejumlah sifat-sifat kombinatorika. 

Dalam kehidupan sehari-hari, sebuah koin mata uang dipandang sebagai sebuah objek. Namun secara kombinatorika, koin dapat dianggap sebagai dua buah objek, yaitu: koin dengan sisi angka, dan koin dengan sisi gambar. Karena sifat-sifat kombinatorial inilah, koin membentuk sebuah kelas kombinatorial. Sebuah koin terdiri memiliki dua objek; dua buah koin memiliki empat objek; tiga buah koin memiliki delapan objek, dan seterusnya. Demikian halnya dengan sebuah dadu. Sebuah dadu memiliki enam objek; dua buah dadu memiliki tiga puluh enam objek; dan seterusnya. 

Contoh lainnya, "pakaian" dapat dipandang sebagai suatu kelas kombinatorial. Misalnya sebuah objek pakaian didefinisikan terdiri dari unsur "baju" dan "celana" (karena terdiri dari dua unsur maka dikatakan sebagai "pakaian berukuran 2") Nah, misalkan pula baju dan celana dapat memiliki warna tertentu saja, yaitu biru (B), merah (M), atau kuning (K). Berbagai kemungkinan warna inilah yang memunculkan sifat-sifat kombinatorika pada objek pakaian. Kita dapat memiliki berbagai kemungkinan pakaian yang dapat dibentuk, misalkan  baju kuning, celana merah (KM); baju kuning, celana biru (KB); baju merah, celana kuning (MK), dan berbagai kemungkinan lainnya. 

Kombinatorika "mengabstraksi" objek-objek tersebut. Jadi, tidak terlalu penting apakah objek itu pakaian, mobil, dadu, atau yang lainnya. Agar dapat "dikaji" secara kombinatorika, terdapat sejumlah cara untuk merepresentasikan objek nyata, antara lain dengan graf, barisan (sebutan lainnya untai, kata, string, sequences/words), atau diagram.

Dengan mengabstraksikan objek pakaian sebagai "barisan", terbentuk sebuah himpunan yang memiliki 9 anggota, yang setiap anggotanya berupa barisan berukuran 2, yaitu BB, BM, BK, MB, MM, MK, KB, KM, dan KK, sebagaimana ilustrasi berikut:

Selanjutnya, misalkan didefinisikan pakaian berukuran 3, dengan sebuah unsur tambahan "sepatu". Misalkan pula sepatu memiliki dua kemungkinan warna, yaitu hijau (H) dan coklat (C). Maka akan terbentuk himpunan berukuran 3 yang memiliki 18 anggota yaitu BBH, BBC, BMH, BMC, BKH, BKC, MBH, MBC, MMH, MMC, MKH, MKC, KMH, KMC, KKH, KKC, sebagaimana ilustrasi berikut:

Dengan cara menambah unsur pembentuk pakaian, kita dapat mendapatkan himpunan pakaian berukuran 4, 5, dan seterusnya. Himpunan-himpunan pakaian dengan berbagai ukuran tersebut membentuk sebuah kelas kombinatorial "pakaian".

Nah, untuk kelas pakaian di atas, dapat diajukan pertanyaan-pertanyaan, antara lain:

• Bagaimana cara mengetahui semua kemungkinan kombinasi pakaian dengan ukuran tertentu? Pertanyaan ini terkait dengan konstruksi.
• Bagaimanakah menghitung banyaknya kemungkinan pakaian dengan ukuran tertentu? Pertanyaan ini terkait dengan enumerasi.
• Ada berapa banyak kombinasi pakaian yang mungkin jika celana merah dilarang digunakan? Pertanyaan ini terkait dengan restriksi.
• Pada kelas pakaian yang diuraikan di atas, apakah terdapat pakaian dengan baju putih, celana merah, sepatu putih? Pertanyaan ini terkait dengan eksistensi.

.... dan banyak lagi. Berbagai pertanyaan itulah yang membentuk berbagai kajian dalam kombinatorika, seperti kombinatorika enumeratif, kombinatorika optimasi, aljabar kombinatorika.

Terdapat banyak sekali kelas-kelas kombinatorial, dan mungkin kelas yang paling primitif adalah kelas bilangan biner. Kelas lainnya contohnya adalah permutasi, permutasi multi himpunan, partisi himpunan, partisi integer, dan banyak lagi (bahkan, rantai DNA adalah sebuah kelas kombinatorial). 
Mungkin titik awal lahirnya kombinatorika sebagai cabang formal dari matematika adalah pada tahun 1736 ketika Euler membuktikan ketiadaan solusi pada masalah "Tujuh jembatan Königsberg". Namun, manusia mengenal problem-problem kombinatorika jauh sebelum itu. Umumnya bersifat rekreatif, seperti Chinese rings dan diagram Murasaki. 
Saat ini, kajian-kajian dalam kombinatorika telah diterapkan dalam domain ilmu lainnya, seperti kriptografi, bioinformatika, geometri, statistika, dan bahkan untuk hal-hal rekreatif seperti memecahkan puzzle.