Fungsi Pembangkit Biasa (Ordinary GF)

Fungsi pembangkit adalah teknik yang sangat kuat untuk menangani masalah pencacahan dan relasi rekurensi dengan mengubah barisan bilangan menjadi objek aljabar formal (deret kuasa).

1. Definisi Fungsi Pembangkit Biasa

Definisi (Fungsi Pembangkit Biasa (OGF))

Misalkan $a_{0}, a_{1}, a_{2}, \dots$ adalah sebuah barisan bilangan. Fungsi pembangkit biasa (FPB) dari barisan tersebut adalah deret kuasa tak hingga:

$A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n} = a_{0} + a_{1} x + a_{2} x^{2} + \dots$

2. Deret Kuasa Penting

$\frac{1}{1 - x} = \sum_{n = 0}^{\infty} x^{n} = 1 + x + x^{2} + x^{3} + \dots$
$\frac{1}{( 1 - x ) ^{2}} = \sum_{n = 0}^{\infty} (n + 1) x^{n} = 1 + 2 x + 3 x^{2} + \dots$
$(1 + x)^{n} = \sum_{k = 0}^{n} (k n) x^{k}$
$\frac{1}{( 1 - x ) ^{k}} = \sum_{n = 0}^{\infty} (n n + k - 1) x^{n}$ (Penting untuk kombinasi multiset)

Contoh Soal & Pembahasan

Contoh (Masalah Pemilihan Apel)

Tentukan banyaknya cara untuk memilih 10 apel dari 3 jenis apel berbeda sedemikian sehingga setiap jenis apel dipilih setidaknya 1 dan tidak lebih dari 4.

Latihan Soal

✏️ Latihan Soal 1 (Koefisien OGF Polinomial)

Koefisien dari $x^{12}$ pada fungsi pembangkit biasa $A (x) = (1 + x + x^{2} + x^{3} + x^{4})^{4}$ adalah…

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: $A (x) = (1 - 4 x^{5} + 6 x^{10} - \dots) \sum_{n = 0}^{\infty} (3 n + 3) x^{n}$ .

$1 \cdot (3 15) = 455$ .
$- 4 x^{5} \cdot (3 10) = - 480$ .
$6 x^{10} \cdot (3 5) = 60$ . Total koefisien = $455 - 480 + 60 = 35$ . $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Matching dan Teorema Hall
Sub-Topik Selanjutnya: Fungsi Pembangkit Eksponensial →

Fungsi Pembangkit Biasa (Ordinary GF)

1. Definisi Fungsi Pembangkit Biasa

2. Deret Kuasa Penting

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

Materi Terkait (Linked References) (2)

Fungsi Pembangkit Eksponensial (Exponential GF)

Matching dan Marriage Theorem (Teorema Hall)

Diskusi & Tanya Jawab

Title