Pembahasan Soal 8 Fungsi Pembangkit

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:

Leave A Comment

Alamat email Anda tidak akan dipublikasikan.

*