Identitas Pascal

Kita mulai diskusi kita dengan beberapa identitas sehubungan dengan koefisien binomial $\displaystyle {n \choose k}$ atau banyaknya cara menentukan $k$-kombinasi atas himpunan dengan $n$ objek.

Baca juga: Kombinasi tanpa perulangan.

Identitas Absorbsi

Untuk semua $n,~k~\in N$ dengan $0 \le k \le n$ berlaku $${n \choose k}=\frac{n}{k} {{n-1}\choose {k-1}}$$

Bukti identitas absorbsi. Kita gunakan argumentasi kombinatorial. Kita perhatikan proses pemilihan ketua dan tim yang beranggota $k$ orang dari $n$ orang. Pertama kita dapat milih $k$ orang dari $n$ orang dalam $\displaystyle {n \choose k}$ cara. Kemudian kita pilih ketua dari $k$ orang terpilih dalam $k$ cara. Sehingga oleh prinsip perkalian pemilihan ketua dan tim dapat dilakukan dalam $\displaystyle k.{n \choose k}$ cara.
Pada sisi lain proses pemilihan dapat kita lakukan dengan memilih seorang ketua terlebih dahulu. Hal ini dapat dilakukan dalam $n$ cara. Kemudian kita pilih $k − 1$ orang anggota tim dari $n − 1$ orang yang tersisa. Hal ini dapat dilakukan dalam $\displaystyle {{n-1} \choose {k-1}}$ cara. Oleh prinsip perkalian pemilihan ketua dan tim yang terdiri dari $k$ orang dapat dilakukan dalam $\displaystyle n.{{n-1} \choose {k-1}}$ cara.
Sekarang kita dapat menyimpulkan bahwa $\displaystyle k.{n \choose k}=n.{{n-1} \choose {k-1}}$. Jadi $\displaystyle {n \choose k}=\frac{n}{k} {{n-1}\choose {k-1}}$.

Identitas Pascal

Untuk semua bilangan bulat positif $k,~n \in N$ dengan $1 \le k \le n$ berlaku $${n \choose k}= {{n-1}\choose {k-1}}+{{n-1} \choose k}$$

Bukti identitas pascal. Pada bagian ini kita berikan bukti kombinatorial dari identitas Pascal. Andaikan $S$ adalah sebuah himpunan atas $n$ unsur. Perhatikan bahwa ekspresi $\displaystyle {n \choose k}$ menyatakan banyaknya himpunan bagian dari $S$ yang terdiri atas $k$ unsur.
Andaikan $x$ adalah sebuah unsur di $S$ dan misalkan $T = S-${$x$}. Perhatikan bahwa himpunan bagian $S$ yang terdiri atas $k$ unsur dapat dipisah menjadi dua bagian, yakni
- Himpunan tersebut memuat unsur $x$ bersama dengan $k − 1$ buah unsur yang berada di $T$. Banyaknya himpunan bagian yang demikian adalah sebanyak himpunan bagian dari $T$ yang terdiri dari $k − 1$ unsur, yakni $\displaystyle {{n-1} \choose {k-1}}$.
- Himpunan tersebut tidak memuat unsur $x$. Hal ini berarti bahwa himpunan tersebut merupakan himpunan bagian dari $T$ yang terdiri dari $k$ unsur. Banyak himpunan bagian yang demikian adalah $\displaystyle {{n-1} \choose k}$.
Oleh prinsip penjumlahan kita peroleh $${n \choose k}= {{n-1}\choose {k-1}}+{{n-1} \choose k}$$
Demikianlah materi tentang identitas pascal. Sampai jumpa dan semoga bermanfaat.