Download - 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
Mutmainah R Indriani ( 11305144002 / Matswa 2011 )
Riska Lutfia ( 11305144008 / Matswa 2011 )
Yohanes Rio Sapto H (11305144040 / Matswa 2011)
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
Mutmainah R Indriani ( 11305144002 / Matswa 2011 )
Riska Lutfia ( 11305144008 / Matswa 2011 )
Yohanes Rio Sapto H (11305144040 / Matswa 2011)
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
Mutmainah R Indriani ( 11305144002 / Matswa 2011 )
Riska Lutfia ( 11305144008 / Matswa 2011 )
Yohanes Rio Sapto H (11305144040 / Matswa 2011)
(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
Mutmainah R Indriani ( 11305144002 / Matswa 2011 )
Riska Lutfia ( 11305144008 / Matswa 2011 )
Yohanes Rio Sapto H (11305144040 / Matswa 2011)
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
Mutmainah R Indriani ( 11305144002 / Matswa 2011 )
Riska Lutfia ( 11305144008 / Matswa 2011 )
Yohanes Rio Sapto H (11305144040 / Matswa 2011)
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
Mutmainah R Indriani ( 11305144002 / Matswa 2011 )
Riska Lutfia ( 11305144008 / Matswa 2011 )
Yohanes Rio Sapto H (11305144040 / Matswa 2011)
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
Mutmainah R Indriani ( 11305144002 / Matswa 2011 )
Riska Lutfia ( 11305144008 / Matswa 2011 )
Yohanes Rio Sapto H (11305144040 / Matswa 2011)
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
Mutmainah R Indriani ( 11305144002 / Matswa 2011 )
Riska Lutfia ( 11305144008 / Matswa 2011 )
Yohanes Rio Sapto H (11305144040 / Matswa 2011)
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) !