Kajian teori pemasangan dalam perluasan permutasi dan kombinasi

ABSTRAK

Dalam Matematika Diskrit diperlukan suatu perhitungan untuk menentukan susunan banyaknya objek dalam suatu tempat. Salah satu metode yang digunakan dalam perhitungan tersebut adalah permutasi dan kombinasi. Metode ini dapat menunujukkan banyaknya suatu susunan yang dapat dibentuk dari suatu kumpulan objek yang berbeda dalam suatu tempat, baik yang dipilih seluruhnya atau sebagian.

Dalam permutasi, urutan unsur yang disusun sangat diperhatikan, jadi permutasi abc dab cab adalah dua permutasi yang berbeda. Kombinasi kebalikannya, jadi dua permutasi yang menandung unsur-unsur yang sama didefinisikan sebagai suatu kombinasi.

Peluasan permutasi dan kombinasi:
(i) apabila terdapat beberapa unsur yang sama, (ii) semua unsumya sama, dan (iii) kelompok unsur yang dapat disamakan. Misalkan n adalah unsur-unsur yang berbeda, disusun menurut besaran dan aturan tertentu. Misakan pula besaran tertentu itu r dan r£ n, maka banyaknya susunan dinyatakan dengan P(n,r)
p(n,r)=r(n-1 )(n-2)... (n-r+ 1)
a)Tetapi jiks Fn maka rumus tersebut di atas menjadi:
p(n,n)=n(n-l)(n-2)...(n-n+1)
p(n,n)=n(n-l)(n-2)٠.. 1
b)Jika n adalah unsur-unsur dengan beberapa unsur yang sama maka rumus tersebut berubah:
p=—ج (Negoro, 1998)
p\q\r\
dan kombinasi bentuk umum: P(n;n n,... ,n) = C(n;nn,... n) =ي p\q\.r\

Berbagai problematika yang sering dijumpai dalam kehidupan sehari-hari dan sangat menarik untuk dikaji dan dipelajari terutama pada matematika kombinatorial salah satunmya adalah masalah pasangan. Masalah pasangan merupakan masalah yang menyangkut penentuan pasangan, penentuan penempatan pekerjaan pada suatu perusahaan sehingga diperoleh pemilihan yang optimal.

Dalam skripsi ini dibahas bagaimana menyelesaikan berbagai permasalahan pasangan, penugasan dengan mtode perluasan permutasi dan kombinasi serta bagaimana menentukan wakil-wakil beda dari suatu himpunan dimana wakil-wakil beda inilah yang dapat menempati suatu pekerjaan tertentu dengan bantuan dari algoritma penugasan yang akan didapatkan suatu pola optimum atau daftar orang-orang yang akan dinikahi pada penempatan jodoh.

Dalam algoritma penugasan, prinsip yang digunakan adalah menentukan pola optimum dengan menggunakan langkah-langkah (i) menyusutkan baris dan kolom yang memuat unsur nol, (ii) mengkaji adanya pola layak yang seluruh unsurnya mengandung angka nol dengan menggunakan teknis garis penutup nol, (iii) meninjau unsur-unsur yang sama sekali belum tetutup garis, (iv) mencari atau memilih angka-angka yang menyusun pla optimum. Secara umum pola optimum tercapai jika terdapat angka nol dalam baris-baris dan kolom-kolom yang berbeda.