My first Magazine pemrograman-kompetitif-dasar | Page 31

2.5 Kombinatorika
Secara umum, jika terdapat N huruf, banyak kata yang dapat kita susun adalah N!. Apabila
terdapat K huruf dengan setiap hurufnya memiliki R i huruf yang sama, maka dengan aturan
pembagian banyak kata berbeda yang dapat disusun adalah:
N!
R 1 ! × R 2 ! × R 3 ! × ... × R K !
Inilah yang kita kenal dengan permutasi elemen berulang. Secara formal, misalkan terdapat
n objek dan terdapat k objek yang mana setiap objeknya memiliki r i elemen yang berulang, maka
banyaknya cara berbeda dalam menyusun objek tersebut adalah:
P r n 1 ,r 2 ,r 3 ,...,r k =
n!
r 1 ! × r 2 ! × r 3 ! × ... × r k !
Permutasi Melingkar
Contoh Soal 2.6: Duduk Melingkar
Terdapat 4 anak, sebut saja A, B, C, dan D. Berapa banyak susunan posisi duduk yang
berbeda apabila mereka duduk melingkar?
Banyak susunan posisi duduk yang berbeda apabila mereka duduk seperti biasa (tidak
melingkar) adalah 4! = 24. Perhatikan bahwa posisi duduk ABCD, BCDA, CDAB, dan DABC
merupakan susunan yang sama apabila mereka duduk melingkar, karena susunan tersebut
merupakan rotasi dari susunan yang lainnya. Dengan kata lain terdapat 4 cara berbeda yang kita
anggap sama. Dengan aturan pembagian, banyak susunan posisi duduk yang berbeda adalah:
24
= 6
4
Secara umum, banyaknya susunan posisi duduk yang berbeda apabila N anak duduk seperti
biasa (tidak melingkar) adalah N!. Untuk setiap konfigurasi duduk yang ada, kita dapat melakukan
rotasi beberapa kali terhadap konfigurasi tersebut dan menghasilkan posisi duduk yang sama.
Akan ada tepat N buah rotasi yang mungkin, misalnya untuk konfigurasi A 1 , A 2 , A 3 , ..., A N−1 , A N :
•
•
•
•
•
Rotasi 0 kali: A 1 , A 2 , A 3 , ..., A N−1 , A N
Rotasi 1 kali: A 2 , A 3 , A 4 , ..., A N , A 1
Rotasi 2 kali: A 3 , A 4 , A 5 , ..., A 1 , A 2
...
Rotasi N − 1 kali: A N , A 1 , A 2 , ..., A N−2 , A N−1
Maka dengan aturan pembagian, banyak susunan posisi duduk yang berbeda adalah:
N!
= (N − 1)!
N
.
Inilah yang kita kenal dengan istilah permutasi melingkar, atau permutasi yang disusun
melingkar. Banyaknya susunan yang berbeda dari permutasi melingkar terhadap n objek adalah:
n
P (melingkar)
= (n − 1)!
21