Fungsi Pembangkit Biasa & Eksponensial

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

1. Fungsi Pembangkit Biasa (Ordinary Generating Functions)

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$

Bentuk Tertutup Deret Kuasa Penting

$\frac{1}{1 - x} = 1 + x + x^{2} + x^{3} + \dots = \sum_{n = 0}^{\infty} x^{n}$
$\frac{1}{( 1 - x ) ^{2}} = 1 + 2 x + 3 x^{2} + \dots = \sum_{n = 0}^{\infty} (n + 1) x^{n}$
$(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}$ (Sangat penting untuk kombinasi multiset)

2. Fungsi Pembangkit Eksponensial (Exponential GF)

Jika fungsi pembangkit biasa digunakan untuk masalah pemilihan (kombinasi), maka fungsi pembangkit eksponensial digunakan untuk masalah penyusunan (permutasi).

Definisi (Fungsi Pembangkit Eksponensial (EGF))

Fungsi pembangkit eksponensial dari barisan $a_{0}, a_{1}, a_{2}, \dots$ didefinisikan sebagai:

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

Deret Eksponensial Penting

Bebas: $e^{x} = \sum_{n = 0}^{\infty} \frac{x ^{n}}{n !}$
Jumlah Genap: $\frac{e ^{x} + e ^{- x}}{2} = \sum_{n = 0}^{\infty} \frac{x ^{2 n}}{( 2 n )!}$
Jumlah Ganjil: $\frac{e ^{x} - e ^{- x}}{2} = \sum_{n = 0}^{\infty} \frac{x ^{2 n + 1}}{( 2 n + 1 )!}$

Contoh Soal & Pembahasan

Contoh (Aplikasi OGF pada 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.

Contoh (Aplikasi EGF pada Pewarnaan Barisan)

Tentukan banyaknya cara menyusun barisan panjang $n$ menggunakan warna Merah, Putih, dan Biru sedemikian sehingga warna Merah muncul dalam jumlah genap.

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) = (\frac{1 - x ^{5}}{1 - x})^{4} = (1 - 4 x^{5} + 6 x^{10} - 4 x^{15} + \dots) (1 - x)^{- 4}$ . Deret $(1 - x)^{- 4} = \sum_{n = 0}^{\infty} (3 n + 3) x^{n}$ . Mencari koefisien $x^{12}$ :

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

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Pengantar Teori Graf
Sub-Topik Selanjutnya: Latihan Akhir Modul Kombinatorika →

Fungsi Pembangkit Biasa & Eksponensial

1. Fungsi Pembangkit Biasa (Ordinary Generating Functions)

Bentuk Tertutup Deret Kuasa Penting

2. Fungsi Pembangkit Eksponensial (Exponential GF)

Deret Eksponensial Penting

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

🏆 Soal ONMIPA Terkait (1 Soal)

Materi Terkait (Linked References) (7)

Fungsi Pembangkit Biasa (Ordinary GF)

Fungsi Pembangkit Eksponensial (Exponential GF)

Latihan Akhir Modul Kombinatorika ONMIPA

Latihan Akhir - Bagian I: Isian Singkat

Matching dan Marriage Theorem (Teorema Hall)

Teori Graf Dasar, Graf Eulerian, Hamiltonian & Teorema Hall

Naskah Soal & Pembahasan KNMIPA PT 2021 — Seleksi Wilayah

Diskusi & Tanya Jawab

Title