PERMUTASI DAN KOMBINASI

PERMUTASI

Permutasi merupakan bentuk khusus aplikasi aturan perkalian. Misalkan jumlah objek adalah n, maka urutan pertama dipilih 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!

Permutasi adalah penyusunan kembali suatu kumpulan objek dalam urutan yang berbeda dari urutan yang semula. Dalam permutasi urutan sangat diperhatikan.

Jika terdapat suatu untai abjad abcd, maka untai itu dapat dituliskan kembali dengan urutan yang berbeda: acbd, dacb, dan seterusnya. Selengkapnya ada 24 cara menuliskan keempat huruf tersebut dalam urutan yang berbeda satu sama lain.

 abcd  abdc  acbd  acdb  adbc  adcb

 bacd  badc  bcad  bcda  bdac  bdca

 cabd  cadb  cbad  cbda  cdab  cdba

 dabc  dacb  dbac  dbca  dcab  dcba

Setiap untai baru yang tertulis mengandung unsur-unsur yang sama dengan untai semula abcd, hanya saja ditulis dengan urutan yang berbeda. Maka setiap untai baru yang memiliki urutan berbeda dari untai semula ini disebut dengan permutasi dari abcd.

Untuk membuat permutasi dari abcd, dapat diandaikan bahwa terdapat empat kartu bertuliskan masing-masing huruf, yang hendak kita susun kembali. Juga terdapat 4 kotak kosong yang hendak kita isi dengan masing-masing kartu:

 Kartu            Kotak kosong

 -----------      ---------------

 a  b  c  d       [ ] [ ] [ ] [ ]

Maka kita dapat mengisi setiap kotak dengan kartu. Tentunya setiap kartu yang telah dipakai tidak dapat dipakai di dua tempat sekaligus. Prosesnya digambarkan sebagai berikut:

·         Di kotak pertama, kita memiliki 4 pilihan kartu untuk dimasukkan.

 Kartu            Kotak

 -----------      ---------------

 a  b  c  d       [ ] [ ] [ ] [ ]

                   ^ 4 pilihan: a, b, c, d

·         Sekarang, kondisi kartunya tinggal 3, maka kita tinggal memiliki 3 pilihan kartu untuk dimasukkan di kotak kedua.

 Kartu            Kotak

 -----------      ---------------

 a  *  c  d       [b] [ ] [ ] [ ]

                       ^ 3 pilihan: a, c, d

·         Karena dua kartu telah dipakai, maka untuk kotak ketiga, kita tinggal memiliki dua pilihan.

 Kartu            Kotak

 -----------      ---------------

 a  *  c  *       [b] [d] [ ] [ ]

                           ^ 2 pilihan: a, c

·         Kotak terakhir, kita hanya memiliki sebuah pilihan.

 Kartu            Kotak

 -----------      ---------------

 a  *  *  *       [b] [d] [c] [ ]

                               ^ 1 pilihan: a

·         Kondisi terakhir semua kotak sudah terisi.

 Kartu            Kotak

 -----------      ---------------

 *  *  *  *       [b] [d] [c] [a]

Di setiap langkah, kita memiliki sejumlah pilihan yang semakin berkurang. Maka banyaknya semua kemungkinan permutasi adalah 4×3×2×1 = 24 buah. Jika banyaknya kartu 5, dengan cara yang sama dapat diperoleh ada 5×4×3×2×1 = 120 kemungkinan. Maka jika digeneralisasikan, banyaknya permutasi dari n unsur adalah sebanyak n!

Banyaknya kemungkinan permutasi seperti ini adalah

Contoh:

1.    Berapa banyak string yang dapat dibentuk dari huruf WEAKNESS jika urutan diperhatikan?

Penyelesaian:

WEAKNESS

W=1

E=2

A=1

K=1

N=1

S=2

n=8 buah

Jumlah string= P(8;1,1,2,1,1,2)=8!/1!1!2!1!2!

                                                  = 8!/2!2!

                                                  = 8!/4!

                                                  =8*7*6*5*4!/4!

                                                  = 10.080 cara

2.        Berapakah jumlah kemungkinan membentuk 3 angka dari 5 angka berikut:1,2,3,4,5 jika tidak boleh ada pengulangan angka.

Penyelesaian:

Ada 3 posisi yang akan dipilih dari 5 angka. Posisi pertama diisi oleh salah satu dari 5 angka, posisi kedua oleh salah satu angka dari 4 angka, dan posisi ketiga oleh salah satu angka dari 3 angka. Sehingga jumlah urutan 3 angka yang dapat dibentuk adalah (5)(4)(3)=120 buah atau dengan rumus permutasi P(5,3)=5!(5-3)!=120 buah.

KOMBINASI

Bentuk khusus dari permutasi adalah kombinasi, jika pada permuutasi urutan kemunculan diperhatikan dan diperhitungkan, maka pada kombinasi urutan kemunculan diabaikan. Urutan acb.bca,abc dianggap sama dan dihitung sekali

Kombinasi k elemen dari n elemen: dinotasikan C(n,k)

Terdapat n objek. Kita akan mengambil sebanyak k elemen.

Jika urutan pengambilan tidak diperhatikan dan pengembalian tidak diperbolehkan, maka banyaknya kemungkinan yang mungkin adalah:

Contoh:

1.      Berapa banyak string yang dapat dibentuk dari huruf WEAKNESS ?

Penyelesaian:

WEAKNESS

W=1

E=2

A=1

K=1

N=1

S=2

n=8 buah

Jumlah String = C(8,1)*C(7,1)*C(6,2)*C(4*1)*C(3,1)*C(2,2)

                        = (8!/1!*7!)* (7!/1!*6!) * (6!/2!*4!) * (4!/1!*3!) * (3!/1!*2!) * (2!/2!)

                        = 8*7*15*3*1

                        = 10.080 cara

2.      Ada 5 orang mahasiswa jurusan Teknik Informatika dan 7 orang mahasiswa jurusan Teknik Elektro. Berapa banyak cara membentuk panitia yang terrdiri dari 4 orang jika:

a.       Tidak ada batasan jurusan

b.      Semua anggota panitia harus dari jurusan Teknik Informatika

c.       Semua anggota panitia harus dari jurusan Teknik Elektro

d.      Semua anggota panitia harus dari jurusan yang sama

e.       2 orang mahawiswa per jurusan harus mewakili

Penyelesaian:

a.       C(12,4)                                   = (12!/4!*8!)

= 495 cara

b.      C(5,4)*C(7,0)                         = (5!/4!*1!) * (7!/0!*7!)

                        = 5 cara

c.       C(7,4)*C(5,0)                         = (7!/4!*3!) * C(5!/0!*5!)

                         = 35 cara

d.      C(5,4)*C(7,0) + C(7,4)*C(5,0)   = 5 + 35

  = 40 cara

e.       C(5,2)*C(7,2)                              = (5!/2!*3!) * (7!/2!*5!)

                              = 10 * 21

                              = 210 cara