[latexpage]
Soal
Use generating functions to find the number of ways to select $r$ objects of $n$ different kinds if we must select at least one object of each kind.
Pembahasan
Karena perlu dipilih setidaknya satu objek dari setiap jenis, masing-masing dari $n$ jenis objek menyumbang faktor $(x + x^2 + x^3 + \dots)$ ke fungsi pembangkit $G(x)$ untuk barisan $\{ a_r \}$, dengan $a_r$ adalah banyaknya jumlah cara untuk memilih $r$ objek dari $n$ jenis yang berbeda jika dibutuhkan setidaknya satu objek dari setiap jenis. Oleh karena itu, $G(x) = {(x + x^2 + x^3 + \dots)}^n = x^n{(1 + x + x^2 + \dots)}^n = \dfrac{x^n}{{(1 – x)}^n}$. Dengan menggunakan teorema binomial yang diperluas dan contoh 2 yang memberikan rumus sederhana untuk $\binom{-n}{k} = {(-1)}^rC(n + r – 1, r)$, diperoleh
\begin{align*}
G(x) & = \dfrac{x^n}{{(1 – x)}^n} \\
& = x^n \cdot {(1 – x)}^{-n} \\
& = x^n \sum_{r = 0}^{\infty} \binom{-n}{r} {(-x)}^r \\
& = x^n \sum_{r = 0}^{\infty} {(-1)}^rC(n + r – 1, r){(-1)}^rx^r \\
& = \sum_{r = 0}^{\infty} C(n + r – 1, r)x^{n + r} \\
& = \sum_{t = n}^{\infty} C(t – 1, t – n)x^t \\
& = \sum_{r = n}^{\infty} C(r – 1, r – n)x^r.
\end{align*}
Telah digeser penjumlahan dalam persamaan berikutnya-ke-terakhir dengan menetapkan $t = n + r$ sehingga $t = n$ ketika $r = 0$ dan $n + r – 1 = t – 1$, dan kemudian diganti $t$ dengan $r$ sebagai indeks penjumlahan dalam persamaan terakhir untuk kembali ke notasi awal asli. Oleh karena itu, ada $C(r – 1, r – n)$ cara untuk memilih $r$ objek dari $n$ jenis yang berbeda jika harus dipilih setidaknya satu objek dari setiap masing-masing jenis.
Credit: Ramadhani Latief Firmansyah
Video Penjelasan:
[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]