Fungsi Pembangkit (Matdis)

1. Fungsi Pembangkit Biasa dan Eksponen

Misal (a_n) = (a₁, a₂, a₃, ...) suatu barisan.

A. Fungsi Pembangkit Biasa / Ordinary Generating Function (OGF)

Fungsi pembangkit biasa dari barisan (a_n) didefinisikan sebagai

B. Fungsi Pembangkit Eksponensial / Exponential Generating Function (EGF)
Fungsi pembangkit eksponensial dari barisan (a_n) didefinisikan sebagai

contoh:

1. Tentukan barisan terkait dengan e^x baik sebagai OGF maupun EGF.

rumus e^x ini merupakan fungsi pembangkit biasa untuk barisan a_n = 1/n!, dan fungsi pembangkit eksponensial untuk barisan a_n = 1.

2. Tentukan OGF dari barisan bilangan genap dimulai dari 0.

0, 2, 4, 6, ...

P(x) = 2x + 4x² + 6x³ + ... + 2nxⁿ + ... = 2x(1 + 2x + 3x² + 4x³ + ... + nx^n-1 + ...)

2. Fungsi Pembangkit untuk Kombinasi

A. Fungsi pembangkit untuk kombinasi tanpa perulangan

Misal dipilih sebanyak r objek dari n objek tanpa perulangan. Karena tidak dibolehkan perulangan, setiap objek hanya dapat dipilih sebanyak 0 atau 1 kali, sehingga masing-masing objek memiliki fungsi pembangkit 1 + x. Fungsi pembangkit biasa untuk kombinasi ini adalah:

P(x) = (1 + x)(1 + x)...(1 + x) sebanyak n faktor.

koefisien untuk x^r adalah C(n, r).

B. Fungsi pembangkit untuk kombinasi dengan perulangan

Misal dipilih sebanyak r objek dari n objek tanpa perulangan. Karena dibolehkan perulangan, setiap objek dapat dipilih tanpa batasan, sehingga masing-masing objek memiliki fungsi pembangkit (1 + x + x² + x³ + ... + x^n-1 + ...). Untuk |x| < 1, deret geometri tak hingga ini dapat dinyatakan sebagai

Fungsi pembangkit biasa untuk kombinasi ini adalah:

P(x) = (1 – x)⁻ⁿ, dalam binomial

Uraian untuk C(–n, r).(–1)ʳ dalam faktorial

Jadi, fungsi pembangkitnya adalah

3. Fungsi Pembangkit untuk Permutasi

Misal terdapat p macam objek dengan sebanyak n_i objek tipe i untuk 1 ≤ i ≤ p. Banyaknya permutasi dengan panjang k dengan paling banyak n_i objek tipe i sama dengan koefisien x^k/k! dalam fungsi pembangkit eksponensial berikut:

4. Mendistribusikan Objek

A. Distribusi r macam objek berbeda ke dalam n sel berbeda dengan setiap sel mendapatkan paling sedikit satu objek.

Misal terdapat r macam objek yang berbeda, akan didistribusikan ke dalam n sel yang berbeda dengan setiap sel mendapatkan paling sedikit satu objek.

Fungsi pembangkit dari permasalahan ini adalah

koefisien x^r/r! dalam e^x(n-k) adalah (n – k)ʳ, sehingga koefisien x^r/r! dalam P(x) adalah

koefisien bentuk terakhir ini adalah banyaknya cara.
B. Distribusi r macam objek berbeda ke dalam n sel identik dengan setiap sel mendapatkan paling sedikit satu objek.

Misal terdapat r macam objek yang berbeda, akan didistribusikan ke dalam n sel yang identik dengan setiap sel mendapatkan paling sedikit satu objek.

Karena sel identik, koefisien pada poin A dibagi n!

Contoh Soal

1. Tentukan fungsi pembangkit dimana koefisien xʳ adalah banyak solusi bulat tak negatif dari persamaan 2a + 3b + 5c = r.

Barisan untuk 2a adalah 0, 2, 4, 6, ...

Barisan untuk 3b adalah 0, 3, 6, 9, ...

Barisan untuk 5c adalah 0, 5, 10, 15, ...

P(x) = (1 + x² + x⁴ + x⁶ + ...)(1 + x³ + x⁶ + x⁹ + ...)(1 + x⁵ + x¹⁰ + x¹⁵ + ...)

2. Terdapat 15 paket pupuk dengan setiap paket adalah kesatuan dan tidak bisa dibagi. Paket-paket pupuk tersebut akan didistribusikan ke kota A, B, dan C dengan ketentuan: 

Kota A menerima minimal 3 paket dan maksimal 7 paket 

Kota B menerima minimal 5 paket dan maksimal 6 paket 

Kota C menerima minimal 5 paket

Berikan fungsi pembangkit untuk mencari banyaknya cara distribusi yang memenuhi ketentuan tersebut.

Tidak diberikan batasan untuk kota C, tetapi misalkan kota A dan B masing-masing menerima paketnya minimal, ada 15 – (3 + 5) = 7 paket untuk kota C. Ini berarti kota C akan menerima paket minimal 5 dan maksimal 7.

Banyaknya solusi dengan batasan-batasan yang diberikan adalah koefisien dari x¹⁵ dalam perluasan (x³ + x⁴ + x⁵ + x⁶ + x⁷)(x⁵ + x⁶)(x⁵ + x⁶ + x⁷).

Jadi, P(x) = (x³ + x⁴ + x⁵ + x⁶ + x⁷)(x⁵ + x⁶)(x⁵ + x⁶ + x⁷)