Theorema Star and Bars

Jika kita diminta untuk menemukan banyak kemungkinan kombinasi jumlah bola identik yang dapat dimasukan ke dalam 3 buah keranjang maka jika dimisalkan $(a,b,c)$ mewakili kejadian sebanyak $a$ bola di keranjang pertama, $b$ bola di keranjang kedua dan $c$ bola dikerangjang ketiga, akan ada banyak kombinasi untuk jumlah yang sama misalkan $(0,0,8),(0,8,0),(8,0,0)$ sehingga jika dicacah satu persatu akan sangat banyak. kondisi inilah yang nantinya dapat di selesaikan dengan konsep star and bar.

Secara sederhana jika bintang dimisalkan banyak bola, dan keranjang adalah banyak garis maka permasalahan diatas sama saja dengan menghitung nilai 10 kombinasi 2 karena kita akan menyusun 10 objek $($ keranjang dan bola dikurang 1 $)$ dari dua objek yang ada $($ 3 keranjang dikurang 1 $)$. untuk lebih jelasnya silahkan pahami penjelasan berikut ini

Theorema Star And Bar

Jika kita diminta memasukan $n$ benda identik ke dalam $r$ objek yang berbeda maka banyak caranya ada sebanyak

$C_{r-1}^{n+r-1}$

Theorema diatas juga dapat di gunakan untuk menghitung banyaknya solusi bilangan bulat positif dari bentuk $x_1+x_2+...+x_r=n$

Untuk lebih memahami theorema star and bar silahkan perhatikan contoh soal berikut.

Contoh Soal

--- Soal No 1 ---

Jika Budi akan memasukan 10 bola identik ke dalam sebuah kantong plastik, maka ada berapa cara mamasukan bola ke dalam kantong tersebut ... .

sesuai informasi disoal kita peroleh bahwa nilai $n=10,r=3$ sehingga jika dimasukan ke dalam rumus akan diperoleh.
$\begin{align*} C_{r-1}^{n+r-1} & = C_{3-1}^{10+3-1}\\ & = C_{2}^{12}\\ & = \frac{12!}{(12-2)!.2!}\\ & = \frac{12.11.10!}{10!.2.1}\\ & = 66 \\ \end{align*}$

jadi ada sebanyak 6 cara memasukan 10 bola ke dalam tiga buah kantong

--- Soal No 2 ---

Ayah akan membagikan 8 lembar uang seribuan kepada keempat anaknya dan setiap anak harus mendapatkan minimal uang sebanyak seribu rupiah. Maka ada berapa cara ayah untuk membagikan uang tersebut ... .

Dalam soal ini ada keharusan setiap anak menerima minimal uang sebanyak seribu, maka uang 8 ribu yang dimiliki ayah harus dibagikan terlebih dahulu kepada masing-masing anaknya sebanyak seribu rupiah. Sehingga yang akan dibagikan adalah sisa dari total uangnya yaitu 4 lembar uang seribuan, sehingga dapat dita temukan nilai $n=4$ dan $r=4$ jika dimasukan ke dalam rumus akan diperoleh.
$\begin{align*} C_{r-1}^{n+r-1} & = C_{4-1}^{4+4-1}\\ & = C_{3}^{7}\\ & = \frac{7!}{(7-3)!.3!}\\ & = \frac{7.6.5.4!}{4!.3.2.1}\\ & = 35 \\ \end{align*}$

Jadi ada 35 cara untuk membagikan uang tersebut.

--- Soal No 3 ---

jika diketahui nilai $x_1+x_1+x_3+x_4=15$, maka ada berapa banyak solusi tak negatif yang memenuhi kondisi tersebut

Jika kita samakan dengan theorema star and bar diatas maka dengan jelas akan diperoleh nilai $n=15$ dan $r=4$ sehingga dengan rumus star and bar diperoleh.
$\begin{align*} C_{r-1}^{n+r-1} & = C_{4-1}^{15+4-1}\\ & = C_{3}^{18}\\ & = \frac{18!}{(18-3)!.3!}\\ & = \frac{18.17.16.15!}{15!.3.2.1}\\ & = 816 \\ \end{align*}$

maka akan ada 816 kondisi yang memenuhi.

--- Soal No 4 ---

jika diketahui nilai $x_1+x_1+2x_3=5$, maka ada berapa banyak solusi tak negatif yang memenuhi kondisi tersebut

untuk menyelesaikan soal ini kita temukan dulu kemungkinan nilai $x_3$ yang mungkin dimana nilainya yang mungkin adalah $1$ dan $2$ dari 6 nilai yang mungkin yaitu $0,1,2,3,4,5$. sehingga dengan konsep star and bar akan diperoleh.
$\begin{align*} \frac{2}{6}.C_{r-1}^{n+r-1} & = \frac{2}{6}.C_{3-1}^{5+3-1}\\ & = \frac{2}{6}.C_{2}^{7}\\ & = \frac{2}{6}.\frac{7!}{(7-2)!.2!}\\ & = \frac{2}{6}.\frac{7.6.5!}{15!.2.1}\\ & = \frac{2}{6}.21 \\ & = 7 \\ \end{align*}$

maka akan ada 7 kondisi yang memenuhi.