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 Batalkan balasan

Artikel Terbaru

Komentar