permutasi dan kombinasi

PERMUTASI DAN KOMBINASI

1)      Permutasi

Permutasi merupakan penyusunan kembali suatu kumpulan objek dalam urutan yang berbeda dari urutan yang semula. Atau dalam kata lain, perutasi merupakan jumlah urutan berbeda dari objek objek.

Permutasi merupakan bentuk khusus aplikasi aturan perkalian. Misalkan jumlah objek adalah n , maka urutan pertama dipilih dari n objek, urutan ke dua dipilih dari n-1 objek, urutan ketiga dipilih dari n-2 objek, begitu seterus nya dan urutan terakhir dipilih dari 1 objek yang tersisa.

n(n-1)(n-2)...(2)(1)=n!

·         Rumus dari Permutasi k unsur dari n unsur:

                                 P(n,k)=

Contoh:

1.       Terdapat 4 orang mahasiswa yang di calonkan sebagai ketua dan wakil ketua. Tentukan berapa banyak cara yang dapat digunakan untuk mengisi posisi tersebut?

Penyelesaian:

n=4

k=2

maka, P(4,2)=

maka ada 12 cara yang dapat dilakukan untuk mengisi posisi tersebut.

·         Permutasi r dari n objek adalah jumlah kemungkinan urutan r buah objek yang dipilih dari n buah objek, dengan r ≤ n, yang dalam hal ini pada setiap kemunkinan urutan tidak ada yang  sama.

             P(n,n)== ==n!

·         Permutasi beberapa unsur yang sama.

Setiap unsur pada permutasi tidak boleh digunakan lebih dari satu kali, kecuali jika dinyatakan secara khusus. Banyaknya permutasi dari unsur n yang memuat k unsur yang sama(k+l+...+m<=n) dapat di tentukan dengan rumus:

       P=

Contoh:

Terdapat dua boneka beruang,1 boneka panda, dan 3 boneka kucing yang sama jenis dan ukurannya. Ada berapa carakah boneka-boneka itu dapat disusun berdampingan?

Pembahasan:

                     

                        Jadi banyaknya susunan boneka-boneka tesebut adalah 60 cara.

2)      KOMBINASI

Kombinasi merupakan bentuk khusus dari permutasi. Jika pada permutasi urutan kemunculan di perhitungkan, maka pada kombinasi urutan kemunculan diabaikan. Dimana urutan acb,bca, dan acb dianggap sama dan dihitung sekali.

Kombinasi r elemen dari n elemen adalah:

Ø  Jumlah pemilihan yang tidak terurut r elemen yang daiambil dari n buah elemen disebut  dengan kombinasi-r.

          C(n,r)=C=

Ø  C(n,r ) dibaca “n diambil r”→r objek diambil dari n buah objek.

Interpretasi kombinasi

1.      Persoalan kombinasi, C(n,r), sama dengan menghitung banyaknya himpunan bagian yang terdiri dari r elemen yang dapat dibentuk dari himpunan dengan n elemen. Dua atau lebih himpunan bagian dengan elemen-elemen yang sama dianggap sebagai himpunan yang sama, meskipun urutan elemen-elemennya berbeda.

Musalkan A={1,2,3}

Jumlah himpunan bagian dengan 2 elemen yang dapat dibentuk dari himpunan a ada 3 buah, yaitu:

{1,2}={2,1}

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

{3,2}={2,3}

Atau  ==

2.      Persoalan kombinasi , C(n,r), dapat di pandang sebagai cara memilih r buah elemen dari n buah elemen yang ada, tetapi urutan elemen di dalam susunan hasil pemilihan tidak penting.

Contoh:

Ada berapa cara dapat memilih 3 dari 4 elemen  himpunan A = {a, b, c, d} ?

Penyelesaian:

 Ini adalah persoalan kombinasi karena urutan kemunculan  ketiga elemen tersebut tidak  

 penting

Himpunan bagian A dengan 3 elemen	Permutasi setiap himpunan bagian
{a, b, c}	abc,acb,bca,bac,cab,cba
{a, b, d}	abd,adb,bda,bad,dab,dba
{a, c, d}	acd,adc,cda,cad,dac,dca
{b, c, d}	bcd,bdc,cdb,cbd,dbc,dcb

 
Untuk setiap 3 elemen ada 3! = 6 urutan yang berbeda  (permutasi  P = n ! ). 

Jadi jumlah cara memilih 3 dari 4 elemen himpunan adalah C(4,3)=

yaitu himpunan {a, b, c}, {a, b, d}, {a, c, d}, dan {b, c, d}.

Soal:

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.      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