Monday, November 3, 2008

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
abacad
bcbdcd
+
e
=
= = 10
abcabd
abeacd
aceade
bcdbce
bdecde
= = 4
abcabd
acdbcd

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
ABCACDADEAEFAFG
ABDACEADFAEG
ABEACFACG

ABFACG


ABG



=
= 35
Kombinasi di atas adalah kombinasi yang mengandung A.
= 10
BCDBDEBEFBFG
BCEBDFBEG
BCFBCG

BCG


Kombinasi di atas adalah kombinasi yang mengandung B, tapi tidak mengandung A (agar tidak terjadi duplikasi)
= 6
CDECEFCFG
CDFCEG
CDG

Kombinasi yang mengandung C tapi tidak mengandung A dan B.
= 3
DEFDFG
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.

3 comments:

  1. maaf mas, mau tanya, tolong dibuktikan kenapa kombinasi 2 dari 6 = kombinasi 4 dari 6? pembuktiannya gimana? maturnuwun...

    ReplyDelete
  2. @atas:
    Buktinya sederhana:

    1. Cara aljabar:
    6C2 = 6! / (2!)(4!)
    6C4 = 6! / (4!)(2!)
    Hasilnya sama.

    2. Cara logika:
    Misalkan
    Mengkombinasikan 5 buku ABCDE menjadi 3 buku hasilnya adalah ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, CDE. Hasilnya ada 10.

    Sekarang, kombinasikan 5 buku ABCDE menjadi 2 buku, hasilnya adalah AB, AC, AD, AE, BC, BD, BE, CD, CE, DE.
    Jika kita mengambil sisa kombinasinya (Misalkan AB tidak diambil. Maka, yang diambil adalah CDE.), maka hasil kombinasinya:
    CDE, BDE, BCE, BCD, ADE, ACE, ACD, ABE, ABD, ABC. (Hasilnya sama seperti cara sebelumnya).
    Artinya 5C3 = 5C2.

    ReplyDelete
  3. maaf mz pembuktian dari c(n,o)+c(n,1)+c(n,2)+...+c(n,n)=2^n
    gmn y?

    ReplyDelete