Matematika Diskrit

PERMUTASI DAN KOMBINASI

If you can DREAM it, you CAN DO IT...!!!

- Walt Disney

Matematika Diskrit merupakan mata kuliah dasar yang berisi dasar-dasar logika matematika yang diperlukan untuk pembelajaran lebih lanjut di bidang Ilmu Komputer. Mata kuliah ini diajarkan pada semester awal dengan beban 2 sks. Dan salah satu tuntutan materi yang harus dikuasai mahasiswanya adalah materi Permutasi dan Kombinasi yang akan di bahas lebih lanjut saat ini.

I. Permutasi

Di dalam ilmu matematika permutasi diartikan sebagai sebuah konsep penyusunan sekumpulan objek/angka menjadi beberapa urutan berbeda tanpa mengalami pengulangan.

Di dalam permutasi, urutan sangat diperhatikan. setiap objek yang dihasilkan harus berbeda antara satu dengan yang lain. kita ambil contoh, urutan huruf ({ABC} berbeda dengan {CAB} begitu juga dengan {BAC) dan {ACB}). Berikut di bawah akan dijelaskan pula jenis-jenis permutas.

1.1 Jenis-jenis Permutasi

a.     Permutasi dari n elemen, setiap permutasi terdiri dari n elemen

Jika ada unsur yang berbeda diambil n unsur, maka banyaknya susunan (permutasi) yang berbeda dari n unsur tersebut adalah P_(n,n) = n! atau _nP_n = n!

Contoh:

Untuk menyambut sebuah pertemuan delegasi negara yang dihadiri oleh lima negara, panitia akan memasang kelima bendera dari lima negara yang hadir. Banyak cara panitia menyusun kelima bendera tersebut adalah...

Jawab :

Dari lima bendera yang ada, berarti n = 5, maka banyak susunan bendera yang mungkin yaitu:

5! = 5.4.3.2.1 = 120 cara.

b.   Permutasi n elemen, tiap permutasi tersendiri dari r unsur dari n elemen dengan r<=n 

Syarat : Urutan di perhatikan

Contoh:

Banyak cara untuk memilih seorang ketua, sekertaris dan bendahara dari 8 siswa yang tersedia adalah…

Jawab:

Banyak siswa, n = 8

Ketua, sekretaris dan bendahara (banyak pilihan objek), r = 3

Maka:

c.      Permutasi dari n unsur yang mengandung p, q, dan r unsur yang sama

Keterangan:

n    = banyaknya elemen seluruhnya

k₁  = banyaknya elemen kelompok 1 yang sama

k₂  = banyaknya elemen kelompok 2 yang sama

…

k_t   = banyaknya elemen kelompok kt yang sama

t = 1,2,3,…

Contoh:

Banyak cara untuk menyusun dari kata ”BASSABASSI” adalah…

Jawab:

Dari kata ”BASSABASSI”, banyak huruf (n) = 10

k₁ = huruf B = 2

k₂ = huruf A = 3

k₃ = huruf S = 4

k₄ = huruf I = 1

d.      Permutasi Siklis

Permutasi siklis adalah permutasi melingkar (urutan melingkar).

Contoh:

Dari 5 orang anggota keluarga akan duduk mengelilingi sebuah meja bundar, banyak cara susunan yang dapat dibuat dari 5 orang tersebut adalah...

Jawab:

Banyak orang (n) = 5, maka :

₅P_siklis = (5 – 1)! = 4! = 4.3.2.1 = 24 cara.

e.      Permutasi berulang dari n unsur, tipe permutasi terdiri dari k unsur

Contoh:

Banyak susunan 3 bilangan dari angka-angka 1, 2, 3, 4, 5 dan 6 adalah…

Jawab:

Banyak susunan 3 bilangan, berarti bilangan ratusan, k = 3
Banyak angka yang akan disusun, n = 6
Banyak susunan 3 bilangan dari angka 1, 2, 3, 4, 5, dan 6:

P₆ = 6³ = 216 susunan.

II. Kombinasi

Kombinasi merupakan sebuah kumpulan dari sebagian atau seluruh objek dengan tidak memperhatikan urutannya. di dalam kombinasi, {AB} dianggap sama dengan {BA} sehingga sebuah kombinasi dari dua objek yang sama tidak dapat terulang.

Rumus Kombinasi :

Contoh

Manuel Pelegrini membawa 16 pemain saat Manchester City melawan Liverpool di Etihad Stadium. 11 orang diantaranya akan dipilih untuk bermain pada babak pertama. jika kita tidak memperhatikan posisi pemain, berapakah banyaknya cara yang dapat diambil oleh pelatih untuk memilih pemain?

Jawab :

Karena tidak mementingkan posisi pemain, maka kita gunakan rumus kombinasi:

¹⁶C₁₁ =       16!        =  16 x 15 x 14 x 13 x 12 x 11!  

              11!(16-11)!                      11!5!                          

      =          524160         =  524160  = 4368

     5 x 4 x 3 x 2 x 1          120

III. Perbedaan Permutasi dan Kombinasi

Perbedaan antara permutasi dan kombinasi adalah permutasi memperhatikan urutan susunan anggota sedangkan kombinasi tidak memperhatikan urutan susunan anggota. Hal ini dapat dilihat dari kedua contoh diatas, yaitu permutasi dan kombinasi dari 2 anggota dari himpunan yang terdiri dari huruf a, b, dan c.

P(3,2) = 6 Keenam cara tersebuat adalah: ab, ac, ba, bc, ca, cb.

C(3,2) = 3 Ketiga cara tersebuat adalah: ab, ac, bc.