Kombinatorial Dan Peluang Diskrit

Diposting pada

Kombinatorial Dan Peluang Diskrit – Pusat Pengetahuan

 Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. Kombinatorial dapat digunakan untuk menjawab soal semacam ini tanpa kita perlu mengenumerai semua kemungkinan jawabannya. Hal ini dapat dilakukan karena didalam kombinatorial terdapat kaidah dasar menghitung. Dan kombinator digunakan pada teori peluang diskrit untuk menghitung peluang suatu kejadian terjadi.

A. Percobaan
Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan. Percobaan adala proses fisik yang hasilnya dapat diamati.

Contoh :
1. Melempar dadu
Enam hasil percobaan yang mungkin untuk pelemparan dadu adalah muka dadu 1,2,3,4,5 atau 6

2. Melempar koin uang Rp 100
Hasil percobaan melempar koin 100 ada dua kemungkinan maka koin bergambar rumah gadang atau muka koin yang bergambar wayang.

B. Kaidah Dasar Menghitung
Dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatrorial adalah kaidah perkalian (rule of product) dan kaidah penjumlahan (rule of sum).

– Kaidah Perkalian (rule of product)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 dan percobaan 2:   p  q hasil

– Kaidah Penjumlahan (rule of sum)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 atau percobaan 2:  p + q hasil

C. Perluasan Kaidah Menghitung
Kaidah perkalian dan penjumlahan diatas dapat diperluas sehingga mengandung lebih dari dua buah percobaan. Jika n buah percobaan masing-masing mempunyai p1, p2, …,pn, hasil percobaan yang mungkin terjadi dalam hal ini setiap p1 tidak bergantung pada pilihan sebelumnya, maka jumlah hasil percobaan yang mungkin terjadi adalah :
a. P1 x p2 x … x pn untuk kaidah perkalian.
b. P1 + p2 + … + pn untuk kaidah penjumlahan.

D. Prinsip Inklusi-Eksklusi
Informasi terkecil yang dapat disimpan di dalam memori computer adalah byte. Setiap byte disusun oleh 8 bit.

Example :
1. Setiap byte disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan ‘11’ atau berakhir dengan ‘11’?

Answer :
Misalkan
A  = himpunan byte yang dimulai dengan ‘11’,
B  = himpunan byte yang diakhiri dengan ‘11’
A Ç  B = himpunan byte yang berawal dan berakhir dengan ‘11’
maka
A È B = himpunan byte yang berawal dengan ‘11’ atau berakhir dengan ‘11’
      ½A½ = 26 = 64,      
    ½B½ = 26 = 64,     
    ½A Ç B½ = 24 = 16.
maka
     ½A È B½ = ½A½ + ½B½ – ½A Ç B½
                    = 26 + 26 – 16   = 64 + 64 – 16 = 112.
E. Permutasi
Permutasi adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Juga merupakan bentuk khusus aplikasi dari n objek, urutan kedua dipilih dari n-1 objek, urutan ketiga dipilih dari n-2 objek, begitu seterusnya, dan urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian permutasi dari n objek adalah
N(n-1) (n-2) … (2)(1) = n!
Example :
Answer :
    Cara 1: (5)(4)(3)(2)(1) = 120 buah kata
    Cara 2: P(5, 5) = 5! = 120 buah kata                                                                             

—  Berapa banyak cara mengurutkan nama 25 orang mahasiswa?
Answer : P(25, 25) = 25!
            Ada juga yang dikatakan permutasi melingkar. Yaitu penyusunan objek-objek yang megelilingi sebuah lingkaran (atau kurva tertutup sederhana). Jumlah susunan objek yang mengelilingi lingkaran adalah (n-1)!.

F.     Kombinasi
Bentuk khusus permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan urutan acb, bca, acb dianggap sama dan dihitung sekali.
Example :
1.      Misalkan ada 2 buah bola yang warnanya sama dan ada 3 buah kotak. Setiap kotak hanya boleh berisi paling banyak 1 bola.
Jumlah cara memasukkan bola ke dalam kotak :

         
2. Bila sekarang jumlah bola 3 dan jumlah kotak 10, maka jumlah cara memasukkan bola ke dalam kotak adalah
karena ada 3! cara memasukkan bola yang warnanya sama.

Kombinasi r elemen dari n elemen, atau  C(n, r),  adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen.
Example from Interpretasi Kombinasi :
1.      C(n, r) = banyaknya himpunan bagian yang terdiri dari r elemen yang dapat dibentuk dari himpunan dengan n elemen.
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}

G.    Permutasi dan Kombinasi Bentuk Umum
Misalkan: ada n buah bola yang tidak seluruhnya berbeda warna (jadi, ada beberapa bola yang warnanya sama – indistinguishable). n1 bola diantaranya berwarna 1, n2 bola diantaranya berwarna 2, nk bola diantaranya berwarna k, dan n1 + n2 + … + nk = n.
Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maks. 1 buah bola)?

Answer :
Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan nbuah   bola ke dalam n buah kotak adalah
   P(n, n) = n!.
   Dari pengaturan n buah bola itu,
–          ada n1! cara memasukkan bola berwarna 1
–          ada n2! cara memasukkan bola berwarna 2
–          ada nk! cara memasukkan bola berwarna k
Permutasi n buah bola yang mana n1 diantaranya berwarna 1, n2 bola berwarna 2, …,nk bola berwarna k adalah:

Dengan cara lain :
–          Ada C(n, n1) cara untuk menempatkan n1 buah bola yang berwarna 1.
–          Ada C(n – n1, n2) cara untuk menempatkan n2 buah bola berwarna 2.
–          Ada C(n – n1 – n2, n3) cara untuk menempatkan n3 buah bola berwarna 3.
–          Ada C(n – n1 – n2 – … –  nk-1, nk ) cara untuk menempatkan nk buah bola berwarna k.

H.    Kombinasi dengan Pengulangan.
Tinjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
                                i.            Jika masing-masing kotak hanya boleh diisi paling banyak satu buah bola, maka jumlah cara memasukkannya boal kedalam kotak adalah C(n,r).
                              ii.            Jika masing-masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan bola kedalam kotak adalah C(n+r-1,r)
Contoh :
Pada persamaan x1  +x2+x3+x4=12, xi  adalah bilangan bulat ≥0 . Berapa jumla kemungkinan solusinya?
Penyelesaian:
Analogikan 12 buah bola akan dimasukkan kedalam 4 kotak, maka:
–          Kotak 1 diisi 3 buah bola (x1=3)
–          Kotak 2 diisi 5  buah bola (x2=5)
–          Kotak  3 diisi 2 buah bola (x3=2)
–          Kotak 4 diisi 2 buah bola  (x4=2)
          sehingga,  x1 +x2+x3+x4=3+5+2+2=12

I. Koefisien Binomial
1. x+y0=1
2. x+y1=x+y
3. x+y2=x2+2xy+y2
4. x+y3=x3+3x2y+3xy2+y3
5. x+y4=x3+4x3y+6x2y2+4xy3+y4
6. x+y5=x5+5x4y+10x3y2+10x2y3+5xy4+y5

            Aturan untuk menjabarkan bentuk perpangkatan x+yn adalah
•         Suku pertama xn, sedangkan suku terakhir adalah yn
•         Pada setiap suku berikutnya, pangkat x berkurang satu sedangkan pangkat y bertambah satu. Untuk setiap suku, jumlah pangkat x dan y adalah n.
•         Koefisien untuk xn-kyk, yaitu suku ke- (k+1) adalah C(n,k). Bilangan C(n,k) disebut koefisien binomial.
Aturan di atas  dapat di simpulkan bahwa:
x+yn=Cn,oxn+Cn,1xn-1y1+…+Cn,kxn-kyk+…+Cn,nyn
                  = k=0nC(n,k)xn-kyk

J. Prinsip Sarang Merpati
Jika n+1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek.
Prinsip sarang merpati dikemukakan oleh G.Lejeune Dirichlet,seorang matematikawan Jerman, sehingga kadang-kadang dinamakan juga prinsip kotak Dirichlet, karena Dirichlet sering menggunakan prinsip ini dalam pekerjaannya.

example :
Misalkan terdapat banyak bola merah,bola putih,dan bola biru di dalam sebuah kotak.Berapa paling sedikit jumlah bola yang diambil dari kotak (tanpa melihat kedalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil?

answer:
Jika setiap warna dianggap sebagai sarang merpati, maka n=3 karena itu orang mengambil paling sedikit n+1=4 bola (merpati),maka dapat dipastikan sepasang bola yang berwarna sama ikut terambil.Jika hanya diambil 3 buah, maka ada kemungkinan ketiga bola itu berbeda warna satu sama lain.jadi, 4 buah bola adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjamin terambil sepasang bola yang berwarna sama.
K.    Peluang Diskrit

Peluang diskrit mempunyai sifat sebagai berikut:
a.       0≤p(xi)≤1, yaitu peluang adalah bilangan tidak negatif dan selalu lebih kecil atau sama dengan 1.
b.      i=1|S|p(xi)=1 , yaitu jumlah peluang semua titik contoh di dalam ruang contoh S adalah 1.
Contoh:
Pada pelemparan dadu, S={1,2,3,4,5,6}. Peluang munculnya setiap angka adalah sama yaitu 1/6.
            Kejadian (event)→ disimbolkan dengan E- adalah himpunan bagian dari ruang. Peluang kejadian E di dalam ruang contoh S adalah P(E)=|E|/|S|. Peluang kejadian E juga diartikan sebagai jumlah peluang semua titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa:
PE=|E||S|=xi∈Ep(xi)
Konsep-konsep pada teori himpunan:
•         P A∩B=xi∈A∩Bp(xi)
•         P A∪B=xi∈A∪Bp(xi)
•         P A-B=xi∈A-Bp(xi)
•         P A⨁B=xi∈A⨁Bp(xi)
•         P(A)=1-P(A)

Soal :
1. Dalam mengadakan suatu pemilihan dengan menggunakan obyek 4 orang pedagang kaki lima untuk diwawancarai, maka untuk memilih 3 orang untuk satu kelompok. Ada berapa cara kita dapat menyusunnya?
2. Suatu warna tertentu dibentuk dari campuran 3 warna yang berbeda. Jika terdapat 4 warna, yaitu Merah, Kuning, Biru dan Hijau, maka berapa kombinasi tiga jenis warna yang dihasilkan?
3. Sebuah kotak berisi 5 bola merah, 4 bola putih, dan 3 bola biru. Sebuah bola dipilih secara acak dari kotak, warnanya dicatat, dan kemudian bolanya dimasukkan kembali. Tentukan peluang bahwa dari 6 bola yang diambil secara acak dengan cara ini, 3 diantaranya berwarna merah, 2 adalah putih, dan 1 biru?
4. Menjelang Pergantian kepengurusan BEM STMIK Bani Saleh akan dibentuk panitia inti sebanyak 2 orang (terdiri dari ketua dan wakil ketua), calon panitia tersebut ada 6 orang yaitu: a, b, c, d, e, dan f. Ada berapa pasang calon yang dapat duduk sebagai panitia inti tersebut?

5. Ada berapa cara bila 4 orang remaja (w,x, y, z) menempati tempat duduk yang akan disusun dalam suatu susunan yang teratur?

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *