Mendaftar : Bagaimana cara mendaftarkan kemungkinan-kemungkinan susunan objek?

Jenis permasalahan yang kita bicarakan sebelumnya adalah menemukan salah satu susunan objek yang harus memenuhi sejumlah syarat tertentu.

Kadang-kadang kita memerlukan bukan hanya salah satu susunan objek saja, melainkan seluruh kemungkinan susunan objek yang dapat dibuat. Sebagai contoh, ada tiga buah kata sebagai berikut.

Bagaimana kamu akan mendaftarkan kemungkinan-kemungkinan susunan kata tersebut? Cobalah mencoret-coret kemungkinan-kemungkinannya di atas kertas, baru setelah itu silakan melihat daftar lengkapnya pada bagian di bawah ini.

Tentunya cukup mudah untuk mendaftarkan kemungkinan-kemungkinan susunan kata-kata tersebut. Namun ini mudah karena kata yang disediakan hanya 3 saja. Untuk mendaftar kemungkinan susunan 10 kata, misalnya, kamu akan memerlukan suatu algoritma tertentu.

Permasalahan ini masih termasuk dalam permutasi. Permutasi membicarakan susunan objek yang terangkai dalam berbagai urutan. Namun berbeda dari bagian sebelumnya yang hanya mengharapkan satu kemungkinan, kali ini kita berusaha mendaftarkan seluruh kemungkinan susunannya. Permasalahan pendaftaran ini juga disebut sebagai enumerasi.

Mendaftarkan posisi Kaleb dan teman-temannya

Dalam permasalahan posisi duduk Kaleb dan teman-temannya, kita dapat mendaftarkannya sebagai berikut:

• Faisal, Kevin, Siska, Rosita, Kaleb
• Faisal, Siska, Kevin, Rosita, Kaleb
• Kevin, Faisal, Siska, Rosita, Kaleb
• Kevin, Siska, Faisal, Rosita, Kaleb
• Siska, Faisal, Kevin, Rosita, Kaleb
• Siska, Kevin, Faisal, Rosita, Kaleb

Terlihat bahwa karena posisi Rosita dan Kaleb sudah pasti, maka kita cukup membolak-balik posisi Faisal, Kevin, dan Siska.

Perhatikan bahwa jika nama Faisal diganti Tidak, Kevin diganti Jadi, dan Siska diganti Bisa, maka permasalahan ini tepat sama dengan permasalahan yang kita bahas di atas. Dalam kombinatorika (dan sebenarnya matematika secara umum), kita bisa mengganti permasalahan yang satu dengan permasalahan lain yang sudah kita ketahui jawabannya sehingga kita tidak perlu lagi berpikir dari nol.

Go Ae-rin lagi

Go Ae-rin juga mendaftarkan segala kemungkinan kode yang dibentuk oleh digit 2, 8, dan 9. Kamu bisa melihat tulisan pada kertasnya.

Tetris

Tetris adalah permainan komputer yang dibuat oleh Alexey Pajitnov, seorang Soviet, pada tahun 1984. Permainan ini sangat terkenal hingga hari ini.

Dalam permainan tetris, pemain disediakan blok-blok persegi yang disusun dalam berbagai bentuk, yang secara silih berganti dijatuhkan dari atas layar yang lebarnya adalah 10 blok. Jika pemain bisa membentuk satu baris penuh blok, maka baris itu akan menghilang dan baris di atasnya akan turun menempati baris sebelumnya. Permainan ini sebenarnya tanpa tujuan. Pemain hanya terus menerus mengatur rotasi bentuk dan letak jatuhnya agar layar tidak penuh. (Yah ini bisa dipandang sebagai tujuan juga.) Namun ini yang membuatnya seru karena menuntut konsentrasi, strategi, dan kecepatan berpikir maupun bertindak.

Nama Tetris memiliki akar kata tetra yang berarti empat. Setiap bentuk dalam permainan Tetris tersusun atas empat blok persegi. Bentuk-bentuk dalam permainan ini disebut sebagai tetromino.

Setiap tetromino terdiri dari 4 blok, dan masing-masing blok mengandung sisi yang dimiliki bersama dengan blok yang lain (alias sisinya ditempel pada sisi blok lain). Salah satu bentuk yang mungkin adalah bentuk berikut ini:

Tentunya ada sejumlah tetromino yang harus dianggap sama (identik), yaitu tetromino yang dapat diperoleh dengan cara memutar tetromino yang lain. Dalam istilah matematika ini disebut sebagai invarian terhadap perputaran (rotational invariant).

Coba daftarkan semua kemungkinan tetromino dalam permainan Tetris!

Pertanyaan-pertanyaan yang dapat diajukan terkait tetromino:

• Bagaimana membuktikan bahwa daftar tetromino ini sudah komplet?
• Apakah jika rotasi dapat dilakukan dalam tiga dimensi, daftarnya masih sama?
• Dalam tetromino, setiap blok terhubung melalui sisi persegi. Jika setiap blok diizinkan untuk terhubung melalui titik sudut dengan titik sudut blok lainnya, daftarnya akan menjadi seperti apa?
• Bagaimana dengan pentomino (bentuk yang tersusun atas 5 blok) atau n-mino yang lebih tinggi?

Sampai di sini, mungkin kamu akan berpikir bahwa kombinatorika hanya digunakan untuk urusan yang tidak terlalu serius semacam permainan dan puzzle. Namun itu tidak benar. Selama ada kumpulan objek, di sana ada kombinatorika.

Isi roti

Seandainya kamu membuat roti dan kamu juga memiliki bahan untuk isinya, yaitu coklat. Maka kamu dapat menjual setidaknya dua macam variasi roti:

• Roti kosong
• Roti coklat

Namun ketika kamu menambahkan satu bahan lagi, misalnya keju, kamu akan dapat menjual variasi yang lebih banyak:

• Roti kosong
• Roti coklat
• Roti keju
• Roti coklat-keju

Perhatikan bahwa proses pendaftaran variasi roti ini dapat dilakukan dengan suatu algoritma tertentu. Dalam contoh ini, pertama kita mendaftar roti dengan 0 kombinasi isi, yaitu roti kosong. Kemudian kita melanjutkan dengan daftar 1 kombinasi isi, baru 2 kombinasi isi. Dengan cara yang sama, kamu bisa mendaftar variasi roti dengan 3 macam isi:

• Roti kosong
• Roti coklat
• Roti keju
• Roti pisang
• Roti coklat-keju
• Roti coklat-pisang
• Roti keju-pisang
• Roti coklat-keju-pisang

Hal ini dalam kombinatorika disebut sebagai permasalahan kombinasi.

Berikutnya: Menghitung