Identitas Kombinatorial ^^

Dalam kombinatorik, terdapat satu identitas yang terkenal. Identitas itu dinamakan sebagai Identitas Kombinatorial.

Identitas Kombinatorial:

= + untuk

Bisakah kaliah membuktikannya?
(Note, temukan juga hubungan antara kombinasi dengan notasi sigma di post ini. ^^)

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Bukti identitas Kombinatorial Secara Aljabar

Identitas di atas bisa dibuktikan secara aljabar secara induktif (dimulai dari hasil akhir). Kita akan mulai dari kesimpulan. Lalu, dijabarkan secara aljabar untuk memperoleh hasil yang lebih sederhana.

= +

=+

= +

= +

Terbukti.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Bukti identitas Kombinatorial dengan Argumen Kombinatorial

(Note, bagian ini adalah inti dari post ini.)

Misalkan ada sebuah himpunan X sebanyak n unsur.

X = {}

Jika di himpunan ini ditambahkan 1 unsur lagi, yaitu {}, maka berapa banyak kombinasi yang dapat dibentuk atas k unsur?

Pertanyaan di atas dapat dijawab dengan 2 cara:

CARA I:

Dengan bertambahnya elemen {}, maka sekarang unsurnya bertambah 1 menjadi n+1. Banyak kombinasi yang terbentuk adalah .

CARA II:

Pisah menjadi 2 kejadian yang saling lepas: (i). kombinasi yang mengandung {} (ii). kombinasi yang tidak mengandung {} Pada kejadian (i), kita menyimpan unsur {}, lalu tinggal menentukan banyaknya kombinasi dari {} atas (k-1) unsur. (dikurangi satu karena kita sudah menyimpan unsur {}). Jadi, banyaknya kombinasi kejadian ini adalah Pada kejadian (ii), kita membuang unsur {}. Lalu kita tinggal menentukan kombinasi dari {} atas k unsur. Jadi, banyaknya kombinasi kejadian ini adalah .

Dari kedua cara di atas, hasilnya sama, maka dapat disimpulkan bahwa:

= + Terbukti

Argumen untuk membuktikan teorema ini disebut dengan argumen kombinatorial.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Ilustrasi untuk Bagian di Atas

Jika masih kesulitan memahami pembuktian secara kombinatorial di atas, di sini akan diberikan contoh ilustrasinya.

Misalkan X= {a,b,c,d}. Berapa banyak kombinasi dari himpunan X U {e} yang terdiri atas 3 unsur? (Maksud dari lambang U adalah gabungan himpunan). (Note: Soal di atas identik dengan soal ini: "Misalkan X= {a,b,c,d,e}. Berapa banyak kombinasi dari himpunan X yang terdiri atas 3 unsur?")

Cara I: = 10.
Cara II: + = 6+4 = 10.

= = 6	ab ac ad bc bd cd	+	e	=	= = 10 abc abd abe acd ace ade bcd bce bde cde
= = 4	abc abd acd bcd

Semoga ilustrasi di atas mampu memperjelas. ^^

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Contoh Soal I

Hitunglah

Jawab:

Ingat identitas sebelumnya bahwa

= +

Tambahkan k dengan 1

= +

Pindahkan , maka hasilnya:

=

Kembali ke soal
Kita dapat menyederhanakan soal di atas sebagai

dimana n=2009 dan k=3

Jabarkan

=

Ubah setiap suku menjadi (kecuali suku pertama)

=

=

Lalu, substitusikan n = 2009 dan k=3, maka hasilnya didapat.

=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Ilustrasi dari Contoh Soal I

Jika masih dengan model soal di atas, ini adalah bagian untuk memperjelasnya.
Model soal di atas sesungguhnya identik dengan model soal ini:
Berapa banyaknya segitiga yang dapat dibentuk dari 7 titik yang tidak segaris?

Apa maksud dari soal di atas?
Sebagai contoh, jika ada 3 titik yang tidak segaris, maka akan terbentik 1 segitiga.

Jika ada 4 titik (A, B, C, dan D) tidak segaris, akan terbentuk 4 segitiga.

Jawaban dari soal itu dapat dengan mudah dijawab dengan cara kombinasi, yaitu = 35. Namun, di sini kita akan memakai pendekatan yang berbeda untuk memperoleh jawaban yang sama. Misalkan, ada 7 titik yaitu A, B, C, D, E, F, dan G. Sekarang, kita akan melihat semua kombinasi yang terbentuk atas titik A. Setelah itu, kita akan menghitung jumlah kombinasi yang terbentuk atas titik B (namun tidak terbentuk atas titik A agar tidak terjadi duplikasi). dan seterusnya. Proses ini dapat digambarkan dalam tabel berikut.

= 15	ABC ACD ADE AEF AFG ABD ACE ADF AEG ABE ACF ACG ABF ACG ABG	=	= 35
	Kombinasi di atas adalah kombinasi yang mengandung A.
= 10	BCD BDE BEF BFG BCE BDF BEG BCF BCG BCG
	Kombinasi di atas adalah kombinasi yang mengandung B, tapi tidak mengandung A (agar tidak terjadi duplikasi)
= 6	CDE CEF CFG CDF CEG CDG
	Kombinasi yang mengandung C tapi tidak mengandung A dan B.
= 3	DEF DFG DEG
	Kombinasi yang mengandung D tapi tidak mengandung A, B, dan C.
= 1	EFG
	Kombinasi yang mengandung E tapi tidak mengandung A, B, C, dan D.

Dari ilustrasi di atas, perhatikan bahwa = + + + + .
Semoga ilustrasi di atas membantu.. ^^

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Hubungan Kombinasi dengan Notasi Sigma

Melalui ilustrasi di atas, perhatikan satu lagi hubungan antara kombinasi dengan notasi sigma..
Setiap kombinasi membentuk urutan tangga:
= 1
= 1+2
= 1+2+3
= 1+2+3+4
= 1+2+3+4+5
Dapat kita tarik kesimpulan bahwa:

Dimodifikasi sedikit agar batas atas sigma menjadi n, maka hubungan yang lebih cantik diperoleh:

Bagaimana dengan .? Dari contoh di atas, terlihat bahwa = + + + + .
Maka untuk , dapat ditulis notasi sigmanya sebagai berikut.

Untuk , , dan seterusnya, polanya juga dapat dicari. Namun, tidak dibahas lebih lanjut di sini.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Mungkin, sampai di sini dulu materi mengenai identitas kombinatorial. Jangan diambil pusing! Rumus tidak perlu dihapal, tapi ambil intisarinya saja di bagian "Bukti Identitas Kombinatorial Dengan Argumen Kombinatorial". ^^

Materi ini sesungguhnya tidak sulit. Jika ada kesulitan, silakan tanya, aku akan berusaha menjawab. Ada yang mw tanya, gakk?? ^^

Sumber: elearning.unej.ac.id. Selebihnya, merupakan hasil pikiran sendiri.