Matematika Diskrit: Fungsi Pembangkit

Model Fungsi Pembangkit

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 a_r  adalah banyaknya cara untuk memilih r objek dalam suatu prosedur. Maka g(x) adalah fungsi pembangkit untuk a_r  jika g(x) memiliki perluasan polinomial

g(x) = a₀ + a₁x + a₂x² + ... + a_rx^r + ...+ a_nxⁿ

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)ⁿ adalah fungsi pembangkit untuk a^r = C(n,r) yang merupakan banyaknya cara untuk memilih r subjek dari n himpunan. Kita menurunkan ekspansi dari  (1+x)ⁿ dengan terlebih dahulu menunjukkan perkalian dari (a+x)³

(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 x^r dalam (1+x)³ dan lebih umumnya dalam (1+x)ⁿ, mengurangi permasalahan dalam menghitung banyaknya hasil kali yang berbeda dengan tepat x sebanyak r kali dan 1 sebanyak (n-r) kali.

Sehingga koefisien dari x^r dalam (1+x)³ adalah C(3,r) dan dalam (1+x)ⁿ 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 r_i yang berbeda dan terdapat n faktor, maka akan ada r1×r2×r3×...×rn hasil kali yang berbeda. Sebagai contoh, akan ada 2ⁿ faktor (1+x)ⁿ

Dalam perluasan dari (1+x+x²)⁴, himpunan dari hasil kali akan dibariskan dalam bentuk

Bahwa 1, x, x² akan ada dalam setiap entri-entri dalam perkalian, seperti x1x²x

            Dalam bahasan kali ini, yang menjadi perhatian utama kita adalah mengalikan faktor-faktor polinomial yang mana setiap x yang berpangkat dalam setiap faktor memiliki koefisien 1, seperti faktor (1+x+x²+x³) atau (1+x²+x³+...). faktor-faktor tersebut secara lengkap telah terspesifikasi  dengan himpunan dari pangkat x yang berbeda. Ingat bahwa 1 = x⁰. Oleh karena itu perluasan (1) dapat dituliskan kembali sebagai:

(x⁰+x¹)(x⁰+x¹)(x⁰+x¹)=x⁰x⁰x⁰+x⁰x⁰x¹+x⁰x¹x⁰+ x⁰x¹x¹+x¹x⁰x⁰+x¹x⁰x¹+x¹x¹x⁰+x¹x¹x¹

Dan perkalian dari perluasan (2) dapat dituliskan dalam bentuk

……………..(3)

Permasalahan untuk menentukan koefisien dari x^r ketika mengalikan beberapa faktor polinomial dapat diulangi dalam suku-suku eksponen. Mempertimbangkan koefisien  dari x⁵ dalam perluasan dari (1+x+x²)⁴. x⁵ merupakan banyaknya perkalian, seperti x²x⁰x²x¹, dibentuk melalui perluasan (3) yang mana jumlah dari pangkatnya adalah 5. Menentukan koefisien dari x⁵ dalam (1+x+x²)⁴ dapat dimodelkan sebagai solusi bulat dari suatu bentuk permasalahan persamaan. Banyaknya perkalian   yang sama dengan x⁵ adalah sama dengan banyaknya solusi bulat dari

Lebih umumnya, koefisien dari x^r dalam (1+x+x²)⁴, diperoleh melalui banyaknya perkalian   yang sama dengan x^r, dan banyaknya solusi bulat  adalah

Permasalahan diatas sama artinya dengan banyaknya cara memilih r objek dari empat tipe dengan paling banyak setiap tipe muncul 2 kali. Oleh karena itu (1+x+x²)⁴ adalah fungsi pembangkit untuk a^r.

Kali ini , kita hanya memperhatikan bagaimana membangun model-model fungsi pembangkit untuk menghitung permasalahan-permasalahan. Kita harus tahu bagaimana koefisien-koefisien dari (1+x+x²)⁴ dapat ditafsirkan sebagai solusi-solusi untuk pilihan tertentu dengan pengulangan atau distribusi dari permasalahan objek-objek yang identik. Untuk lebih lanjutnya, akan dibahas contoh –contoh dalam membangun fungsi pembangkit.

Contoh 1:

Temukan fungsi pembangkit untuk, yaitu banyaknya cara untuk memilihbola dari suatu kumpulan yang terdiri dari 3 bola hijau, 3 bola putih, 3 bola biru, dan 3 bola kuning. 

Jawab:

Persoalan ini dapat dimodelkan dalam bentuk solusi bilangan bulat sebagai berikut:

Dimana

Kita akan membentuk formasi perkalian dari faktor-faktor pada suatu polynomial sedemikian hingga jika dikalikan akan diperoleh semua bentuk hasil perkalian

Maka, dibutuhkan empat faktor, tiap factor akan menunjukkan bentuk pengaruhsesuai nilai yang bersesuaian. Maka tiap factor warna akan berbentuk

Karena ada empat warnaberbeda, maka FungsiPembangkit yang bersesuaian adalah

Contoh 2:

Gunakan fungsi pembangkit untuk membuat pemodelan masalah menghitung semua pilihan 6 objek dari 3 tipe objek dengan perulangan hingga 4 objek dari tiap tipe. Buat juga model untuk perulangan tak berhingga.

Jawab:

• Kasus Pertama: Perulangan 4 kali

Masalah pemilihan ini dapat dimodelkan sebagai solusi bulat berbentuk:

Kita tidak diminta untuk menentukan solusi umum untuk banyak cara memilih r objek.  Bagaimanapun dalam membentuk fungsi pembangkit,  kita secara otomatis memodelkan fungsi pembangkit umum untuk r, bukan hanya untuk r = 6. Solusi untuk masalah 6 objek,  berarti kita hanya memerlukan sampai koefisen x⁶ dalam arti: langkah-langkah bias sama dengan. Kita bentuk suatu fungsi pembangkit dengan suatu faktor:

Dari persamaan

Maka pembangkit yang diharapkan adalah:

• Kasus Kedua: Perulangan Tak Terbatas

Membolehkan pengulangan tak terbatas,  berarti sebarang bilangan dapat dipilih untuk tiap tipe. Maka sebarang nilai eksponen diperbolehkan (walaupun dalam kasus ini, tidak ada eskponen yang lebih dari 6). Karena itu, jawabannya adalah koefisien daripada . Jadi faktornya berupa deret takhingga

Pada kasus perulangan tak terbatas di atas, pilihan eksponen tidak boleh melebihi 6,  maka untuk tiga tipe bola tersebut, fungsi pembangkitnya adalah

Contoh 3:

Temukan fungsi pembangkit untuk yaitu banyaknya cara untukmendistribusikan objek identik ke dalam 5 kotak berbeda,  dengan ketentuan dua kotak pertama tidak memuat bilangan genap lebih dari 10, dan bilangan antara 3 dan 5 pada kotak-kotak lainnya.

Karena batasan dirancang untuk 1 bit, maka solusinya adalah solusi bulat dengan batas yang wajar. Semua solusi bulatnya berbentuk

Untuk membentuk semua hasil kali dari bentuk

                                                                                   

Sesuai batasan masing-masing ,  kita kalikan ke-lima faktornya, masing-masing memuat unsur dengan basis  yakni. Sebagai contoh, unsur yang bersesuaian denganadalah

Maka, fungsi pembangkit yang sesuai adalah

Contoh 4

Gunakan fungsipembangkituntukmembuat 5 kombinasidarihuruf-huruf  dimana boleh muncul kapan saja,  tapi hanya boleh muncul maksimal satu kali. Tentukan koefisien fungsi pembangkit momennya.

Jawab:

Menuju hasil perkalian berikut

Sesuai batasannya, sebagai contoh unsur untukadalah

Sehingga fungsi pembangkit yang diinginkan adalah