Loading Preview
Sorry, preview is currently unavailable. You can download the paper by clicking the button above.
DESCRIPTION
permutasi dan kombinasi
Transcript
TUGAS
Diajukan untuk Memenuhi Salah Satu Tugas pada Mata Kuliah
Introduction Discrete Math
Disusun Oleh:
Jumalia 1311441028
PRODI PENDIDIKAN MATEMATIKA KELAS INTERNASIONAL
JURUSAN MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS NEGERI MAKASSAR
2015
A. Permutasi
Diberikan sebanyak n objek berbeda. Sebuah permutasi k dari n objek tersebut adalah
sebuah jajaran dari k objek yang urutannya diperhatikan. Misalnya, diberikan tiga objek
berbeda, katakana a,b, dan c. jajaran seperti ab adalah sebuah permutasi-2 dari tiga objek
tersebut. Begitu juga jajaran seperti ba merupakan sebuah permutasi-2 dari tiga objek tersebut.
Jika perulangan tidak diperkenankan, artinya objek-objek dalam jajaran tersebut tidak boleh
sama, maka terdapat 6 permutasi-2 yang mungkin, yaitu : ab, ac, ba, bc, ca, cb. Jika perulangan
diperbolehkan maka jajaran seperti aa juga merupakan sebuah permutasi-2 dari tiga objek
tersebu; begitu juga dengan bb dan cc. Dengan demikian, jika perulangan diperbolehkan, maka
terdapat 9 permutasi-2 yang mungkin. Selanjutnya, banyaknya permutasi-k dari n objek
berbeda, tanpa pengulangan disimbolkan dengan P(n,k). Sedangkan, p*(n,k) menyatakan
banyaknya permutasi-k dari n objek berbeda, dengan pengulangan. Dari uraian diatas diperoleh
P(3,2) = 6 dan P*(3,2) = 9.
Jika n sebuah bilangan bulat positif, maka 1x2x3xx n = n!. Jika n = 0, definisikan n!=0!=1.
Teorema 1.1:
Jika n dan k dua bilangan bulat positif, maka P*(n,k) = nk ; dan P(n,k) = !
()!, untuk k .
Bukti:
Misalkan O1,O2,O3, , On adalah objek berbeda. Pikirkan akan dijajar secara linear
sebanyak k objek dari n objek tersebut. Misalkan pengulangan tidak diperkenankan. Terdapat
n cara memilih objek pertama ( mungkin O1, atau mungkin O2, dan seterusnya, mungkin On)
jika satu objek telah terpilih dan diletakkan pada posisi pertama dalam jajaran, maka ada (n-1)
cara untuk memilih satu objek untuk diletakkan pada posisi kedua tidak boleh sama dengan
objek pada posisi pertama. Begitu juga terdapat (n-2) cara untuk memilih objek yang tersisa
untuk diletakkan pada posisi ketiga, dan seterusnya, akhirnya terdapat n-(k-1) cara memilih
objek tersisa untuk diletakkan pada posisi ke-k dalam jajaran. Berdasarkan aturan perkalian,
diperoleh
P(n,k) = n(n-1)(n-2) (n-(k-1)
=()()(())()!
()!
=!
()!
Jika pengulangan diperkenankan, maka terdapat n cara memilih satu objek untuk diletakkan
pada setiap posisi dari k posisi dalam jajaran tersebut. Sehingga, berdasarkan aturan perkalian,
banyaknya jajaran-k yang mungkin adalah
P*(n,k) = n x n x n x x n (sebanyak k factorial) = nk
Dengan demikian teorema terbukti.
Perhatikan bahwa, untuk k = n, sebagai akibat langsung dari teorema diatas, diperoleh
P(n,n) = !
()!=
!
! (, ) =
Contoh 1.4:
a. Dari 10 mahasiswa akan dibentuk sebuah tim beranggotakan 4 orang berbeda terdiri
dari satu ketua, satu sekretaris, dan satu bendahara. Ada berapa tim yang mungkin
terbentuk ?
Penyelesaian: dalam hal ini urutan diperhatikan. Karena n = 10, k = 4, dan 4 orang
dalam tim berbeda, maka banyaknya tim yang mungkin terbentuk adalah
(10,4) =10!
(10 4)!=
10!
6!= 10 . 9 . 8 . 7 = 5040
b. Ada berapakah barisan binair 5 angka ?
Penyelesaian:
Barisan binair dibentuk dari n = 2 angka berbeda yaitu 0 dan 1. Karena barisan
Binair 5 angka maka dalam hal ini k = 5. Selanjutnya, karena angka-angka dalam
barisan tersebut tidak harus berbeda, maka banykanya barisan binair adalah
(2,5) = 25 = 32.
Perhatikan bahwa dalam permutasi yang dibicarakan diatas, objek-objek dijajar dalam
satu garis. Permutasi yang demikian disebut permutasi linear. Jika objek objek tersebut dijajar
melingkar (pada suatu lingkaran) dan arah melingkarnya diperhatikan, misalnya searah putaran
jarum jam, maka permutasi yang demikian disebut permutasi siklik. Misalkan tiga objek 1, 2,
dan 3 secara terurut dijajar melingkar menurut putaran jarum jam, maka akan diperolah sebuah
permutasi siklik. Selanjutnya permutasi siklik tersebut ditulis (123). Dua permutasi siklik
dikatakan ekuivalen(sama) jika yang satu dapat diperoleh dari yang lain putaran. Misalnya,
permutasi siklik (123) ekuivalen dengan permutasi siklik (231) dan (312). Jadi dari tiga buah
permutasi linear 123,231, dan 312 diperoleh hanya satu buah permutasi siklik (123). Begitu
juga dari tiga permutasi linear 132,321, dan 213 diperoleh hanya satu permutasi siklik yaitu,
(132) = (321) = (213). Dengan demikian terdapat dua buah permutasi-3 siklik dari 3 objek 1,
2, dan 3 yaitu (123) dan (132).
Mudah ditunjukkan bahwa terdapat hanya enam buah permutasi-4 siklik dari 4 objek
1,2,3, dan 4, yaitu; (1234), (1243), (1324), (1342), (1423), dan (1432). Perhatikan bahwa dari
setiap permutasi-4 siklik tersebut terdapat 4 permutasi linear. Sehingga seluruhnya terdapat
6 x 4 = 24 permutasi linear. Secara umum, jika pengulangan tidak diperkenankan, hubungan
antara banyaknya permutasi siklik dan banyaknya permutasi linear disajikan dalam teorema
berikut.
Teorema 1.2
Jika PS(n,k) menyatakan banyak permutasi-k siklik dari n objek berbeda maka
PS(n,k) = =(,)
!=
!
()! , (, ) = ( )!
Bukti :
Karena dari setiap permutasi-k siklik terdapat k buah permutasi-k linear, maka
berdasarkan aturan perkalian diperoleh
PS(n,k) x k = P(n,k), ekuivalen dengan PS(n,k) x k = (,)
Berdasarkan teorema 1.1 diperoleh PS(n,k) = !
() =
(, ) =!
.!=
()!
= ( )!
Dengan demikian teorema terbukti.
Catatan:
Jika arah putaran tidak dibedakan, artinya memutar searah ataupun berlawanan arah putaran
jarum jam tidak dibedakan maka permutasi siklik (12345) ekuivalen dengan permutasi siklik
(15432), ditulis permutasi siklik [15432], seperti terlihat pada diagram berikut.
Demikian juga, permutasi siklik (12453) ekuivalen dengan permutasi siklik (13542). Jika
PS*(n,k) menyatakan banyak permutasi-k siklik dari n objek, tanpa memperhatikan arah
putaran, maka
PS*(n,k) = (,)
=
!
()!
Contoh:
Dari seratus manik-manik berlabel 1,2,3, , 30 akan dibuat sebuah kalung yang terdiri dari
25 manik-manik berbeda. Maka banyka kalung yang mungkin terbentuk adalah
PS(30,25) = !
()()!=
!
()=
!
1
2
34
51
2
34
5
1
2
34
5
B. KOMBINASI
Diberikan sebanyak n objek berbeda. Sebuah kombinasi-k dari n objek tersebut adalah sebuah
jajaran dari k yang urutannya tidak diperhatikan. Misalkan, dari 4 objek berbeda a, b, c, dan d,
jika pengulangan diperbolehkan, dapat dibentuk sebanyak empat kombinasi-3 yang berbeda
yaitu : abc, abd, acd, dan bcd. Perhatikan kombinasi abc dan kombinasi bca dianggap sama,
karena dalam kombinasi urutan objek tidak diperhatikan. Jika perulangan diperbolehkan, maka
terdapat sebanyak 20 kombinasi-3 yang dapat dibentuk yaitu : abc, abd, acd, bcd, aab, aac, aad,
aaa, bba, bbc, bbd, bbb, cca, ccb, ccd, ccc, dda, ddb, ddc, ddd. Banyaknya kombinasi-k dari n
objek berbeda disimbolkan dengan C(n,k), jika pengulangan tidak diperbolehkan, dan C*(n,k),
jika pengulangan diperbolehkan. Dari uraian diatas diperoleh C(4,3) = 4 dan C*(4,3) = 20.
TEOREMA 1.2
Misalkan n dan k bilangan bulat non negative dengan k n. Banyaknya kombinasi-k
dari n objek berbeda, tanpa pengulangan, adalah C(n,k) =!
!()!.
Bukti:
Karena untuk setiap kombinasi-k dari n objek dapat dibentuk sebanyak P(k,k)
permutasi-k dari n objek, maka dari aturan perkalian diperoleh P(k,k) C(n,k) = P(n,k).
Berdasarkan Teorema 1.1 diperoleh
C(n,k) = (,)
(,)!=
(,)
!=
!
!()!
Dengan demikian teorema terbukti.
Contoh 1.6:
a. Dari 10 mahasiswa akan dipilih 6 orang sebagai tim bola-volly. Ada berapa tim yang
mungkin terbentuk ?
Penyelesaian:
Karena dalam tim bola volley, urutan pemain tidal diperhatikan, maka persoalan
tersebut terkait dengan persoalan kombinasi. Dalam hal ini n = 10 dan k = 6, sehingga
banyaknya tim yang mungkin terbentuk adalah
C(10,6) =!
!()!=
b. Sebuah kotak berisikan 5 bola merah dan 10 bola putih. Ada berapa cara mengambil 6
bola sedemikian hingga dari bola-bola yang terambil tersebut terdapat: (a) tepat 2 bola
merah?;(b) paling banyak 2 bolah merah?; (c) bola merah ?
Penyelesaian:
a. Dari 6 bola yang terambil terdapat 2 bolah merah dan 4 bola putih. Untuk mengambil
2 bola merah dari 5 bola merah yang ada dalam kotak terdapat C(5,2) = !
!!=
dan untuk mengambil 4 bolah putih dari 10 bola putih yang ada dalam kotak
terdapat C(10,4) = !
!!= cara. Karena setiap mengambil 2 bola merah selalu
diikuti dengan pengambilan 4 bolah putih, berdasarkan aturan perkalian, banyaknya
cara yang dimaksud adalah C(5,2) x C(10,4) = 10 x 210 = 2100.
b. Untuk memperoleh paling bamyak 2 bola merah dari 6 bola merah yang diambil dari
kotak terdapat tiga kemungkinan yaitu : 2 bola merah dan 4 bola putih, atau 1 bola
merah dan 5 bolah putih, atau 6 bolah putih. Berdasarkan aturan perkalian, untuk
mengambil 2 bola merah dan 4 bola putih terdapat C(5,2) x C(10