permutasi

KELOMPOK

Mutmainah R Indriani ( 11305144002 / Matswa 2011 )

Riska Lutfia ( 11305144008 / Matswa 2011 )

Yohanes Rio Sapto H (11305144040 / Matswa 2011)

PENDAHULUAN

I. PENDAHULUAN

Permutasi dan kombinasi merupakan suatu analisis yang mempunyai peranan

penting dalam matematika modern, khususnya dalam menentukan banyaknya alternatif

yang mungkin terjadi di dalam pengambilan keputusan.

Dalam berapa macam carakah suatu peristiwa dapat terjadi? Dalam berapa

macam carakah 5 orang dapat duduk berjajar dalam suatu deretan di atas sebuah

bangku panjang?

Pertanyaan-pertanyaan yang demikian itu sering kali kita jumpai dalam

persoalan tentang cara menghitung berbagai kemungkinan memilih, yang pada

dasarnya sama dengan persoalan mencari jumlah alternatif cara menyusun (mengatur)

suatu kelompok obyek tertentu.

Persoalan di atas dalam matematika/statistika biasa disebut Permutasi dan

Kombinasi. Dalam pembahasan mengenai Permutasi dan Kombinasi ini, pertama-tama

yang perlu diketahui adalah pengertian mengenai Factorial yang secara sistematis diberi

notasi tanda seru (!). Harga dari suatu bilangan yang difactorialkan diformulasikan

sebagai berikut :

n ! = n (n-1) (n-2) (n-3) ……….{n-(n-1)}

atau :

n ! = 1 x 2 x 3 ……….x n

Catatan : 0 ! = 1 ! = 1

Contoh : 3 ! = 1 x 2 x 3 = 6

5 ! = 1 x 2 x 3 x 4 x 5 = 120

10 ! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 = 3.628.800

Sebuah sandi-lewat (password) panjangnya 6 sampai 8 karakter. Karakter boleh berupa

huruf atau angka. Berapa banyak kemungkinan sandi-leawt yang dapat dibuat?

abcdef

KELOMPOK




aaaade

a123fr

…

erhtgahn

yutresik

…

????

Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan

objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.

Kaidah Dasar Menghitung

1. Kaidah perkalian (rule of product)

Misalkan,

Percobaan 1: p hasil

Percobaan 2: q hasil

maka,

Percobaan 1 dan percobaan 2: p ´ q hasil

2. Kaidah penjumlahan (rule of sum)

Misalkan,

Percobaan 1: p hasil

Percobaan 2: q hasil

maka,

Percobaan 1 atau percobaan 2: p + q hasil

Contoh. Ketua angkatan IF 2002 hanya 1 orang (pria atau wanita, tidak bias gender).

Jumlah pria IF2002 = 65 orang dan jumlah wanita = 15 orang. Berapa banyak cara

memilih ketua angkatan?

Penyelesaian:

65 + 15 = 80 cara.

KELOMPOK




Contoh. Dua orang perwakilan IF2002 mendatangai Pak Rinaldi untuk protes nilai kuis.

Wakil yang dipilih 1 orang pria dan 1 orang wanita. Berapa banyak cara memilih 2 orang

wakil tersebut?

Penyelesaian:

65 ´ 15 = 975 cara.

Perluasan Kaidah Dasar Menghitung

Misalkan ada n percobaan, masing-masing dg pi hasil

1. Kaidah perkalian (rule of product)

p1 ´ p2 ´ … ´ pn hasil

2. Kaidah penjumlahan (rule of sum)

p1 + p2 + … + pn hasil

Contoh. Bit biner hanya 0 dan 1. Berapa banyak string biner yang dapat dibentuk jika:

(a) panjang string 5 bit

(b) panjang string 8 bit (= 1 byte)

Penyelesaian:

(a) 2 ´ 2 ´ 2 ´ 2 ´ 2 = 25 = 32 buah

(b) 28 = 256 buah

Contoh. Berapa banyak bilangan ganjil antara 1000 dan 9999 (termasuk 1000 dan 9999

itu sendiri) yang

(a) semua angkanya berbeda

(b) boleh ada angka yang berulang.

Penyelesaian:

(a)

posisi satuan: 5 kemungkinan angka (yaitu 1, 3, 5, 7 dan 9);

posisi ribuan: 8 kemungkinan angka

posisi ratusan: 8 kemungkinan angka

posisi puluhan: 7 kemungkinan angka

Banyak bilangan ganjil seluruhnya = (5)(8)(8)(7) = 2240 buah.

KELOMPOK




(b)

posisi satuan: 5 kemungkinan angka (yaitu 1, 3, 5, 7 dan 9);

posisi ribuan: 9 kemungkinan angka (1 sampai 9)

posisi ratusan: 10 kemungkinan angka (0 sampai 9)

posisi puluhan: 10 kemungkinan angka (0 sampai 9)

Banyak bilangan ganjil seluruhnya = (5)(9)(10)(10) = 4500

Contoh. Lihat kembali contoh ilustrasi pada awal bab ini. Sandi-lewat (password)

sistem komputer panjangnya enam sampai delapan karakter. Tiap karakter boleh

berupa huruf atau angka; huruf besar dan huruf kecil tidak dibedakan. Berapa banyak

sandi-lewat yang dapat dibuat?

Penyelesaian:

Banyaknya huruf alfabet adalah 26 (A-Z) dan banyak angka desimal adalah 10 (0-9),

jadi seluruhnya 36 karakter.

Untuk sandi-lewat dengan panjang 6 karakter, jumlah kemungkinan sandi-lewat adalah

(36)(36)(36)(36)(36)(36) = 366 = 2.176.782.336

untuk sandi-lewat dengan panjang 7 karakter, jumlah kemungkinan sandi-lewat adalah

(36)(36)(36)(36)(36)(36)(36) = 367 = 78.364.164.096

dan untuk sandi-lewat dengan panjang 8 karakter, jumlah kemungkinan sandi-lewat

adalah

(36)(36)(36)(36)(36)(36)(36)(36) = 368 = 2.821.109.907.456

Jumlah seluruh sandi-lewat (kaidah penjumlahan) adalah

2.176.782.336 +

78.364.164.096 +

2.821.109.907.456 = 2.901.650.833.888 buah.

KELOMPOK




II. PERMUTASI

1. Permutasi dari n obyek tanpa pengembalian

(a). Permutasi dari n obyek seluruhnya

Permutasi dari n obyek seluruhnya tanpa pengembalian dirumuskan :

n P n = n !

Contoh soal :

Pada suatu tempat terdapat 4 buku matematika yang berbeda, 3 buku statistik yang

berbeda, dan 2 buku akuntansi. Semua buku akan disusun pada sebuah rak buku.

Berapa cara susunan yang mungkin dari kejadian berikut ini?

a. Buku-buku matematika dapat disusun.

b. Buku-buku statistik dapat disusun.

c. Buku-buku akuntansi dapat disusun.

d. Ketiga kelompok buku itu dapat disusun.

Penyelesaian :

a. Buku-buku matematika dapat disusun dalam :

4P4 = 4 ! = 4 x 3 x 2 x 1 = 24 cara

b. Buku-buku statistik dapat disusun dalam :

3P3 = 3 ! = 3 x 2 x 1 = 6 cara

c. Buku-buku akuntansi dapat disusun dalam :

2P2 = 2 ! = 2 x 1 = 2 cara

d. Ketiga kelompok buku dapat disusun dalam :

3P3 = 3 ! = 3 x 2 x 1 = 6 cara

(b). Permutasi sebanyak r dari n obyek

Permutasi sebanyak r dari n obyek tanpa pengembalian dirumuskan :

n P r = (n ≠ r)

Permutasi r dari n elemen

KELOMPOK




Ada enam buah bola yang berbeda warnanya dan 3 buah kotak. Masing-masing kotak

hanya boleh diisi 1 buah bola. Berapa jumlah urutan berbeda yang mungkin dibuat dari

penempatan bola ke dalam kotak-kotak tersebut?

Penyelesaian:

kotak 1 dapat diisi oleh salah satu dari 6 bola (ada 6 pilihan);

kotak 2 dapat diisi oleh salah satu dari 5 bola (ada 5 pilihan);

kotak 3 dapat diisi oleh salah satu dari 4 bola (ada 4 pilihan).

Jumlah urutan berbeda dari penempatan bola = (6)(5)(4) = 120

Bola:

m b p h k j

Kotak:

1 2 3

Perampatan:

Ada n buah bola yang berbeda warnanya dan r buah kotak (r £ n), maka

kotak ke-1 dapat diisi oleh salah satu dari n bola (ada n pilihan) ;

kotak ke-2 dapat diisi oleh salah satu dari (n - 1) bola (ada n – 1 pilihan);

kotak ke-3 dapat diisi oleh salah satu dari (n - 2) bola (ada n – 2) pilihan;

kotak ke-r dapat diisi oleh salah satu dari (n - (r - 1)) bola (ada n – r + 1 pilihan);

Jumlah urutan berbeda dari penempatan bola adalah:

n(n - 1)(n - 2)…(n - (r - 1))

Contoh soal :

KELOMPOK




Dari 4 calon pimpinan sebuah perusahaan, misalkan A, B, C, dan D hendak dipilih

seorang ketua, seorang sekretaris, dan seorang bendahara. Berapa cara keempat calon

tersebut dipilih?

Penyelesaian :

4P3 = = = 24

(c). Permutasi melingkar

Sejumlah obyek yang berbeda dapat disusun secara teratur dalam suatu lingkaran

dalam:

P = (n – 1) ! cara.

Contoh soal :

Sebuah kelompok orang yang terdiri dari 4 orang mengelilingi sebuah meja bundar.

Dalam berapa cara keempat orang itu dapat diatur sekeliling meja tersebut?

Penyelesaian :

P = (n – 1) ! = (4 – 1) ! = 3 ! = 3 x 2 x 1 = 6 cara

2. Permutasi dari n obyek dengan pengembalian

Permutasi dari n obyek dengan pengembalian dirumuskan :

n P*r = n

r ≤ n dan bilangan bulat positif

Contoh soal :

Tentukan permutasi dari ABC sebanyak 2 unsur dengan pengembalian unsur yang

terpilih!

Penyelesaian :

3P*2 = 3 = 9

Yaitu : AA, AB, AC, BB, BA, BC, CC, CA, CB

3. Permutasi dari n obyek yang sama

Permutasi dari n obyek yang sama dirumuskan :

n P n , n , n ………. =

r

KELOMPOK




dengan n + n + n + ……… = n

Contoh soal :

-Tentukan permutasi dari kata “TAMAT”!

Penyelesaian :

n = 5 ; n = 2 ; n = 2 ; n = 1

5 P 2,2,1 = = = 30

- 4 bola putih, 5 bola kuning, dan 2 bola hitam disusun dalam satu baris. Jika semua

bola yang berwarna sama tidak dibedakan satu sama lain, berapa carakah penyusunan

yang mungkin.

Penyelesaian :

n = 11 ; n1 = 4 ; n2 = 5 ; n3 = 2

11 P 4,5,2 =

PERMUTASI

1). Permutasi dari n obyek 2). Permutasi dari n obyek 3). Permutasi dari n obyek

tanpa pengembalian dengan pengembalian yang sama

r ≤ n & bilangan bulat +

a. Permutasi dari n obyek seluruhnya

n Pn1 ,n2 ,n3 =

n !n1 !n2 ! n3 !

KELOMPOK




b. Permutasi sebanyak r dari obyek n

c. Permutasi melingkar

Referensi Modul Matematika Diskrit Ir. Rinaldi

n Pn = n!

n Pr =

n !(n−r ) !

P = (n-1) !

permutasi

Documents