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