[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]
[latexpage]
Soal: Berikan bukti kombinatorika untuk membuktikkan persamaan
$$ n^{3} = 6 \binom{n}{3} + 6 \binom{n}{2} + \binom{n}{1} .$$
Pembahasan:
Ruas kiri:
Diberikan himpunan $S$ yang terdiri dari $3$ elemen, yang dipilih dari himpunan $\{1,2,\ldots,n\}$ maka banyaknya cara memilih tiap elemen nya adalah \[n\times n\times n = n^3 .\]
Ruas kanan:
Jika $3$ elemen dari $S$ yang dipilih dari himpunan $\{1,2,\ldots,n\},$ di mana
[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]
[latexpage]
Soal: Diberikan bilangan bulat positif $n$, buktikkan bahwa
\[ \binom{2n}{2} = 2 \binom{n}{2} + n^2\]
a). dengan manipulasi aljabar,
b). dengan argumentasi kombinatorial.
Pembahasan:
a. Diperoleh,
\begin{align*}
\binom{2n}{2} &= \frac{(2n)!}{2! (2n-2)!} \\
&= 2n^2 – n \\
&= n(n-1) + n^2 \\
&= 2 \frac{n(n-1)(n-2)!}{2!(n-2)!} + n^2 \\
&= 2\binom{n}{2} + n^2
\end{align*}
b. Misalkan pada suatu kelas terdiri atas $2n$ mahasiswa di mana terdapat $n$ anak laki-laki dan $n$ anak perempuan. Ingin memilih ketua kelas dan wakil ketua kelas secara acak. Maka banyak cara memilih ketua kelas dan wakil ketua kelas yaitu \[\displaystyle\binom{2n}{n} .\]
Diperhatikan bahwa, terdapat cara lain untuk memilih nya, yaitu:
[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]
[latexpage]
Soal: Diberikan $n \in \mathbb{N,}$ buktikkan bahwa
$$\sum_{k=1}^{n} k(n+1-k) = \binom{n+2}{3} .$$
Pembahasan:
Dengan manipulasi aljabar, diperoleh
\begin{align*}
\sum_{k=1}^{n} k(n+1-k) &=(n+1) \sum_{k=1}^{n} k – \sum_{k=1}^{n} k^2 \\
&= (n+1) \frac{n(n+1)}{2} – \frac{n(n+1)(2n+1)}{6} \\
&= \frac{n(n+1)(n+2)}{6} \\
&= \binom{n+2}{3}
\end{align*}
Persamaan tersebut juga dapat dibuktikan dengan argumentasi kombinatorial.
Misalkan terdapat $n+2$ orang yang akan ditempatkan pada sebuah bangku yang sejajar. Banyak cara untuk memilih kombinasi $3$ orang dari $n+2$ kapasitas bangku yaitu sebanyak $\displaystyle\binom{n+2}{3}$.
Diperhatikan bahwa, terdapat cara lain untuk memilihnya. Akan dibagi menjadi beberapa kasus berdasarkan elemen tengah dari tiga buah subset. Misalkan $\{a,b,c\}$ yang telah diurutkan sedemikian sehingga $b$ selalu di antara $a$ dan $c$. Karena $b$ selalu di antara $a$ dan $c$ artinya $b$ hanya boleh ditempatkan pada urutan ke-$2$ sampai urutan ke-$n+1$.
[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]
[latexpage]
Soal: Tentukan koefisien $x^{12}$ pada ekspansi $\displaystyle\left( x + y + \frac{1}{y}\right)^{20}$.
Pembahasan:
Misalkan $n$ merupakan bilangan asli, Maka untuk semua $x_{1},x_{2},\ldots,x_{k}$ berlaku
\[(x_{1}+x_{2} + \ldots + x_{m})^{n} = \sum \frac{n!}{k_{1}! k_{2}! \cdots k_{m}!} x_{1}^{k_{1}} x_{2}^{k_{2}} \cdots x_{m}^{k_{m}}.\]
Menurut teorema multinomial di atas, diperoleh koefisien $x^{12}$ pada ekspansi $\left(x + y + \frac{1}{y}\right)^{12}$ adalah \[ \displaystyle\binom{20}{12,8,4} =\binom{20}{12} \binom{12}{8} \binom{4}{4} = 125970 \times 70 \times 1 = 8817900 .\]
[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]
[latexpage]
Soal: Tentukan koefisien $x^2y^5$ dan $x^3y^4$ pada ekspansi $(2x+y)^7$.
Pembahasan:
Diperhatikan pada teorema binomial berikut, untuk setiap bilangan bulat $n \geq 0,$ berlaku
\[(x+y)^{n} = \sum_{r=0}^n \binom{n}{r} x^{n-r} y^{r} .\]
Menurut teorema binomial tersebut, $(2x+y)^{7}$ dapat dinyatakan dengan:
\[(2x+y)^7 = \sum_{r=0}^n \binom{7}{r} 2^{7-r} x^{7-r} y^{r}.\]
Maka, didapat koefisien $x^2 y^5$ pada ekspansi $(2x+7)^7$ yaitu $\displaystyle\binom{7}{5} 2^{2} =84$ serta koefisien $x^3 y^4$ pada ekspansi $(2x+7)^7$ yaitu $\displaystyle\binom{7}{4} 2^{3} =280.$
[embedyt] https://www.youtube.com/watch?v=ecN0SttjYww[/embedyt]
[latexpage]
Soal: Tunjukkan bahwa jumlah $r$ permutasi melingkar dari $n$ objek, dengan $1\leq r\leq n$, yaitu \[
\frac{n!}{(n-r)!r}.\]
Pembahasan:
Pertama-tama, jika memilih $r$ benda dari $n$ objek, yaitu $\displaystyle\binom{n}{r}=\frac{n!}{r!(n-r)!}$. Selanjutnya, apabila $r$ benda tersebut diletakan melingkar maka banyak caranya yaitu $(r-1)!$. Maka menurut permutasi perkalian diperoleh banyaknya cara yaitu
\[\binom{n}{r}(r-1)!= \frac{n!}{r!(n-r)!}(r-1)! = \frac{n!}{(n-r)!r} .\]
Maka terbukti bahwa, jumlah $r$ permutasi melingkar dari $n$ objek, dengan $1\leq r\leq n$, yaitu \[\frac{n!}{(n-r)!r} .\]
[embedyt] https://www.youtube.com/watch?v=j5es_42Nur8[/embedyt]
[latexpage]
Soal: Tentukan banyaknya solusi bulat non negatif dari
$$x + y + z = 12$$
dengan kendala $ 0\leq x \leq 4,$ $ 0\leq y \leq 5,$ $0\leq z \leq 6.$
Pembahasan:
Untuk $x,y,z \geq 0, $ menurut Stars and Bars theorem, diperoleh banyaknya solusi, yaitu
$$ |S| =\binom{3+12-1}{12} = \binom{14}{12} = 91 .$$
Didefinisikan
\begin{align*}
\begin{cases}
A = \{x\in\mathbb{Z}|x+y+z=12,x\geq 5\} \\
B = \{ y\in\mathbb{Z}|x+y+z=12, y\geq 6\} \\
C = \{z\in\mathbb{Z}|x+y+z=12,z\geq 7\} \\
\end{cases}
\end{align*}
Untuk memperoleh himpunan $0\leq x \leq 4,$ $ 0\leq y \leq 5,$ $0\leq z \leq 6,$ yaitu irisan dari negasi ketiga himpunan tersebut. Dinotasikan
$$ |A^{c}\cap B^{c} \cap C^{c}| .$$
Dengan Prinsip Inklusi-Eksklusi, akan ditentukan banyak solusinya dari $|A^{c}\cap B^{c} \cap C^{c}|.$
Diperoleh,
$$|A^{c} \cap B^{c} \cap C^{c}| = |S| – |A| – |B| – |C| + |A \cap B| + |A \cap C| + |B \cap C | – | A \cap B \cap C|.$$
Selanjutnya, akan dicari:
[embedyt] https://www.youtube.com/watch?v=e53lnDM0hVQ[/embedyt]
[latexpage]
Soal: Tentukan banyaknya permutasi-13 dari multiset $S : \{4\cdot x, 5\cdot y,6\cdot z\}$
Pembahasan:
Karena $|S| = 15,$ akan ditentukan banyaknya permutasi-13, yaitu
[embedyt] https://www.youtube.com/watch?v=XyvjVteOKKc[/embedyt]
[latexpage]
Soal: Dalam sebuah kelas terdapat $4$ guru, $9$ murid laki-laki, dan $7$ murid perempuan. Tentukan banyaknya cara memilih kelompok yang berisi $5$ orang dari kelas tersebut.
Pembahasan:
Jumlah orang di dalam kelas tersebut adalah 9+4+7 = 20 orang. Maka, banyaknya cara memilih 5 orang dari kelas tersebut adalah
\begin{align*}
\binom{20}{5} = \frac{20!}{5!15!} = \boxed{\textbf{15504}} \text{ cara}.
\end{align*}
Credit: Fadhlan Zhaahiran
[embedyt] https://www.youtube.com/watch?v=P6MPg8N1zF8[/embedyt]
[latexpage]
Soal: Formulasikan dan buktikan dengan induksi rumus umum dari bentuk berikut
\begin{align*}
1^3 &= 1 \\
2^3 &= 3 + 5 \\
3^3 &= 7 + 9 + 11 \\
4^3 &= 13 + 15 + 17 + 19
\end{align*}
Pembahasan:
Diperhatikan bahwa pada soal akan memiliki bentuk umum
\[p(n) : n^3 = \sum_{i=1} ^n (n^2 -n-1 + 2i) .\]
Akan dibuktikan dengan induksi matematika bahwa $p(n)$ di atas benar untuk setiap $n.$
Terbukti bentuk pada soal memiliki formula umum $n^3 = \sum_{i=1} ^n (n^2 -n-1 + 2i).$
Komentar