[latexpage]

Soal

Use generating functions to find the number of $k$-combinations of a set with $n$ elements. Assume that the binomial theorem has already been established.

Pembahasan

Masing-masing dari $n$ elemen dalam himpunan menyumbangkan suku $(1 + x)$ ke fungsi pembangkit $f(x) = \sum_{k = 0}^{n} a_kx^k$. Di sini $f(x)$ adalah fungsi pembangkit untuk $\{ a_k \}$, di mana $a_k$ menyatakan jumlah banyaknya $k$-kombinasi dari suatu himpunan dengan $n$ elemen. Karena itu, $f(x) = (1 + x)^n$. Tetapi dengan teorema binomial, didapatkan $f(x) = \sum_{k = 0}^{n} \binom{n}{k}x^k$, dengan $\binom{n}{k} = \dfrac{n!}{k!(n – k)!}$. Oleh karena itu, $C(n, k)$, banyaknya jumlah $k$-kombinasi dari suatu himpunan dengan $n$ elemen, adalah $\dfrac{n!}{k!(n – k)!}$. read more

[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 read more

[latexpage]

Soal

Berapa banyak cara delapan biskuit dapat diberikan ke 3 anak sehingga setiap anak menerima minimal 2 biskuit dan tidak lebih dari 4 biskuit?

Pembahasan

Karena setiap anak menerima setidaknya paling sedikit dua tetapi tidak lebih dari empat kue, untuk setiap anak ada faktor yang sama dengan $(x^2 + x^3 + x^4)$ dalam fungsi pembangkit untuk barisan $\{ c_n \}$, di mana $c_n$ adalah jumlah cara untuk membagikan sebanyak $n$ buah kue. Karena ada tiga anak, maka fungsi pembangkit ini adalah ${(x^2 + x^3 + x^4)}^3$. Kita membutuhkan koefisien $x^8$ dalam hasil kali ini. Alasannya adalah bahwa suku $x^8$ dalam ekspansi sesuai dengan cara pemilihan tiga suku, dengan satu dari setiap faktor, yang memiliki pangkat yang ditambahkan hingga berjumlah 8. read more

[latexpage]

Soal

Carilah banyaknya solusi bulat dari $e_1 + e_2 + e_3 = 17$, dengan $e_1$, $e_2$, and $e_3$ bilangan bulat tak negatif yang memenuhi $2 \leq e_1 \leq 5,$ $3 \leq e_2 \leq 6$, dan $4 \leq e_3 \leq 7$.

Pembahasan

Banyaknya solusi dengan batasan-batasan yang diberikan adalah koefisien dari $x^{17}$ dalam perluasan $(x^2 + x^3 + x^4 + x^5)(x^3 + x^4 + x^5 + x^6)(x^4 + x^5 + x^6 + x^7)$. Hal ini terjadi karena kita memperoleh suku yang sama dengan $x^{17}$ pada hasil kali dengan memilih suku pada jumlah pertama $x^{e_1}$, suku pada jumlah kedua $x^{e_2}$, dan suku pada jumlah ketiga $x^{e_3}$, di mana eksponen $e_1$, $e_2$, dan $e_3$ memenuhi persamaan $e_1 + e_2 + e_3 = 17$ dan batasan-batasan yang diberikan. Tidak sulit untuk melihat bahwa koefisien $x^{17}$ pada hasil kali ini adalah 3. Oleh karena itu, ada tiga solusi. read more

[latexpage]

Soal

Apakah fungsi pembangkit dari barisan $1, 1, 1, 1, 1, 1$?

Pembahasan

Fungsi pembangkit dari 1, 1, 1, 1, 1, 1 adalah $1 + x + x^2 + x^3 + x^4 + x^5$. Sehingga dengan teorema jika $a$ dan $r$ adalah bilangan real dan $r \neq 0$, maka
\begin{equation*}
\sum_{j = 0}^{n} ar^j =
\begin{cases}
\dfrac{ar^{n + 1} – a}{r – 1} & \text{jika $r \neq 1$,}
(n + 1)a & \text{jika $r = 1$.}
\end{cases}
\end{equation*}
didapatkan $\dfrac{x^6 – 1}{x – 1} = 1 + x + x^2 + x^3 + x^4 + x^5$ dengan $x \neq 1$. Akibatnya, $G(x) = \dfrac{x^6 – 1}{x – 1}$ adalah fungsi pembangkit dari barisan 1, 1, 1, 1, 1, 1. read more

[latexpage]

Soal Diberikan barisan $(a_{n})$ yang memenuhi relasi rekurensi
\begin{equation*}
a_{n}=n^{2}a_{n-1}+(n-1)\cdot n!
\end{equation*}
untuk setiap $n\geq 1$ dan dengan suku awal $a_{0}=6$. Dengan menggunakan fungsi pembangkit, tentukan formula untuk $a_{n}$.

Pembahasan

Dibentuk barisan $\{b_{n}\}_{n\geq 0}$ dengan
\begin{equation*}
b_{n}=\displaystyle \frac{a_{n}}{n!}
\end{equation*}
untuk setiap $n\geq 0$.
Diperhatikan bahwa untuk $n\geq 1$ berlaku
\begin{equation*}
\begin{split}
a_{n}&=n^{2}a_{n-1}+(n-1)\cdot n!\\
(n!)^{2}b_{n}&=n^{2}((n-1)!)^{2}b_{n-1}+(n-1)\cdot n!\\
n!b_{n}&=n!b_{n-1}+(n-1)\\
b_{n}&=b_{n-1}+\displaystyle \frac{n-1}{n!}
\end{split}
\end{equation*}
dan $b_{0}=a_{0}=6$.
\newline
Selanjutnya, misalkan $B(x)$ adalah fungsi pembangkit untuk barisan $\{b_{n}\}_{n\geq 0}$. Dengan demikian
\begin{equation*}
\begin{split}
B(x)&=\displaystyle \sum_{n=0}^{\infty}b_{n}x^{n}\\
B(x)&=b_{0}+\displaystyle \sum_{n=1}^{\infty}b_{n}x^{n}\\
B(x)&=6+\displaystyle \sum_{n=1}^{\infty}\left(b_{n-1}+\displaystyle \frac{n-1}{n!}\right)x^{n}\\
B(x)&=6+\displaystyle \sum_{n=1}^{\infty}b_{n-1}x^{n}+\displaystyle \sum_{n=1}^{\infty}\left(\displaystyle \frac{n-1}{n!}\right)x^{n}\\
B(x)&=6+x\displaystyle \sum_{n=1}^{\infty}b_{n-1}x^{n-1}+\displaystyle \sum_{n=1}^{\infty}\left(\displaystyle \frac{n-1}{n!}\right)x^{n}\\
B(x)&=6+x\displaystyle \sum_{n=0}^{\infty}b_{n}x^{n}+\displaystyle \sum_{n=1}^{\infty}\left(\displaystyle \frac{n}{n!}\right)x^{n}-\displaystyle \sum_{n=1}^{\infty}\left(\displaystyle \frac{1}{n!}\right)x^{n}\\
B(x)&=6+x\displaystyle \sum_{n=0}^{\infty}b_{n}x^{n}+x\displaystyle \sum_{n=1}^{\infty}\left(\displaystyle \frac{1}{(n-1)!}\right)x^{n-1}-\displaystyle \sum_{n=1}^{\infty}\left(\displaystyle \frac{1}{n!}\right)x^{n}\\
B(x)&=6+xB(x)+x\displaystyle \sum_{n=0}^{\infty}\left(\displaystyle \frac{1}{n!}\right)x^{n}-\displaystyle \sum_{n=1}^{\infty}\left(\displaystyle \frac{1}{n!}\right)x^{n}\\
(1-x)B(x)&=6+xe^{x}-(\displaystyle e^{x}-1)\\
(1-x)B(x)&=6+xe^{x}-e^{x}+1\\
(1-x)B(x)&=7+(x-1)e^{x}\\
B(x)&=\displaystyle \frac{7}{1-x}-e^{x}
\end{split}
\end{equation*}
Dengan demikian diperoleh $b_{n}=7-\displaystyle \frac{1}{n!}$ untuk setiap $n\geq 0$.
\newline
Mengingat \begin{equation*}
b_{n}=\displaystyle \frac{a_{n}}{n!}
\end{equation*}
untuk setiap $n\geq 0$, diperoleh
$$a_{n}=(n!)^{2}b_{n}=(n!)^{2}\left(7-\displaystyle \frac{1}{n!}\right)=7(n!)^{2}-n!$$ read more

[latexpage]

Soal Diberikan barisan Fibonacci $(F_{n})$ dengan $F_{0}=0$ dan $F_{1}=1$

[latexpage]

Soal Solve the recurrence relation $$a_{n}=3a_{n-1}-2a_{n-2}+4n\cdot 3^{n},$$ with initial conditions $a_{0} = -44, a_{1} = -78$.

Pembahasan

Diberikan relasi rekurensi $$a_{n}=3a_{n-1}-2a_{n-2}+4n\cdot 3^{n},$$ dengan nilai awal $a_{0} = -44, a_{1} = -78$.
Diperhatikan bahwa polinomial karakteristik rekurensi linear homogen yang berkorespondensi dengan relasi rekurensi tersebut adalah
$$p(x)=x^{2}-3x+2=(x-1)(x-2)$$
dengan akar-akarnya adalah $1$ dan $2$. Dengan demikian solusi homogennya mempunyai bentuk
$$a_{n}^{(h)}=A+B2^{n}$$ untuk suatu bilangan real $A$ dan $B$. read more

[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]

[latexpage]

Soal Diberikan barisan $\{a_{n}\}$ dengan relasi rekurensi $a_{n+2}=4a_{n+1}-4a_{n}$ untuk $n\geq 0$ dan nilai awal $a_{0}=3$ dan $a_{1}=7$. Tentukan formula untuk $a_n$.

Pembahasan

Persamaan karakteristik yang bersesuaian adalah $p(x) = x^{2}-4x+4$. Diperoleh $k = 2$, $m_{1} = 2$, $r_{1} = 2$ yang menghasilkan
\[ a_{n} = (A_{0}+A_{1}n)2^{n} .\]
Dari nilai awal, ketika disubstitusi menjadi
\begin{equation*}
\begin{split}
3 = a_{0} &= A_{0}\\
10= a_{1}&=2A_{0}+2A_{1}.
\end{split}
\end{equation*}
Diperoleh
\begin{equation*}
A_{0}=3~\text{dan}~A_{1}=2.
\end{equation*}
Jadi $a_{n}=(A_{0}+A_{1}n)2^{n}=(3+2n)2^{n}=3\cdot2^{n}+n\cdot2^{n+1}$ untuk setiap $n\geq 0$. read more

[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]

[latexpage]

Soal Diberikan barisan $\{a_{n}\}$ dengan relasi rekurensi $a_{n+2}=2a_{n+1}-a_{n}$ untuk $n\geq 0$ dan nilai awal $a_{0}=3$ dan $a_{1}=7$. Tentukan formula untuk $a_n$.

Pembahasan

Dapat dilihat persamaan karakteristik yang memenuhi adalah $p(x) = x^{2}-2x+1$. Diperoleh $k = 2$, $m_{1} = 2$, $r_{1} = 1.$ Hal ini mengakibatkan

\[ a_{n} = (A_{0}+A_{1}n)1^{n} .\]

\begin{equation*}
\begin{split}
3 = a_{0} &= A_{0}\\
7= a_{1}&=A_{0}+A_{1}.
\end{split}
\end{equation*}
Diperoleh
\begin{equation*}
A_{0}=3~\text{dan}~A_{1}=4 .
\end{equation*}
Jadi $a_{n}=(A_{0}+A_{1}n)1^{n}=3+4n$ untuk setiap $n\geq 0.$ read more