Bukti kombinatorial pada ON Mipa PT Matematika Tingkat Nasional Tahun 2021

 Postingan ini berisi tentang pembahasan salah satu soal kombinatorika pada soal ON Mipa PT Bidang Matematika Tingkat Nasional Tahun 2021. Dimana soalnya terkait pembuktian kombinatorika. Dan pada penyelesaian soal ini saya akan membahas nya dengan menggunakan bukti kombinatorial. Sebelumnya bagi kalian yang masih baru mendengar tentang "bukti kombinatorial". Jadi, jika ada suatu persamaan dan kita ingin membuktikannya secara kombinatorial, yaitu dengan mencari suatu kejadian dimana kejadian tersebut dapat ditinjau dari dua momen yang berbeda, dimana momen pertama menghasilkan ruas kiri dan momen kedua menghasilkan ruas kanan maka terbukti bahwa ruas kiri sama dengan ruas kanan pada soal. 

Oke jika masih belum paham kita langsung ke soalnya saja. Soalnya adalah sebagai berikut.

Diberikan bilangan bulat positif $n$ dan $k$ dengan $2\leq k\leq n$. Buktikan bahwa

$\begin{align*}\sum_{k=2}^{n}\binom{k}{2}\binom{n+2}{k}\binom{n-2}{k-2}=\binom{n+2}{2}\binom{2n-2}{n-2}\end{align*}$

Jawab :

Kita akan menggunakan bukti kombinatorial. 

Diberikan himpunan $A$ dan $B$ yang saling lepas dengan $|A|=n+2$ dan $|B|=n-2$, Akan ditulis himpunan $C$ dimana $|C|=n$ yang anggotanya dipilih dari himpunan $A$ dan $B$ dengan syarat terdapat $2$ anggota $C$ yang dipilih dari $A$ yang diperlakukan khusus. Maka banyak cara untuk mendapatkan himpunan $C$ dapat kita hitung sebagai berikut.

Cara 1 : Kita memilih sebanyak $k$ anggota himpunan $A$ untuk $2\leq k\leq n$ dan $n-k$ anggota himpunan $B$ kemudian kita pilih $2$ dari $k$ anggota $A$ yang sudah dpilih untuk diperlakukan khusus. Ini dapat dihitung sebagai 

$\begin{align*}\sum_{k=2}^{n}\binom{k}{2}\binom{n+2}{k}\binom{n-2}{n-k}=\sum_{k=2}^{n}\binom{k}{2}\binom{n+2}{k}\binom{n-2}{k-2}\end{align*}$

Cara 2 : Kita pilih $2$ anggota $A$ yang akan diperlakukan khusus kemudian pilih $n-2$ dari sisa anggota $A$ dan $B$. Dalam cara ini yaitu menghasilkan 

$\begin{align*}\binom{n+2}{2}\binom{2n-2}{n-2}\end{align*}$

Karena kedua cara tersebut menghitung kejadian yang sama maka dapat disimpulkan bahwa

$\begin{align*}\sum_{k=2}^{n}\binom{k}{2}\binom{n+2}{k}\binom{n-2}{k-2}=\binom{n+2}{2}\binom{2n-2}{n-2}\end{align*}$

Dan kita selesai. Oke cukup segitu saja pembahasan kali ini, jika ada komentar silakan bisa dituliskan di kolom komentar. Terima kasih.