Permutasi

A.    Definisi permutasi

Permutasi adalah penyusunan kembali suatu kumpulan objek dalam urutan yang berbeda dari urutan yang semula.

Jika terdapat suatu susunan abjad abcd, maka susunan 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 susunan baru yang tertulis mengandung unsur-unsur yang sama dengan susunan semula abcd, hanya saja ditulis dengan urutan yang berbeda. Maka setiap susunan baru yang memiliki urutan berbeda dari susunan semula ini disebut dengan permutasi dari abcd.

B.     Menghitung Banyaknya Permutasi yang Mungkin

Untuk membuat permutasi dari a, b, c, d, 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 -------------- a   b   c   d

Kotak Kosong -------------- [ ] [ ] [ ] [ ]

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

A.  Permutasi dari unsur-unsur yang berbeda 
              Perhatikan susunan angka-angka yang terdiri atas 4, 5, dan 6 berikut:

                456      465      546      564      645      654

         Letak angka dalam susunan tersebut mempengaruhi nilai bilangan yang terbentuk. Bilangan-bilangan 456  465. Demikian juga untuk susunan yang lain. Banyak susunan angka ratusan yang dapat dibuat dari 3 buah angka, yaitu 4, 5, dan 6 sebanyak 6 buah. Bagaimana susunanya jika angka-angka yang tersedia 4,5,6,dan 7? Susunan angka ratusan yang mungkin dari 4 angka, yaitu 4,5,6 dan 7 adalah sebagai berikut:

                             456      465      546      564      645      654

                             457      475      547      574      745      754

                             467      476      647      674      746      764     

                             567      576      657      675      756      765

Ternyata ada 24 cara
Susunan obyek-obyek yang memerhatikan susunan seperti ini dinamakan permutasi.
Dari permasalahan di atas diperoleh bahwa Jika angka-angka disusun terdiri atas 3 angka dari 3 angka yang tersedia, banyak susunannya. 
Jika angka-angka disusun terdiri atas 3 angka dari 4 angka yang tersedia, banyak susunanya.
Jika kalian teruskan, angka-angka disusun terdiri atas k angka dari n angka yang tersedia, banyak susunanya adalah.
Jadi diperoleh kesimpulan sebagai berikut.

Permutasi k unsur atau objek unsur n yang tersedia, dengan memerhatikan urutan susunanya dapat ditentukan dengan rumus: nPk  =

 

Contoh;

Di dalam sebuah kelas, akan dibentuk kepengurusan yang terdiri atas ketua, sekretaris, dan bendahara kelas. Berapa banyak cara 6 calon yang akan memperebutkan ketiga posisi tersebut?

Penyelesaian:

Karena posisi yang diperebutkan masing-masing berbeda, kasus ini dapat dikerjakan dengan permutasi 3 unsur dari 6 unsur yang tersedia

ⁿP_k =

⁶P₃ = = 120 cara

C. Permutasi Memuat Beberapa Unsur yang Sama

            Pada pembahasan sebelumnya, permutasi memuat unsur yang berbeda. Sekarang, perhatikan unsur  penyusun “APA”  yaitu A, P, A.

            Huruf A pada urutan pertama dan ketiga meskipun dibalik akan mempunyai makna yang sama. Misalkan A₁  dan  A₃ masing-masing adalah huruf A yang pertama dan ketiga.

1.      Permutasi 3 unsur dari 3 unsur yang tersedia, yaitu A_1, P, A₃ (A₁  dan A₃  diandaikan berbeda) adalah

³P₃ = 3! = 3 x 2 x 1= 6

Dengan demikian, diperoleh susunan dalam 3 kelompok berikut

a)      A₁PA₃

A₃PA₁

b)      A₁A₃P

A₃A₁P

c)      PA₁A₃

PA₃A₁

2.      Permutasi 3 unsur dari 3 unsur yang tersedia, yaitu A₁PA₃ (A₁ dan A₃ diandaikan sama) susunanya adalah

APA    AAP    PAA

Jadi hanya terdapat 3 cara. Hal ini terjadi karena pada setiap kelompok terdapat 2! = permutasi pada penyusunan 2 huruf A yang sama, yaitu A₁ dan A₃.

Dengan demikian, permutasi 3 unsur, dengan 2 unsur yang sama dari 3 unsur adalah

Permutasi n unsur, dengan k unsur sama dari n  unsur itu  adalah

Secara umum dapat disimpulkan sebagai berikut.

Aturan ini dapat diperluas sebagai berikut.

Untuk permutasi n unsur, dengan k1 unsur sama, k2 unsur sama…., dan kn  unsur sama dari n unsur , yaitu

Contoh :

1.      Tentukan banyak susunan huruf yang dibentuk dari unsur-unsur huruf pembentuk kata PENDIDIKAN

2.      Misalnya terdapat 6 bendera dengan rincian 2 bendera berwarna merah, 3 bendera berwarna putih, dan 1 berwarna biru.

Berapa banyak susunan yang dapat dibuat untuk menyusun bendera itu secara berjajar?

Penyelesaian:

1. PENDIDIKAN

Unsur yang tersedia ada 10

Unsur yang sama adalah

1)      k₁ = 2, yaitu huruf N ada 2;

2)      k₂ = 2, yaitu huruf D ada 2;

3)      k₃  = 2, yaitu huruf I ada 2.

Jadi

2. Banyak susunan yang dapat dibuat adalah

B

B

D.  Permutasi siklis

 Perhatikan gambar berikut

A

C

C

A

 

                        I                                                                       II

Perhatikan susunan melingkar pada gambar I. Susunan tersebut dapat dikatakan sebagai susunan dari  ABC, BCA, CAB. Dengan demikian, susunan ABC, BCA, dan CAB pada dasarnya merupakan satu susunan yang sama. Kemudian, jika kita memerhatikan gambar 2, kita menjumpai susunan ACB, CBA, BAC adalah suatu susunan yang sama. Secara keseluruhan susunan itu ada 2 macam, yaitu

            Susunan 1 : ABC, BCA, CAB

            Susunan 2 : ACB, CBA, BAC

Penenpatan pada unsur-unsur dalam permutasi seperti inilah yang disebut permutasi siklis. Jadi permutasi siklis adalah permutasi yang disusun secara melingkar.

Untuk menentukan bentuk susunan n objek yang disusun secara melingkar  maka tentukan sebuah titik yang dianggap sebagai titik tetap. Kemudian, sisanya dianggap sebagai penyusunan (n - 1) unsur dari (n-1) unsur yang berbeda.

Dengan demikian dapat dikatakan sebagai berikut.

Jika terdapat 3 objek disusun secara melingkar, banyak susunan yang mugkin yaitu 2! = (3- 1)!

Jika terdapat 4 unsur disusun secara melingkar , banyak susunan yang mugkin adalah 3!= (4 – 1)! Dan seterusnya. Misalkan terdapat n unsur yang berbeda disusun secara melingkar. Banyak susunan dapat ditentukan dengan permutasi siklis dengan aturan

Contoh:

Sebanyak 6 orang mengadakan rapat. Mereka duduk menghadap sebuah meja bundar. Berapakah banyak cara mereka menempati kursi yang disusun melingkar itu?

Penyelesaian:

Banyak cara mereka menempati kursi adalah

P_siklis = (6 - 1)! = 5! = 120 cara.