Bahasan ini akan memperkenalkan konsep fungsi pembangkit. Fungsi pembangkit dikembangkan untuk menangani batasan-batasan khusus dalam pemilihan dan permasalahan arangement (menyusun objek) dengan pengulangan. Fungsi pembangkit merupakan salah satu teknik pemecahan masalah yang paling abstrak yang diperkenalkan dalam matematika diskrit.
Misalkan ar adalah banyaknya cara untuk memilih r objek dalam suatu prosedur. Maka g(x) adalah fungsi pembangkit untuk ar jika g(x) memiliki perluasan polinomial
g(x) = a0 + a1x + a2x2 + ... + arxr + ...+ anxn
Jika fungsi memiliki suku-suku yang tak terhingga maka fungsi tersebut dikatakan sebuah “deret tak hingga”. Perhatikan Binomial Expansi berikut:
Maka g(x) = (1+x)n adalah fungsi pembangkit untuk ar = C(n,r) yang merupakan banyaknya cara untuk memilih r subjek dari n himpunan. Kita menurunkan ekspansi dari (1+x)n dengan terlebih dahulu menunjukkan perkalian dari (a+x)3
(a+x)(a+x)(a+x)=aaa + aax + axa + axx + xaa +xax + xxa +xxx
Ketika a = 1, maka diperoleh:
(1+x)(1+x)(1+x)=111+11x+1x1+1xx+x11+x1x+xx1+xxx …………(1)
Suatu perluasan/ekspansi secara umum yaitu mendaftarkan sebuah suku dalam faktor yang pertama dikalikan dengan faktor kedua dan ketiga. Permasalahan dalam menentukan koefisien xr dalam (1+x)3 dan lebih umumnya dalam (1+x)n, mengurangi permasalahan dalam menghitung banyaknya hasil kali yang berbeda dengan tepat x sebanyak r kali dan 1 sebanyak (n-r) kali.
Sehingga koefisien dari xr dalam (1+x) 3 adalah C (3,r) dan dalam (1+x) n adalah C (n,r).
Hal tersebut sangat penting bahwa perkalian dari beberapa faktor-faktor polinomial dapat terlihat sebagai koleksi pembangkit dari semua hasil kali yang ditemukan sebagai perkalian tiap-tiap suku dalam tiap-tiap faktor polinomial. Jika faktor polinomial ke-i memuat suku-suku ri yang berbeda dan terdapat n faktor, maka akan ada r1×r2×r3×...×rn hasil kali yang berbeda. Sebagai contoh, akan ada 2n faktor (1+x)n
Posting Komentar