Teorema Identitas Vandermonde

martha yunanda kombinatorika

Teorema Vandermonde ini merupakan tiga serangkai dari teorema Identitas Pascal dan Teorema Ekspansi Binomial. Bunyi dari teorema Identitas Vandermonde ini sebagai berikut,

Misalkan m, n, dan r adalah bilangan bulat non-negatif dengan r tidak melebihi salah satu dari m atau n. Maka berlaku,

Pembuktian teorema Vandermonde,
Misalkan ada m anggota himpunan pertama dan n anggota pada himpunan kedua, maka banyaknya cara memilih r elemen dari gabungan dua himpunan ini adalah  $\begin{pmatrix}m+n \\  r \end{pmatrix}$.

Cara lainnya untuk memilih r elemen dari gabungan himpunan adalah mengambil k elemen dari himpunan kedua kemudian r−k elemen dari himpunan kedua, dimana k adalah bilangan bulat dengan 0≤k≤r.  Karena ada $\begin{pmatrix} n \\  k \end{pmatrix}$ cara untuk memilih k elemen dari himpunan kedua DAN
ada$\begin{pmatrix} m \\ r- k \end{pmatrix}$ cara untuk memilih r−k elemen dari himpunan pertama, maka berdasarkan aturan perkalian, banyaknya cara memilih r elemen dengan prosedur ini bisa dilakukan dengan,
$\begin{pmatrix} n \\  k \end{pmatrix} \begin{pmatrix} m \\  r- k \end{pmatrix}$
Jadi jumlah total banyaknya cara memilih r elemen dari gabungan dua himpunan tersebut adalah
 $\sum_{k=0}^{r}  \begin{pmatrix} n \\  k \end{pmatrix} \begin{pmatrix} m \\  r- k \end{pmatrix}$


Sudah ditemukan dua ekspresi dalam perhitungan banyak cara mengambil r elemen dari gabungan himpinan m anggota dan n anggota. Penyamaan ekspresi-ekspresi tersebut yang akan memberikan identitas vandermonde. Ini akan melahirkan akibat,
Jika n adalah bilangan bulat nonnegatif, maka
 $\begin{pmatrix} 2n \\  n \end{pmatrix} =\sum_{k=0}^{n}  \begin{pmatrix} n \\ n \end{pmatrix} ^2$

Pembuktian akibat di atas sebagai berikut,
Dengan menggunakan identitas Vandermonde dengan n=m=r akan didapat
 $\begin{pmatrix} 2n \\  n \end{pmatrix} =\sum_{k=0}^{n}  \begin{pmatrix} n \\ n -k \end{pmatrix} \begin{pmatrix} n \\   k \end{pmatrix}$
Karena sesuai identitas binomial
$\begin{pmatrix} n \\ n -k \end{pmatrix} =  \begin{pmatrix} n \\   k \end{pmatrix}$
Maka,
$\begin{pmatrix} 2n \\  n \end{pmatrix} =\sum_{k=0}^{n}  \begin{pmatrix} n \\ n -k \end{pmatrix} \begin{pmatrix} n \\   k \end{pmatrix} = \sum_{k=0}^{n}  \begin{pmatrix} n \\ n \end{pmatrix} ^2$

Share on Facebook

Share on Twitter

Share on LinkedIn