Fungsi Pembangkit untuk Kombinasi (Pengayaan)

 $\color{blue}\textrm{F. Fungsi Pembangkit}$

$\begin{aligned}&\textrm{Pandang}\: \: \color{red}\left ( a_{n} \right )\color{black}=\left ( \color{red}a_{0},a_{1},a_{2},a_{3},\cdots \color{black}\right )\: \: \textbf{suatu barisan}\\ &\textrm{Fungsi Pembangkit Biasa (FPB) dari barisan}\: \: \color{red}\left ( a_{n} \right )\\ &\displaystyle \sum_{n=0}^{\infty }\color{red}a_{n}\color{black}x^{n}=\color{red}a_{0}\color{black}+\color{red}a_{1}\color{black}x+\color{red}a_{2}\color{black}x^{2}+\color{red}a_{3}\color{black}x^{3}+\cdots \\ &\underline{\color{blue}\textrm{CONTOH 1}}\\ &\textrm{Diketahui}\: \: f(x)=\displaystyle \frac{1}{1-x}\: .\: \textrm{Tentukanlah barisan}\: \: \left ( a_{n} \right )\\ &\textrm{yang terkait pada FPB di atas}\\ &\underline{\textbf{Jawab}}\\ &\textrm{Diketahui bahwa}\: \: f(x)=\displaystyle \frac{1}{1-x}\\ &\textrm{karena}\: \: \: \: \displaystyle \frac{1}{1-x}= 1+x+x^{2}+x^{3}+x^{4}+x^{5}+\cdots\\ &\textrm{maka}\: \: \: \displaystyle \frac{1}{1-x}\: \: \: \textrm{adalah fungsi pembangkit dari barisan}\\ &\left ( a_{n} \right )=(1,1,1,1,1,\cdots ) \end{aligned}$

$\begin{aligned} &\underline{\color{blue}\textrm{CONTOH 2}}\\ &f(x)=2+3x^{2}+\displaystyle \frac{2}{1-4x}\: .\: \textrm{Tentukanlah barisan}\: \: \left ( a_{n} \right )\\ &\textrm{yang terkait pada FPB di atas}\\ &\underline{\textbf{Jawab}}\\ &\textrm{Diketahui bahwa}\: \: f(x)=2+3x^{2}+\displaystyle \frac{2}{1-4x}\\ &\begin{aligned}f(x)&=2+3x^{2}+2\left (\displaystyle \frac{1}{1-4x} \right )\\ &=2+3x^{2}+2\displaystyle \sum_{n=0}^{\infty }(4x)^{n}\\ &=2+3x^{2}+2\displaystyle \sum_{n=0}^{\infty }4^{n}\: x^{n}\\ &=2+3x^{2}+2\left ( 4^{0}+4^{1}x+4^{2}x^{2}+4^{3}x^{3}+\displaystyle \sum_{n=4}^{\infty }(4n)^{n} \right )\\ &=2+3x^{2}+28x+32x^{2}+128x^{3}+2\displaystyle \sum_{n=4}^{\infty }(4x)^{n}\\ &=4+8x+35x^{2}+128x^{3}+2\displaystyle \sum_{n=4}^{\infty }(4x)^{n} \end{aligned}\\ &\textrm{maka}\: \: \: f(x)\: \: \: \textrm{adalah fungsi pembangkit dari barisan}\\ &\left ( a_{n} \right )=(4,8,35,128,\cdots ,2(4)^{n}) \end{aligned}$

$\color{blue}\textrm{G. Fungsi Pembangkit untuk Kombinasi}$

Perhatikanlah permasalahan berikut:

$\begin{aligned}&\textrm{Ada berapa cara jika ada 3 objek}\: \: a,\: b,\: \textrm{dan}\: c\\ &\textrm{diambil}\: \: k\: \: \textrm{objek dengan ketentuan bahwa}\\ &a\: \: \textrm{terambil maksimum 1},\: b\: \: \textrm{terambil maksimum}\\ &2,\: c\: \: \textrm{terambil maksimum 1}\\ &\textbf{Pembahasan}\\ &\textrm{Permasalahan di atas dapat dimodelkan}\\ &\left ( (ax)^{0}+(ax)^{1} \right )\left ( (bx)^{0}+(bx)^{1}+(bx)^{2} \right )\left ( (cx)^{0}+(cx)^{1} \right )\\ &\quad =\left ( a^{0}x^{0}+a^{1}x^{1} \right )\left ( b^{0}x^{0}+b^{1}x^{1}+b^{2}x^{2} \right )\left ( c^{0}x^{0}+c^{1}x^{1} \right )\\ &\quad =\left ( 1+ax \right )\left ( 1+bx+b^{2}x^{2} \right )\left ( 1+cx \right )\\ &\quad =1+(a+b+c)x+(ab+ac+bc+b^{2})x^{2}\\ &\qquad +(abc+ab^{2}+b^{2}c)x^{3}+ab^{2}cx^{4}\\ &\textrm{Sebagai misal Untuk 2 huruf, maka koefisien dari}\: \: x^{2}\\ &\textrm{yaitu}:\: ab,\: ac,\: bc,\: \textrm{dan}\: bb\: \: \textrm{ada 4 cara}.\\ &\textrm{Sehingga}\\ &\begin{array}{rl} (a+b+c)\color{red}x&\textrm{ada 3 cara untuk 1 huruf}\\ (ab+ac+bc+b^{2})\color{red}x^{2}&\textrm{ada 4 cara untuk 2 huruf}\\ (abc+ab^{2}+b^{2}c)\color{red}x^{3}&\textrm{ada 3 cara untuk 3 huruf}\\ ab^{2}c\color{red}x^{4}&\textrm{ada 1 cara untuk 4 huruf} \end{array}\\ &\textrm{Selanjutnya coba kita bandingkan dengan FPB}.\\ &\textrm{FPB dari permasalahan di atas adalah}:\\ &f(x)=(1+x)(1+x+x^{2})(1+x)\\ &\: \: \: \: \quad =1-3x-4x^{2}-3x^{3}-x^{4} \end{aligned}$

$\begin{aligned}&\textrm{Sehingga secara UMUM}\\ &\textrm{Misalkan terdapat}\: \: \color{red}p\: \: \color{black}\textrm{sekian objek}.\\ &\textrm{Jika ada}\: \: n_{1}\: \: \textrm{objek pada tipe ke}-1,\\ &\textrm{dan ada}\: \: n_{2}\: \: \textrm{objek pada tipe ke}-2,\\ &\textrm{lalu ada}\: \: n_{3}\: \: \textrm{objek pada tipe ke}-3,\\ &\vdots \\ &dst\\ &\vdots \\ &\textrm{dan ada}\: \: n_{p}\: \: \textrm{objek pada tipe ke}-p,\\ &\textrm{Dan misalkan}\: \: t_{r}\: \: \textrm{menyatakan banyaknya}\\ &\textrm{cara mengambil}\: \: r\: \: \textrm{objek dengan membolehkan}\\ &\textrm{mengambil sembarang banyak objek pada tipa tipe},\\ &\color{red}\textrm{fungsi pembangkit untuk}\: \: \color{black}t_{r}\: \: \color{red}\textrm{adalah}:\\ &f(x)=\displaystyle \sum t_{r}x^{r},\: \: \: \textrm{di mana}\\ &f(x)=(1+x+x^{2}+\cdots +x^{n_{1}})(1+x+x^{2}+\cdots +x^{n_{2}})\cdots (1+x+x^{2}+\cdots +x^{n_{p}})\\ &\textrm{Nantinya}\: \: t_{r}\: \: \textrm{adalah koefisien}\: \: x^{r}\: \: \textrm{dalam}\: \: f(x)\\\\ &\begin{aligned}\textrm{Sela}&\textrm{njutnya dalam peruntukannya dibagi menjadi}\\ \textrm{a}.\quad &\textrm{Fungsi Pembangkit Tanpa Pengulangan}\\ &f(x)=\underset{n\: \: \textbf{faktor}}{\underbrace{(1+x)(1+x)(1+x)\cdots (1+x)}}\\ &f(x)=(1+x)^{n}=\displaystyle \sum_{r=0}^{n}\begin{pmatrix} n\\ r \end{pmatrix}x^{r}\quad (\color{red}\textrm{teorema binom})\\ \textrm{b}.\quad &\textrm{Fungsi Pembangkit Dengan Pengulangan}\\ &f(x)=\underset{n\: \: \textbf{faktor}}{\underbrace{(1+x+x^{2}+\cdots )(1+x+x^{2}+\cdots )\cdots (1+x+x^{2}+\cdots )}}\\ &f(x)=(1+x+x^{2}+\cdots )^{n}\\ &\qquad =\left ( \displaystyle \frac{1}{1-x} \right )^{n}\\ &\qquad =(1-x)^{-n}\\ &\qquad =\displaystyle \sum_{r=0}^{\infty }\begin{pmatrix} -n\\ r \end{pmatrix}(-1)^{r}\: x^{r}\quad (\color{red}\textrm{teorema binom})\\ &\textrm{Selanjutnya, untuk}\: \: r>0\: \: \textrm{koefisien}\: \: x^{r}\\ &\textrm{pada}\: \: f(x)\: \: \textrm{di atas adalah}:\\ & \end{aligned} \end{aligned}$

$\begin{aligned} \begin{pmatrix} -n\\ r \end{pmatrix}(-1)^{r}&=\displaystyle \frac{(-n)(-n-1)\cdots (-n-r+1)(-n-r)!}{r!(-n-r)!}\color{red}(-1)^{r}\\ &=\displaystyle \frac{(-n)(-n-1)\cdots (-n-r+1)}{r!}\color{red}(-1)^{r}\\ &=\displaystyle \frac{n(n+1)\cdots (n+r-1)}{r!}\\ &=\displaystyle \frac{(n+r-1)(n+r-2)\cdots (n+1)n}{r!}\\ &=\displaystyle \frac{(n+r-1)(n+r-2)\cdots (n+1)n(n-1)!}{r!(n-1)!}\\ &=\displaystyle \frac{(n+r-1)!}{r!(n-1)!}\\ &=\color{red}\begin{pmatrix} n+r-1\\ r \end{pmatrix}\\ \textrm{Sehingga}\: &\\ f(x)&=\displaystyle \sum_{r=0}^{\infty }\begin{pmatrix} -n\\ r \end{pmatrix}(-1)^{r}x^{r}=\displaystyle \sum_{r=0}^{\infty }\begin{pmatrix} n+r-1\\ r \end{pmatrix}x^{r}=\displaystyle \sum t_{r}x^{r}\\ \textrm{maka}&\\ t_{r}&=\color{red}\begin{pmatrix} n+r-1\\ r \end{pmatrix} \end{aligned}$

$\begin{aligned}&\textrm{Dan yang perlu diingat untuk selanjutnya}\\ &\textrm{adalah bahwa untuk}\: \: x\neq 0\: \: \textbf{dan}\: \: n\: \: \textrm{bilangan}\\ &\textrm{cacah berlaku identitas}\\ &\qquad \displaystyle \frac{1-x^{n+1}}{1-x}=\color{red}1+x+x^{2}+x^{3}+\cdots +x^{n} \end{aligned}$

$\LARGE\colorbox{yellow}{CONTOH SOAL}$

1. Rasiman, Rahmawati, N., D. 2012. Matematika Diskrit. Semarang: IKIP PGRI Semarang Press.