Materi, Soal, dan Pembahasan – Pembuktian Kombinatorial

Pembuktian kombinatorial (combinatorial proof), atau argumen kombinatorial, merupakan salah satu metode pembuktian yang dipakai untuk membuktikan kebenaran dari identitas kombinatorial. Pembuktian kombinatorial juga dikenal sebagai pembuktian dengan pencacahan ganda (proof by double counting). Identitas kombinatorial dibuktikan dengan  mencacah banyak elemen dari himpunan terpilih dalam dua cara berbeda untuk mendapatkan ekspresi berbeda yang termuat di dalam identitas tersebut. Karena ekspresi tersebut menyatakan objek yang sama, hasilnya tentu sama dan identitas kombinatorial itu akhirnya terbangun.

Ide yang dipakai dalam pembuktian kombinatorial terkadang cukup tricky, tetapi proses pembuktian kombinatorial dirasa lebih mudah dicerna karena kita bekerja pada objek yang konkret. Di sisi lain, identitas binomial juga sebenarnya sering kali berhasil dibuktikan dengan pembuktian aljabar (algebraic proof).

Berikut ini merupakan beberapa soal yang jawabannya melibatkan penggunaan pembuktian kombinatorial. Sebagai catatan, notasi kombinasi $\displaystyle \binom{n}{k}$ menyatakan banyaknya subhimpunan beranggotakan $k$ elemen dari himpunan beranggotakan $n$ elemen, yaitu $\dfrac{n!}{k! \cdot (n-k)!}.$

Quote by Wilson Kanadi

To be the best, you must be able to handle the worst.

Soal Nomor 1

Buktikan teorema binomial berikut.
$$\begin{aligned} (x + y)^n & = \displaystyle \sum_{j=0}^n \binom{n}{j} x^{n-j}y^j \\ & = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \cdots + \binom{n}{n-1}xy^{n-1} + \binom{n}{n}y^n \end{aligned}$$dengan $x$ dan $y$ adalah variabel serta $n$ merupakan suatu bilangan bulat nonnegatif.

Pembahasan

Kita akan menggunakan pembuktian kombinatorial. Jika dijabarkan, suku-suku hasil perkaliannya berbentuk $x^{n-j}y^j$ untuk $j = 0, 1, 2, \cdots, n.$ Untuk menghitung banyaknya suku berbentuk $x^{n-j}y^j$, perhatikan bahwa kita perlu memilih $(n-j)$ variabel $x$ dari penjumlahan $n$ suku tersebut sehingga kita juga secara otomatis memilih $j$ variabel $y.$ Oleh karena itu, koefisien dari $x^{n-j}y^{j}$ adalah $\displaystyle \binom{n}{n-j}$ yang senilai dengan $\displaystyle \binom{n}{j}.$ Dengan demikian, teorema binomial tersebut terbukti benar. $\blacksquare$

[collapse]

Baca Juga: Soal dan Pembahasan – Teorema Binomial dan Perluasannya 

Soal Nomor 2

Buktikan identitas Pascal berikut.
$$\displaystyle \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$$

Pembahasan

Dengan menggunakan pembuktian kombinatorial, misalkan kita mempunyai himpunan $A$ dengan $n+1$ elemen. Banyaknya subhimpunan dengan $k$ elemen dari $A$ adalah $\displaystyle \binom{n+1}{k}.$
Dengan cara yang berbeda, misalkan $x$ merupakan salah satu elemen $A.$ Kita dapat menggolongkan subhimpunan dengan $k$ elemen yang ingin kita bentuk seperti berikut.
$x$ bukan elemen subhimpunan yang dibentuk.
$x$ merupakan salah satu elemen subhimpunan yang dibentuk.


Pada kasus pertama, $x$ diabaikan sehingga himpunan kita beranggotakan $n$ elemen saja. Kita perlu memilih $k$ elemen. Dengan demikian, banyaknya subhimpunan dengan $k$ elemen adalah $\displaystyle \binom{n}{k}.$


Pada kasus kedua, $x$ merupakan salah satu elemen subhimpunan sehingga kita cukup memilih $k-1$ elemen lagi dari $n$ elemen tersisa. Jadi, banyaknya subhimpunan yang dapat dibentuk adalah $\displaystyle \binom{n}{k-1}.$


Dengan menggunakan aturan penjumlahan, kita berhasil membuktikan identitas Pascal bahwa
$$\displaystyle \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}.$$ $\blacksquare$

[collapse]

Soal Nomor 3

Tunjukkan bahwa $\displaystyle \binom{2n}{n}$ merupakan bilangan genap.

Pembahasan

Perhatikan bahwa $\displaystyle \binom{2n}{n}$ menyatakan banyaknya subhimpunan dengan $n$ elemen dari himpunan dengan $2n$ elemen.
Misalkan $X_i (i = 1, 2, 3, \cdots)$ adalah subhimpunan dengan $n$ elemen dari $A$ yang merupakan himpunan dengan $2n$ elemen. Dengan demikian, kita tahu bahwa
$$\begin{aligned} |X_i| & = n \\ |A \setminus X_i| & = 2n-n = n. \end{aligned}$$Jadi, kita dapat mendaftarkan setiap subhimpunan dengan $n$ elemen secara berpasangan seperti berikut.
$$\begin{aligned} & X_1, A \setminus X_1, \\ & X_2, A \setminus X_2, \\ & X_3, A \setminus X_3 \\ & \cdots \end{aligned}$$Dari sini, kita bisa simpulkan bahwa banyaknya subhimpunan dengan $n$ elemen dari himpunan dengan $2n$ elemen adalah sebanyak genap. Dengan kata lain, $\displaystyle \binom{2n}{n}$ merupakan bilangan genap. $\blacksquare$

[collapse]

Soal Nomor 4

Buktikan identitas Vandermonde berikut.
$$\displaystyle \binom{m+n}{k} = \sum_{i=0}^k \binom{m}{i} \binom{n}{k-i}$$dengan syarat $m, n, k \ge 0,$ $k \le m$, dan $k \le n.$

Pembahasan

Dengan menggunakan pembuktian kombinatorial, misalkan kita memilih $k$ orang dari $m+n$ orang. Banyak cara yang kita punya untuk memilih mereka adalah $\displaystyle \binom{m+n}{k}.$
Misalkan $m+n$ orang tersebut meliputi $m$ orang yang memakai baju biru dan $n$ orang yang memakai baju merah.
Kita punya beberapa kemungkinan untuk memilih mereka sesuai dengan kelompoknya.
Kemungkinan 1: Jika kita tidak memilih orang berbaju biru, berarti kita harus memilih $k$ orang berbaju merah. Banyak caranya adalah $\displaystyle \binom{m}{0} \binom{n}{k}.$
Kemungkinan 2: Jika kita memilih $1$ orang berbaju biru, berarti kita harus memilih $k-1$ orang berbaju merah. Banyak caranya adalah $\displaystyle \binom{m}{1} \binom{n}{k-1}.$
Kemungkinan 3: Jika kita memilih $2$ orang berbaju biru, berarti kita harus memilih $k-2$ orang berbaju merah. Banyak caranya adalah $\displaystyle \binom{m}{2} \binom{n}{k-2}.$
Hal ini berlaku seterusnya sampai
Kemungkinan terakhir: Jika kita memilih $k$ orang berbaju biru, berarti kita tidak memilih orang berbaju merah. Banyak caranya adalah$\displaystyle \binom{m}{k} \binom{n}{0}.$
Dengan menggunakan aturan penjumlahan, banyak cara secara keseluruhan adalah
$$\displaystyle \binom{m}{0} \binom{n}{k} + \binom{m}{1} \binom{n}{k-1} + \binom{m}{2} \binom{n}{k-2} + \cdots + \binom{m}{k} \binom{n}{0}$$yang bisa kita tulis secara singkat dengan menggunakan notasi sigma berikut.
$$\displaystyle \sum_{i=0}^k \binom{m}{i} \binom{n}{k-i}$$Jadi, terbukti kebenaran identitas Vandermonde tersebut bahwa $$\displaystyle \binom{m+n}{k} = \sum_{i=0}^k \binom{m}{i} \binom{n}{k-i}$$dengan syarat $m, n, k \ge 0,$ $k \le m$, dan $k \le n.$ $\blacksquare$

[collapse]

Soal Nomor 5

Diberikan bilangan bulat $n \geq 5.$ Tuliskan pembuktian kombinatorial ntuk memperlihatkan bahwa
$$\displaystyle \binom{2n} {5} = 2\binom{n} {5} + 2n\binom{n}{4} + (n^2-n) \binom{n} {3}.$$

Pembahasan

Dengan menggunakan pembuktian kombinatorial, misalkan terdapat $2n$ orang dalam suatu grup yang terdiri dari $n$ pria dan $n$ wanita. Kita hendak memilih $5$ orang perwakilan dari grup tersebut sehingga banyak cara memilihnya adalah $\displaystyle \binom{2n} {5}.$
Di lain sisi, perwakilan tersebut dapat terdiri dari pria (P) dan wanita (W) dengan kombinasi 5P, 5W, 4P 1W, 3P 2W, 2P 3W, dan 1P 4W. Banyak cara memilih perwakilan tersebut dengan menggunakan aturan perkalian dan penjumlahan adalah 
$$\begin{aligned} & \displaystyle \binom{n} {5} \binom{n} {0} + \binom{n}{0} \binom{n}{5} + \binom{n} {4}\binom{n} {1} + \binom{n} {3}\binom{n} {2} + \binom{n} {2} \binom{n} {3} + \binom{n} {1} \binom{n} {4} \\ & = 2 \binom{n} {5} \binom{n} {0} + 2 \binom{n} {4}\binom{n} {1} + 2 \binom{n} {3}\binom{n} {2} \\ & = 2 \binom{n} {5} + 2n \binom{n} {4} + (n^2-n) \binom{n}{3}. \end{aligned}$$Jadi, terbukti bahwa
$$\displaystyle \binom{2n} {5} = 2\binom{n} {5} + 2n\binom{n}{4} + (n^2-n) \binom{n} {3}.$$ $\blacksquare$

[collapse]

Soal Nomor 6

Misalkan $m$ dan $n$ merupakan bilangan bulat positif. Dengan menggunakan pembuktian kombinatorial, buktikan identitas berikut.
$$\displaystyle \binom{m+n}{n} = \binom{m} {0}\binom{n} {0} + \binom{m} {1}\binom{n} {1} + \cdots + \binom{m} {n} \binom{n} {n}$$

Pembahasan

Ubah bentuk persamaan kombinatorialnya dengan menggunakan sifat kesimetrisan koefisien binomial.
$$\displaystyle \binom{m+n} {n} = \binom{m} {0}\binom{n} {n} + \binom{m} {1}\binom{n} {n-1} + \cdots + \binom{m} {n} \binom{n} {0}$$Dengan menggunakan pembuktian kombinatorial, misalkan terdapat subhimpunan $S$ dengan $n$ elemen dari himpunan $H$ beranggotakan $m+n$ elemen. Banyak subhimpunan yang dapat dibentuk adalah $\displaystyle \binom{m+n} {n}.$ Di lain sisi, anggap $H = A \cup B$ dengan $A \cap B = \emptyset.$ Misalkan $|A| = m$ dan $|B| = n.$ Subhimpunan $S$ dapat dikonstruksi dengan cara: (1) mengambil $0$ elemen dari $A$ dan $n$ elemen dari $B$; (2) mengambil $1$ elemen dari $A$ dan $n-1$ elemen dari $B$; (3) mengambil $2$ elemen dari $A$ dan $n-2$ elemen dari $B$; dan seterusnya sampai mengambil $n$ elemen dari $A$ dan $0$ elemen dari $A.$ Dengan menggunakan aturan perkalian dan penjumlahan, diperoleh banyak subhimpunan $S$ berbeda, yaitu
$$\displaystyle\binom{m} {0}\binom{n} {n} + \binom{m} {1}\binom{n} {n-1} + \cdots + \binom{m} {n} \binom{n} {0}.$$Dengan menggunakan sifat kesimetrisan koefisien binomial, diperoleh
$$\binom{m} {0}\binom{n} {0} + \binom{m} {1}\binom{n} {1} + \cdots + \binom{m} {n} \binom{n} {n}.$$Jadi, terbukti bahwa $$\displaystyle \binom{m+n}{n} = \binom{m} {0}\binom{n} {0} + \binom{m} {1}\binom{n} {1} + \cdots + \binom{m} {n} \binom{n} {n}.$$ $\blacksquare$

[collapse]