Aplikasi Fungsi Pembangkit dalam Masalah Counting

martha yunanda fungsi pembangkit, kombinatorika

Bentuk aplikasi dan penerapan fungsi pembangkit bisa digunakan dalam masalah counting. Contohnya dalam menemukan banyaknya solusi dari persamaan:
$x_1+x_2+x_3+...+x_n = C$,
C adalah konstanta.
dan x adalah bilangan positif dengan batas batas tertentu.

Sebagai contoh:
Tentukan banyak solusi dari
$\begin{align*} e_1+e_2+e_3=17 \end{align*}$
dimana $e_1, e_2, e_3$ adalah bilangan bulat non negatif dengan
$2 \leq e_1 \leq 5 \\ 3 \leq e_2 \leq 6 \\ 4 \leq e_3 \leq 7$

Jawab:
Banyaknya solusi pada batas interval masing masing e adalah koefisien $x^{17}$ dari ekspansi:
$\begin{align*} F(x)&=(x^2+x^3+x^4+x^5)(x^3+x^4+x^5+x^6)(x^4+x^5+x^6+x^7)\\ &=x^2(1+x+x^2+x^3)x^3(1+x+x^2+x^3)x^4(1+x+x^2+x^3)\\ &=x^9(\frac{(1-x^4}{1-x})^3) \end{align*} $

Karena sudah ada $x^9$ terfaktorkan, sisanya anda harus menemukan $x^8$ (ingat $x^{17} = x^9.x^8$ ) dari $\frac{(1-x^4}{1-x})^3$
misal $g(x)=(\frac{1-x^4}{1-x})^3=(1-x^4)^3(1-x)^{-3}$
$h(x)=(1-x^4)^3=1-3x^4+3x^8-x^12$
$i(x) =(1-x)^{-3}$
Pada h(x) terdapat $x^0$ , $x^4$ , $x^{12}$
Agar g (x) menjadi $x^8$ maka

Aplikasi Fungsi Pembangkit dalam Masalah Counting

Akan dicari koefisien nilai a,b,c di atas. pada baris terakhir nilai i(x) tak dicari karena untuk pangkah h(x) saja sudah lebih dari 8.
Untuk $i(x) =(1-x)^{-3}$ disini anda gunakan, baca selengkapnya di Teorema Binomial Diperluas.
Rumus umum teorema binomial diperluas: