Memisahkan Bintang untuk Mencari Solusi

Bayangkan, suatu hari Mindie akan membagikan 12 bintang kepada 4 temannya di dunia. Kalau masing-masing teman punya kemungkinan mendapatkan 0 sampai 12 bintang, ada berapa banyak susunan pembagian bintang yang mungkin?

Apakah harus kita susun satu-satu?

Tentu tidak! Menyusun setiap kemungkinan satu per satu adalah cara yang tidak efisien, sehingga risiko terjadinya kesalahan akan semakin besar. Lalu, bagaimana dong?

Mari berkenalan dengan Stars and Bars Theorem!

Untuk menyelesaikan permasalahan ini, kita lambangkan bintang sebagai "⭐". Kemudian, kita buat ruang bagi masing-masing teman untuk meletakkan ⭐ mereka. Untuk memisahkan ruang antarteman, kita gunakan simbol "|".

Jika setiap teman mendapatkan 3 bintang, skenario tersebut bisa kita gambarkan sebagai berikut:

⭐⭐⭐|⭐⭐⭐|⭐⭐⭐|⭐⭐⭐

Dari sini, bisa kita lihat bahwa untuk membentuk 4 ruang, kita hanya memerlukan 3 "|".

Lalu, bagaimana jika ternyata teman pertama hanya mendapat dua ⭐ sementara teman kedua mendapat 4? Geser saja garisnya! Susunannya akan menjadi seperti ini:

⭐⭐|⭐⭐⭐⭐|⭐⭐⭐|⭐⭐⭐

Artinya, masalah ini bisa diibaratkan sebagai mencari banyaknya cara yang mungkin untuk menyusun 12 ⭐ dan 3 "|"! Sama juga dengan menyusun 3 buah "|" pada 15 tempat yang kosong, yang tentunya bisa kita selesaikan dengan kombinasi!

Banyaknya susunan yang mungkin adalah:

$$C(15,\,3) = \frac{15!}{3!\,(15-3)!} = \frac{15!}{3!\,12!} = \frac{15 \times 14 \times 13}{3 \times 2} = 455 \text{ susunan!}$$

Bagaimana dengan $n$ buah bintang dan $k$ orang teman?

Pertama-tama, ingat bahwa untuk membuat 4 ruang, kita membutuhkan 3 "|", yang sama saja dengan $4 - 1$. Maka, untuk membuat $k$ ruang, kita membutuhkan $k - 1$ buah "|".

Selain itu, kita juga mempunyai $n$ buah ⭐. Sehingga, jumlah tempat kosong yang kita miliki adalah sebanyak $n + k - 1$.

Maka, sama saja dengan menyusun $k - 1$ buah "|" pada $n + k - 1$ tempat kosong. Sehingga, banyak cara membagikan $n$ bintang kepada $k$ teman adalah:

$$C(n + k - 1,\ k - 1)$$

Dari sini, kita belajar bahwa berpikir sejenak bukan berarti buang-buang waktu

Seperti saat kita berusaha untuk menyelesaikan masalah ini: jika kita langsung mencoba membuat setiap susunan yang mungkin satu per satu, waktu yang kita butuhkan akan sangat lama. Tetapi, jika kita berpikir sejenak dan menemukan solusi yang lebih efektif, kita dapat mengerjakan suatu permasalahan dengan lebih cepat, dan risiko terjadinya kesalahan akan menjadi jauh lebih kecil.