Berpikir Kreatif Bagai Pemula: Kombinatorik

Bermula dari pertanyaan sederhana di kuliah struktur diskrit:

Tentukan banyak penyelesaian bilangan asli dari persamaan .

Ide dalam menyelesaikan persamaan macam ini adalah melalui konsep kombinasi dengan perulangan. Kita ibaratkan permasalahan ini seperti menyimpan 10 bola dalam 4 kotak berbeda. Maka akan ada solusi bilangan asli dari persamaan diatas.

Kali ini saya akan mencoba memberikan pendekatan yang lebih umum dan mudah untuk dibayangkan untuk menyelesaikan soal semacam soal diatas. Berikut deskripsi pola pikir untuk menyelesaikan soal diatas:

Misalkan terdapat 10 bintang dan 3 sekat, sekat-sekat tersebut dapat disimpan diantara dua buah bintang. Maka banyak tempat yang dapat ditempati oleh sekat-sekat tersebut sebanyak tempat.

10 bintang

Lalu, banyak cara untuk menempatkan ketiga sekat adalah cara. Sebagai contoh solusinya adalah yang digambarkan dengan pemisahan 4,3,2, dan 1 bintang oleh ketiga sekat.

4,3,2, dan 1 bintang yang dipisahkan sekat

Ilustrasi yang lebih umum adalah sebagai berikut:

Untuk mencari banyaknya suatu sistem persamaan , dengan untuk dapat digambarkan sebagai banyak cara menempatkan sekat (karena ada tanda tambah) diantara tempat antara dua bintang yang saling berdekatan. Sehingga solusi umum untuk persoalan diatas adalah .

Lalu, bagaimana jika tiap ? Kita cukup memisalkan untuk setiap yaitu untuk setiap sehingga setiap merupakan bilangan asli. Dengan begitu, banyak penyelesaian dari sistem persamaan adalah sama dengan banyak penyelesaian bilangan asli dari sistem persamaan atau yaitu .

Itu hanyalah salah satu cara dalam menyelesaikan soal bertema kombinasi berulang. Cara yang saya paparkan diatas sudah cukup mendasar asalkan mengerti kapan konsep kombinasi digunakan yaitu saat urutan objek yang dipilih tidak diperhatikan (dalam hal ini urutan ‘sekat’ diantara bintang tidak diperhatikan). Pesan implisit dari tulisan saya kali ini adalah mengajak para pembaca untuk berpikir secara elementer atau mulai dari hal-hal kecil sebelum menempuh kompleksitas.

Sebagai penutup, saya titipkan soal-soal berikut yang dapat dikerjakan dengan konsep diatas:

1. Ujian struktur diskrit terdiri dari 10 soal. Berapa banyak cara memberi bobot nilai pada setiap soal jika jumlah semua 10 soal benar adalah 100 dan setiap soal berbobot nilai paling sedikit 5? (UAS 2009)
2. Berapa banyak solusi bilangan bulat dari dengan syarat , , dan ? (Kuis 2010)
3. a. (melenceng dari topik) Buktikan pernyataan berikut: Untuk setiap bilangan asli dengan berlaku .
   b. (ini baru soal kombinatorik) Hitunglah banyak penyelesaian bilangan cacah dari (Orisinil)

Sekian dulu tulisan kali ini, bila ada pertanyaan mengenai ketiga soal diatas, bisa ditanyakan langsung ke kontak penulis atau lewat komentar di blog ini.