Jawaban:

Soal. Ada berapa banyak cara memasukkan 7 buah bola yang identik (sama persis) ke dalam 3 keranjang yang berbeda?

Jawab: Kemungkinan pertama: kita tulis kemungkinannya satu per satu. Misalkan (a, b,c) menyatakan bahwa kita akan memasukkan a bola di kotak pertama, b bola di kotak kedua, dan c bola di kotak ketiga. Berarti kita punya (7,0,0), (6,1,0), (6,0,1), (5,2,0), (5,1,1), (5,0,1)…

Oke, mungkin Anda lebih rajin dari saya, tapi buat saya, 6 itu sudah agak kebanyakan.

Ide bagus, tapi sayangnya apa yang dimasukkan di satu kotak memengaruhi apa yang dimasukkan di kotak lain; kejadian-kejadian tersebut tidak saling bebas/independen. Oleh karenanya, aturan perkalian kurang tepat dipakai

Bayangkan 7 bola yang akan kita masukkan tadi kita jajarkan dalam satu baris, dan kita lambangkan dengan bintang (*) — satu lambang ini cukup karena bola-bola yang kita miliki identik:

* * * * * * *

Lalu, untuk menentukan bola mana yang masuk di masing-masing kotak, kita gunakan suatu pemisah – bayangkan saja seperti kertas atau partisi buku di perpustakaan – yang kita lambangkan dengan garis (|):

**|***|**

Karena kita akan memisahkan ke dalam 3 kotak, kita butuh 2 buah partisi. Lambang **|***|** di atas berarti kita akan memasukkan 2 bola ke kotak pertama, 3 bola ke kotak kedua, dan 2 bola di kotak ketiga.

Nah, kalau begitu, ketika kita menggeser kedua partisi tadi, kita sesungguhnya akan menemukan kemungkinan lain untuk memasukkan bola-bola tersebut ke dalam kotak! Misalnya, kalau sekarang partisi tadi kita geser seperti ini:

****|*|**

itu berarti kita akan memasukkan 4 bola ke kotak pertama, 1 bola ke kotak kedua, dan 2 bola ke kotak ketiga.

Wah, ini berarti, cara memasukkan 7 buah bola ke dalam 3 kotak berbeda sama dengan cara kita menyusun 7 buah bintang dan 2 buah garis! Dengan demikian, kita cukup mencari banyak cara menempatkan 2 buah garis tersebut di 7 + 2 = 9 tempat yang tersedia. Sehingga, banyak cara memasukkan 7 buah bola ke dalam 3 kotak berbeda adalah

\displaystyle C(9,2) = \frac{9!}{2!\times 7!} = 36.

Nah, sekarang, seperti biasanya, mari kita memperumum! Sekarang kita punya n bola identik yang akan dimasukkan ke dalam k kotak yang berbeda.

Seperti tadi, bayangkan bahwa kita akan menyusun n buah bintang. Karena ada k kotak, kita membutuhkan k-1 buah partisi. Ini berarti kita akan menyusun sebanyak n + k - 1 objek. Oleh karena itu, banyak cara menyusun n buah bola ke dalam k kotak yang berbeda tak lain adalah cara memilihkan tempat bagi k-1 buah partisi dari n + k - 1 tempat yang tersedia, yakni:

C(n+k-1,k-1).

Hasil tadi adalah apa yang biasa disebut sebagai teorema star-and-bars. Secara lebih formal, teorema ini juga ingin menjawab pertanyaan berikut: ada berapa solusi bulat taknegatif untuk persamaan

x_1 + x_2 + \cdots + x_k = n?

Solusi bulat taknegatif (atau nonnegatif) berarti kita hanya menginginkan solusi-solusi yang melibatkan bilangan-bilangan bulat yang lebih besar atau sama dengan 0.

Perhatikan bahwa ini sama saja dengan permasalahan kita tadi: meletakkan n buah bola ke dalam k buah kotak — masing-masing variabel menyatakan banyaknya bola yang diletakkan di kotak tersebut! Ketika kita mencari banyaknya cara memasukkan 7 buah bola ke dalam 3 kotak yang berbeda, kita sesungguhnya sedang mencari banyak solusi bulat taknegatif dari sistem persamaan

x_1 + x_2 + x_3 = 7

dengan x_1, x_2, dan x_3 masing-masing menyatakan banyaknya bola di kotak ke-1, 2, dan 3.

Kedua interpretasi dari teorema stars-and-bars ini cukup penting. Oleh karena itu, saya tuliskan kembali kesimpulan diskusi tadi:

Teorema. Banyak cara memasukkan n buah benda yang identik ke dalam k kotak yang berbeda adalah

C(n+k-1,k-1).

Secara ekuivalen, banyaknya solusi bulat nonnegatif untuk persamaan

x_1 + x_2 + x_3 + \cdots + x_k = n

adalah

C(n+k-1,k-1).

Mari kita lihat satu contoh soal lagi.

Soal. Edgar sedang berada di bandara Haneda. Ia ingin membeli 6 bungkus teh jepang untuk dibawa pulang ke Indonesia. Di toko yang sedang ia kunjungi, terdapat 3 varian teh yang menarik: matcha, genmaicha, dan oolong. Berapa macam cara Edgar dapat membeli 6 bungkus teh yang ia mau?

Jawab. Sepintas mungkin soal ini tidak terlihat seperti soal yang dapat diselesaikan menggunakan teorema stars-and-bars. Namun, perhatikan bahwa kita menginginkan banyak teh matcha, genmaicha, dan oolong yang dibeli Edgar sejumlah 6 buah. Dengan kata lain, kita sedang mencari solusi bulat bagi persamaan ini:

Penjelasan:

Semoga bermanfaat