Fungsi Pembangkit - Teknik Menghitung
Fungsi pembangkit di dalam matematika diskrit sering kali digunakan untuk menyelesaikan berbagai masalah menghitung.
Fungsi pembangkit juga dapat digunakan untuk menyelesaikan relasi rekursif. Pembuktian identitas dalam kombinatorial juga dapat menggunakan fungsi pembangkit.
Apa itu Fungsi Pembangkit
Fungsi pembangkit adalah fungsi yang berbentuk deret kuasa yang digunakan untuk merepresentasikan barisan secara efektif dengan menjadikan suku-suku barisan menjadi koefisien dari variabel \(x\) di dalam bentuk formal deret kuasa.
Fungsi pembangkit dibagi menjadi dua yaitu fungsi pembangkit biasa dan fungsi pembangkit eksponensial.
Definisi formal fungsi pembangkit biasa untuk suatu barisan sebagai berikut
DEFINISI
Fungsi pembangkit biasa untuk barisan \(\left(a_{0}, a_{1}, a_{2}, \cdots, a_{k}, \cdots\right)\) adalah deret tak hingga\[G(x):=\sum_{k=0}^{\infty}a_{k}x^{k}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}\cdots\]
Mari kita lihat contoh soal penggunaan dari definisi fungsi pembangkit di atas
Contoh Soal 1
Fungsi pembangkit biasa dari barisan konstan \((2, 2, 2, 2, \cdots)\) adalah\[G(x)=\sum_{k=0}^{\infty}2 x^{k}=2+2x+2x^{2}+2x^{3}+\cdots\]Sedangkan fungsi pembangkit untuk barisan \((a_{k})\) dengan \(a_{k}=k+2\) adalah\[G(x)=\sum_{k=0}^{\infty}(k+2) x^{k}=2+3x+4x^{2}+5x^{3}+\cdots\]Dan fungsi pembangkit untuk barisan \(a_{k}=3^{k}\) adalah fungsi\[G(x)=\sum_{k=0}^{\infty}\left(3^{k}\right) x^{k}=1+3x+9x^{2}+27x^{3}+\cdots\]
Berikut adalah beberapa macam-macam deret kuasa yang biasa dijadikan rujukan dalam fungsi pembangkit
\[
\begin{eqnarray*}
e^{x}&=&\sum_{n=0}^{\infty}\frac{x^{n}}{n!}\\
&=&1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\cdots\\
\frac{1}{1-x}&=&\sum_{n=0}^{\infty}x^{n}\\
&=&1+x+x^{2}+x^{3}+\cdots\\
\frac{1}{(1-x)^{2}}&=&\sum_{n=0}^{\infty}(n+1)x^{n}\\
&=&1+2x+3x^{2}+4x^{3}+\cdots\\
\frac{1}{1-ax}&=&\sum_{n=0}^{\infty}a^{n}x^{n}\\
&=&1+ax+a^{2}x^{2}+a^{3}x^{3}+\cdots\\
\frac{1}{1-x^{r}}&=&\sum_{n=0}^{\infty}x^{rn}\\
&=&1+x^{r}+x^{2r}+x^{3r}+\cdots\\
(1+x)^{n}&=&\sum_{k=0}^{n}C(n,k)x^{k}
\end{eqnarray*}
\]
Contoh 1 di atas yang dicari adalah fungsi pembangkit dari suatu barisan yang diketahui. Contoh berikut kebalikannya, dicari barisan dengan fungsi pembangkit yang diketahui.
Contoh Soal 2
Fungsi \(\frac{1}{1-x}\) merupakan fungsi pembangkit dari barisan \((1, 1, 1, 1, \cdots)\) karena\[\frac{1}{1-x}=\sum_{k=0}^{\infty} x^{k}=1+x+x^{2}+x^{3}+\cdots\]untuk \(|x|<1\).
Contoh Soal 3
Fungsi \(f(x)=e^{x}\) merupakan fungsi pembangkit untuk barisan \((1, 1, \frac{1}{2!}, \frac{1}{3!}, \cdots)\) karena\[e^{x}=\sum_{k=0}^{\infty} \frac{x^{k}}{k!}=1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\cdots\]
Beberapa contoh soal berikut adalah mencari fungsi pembangkit dari barisan yang khusus
Contoh Soal 4
Fungsi pembangkit dari barisan \((0, 0, \frac{1}{2!}, \frac{1}{3!}, \frac{1}{4!}, \cdots)\) adalah
\[\begin{eqnarray*}
G(x)&=&0+0+\frac{1}{2!}x^{2}+\frac{1}{3!}x^{3}+\frac{1}{4!}x^{4}+\cdots\\
&=&\left(1+x+\frac{1}{2!}x^{2}+\frac{1}{3!}x^{3}+\frac{1}{4!}x^{4}+\cdots \right)-(1+x)\\
&=&e^{x} - (1+x)
\end{eqnarray*}
\]Oleh karena itu fungsi pembangkit yang diinginkan adalah fungsi \(\boldsymbol{e^{x}-1-x}\).
Contoh soal sebelumnya membahas fungsi pembangkit untuk barisan yang tak hingga. Namun, fungsi pembangkit juga dapat digunakan pada barisan yang berhingga.
Contoh Soal 5
Fungsi pembangkit dari barisan \((1,1,1,1,1)\) adalah
\[\begin{eqnarray*}
G(x)&=&1+x+x^{2}+x^{3}+x^{4}\\
&=&\left(1+x+x^{2}+x^{3}+x^{4}+\cdots\right) - \left(x^{5}+x^{6}+x^{7}+x^{8}+\cdots\right)\\
&=&\frac{1}{1-x}- x^{5}\left(1+x+x^{2}+x^{3}+x^{4}+\cdots\right) \\
&=&\frac{1}{1-x} - \frac{x^{5}}{1-x}\\
&=&\frac{1-x^{5}}{1-x}
\end{eqnarray*}
\]Oleh karena itu fungsi pembangkit yang dicari adalah fungsi \(\boldsymbol{\frac{1-x^{5}}{1-x}}\).
Mulai dari awal tadi anda mungkin secara sadar bahwa dalam fungsi pembangkit banyak menggunakan deret tak hingga.
Deret tak hingga yang didefinisikan pada fungsi pembangkit tersebut digolongkan dalam deret kuasa.
Sifat Deret Kuasa
Karena dalam pembahasan fungsi pembangkit, kita banyak melibatkan deret kuasa, maka akan kita tinjau beberapa sifat dari deret kuasa
Teorema
Misalkan \(f(x) = \sum\limits_{k=0}^{\infty}a_{k}x^{k}\) dan \(g(x) = \sum\limits_{k=0}^{\infty}b_{k}x^{k}\) maka
\[
\begin{eqnarray*}
f(x)+g(x)&=&\sum\limits_{k=0}^{\infty}\left(a_{k}+b_{k}\right) x^{k}\\
f(x)\cdot g(x)&=&\sum\limits_{k=0}^{\infty}\left(\sum\limits_{j=0}^{k}a_{j}b_{k-j}\right)x^{k}
\end{eqnarray*}
\]
\[
\begin{eqnarray*}
f(x)+g(x)&=&\sum\limits_{k=0}^{\infty}\left(a_{k}+b_{k}\right) x^{k}\\
f(x)\cdot g(x)&=&\sum\limits_{k=0}^{\infty}\left(\sum\limits_{j=0}^{k}a_{j}b_{k-j}\right)x^{k}
\end{eqnarray*}
\]
Contoh Soal 6
Misalkan fungsi \(f(x)= \frac{1}{(1-x)^{2}}\). Tentukan barisan yang fungsi pembangkitnya adalah fungsi \(f(x)\)!
Solusi Contoh soal 6
Berdasarkan deret kuasa dari fungsi \(f(x)\) diperoleh\[\frac{1}{1-x}=1+x+x^{2}+x^{3}+\cdots\]Berdasarkan teorema di atas didapatkan
\[\frac{1}{1-x}\cdot\frac{1}{1-x}=\sum\limits_{k=0}^{\infty}\left(\sum\limits_{j=0}^{k}1\right)x^{k}=\sum\limits_{k=0}^{\infty}(k+1)x^{k}
\]Oleh karena itu, barisan yang dicari adalah \(a_{k}=k+1\) yaitu \((1,2,3,4,5,\cdots)\).
Penggunaan fungsi pembangkit dalam menyelesaikan masalah perhitungan juga seringkali melibatkan teorema binomial dengan pangkat tidak hanya bilangan bulat positif.
Oleh karena itu diperlukan koefisien binomial yang diperluas.
DEFINISI
Misalkan \(u\) adalah bilangan riil dan \(k\) adalah bilangan bulat tak negatif. Maka koefisien binomial diperluas \(\left(\begin{array}{c}u\\k\end{array}\right)\) yang didefinisikan dengan
\[
\left(\begin{array}{c}u\\k\end{array}\right):=\left\{\begin{array}{ll}u(u-1)(u-2)\cdots\frac{(u-k+1)}{k!}&\quad\text{jika } k>0\\1,&\quad\text{jika }k=0\end{array}
\right.
\]
\[
\left(\begin{array}{c}u\\k\end{array}\right):=\left\{\begin{array}{ll}u(u-1)(u-2)\cdots\frac{(u-k+1)}{k!}&\quad\text{jika } k>0\\1,&\quad\text{jika }k=0\end{array}
\right.
\]
Ketika parameter atas pada koefisien binomial meruapakan bilangan bulat negatif, maka koefisien binomial diperluas ini dapat disajikan dengan koefisien binomial biasa, yaitu\[\left(\begin{array}{c}-n\\r\end{array}\right)=(-1)^{r}\left(\begin{array}{c}n+r-1\\r\end{array}\right)\]Sehingga mengantarkan kita pada teorema binomial berikut
Teorema Binomial Diperluas
Misalkan \(x\) adalah bilangan riil dengan \(|x|<1\) dan misalkan \(u\) merupakan bilangan riil. Maka\[\left(1+x\right)^{u}=\sum_{k=0}^{\infty}\left(\begin{array}{c}u\\k\end{array}\right)x^{k}\]
Sekarang kita akan melihat beberapa aplikasi dari fungsi pembangkit untuk teknik menghitung
Fungsi Pembangkit untuk Kombinasi
Masalah menghitung tingkat lanjut dapat menggunakan fungsi pembangkit dalam solusinya.
Kalau di dalam masalah kombinasi, Anda sering menghitung banyaknya cara untuk memilih suatu cara dengan bilangan yang tetap.
Bagaimana kalau pemilihan cara ini dengan bilangan yang umum dan objek pun umum.
Bingung??hehe
Mari lihat contoh di bawah ini.
===================
Soal Contoh 7
Misalkan terdapat tiga objek \(a, b\) dan \(c\). Syarat pengambilan objek tersebut sebagai berikut
Objek \(a\) boleh diambil paling banyak 2 kali
Objek \(b\) boleh diambil paling banyak 1 kali
Objek \(c\) boleh diambil paling banyak 1 kali
Ada berapa banyak cara pengambilan \(k\) objek dengan syarat di atas ?
Solusi Soal Contoh 7
Misalkan \(a_{k}\) adalah banyak cara pengambilan \(k\) objek dengan syarat yang ditentukan.
Fungsi pembangkit untuk masalah ini adalah\[\boldsymbol{P(x)=\sum_{k=0}^{\infty}a_{k}x^{k}}\]Berdasarkan syarat yang ditentukan
Objek \(a\) dapat dipilih 0, 1, dan 2 kali, bbjek \(a\) dapat dipilih 0 dan 1kali, objek \(a\) dapat dipilih 0 dan 1 kali
Objek \(a\) dapat dipilih 0, 1, dan 2 kali, bbjek \(a\) dapat dipilih 0 dan 1kali, objek \(a\) dapat dipilih 0 dan 1 kali
Maka fungsi pembangkit yang dipakai adalah\[
\begin{eqnarray*}
P(x)&=&\left[(ax)^{0}+(ax)^{1}+(ax)^{2}\right]\left[(bx)^{0}+(bx)^{1}\right]\left[(cx)^{0}+(cx)^{1}\right]\\
&=&\left(1+ax+a^{2}x^{2}\right)\left(1+bx\right)\left(1+cx\right)\\
&=&1+(a+b+c)x+(ab+bc+ac+a^{2})x^{2}+(abc+a^{2}b+a^{2}c)x^{3}+(a^{2}bc)x^{4}
\end{eqnarray*}
\]Jika dilhat persamaan terakhir, koefisien \(x^{k}\) mengindikasikan memilih \(k\) objek dengan syarat yang telah ditentukan.
\begin{eqnarray*}
P(x)&=&\left[(ax)^{0}+(ax)^{1}+(ax)^{2}\right]\left[(bx)^{0}+(bx)^{1}\right]\left[(cx)^{0}+(cx)^{1}\right]\\
&=&\left(1+ax+a^{2}x^{2}\right)\left(1+bx\right)\left(1+cx\right)\\
&=&1+(a+b+c)x+(ab+bc+ac+a^{2})x^{2}+(abc+a^{2}b+a^{2}c)x^{3}+(a^{2}bc)x^{4}
\end{eqnarray*}
\]Jika dilhat persamaan terakhir, koefisien \(x^{k}\) mengindikasikan memilih \(k\) objek dengan syarat yang telah ditentukan.
Jadi, jika \(a=b=c=d=1\) maka koefisien \(x^{k}\) menyatakan banyaknya cara memilih \(k\) objek tersebut.
Sehingga, persamaan pembangkit dari masalah ini menjadi\[
\begin{eqnarray}
P(x)&=&1+3x+4x^{2}+3x^{3}+x^{4}\\
P(x)&=&(1+x+x^{2}+x^{3})(1+x)(1+x)
\end{eqnarray}
\]===================
\begin{eqnarray}
P(x)&=&1+3x+4x^{2}+3x^{3}+x^{4}\\
P(x)&=&(1+x+x^{2}+x^{3})(1+x)(1+x)
\end{eqnarray}
\]===================
Soal Contoh 8
Tentukan fungsi pembangkit untuk banyaknya cara memilih \(r\) objek dari \(n\) objek, dengan pengulangan tidak diperkenankan.
Penyelesaian Soal Contoh 8
Karena pengulangan tidak diperbolehkan maka pengambilang masing-masing objek hanya boleh 0 dan 1 kali.
Jadi fungsi pembangkit adalah\[
\begin{array}
G(x)&=&\underbrace{(1+x)(1+x) \cdots (1+x)}_{n}\\
&=&(1+x)^{n}\\
&=&\sum\limits_{k=0}^{\infty}C(n,k)~x^{k}
\end{array}
\]
\begin{array}
G(x)&=&\underbrace{(1+x)(1+x) \cdots (1+x)}_{n}\\
&=&(1+x)^{n}\\
&=&\sum\limits_{k=0}^{\infty}C(n,k)~x^{k}
\end{array}
\]
