Materi, Soal, dan Pembahasan – Pembuktian Kombinatorial

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 $\displaystyle \binom{n}{k}.$ Hal ini sama saja dengan memilih $n-k$ dari $n$ bola untuk ditempatkan ke dalam kotak kedua, yaitu $\displaystyle \binom{n}{n-k}.$ Jadi, terbukti bahwa $\displaystyle \binom{n}{k} = \binom{n}{n-k}.$ $\blacksquare$

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$

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.

1. $x$ bukan elemen subhimpunan yang dibentuk.
2. $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$

Perhatikan bahwa $\displaystyle \binom{2n}{n}$ menyatakan banyaknya subhimpunan dengan $n$ elemen dari himpunan dengan $2n$ elemen. Misalkan $X_i $ dengan $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$

Misalkan kita memilih $k$ orang dari $m+n$ orang. Banyak cara 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$

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$

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

1. Pertama, $2$ bola yang dipilih semuanya berwarna merah. Jadi, ada $\displaystyle \binom{n}{2}$ cara yang dapat dilakukan.
2. Kedua, $2$ bola yang dipilih semuanya berwarna biru. Jadi, ada $\displaystyle \binom{n}{2}$ cara juga yang dapat dilakukan.
3. Terakhir, $2$ bola yang dipilih masing-masing berwarna biru dan merah. Ada $\displaystyle \binom{n}{1} = n$ cara memilih bola merah dan $\displaystyle \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 $$\displaystyle \binom{n}{2} + \binom{n}{2} + n^2 = 2 \binom{n}{2} + n^2.$$Karena merepresentasikan pencacahan objek yang sama, disimpulkan bahwa $\displaystyle \binom{2n}{2} = 2\binom{n}{2} + n^2.$ $\blacksquare$

Misalkan terdapat $2n$ bola yang terdiri dari $n$ bola merah dan $n$ bola biru. Memilih $n$ dari $2n$ bola yang ada dapat dilakukan dengan $\displaystyle \binom{2n}{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 \le x \le n.$ Kita dapat memilih $x$ bola merah dengan $\displaystyle \binom{n}{x}$ cara dan $n-x$ bola biru dengan $\displaystyle \binom{n}{n-x} = \binom{n}{x}$ cara juga. Jadi, memilih $x$ bola merah dan $n-x$ bola biru secara keseluruhan dapat dilakukan dengan $\displaystyle \binom{n}{x} \cdot \binom{n}{x} = \binom{n}{x}^2$ cara. Karena $0 \le x \le n,$ total banyaknya cara dengan menggunakan pendekatan ini adalah $$\displaystyle \sum_{x = 0}^n \binom{n}{x} = \binom{n}{x}^2 = \binom{n}{0}^2 + \binom{n}{1}^2 + \cdots \binom{n}{n}^2.$$Jadi, terbukti bahwa $$\displaystyle \binom{2n}{n} = \binom{n}{0}^2 + \binom{n}{1}^2 + \cdots \binom{n}{n}^2.$$ $\blacksquare$

Misalkan terdapat $3n$ bola yang terdiri dari $2n$ bola berwarna merah dan $n$ bola sisanya berwarna biru. Pilih $n$ dari $3n$ bola yang ada sehingga akan ada $\displaystyle \binom{3n}{n}$ cara melakukannya. Dalam memilih $n$ bola tersebut, kita dapat memilih $i \le n$ bola merah, kemudian memilih $n-i \le 2n$ bola biru dengan $0 \le i \le 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 $\displaystyle \sum_{i=0}^n \binom{n}{i} \binom{2n}{n-i}.$ Karena merepresentasikan pencacahan objek yang sama, disimpulkan bahwa $$\displaystyle \sum_{i=0}^n \binom{n}{i} \binom{2n}{n-i} = \binom{3n}{n}.$$

Misalkan terdapat $2n+2$ bola yang terdiri dari $2n$ bola berwarna merah dan $2$ bola berwarna biru. Pilih $n+1$ dari $2n+2$ bola yang ada sehingga akan ada $\displaystyle \binom{2n+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.

1. Pertama, bola yang dipilih semuanya berwarna merah. Banyaknya cara memilih $n+1$ bola merah dari $2n$ bola merah yang ada adalah $\displaystyle \binom{2n}{n+1}.$
2. Kedua, ada tepat satu bola biru yang dipilih dan bola lainnya berwarna merah. Ini berarti kita hanya perlu menentukan banyaknya cara memilih $n$ dari $2n$ bola merah yang ada, yaitu $\displaystyle \binom{2n}{n},$ sedangkan banyaknya cara memilih $1$ dari $2$ bola biru yang ada adalah $\displaystyle \binom{2}{1} = 2.$ Jadi, akan ada $\displaystyle 2 \binom{2n}{n}$ cara melakukannya secara keseluruhan.
3. 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 $2n$ bola merah yang ada, yaitu $\displaystyle \binom{2n}{n-1},$ sedangkan banyaknya cara memilih $2$ dari $2$ bola biru yang ada adalah $\displaystyle \binom{2}{2} = 1.$ Jadi, akan ada $\displaystyle \binom{2n}{n-1}$ cara melakukannya secara keseluruhan.

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

Pertama, 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}$$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$

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 $\displaystyle \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 $\displaystyle \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 $\displaystyle \binom{n-k}{m-k}.$ Secara keseluruhan, banyaknya pasangan terurut $(M, K)$ dalam hal ini adalah $\displaystyle \binom{n}{k} \binom{n-k}{m-k}.$
Karena dua cara di atas merepresentasikan pencacahan objek yang sama, dapat disimpulkan bahwa $$\displaystyle \binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}.$$ $\blacksquare$

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 $\displaystyle \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 $\displaystyle \binom{j+q-2}{q-2}$ cara dengan menggunakan teorema bintang dan garis. Karena $0 \le j \le m,$ banyaknya cara secara keseluruhan untuk nilai-nilai $j$ tersebut adalah $\displaystyle \sum_{j=0}^m \binom{j+q-2}{q-2}.$ Karena merepresentasikan pencacahan objek yang sama, disimpulkan bahwa
$$\displaystyle \sum_{j=0}^m \binom{j+q-2}{q-2} = \binom{m+q-1}{q-1}$$yang dapat dijabarkan menjadi
$$\displaystyle \binom{q-2}{q-2} + \binom{q-1}{q-2} + \cdots + \binom{m+q-2}{q-2} = \binom{m+q-1}{q-1}.$$Substitusikan $r = q-2$ dan $n = m + q-2$ sehingga didapat
$$\displaystyle \binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}$$atau dapat dituliskan dalam notasi sigma menjadi
$$\displaystyle \sum_{k=r}^n \binom{k}{r} = \binom{n+1}{r+1}.$$ $\blacksquare$

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) = \displaystyle \binom{n-1}{k-1}.$$

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, \cdots, 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
$$\left\{\begin{array}{c} n \\ n-1 \end{array}\right\} = \displaystyle \binom{n}{2}.$$ $\blacksquare$
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 $\displaystyle \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 $\displaystyle \binom{n}{2}$ cara melakukannya. Berikutnya, pilih $2$ dari $n-2$ bola tersisa untuk ditempatkan secara bersama dalam $1$ kotak lain. Akan ada $\displaystyle \binom{n-2}{2}$ cara melakukannya. Karena urutan kotak tidak diperhatikan (kotak-kotak tersebut identik), hasil perkalian dari $\displaystyle \binom{n}{2} \binom{n-2}{2}$ perlu dibagi dua untuk menghindari pencacahan ganda (double counting). Oleh karena itu, dalam kasus ini, akan ada $\dfrac12 \displaystyle \binom{n}{2} \binom{n-2}{2}$ cara.

Berdasarkan dua kasus di atas, banyak cara menempatkan $n$ bola ke dalam $n-2$ kotak adalah $\displaystyle \binom{n}{3} + \dfrac12 \binom{n}{2} \binom{n-2}{2},$ yang sama dengan banyaknya cara untuk mempartisi himpunan $\{1, 2, 3, \cdots, n\}$ menjadi $n-2$ subhimpunan takkosong. $\blacksquare$
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 $\left\{\begin{array}{c} n \\ 2 \end{array}\right\}.$ 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 $\dfrac{2^{n-2}}{2} = 2^{n-1}-1.$ Dari sini, dapat disimpulkan bahwa
$$\left\{\begin{array}{c} n \\ 2 \end{array}\right\} = \dfrac{2^n-2}{2} = 2^{n-1}-1.$$ $\blacksquare$

Misalkan terdapat himpunan $[n+1] = \{1, 2, \cdots, 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 $\displaystyle \binom{n}{0}.$ Kemudian, buat partisi dari $n$ elemen tersisa, yaitu sebanyak $b(n).$ Dengan demikian, banyak cara dalam kasus ini adalah $\displaystyle \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 $\displaystyle \binom{n}{1}.$ Kemudian, buat partisi dari $n-1$ elemen tersisa, yaitu sebanyak $b(n-1).$ Dengan demikian, banyak cara dalam kasus ini adalah $\displaystyle \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 $\displaystyle \binom{n}{2}.$ Kemudian, buat partisi dari $n-2$ elemen tersisa, yaitu sebanyak $b(n-2).$ Dengan demikian, banyak cara dalam kasus ini adalah $\displaystyle \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 $\displaystyle \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 $\displaystyle \binom{n}{n} b(n-n).$

Dengan menjumlahkan banyak cara dari setiap kasus di atas, diperoleh
$$\begin{aligned} b(n+1) & = \displaystyle \binom{n}{0} b(n) + \binom{n}{1} b(n-1) + \binom{n}{2} b(n-2) + \cdots + \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) + \cdots + \binom{n}{0} b(n-n) \\ & = \sum_{k=0}^n \displaystyle \binom{n}{k}b(k). \end{aligned}$$Jadi, terbukti bahwa $$b(n + 1) =\sum_{k=0}^n \displaystyle \binom{n}{k}b(k)$$dengan $n \ge 0$ dan $b(0) = 1.$ $\blacksquare$

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

1. Kelompok $1$ memuat permutasi yang tidak memiliki titik tetap sehingga banyak permutasi yang demikian adalah $D(n).$
2. 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 $\displaystyle \binom{n}{1}D(n-1).$
3. 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 $\displaystyle \binom{n}{2}D(n-2).$
4. Dengan cara yang serupa, lanjutkan sampai kelompok terakhir.
5. 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 $\displaystyle \binom{n}{n}D(n-n).$

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