Pencacahan Ganda Archives — Page 2 of 2

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).

Sebagai contoh, akan dibuktikan bahwa $\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}$ untuk setiap bilangan asli $n$ dengan menggunakan pembuktian kombinatorial.

Pandang eksperimen acak berupa pengetosan sekeping koin sebanyak $n$ kali. Dalam hal ini, kita akan menghitung banyaknya keluaran yang mungkin dari eksperimen acak tersebut dengan menggunakan dua cara yang berbeda. Cara pertama akan menghasilkan $2^{n},$ sedangkan cara kedua akan menghasilkan $\sum_{k = 0}^{n} (\binom{n}{k}) .$ Kemudian, kita akan menyimpulkan bahwa dua ekspresi ini pasti memiliki nilai yang sama karena keduanya menghitung keluaran dari eksperimen acak yang sama.

Karena masing-masing pengetosan menghasilkan $2$ keluaran (angka atau gambar), akan ada $2^{n}$ keluaran berbeda dari pengetosan koin sebanyak $n$ kali yang didapat dengan menggunakan aturan perkalian.

Di sisi lain, dari $n$ kali pengetosan koin, setiap keluaran akan memunculkan $k$ angka dan $n - k$ gambar dengan $0 \leq k \leq n .$ Dengan kata lain, akan ada $(\binom{n}{k})$ keluaran yang memuat tepat $k$ angka. Hal ini terjadi karena pada masing-masing keluaran tersebut, kita seperti memilih $k$ dari $n$ pengetosan yang menghasilkan sisi angka. Oleh karena itu, banyak keluaran secara keseluruhan adalah $\sum_{k = 0}^{n} (\binom{n}{k}) .$

Dari sini, disimpulkan bahwa $\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n} .$

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

Artikel ini ditulis berdasarkan beberapa sumber, termasuk sumber berbahasa Inggris. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.

$\begin{array}{ccc} No. & Bahasa Indonesia & Bahasa Inggris \\ 1. & Pembuktian Kombinatorial & Combinatorial Proof \\ 2. & Argumen Kombinatorial & Combinatorial Argument \\ 3. & Identitas Kombinatorial & Combinatorial Identity \\ 4. & Pembuktian Aljabar & Algebraic Proof \\ 5. & Pembuktian dengan Pencacahan Ganda & Proof by Double Counting \\ 6. & Pencacahan Ganda & Double Counting \\ 7. & Himpunan Takkosong & Nonempty Set \\ 8. & Teorema Binomial & Binomial Theorem \\ 9. & Identitas Pascal & Pascal’s Identity \\ 10. & Identitas Vandermonde & Vandermonde’s Identity \\ 11. & Partisi & Partition \\ 12. & Identitas Tongkat Hoki & Hockey Stick Identity \end{array}$

Quote by Wilson Kanadi

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

Soal Nomor 1

Dengan menggunakan pembuktian kombinatorial, buktikan bahwa $(\binom{n}{k}) = (\binom{n}{n - k}) .$

Pembahasan

Misalkan terdapat $n$ bola yang akan ditempatkan pada dua kotak berbeda. Kotak pertama harus memuat $k$ bola, sedangkan kotak kedua harus memuat $n - k$ bola. Banyaknya cara memilih $k$ dari $n$ bola untuk ditempatkan ke dalam kotak pertama adalah $(\binom{n}{k}) .$ Hal ini sama saja dengan memilih $n - k$ dari $n$ bola untuk ditempatkan ke dalam kotak kedua, yaitu $(\binom{n}{n - k}) .$ Jadi, terbukti bahwa $(\binom{n}{k}) = (\binom{n}{n - k}) .$

[collapse]

Soal Nomor 2

Buktikan teorema binomial berikut.
$\begin{aligned} (x + y)^{n} & = \sum_{j = 0}^{n} (\binom{n}{j}) x^{n - j} y^{j} \\ = (\binom{n}{0}) x^{n} + (\binom{n}{1}) x^{n - 1} y + \dots + (\binom{n}{n - 1}) x y^{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, \dots, 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 $(\binom{n}{n - j})$ yang senilai dengan $(\binom{n}{j}) .$ Dengan demikian, teorema binomial tersebut terbukti benar.

[collapse]

Soal Nomor 3

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

Pembahasan

Misalkan kita mempunyai himpunan $A$ dengan $n + 1$ elemen. Banyaknya subhimpunan dengan $k$ elemen dari $A$ adalah $(\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 $(\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 $(\binom{n}{k - 1}) .$

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

[collapse]

Soal Nomor 4

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

Pembahasan

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

[collapse]

Soal Nomor 5

Buktikan identitas Vandermonde berikut.
$(\binom{m + n}{k}) = \sum_{i = 0}^{k} (\binom{m}{i}) (\binom{n}{k - i})$ dengan syarat $m, n, k \geq 0,$ $k \leq m$ , dan $k \leq n .$

Pembahasan

Misalkan kita memilih $k$ orang dari $m + n$ orang. Banyak cara untuk memilih mereka adalah $(\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 $(\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 $(\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 $(\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 $(\binom{m}{k}) (\binom{n}{0}) .$
Dengan menggunakan aturan penjumlahan, banyak cara secara keseluruhan adalah
$(\binom{m}{0}) (\binom{n}{k}) + (\binom{m}{1}) (\binom{n}{k - 1}) + (\binom{m}{2}) (\binom{n}{k - 2}) + \dots + (\binom{m}{k}) (\binom{n}{0})$ yang bisa kita tulis secara singkat dengan menggunakan notasi sigma berikut.
$\sum_{i = 0}^{k} (\binom{m}{i}) (\binom{n}{k - i})$ Jadi, terbukti kebenaran identitas Vandermonde tersebut bahwa $(\binom{m + n}{k}) = \sum_{i = 0}^{k} (\binom{m}{i}) (\binom{n}{k - i})$ dengan syarat $m, n, k \geq 0,$ $k \leq m$ , dan $k \leq n .$

[collapse]

Soal Nomor 6

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

Pembahasan

Misalkan terdapat $2 n$ 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 $(\binom{2 n}{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} (\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}) + 2 n (\binom{n}{4}) + (n^{2} - n) (\binom{n}{3}) . \end{aligned}$ Jadi, terbukti bahwa
$(\binom{2 n}{5}) = 2 (\binom{n}{5}) + 2 n (\binom{n}{4}) + (n^{2} - n) (\binom{n}{3}) .$

[collapse]

Soal Nomor 7

Dengan menggunakan pembuktian kombinatorial, buktikan bahwa
$(\binom{2 n}{2}) = 2 (\binom{n}{2}) + n^{2} .$

Pembahasan

Misalkan terdapat $2 n$ bola yang terdiri dari $n$ bola merah dan $n$ bola biru. Banyaknya cara memilih $2$ dari $2 n$ bola yang ada adalah $(\binom{2 n}{2}) .$ Dengan menggunakan pendekatan yang berbeda, kita dapat menentukan banyaknya cara memilih $n$ bola dengan membagi kasus seperti berikut.

Pertama, $2$ bola yang dipilih semuanya berwarna merah. Jadi, ada $(\binom{n}{2})$ cara yang dapat dilakukan.
Kedua, $2$ bola yang dipilih semuanya berwarna biru. Jadi, ada $(\binom{n}{2})$ cara juga yang dapat dilakukan.
Terakhir, $2$ bola yang dipilih masing-masing berwarna biru dan merah. Ada $(\binom{n}{1}) = n$ cara memilih bola merah dan $(\binom{n}{1}) = n$ cara memilih bola biru. Dengan demikian, akan ada $n \cdot n = n^{2}$ cara yang dapat dilakukan untuk kasus ini.

Jadi, secara keseluruhan, ada $(\binom{n}{2}) + (\binom{n}{2}) + n^{2} = 2 (\binom{n}{2}) + n^{2} .$ Karena merepresentasikan pencacahan objek yang sama, disimpulkan bahwa $(\binom{2 n}{2}) = 2 (\binom{n}{2}) + n^{2} .$

[collapse]

Soal Nomor 8

Dengan menggunakan pembuktian kombinatorial, buktikan bahwa
$(\binom{2 n}{n}) = {(\binom{n}{0})}^{2} + {(\binom{n}{1})}^{2} + \dots {(\binom{n}{n})}^{2} .$

Pembahasan

Misalkan terdapat $2 n$ bola yang terdiri dari $n$ bola merah dan $n$ bola biru. Memilih $n$ dari $2 n$ bola yang ada dapat dilakukan dengan $(\binom{2 n}{n})$ cara. Pendekatan lain dapat digunakan untuk memilih $n$ bola tersebut. Setiap pemilihan $n$ bola akan menghasilkan sebanyak $x$ bola merah dan $n - x$ bola biru dengan $0 \leq x \leq n .$ Kita dapat memilih $x$ bola merah dengan $(\binom{n}{x})$ cara dan $n - x$ bola biru dengan $(\binom{n}{n - x}) = (\binom{n}{x})$ cara juga. Jadi, memilih $x$ bola merah dan $n - x$ bola biru secara keseluruhan dapat dilakukan dengan $(\binom{n}{x}) \cdot (\binom{n}{x}) = {(\binom{n}{x})}^{2}$ cara. Karena $0 \leq x \leq n,$ total banyaknya cara dengan menggunakan pendekatan ini adalah $\sum_{x = 0}^{n} (\binom{n}{x}) = {(\binom{n}{x})}^{2} = {(\binom{n}{0})}^{2} + {(\binom{n}{1})}^{2} + \dots {(\binom{n}{n})}^{2} .$ Jadi, terbukti bahwa $(\binom{2 n}{n}) = {(\binom{n}{0})}^{2} + {(\binom{n}{1})}^{2} + \dots {(\binom{n}{n})}^{2} .$

[collapse]

Soal Nomor 9

Dengan menggunakan pembuktian kombinatorial, buktikan bahwa
$\sum_{i = 0}^{n} (\binom{n}{i}) (\binom{2 n}{n - i}) = (\binom{3 n}{n}) .$

Pembahasan

Misalkan terdapat $3 n$ bola yang terdiri dari $2 n$ bola berwarna merah dan $n$ bola sisanya berwarna biru. Pilih $n$ dari $3 n$ bola yang ada sehingga akan ada $(\binom{3 n}{n})$ cara melakukannya. Dalam memilih $n$ bola tersebut, kita dapat memilih $i \leq n$ bola merah, kemudian memilih $n - i \leq 2 n$ bola biru dengan $0 \leq i \leq n .$ Sebagai ilustrasi, jika $i = 3,$ artinya kita memilih $3$ bola merah dan $n - 3$ bola biru. Dengan demikian, banyak cara memilih $n$ bola dengan menggunakan pendekatan seperti ini adalah $\sum_{i = 0}^{n} (\binom{n}{i}) (\binom{2 n}{n - i}) .$ Karena merepresentasikan pencacahan objek yang sama, disimpulkan bahwa $\sum_{i = 0}^{n} (\binom{n}{i}) (\binom{2 n}{n - i}) = (\binom{3 n}{n}) .$

[collapse]

Soal Nomor 10

Dengan menggunakan pembuktian kombinatorial, buktikan bahwa
$(\binom{2 n + 2}{n + 1}) = (\binom{2 n}{n + 1}) + 2 (\binom{2 n}{n}) + (\binom{2 n}{n - 1}) .$

Pembahasan

Misalkan terdapat $2 n + 2$ bola yang terdiri dari $2 n$ bola berwarna merah dan $2$ bola berwarna biru. Pilih $n + 1$ dari $2 n + 2$ bola yang ada sehingga akan ada $(\binom{2 n + 2}{n + 1})$ cara melakukannya. Dalam memilih $n + 1$ bola tersebut, kita dapat melakukannya dengan meninjau tiga kasus yang dibedakan berdasarkan banyaknya bola biru yang dipilih.

Pertama, bola yang dipilih semuanya berwarna merah. Banyaknya cara memilih $n + 1$ bola merah dari $2 n$ bola merah yang ada adalah $(\binom{2 n}{n + 1}) .$
Kedua, ada tepat satu bola biru yang dipilih dan bola lainnya berwarna merah. Ini berarti kita hanya perlu menentukan banyaknya cara memilih $n$ dari $2 n$ bola merah yang ada, yaitu $(\binom{2 n}{n}),$ sedangkan banyaknya cara memilih $1$ dari $2$ bola biru yang ada adalah $(\binom{2}{1}) = 2.$ Jadi, akan ada $2 (\binom{2 n}{n})$ cara melakukannya secara keseluruhan.
Terakhir, ada tepat dua bola biru yang dipilih dan bola lainnya berwarna merah. Ini berarti kita hanya perlu menentukan banyaknya cara memilih $n - 1$ dari $2 n$ bola merah yang ada, yaitu $(\binom{2 n}{n - 1}),$ sedangkan banyaknya cara memilih $2$ dari $2$ bola biru yang ada adalah $(\binom{2}{2}) = 1.$ Jadi, akan ada $(\binom{2 n}{n - 1})$ cara melakukannya secara keseluruhan.

Dengan demikian, dapat disimpulkan bahwa
$(\binom{2 n + 2}{n + 1}) = (\binom{2 n}{n + 1}) + 2 (\binom{2 n}{n}) + (\binom{2 n}{n - 1}) .$

[collapse]

Soal Nomor 11

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

Pembahasan

Pertama, ubah bentuk persamaan kombinatorialnya dengan menggunakan sifat kesimetrisan koefisien binomial.
$(\binom{m + n}{n}) = (\binom{m}{0}) (\binom{n}{n}) + (\binom{m}{1}) (\binom{n}{n - 1}) + \dots + (\binom{m}{n}) (\binom{n}{0})$ Misalkan terdapat subhimpunan $S$ dengan $n$ elemen dari himpunan $H$ beranggotakan $m + n$ elemen. Banyak subhimpunan yang dapat dibentuk adalah $(\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
$(\binom{m}{0}) (\binom{n}{n}) + (\binom{m}{1}) (\binom{n}{n - 1}) + \dots + (\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}) + \dots + (\binom{m}{n}) (\binom{n}{n}) .$ Jadi, terbukti bahwa $(\binom{m + n}{n}) = (\binom{m}{0}) (\binom{n}{0}) + (\binom{m}{1}) (\binom{n}{1}) + \dots + (\binom{m}{n}) (\binom{n}{n}) .$

[collapse]

Soal Nomor 12

Misalkan $n, m,$ dan $k$ merupakan bilangan asli yang memenuhi $n > m > k .$ Dengan menggunakan pembuktian kombinatorial, buktikan bahwa
$(\binom{n}{m}) (\binom{m}{k}) = (\binom{n}{k}) (\binom{n - k}{m - k}) .$

Pembahasan

Misalkan $N$ merupakan himpunan dengan $n$ elemen. Pandang pasangan terurut $(M, K)$ dengan $M \subseteq S$ dan $K \subseteq M$ yang memenuhi $| M | = m$ dan $| K | = k .$ Banyaknya pasangan terurut yang dapat dibentuk sama dengan banyaknya cara memilih $m$ dari $n$ elemen dari $N$ untuk membentuk $M$ dikali dengan banyaknya cara memilih $k$ dari $m$ elemen dari $M$ untuk membentuk $K .$ Dengan kata lain, ada $(\binom{n}{m}) (\binom{m}{k})$ pasangan terurut berbeda yang mungkin.
Dengan cara yang berbeda, pilih $k$ dari $n$ elemen di $N$ untuk membentuk $K$ terlebih dahulu. Ada sebanyak $(\binom{n}{k})$ cara melakukannya. Berikutnya, akan dibentuk himpunan $M$ yang memenuhi $K \subseteq M .$ Untuk memperoleh $M,$ kita harus menambahkan $m - k$ elemen berbeda pada $K$ yang dipilih dari $n - k$ elemen tersisa di $N .$ Oleh karena itu, banyak cara melakukannya adalah $(\binom{n - k}{m - k}) .$ Secara keseluruhan, banyaknya pasangan terurut $(M, K)$ dalam hal ini adalah $(\binom{n}{k}) (\binom{n - k}{m - k}) .$
Karena dua cara di atas merepresentasikan pencacahan objek yang sama, dapat disimpulkan bahwa $(\binom{n}{m}) (\binom{m}{k}) = (\binom{n}{k}) (\binom{n - k}{m - k}) .$

[collapse]

Soal Nomor 13

Buktikan identitas tongkat hoki berikut.
$(\binom{n + 1}{r + 1}) = \sum_{k = r}^{n} (\binom{k}{r}) .$

Pembahasan

Misalkan terdapat $m$ bola yang akan didistribusikan pada $q$ kotak berbeda dengan ketentuan bahwa kotak boleh kosong. Dengan menggunakan teorema bintang dan garis, akan ada $(\binom{m + q - 1}{q - 1})$ cara melakukannya.
Pendekatan yang berbeda dapat dilakukan dengan meninjau banyaknya bola yang terdapat pada kotak terakhir. Distribusikan $j$ bola pada $q - 1$ kotak pertama, kemudian $m - j$ bola pada kotak terakhir. Hal demikian dapat terjadi dalam $(\binom{j + q - 2}{q - 2})$ cara dengan menggunakan teorema bintang dan garis. Karena $0 \leq j \leq m,$ banyaknya cara secara keseluruhan untuk nilai-nilai $j$ tersebut adalah $\sum_{j = 0}^{m} (\binom{j + q - 2}{q - 2}) .$ Karena merepresentasikan pencacahan objek yang sama, disimpulkan bahwa
$\sum_{j = 0}^{m} (\binom{j + q - 2}{q - 2}) = (\binom{m + q - 1}{q - 1})$ yang dapat dijabarkan menjadi
$(\binom{q - 2}{q - 2}) + (\binom{q - 1}{q - 2}) + \dots + (\binom{m + q - 2}{q - 2}) = (\binom{m + q - 1}{q - 1}) .$ Substitusikan $r = q - 2$ dan $n = m + q - 2$ sehingga didapat
$(\binom{r}{r}) + (\binom{r + 1}{r}) + \dots + (\binom{n}{r}) = (\binom{n + 1}{r + 1})$ atau dapat dituliskan dalam notasi sigma menjadi
$\sum_{k = r}^{n} (\binom{k}{r}) = (\binom{n + 1}{r + 1}) .$

[collapse]

Soal Nomor 14

Misalkan $n$ dan $k$ merupakan bilangan asli dengan $n \geq k$ dan $f (n, k)$ menyatakan banyaknya cara untuk menuliskan $n$ sebagai penjumlahan $k$ suku bilangan asli dengan memperhatikan urutan. Sebagai contoh, $f (5, 3) = 6,$ yaitu
$\begin{array}{cc} 1 + 1 + 3 = 5 & 1 + 3 + 1 = 5 \\ 3 + 1 + 1 = 5 & 2 + 2 + 1 = 5 \\ 2 + 1 + 2 = 5 & 1 + 2 + 2 = 5 \end{array}$ Dengan menggunakan pembuktian kombinatorial, buktikan bahwa $f (n, k) = (\binom{n - 1}{k - 1}) .$

Pembahasan

Misalkan terdapat $n$ garis yang disusun berbaris menyamping. Selipkan $k - 1$ bintang di antara garis-garis tersebut dengan syarat bahwa tidak boleh ada dua atau lebih bintang di antara dua garis serta tidak ada bintang yang ditempatkan di ujung. Dengan demikian, akan ada $n - 1$ tempat untuk menyelipkan bintang tersebut.

Agar lebih jelas, ilustrasi dengan mengambil kasus khusus dengan $n = 7$ garis dan $k - 1 = 2$ bintang diberikan sebagai berikut.
Tampak bahwa $2$ bintang yang kita miliki dapat diposisikan pada $6$ tempat. Jika dikaitkan dengan soal awal, posisi garis dan bintang tersebut merepresentasikan penjumlahan $2 + 2 + 3 = 7$ dengan banyak garis merepresentasikan besarnya bilangan dan bintang merepresentasikan operator penjumlahan.

Banyaknya cara untuk menuliskan $n$ sebagai penjumlahan $k$ suku bilangan asli, $f (n, k),$ sama dengan banyaknya cara menyusun $k - 1$ bintang tersebut pada $n - 1$ tempat yang tersedia. Dengan menggunakan aturan kombinasi, diperoleh
$f (n, k) = (\binom{n - 1}{k - 1}) .$

[collapse]

Soal Nomor 15

Bilangan Stirling jenis kedua (Stirling number of the second kind) menyatakan banyaknya cara mempartisi $[n] = {1, 2, \dots, n}$ menjadi $k$ kelas yang dinotasikan oleh ${\begin{array}{cc} n \\ k \end{array}} .$ Dengan menggunakan pembuktian kombinatorial, buktikan bahwa proposisi berikut benar.
a. ${\begin{matrix} n \\ n - 1 \end{matrix}} = (\binom{n}{2})$
b. ${\begin{matrix} n \\ n - 2 \end{matrix}} = (\binom{n}{3}) + \frac{1}{2} (\binom{n}{2}) (\binom{n - 2}{2})$
c. ${\begin{matrix} n \\ 2 \end{matrix}} = 2^{n - 1} - 1.$

Pembahasan

Jawaban a)
Misalkan terdapat $n$ bola dan $n - 1$ kotak. Agar tidak ada kotak yang kosong, isilah $n - 2$ kotak dengan $1$ bola dan $1$ kotak sisanya dengan $2$ bola. Dengan demikian, banyaknya cara untuk mempartisi himpunan ${1, 2, 3, \dots, n}$ menjadi $n - 1$ subhimpunan takkosong sama dengan banyaknya cara memilih $2$ dari $n$ bola tersebut untuk ditempatkan secara bersama dalam $1$ kotak. Dengan menggunakan aturan kombinasi, diperoleh
${\begin{matrix} n \\ n - 1 \end{matrix}} = (\binom{n}{2}) .$
Jawaban b)
Misalkan terdapat $n$ bola dan $n - 2$ kotak. Untuk menempatkan bola-bola tersebut dalam $n - 2$ kotak, kita dapat melakukan cara sesuai dengan dua kasus berikut.
Kasus 1:
Misalkan terdapat $3$ bola dalam $1$ kotak dan $1$ bola dalam kotak-kotak lainnya. Banyaknya cara memilih $3$ dari $n$ bola tersebut untuk ditempatkan secara bersama dalam $1$ kotak dapat ditentukan dengan menggunakan aturan kombinasi, yaitu $(\binom{n}{3}) .$
Kasus 2:
Misalkan terdapat $2$ bola dalam $2$ kotak dan $1$ bola dalam kotak-kotak lainnya.
Pertama, pilih $2$ dari $n$ bola yang ada untuk ditempatkan secara bersama dalam $1$ kotak. Akan ada $(\binom{n}{2})$ cara melakukannya. Berikutnya, pilih $2$ dari $n - 2$ bola tersisa untuk ditempatkan secara bersama dalam $1$ kotak lain. Akan ada $(\binom{n - 2}{2})$ cara melakukannya. Karena urutan kotak tidak diperhatikan (kotak-kotak tersebut identik), hasil perkalian dari $(\binom{n}{2}) (\binom{n - 2}{2})$ perlu dibagi dua untuk menghindari pencacahan ganda (double counting). Oleh karena itu, dalam kasus ini, akan ada $\frac{1}{2} (\binom{n}{2}) (\binom{n - 2}{2})$ cara.

Berdasarkan dua kasus di atas, banyak cara menempatkan $n$ bola ke dalam $n - 2$ kotak adalah $(\binom{n}{3}) + \frac{1}{2} (\binom{n}{2}) (\binom{n - 2}{2}),$ yang sama dengan banyaknya cara untuk mempartisi himpunan ${1, 2, 3, \dots, n}$ menjadi $n - 2$ subhimpunan takkosong.
Jawaban c)
Misalkan $A \subset [n]$ dengan $A \neq \emptyset .$ Dengan demikian, diperoleh partisi dari $[n]$ menjadi $2$ kelas, yaitu ${A, [n] - A} .$ Ini juga menunjukkan bahwa untuk setiap $A \subset [n]$ dengan $A \neq \emptyset,$ diperoleh partisi dari $[n]$ menjadi $2$ kelas dengan cara sebanyak ${\begin{matrix} n \\ 2 \end{matrix}} .$ I
Di sisi lain, partisi dari $[n],$ yaitu ${A, [n] - A}$ berkorespondensi dengan $2$ subhimpunan sejati takkosong dari $[n],$ yaitu $A$ dan $[n] - A .$ Banyaknya cara membentuk subhimpunan dari $[n]$ adalah $2^{n} .$ Karena subhimpunan tersebut tidak boleh kosong dan tidak boleh $[n]$ itu sendiri, banyak subhimpunan yang demikian menjadi $2^{n} - 2.$ Namun, susunan kelas $A$ dan $[n] - A$ tidak memandang urutan. Jadi, untuk menghindari pencacahan ganda, banyak partisi dengan $2$ kelas tersebut adalah $\frac{2^{n - 2}}{2} = 2^{n - 1} - 1.$ Dari sini, dapat disimpulkan bahwa
${\begin{matrix} n \\ 2 \end{matrix}} = \frac{2^{n} - 2}{2} = 2^{n - 1} - 1.$

[collapse]

Soal Nomor 16

Bilangan Bell (Bell number) $b (n)$ merupakan jumlah dari bilangan-bilangan Stirling jenis kedua. Dengan kata lain, bilangan Bell menyatakan banyaknya cara mempartisi $[n] .$ Dengan menggunakan pembuktian kombinatorial, buktikan bahwa $b (n + 1) = \sum_{k = 0}^{n} (\binom{n}{k}) b (k)$ dengan $n \geq 0$ dan $b (0) = 1.$

Pembahasan

Misalkan terdapat himpunan $[n + 1] = {1, 2, \dots, n, n + 1} .$ Banyaknya cara mempartisi $[n + 1]$ dapat dilakukan dengan memandang letak elemen $n + 1$ seperti yang ditinjau dalam kasus-kasus berikut.
Kasus 1:
Elemen $n + 1$ diletakkan sendirian dalam satu kelas. Jadi, pilih $0$ dari $n$ elemen lainnya untuk ditempatkan di kelas tersebut, yaitu sebanyak $(\binom{n}{0}) .$ Kemudian, buat partisi dari $n$ elemen tersisa, yaitu sebanyak $b (n) .$ Dengan demikian, banyak cara dalam kasus ini adalah $(\binom{n}{0}) b (n) .$
Kasus 2:
Elemen $n + 1$ diletakkan bersama $1$ elemen lainnya. Jadi, pilih $1$ dari $n$ elemen lainnya untuk ditempatkan di kelas tersebut, yaitu sebanyak $(\binom{n}{1}) .$ Kemudian, buat partisi dari $n - 1$ elemen tersisa, yaitu sebanyak $b (n - 1) .$ Dengan demikian, banyak cara dalam kasus ini adalah $(\binom{n}{1}) b (n - 1) .$
Kasus 3:
Elemen $n + 1$ diletakkan bersama $2$ elemen lainnya. Jadi, pilih $2$ dari $n$ elemen lainnya untuk ditempatkan di kelas tersebut, yaitu sebanyak $(\binom{n}{2}) .$ Kemudian, buat partisi dari $n - 2$ elemen tersisa, yaitu sebanyak $b (n - 2) .$ Dengan demikian, banyak cara dalam kasus ini adalah $(\binom{n}{2}) b (n - 2) .$

Dengan cara yang serupa, lanjutkan kasus ini sampai kasus $n$ :
Elemen $n + 1$ diletakkan bersama $n$ elemen lainnya. Jadi, pilih $n$ dari $n$ elemen lainnya untuk ditempatkan di kelas tersebut, yaitu sebanyak $(\binom{n}{n}) .$ Kemudian, buat partisi dari $0$ elemen tersisa, yaitu sebanyak $b (0) = b (n - n) .$ Dengan demikian, banyak cara dalam kasus ini adalah $(\binom{n}{n}) b (n - n) .$

Dengan menjumlahkan banyak cara dari setiap kasus di atas, diperoleh
$\begin{aligned} b (n + 1) & = (\binom{n}{0}) b (n) + (\binom{n}{1}) b (n - 1) + (\binom{n}{2}) b (n - 2) + \dots + (\binom{n}{n}) b (n - n) \\ = (\binom{n}{0}) b (n) + (\binom{n}{n - 1}) b (n - 1) + (\binom{n}{n - 2}) b (n - 2) + \dots + (\binom{n}{0}) b (n - n) \\ = \sum_{k = 0}^{n} (\binom{n}{k}) b (k) . \end{aligned}$ Jadi, terbukti bahwa $b (n + 1) = \sum_{k = 0}^{n} (\binom{n}{k}) b (k)$ dengan $n \geq 0$ dan $b (0) = 1.$

[collapse]

Soal Nomor 17

Peracakan (derangement) dari $[n] = {1, 2, \dots, n}$ adalah permutasi dari elemen $[n]$ sehingga setiap elemen selalu berpindah posisi (tidak memiliki titik tetap). Sebagai contoh, $231$ dan $312$ adalah peracakan dari $[3]$ dan tidak ada peracakan lain yang mungkin dari himpunan tersebut. Misalkan $D (n)$ menyatakan banyaknya peracakan dari $[n] .$ Dengan menggunakan pembuktian kombinatorial, buktikan bahwa
$n! = \sum_{k = 0}^{n} (\binom{n}{k}) D (n - k)$ dengan $n \geq 0.$

Pembahasan

Misalkan terdapat himpunan $[n] = {1, 2, \dots, n} .$ Banyaknya permutasi dari elemen $[n]$ adalah $n! .$ Di sisi lain, permutasi-permutasi tersebut dapat dikelompokkan berdasarkan banyaknya elemen yang tetap pada posisinya.

Kelompok $1$ memuat permutasi yang tidak memiliki titik tetap sehingga banyak permutasi yang demikian adalah $D (n) .$
Kelompok $2$ memuat permutasi yang memiliki $1$ titik tetap. Pilih $1$ dari $n$ elemen yang ada untuk dijadikan titik tetap. Dengan demikian, banyak permutasi yang demikian adalah $(\binom{n}{1}) D (n - 1) .$
Kelompok $3$ memuat permutasi yang memiliki $2$ titik tetap. Pilih $2$ dari $n$ elemen yang ada untuk dijadikan titik tetap. Dengan demikian, banyak permutasi yang demikian adalah $(\binom{n}{2}) D (n - 2) .$
Dengan cara yang serupa, lanjutkan sampai kelompok terakhir.
Kelompok $n$ memuat permutasi yang memiliki $n$ titik tetap. Pilih $n$ dari $n$ elemen yang ada untuk dijadikan titik tetap. Dengan demikian, banyak permutasi yang demikian adalah $(\binom{n}{n}) D (n - n) .$

Karena mepresentasikan pencacahan objek yang sama, disimpulkan bahwa
$\begin{aligned} n! & = D (n) + (\binom{n}{1}) D (n - 1) + (\binom{n}{2}) D (n - 2) + \dots + (\binom{n}{n}) D (n - n) \\ = \sum_{k = 0}^{n} (\binom{n}{k}) D_{n - k} . \end{aligned}$

[collapse]

Tag: Pencacahan Ganda

Materi, Soal, dan Pembahasan – Pembuktian Kombinatorial

Quote by Wilson Kanadi

Soal Nomor 1

Soal Nomor 2

Soal Nomor 3

Soal Nomor 4

Soal Nomor 5

Soal Nomor 6

Soal Nomor 7

Soal Nomor 8

Soal Nomor 9

Soal Nomor 10

Soal Nomor 11

Soal Nomor 12

Soal Nomor 13

Soal Nomor 14

Soal Nomor 15

Soal Nomor 16

Soal Nomor 17