Pembahasan Soal 5 Fungsi Pembangkit

Soal

Gunakan fungsi pembangkit untuk mencari banyaknya kombinasi token bernilai 1 dollar, 2 dollar, and 5 dollar  untuk membayar barang seharga r dollar di mesin penjual (baik memperhatikan urutan, maupun tidak memperhatikan urutan).

Pembahasan

Pertimbangkan kasus ketika urutan token yang dimasukkan tidak menjadi masalah. Di sini, yang dipedulikan hanyalah jumlah setiap token yang digunakan untuk menghasilkan total r dolar. Karena kita dapat menggunakan sejumlah token 1 dollar, sejumlah token 2 dollar, dan sejumlah token 5 dollar, jawabannya adalah koefisien x^r dalam fungsi pembangkit

(1 + x + x^2 + x^3 + \dots)(1 + x^2 + x^4 + x^6 + \dots)(1 + x^5 + x^{10} + x^{15} + \dots).

Faktor pertama dalam perkalian ini mewakili banyaknya token 1 dollar yang digunakan, yang kedua adalah banyaknya token 2 dollar yang digunakan, dan yang ketiga banyaknya token 5 dollar yang digunakan. Misalnya, banyaknya cara untuk membayar barang seharga 7 dollar menggunakan token 1 dollar, 2 dollar, dan 5 dollar diberikan oleh koefisien x^7 dalam ekspansi ini, yang sama dengan 6.

Ketika urutan token yang dimasukkan penting, banyak cara untuk memasukkan tepat n token untuk menghasilkan total r dolar adalah koefisien dari x^r dalam {(x + x^2 + x^5)}^n, karena masing-masing r token dapat berupa token 1 dollar, token 2 dollar, atau token 5 dollar. Karena sejumlah token dapat dimasukkan, banyaknya cara untuk menghasilkan r dolar menggunakan token 1 dollar, 2 dollar, atau 5 dollar, bila urutan token yang dimasukkan penting, adalah koefisien x^r dalam

    \begin{align*} 1 + (x + x^2 + x^5) + {(x + x^2 + x^5)}^2 + \dots & = \dfrac{1}{1 - (x + x^2 + x^5)} \\ & = \dfrac{1}{1 - x - x^2 - x^5}, \end{align*}

di mana kita telah menambahkan banyak cara untuk memasukkan 0 token, 1 token, 2 token, 3 token, dan seterusnya, dan di mana kita telah menggunakan identitas \dfrac{1}{1 - x} = 1 + x + x^2 + \dots dengan x diganti dengan x + x^2 + x^5.

Misalnya, jumlah cara untuk membayar barang seharga 7 dengan menggunakan token 1, 2, dan 5, jika urutan penggunaan token penting, adalah koefisien x^7 dalam ekspansi ini, yang sama dengan 26. Untuk melihat bahwa koefisien ini sama dengan 26, diperlukan penambahan koefisien x^7 dalam ekspansi {(x + x^2 + x^5)}^k untuk 2 \leq k \leq 7.

 

Credit: Ramadhani Latief Firmansyah

 

Video Penjelasan:

Leave A Comment

Alamat email Anda tidak akan dipublikasikan.

*