Kombinatorial | TI Politala Matdis 1C

Kombinatorial Dan Peluang Diskrit

1.  Teori Kombinatorial

Teori Kombinatorial merupakan salah satu pokok bahasan Matematika Diskrit yang telah banyak dikembangkan dan diaplikasikan dalam berbagai bidang. Kombinatorial juga merupakan cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. Dalam perkembangan Matematika, dapat dilihat bahwa kajian kombinatorial sangat menarik bagi sebagian orang. Salah satu contoh permasalahan yang dapat diselesaikan dengan kombinatorial adalah menghitung banyaknya kombinasi karakter password.

Contoh

Sebuah password panjangnya 6 sampai 8 karakter. Karakter boleh berupa huruf atau angka. Berapa banyak kemungkinan password yang dapat dibuat?

Penyelesaian:

- Abcdef

- aaaade

- a123f

- erhtgahn

- Yutresik

- …  

dan seterusnya…

Sangatlah mungkin bahwa kita sudah lelah sebelum proses enumerasi selesai dilakukan. Di sinilah peran kombinatorial, yang merupakan “seni berhitung”, menyelesaikan persoalan semacam ini dengan cepat.

2.  Prinsip Dasar Menghitung

A. Prinsip Penjumlahan (rule of sum)

Jika suatu himpunan A terbagi kedalam himpunan bagian A1, A2, …, An, maka jumlah unsur pada himpunan A akan sama dengan jumlah semua unsur yang ada pada setiap himpunan bagian A1, A2, …,An. Setiap himpunan bagian A1, A2, …, An tidak saling tumpang tindih (saling lepas).

Untuk himpunan yang saling tumpang tindih tidak berlaku lagi prinsip penjumlahan, dan ini harus diselesaikan dengan prinsip inklusi-eksklusi.

Misalkan,

Percobaan 1 : p hasil                    
Percobaan 2 : q hasil

maka, Percobaan 1 atau percobaan 2: p + q hasil

Contoh

Jika Ketua kelas hanya 1 orang (pria atau wanita). Jumlah pria di kelas adalah 25 orang dan jumlah wanita adalah 15 orang.Berapa banyak cara memilih ketua kelas?

Penyelesaian:

25 + 15 = 40 cara.

B. Prinsip Perkalian (rule of product)

Misalkan sebuah prosedur dapat dipecah dalam dua penugasan. Penugasan pertama dapat dilakukan dalam n1 cara, dan tugas kedua dapat dilakukan dalam n2 cara setelah tugas pertama dilakukan.

Dengan demikian, dalam mengerjakan prosedur tersebut ada (n1 x n2) cara. Secara tidak langsung, pada prinsip perkalian, bisa terjadi saling tumpang tindih (tidak saling lepas).

Misalkan,

Percobaan 1: p hasil       
Percobaan 2: q hasil

maka, Percobaan 1 dan percobaan 2: p x q hasil

Contoh

Jumlah mahasiswa laki-laki kelas 2. F adalah 31 orang sedangkan jumlah wanitanya hanya 4 orang. Untuk memilih wakil 1 orang pria dan 1 orang wanita. Berapa banyak cara memilih 2 orang wakil tersebut?

Penyelesaian:

31 x  4 = 124 cara.

3.  Prinsip Inklusi Dan Eksklusi

Misalkan A dan B sembarang himpunan, Penjumlahan |A|+|B| menghitung banyaknya elemen A yang tidak terdapat di B dan banyakan elemen B tidak terdapat di A dan banyaknya elemen yg terdapat di A ∩ B.

Oleh Karna itu, pengurangan banyaknya elemen yg terdapat A ∩ B dari |A|+|B| membuat banyaknya elemen A є B dihitung tepat satu kali, Dengan demikian

                |A u B|= |A|+|B|-|A ∩ B|

Generalisasi dari hal tersebut bagi gabungan dari sejumlah himpunan dinamakan prinsip inklusi dan eksklusi.

Contoh

Dalam sebuah kelas terdapat 29 mahasiswa yang menyukai matematika diskrit, 17 mahasiswa menyukai aljabar linear dan 11 orang diantaranya menyukai keduanya, Berapa mahasiswa terdapat dalam kelas tersebut ?

Penyelesaian ;

Misal:  A = mahasiswa yg menyukai matematika diskrit

             B = mahasiswa yg menyukai aljabar linear

Menurut data yg ada ;

|A|=29 ; |B|=17 ; |A ∩ B|= 11

|A u B|= |A|+|B|-|A ∩ B|

                  = 29 + 17 – 11 = 35

4.  Permutasi

Permutasi merupakan susunan yang mungkin dibuat dengan memperhatikan urutan. Dengan kata lain, permutasi merupakan bentuk khusus aplikasi prinsip perkalian.

Menurut kaidah perkalian, permutasi dari n objek adalah n(n – 1)(n – 2) … (2)(1) = n!
Rumus permutasi-r (jumlah susunan berbeda dari pemilihan r objek yang diambil dari n objek), dilambangkan dengan P (n,r):

A.     Permutasi Dengan Pengulangan

Banyaknya permutasi dari n objek dari n1 yang sama, n2 yang sama,……, nr yang sama

Contoh

Tentukan banyaknya kata yang dapat dibentukdari kata “DISKRIT”.

Penyelesaian:

n=7  ; n1 = 2 (huruf I yang sama, jumlahnya = 2)

Banyaknya kata yang dapat dibentuk dari kata“DISKRIT” = n!/n1! = 7!/2! = 2520 Kata.

5.  Kombinasi

Bentuk khusus dari permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan. Rumus kombinasi-r (jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen), dilambangkan dengan C(n,r) atau ( n   r ) .

A.      Interpretasi Kombinasi

           a. C(n, r) = banyaknya himpunan bagian yang terdiri atas r elemen yang dapat dibentuk dari himpunan dengan n elemen. 

            b. C(n, r) = cara memilih r buah elemen dari n elemen yang ada, tetapi urutan elemen di dalam susunan hasil pemilihan tidak penting.

Contoh

Misalkan A = {1, 2, 3}
Jumlah Himpunan bagian dengan 2 elemen:

{1, 2} = {2, 1}

{1, 3} = {3, 1}               3 buah atau

{2, 3} = {3, 2}

6.     Peluang

A.   Teori Peluang

Kombinatorial dan teori peluang (probability) berkaitan sangat erat. Teori peluang banyak menggunakan konsep-konsep dalam kombinatorial. Sebenarnya kedua bidang ini lahir dari arena judi (gambling games) – salah satu kasusnya adalah menghitung peluang munculnya nomor lotre tertentu. Meskipun demikian, aplikasi kombinatorial dan teori peluang saat ini telah meluas ke berbagai bidang ilmu lain maupun dalam kehidupan nyata seperti ilmu statistika, fisika, ekonomi, biologi, dan berbagai bidang ilmu lainnya.

B.   Ruang Contoh (sample space)

Ruang Contoh dari suatu percobaan adalah himpunan semua kemungkinan hasil percobaan yang bersangkutan.

C.  Titik Contoh (sample point)

Titik Contoh adalah setiap hasil percobaan di dalam ruang contoh. Hasil-hasil percobaan tersebut bersifat saling terpisah (mutually exclusive) karena dari seluruh ruang contoh, hanya satu titik contoh yang muncul.

D.  Ruang Contoh Diskrit (discrete sample space)

Ruang Contoh Diskrit adalah ruang contoh yang jumlah anggotanya terbatas. Misalkan ruang contoh dilambangkan dengan S dan titik-titik contohnya dilambangkan dengan x1, x2, …, maka

S = { x1, x2, …, xi, … }Menyatakan ruang contoh S yang terdiri atas titik-titik contoh x1, x2, …, xi, dan seterusnya.

E.  Peluang Diskrit

             Peluang Diskrit adalah peluang terjadinya sebuah titik contoh, dan disimbolkan dengan p(xi).
Kejadian (event)

Kejadian –disimbolkan dengan E– adalah himpunan bagian dari ruang contoh. Misalnya pada percobaan melempar dadu, kejadian munculnya angka ganjil adalah E = {1,3,5}, kejadian munculnya angka 1 adalah E = {1}.

Kejadian yang hanya mengandung satu titik contoh disebut kejadian sederhana (simple event), sedangkan kejadian yang mengandung lebih dari satu titik contoh disebut kejadian majemuk (compound event).

F.  Peluang Kejadian

          Peluang Kejadian E di dalam ruang contoh S dapat diartikan sebagai jumlah peluang semua titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa

Contoh

Sebuah koin yang mempunyai sisi A dan sisi B di lempar  keatas sebanyak 4 (empat) kali.
Berapakah jumlah kemungkinan munculnya sisi A  sebanyak 3(tiga) kali?

Penyelesaian:

Munculnya sisi A sebanyak 3 (tiga) kali adalah C (4, 3) = 4

Jumlah seluruh hasil percobaan adalah 2x2x2x2 = 16,

sehingga peluang munculnya sisi A sebanyak 3 kali adalah 4/16 = 1/4

Sumber :
https://www.academia.edu/11795682/Matdis_Kombinatorial_dan_peluang_diskrit