BAB 3

Diposting oleh Unknown


KOMBINATORIKA
Dasar-dasar Perhitungan
1 ) Aturan Penjumlahan
          Misal himpunan A adl gabungan dari himpunan-himpunan bagian yang tidak kosong dan saling asing maka jumlah elemen  himpunan A sama dengan jumlah anggota semua himpunan bagian
Contoh
Dalam suatu kartu bridge lengkap berapa cara untuk mengambil
a) Sebuah kartu jantung atau sebuah daun
          Jawab :
          Kartu jantung dan kartu daun merupakan himpunan yang saling asing maka untuk mendapatkan salah satunya adalah JUMLAH cara pada masing-masing bagian(jantung dan daun), untuk mendpat satu kartu jantung adalah 13 cara (karena kartu jantung ada 13 buah), untuk mendapat kartu daun adalah 13 cara(karena kartu daun 13 buah ) jadi untuk mendapat satu kartu jantung atau satu kartu daun adalah 13+13=26 cara
b) Sebuah kartu  jantung atau as
Jawab :
 ingat  jumalah kartu jantung 13 sudah termasuk as
Kartu as semua 4 buah (ada 3 kartu as selan jantung) maka banyak cara sebuah kartu jantung atau as adalah 13+3=16
Contoh 2
Misal dua dadu berbeda warna (merah dan putih) dilempar ada berapa macam cara untuk mendapatkan jumlah angka 4 atau 8.
Jawab :
Bentuk elemen (merah, putih)
Untuk mendapat jumlah 4 adalah 3 cara yaitu (1,3); (2,2); (3,1)
Untuk mendapat jumlah  8 adalah 5 cara yaitu........
Jadi untuk mendapat jumlah 4 atau 8 adalah 3+5=8 cara
Contoh 3
Misal dua dadu warna sama dilempar ada berapa macam cara untuk mendapatkan jumlah angka 4 atau 8.
Jawab :
karena warna sama maka elemen  (1,3) dg (3,1) dianggap satu elemen
Begitu juga elemen (2,6) dg (6,2) dan (3,5) dg (5,3) jadi kemungkinannya tinggal 5 cara
2)  Aturan Perkalian
Misal suatu pekerjaan melibatkan k buah langkah dimana
Langkah  ke-1 ada n1 cara  (cara ke1,cara ke2, ..... Cara ke n1 )
Langkah  ke-2 ada n2 cara  (carake1,cara ke2, ..... Cara ke n2 )
Langkah  ke-3 ada n3 cara (carake1,cara ke2, ..... Cara ke  n3 )
.........................................
Langkah  ke-k ada nk cara (cara ke1,cara ke2, ..... Cara ke nk ).
Dg demikain semua pekerjaan adalah sebanyak (n1 )(n2 )... (nk ) cara
(untuk membayangkan bentuk elemennya,  ingat perkaian kartesian jika ada k-terorder identik dg titik pada Rk/ruang demensi k )
Contoh 1
Jika dua buah dadu berbeda dilontarkan ada berapa banyak cara angka yang muncul ?bagaimana jika 5 dadu, bagaimna jika n dadu ?
 jawab adl  (6)(6)= 62 cara; untuk 5 dadu adl 65; untuk n dadu adalah 6n cara
Contoh 2
Misalkan barang-barang disuatu pabrik diberi nomer kode yang terdiri dari  3 huruf dan 4 angka (misal BUD1234)
a)Jika baik huruf maupun angka boleh diulang penggunaannya ada berapa macam barang yg dat diberi kode yg berbeda?
b)Jika huruf saja yg dapat diulang
 jawab
a)Jumlah huruf 26 dan jumlah angka 10, maka kode yg terdiri dari 3 huruf adalah 263cara ,sedang kode yg terdiri dari 4 angka adl (10)4cara, maka banyak kode dg kombinasi 3 huruf dan 4 angka adl (26)3(10)4cara.=   ........ cara
b) kode yg terdiri dari 3 huruf adalah 263cara
    kode yg terdiri dari 4 angka adalah (10)(9)(8)(7) cara
Maka banyak kode dengan  3 huruf dan 4 angka adalah (26)3(10)(9)(8)(7) cara
 Contoh 3
berapa banyak bilangan yg terdiri dari 2digit atau 3 digit yang dapat dibentuk menggunakan angka-angka 1,2,3,4,5,6,7 jika perulangan tidak  diperbolehkan.
Jawab
Banyak bilangan dari 2 digit adalah45545555 (7)(6) cara= 42 cara
Banyak bilangan dari 3 digit adalah (7)(6)(5) cara = 210 cara
Maka banyak bilangan terdiri dari 2 digit atau 3 digit adalah
 (7)(6)+ (7)(6)(5) cara
KOMBINASI DAN PERMUTASI
Untuk perhitungan bagian ini yang perlu dipahami yaitu tentang Faktorial
Definisi
Besaran n faktorial (degan simbul n!)adalah sebagai hasil kali semua bilangan bulat antara 1 hingga n
Catatan
Untuk n=0 didefinisikan husus yaitu 0!=1
 selanjutnya  untuk bilangan bulat yang lain didapat sbb n!=1.2.3.......(n-1).n
Dari definisi faktorial didapat persamaan sbb   n!= n(n-1)! (buktikan)

=                                                sehingga didapat n!=  n(n-1)!

Kombinasi ( hal yang diperhatikan obyek-obyek yg muncul)
Misal himpunan S memiliki n elemen
  n
  r
Ada  himpunan bagian S memiliki r elemen dimana r≤n disebut kombinasi n obyek yang diambil sebanyak r obyek sekaligus, simbulnya adalah
                        atau ditulis C(n,r)
  n
  r
    n!
r! (n-r)!
 


Banyaknya kombinasi yg dimaksud adl                   = 

Catatan: urutan tidak diperhatikan maksudnya adalah elemen bentuk ab dengan elemen bentuk ba dianggap satu elemen(dianggap sama)
Contoh
seorang pelatih basket  akan memilh komposisi pemain yg akan diturunkan dlm pertandingan , ada 12 orang pemain yg dapat dipilih. Berapa macam tim yg dapat dibentuk?
Jawab jumlah pemain basket dalam suatu tim ada 5 orang
Banyak tim yg dapat dibentuk adl
                                                                     =                 =                         =  792
Contoh 2
Suatu perusahaan memiliki 5 karyawan laki-laki dan 7 karyawan wanita , lalu akan dipilih 5 orang untuk mengerjakan suatu proyak, ada berapa tim yg dapat dibentuk apabila dalam tim tersebut harus
a)Terdiri dari 3 karyawan laki dan 2 karyawan wanita
Jawab
Untuk laki-laki adl C(5,3))=               = 10
Untuk wanita adl C(7,2) =                       =21
Jadi unt milih tim terdiri 3 laki dan 2 wanita adl  ,                               =210  cara
 b) Terdiri dari paling sedikit terdapat 1 karyawan laki
jawab                                                               
Kasus ini ada 5  tim(setiap tim ada beberapa cara)
tim satu 1 laki dan 4 wanita banyak cara adl
                                                                            5         7
                                                                            1         4     cara=175
Tim dua 2 laki dan 3 wanita banyak cara adl
                                                                             5         7
                                                                             2         3    cara=350
Tim tiga 3 laki dan 2 wanita banyak cara adl
                                                                              5        7
                                                                              3        2      cara=210
Tim empat 4 laki dan 1 wanita banyak cara adl
                                                                               5        7
                                                                               4        1    cara=35
Tim lima 5 laki dan 0 wanita banyak cara adl         5      7
                                                                                 5      0     cara=1
Jadi cara memilih paling sedikit 1karyawan laki adl semua cara dijumlah=771

Permutasi (urutan diperhatikan artinya elemen ab beda dg elemen ba)
                    pengulangan elemen tidak diperbolehkanartinnya tdk bisa dplih lagi
Misalkan dalam kelas terdiri dari 30 mahasiswa coba perhatikan 2 kasus berikut; yaitu
    a) diambil 2 mahasiswa ada berapa cara
         b) diambil  1 mahasiswa sbg ketua dan 1 mahasiswa lagi sebagai bendahara
Terlihat kasus ponit b) adalah permutasi karena ab dg ba adl beda sedangkan kasus a) terlihat ab dengan ba adalah sama (dihitung satu elemen )
Perhatikan gambar tentang 4 elemen diambil 2 elemen berikut;
{a,b,c,d}      { a,b}             a,b
                                           b,a
                    { a,c}              a,c
                                            c,a
                    {a,d}
                    {b,c}
                    { b,d}
                    {c,d }                         dstnya ,dari sini didapat rumus

  n!
(n-r)!
Rumus cecara umum untuk r obyek yg diambil dari n obyek adalah
          
           P(n,r) =                        jika n=r disebut permutasi n obyek  P(n,n)=n!
Contoh
Suatu undian dilakukan dg menggunakan angka yg terdidi dari 7 digit , jika digit digit dalam suatu angka diharuskan berbeda satu dg yang lain , ada berapa kemungkinan nomer undiannya?
Jawab
Dalam undian tsb jelas urutan angka diperhatikan (dihitung), maka banyaknya undian adlah
  n!
(n-r)!
                        
   P(10, 7) =                             =10.9.8.7.6.5.4=604800 macam kmungkin


Contoh 2
Sebuah grup terdiri dari 7 wanita dan 3 pria . Ada berapa macam cara berbaris yg mungkin dibuat jika 3 pria tersebut selalu kumpul/bersebelahan
Jawab dalam hal ini ada dualangkah penyelesaiannya
Langkah 1 adalah permutasi dari 3 obyek adalah P(3,3)=3!=3.2.1=6
Langkah 2 adl permutasi dari 8 obyek P(8,8)=8!=40320
Jadi macamnya grup laki dan wanita adalah (6)(40320)=241920 macam
Rumus permutasi untuk susunan melingkar dengan n obyek yang beda adalah P(n,n)=(n-1)!
Berkurang karena posisi obyek yang pertama yang ditempatkan tidak begitu penting (yang dipentingkan kedudukan setiap obyek relatif dengan obyek yang lain
Kombinasi dan permutasi dengan elemen berulang(elemen nya sama/elemen ada yang lebih dari satu
Jika suatu himpunan terdiri dari n obyek tersusun dari
Jenis 1 sebanyak n1
Jenis 2 sebanyak n2
…………………….
Jenis k sebanyak nk , dimana n1+n2+…..+nk=n
Menggunakan rumus
       
        P(n,n1,n2,….nk)=                       ...                            =
contoh
Tentukan banyaknya macam cara untuk menyusun huruf-huruf dalam kata MISSISSIPPI
Jawab n=11, jenis huruf M =1 buah
                      jenis huruf   I =4 buah
Jenis huruf S =4 buah
jenis huruf P =2 buah
jadi banyaknya cara     adl =                   =34650
Contoh
Ada berapa macam cara agar 23 macam buku yang berbeda dapat diberikan pada 5 mahasiswa dengan aturan 2 mahasiswa memperoleh 4 buku dan 3 mahasiswa memperoleh 5 buku
Jawab
Ada dua langkah
Langkah pertama memilih 2 mahasiswa memperoleh 4 buku
Ada    5         =    5!        =10 cara    (rumus  2 sekat)
           2            2! (5-2)!  
Langkah kedua pendistribusian 23 buku dibagikan 5 mahasiswa, itu merupakan    permutasi berulang yaitu                    
                                                                                         cara    (rumus 5 sekat)
Jadi banyak cara pendistribusiannya adl
    10                             =    ......   macam cara

Aplikasi kombinatorika dalam ilmu Komputer
1. Pengenal (identifer) dalam Pascal
-harus dibuat(dideklarasikan) dulu sebelum identifer tsb dipakai
-identifer terdiri dari gabungan huruf, angka dan simbul-simbul husus
-karakter pertama harus huruf
-panjang identifer tentang kompiler yg dipakai
-identifer yang sudah dipakai oleh pascal sebagai kata kunci(reserved word) tdk boleh dipakai untuk keperluan lain seperti begin, end dll
Contoh
Misalkan dalam kompiler pascal, identifer tersusun dari 26 huruf,10 angka dan 3 simbul husus, panjang identifer yg diizinkan 8 karakter, jumlah kata kunci yang sudah dipakai 35, berapa identifer yg masih dapat digunakan?
Jawab
Panjang identifer maksimal 8 karakter
-Identifer dengan panjang 1 karakter =26  macam (karena pertama hrs huruf)
-Identifer dengan panjang 2 karakter= (26)(39) macam (karena karakter pertama harus huruf karakter kedua bisa berupa huruf,angka dan sibul husus)
-identifer dengan panjang 3 karakter=26(39)2
-identifer dengan panjang 4 karakter=26(39)(39)(39)=26(39)3
………………………………………………..
-identifer dengan panjang 8 karakter=26(39)(39)(39)(39)(39)(39)(39)=26(39)7
jadi jumlah identiber dengan panjang maksimal 8 adal = jumlah semua identifer dengan panjang 1 sampai 8 dijumlahkan yaitu
            26+26(39)+26(39)2+26(39)3………..+26(39)7
Karena sudah dipakai 35 identifer sebagai kata kunci seingga identifer yang dapat dipakai adalah; (26+26(39)+26(39)2+26(39)3………..+26(39)7-35) macam
Jumlah iterasi dalam suatu loop(kalang)
-kebanyakan program menggunakan kalang
-statemen dalam kalang inilah yang sering dieksekusi sehingga lama waktu eksekusi tgt dari banyaknya kalang-kalang dalam yang dieksekusi
contoh
Perhatikan kalang FOR dibawah ini , berapa kali statemen didalamnya dieksekusi?
a)      For     i = 1 to n do
       statemen – statemen dalam kalang. Tidak ada perintah di dalamnya yang menyebabkan eksekusi melompat keluar kalang.
        { end for - i}
Jawab
Misal x = statement dalam kalang, x tidak boleh keluar kalang sebelum kalang selesai dieksekusi
 x akan dieksekusi untuk i =1,2,3,….n; jadi dieksekusi sebanyak n kali
b)      For i = 1 to n Do
            For j = 1 to m Do
          Statemen – statemen dalam kalangan. Tidak ada perintah di dalamya yang menyebabkan eksekusi melompat keluar kalang.(jmlah=nilai+kuis)
          { End For – j }
{ End For – i}
Jawab
Eksekusi statemen dalam kalang dapat digambar sbb
i=1           j=1
                j=2
                j=3
               ….
                j=m (dan seterusnya untuk  i=2, ………i=n)
Ada tiap cabang keluar, statement selalu dieksekusi sekali menggunakan aturan perkalian, maka statement akan dieksekusi sebanyak mana kali
Contoh
Ada berapa banyak fungsi bool 3 variabel yg dapat dibuat, bila fungsi bool didefinisikan dg mengawankan masing-masing bil biner 3 digit 0 atau 1
Jawab
Salah satu nilai fungsi biner adl 10011000 jadi didapat 28 cara

1. Segitiga Pascal
Salah satu persamaan dlm kombinatorika dan dapat diguna untuk menghitung kombinasi suatu suku berdasarkan kombinasi suku-suku yg lebih rendah
 identitas paskal dinyatakan dalam persamaan
                             =                  +  
                                                                                                                        =
Secara geometris dapat digambar sbb
    r 
n        0          1             2           3              4.........                   r-1             r
  0      1                    
  1      1           1
  2      1           2           1    
  3      1           3           3            1
  4      1           4           6            4              1
.....      .....       ....          ....           ...
  n                                                        ..........................
n+1                                           .................................

Ada beberapa sifat penting dalam segi tiga Pascal
a)     
n
n
n
0
Kondisi batas
Nilai segitiga pascal dibagian ujung kiri kanan selalu = 1 karena,          =          = 1
b)      Kondisi sekunder
 n
n-1
n
1
Nilai segi tiga pascal pada baris ke n di kolom kedua dan kolom kedua sebelum terakhir selalu = n karena          =             = n
c)     
n
k
 n
n-k
Simetris
n+r+1
  n-1
n+r
 r
n+2
 1
n+1
 0
Nilai pada setiap baris bersifat simetris karena           =
d)    
n
r
n
n
n
0
n
1
Jumlah diagonal :                +              ……. +               =
e)     
2n
 n
Jumlah baris            +          ……. +          …….   +           = 2n
f)     
n
2
n
0
n
1
n
n
n
r
Kuadrat penjumlahan baris          2 +          2  +          2  …. +          …. +        2  =
g)    
n+1
r+1
n
r
r+1
  r
r
r
Jumlah kolom : dg bil positif n dan r, n ≥ r berlaku :           +             + ….          =

Menggunakan sifat-sifat koefisien binomial hitunglah
a.       1 + 2 + 3 + ……….. + n
b.      12 + 22 + …………. + n2
n+1
1+1
n
1
2
1
1
1
k
1
Jawab
a.       k =          maka 1+2+3 + ………+n =          +          + ….          =
n(n+1)!
    2
 (n+1)!
2!(n-1)!
n+1
  2
                                                         =              =                    =
Catatan : ingat sifat penjumlahan kolom untuk r = 1
b.     
k
1
k
2
k
1
k
2
k2 = k(k-1) + k      dalam hal ini r = 2
 2          +          maka 12 + 22 + ….. + n2 = ∑   2          +
k
1
k
2
                                                                =  ∑ 2          + ∑
 n(n+1) (2n+1)
           6
n+1
1+1
n+1
2+1
                                                                =  2             +             =
  n
 r-1
  n
 r-2
 n
 r
n+2
  r
Contoh n, r bil bulat positif  2 ≤ r ≤ n, nyatakan              dalam suku-suku
               ,             dan
n+1
  r
n+1
r -1
n+2
  r
Jawab
                 =                 +                                       ( identitas pascal )
n+2
  r
n+2
  r
  n
 r-2
 n
 r
  n
 r-1
  n
 r-1
  n
 r-2
                 =                +              +              +           =              + 2             +


Teorema Binomial dan Multinomial
 n
 k
n
k=0
Misalkan x dan y adalah bilangan 2 riil dan n adalah bilangan bulat tak negative maka
(x + y)n = ∑            xn-k yk =           xn +         xn-1 y1   +           xn-2 y2  + …. +         yn
Contoh
Uraikan pernyataan: a) (2x + 5y)3      b) (x – 4y)4
Soal
          Manakah yang lebih besar 101 atau 1,0110000
Teorema Multinomial
       n!
n1!n2!    nt!
Multinomial jumlah suku berbeda sebanyak t buah yaitu, dalam hal ini jika jumlahan suku t = 2 disebut binomial dengan demikian berbentuk
          (x1 + x2 + ….. + xt )n = ∑                         x1n1 . x2n2 …. xtnt, dimana n1 + n2 + … +nt = n
n+t-1
    n
          n!
n1!n2!.... nt!
 
Dan banyak suku (x1 + x2 + ….. + xt )n adalah                sedangkan koefisien
Contoh
1. Hitunglah koefisien x12.x3.x43.x54 pada pernyataan (x1 + x2 + x3 + x4 + x5)10
2. Hitunglah koefisien dan banyak suku x3.y3.z2 pada pernyataan (2x – 3y + 5z)8
        10!
2!.0!.1!.3!.4!
Jawab
1. Koefisien adalah                          = 12600
2.
     8!
8!.3!.2!
Koefisien adalah 23.(-3)3.52.                 = -3024000
   10!
  8!.2!
(8+3-1)!
   8!.2!
Dan banyak sukunya adalah                     =                  =                 = 45
Category: 0 komentar

0 komentar:

Posting Komentar