Permutasi (Matdis)

1. Permutasi Unsur Beda Tanpa Perulangan

A. Permutasi Sebagian

Permutasi adalah banyak cara mengambil r obyek dari n obyek berbeda di mana urutan pengambilan diperhatikan dan tidak boleh ada perulangan.

Karena tidak boleh ada perulangan, diharuskan r ≤ n. Permutasi r obyek dari n obyek dinotasikan dengan

_nP_r    atau    P_n,r    atau    P_rⁿ    atau P(n, r)

Tempat pertama masih bebas, sehingga terdapat n pilihan.

Tempat selanjutnya karena sudah terambil 1, tersisa n − 1 pilihan

Tempat selanjutnya karena sudah terambil 2, tersisa n − 2 pilihan

...

Hingga akhirnya terambil sebanyak r − 1 obyek, tersisa n − r + 1 pilihan,

Ambil, dan akhirnya terambil sebanyak r obyek.

Banyaknya cara adalah

n × (n − 1) × (n − 2) × ... × (n − r + 1), jika dituliskan dalam bentuk faktorial

P(n, r) = [n × (n − 1) × (n − 2) × ... × (n − r + 1) × (n − r)!]/(n − r)! = n!/(n − r)!

contoh:

Ada berapa banyak cara memilih 3 orang siswa dari 8 orang siswa yang akan ditunjuk sebagai Ketua, Wakil Ketua dan Sekretaris?

Banyak caranya adalah mengambil 3 orang dari 8 orang untuk menjadi ketua, wakil dan sekretaris. Karena jika 3 orang terpilih menjadi ketua, wakil dan sekretaris, susunannya berbeda dianggap lain, maka urutan diperhatikan. Dan tidak ada orang yang terpilih menjadi ketua sekaligus wakil atau sekretaris, sehingga ini termasuk permutasi, P(8, 3)

P(8, 3) = 8!/(8 − 3)! = [8 × 7 × 6 × 5!]/5! = 8 × 7 × 6 = 336.

Jadi, terdapat 336 cara.

B. Permutasi Utuh

Permutasi utuh adalah banyak cara mengambil semua dari n obyek berbeda di mana urutan pengambilan diperhatikan dan tidak boleh ada perulangan.

Ganti r dengan n, sehingga menjadi:

P(n, n) = n!/(n − n)! = n!/0! = n!/1 = n!

Jadi, banyak cara mengambil semua dari n obyek berbeda di mana urutan pengambilan diperhatikan dan tidak boleh ada perulangan adalah n!.

C. Permutasi Siklis

Permutasi siklis pengaturan n obyek berbeda dalam satu lingkaran.

Misal semua obyek digeser dengan penggeseran yang sama, dianggap tidak mengubah urutan. Dikarenakan terdapat n kemungkinan penggeseran, banyak pengaturannya adalah

P_siklis(n) = n!/n = n(n − 1)!/n = (n − 1)!

Sebagai contoh, terdapat meja bundar dengan 6 kursi A, B, C, D, E, F. Susunan

ABCDEF, BCDEFA, CDEFAB, DEFABC, EFABCD, FABCDE

ini dianggap sama. Banyak semua susunan adalah (6 − 1)! = 5! = 120

2. Permutasi Unsur Sama Tanpa Perulangan

Misal terdapat n obyek dengan

Ada sebanyak n₁ unsur u₁, sebanyak n₁! susunan dianggap sama

Ada sebanyak n₂ unsur u₂, sebanyak n₂! susunan dianggap sama

...

Ada sebanyak n_k unsur u_k, sebanyak n_k! susunan dianggap sama

dengan n₁ + n₂ + ... + n_k ≤ n. Anggapan sama ini menyebabkan banyak susunan n! dibagi dengan susunan-susunan yang dianggap sama, sehingga banyak penyusunannya adalah

contoh:
Banyak penyusunan dari "SUCCESS" adalah...

Perhatikan, bahwa unsur-unsur nya ada yang sama, yaitu S sebanyak 3, dan C sebanyak 2, dari 7 huruf.

P(7; 3, 2) = 7!/[3!2!] = 420
terdapat sebanyak 420 cara penyusunan.

3. Permutasi Dengan Perulangan

Misal diambil r obyek dari n obyek dengan dibolehkannya perulangan, akan ada r tempat yang masing-masing terdapat n pilihan, sehingga banyaknya cara adalah

n × n × ... × n sebanyak r, sehingga banyaknya adalah n^r.

Contoh Soal

1. Ada berapa banyak susuna dari huruf ABCDEFGH dengan ABC selalu berdampingan

ABC berdampingan dan tersisa 5 huruf, terdapat 6 blok, sehingga terdapat 6! = 720 susunan blok

di internal ABC terdapat 3 huruf, sehingga terdapat 3! = 6 susunan huruf

Ada sebanyak 720 × 6 = 4320 susunan.

2. Dalam suatu makan siang terdapat 5 team yang hadir dengan masing-masing team terdiri dari 3 anggota. Mereka duduk mengelilingi meja makan. Tentukan banyaknya kemungkinan mereka duduk jika:

2a. Mereka duduk bebas

P_siklis(15) = (15 − 1)! = 14! = 87.178.291.200 kemungkinan

2b. Setiap team selalu duduk berdampingan

Terdapat 5 team, sehingga banyaknya urutan team adalah

P_siklis(5) = (5 − 1)! = 4! = 24 kemungkinan, kasus ini siklis karena pengurutan ini di pengurutan umum meja makan.

Masing-masing team ada 3! = 6 kemungkinan, kasus ini tidak siklis karena pengurutan ini di internal masing-masing team.

Banyak kemungkinan adalah 24 × 6 = 144 kemungkinan

3. Diketahui 5 pemuda dan 3 pemudi duduk pada 8 kursi berjajar. Berapa banyak kemungkinan susunan mereka duduk jika:

3a. Mereka duduk bebas

8! = 40320 kemungkinan

3b. Ketiga pemudi selalu duduk berdekatan

Ketiga pemudi selalu berdekatan, dianggap 1, sehingga ada 6! = 720 kemungkinan

Susunan tiga pemudi adalah 3! = 6 kemungkinan

Total ada 720 × 6 = 4320 kemungkinan

3c. Diujung-ujung selalu ditempati pemuda

Terdapat 5 pemuda

Banyak susunan ujung adalah P(5, 2) = 20 kemungkinan

karena sudah dikurangi 2 untuk ujung, tersisa 6 orang

Banyak susunan selain ujung adalah 6! = 720 kemungkinan

Total ada 20 × 720 = 14400 kemungkinan

3d. Diujung-ujung selalu ditempati pemuda dan tidak ada pemudi yang duduk berdekatan

Posisi 1 dan 8 harus ditempati oleh pemuda.

Kemungkinan adanya pemudi berdekatan adalah dari 6 posisi terdapat 2 yang berdekatan

(2, 3), (3, 4), (4, 5), (5, 6), (6, 7) ada 5 posisi berdekatan dan masing-masing terdapat 2 urutan

tersisa 1 pemudi yang memiliki 4 kemungkinan posisi

banyak susunan pemudi adalah 5 × 2 × 4 = 40 kemungkinan

sedangkan banyak susunan pemuda adalah 5! = 120 kemungkinan

Total ada 40 × 120 = 4800 kemungkinan

4. Diketahui 5 pemuda dan 3 pemudi duduk pada 8 kursi ditata mengelilingi meja belajar. Berapa banyak kemungkinan susunan mereka duduk jika

4a. Mereka duduk bebas

P_siklis(8) = (8 − 1)! = 7! = 5040 kemungkinan

4b. Ketiga pemudi selalu duduk berdekatan

Ketiga pemudi selalu berdekatan, dianggap 1, sehingga ada

P_siklis(6) = (6 − 1)! = 5! = 120 kemungkinan

Susunan tiga pemudi adalah 3! = 6 kemungkinan

Total ada 120 × 6 = 720 kemungkinan

4c. Jika dari 5 pemuda ada yang bernama Tono dan ada diantara 3 pemudi ada yang bernama Tini, berapa banyak cara susunan mereka duduk jika Tono tidak boleh ada di dekat Tini

Kemungkinan Tono di dekat Tini, anggap Tono dan Tini 1, sehingga ada

P_siklis(7) = (7 − 1)! = 6! = 720 kemungkinan

Susunan Tono dan Tini adalah 2! = 2 kemungkinan

Total ada sebanyak 720 × 2 = 1440 kemungkinan Tono di dekat Tini

Kemungkinan Tono tidak di dekat Tini adalah 5040 − 1440 = 3600 kemungkinan.

5. Penjaga perpustakaan bermaksud menyimpan buku sehingga buku dengan bahasa yang sama akan berjajar berdekatan. Jika ia mempunyai 12 tempat untuk 5 buku berbeda dalam bahasa Inggris, 4 buku berbeda dalam bahasa Perancis, 3 buku berbeda dalam bahasa Jerman. Tentukan banyak kemungkinan susunan buku tersebut!

P(12; 5, 4, 3) = 12!/(5!4!3!) = 27720 kemungkinan

6. Sepasang Kakek dan nenek memiliki 3 orang anak, semua anaknya sudah berkeluarga dan masing-masing memiliki satu orang anak. Pada hari raya mereka semua berkumpul.

a. Pada saat acara makan bersama mereka duduk mengelilingi hidangan di meja makan. Jika kakek selalu berdekatan dengan nenek serta setiap keluarga selalu duduk berdekatan, berapa banyak cara mereka duduk di meja makan tersebut?

Blok 1: Kakek dan Nenek

Blok 2, 3, 4: 3 keluarga dengan masing-masing 3 orang

Banyak cara mereka duduk di meja makan tersebut adalah

P_siklis(4) × 2! × 3! × 3! × 3! = 6 × 2 × 6 × 6 × 6 = 2592 cara.

b. Setelah acara makan bersama mereka duduk berjajar untuk menyaksikan film keluarga yang mereka suka, jika kakek dan nenek selalu duduk di pinggir dan setiap keluarga selalu duduk berdekatan, berapa banyak cara mereka duduk?

Posisi 1 dan 11 untuk kakek dan nenek, ada 2! = 2 cara.

Posisi 2 s/d 10 dibagi menjadi 3 blok, ada 3! = 6 cara.

Masing-masing blok terdiri dari 3 orang, ada 3! = 6 cara, karena ada 3 blok menjadi 6³ = 216 cara.

Banyak cara adalah 2 × 6 × 216 = 2592 cara.