0XVOkzIOMuVO2ISulfVeSoRy4XR0Z5HcQhXOZ6RK

Star and Bar Theorem

 Halo sobat nimu! Di artikel ini aku bakal membahas tentang Star and Bar Theorem,  salah satu teorema yang cukup berguna di kombinatorik. Kadang juga disebut dengan De Moivre. Yuk simak penjelasan berikut! ๐Ÿ‘€

Jika kamu menemukan tulisan-tulisan aneh seperti ada tulisan dollar ($), \frac, \ge, \le, dan lain-lain, harap ditunggu sebentar ya hehe... Karena rumus matematika masih loading... Kalau masih tidak berubah, silahkan tulis di komentar ya... Dan ketika muncul tulisan [Math Processing Error], kamu harus refresh halamanmu. Ketika menemukan rumus matematika yang terpotong (terutama pengguna HP), kusarankan kamu untuk mengubah posisi HP mu menjadi landscape oke!

0. Notasi

Sebelum membaca artikel ini, ada beberapa notasi yang perlu dipahami.
Notasi $\mathbb{N}$ menyatakan himpunan bilangan asli, yaitu  $\{1,2,3,4,\cdots,\}$. 
Notasi $\mathbb{N}_0$ menyatakan himpunan bilangan bulat tak negatif (bilangan cacah), yaitu $\{0,1,2,3,\cdots\}$.
Notasi $n!$ menyatakan perkalian bilangan asli berurutan dari $1$ sampai $n$ untuk setiap bilangan asli $n$. Dengan kata lain,\[n! = 1\times 2 \times 3 \times \cdots \times n\] Definisikan juga $0!=1$.
Notasi $\displaystyle \binom{a}{b} = \frac{a!}{b!(a-b)!}$ dimana $a,b $ bilangan bulat tak negatif.
Notasi sigma pada umumnya: \[\sum_{i=1}^n a_i= a_1+a_2+\cdots + a_n\]

A. Teorema


Star and Bar Theorem

Jika $a_1,a_2,a_3,\cdots, a_n$ bilangan bulat tak negatif sehingga \[a_1+a_2+a_3+\cdots + a_n=k\] dengan $k$ bilangan bulat tak negatif, maka banyak pasangan $(a_1,a_2,\cdots,a_n)$ yang memenuhi ada sebanyak \[\binom{n+k-1}{n-1} \quad \text{atau}\quad \binom{n+k-1}{k}\]

Bukti. Hal ini sama saja dengan menyusun $n-1$ buah $\mid$ dan $k$ buah $\star$ dari susunan \[\mid\star \mid\star  \mid\cdots \mid\star \mid\mid \mid\] dimana diantara dua buah $\mid$ tidak harus berisi $\star$. Hal ini dapat menggunakan permutasi objek yang sama, yaitu banyak susunan ada \[\frac{(n+k-1)!}{(n-1)!k!} = \binom{n+k-1}{n-1}\quad \text{atau}\quad \binom{n+k-1}{k}\] 
$\blacksquare$
Teorema ini juga disebut "Ball and Urn" theorem dengan : Jika terdapat $k$ bola yang identik (sama) dan $n$ kotak yang berbeda, maka banyak cara meletakkan bola-bola tersebut adalah $\displaystyle \binom{n+k-1}{n-1}$ atau $\displaystyle \binom{n+k-1}{k}$.

B. Star and Bar Pada Persamaan

1. Tanpa syarat

Pada hal ini masih sederhana dan cukup langsung pasang teoremanya. Perhatikan contoh berikut.

Contoh 1.1

Tentukan banyak pasangan bilangan bulat tak negatif $(a,b,c)$ sehingga $a+b+c=100$.
Pembahasan. Banyak pasangan $(a,b,c)$ ada \[\binom{100+3-1}{3-1}=\binom{102}{2} = \frac{102!}{2!100!} =6060\] Jadi, banyak pasangan bilangan bulat tak negatif $(a,b,c)$ ada $\boxed{6060}$.

Contoh 1.2.

Berapa banyak cara meletakkan $8$ bola identik ke $10$ kotak berbeda dimana kotak-kotak tersebut boleh kosong?
Pembahasan. Misalkan $a_1,a_2,a_3,\cdots,a_{10}$ menyatakan banyak bola yang terdapat pada masing-masing kotak tersebut. Maka \[a_1+a_2+a_3+\cdots+ a_{10}=8\] Karena kotak boleh kosong, maka $a_1,a_2,a_3,\cdots,a_{10}$ bilangan cacah. Sehingga banyak kemungkinannya ada $\displaystyle \binom{8+10-1}{10-1} = \boxed{\binom{17}{9}}$.

2. Dengan syarat

Terkadang dalam menerapkan star and bar theorem, terdapat syarat tambahan pada soal. Perhatikan contoh berikut.

Contoh 2.1.

Tentukan banyak pasangan bilangan asli $(a,b,c)$ sehingga $a+b+c=100$.
Pembahasan. Hal ini menjadi berbeda karena $a,b,c\ge 1$. Sedangkan, jika ingin menerapkan teorema star and bar harus $a,b,c\ge 0$. Maka kita subtitusi $a=x+1, b=y+1,$ dan $c=z+1$ dimana $x,y,z\ge 0$. Karena $a+b+c=100$, sehingga \begin{align*}a+b+c &= 100\\ x+y+z +3 &= 100\\ x+y+z &= 97 \end{align*} Sehingga banyak kemungkinan $(x,y,z)$ ada $\displaystyle \binom{97+3-1}{3-1} = \binom{99}{2}=4851$. Karena pasangan $(a,b,c)$ tergantung pada pasangan $(x,y,z)$ (alias disebut bijeksi kata kerennya), maka banyak pasangan $(a,b,c)$ sama dengan banyak pasangan $(x,y,z)$, yaitu $\boxed{4851}$.
Hal diatas dapat kita perumum sebagai berikut.

Star and Bar Theorem

Jika $a_1,a_2,a_3,\cdots, a_n$ bilangan asli sehingga \[a_1+a_2+a_3+\cdots + a_n=k\] dengan $k$ bilangan asli dan $k\ge n$, maka banyak pasangan $(a_1,a_2,\cdots,a_n)$ yang memenuhi ada sebanyak $\displaystyle \binom{k-1}{n-1}$.

Bukti. Misalkan $a_i =b_i+1$ dimana $b_i$ bilangan cacah untuk setiap $i=1,2,\cdots, n$. Maka \begin{align*}a_1+a_2+\cdots + a_n &= k\\(b_1+1)+(b_2+1)+\cdots +(b_n+1) &= k\\ b_1+b_2+\cdots + b_n &= k-n  \end{align*} Maka banyak penyelesaiannya adalah \[\binom{k-n + n-1}{n-1} = \binom{k-1}{n-1}\]
$\blacksquare$

Contoh 2.2.

Berapa banyak cara meletakkan $10$ bola identik ke $5$ kotak berbeda sehingga setiap kotak minimal terdapat $1$ bola?
Pembahasan. Misalkan banyak bola pada masing-masing kotak adalah $a_1,a_2,a_3,a_4,a_5$ dimana $a_1,a_2,a_3,a_4,a_5\ge 1$. Jumlah bola ada $10$, sehingga \[a_1+a_2+a_3+a_4+a_5=10\] Maka banyak penyelesaiannya ada \[\binom{10-1}{5-1}=\binom{9}{4}=\frac{9!}{4!5!} =126\] Jadi, banyak cara meletakkan bola-bola tersebut adalah $\boxed{126}$.

Contoh 2.3.

Tentukan banyak penyelesaian bilangan bulat $a,b,c$ dimana $a+b+c=10$ serta $a\ge 0$, $b\ge 1$, dan $c\ge 2$.
Pembahasan. Misalkan $b= y+1$ dan $c=z+2$ dimana $b,c\ge 0$. Karena $a+b+c=10$, maka\begin{align*} a+b+c &=10\\ a+y+1+z+2 &= 10\\a+y+z &=7\end{align*} Karena $a,y,z\ge 0$, maka banyak penyelesaiannya adalah \[\binom{7+3-1}{3-1}=\binom{9}{2}=\frac{9!}{2!7!} = 36\] Karena pasangan $(a,b,c)$ bijeksi dari $(a,y,z)$, maka banyak pasangan $(a,b,c)$ sama dengan banyak pasangan $(a,y,z)$, yaitu $\boxed{36}$.

Contoh 2.4.

Tentukan banyak penyelesaian bilangan asli $(a,b,c)$ sehingga \[a+b-c= 20\] dimana $c\le 20$.
Pembahasan. Perhatikan bahwa $a+b=c+20$. Maka banyak penyelesaian $(a,b)$ adalah \[ \binom{20+c-1}{2-1}=\binom{19+c}{1}=\frac{(19+c)!}{1!(18+c)!}=19+c\] Perhatikan bahwa banyak pasangan $(a,b)$ bergantung dengan nilai $c$. Sebagai contoh, banyak pasangan $(a,b,1)$ ada sebanyak $20$, banyak pasangan $(a,b,2)$ ada sebanyak $21$, dan seterusnya. Maka banyak pasangan $(a,b)$ seluruhnya ada \begin{align*}\sum_{i=1}^{20}(c+19) &= \sum_{i=1}^{20} c + \sum_{i=1}^{20}1\\ &= \frac{20\cdot 21}{2} + 20 \\ &= 210 +20\\ &=230 \end{align*} Jadi, banyak pasangan bilangan asli $(a,b,c)$ yang memenuhi ada $\boxed{230}$. Okay ini mungkin masih cukup mudah karena bentuknya belum cukup absurd. Bagaimana kalau dengan soal berikut:

Contoh 2.5.

Tentukan banyak pasangan bilangan asli $(a,b,c,d,e)$ sehingga \[a+b+c+d-e=20\] dimana $e\le 20$.
Pembahasan. Seperti soal sebelumnya, kita rubah menjadi $a+b+c+d=20+e$. Sehingga banyak pasangan $(a,b,c,d)$ ada $\displaystyle \binom{20+e-1}{4-1} = \binom{19+e}{3}$. Karena $e\le 20$, maka banyak pasangan $(a,b,c,d,e)$ senilai dengan \[\binom{20}{3} + \binom{21}{3} + \binom{22}{3}+\cdots + \binom{39}{3}\tag{$*$}\] Jika kamu yang berjiwa nekad, silahkan menghitungnya satu per satu. Tapi, ini cukup membuang waktu! Mending rakit pc. Ada salah satu identitas yang cukup berguna yang bernama Hockey Stick Identity.

Hockey Stick Identity

Jika $n,r$ bilangan asli dimana $n\ge r$, maka\[\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r}=\binom{n+1}{r+1}\] Atau dapat dituliskan dengan \[\sum_{i=r}^n\binom{i}{r} = \binom{n+1}{r+1}\]

Dengan identitas ini, menghitung $(*)$ mungkin bukan masalah. Tapi, masalah pertama bentuk $(*)$ tidak berlaku langsung dengan Hockey Stick Identity. Karena kita baru bisa menerapkan jika bentuk $(*)$ berupa \[\binom{3}{3}+\binom{4}{3}+\cdots + \binom{39}{3}\] Jadi, apa yang dapat kita lakukan? Kita paksa! Misalkan \begin{align*}S &=\binom{3}{3} + \binom{4}{3}+\cdots + \binom{39}{3} \\ T &= \binom{3}{3} + \binom{4}{3} + \cdots + \binom{19}{3} \end{align*} Perhatikan bahwa bentuk $S-T$ senilai dengan $(*)$. Dengan menerapkan Hockey Stick identity, kita peroleh bahwa \[S=\binom{40}{4}\quad \text{dan}\quad T=\binom{20}{4}\] Demikian bentuk $(*)$: \[\sum_{i=20}^{39} \binom{i}{3} =\binom{40}{4} - \binom{20}{4}\] Sekarang untuk menghitungnya menjadi lebih mudah, kan? Dapat kita peroleh \[\binom{40}{4} - \binom{20}{4}=91.390-4.845=86.545\] Jadi, banyak pasangan bilangan asli $(a,b,c,d,e)$ adalah $\boxed{86.545}$.

C. Star and Bar Pada Pertidaksamaan

Pada suatu soal kita diperintahkan untuk mencari banyak penyelesaian berupa pertidaksamaan. Perhatikan contoh berikut.

Contoh 3.1

Tentukan banyak penyelesaian bilangan bulat tak negatif $a,b,c$ sehingga $a+b+c\le 10$.
Pembahasan. Mungkin kita bisa mengerjakannya dengan memulai dari $a+b+c=0$, kemudian $a+b+c=1$, kemudian $a+b+c=2$, dan seterusnya hingga $a+b+c=10$. Jika kita misalkan $a+b+c=k$ dengan $0\le k\le 10$, maka banyak penyelesaian $(a,b,c)$ ada \[\binom{k+3-1}{3-1} = \binom{k+2}{2}\] Maka banyak pasangan $(a,b,c)$ seluruhnya adalah \[\binom{2}{2} + \binom{3}{2} + \cdots + \binom{12}{2}\] Dengan Hockey Stick Identity, kita peroleh jawaban akhirnya adalah $\displaystyle \boxed{\binom{13}{3}}$.
Tapi, ada metode lain yang lebih mudah. Kita buat bilangan baru semisal $d$ dimana $d$ bilangan cacah sehingga $a+b+c = 10 -d$. Hal tersebut mewakili $a+b+c\le 10$, kita dapat meninjau dari $d=0,1,2,\cdots,10$. Maka $a+b+c+d=10$ sehingga banyak penyelesaiannya adalah \[\binom{10+4-1}{4-1} = \boxed{\binom{13}{3}}\] sebagai jawaban akhir. Metode berbeda, tapi jawaban sama ๐Ÿ˜Ž
Hal diatas dapat kita perumum sebagai berikut.

Star and Bar 2

Misalkan $a_1,a_2,a_3,\cdots,a_n,K$ bilangan cacah sehingga \[a_1+a_2+a_3+\cdots + a_n\le K\] Maka banyak pasangan $(a_1,a_2,\cdots,a_n)$ ada sebanyak $\displaystyle \binom{K+n}{n}$ atau $\displaystyle \binom{K+n}{K}$.

Bukti. Terdapat bilangan cacah $a_{n+1}$ sehingga \[a_1+a_2+\cdots + a_n= K-a_{n+1}\] atau senilai dengan $a_1+a_2+\cdots + a_{n+1}=K$. Maka banyak penyelesaiannya adalah \[\binom{K+n+1 -1}{n+1 - 1} = \binom{K+n}{n}\] atau juga senilai dengan \[\binom{K+n+1-1}{K} = \binom{K+n}{K}\]
$\blacksquare$

Contoh 3.2.

Buktikan bahwa banyak pasangan bilangan asli $a_1,a_2,a_3,\cdots,a_n,K$ sehingga \[a_1+a_2+a_3+\cdots+ a_n\le K\] dimana $K\ge n$, maka banyak penyelesaian $(a_1,a_2,\cdots,a_n)$ ada $\displaystyle \binom{K}{n}$.
Pembahasan. Terdapat bilangan asli $a_{n+1}$ sehingga \[a_1+a_2+\cdots + a_n = K+1-a_{n+1}\] atau senilai dengan $a_1+a_2+\cdots + a_{n+1}= K+1$. Maka banyak penyelesaiannya ada $\displaystyle \binom{K+1-1}{n+1-1} = \binom{K}{n}$. 
Jika kamu ingin membuat bilangan baru berupa bilangan cacah, misalkan $a_{n+1}$, maka \[a_1+a_2+\cdots + a_n = K-a_{n+1}\] atau senilai dengan $a_1+a_2+\cdots + a_{n+1} = K$. Perhatikan bahwa $a_1,a_2,\cdots,a_n\ge 1$ dan $a_{n+1} \ge 0$. Untuk menyamakan batasnya, kita misalkan $b_ i = a_i+1$ dengan $b_i$ bilangan cacah untuk setiap $i=1,2,3,\cdots,n$. Maka \begin{align*}a_1 + a_2+\cdots + a_n +a_{n+1}&= K\\ (b_1+1)+(b_2+1)+\cdots + (b_n+1)+a_{n+1} &= K\\ b_1+b_2+\cdots +b_n+a_{n+1} &= K-n \end{align*} Maka banyak penyelesaiannya adalah \[\binom{K-n+n+1-1}{n+1-1} = \binom{K}{n}\]
$\blacksquare$

Contoh 3.3.

Tentukan banyak pasangan bilangan asli $(a,b,c)$ sehingga $a+b+c \le 100$.
Pembahasan. Buat bilangan asli baru, semisal $d\in \mathbb{N}$, sehingga $a+b+c=101-d$ yang senilai dengan $a+b+c+d=101$. Maka banyak penyelesaiannya adalah \[\binom{101-1}{4-1} = \binom{100}{3} = \frac{100!}{3!97!}=\boxed{161.700}\] Atau jika dari Contoh 3.2 maka ada $\displaystyle \binom{K}{n}=\binom{100}{3}=\boxed{161.700}$.

Contoh 3.4.

Tentukan banyaknya pasangan bilangan bulat tak negatif $(a,b,c,d)$ sehingga \[10\le a+b+c+d\le 20\]
Pembahasan. Hal ini sama saja dengan mencari banyak pasangan $(a,b,c,d)$ sehingga $a+b+c+d\le 20$, kemudian dikurangi dengan banyak pasangan $(a,b,c,d)$ sehingga $a+b+c+d\le 9$. Untuk $a+b+c+d\le 20$, buat bilangan cacah baru, semisal $e$ sehingga $a+b+c+d=20-e$ yang senilai dengan $a+b+c+d+e=20$. Maka banyak penyelesaiannya ada \[\binom{20+5-1}{5-1} = \binom{24}{4} = \frac{24!}{4!20!} = 10.626\] Jika $a+b+c+d\le 9$, dengan cara yang sama kita dapatkan $a+b+c+d+e=9$. Banyak penyelesaiannya adalah \[\binom{9+5-1}{5-1} = \binom{13}{4} = \frac{13!}{4!9!}=715\] Maka banyak penyelesaian bilangan bulat tak negatif (cacah) dari $10\le a+b+c+d \le 20$ adalah $10.626 - 715 =\boxed{9911}$.

Contoh 3.5.

Tentukan banyak pasangan bilangan asli $(a,b,c,d,e)$ dimana $e\le 20$ sehingga\[a+b+c+d-e = 20\]
Pembahasan. Soal ini mirip dengan soal sebelumnya. Tapi, akan kita gunakan metode yang berbeda. Perhatikan bahwa karena $e\le 20$, maka \[a+b+c+d=20+e \le 20+20=40\] Namun, $a+b+c+d= 20+e \ge 21$. Artinya, hal ini sama saja dengan menyelesaikan $21\le a+b+c+d\le 40$. Seperti pada Contoh 3.4, akan kita cari banyak pasangan $(a,b,c,d)$ sehingga $a+b+c+d=40$, kemudian dikurangi dengan banyak pasangan $(a,b,c,d)$ sehingga $a+b+c+d\le 20$. Buat bilangan asli baru, semisal $f$, sehingga $a+b+c+d=41-f$ atau senilai dengan $a+b+c+d+f=41$. Maka banyak penyelesaiannya ada $\displaystyle \binom{41-1}{5-1}=\binom{40}{4}$. Dengan cara yang sama, untuk $a+b+c+d+e\le 20$, maka $a+b+c+d+e+f= 21$ yang dimana banyak penyelesaiannya adalah $\displaystyle \binom{21-1}{5-1} = \binom{20}{4}$. Sehingga banyak penyelesaian $21\le a+b+c+d \le 40$ adalah $\displaystyle \boxed{\binom{40}{4} - \binom{20}{4}}$. Sama kan jawabannya ๐Ÿ˜Ž

D. Latihan Soal

Berikut beberapa latihan soal untuk dicoba. Beberapa soal telah saya cantumkan solusi/pembahasan. 

Soal 1. Tentukan banyak penyelesaian bilangan bulat tak negatif $(a,b)$ sehingga $a+b =2020$.
Soal 2. Tentukan banyak penyelesaian bilangan bulat tak negatif $(a,b,c,d)$ sehingga \[a+b+c+d = 20\]
Soal 3. Tentukan banyak penyelesaian bilangan asli $(a,b,c,d)$ sehingga $a+b+c+d=100$.
Soal 4. (OSN SMP) Tentukan banyak penyelesaian bilangan bulat tak negatif dari \[x_1+x_2+x_3+x_4 = 10\]
Soal 5. Sebanyak $8$ bola identik akan diletakkan dalam $10$ kotak yang berbeda sehingga setiap kotak boleh tidak berisi bola. Tentukan banyak cara meletakkan bola-bola tersebut.
Soal 6. Sebanyak $20$ bola identik akan diletakkan dalam $5$ kotak yang berbeda sehingga setiap kotak harus berisi minimal $1$ bola. Tentukan banyak cara meletakkan bola-bola tersebut.
Soal 7. Tentukan banyak penyelesaian bilangan asli $(a,b,c,d)$ dimana $b\ge 2$ dan $d\ge 4$ sehingga\[a+b+c+d = 20\] 
Perhatikan bahwa $b-1\ge 1$ dan $d-3\ge 1$. Misalkan $x=b-1$ dan $y=d-3$. Maka $x\ge 1$ dan $y\ge 1$. Perhatikan juga bahwa $b=x+1$ dan $d=y+3$. Karena $a+b+c+d=20$, maka \begin{align*}a+(x+1)+c+(y+3) &=20\\ a+x+c+y &=16 \end{align*} Karena $a,x,c,y\ge 1$, maka banyak penyelesaiannya adalah $\displaystyle \binom{16-1}{4-1} = \binom{15}{3}=\boxed{455}$.
Soal 8. Sebanyak $10$ bola putih identik dan $2$ bola hitam identik akan diletakkan secara berjajar. Tentukan banyak cara menyusun bola-bola tersebut sehingga bola hitam tidak terletak berdampingan.
Misalkan bola putih tersebut sebagai $P$ dan bola hitam sebagai $H$. Ilustrasi penyusunannya:\[\underbrace{PP\cdots P}_{\text{sebanyak }a}H\underbrace{PP\cdots P}_{\text{sebanyak }b}H\underbrace{PP\cdots P}_{\text{sebanyak }c}\] Kita misalkan $a,b,$ dan $c$ sebagai banyak bola putih seperti susunan diatas. Karena hitam tidak boleh berdampingan, maka haruslah $b\ge 1$, sedangkan $a,c\ge 0$. Karena banyak bola putih ada $10$, maka sama saja dengan mencari banyak solusi dari \[a+b+c =10\] dengan $a,c\ge 0$ dan $b\ge 1$. Perhatikan bahwa $b-1\ge 0$, misalkan $x=b-1$. Maka $x\ge 0$ dan $b=x+1$. Karena $a+b+c=10$,\begin{align*}a+b+c &=10 \\ a+x+1+c &=10 \\ a+x+c &=9 \end{align*} Maka banyak penyelesaiannya ada\[\binom{9+3-1}{3-1} = \binom{11}{2} = 55\] Jadi, banyak cara menyusun bola-bola tersebut adalah $\boxed{55}$.
Soal 9. Sebanyak $12$ bola putih identik dan $4$ bola hitam identik akan diletakkan secara berjajar. Tentukan banyak cara menyusun bola-bola tersebut sehingga tidak ada bola hitam yang terletak berdampingan.
Misalkan bola putih tersebut sebagai $P$ dan bola hitam sebagai $H$. Ilustrasi penyusunannya:\[\underbrace{P\cdots P}_{\text{sebanyak }a}H\underbrace{P\cdots P}_{\text{sebanyak }b}H\underbrace{P\cdots P}_{\text{sebanyak }c}H\underbrace{P\cdots P}_{\text{sebanyak }d}H\underbrace{P\cdots P}_{\text{sebanyak }e}\] Kita misalkan $a,b,c,d,$ dan $e$ sebagai banyak bola putih seperti susunan diatas. Karena hitam tidak boleh berdampingan, maka haruslah $b,c,d\ge 1$, sedangkan $a,e\ge 0$. Karena banyak bola putih ada $12$, maka sama saja dengan mencari banyak solusi dari \[a+b+c+d+e =12\] dengan $a,e\ge 0$ dan $b,c,d\ge 1$. Perhatikan bahwa $b-1\ge 0$, $c-1\ge 0$, dan $d-1\ge 0$. Misalkan $x=b-1$, $y=c-1$, dan $z=d-1$. Maka $x,y,z\ge 0$ dan $b=x+1$, $c=y+1$, dan $d=z+1$. Karena $a+b+c+d+e=12$,\begin{align*}a+b+c+d+e &=12 \\ a+(x+1)+(y+1)+(z+1)+e &=12 \\ a+x+y+z+e &=9 \end{align*} Maka banyak penyelesaiannya ada\[\binom{9+5-1}{5-1}= \binom{13}{4} = 715\] Jadi, banyak cara menyusun bola-bola tersebut adalah $\boxed{715}$.
Soal 10. Sebanyak $12$ bola putih identik dan $3$ bola hitam berbeda satu sama lain akan diletakkan secara berjajar. Tentukan banyak cara menyusun bola tersebut sehingga tidak ada bola hitam yang terletak berdampingan.
Misalkan bola putih tersebut sebagai $P$ dan bola hitam sebagai $H_1,H_2,H_3$ (karena berbeda). Ilustrasi penyusunannya:\[\underbrace{P\cdots P}_{\text{sebanyak }a}H_1\underbrace{P\cdots P}_{\text{sebanyak }b}H_2\underbrace{P\cdots P}_{\text{sebanyak }c}H_3\underbrace{P\cdots P}_{\text{sebanyak }d}\] Kita misalkan $a,b,c,$ dan $d$ sebagai banyak bola putih seperti susunan diatas. Karena hitam tidak boleh berdampingan, maka haruslah $b,c\ge 1$, sedangkan $a,d\ge 0$. Karena banyak bola putih ada $12$, maka sama saja dengan mencari banyak solusi dari \[a+b+c+d =12\] dengan $a,d\ge 0$ dan $b,c\ge 1$. Perhatikan bahwa $b-1\ge 0$, $c-1\ge 0$. Misalkan $x=b-1$, $y=c-1$. Maka $x,y\ge 0$ dan $b=x+1$ dan $c=y+1$. Karena $a+b+c+d=12$,\begin{align*}a+b+c+d+e &=12 \\ a+(x+1)+(y+1)+d &=12 \\ a+x+y+d &=10 \end{align*} Maka banyak penyelesaiannya ada\[\binom{10+4-1}{4-1}= \binom{13}{3} = 286\] Namun, posisi bola hitam $H_1,H_2,H_3$ dapat ditukar-tukar, yaitu sebanyak $3!=6$. Jadi, banyak cara menyusun bola-bola tersebut adalah $286 \cdot 6=\boxed{1716}$.
Soal 11. Berapa banyak penyelesaian bilangan bulat $(a,b,c,d)$ sehingga \[a+b+c+d = 20\] dimana $a\ge -1,b \ge 2, c\ge 3,$ dan $d\ge 0$?
Soal 12. Buktikan Hockey Stick Identity.
Akan kita buktikan dengan induksi. Untuk $\displaystyle n=r$, maka \[\binom{r}{r} = \binom{r+1}{r+1}\] karena $\displaystyle \binom{r}{r}=1$ dan $\displaystyle \binom{r+1}{r+1}=1$. Asumsikan benar untuk $n=k$ dimana $k\ge r$. Maka untuk $n=k+1$, \begin{align*}\sum_{i=r}^{k+1} \binom{i}{r} &= \sum_{i=r}^k \binom{i}{r} + \binom{k+1}{r}\\ &=\binom{k+1}{r+1} + \binom{k+1}{r} \end{align*} Bentuk terakhir bila menggunakan Identitas Pascal, maka \[\binom{k+1}{r+1} + \binom{k+1}{r} = \binom{k+2}{r+1}\] Atau kita dapat membongkar bentuk tersebut, yaitu \begin{align*}\binom{k+1}{r+1} + \binom{k+1}{r} &=\frac{(k+1)!}{(r+1)!(k-r)!}+\frac{(k+1)!}{r!(k+1-r)!}\\ &=\frac{(k+1)!}{r!(k-r)!}\left (\frac{1}{r+1} + \frac{1}{k+1-r} \right )\\ &= \frac{(k+1)!}{r!(k-r)!}\left (\frac{k+1-r+r+1}{(r+1)(k+1-r)} \right )\\ &= \frac{(k+1)!}{r!(k-r)!}\left (\frac{k+2}{(r+1)(k+1-r)}\right ) \\ &=\frac{(k+2)!}{(k+1-r)!(r+1)!} \\ &=\binom{k+2}{r+1} \end{align*}Jadi, \[\sum_{i=r}^{k+1} \binom{i}{r} = \binom{k+2}{r+1}\] yang berarti benar untuk $n=k+1$. Sehingga menurut induksi terbukti.
Soal 13. Tentukan banyak penyelesaian bilangan bulat tak negatif $(a,b,c,d)$ sehingga \[a+b +c-d =10\] dimana $d\le 15$.
Soal 14. Tentukan banyak penyelesaian bilangan asli $(a,b,c)$ sehingga $a+b+c \le 100$.
Soal 15. Tentukan banyak penyelesaian bilangan bulat $(a,b,c)$ sehingga \[a+b+c\le 20\] dimana $a\ge 1, b\ge 3$, dan $c\ge -1$.
Tinjau $b-2 \ge 1$ dan $c+2\ge 1$. Misalkan $x=b-2$ dan $y=c+2$ dimana $x,y\ge 0$. Tinjau juga $b=x+2$ dan $c=y-2$. Karena $a+b+c\le 20$, maka \begin{align*}a+b+c &\le 20\\ a + (x+2) + (y-2) &\le 20 \\ a+x+y &\le 20 \end{align*} Buat bilangan asli baru, semisal $z$, sehingga \[a+x+y=21-z \Leftrightarrow a+x+y+z=21\] Karena $a,x,y,z\ge 1$, maka banyak penyelesaiannya adalah \[\binom{21-1}{4-1} =\binom{20}{3} = 1.140\] Karena pasangan $(a,x,y)$ bijektif dengan $(a,b,c)$, maka banyak pasangan $(a,b,c)$ yang demikian sama banyak dengan $(a,x,y)$, yaitu $\boxed{1.140}$.
Soal 16. Tentukan banyak penyelesaian bilangan bulat tak negatif $(a,b,c,d)$ dari \[4 \le a+b+c+d\le 10\]

Yak cukup sekian pembahasan mengenai Star and Bar Theorem. Bila ada yang tidak dipahami, yuk bertanya! Ketimbang bingung terus-terusan ๐Ÿ‘€ Kalian juga bisa menjawab soal-soal tersebut di kolom komentar sekalian berdiskusi ๐Ÿ˜ Sampai jumpa di post selanjutnya!
Nimba Ilmu
Tempat Belajar Bersama Paling Asyik

Postingan Terkait

Posting Komentar