Pembahasan soal UAS Matematika Diskrit Tahun 2020

 Oke guys di kesempatan ini mimin akan ngebahas soal UAS Matematika Dikrit tahun 2020. Silahkan disimak dan dipelajari dengan baik. Langsung saja ke pembahasannya.

1. Ingat bahwa polindrom adalah sebuah jajaran objek (huruf) dalam satu baris sedemikian hingga dibaca dari kiri maupun dari kanan sama. Misal : ADA sebuah polindrom Panjang 3, 1221 sebuah polindrom Panjang 4, NABABAN sebuah polindrom Panjang 7. Gunakan Aturan Perkalian, untuk membuktikan bahwa banyak polindrom Panjang 2k atau 2k-1 yang dibentuk dari n objek berbeda sedemikian hingga setiap objek muncul maksimum dua kali adalah $P(n,k) =\frac{n!}{(n-k)!}$

Jawab : Pertama untuk kasus polindrom dengan panjang 2k. Karena objek muncul maksimum dua kali, maka dari itu objek tersebut muncul dua kali atau tidak muncul sama sekali karena polindrom panjang genap. Karena objek ke-(k+1), objek ke-(k+2), ... , objek ke-(2k) berturut turut bisa didapat dari pemilihan objek ke-(k), objek ke-(k-1), ... , objek ke-(1). Oleh karnyanya kita cukup menghitung banyak kemungkinan dari pemilihan objek ke-(k), objek ke-(k-1), ... , objek ke-(1). Tanpa mengurangi keumuman misalkan

$$\begin{align*}T_1&=\text{kemungkinan pemilihan objek ke-1}.\\ &T_1 \text{ bisa dipilih dari } n \text{ objek}\end{align*}$$

$$\begin{align*}T_2&=\text{kemungkinan pemilihan objek ke-2 sehingga objek ke-2}\neq\text{objek ke-1}.\\ &T_2 \text{ bisa dipilih dari } n-1 \text{ objek karena objek ke-2}\neq\text{objek ke-1}\end{align*}$$

$$\begin{align*}T_3&=\text{kemungkinan pemilihan objek ke-3 sehingga objek ke-3}\neq\text{objek ke-2}\neq\text{objek ke-1}.\\ &T_3 \text{ bisa dipilih dari } n-2 \text{ objek karena objek ke-3}\neq\text{objek ke-2}\neq\text{objek ke-1}\end{align*}$$

dan seterusnya hingga

$$\begin{align*}T_k&=\text{kemungkinan pemilihan objek ke-k sehingga objek ke-k}\neq\text{objek ke-(k-1)}\neq\cdots\neq\text{objek ke-1}.\\ &T_k \text{ bisa dipilih dari } n-(k-1) \text{ objek karena objek ke-k}\neq\text{objek ke-(k-1)}\neq\cdots\neq\text{objek ke-1}\end{align*}$$

Jadi, berdasarkan aturan perkalian maka banyak polindrom Panjang 2k yang dibentuk dari n objek berbeda sedemikian hingga setiap objek muncul maksimum dua kali adalah $n(n-1)(n-2)\cdots (n-k+1)=P(n,k) =\frac{n!}{(n-k)!}$

Kemudian untuk kasus polindrom panjang 2k-1 maka objek ke-(k+1), objek ke-(k+2), ... , objek ke-(2k-1) berturut turut bisa didapat dari pemilihan objek ke-(k-1), objek ke-(k-2), ... , objek ke-(1). Oleh karnyanya kita cukup menghitung banyak kemungkinan dari pemilihan objek ke-(k), objek ke-(k-1), ... , objek ke-(1). Yang sudah di hitung sebelumnya pada kasus polindrom panjang 2k. Jadi, banyak polindrom Panjang 2k-1 yang dibentuk dari n objek berbeda sedemikian hingga setiap objek muncul maksimum dua kali adalah $P(n,k) =\frac{n!}{(n-k)!}$.

Dengan demikian terbukti bahwa banyak polindrom Panjang 2k atau 2k-1 yang dibentuk dari n objek berbeda sedemikian hingga setiap objek muncul maksimum dua kali adalah $P(n,k) =\frac{n!}{(n-k)!}$

2. Tentukan banyak cara menempatkan n objek kedalam k kotak, jika:

a. Objek berbeda dan kotak berbeda

b. Objek berbeda dan kotak identik

c. Objek identik dan kotak berbeda

Jawab : a. Perhatikan bahwa kita dapat mengilustrasikannya sebagai berikut. Objek pertama kemungkinan bisa ditempatkan di $k$ kotak. Begitupun objek kedua kemungkinan bisa ditempatkan di $k$ kotak. Hingga objek ke-n juga kemungkinan bisa ditempatkan di $k$ kotak. Dengan aturan perkalian didapat banyak cara untuk kasus ini adalah $k^n$

b. Berdasarkan Stirling numbers of second kind, banyaknya menempatkan $n$ objek berbeda ke dalam $k$ kotak identik dimana setiap kotak tidak boleh kosong adalah

$$\begin{equation*}s(n,k)=\frac{1}{k!}\sum\limits_{i=0}^{k}(-1)^i\binom{k}{i}(k-i)^n\end{equation*}$$

Maka dari itu banyaknya cara menempatkan n objek berbeda kedalam k kotak identik bisa kita menjadi beberapa kasus :

-) Jika tepat satu kotak yang diisi. Banyak cara menempatkannya adalah $s(n,1)$

-) Jika tepat dua kotak yang diisi. Banyak cara menempatkannya adalah $s(n,2)$

dan seterusnya hingga

-) Jika tepat k kotak yang diisi. Banyak cara menempatkannya adalah $s(n,k)$

Oleh karena itu banyaknya cara menempatkan n objek berbeda kedalam k kotak identik adalah

$$\begin{align*}\sum\limits_{j=1}^ks(n,j)&=\sum\limits_{j=1}^k\frac{1}{j!}\sum\limits_{i=0}^{j}(-1)^i\binom{j}{i}(j-i)^n\\ &=\sum\limits_{j=1}^k\sum\limits_{i=0}^{j}(-1)^i\frac{1}{i!(j-i)!}(j-i)^n\end{align*}$$

c. Hal ini sama saja dengan menghitung banyaknya bilangan bulat tak negatif $x_1,x_2,\cdots ,x_k$ yang memenuhi persamaan

$$\begin{equation*}x_1+x_2+\cdots x_k=n\end{equation*}$$

Misalkan $P(x)$ adalah fungsi pembangkit biasa dari kasus tersebut, diperoleh

$$\begin{align*}P(x)&=(1+x+x^2+x^3+\cdots)^k\\ &=\left(\frac{1}{1-x}\right)^k\\ &=(1-x)^{-k}\\ &=\sum\limits_{r=0}^{\infty}\binom{k+r-1}{r}x^r\end{align*}$$

Banyak cara yang kita inginkan adalah koefisien dari $x^n$ pada fungsi pembangkit tersebut yaitu $\binom{k+n-1}{n}$

3. Sebanyak n buah lingkaran Digambar pada bidang datar, sedemikian hingga setiap dua lingkaran berpotongan di tepat dua titik dan tidak ada tiga lingkaran melalui satu titik. Misalkan $a_n$ menyatakan banyak daerah terbentuk.

a. Tunjukkan bahwa relasi rekursif untuk $a_n$ adalah sebagai berikut:

$$\begin{equation*}a_0 = 2; a_n = a_{n-1} + 2(n-1), n \geq 1\end{equation*}$$

b. Selesaikan relasi rekursif tersebut.

Jawab : a. Jelas bahwa $a_1=2$. Untuk $n\geq 2$ maka diberikan $n$ buah lingkaran dengan syarat pada soal maka banyak daerah yang terbentuk adalah $a_n$. Dari $n$ lingkaran tersebut dapat kita pandang dimana terdapat $n-1$ lingkaran dengan syarat pada soal dan sebuah lingkaran digambar dengan memotong $n-1$ lingkaran tersebut dengan syarat pada soal. Karena lingkaran tersebut memotong $n-1$ lingkaran tersebut depat di dua titik, maka akan ada $2(n-1)$ titik potong. Dimana setiap dua titik akan membentuk satu daerah, karena siklis maka akan ada $2(n-1)$ daerah pada satu lingkaran tersebut. Maka diperoleh relasi rekursif untuk $a_n$ adalah

$$\begin{equation*}a_1 = 2; a_n = a_{n-1} + 2(n-1), n \geq 2\end{equation*}$$

Pilih $a_0=2$ agar relasi rekursif tersebut masih berlaku untuk $n\geq 1$. Sehingga bisa kita simpulkan bahwa relasi rekursif dari $a_n$ pada permasalahan tersebut adalah

$$\begin{equation*}a_0 = 2; a_n = a_{n-1} + 2(n-1), n \geq 1\end{equation*}$$

b. Kita akan selesaikan dengan menggunakan fungsi pembangkit. Pertama misalkan $P(x)$ adalah Fungsi pembangkit biasa dari $a_n$.

$$\begin{equation*}P(x)=\sum\limits_{n=0}^{\infty}a_nx^n\end{equation*}$$

Dari bagian rekursif kita punya

$$\begin{equation*}a_n = a_{n-1} + 2(n-1)\end{equation*}$$

Kalikan kedua ruas dengan $x^n$ didapat

$$\begin{align*}a_n x^n&= a_{n-1} x^n+ 2(n-1)x^n\\ \sum\limits_{n=1}^{\infty}a_n x^n&= \sum\limits_{n=1}^{\infty}a_{n-1} x^n+\sum\limits_{n=1}^{\infty} 2(n-1)x^n\\ \sum\limits_{n=0}^{\infty}a_n x^n-a_0&= x\sum\limits_{n=0}^{\infty}a_{n} x^{n}+2x\sum\limits_{n=0}^{\infty} nx^n\\ P(x)-2&= xP(x)+2x.\frac{x}{(1-x)^2}\\ (1-x)P(x)&=2+ 2x.\frac{x}{(1-x)^2}\\ P(x)&=\frac{2}{1-x}+\frac{2x^2}{(1-x)^3}\\ P(x)&=\frac{4x^2-4x+2}{(1-x)^3}\\ &=(4x^2-4x+2)\sum\limits_{k=0}^{\infty}\binom{k+2}{2}x^k\end{align*}$$

Sehingga koefisien $x^n$ dari $P(x)$ adalah $2\binom{n+2}{2}-4\binom{n+1}{2}+4\binom{n}{2}$

4. Dalam sebuah ruangan terdapat n mahasiswa menempati n kursi. Sewaktu jam istirahat semua mahasiswa diminta ke luar ruangan. Setelah waktu istirahat habis, semua mahasiswa diminta masuk ruangan dan menempati n kursi yang ada. Berapakah peluang kejadian terdapat tepat 5 mahasiswa kembali menempati kursinya semula?

Jawab : Misalkan $S$ himpunan semua $n$ mahasiswa menempati $n$ kursi, maka $|S|=n!$. Kemudian misalkan $A$ adalah himpunan kejadian terdapat tepat $5$ mahasiswa menempati tempatnya semula. $n(A)$ sama halnya menghitung banyaknya kejadian terdapat $n-5$ mahasiswa menempati $n-5$ kursi sehingga semuanya tidak menempati kursinya semula. Dengan prinsip inklusi eksklusi maka diperoleh

$$\begin{align*}&n(A)\\&=\binom{n}{n-5}\left(\binom{n-5}{0}(n-5)!-\binom{n-5}{1}(n-6)!+\cdots+(-1)^{n-5} \binom{n-5}{n-5}(0)!\right)\\ &=\frac{n!}{(n-5)!5!}\left(\frac{(n-5)!}{0!}-\frac{(n-5)!}{1!}+\cdots+(-1)^{n-5} \frac{(n-5)!}{(n-5)!}\right)\\ &=\frac{n!}{5!}\left(\frac{1}{0!}-\frac{1}{1!}+\cdots+(-1)^{n-5} \frac{1}{(n-5)!}\right)\end{align*}$$

Sehingga peluang kejadian terdapat tepat 5 mahasiswa kembali menempati kursinya semula adalah

$$\begin{align*}\frac{n(A)}{n(S)} &=\frac{1}{5!}\left(\frac{1}{0!}-\frac{1}{1!}+\cdots+(-1)^{n-5} \frac{1}{(n-5)!}\right)\\ &=\frac{1}{5!}\sum\limits_{k=0}^{n-5}\frac{(-1)^k}{k!}\end{align*}$$