$\textcolor{ForestGreen}{\textbf{Stars and Bars}}$  

Stars and Bars adalah teknik kombinatorial untuk menghitung banyaknya solusi bilangan bulat non‐negatif dari

$$
x_1 + x_2 + \dots + x_n = r.
$$

Intinya kita merepresentasikan setiap satuan sebagai “bintang” dan pemisah antar variabel sebagai “bar.”


$\textcolor{ForestGreen}{\textbf{1. Kasus tanpa batas}}$  

Kita memiliki $r$ bintang dan $n-1$ bar. Total posisi yang dipilih dari $r + n - 1$ adalah di mana bar‐bar itu berdiri:

$$
\binom{r + n - 1}{n - 1}
$$

Contoh: Hitung banyak solusi $x_1 + x_2 + x_3 = 5$ dengan $x_i \ge 0$.

$$
\binom{5 + 3 - 1}{3 - 1}
=
\binom{7}{2}
=
21.
$$


$\textcolor{ForestGreen}{\textbf{2. Kasus dengan batas bawah}}$  

Jika setiap $x_i \ge a_i$, lakukan substitusi $y_i = x_i - a_i$, sehingga

$$
\sum_{i=1}^n y_i = r - \sum_{i=1}^n a_i,
\quad
y_i \ge 0.
$$

Hasil akhirnya:

$$
\binom{(r - \sum_{i=1}^n a_i) + n - 1}{n - 1}.
$$

Contoh: Banyak solusi $x_1 + x_2 + x_3 = 10$ dengan $x_1 \ge 2,\;x_2 \ge 1,\;x_3 \ge 0$.

Setelah substitusi $y_1+y_2+y_3 = 10 - (2+1+0) = 7$, maka

$$
\binom{7 + 3 - 1}{3 - 1}
=
\binom{9}{2}
=
36.
$$


$\textcolor{ForestGreen}{\textbf{3. Kasus dengan batas atas}}$  

Untuk $x_i \le u_i$, gunakan prinsip inklusi‐eksklusi: hitung semua solusi non‐negatif kemudian kurangi yang melanggar batas atas.

Jumlah awal:

$$
\binom{r + n - 1}{n - 1},
$$

dikurangi jumlah kasus $x_i > u_i$ satu per satu, dua per dua, dan seterusnya.

Contoh: $x_1 + x_2 = 5$ dengan $0 \le x_1 \le 3$, $0 \le x_2 \le 4$.

Tanpa batas:

$$
\binom{5 + 2 - 1}{2 - 1}
=
\binom{6}{1}
=
6.
$$

Kasus $x_1 > 3$: misal $x_1' = x_1 - 4 \ge 0$, sehingga

$$
x_1' + x_2 = 1
\quad\Longrightarrow\quad
\binom{1 + 2 - 1}{2 - 1} = 2.
$$

Kasus $x_2 > 4$: misal $x_2' = x_2 - 5 \ge 0$, sehingga

$$
x_1 + x_2' = 0
\quad\Longrightarrow\quad
\binom{0 + 2 - 1}{2 - 1} = 1.
$$

Total:

$$
6 - 2 - 1 = 3.
$$


$\textcolor{ForestGreen}{\textbf{4. Partisi Bilangan}}$  

Jika setiap $x_i > 0$, substitusi $y_i = x_i - 1$, sehingga

$$
\sum_{i=1}^n y_i = r - n,
\quad
y_i \ge 0.
$$

Jumlah solusi:

$$
\binom{(r - n) + n - 1}{n - 1}
=
\binom{r - 1}{n - 1}.
$$

Contoh: Partisi $r=7$ ke dalam $n=3$ bagian positif:

$$
\binom{7 - 1}{3 - 1}
=
\binom{6}{2}
=
15.
$$