Fungsi Pembangkit untuk Kombinasi (Pengayaan)

 $\text{F. Fungsi Pembangkit}$

$\begin{array}{rl}& \text{Pandang}\left(a_n\right)=\left(a_0,a_1,a_2,a_3,\cdots \right)\mathbf{\text{suatu barisan}}\\ & \text{Fungsi Pembangkit Biasa (FPB) dari barisan}\left(a_n\right)\\ & {\displaystyle \sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\cdots }\\ & \underset{―}{\text{CONTOH 1}}\\ & \text{Diketahui}f(x)={\displaystyle \frac{1}{1-x}.\text{Tentukanlah barisan}\left(a_n\right)}\\ & \text{yang terkait pada FPB di atas}\\ & \underset{―}{\mathbf{\text{Jawab}}}\\ & \text{Diketahui bahwa}f(x)={\displaystyle \frac{1}{1-x}}\\ & \text{karena}{\displaystyle \frac{1}{1-x}=1+x+x^2+x^3+x^4+x^5+\cdots }\\ & \text{maka}{\displaystyle \frac{1}{1-x}\text{adalah fungsi pembangkit dari barisan}}\\ & \left(a_n\right)=(1,1,1,1,1,\cdots )\end{array}$

$\begin{array}{rl}& \underset{―}{\text{CONTOH 2}}\\ & f(x)=2+3x^2+{\displaystyle \frac{2}{1-4x}.\text{Tentukanlah barisan}\left(a_n\right)}\\ & \text{yang terkait pada FPB di atas}\\ & \underset{―}{\mathbf{\text{Jawab}}}\\ & \text{Diketahui bahwa}f(x)=2+3x^2+{\displaystyle \frac{2}{1-4x}}\\ & \begin{array}{rl}f(x)& =2+3x^2+2\left({\displaystyle \frac{1}{1-4x}}\right)\\ & =2+3x^2+2{\displaystyle \sum _{n=0}^{\mathrm{\infty }}(4x{)}^n}\\ & =2+3x^2+2{\displaystyle \sum _{n=0}^{\mathrm{\infty }}{4}^n{x}^n}\\ & =2+3x^2+2(4^0+4^{1}x+4^2{x}^2+4^3{x}^3+{\displaystyle \sum _{n=4}^{\mathrm{\infty }}(4n{)}^n})\\ & =2+3x^2+28x+32x^2+128x^3+2{\displaystyle \sum _{n=4}^{\mathrm{\infty }}(4x{)}^n}\\ & =4+8x+35x^2+128x^3+2{\displaystyle \sum _{n=4}^{\mathrm{\infty }}(4x{)}^n}\end{array}\\ & \text{maka}f(x)\text{adalah fungsi pembangkit dari barisan}\\ & \left(a_n\right)=(4,8,35,128,\cdots ,2(4{)}^n)\end{array}$

$\text{G. Fungsi Pembangkit untuk Kombinasi}$

Perhatikanlah permasalahan berikut:

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

$\begin{array}{rl}& \text{Sehingga secara UMUM}\\ & \text{Misalkan terdapat}p\text{sekian objek}.\\ & \text{Jika ada}{n}_1\text{objek pada tipe ke}-1,\\ & \text{dan ada}{n}_2\text{objek pada tipe ke}-2,\\ & \text{lalu ada}{n}_3\text{objek pada tipe ke}-3,\\ & ⋮\\ & dst\\ & ⋮\\ & \text{dan ada}{n}_p\text{objek pada tipe ke}-p,\\ & \text{Dan misalkan}{t}_r\text{menyatakan banyaknya}\\ & \text{cara mengambil}r\text{objek dengan membolehkan}\\ & \text{mengambil sembarang banyak objek pada tipa tipe},\\ & \text{fungsi pembangkit untuk}{t}_r\text{adalah}:\\ & f(x)={\displaystyle \sum t_r{x}^r,\text{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})\\ & \text{Nantinya}{t}_r\text{adalah koefisien}{x}^r\text{dalam}f(x)\\ \\ & \begin{array}{rl}\text{Sela}& \text{njutnya dalam peruntukannya dibagi menjadi}\\ \text{a}.& \text{Fungsi Pembangkit Tanpa Pengulangan}\\ & f(x)=\underset{n\mathbf{\text{faktor}}}{\underbrace{(1+x)(1+x)(1+x)\cdots (1+x)}}\\ & f(x)=(1+x{)}^n={\displaystyle \sum _{r=0}^n\left(\begin{array}{c}n\\ r\end{array}\right)x^r(\text{teorema binom})}\\ \text{b}.& \text{Fungsi Pembangkit Dengan Pengulangan}\\ & f(x)=\underset{n\mathbf{\text{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\\ & ={\left({\displaystyle \frac{1}{1-x}}\right)}^n\\ & =(1-x{)}^{-n}\\ & ={\displaystyle \sum _{r=0}^{\mathrm{\infty }}\left(\begin{array}{c}-n\\ r\end{array}\right)(-1{)}^r{x}^r(\text{teorema binom})}\\ & \text{Selanjutnya, untuk}r>0\text{koefisien}{x}^r\\ & \text{pada}f(x)\text{di atas adalah}:\\ & \end{array}\end{array}$

$\begin{array}{rl}\left(\begin{array}{c}-n\\ r\end{array}\right)(-1{)}^r& ={\displaystyle \frac{(-n)(-n-1)\cdots (-n-r+1)(-n-r)!}{r!(-n-r)!}(-1{)}^r}\\ & ={\displaystyle \frac{(-n)(-n-1)\cdots (-n-r+1)}{r!}(-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)!}}\\ & =\left(\begin{array}{c}n+r-1\\ r\end{array}\right)\\ \text{Sehingga}& \\ f(x)& ={\displaystyle \sum _{r=0}^{\mathrm{\infty }}\left(\begin{array}{c}-n\\ r\end{array}\right)(-1{)}^r{x}^r={\displaystyle \sum _{r=0}^{\mathrm{\infty }}\left(\begin{array}{c}n+r-1\\ r\end{array}\right)x^r={\displaystyle \sum t_r{x}^r}}}\\ \text{maka}& \\ t_r& =\left(\begin{array}{c}n+r-1\\ r\end{array}\right)\end{array}$

$\begin{array}{rl}& \text{Dan yang perlu diingat untuk selanjutnya}\\ & \text{adalah bahwa untuk}x\ne 0\mathbf{\text{dan}}n\text{bilangan}\\ & \text{cacah berlaku identitas}\\ & {\displaystyle \frac{1-x^{n+1}}{1-x}=1+x+x^2+x^3+\cdots +x^n}\end{array}$

$\text{CONTOH SOAL}$

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