Lewati ke konten utama

Subbab 2.4 Bukti Kombinatorial

Argumen kombinatorial termasuk argumen yang paling indah dalam matematika. Sering kali, pernyataan yang dapat dibuktikan dengan metode lain yang lebih rumit (biasanya melibatkan banyak manipulasi aljabar yang membosankan) ternyata memiliki bukti sangat singkat setelah kita menemukan kaitannya dengan pencacahan. Dalam bagian ini, kita memperkenalkan cara baru untuk memikirkan masalah kombinatorial melalui beberapa contoh. Tujuannya adalah membantu Anda mengembangkan “intuisi” terhadap masalah kombinatorial.

Contoh 2.13.

Misalkan \(n\) merupakan bilangan bulat positif. Gunakan Gambar 2.14 untuk menjelaskan mengapa
\begin{equation*} 1+2+3+\dots+n=\frac{n(n+1)}{2}. \end{equation*}
dijelaskan secara terperinci setelah gambar
Susunan persegi yang pada contoh terdiri atas tujuh baris dan tujuh kolom titik, mewakili susunan dengan n tambah satu baris dan n tambah satu kolom. Sebuah pita diagonal dari kiri atas ke kanan bawah menandai titik-titik pada diagonal utama. Titik-titik di atas dan di bawah diagonal membentuk dua daerah segitiga kongruen; masing-masing memuat baris yang banyak titiknya berturut-turut satu, dua, dan seterusnya hingga \(n\text{.}\)
Gambar 2.14. Jumlah \(n\) bilangan bulat positif pertama
Penyelesaian.
Perhatikan susunan titik berukuran \((n+1)\times (n+1)\) seperti yang ditampilkan dalam Gambar 2.14. Seluruhnya terdapat \((n+1)^2\) titik, dengan tepat \(n+1\) titik pada diagonal utama. Titik-titik di luar diagonal secara alami terbagi menjadi dua bagian yang sama besar, yaitu bagian di atas dan bagian di bawah diagonal.
Selain itu, masing-masing dari kedua bagian tersebut memuat \(S(n)=1+2+3+\dots+n\) titik. Dengan demikian,
\begin{equation*} S(n)=\frac{(n+1)^2-(n+1)}{2} \end{equation*}
dan hasil ini tampak langsung dari gambar. Sedikit manipulasi aljabar pada ruas kanan persamaan tersebut menghasilkan rumus yang diberikan sebelumnya.

Contoh 2.15.

Misalkan \(n\) merupakan bilangan bulat positif. Jelaskan mengapa
\begin{equation*} 1+3+5+\dots+2n-1=n^2. \end{equation*}
dijelaskan secara terperinci setelah gambar
Susunan titik persegi yang dibagi menjadi lapisan-lapisan berbentuk L. Lapisan pertama memuat satu titik; setiap lapisan berikutnya menambahkan bilangan ganjil berikutnya. Gabungan \(n\) lapisan membentuk persegi dengan n baris dan n kolom; banyak titik pada lapisan-lapisannya adalah satu, tiga, lima, dan seterusnya hingga dua n dikurangi satu.
Gambar 2.16. Jumlah \(n\) bilangan bulat ganjil positif pertama
Penyelesaian.
Ruas kiri tidak lain adalah jumlah \(n\) bilangan bulat ganjil positif pertama. Seperti yang ditunjukkan dalam Gambar 2.16, jumlah ini jelas sama dengan \(n^2\text{.}\)

Contoh 2.17.

Misalkan \(n\) merupakan bilangan bulat positif. Jelaskan mengapa
\begin{equation*} \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\dots+\binom{n}{n}=2^n. \end{equation*}
Penyelesaian.
Kedua ruas menghitung banyaknya string bit dengan panjang \(n\text{;}\) ruas kiri lebih dahulu mengelompokkannya menurut banyaknya angka \(0\text{.}\)

Contoh 2.18.

Misalkan \(n\) dan \(k\) merupakan bilangan bulat dengan \(0\le k\lt n\text{.}\) Jelaskan mengapa
\begin{equation*} \binom{n}{k+1} = \binom{k}{k} + \binom{k+1}{k} + \binom{k+2}{k} +\dots+ \binom{n-1}{k}. \end{equation*}
Penyelesaian.
Untuk membuktikan rumus ini, cukup perhatikan bahwa kedua ruas menghitung banyaknya string bit dengan panjang \(n\) yang memuat \(k+1\) angka \(1\text{;}\) ruas kanan lebih dahulu mempartisinya menurut posisi kemunculan terakhir angka \(1\text{.}\) (Sebagai contoh, jika angka \(1\) terakhir muncul pada posisi \(k+5\text{,}\) maka \(k\) angka \(1\) lainnya harus muncul dalam \(k+4\) posisi sebelumnya, sehingga terdapat \(C(k+4,k)\) string jenis ini.) Perhatikan bahwa ketika \(k=1\) (sehingga \(k+1=2\)), kita memperoleh rumus yang sama seperti rumus terdahulu untuk jumlah semua bilangan bulat positif yang lebih kecil daripada \(n\text{.}\)

Contoh 2.19.

Jelaskan identitas
\begin{equation*} 3^n=\binom{n}{0}2^0+\binom{n}{1}2^1+\binom{n}{2}2^2+ \dots+\binom{n}{n}2^n. \end{equation*}
Penyelesaian.
Kedua ruas menghitung banyaknya string atas \(\{0,1,2\}\) dengan panjang \(n\text{;}\) ruas kanan lebih dahulu mempartisinya menurut posisi-posisi dalam string yang tidak berisi angka \(2\text{.}\) (Sebagai contoh, jika \(6\) posisi tidak berisi angka \(2\text{,}\) mula-mula kita harus memilih \(6\) posisi tersebut dengan \(C(n,6)\) cara, lalu terdapat \(2^6\) cara untuk mengisinya dengan memilih angka \(0\) atau \(1\) pada setiap posisi.)

Contoh 2.20.

Jelaskan mengapa, untuk setiap bilangan bulat tak negatif \(n\text{,}\)
\begin{equation*} \binom{2n}{n}= {\binom{n}{0}}^2+{\binom{n}{1}}^2+{\binom{n}{2}}^2+\dots+ {\binom{n}{n}}^2. \end{equation*}
Penyelesaian.
Kedua ruas menghitung banyaknya string bit dengan panjang \(2n\) yang separuh bitnya berupa angka \(0\text{;}\) ruas kanan lebih dahulu mempartisinya menurut banyaknya angka \(1\) yang muncul dalam \(n\) posisi pertama string. Perhatikan bahwa kita juga menggunakan identitas sederhana \(\binom{n}{k}=\binom{n}{n-k}\text{.}\)
SblmKe AtasLnjt