[latexpage]
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:
[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]