Materi MatDis (Matematika Diskrit) : Permutasi dan Kombinasi

PERMUTASI Permutasi adalah jumlah urutan berbeda dari pengaturan objek-objek. Permutasi merupakan bentuk khusus aplikasi aturan perkalian. Misalkan jumlah objek adalah n, maka urutan pertama dipilih dari n objek, urutan kedua dipilih dari n – 1 objek, urutan ketiga dipilih dari n – 2 objek, begitu seterusnya dan urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian, permutasi dari n objek adalah n(n – 1) (n – 2) . . . (2)(1) = n! Menurut kaidah perkalian, ada sebanyak n(n – 1) (n – 2) . . . (n – (r – 1)) buah susunan berbeda dari penyusunan r objek yang dipilih dari n objek. Jumlah susunan berbeda dari pemilihan r objek yang diambil dari n objek disebut permutasi-r, dilambangkan dengan P(n, r), yaitu P(n, r) = n(n – 1)(n – 2). . . (n – (r – 1)) = n!/(n-r)! Menurut persamaan tersebut, jumlah cara memasukkan 6 buah bola yang berbeda warnanya ke dalam 3 buah kotak adalah P(6, 3) = 6!/(6 - 3)! = 120 dan jumlah kemungkinan urutan 2 dari 3 elemen himpunan A = {a, b, c} adalah P(3, 2) = 3!/(3 – 2)! = 6. Permutasi r dari n objek adalah jumlah kemungkinan urutan r buah objek yang dipilih dari n buah objek, dengan r ≤ n, yang dalam hal ini, pada setiap kemungkinan urutan tidak ada objek yang sama. Bila r = n, maka P(n, n) = n!/(n-n)! = n!/0! = n!/1 = n! Contoh : Berapa banyak “kata” yang terbentuk dari kata “BOSAN”? Penyelesaian : Anggap setiap huruf di dalam kata “BOSAN” sebagai bola yang berbeda warnanya dan 5 buah kotak yang akan diisi dengan 1 bola pada setiap kotak. Cara 1 : (5)(4)(3)(2)(1) = 120 buah kata Cara 2 : P(5, 5) = 5! = 120 buah kata Berapa banyak cara mengurutkan nama 25 orang mahasiswa? Penyelesaian : Analogikan dengan mengisi 25 kotak dengan 25 bola huruf berbeda, setiap kotak diisi dengan 1 bola. Jadi, jumlah cara pengurutan nama mahasiswa sama dengan jumlah susunan 25 bola ke dalam 25 kotak, yaitu P(25, 25) = 25! Tiga buah ujian dilakukan dalam suatu periode enam hari (Senin sampai Sabtu). Berapa banyak pengaturan jadwal yang dapat dilakukan sehingga tidak ada dua ujian atau lebih yang dilakukan pada hari yang sama. Penyelesaian : Cara 1 (dengan kaidah perkalian) : sama seperti menempatkan 3 bola (ujian) berbeda ke dalam enam kotak (hari). Ujian pertama dapat ditempatkan pada salah satu dari enam hari; Ujian kedua dapat ditempatkan pada salah satu dari lima hari; Ujian ketiga dapat ditempatkan pada salah satu dari empat hari; Jumlah pengaturan jadwal ujian = (6)(5)(4) = 120 Cara 2 (dengan rumus permutasi) : P(6, 3) = 6! / (6 – 3)! = 120 Sebuah bioskop mempunyai jajaran kursi yang disusun per baris. Tiap baris terdiri dari 6 tempat kursi. Jika dua orang akan duduk, berapa banyak pengaturan tempat duduk yang mungkin pada suatu baris? Penyelesaian : Orang pertama mempunyai 6 pilihan kursi dan orang kedua mempunyai 5 pilihan kursi. Jadi, jumlah pengaturan tempat duduk = (6)(5) = 30 atau P(6, 2) = 6! / 4! = (6)(5) = 30 cara Berapa banyak string yang dapat dibentuk yang terdiri dari 4 huruf berbeda dan diikuti dengan 3 angka yang berbeda pula? Penyelesaian : Ada P(26, 4) cara mengisi posisi 4 huruf dan P(10, 3) cara untuk mengisi posisi 3 buah angka. Karena string disusun oleh 4 huruf dan 3 angka, maka jumlah string yang dapat dibuat adalah P(26, 4) x P(10, 3) = 258.336.000 KOMBINASI Bentuk khusus dari permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan. Urutan acb, bca dan acb dianggap sama dan dihitung sekali. Secara umum, jumlah cara memasukkan r buah bola yang berwarna sama ke dalam n buah kotak adalah (n(n-1)(n-2)...(n-(r-1)))/r! = n!/r!(n-r)! Rumus n!/r!(n-r)! Disebut rumus kombinasi-r dan dilambangkan dengan C(n, r) atau (n¦r). Jadi, C(n, r) = n!/r!(n-r)! C(n, r) sering dibaca “n diambil r”, artinya r objek diambil dari n buah objek. Kombinasi r elemen dari n elemen adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen. Dapat juga dibuktikan dengan cara membentuk permutasi-r dari n elemen. Mula-mula hitung kombinasi-r , yaitu C(n , r), kemudian urutkan elemen-elemen di dalam setiap kombinasi-r. Pengurutan ini dapat dilakukan dengan P(r, r) cara. Dengan demikian, permutasi-r dari n elemen adalah P(n, r) = C(n, r) P(r, r) Dari persamaan di atas kita peroleh C(n, r) = (P(n,r))/(P(r,r)) = (n!/(n-r)!)/r!(r-r)! = n!/r!(n-r)! Contoh : Berapa banyak cara menyusun menu nasi goreng tiga kali seminggu untuk sarapan pagi? Penyelesaian : Bayangkan tiga kali menu nasi goreng sebagai tiga buah bola dan tujuh hari dalam seminggu sebagai 7 buah kotak. Persoalan ini sama dengan menempatkan 3 buah bola ke dalam 7 buah kotak. Banyaknya pengaturan jadwal menu nasi goreng adalah C(7, 3) = 7!/3!4! = 35 cara. String biner yang panjangnya 32 bit disusun oleh angka 1 atau 0. Berapa banyak string biner yang tepat berisi 7 buat bit 1? Penyelesaian : Analogikan 7 bit 1 sebagai 7 buah bola dan 32 posisi bit sebagai 32 buah kotak. Persoalan ini sama dengan memasukkan 7 bola ke dalam 32 kotak, sisanya kosong (0). Banyak string biner yang terbentuk adalah C(32, 7). Sebuah koin yang mempunyai sisi A dan sisi B dilempar ke atas sebanyak empat kali. Berapakah jumlah kemungkinan munculnya sisi A sebanyak tiga kali? Penyelesaian : Ini adalah persoalan dari kombinasi karena kita tidak mementingkan kapan sisi A tersebut muncul. Jadi, jumlah kemungkinan munculnya sisi A sebanyak tiga kali adalah C(4, 3) = 4. Tiga buah apartemen A, B dan C disewakan untuk mahasiswa. Tiap unit apartemen dapat menampung 3 atau 4 orang mahasiswa. Berapa jumlah cara menyewakan apartemen kepada 10 orang mahasiswa? Penyelesaian : Andaikan apartemen A, B, C ditempati masing-masing oleh 4, 3 dan 3 orang mahasiswa. Jumlah cara menyewakan = C(10, 4) x C(6, 3) x C(3, 3) Andaikan apartemen A, B, C ditempati masing-masing oleh 3, 4 dan 3 orang mahasiswa. Jumlah cara menyewakan = C(10, 3) x C(7, 4) x C(3, 3) Andaikan apartemen A, B, C ditempati masing-masing oleh 3, 3 dan 4 orang mahasiswa. Jumlah cara menyewakan = C(10, 3) x C(7, 3) x C(4, 4) Total seluruh cara menyewakan = C(10, 4)C(6, 3) + C(10, 3)C(7, 4) + C(10, 3)C(7, 3) = 3C(10, 4)C(6, 3). PERMUTASI DAN KOMBINASI BENTUK UMUM P(n;n_1,n_2, ... , n_k) = (P(n,n))/(n_1 !n_(2!…n_k !) ) = n!/(n_1 !n_(2!…n_k !) ) Persamaan ini diterapkan untuk menghitung pengaturan (atau pengurutan) n buah objek dari himpunan ganda S (himpunan S terdiri dari n buah objek yang tidak perlu semuanya berbeda). Persamaan tersebut dinamakan permutasi bentuk umum (generalized permutation) terhadap S. C(n;n_1,n_2, ... , n_k) = C(n, n_1) C(n - n_1, n_2) C(n - n_1 - n_2, n_3) . . . C(n - n_1 - n_2 - . . . - n_(k-1), n_k) = n!/(n_(1 ) !(n- n_1 )!) (n-n_(1 ) )!/(n_2 !(n- n_1- n_2 )!) (n- n_1- n_2 )!/(n_3 !(n- n_1- n_2- n_k )!) . . . ((n- n_1- n_2- n_(k-1) )! )/(n_k !(n- n_1- n_2-…- n_(k-1)- n_k )!) = n!/(n_1 !n_(2!…n_k !) ) Persamaan ini dinamakan kombinasi bentuk umum (generalized combination). Kita dapat melihat bahwa tidak ada perbedaan antara permutasi bentuk umum dengan kombinasi bentuk umum. Keduanya dapat dihitung dengan rumus yang sama. Jadi, apabila S adalah himpunan ganda dengan n buah objek yang di dalamnya terdiri atas k jenis objek berbeda dan tiap objek memiliki multiplisitas n_1, n_2, . . ., n_k (jumlah objek seluruhnya n_1 + n_2 + . . . + n_k = n), maka jumlah cara menyusun seluruh objek adalah : P(n;n_1,n_2, ... , n_k) = C(n;n_1,n_2, ... , n_k) = n!/(n_1 !n_(2!…n_k !) ) Contoh : 12 lembar karton akan diwarnai sehingga 3 diantaranya berwarna hijau, 2 berwarna merah, 2 berwarna kuning dan sisanya berwarna biru. Berapa jumlah cara pengecatan? Penyelesaian : Diketahui n_1 = 3, n_2 = 2, n_3 = 2, n_4 = 5 dan n_(1 )+ n_2 + n_3 + n_4 = 3 + 2 + 2 + 5 = 12 Jumlah cara pengecatan = P(12; 3, 2, 2, 5) = (P(12,12))/((3!)(2!)(2!)(5!)) = 12!/((3!)(2!)(2!)(5!)) = 166320 cara 12 buah lampu berwarna (4 merah, 3 putih dan 5 biru) dipasang pada 18 buah soket dalam sebuah baris (sisanya 6 buah soket dibiarkan kosong). Berapa jumlah cara pengaturan lampu? Penyelesaian : Diketahui, n = 18; n_1 = 4, n_2 = 3, n_3 = 5 dan n_(4 )= 6 (socket kosong) Jumlah cara pengaturan lampu = P(18; 4, 3, 5, 6) = 18!/((4!)(3!)(5!)(6!)) cara Berapa banyak cara membagikan delapan buah buku berbeda kepada 3 orang mahasiswa, bila Billy mendapat empat buah buku dan Andi serta Toni masing-masing memperoleh 2 buah buku. Penyelesaian : Diketahui n = 8, n_1 = 4, n_2 = 2, n_3 = 2 dan n_(1 )+ n_2 + n_3 = 4 + 2 + 2 = 8 Jadi, jumlah cara membagi seluruh buku = 8!/((4!)(2!)(2!)) = 420 cara KOMBINASI DENGAN PENGULANGAN Tinjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak. Jika masing – masing kotak hanya boleh diisi paling banyak satu buah bola, maka jumlah cara memasukkan bola ke dalam kotak adalah C(n, r). Jika masing -masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan bola ke dalam kotak adalah C(n + r – 1, r). C(n + r – 1, r) adalah jumlah kombinasi yang membolehkan adanya pengulangan elemen, yaitu dari n buah objek kita akan mengambil r buah objek, dengan pengulangan diperbolehkan. Pembuktian rumus kombinasi dengan pengulangan tidak disertakan di sini. Perhatikan bahwa C(n + r – 1, r) = C(n + r – 1, n – 1). Contoh : Toko roti ”Enak” menjual 8 jenis roti. Berapa jumlah cara mengambil 1 lusin roti (1 lusin = 12 buah) Penyelesaian : Analogikan 8 jenis roti sebagai 8 kotak. Kita akan mendistribusikan 12 roti itu ke dalam 8 kotak. Setiap kotak mungkin berisi lebih dari 1 buah roti. Di sini n = 8 dan r = 12, maka jumlah cara memilih 12 buah roti itu sama dengan jumlah cara memasukkan 12 buah roti ke dalam 8, yaitu sebanyak C(8 + 12 – 1, 12) = C(19, 12) cara. Andaikan terdapat kumpulan bola yang berwarna merah, biru dan hijau. Jumlah bola dari masing – masing warna paling sedikit jumlahnya 8 buah. Berapa banyak cara memilih 8 buah bola (tanda ada batasan warna)? Berapa banyak cara memilih 8 buahbola jika paling sedikit 1 bola dari masing – masing warna terwakili? Penyelesaian : n = 3, r = 8, maka C(n + r – 1, r) = C(3 + 8 – 1, 8) = C(10, 8) = 45 Ambil terlebih dulu 1 bola dari masing – masing warna, kemudian ambil 5 boal sisanya. Jumlah cara seluruhnya adalah C(3 + 5 – 1, 5) = C(7, 5) = 21 cara. Tiga buah dadu dilempar bersamaan. Berapa banyaknya hasil berbeda yang mungkin? Penyelesaian : C(6 + 3 – 1, 3) = C(8, 3) = 56.