Pembahasan Soal 7 Fungsi Pembangkit

Soal

Use generating functions to find the number of r-combinations from a set with n elements when repetition of elements is allowed.

Pembahasan

Misalkan G(x) adalah fungsi pembangkit untuk barisan \{ a_r \}, di mana a_r sama dengan banyaknya jumlah r-kombinasi dari suatu himpunan dengan n elemen dengan pengulangan yang diperbolehkan. Yaitu, G(x) = \sum_{r = 0} ^{\infty} a_rx^r. Karena kita dapat memilih sejumlah anggota tertentu dari himpunan dengan n elemen ketika kita membentuk kombinasi-r dengan pengulangan yang diperbolehkan, masing-masing dari n elemen berkontribusi (1 + x + x^2 + x^3 + \dots) pada ekspansi perkalian untuk G(x). Setiap elemen memberikan kontribusi faktor tersebut karena dapat dipilih nol kali, satu kali, dua kali, tiga kali, dan seterusnya, ketika r-kombinasi terbentuk (dengan total r elemen yang dipilih).

Karena ada n elemen dalam himpunan dan masing-masing memberikan kontribusi faktor yang sama tersebut untuk ke G(x), didapatkan G(x) = {(1 + x + x^2 + x^3 + \dots)}^n. Selama \lvert x \rvert < 1, didapatkan 1 + x + x^2 + \dots = \dfrac{1}{1 - x}, jadi G(x) = \dfrac{1}{{(1 - x)}^n} = {(1 - x)}^{-n}. Dengan menerapkan teorema binomial yang diperluas (Misalkan x adalah bilangan real dengan \lvert x \rvert < 1 dan misalkan u bilangan real, maka {(1 + x)}^u = \sum_{k = 0}^{\infty} \binom{u}{k} x^k.), maka didapatkan {(1 - x)}^{-n} = {(1 + (-x))}^{-n} = \sum_{r = 0}^{\infty} \binom{-n}{r} {(-x)}^r. Banyaknya r-kombinasi dari suatu himpunan dengan n elemen dengan pengulangan yang diperbolehkan, ketika r adalah bilangan bulat positif, adalah koefisien a_r dari x^r dalam jumlah ini. Akibatnya, dengan menggunakan contoh 2, yang memberikan rumus sederhana untuk \binom{-n}{k} = {(-1)}^rC(n + r - 1, r) ditemukan bahwa a_r sama dengan \binom{-n}{r} {(-1)}^r = {(-1)}^rC(n + r - 1, r) \cdot {(-1)}^r = C(n + r - 1, r).

Credit: Ramadhani Latief Firmansyah

 

Video Penjelasan:

Leave A Comment

Alamat email Anda tidak akan dipublikasikan.

*