[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
- Jika semua elemen berbeda
Banyak cara memilihnya yaitu $n\times (n-1)\times(n-2).$ - Jika semua elemen adalah sama
Banyak cara memilihnya yaitu $ n\times(1)\times(1) = n.$ - Jika dua dari 3 element adalah sama
Banyak cara memilihnya yaitu $\binom{3}{1} \times n\times(n-1)\times 1= 3n(n-1).$
Maka, total cara memilihnya yaitu
\begin{align*}
n(n-1)(n-2)+3n(n-1)+n &= 6\frac{n!}{6(n-3)!} + 6 \frac{n!}{2(n-2)!}+\binom{n}{1}\\
&= 6 \binom{n}{3} + 6 \binom{n}{2} + \binom{n}{1} .
\end{align*}
Credit: Fadhlan Zhaahiran