Materi, Soal, dan Pembahasan – Teorema Bintang dan Garis

Salah satu teorema yang mewarnai dunia kombinatorika dan sering dipakai untuk menyelesaikan soal terkait konfigurasi susunan objek adalah Teorema Bintang dan Garis (Stars and Bars Theorem). Teorema ini kadang-kadang juga menggunakan istilah “Sumpit dan Batu” atau “Bola dan Garis”. Teorema ini dipopulerkan oleh William Feller (matematikawan Kroasia-Amerika) dalam bukunya yang membahas tentang peluang (probability).

Contoh masalah yang membuat kita harus berpikir keras sebelum mengenal Teorema Bintang dan Garis adalah sebagai berikut.

Stimulus

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

Masalah ini tidak bisa diselesaikan dengan cara biasa karena kita tidak tahu persis apa yang harus dipilih atau disusun karena keidentikan bola tersebut. Kemungkinan pertama yang dapat dilakukan adalah menuliskannya satu per satu. Misalkan $(a, b, c)$ menyatakan bahwa kita akan memasukkan $a$ bola pada kotak pertama, $b$ bola kotak kedua, dan $c$ bola pada kotak ketiga. Dengan demikian, beberapa cara berbeda yang dimaksud adalah $(8, 0, 0), (6, 2, 0),$ $(3, 4, 1),$ $(5, 1, 2),$ dan sebagainya. Banyak sekali! Tentu sangat tidak efisien bila kita menuliskannya satu per satu seperti tadi.

Apa lagi yang bisa dicoba? Bagaimana kalau menghitung banyak cara memasukkan bola ke masing-masing kotak, kemudian menggunakan aturan perkalian? Sayangnya, apa yang dimasukkan di satu kotak memengaruhi apa yang dimasukkan di kotak lain sehingga dapat kita katakan bahwa kejadian-kejadian tersebut tidak saling bebas, atau dependen. Oleh karena itu, aturan perkalian kurang tepat untuk dipakai dalam menyelesaikan masalah ini.

Teorema Bintang dan Garis hadir untuk menyelesaikannya. Bayangkan $8$ bola yang akan kita masukkan tadi kita jajarkan dalam satu baris, kemudian kita lambangkan dengan bintang $(\color{red}{\bigstar}).$ Gunakan satu lambang yang sama karena bolanya identik.
$$\color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar}$$Untuk menentukan bola mana yang masuk ke masing-masing kotak, kita gunakan suatu pemisah—seperti partisi buku-buku di perpustakaan—yang kita lambangkan sebagai garis vertikal $(\mid).$
$$\color{red}{\bigstar} \color{red}{\bigstar} \mid \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \mid \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar}$$

Partisi buku-buku di perpustakaan

Karena kita akan menempatkan bola-bola ke dalam $3$ kotak, kita membutuhkan $2$ partisi yang diwakili oleh garis vertikal tersebut. Konfigurasi di atas menunjukkan bahwa kita akan memasukkan $2$ bola pada kotak pertama, $3$ bola pada kotak kedua, dan $3$ bola pada kotak ketiga.

Nah, kalau begitu idenya sudah dapat! Kita hanya perlu menggeser kedua partisi tersebut sehingga kita akan peroleh konfigurasi yang lain seperti contoh berikut.
$$\color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \mid \color{red}{\bigstar} \mid \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar}$$Itu berarti kita akan memasukkan $4$ bola pada kotak pertama, $1$ bola pada kotak kedua, dan $3$ bola pada kotak ketiga.

Jadi, banyak cara memasukkan $8$ buah bola identik ke dalam $3$ kotak berbeda sama dengan banyk cara menyusun $8$ bintang dan $3$ garis. Dengan kata lain, kita cukup mencari banyak cara menempatkan $2$ garis tersebut di $8 + 2 = 10$ tempat yang tersedia. Ditambah $2$ karena kita bisa menempatkan garis di posisi paling ujung seperti contoh berikut.
$$\mid \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \mid$$Itu berarti kita akan memasukkan $0$ bola pada kotak pertama, $8$ bola pada kotak kedua, dan $0$ bola pada kotak ketiga.

Dengan menggunakan aturan kombinasi, kita peroleh
$$C(10,2) = \dfrac{10!}{8! \cdot 2!} = 45.$$

Sekarang, kita tinggal memperumum. Kita punya $n$ buah bola identik yang akan dimasukkan ke dalam $k$ kotak yang berbeda. Sama seperti tadi, bayangkan kita akan menyusun $n$ bintang. Karena ada $k$ kotak, kita membutuhkan $(k-1)$ partisi/garis. Ini berarti kita akan menyusun $(n+k-1)$ objek. Oleh karena itu, banyak cara menyusun $n$ buah bola ke dalam $k$ kotak yaang berbeda sama aja dengan banyak cara memilihkan tempat bagi $(k-1)$ partisi tadi ke $(n+k-1)$ tempat yang tersedia, yakni
$$\boxed{{\large C(n+k-1, k-1)}}$$Bentuk terakhir inilah yang dikenal sebagai rumus dari Teorema Bintang dan Garis. Sekarang, kalian juga pasti sudah tahu alasan mengapa nama teorema tersebut seperti itu, ada bintang dan ada garisnya.

Di sisi lain, ternyata masalah kontekstual di atas dapat direpresentasikan oleh pertanyaan berikut: Ada berapa solusi bulat nonnegatif dari persamaan $$x_1 + x_2 + x_3 + \cdots + x_k = n?$$Solusi bulat nonnegatif artinya solusi yang melibatkan bilangan-bilangan bulat yang lebih besar atau sama dengan nol. Perhatikan bahwa ini sebenarnya sama saja dengan permasalahan penempatan bola ke dalam kotak tadi. Letakkan $n$ buah bola ke dalam $k$ kotak. Masing-masing variabel menyatakan banyaknya bola yang dimasukkan pada kotak tersebut. Sebagai contoh, $x_3$ menyatakan banyak bola yang akan dimasukkan pada kotak ketiga. Ketika mencari banyaknya cara memasukkan $8$ buah bola ke dalam $3$ kotak yang berbeda, kita sebenarnya sedang mencari banyak solusi bulat nonnegatif dari persamaan $$x_1+x_2+x_3 = 8$$dengan $x_1, x_2, x_3$ berturut-turut menyatakan banyak bola yang akan dimasukkan pada kotak pertama, kedua, dan ketiga.

Teorema Bintang dan Garis

Banyak cara memasukkan $n$ buah benda yang identik ke dalam $k$ kotak yang berbeda adalah
$$\boxed{{\large C(n+k-1, k-1)} = \displaystyle \binom{n+k-1}{k-1}}$$Secara ekuivalen, banyaknya solusi bulat nonnegatif untuk persamaan $$x_1+x_2+x_3+\cdots+x_k = n$$adalah $$\boxed{{\large C(n+k-1, k-1)} = \displaystyle \binom{n+k-1}{k-1}}$$

Berikut telah disediakan sejumlah soal dan pembahasan terkait penggunaan Teorema Bintang dan Garis yang dikumpulkan dari berbagai sumber. Semoga bermanfaat.

Today Quote

Ada yang sibuk berjuang sampai tidur terasa nikmat saking lelahnya. Ada juga yang sibuk tidur-tiduran sampai badan sakit semua. Kita sama-sama punya $24$ jam, tinggal bagaimana cara kita menghargainya.

Bagian Pilihan Ganda

Soal Nomor 1
Banyaknya cara memasukkan $9$ bunga yang identik ke dalam $3$ vas yang berbeda dengan syarat setiap vasnya minimal terdapat $1$ bunga adalah $\cdots \cdot$
A. $15$                  C. $24$                E. $36$
B. $20$                D. $28$

Pembahasan

Pertama, masukkan $1$ bunga ke masing-masing vas sehingga sekarang tersisa $6$ bunga. Sekarang kita tinggal menempatkan $6$ bunga ini ke masing-masing vas tersebut dengan kondisi syarat nonnegatif telah terpenuhi sehingga Teorema Bintang dan Garis dapat kita terapkan.
Banyak cara membagikan $n = 6$ bunga yang identik ke dalam $k = 3$ vas yang berbeda adalah sebagai berikut.
$$\begin{aligned} \displaystyle \binom{n+k-1}{k-1} & = \binom{6+3-1}{3-1} \\ & = \binom{8}{2} \\ & = \dfrac{8!}{6! \cdot 2!} \\ & = 28 \end{aligned}$$Jadi, banyak cara memasukkan bunga-bunga tersebut ke dalam vas adalah $\boxed{28}$
(Jawaban D)

[collapse]

Soal Nomor
Banyaknya solusi bulat tak negatif yang memenuhi persamaan $x_1 + x_2 + x_3 + x_4 = 15$ adalah $\cdots \cdot$
A. $136$                     D. $680$
B. $153$                     E. $816$
C. $455$

Pembahasan

Dengan menggunakan Teorema Bintang dan Garis, permasalahan di atas ekuivalen dengan mencari banyaknya cara menempatkan $n = 15$ bola identik ke dalam $k = 4$ kotak berbeda, yaitu sebagai berikut.
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{15+4-1}{4-1} \\ & = \binom{18}{3} \\ & = \dfrac{18!}{15! \cdot 3!} \\ & = 816 \end{aligned}$$Jadi, ada $\boxed{816}$ solusi bulat tak negatif yang memenuhi persamaan tersebut.
(Jawaban E)

[collapse]

Soal Nomor
Pada persamaan $x_1 + x_2 + x_3 = 12,$ $x_i$ adalah bilangan bulat nonnegatif. Banyak kemungkinan solusinya adalah $\cdots \cdot$
A. $78$                     D. $220$
B. $91$                     E. $495$
C. $165$

Pembahasan

Dengan menggunakan Teorema Bintang dan Garis, permasalahan di atas ekuivalen dengan mencari banyaknya cara menempatkan $n = 12$ bola identik ke dalam $k = 3$ kotak berbeda, yaitu sebagai berikut.
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{12+3-1}{3-1} \\ & = \binom{14}{2} \\ & = \dfrac{14!}{12! \cdot 2!} \\ & = 91 \end{aligned}$$Jadi, banyak kemungkinan solusi persamaan tersebut adalah $\boxed{91}$
(Jawaban B)

[collapse]

Soal Nomor
Diberikan persamaan $x_1 + x_2 + x_3 + x_4 = 13$ dengan syarat $x_1 > 0,$ $x_2 > 1,$ $x_3 > 2,$ dan $x_4 \geq 0$ dengan $x_i$ berupa bilangan bulat. Banyak kemungkinan solusinya adalah $\cdots \cdot$
A. $80$                       D. $150$
B. $100$                     E. $180$
C. $120$

Pembahasan

Perhatikan bahwa nilai minimum variabel $x_1, x_2, x_3,$ dan $x_4$ berturut-turut adalah $1, 2, 3,$ dan $0.$ Dengan menganalogikan masalah ini sebagai masalah bola dan kotak, kita punya $13$ bola identik dan $4$ kotak berbeda. Tempatkan $1$ bola pada kotak pertama, $2$ bola pada kotak kedua, dan $3$ bola pada kotak ketiga sehingga sekarang tersisa $13-(1+2+3) = 7$ bola.
Selanjutnya, kita tinggal mencari banyak cara menempatkan $n = 7$ bola tersebut ke dalam $k = 4$ kotak dengan menggunakan Teorema Garis dan Bintang.
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{7+4-1}{4-1} \\ & = \binom{10}{3} \\ & = \dfrac{10!}{7! \cdot 3!} \\ & = 120 \end{aligned}$$Jadi, banyak kemungkinan solusi persamaan tersebut adalah $\boxed{120}$
(Jawaban C)

[collapse]

Soal Nomor
Berapa banyak cara memilih $5$ huruf dari $26$ huruf alfabet Inggris $(A, B, C, \cdots, Z)$ dengan syarat: huruf kecil dan kapital tidak dipermasalahkan, kemunculan huruf boleh berulang, dan kata yang termasuk anagram dianggap sama (contohnya: KURSI dianggap sama dengan RUKIS)?
A. $14.950$
B. $27.405$
C. $65.780$
D. $142.506$
E. $169.911$

Pembahasan

Kita punya $26$ pilihan huruf dan akan ditempatkan pada $5$ posisi berbeda. Kemunculan huruf boleh lebih dari sekali, atau mungkin tidak sama sekali. Andaikan $C_A, C_B, C_C, \cdots, C_Z$ berturut-turut menyatakan banyak kemunculan huruf $A, B, C, \cdots Z$ sehingga kita peroleh persamaan berikut.
$$C_A + C_B + C_C + \cdots + C_Z = 5$$Fokus kita hanya mengatur seberapa banyak kemunculan 26 huruf tersebut. Menurut Teorema Garis dan Bintang untuk $n = 5$ dan $k = 26,$ kita peroleh
$$\begin{aligned} \displaystyle \binom{n+k-1}{k-1} & = \binom{5+26-1}{26-1} \\ & = \binom{30}{25} \\ & = \dfrac{30!}{25! \cdot 5!} \\ & = 142.506 \end{aligned}$$Jadi, banyak cara memilih $5$ huruf tersebut adalah $\boxed{142.506}$
(Jawaban D)

[collapse]

Soal Nomor 1
Sebanyak $20$ buah apel dan $15$ buah jeruk dibagikan kepada $5$ orang anak. Tiap anak boleh mendapat lebih dari $1$ buah apel atau jeruk, atau tidak sama sekali. Banyak cara pembagian yang dapat dilakukan adalah $\cdots \cdot$
A. $C(24, 19)$
B. $C(19, 14)$
C. $C(24, 19) + C(19, 14)$
D. $C(24, 19) \times C(19, 14)$
E. $C(20, 5) \times C(15, 5)$

Pembahasan

Pada persoalan ini, nilai $n = 5,$ $r_1 = 20$ (apel), dan $r_2 = 15$ (jeruk). Perhatikan bahwa setiap anak boleh tidak mendapatkan apel/jeruk sama sekali sehingga syarat nonnegatif telah terpenuhi.
Dengan menggunakan Teorema Bintang dan Garis, banyak cara membagikan $20$ buah apel (identik) kepada $5$ orang anak adalah sebagai berikut.
$$\begin{aligned} \displaystyle \binom{n+r_1-1}{r_1-1} & = \binom{5+20-1}{20-1} \\ & = \binom{24}{19} \\ & = C(24, 19) \end{aligned}$$Dengan cara yang sama, banyak cara membagikan $15$ buah jeruk (identik) kepada $5$ orang anak adalah sebagai berikut.
$$\begin{aligned} \displaystyle \binom{n+r_2-1}{r_2-1} & = \binom{5+15-1}{15-1} \\ & = \binom{19}{14} \\ & = C(19, 14) \end{aligned}$$Jadi, banyak cara pembagian yang dapat dilakukan secara keseluruhan dapat dicari dengan menggunakan aturan perkalian (karena kejadiannya saling bergantung/dependen), yakni $\boxed{C(24, 19) \times C(19, 14)}$ cara.
(Jawaban D)

[collapse]

Soal Nomor
Berapa banyak pasangan terurut bilangan bulat positif $(a_1, a_2, a_3, a_4, a_5, a_6)$ dengan $a_i \geq i$ untuk $i = 1, 2, 3, 4, 5, 6$ yang memenuhi persamaan $$a_1 + a_2 + a_3 + a_4 + a_5 + a_6 \le 100?$$
A. $C(105, 6)$                     D. $C(79, 6)$
B. $C(100, 6)$                     E. $C(79, 5)$
C. $C(85, 6)$

Pembahasan

Perhatikan bahwa kita punya beberapa kondisi berikut.
$$\begin{cases} a_1 & \ge 1 \\ a_2 & \ge 2 \\ a_3 & \ge 3 \\ a_4 & \ge 4 \\ a_5 & \ge 5 \\ a_6 & \ge 6 \end{cases}$$Misalkan terdapat bilangan $c \geq 0$ sedemikian sehingga berlaku persamaan
$$a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + c = 100.$$Sekarang munculkan $b_i = a_i-i$ untuk $i = 1, 2, \cdots, 6$ sedemikian sehingga kita ingin mencari pasangan terurut $(b_1, b_2, b_3, b_4, b_5, b_6, c)$ dengan syarat $b_i \ge 0, c \ge 0.$ Kita peroleh persamaan yang baru sebagai berikut.
$$\begin{aligned} (b_1 + 1) + (b_2 + 2) + (b_3 + 3) + (b_4 + 4) + (b_5 + 5) + (b_6 + 6) + c & = 100 \\ b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + c & = 100-(1+2+3+4+5+6) \\ b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + c & = 79 \end{aligned}$$Syarat nonnegatif telah terpenuhi oleh tujuh variabel tersebut sehingga kita bisa menerapkan Teorema Bintang dan Garis untuk $n = 79$ dan $k = 7.$
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{79+7-1}{7-1} \\ & = \binom{85}{6} \\ & = C(85, 6) \end{aligned}$$Jadi, banyak pasangan terurut yang dimaksud adalah $\boxed{C(85, 6)}$
(Jawaban D)

[collapse]