Retno Mayapada: MAKALAH PRINSIP INKLUSI-EKSKLUSI DAN PERMUTASI

BAB I

PENDAHULUAN

I.1 Latar Belakang

Kita tidak jarang menemukan permasalahan kehidupan sehari-hari yang terkait dengan matematika diskrit. Salah satu cabang bahasan dalam matematika diskrit adalah kombinatorial. Persoalan kombinatorik bukan merupakan persoalan yang baru dalam kehidupan nyata. Banyak persoalan atau permasalahan kombinatorik baik sederhana maupun yang rumit kita temukan dalam kehidupan sehari-hari.

Contohnya permasalahan dengan berapa macam cara dari suatu himpunan objek disusun dengan persyaratan tertentu. Berapa macam plat mobil bisa dikeluarkan dengan 5 digit dan dua huruf? Saat pemilihan pemain untuk tim sepak bola yang terdiri dari 11 pemain. Apabila ada 15 orang ingin membentuk suatu tim sepak bola, ada berapa kemungkinan komposisi pemain yang dapat terbentuk?

Untuk menjawab pertanyaan tersebut amat rumit dan sangat kompleks cara menghitungnya. Namun, permasalahan-permasalahan yang serupa dengan di atas akan dibahas oleh penulis dalam makalah ini menggunakan bentuk permutasi khususnya agar memudahkan kita untuk menjawab permasalahan-permasalahan tadi. Adapula permasalahan lain yang kerap kita jumpai, misalnya sebuah perkuliahan umum dihadiri oleh 20 mahasiswa yang memiliki kegemaran membaca dan 30 mahasiswa yang memiliki kegemaran menulis, serta 10 mahasiswa yang gemar membaca dan menulis. Berapa mahasiswa di dalam perkuliahan tersebut yang memiliki kegemaran membaca atau menulis? Permasalahan ini kemudian dpaat diselesaikan menggunakan prinsip inklusi-eksklusi.

Dengan demikian, penulis dalam makalah ini akan membahas tentang kombinatorik terkhusus kepada permutasi dan prinsip inklusi-ekslusi.

I.2 Rumusan Masalah

Beberapa masalah yang dapat penulis rumuskan dan akan dibahas dalam makalah ini adalah:

1. Bagaimana penerapan prinsip inklusi-eksklusi untuk menyelesaikan persoalan matematika?

2. Bagaimana penjelesan rumus-rumus permutasi?

3. Apa saja contoh-contoh permasalahan yang dapat diselesaikan dengan permutasi?

I.3 Tujuan

Dengan melihat rumusan masalah yang telah disebutkan di atas, maka tujuan dari pembuatan makalah ini adalah:

1. Mengetahui penerapan prinsip inklusi-eksklusi untuk menyelesaikan persoalan matematika

2. Mengetahui penjelasan rumus-rumus permutasi

3. Mengetahui penyelesaian suatu permasalahan menggunakan rumus-rumus permutasi

BAB II

PEMBAHASAN

II.1 PRINSIP INKLUSI-EKSKLUSI

Pendahuluan

ü Irisan ( ∩ )

Irisan (intersection) dari himpunan A dan B adalah himpunan yg setiap elemennya merupakan elemen dari himpunan A dan himpunan B.

Notasi: A ∩ B={x | x ∈ A dan x ∈ B}

Misalkan A={1,2,3,4,5} dan B={2,3,5,7,11} maka A ∩ B={2,3,5}

ü Gabungan ( ∪ )

Gabungan(union) dari himpunan A dan B adalah himpunan yang setiap anggotanya merupakan anggota himpunan A atau himpunan B.

Notasi : A ∪ B = { x | x ∈ A atau x ∈ B }

Misalkan A={1,2,3,4,5} dan B={2,3,5,7,11} maka,

A ∪ B={1,2,3,4,5,7,11}

Prinsip Inklusi-Eksklusi

Prinsip Inklusi dan Eksklusi merupakan perluasan ide dalam Diagram Venn beserta operasi irisan dan gabungan, namun dalam pembahasan kali ini konsep tersebut diperluas, dan diperkaya dengan ilustrasi penerapan yang bervariasi dalam matematika kombinatorik. Berapa banyak anggota di dalam gabungan dua buah himpunan A dan B? penggabungan dua buah himpunan menghasilkan himpunan baru yang elemen-elemennya berasal dari berasal dari himpunan A dan himpunan B. Himpunan A dan himpunan B mungkin saja memiliki elemen-elemen yang sama. Banyaknya elemen bersama A dan B adalah . Setiap unsur yang sama itu telah dihitung dua kali, sekali pada dan sekali pada , meskipun ia seharusnya dianggap sebagai satu buah elemen di dalam . Karena itu, jumlah elemen hasil penggabungan seharusnya adalah jumlah elemen di masing-masing himpunan dikurangi dengan jumlah elemen di dalam irisannya, atau

Prinsip ini dikenal dengan nama prinsip inklusi-eksklusi.

Prinsip inklusi-eksklusi dapat dirampatkan untuk operasi lebih dari dua buah himpunan. Untuk tiga buah himpunan A, B, dan C berlaku teorema berikut.

Misalkan A, B, dan C adalah himpunan berhingga, maka berhingga dan

Bukti:

Sehingga, untuk r buah himpunan berlaku teorema berikut:

Contoh Soal dan Pembahasan

1. Berapa banyaknya bilangan bulat antara 1 dan 100 yang habis dibagi 3 atau 5?

Jawab:

Misalkan,

A = himpunan bilangan bulat yang habis dibagi 3,

B = himpunan bilangan bulat yang habis dibagi 5,

2. Sebanyak 1232 orang mahasiswa mengambil kuliah Bahasa Inggris, 879 orang mahasiswa mengambil kuliah Bahasa Perancis, dan 114 orang mahasiswa mengambil kuliah Bahasa Jerman. Sebanyak 103 orang mahasiswa mengambil kuliah Bahasa Inggris dan Perancis. 23 orang mahasiswa mengambil kuliah Bahasa Inggris dan Jerman, dan 14 orang mahasiswa mengambil kuliah Bahasa Perancis dan Bahasa Jerman. Jika 2092 orang mahasiswa mengambil paling sedikit satu buah kuliah Bahasa Inggris, Bahasa Perancis, dan Bahasa Jerman, berapa banyak mahasiswa yang mengambil kuliah ketiga buah bahasa tersebut?

Jawab:

Misalkan,

I = himpunan mahasiswa mengambil kuliah Bahasa Inggris

P = himpunan mahasiswa mengambil kuliah Bahasa Perancis

J = himpunan mahasiswa mengambil kuliah Bahasa Jerman

Maka,

Jadi, ada 7 orangmahasiswa yang mengambil kuliah ketiga buah bahasa Inggris, Perancis, dan Jerman.

3. Berapa banyak bilangan bulat positif yang tidak melampaui 1000 yang habis dibagi oleh 7 atau 11 ?

Jawab :

Misalkan:

P himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7

Q himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 11.

Dengan demikian P Q adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 atau habis dibagi 11, dan P ∩ Q himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan habis dibagi 11.

II. 1 PERMUTASI

Permutasi adalah setiap susunan yang berbeda dari elemen-elemen (objek) (Suparman:1985). Permutasi merupakan penyusunan kembali suatu kumpulan objek dalam urutan yang berbeda dari urutan yang semula.

a. Permutasi dari n unsur yang berbeda dengan sekali pengambilan r unsur

Terkadang kita hanya ingin menyusun ulang sejumlah elemen saja, tidak semuanya. Permutasi ini disebut permutasi-r dari n benda. Artinya, permutasi dari n yang berbeda dengan sekali pengambilan r unsur , r ≤ n, ialah semua urutan berbeda yang mungkin dari r unsur yang diambil dari n unsur yang berbeda.

contoh untai abcd, maka permutasi-2 dari abcd (yang semuanya ada 4 unsur) adalah sebanyak 12:

                              ab  ac  ad

                              ba  bc  bd

                              ca  cb  cd

                              da  db  dc

Sedangkan permutasi-3 dari untai yang sama adalah sebanyak 24:

                      abc  abd  acb  acd  adb  adc

                      bac  bca  bad  bda  bcd  bdc

                      cab  cba  cad  cda  cbd  cdb

                      dab  dba  dac  dca  dbc  dcb

Perhatikan bahwa tersedia r tempat untuk diisi dan dapat diisi dengan n benda. Tempat pertama dapat diisi dengan salah satu dari ke-n benda, jadi dalam n cara. Selanjutnya tersisa n-1 benda, masing-masing dapat dipakai untuk mengisi tempat yang kedua. Jadi tempat kedua dapat diisi dalam n-1 cara. Begitu pula tempat ketiga dapat diisi dalam n-2 cara, dan seterusnya. Pola ini dapat menunjukkan bahwa tempat ke-10 dapat diisi dalam n-9 cara, sehingga tempat ke-r dalam n – (r-1) cara. Sehingga menurut sila perkalian, ke-r tempat dapat diisi dalam, (Mosteller:1988)

_nP_r, = n(n-1)(n-2)…(n-r+1) cara

Contoh

1. Dalam berapa banyak cara kita bisa memilih seorang ketua, wakil ketua, sekretaris, dan bendahara dari kelompok yang terdiri dari 10 orang?

Jawab:

Cara 1: kita harus menghitung banyaknya pengurutan dari empat orang terpilih dari kelompok 10 orang, karena sebuah pengurutan mengambil (secara tunggal) seorang ketua (pilihan pertama), seorang wakil ketua (pilihan kedua), seorang sekretaris (pilihan ketiga), dan seorang bendahara (pilihan keempat). maka solusinya = 10 . 9 . 8 . 7 . = 5040

Cara 2: Kita juga bisa menyelesaikan contoh di atas dengan menerapkan secara langsung prinsip perkalian.

2. Lima mahasiswa fakultas A dan tiga mahasiswa fakultas B duduk berderet pada 8 kursi kosong sesuai dengan 8 lembar tiket seminar yang mereka miliki. Berapa banyak cara untuk duduk yang diperoleh dengan urutan berbeda jika mahasiswa fakultas A dan mahasiswa fakultas B masing-masing mengelompok sehingga hanya seorang mahasiswa fakultas A dan seorang mahasiswa fakultas B yang dapat duduk berdampingan?

Jawaban:
5 mahasiswa fakultas A duduk pada 5 kursi tertentu dan pertukaran duduk hanya boleh pada ke 5 kursi tersebut, sehingga banyaknya cara duduk mahasiswa fakultas A adalah P(5, 5). Demikian juga 3 mahasiswa fakultas B duduk pada tiga kursi tertentu dan pertukaran duduk diatara mereka hanya boleh pada ke 3 kursi ini, sehingga banyaknya cara untuk duduk mahasiswa fakultas B adalah P(3, 3). Dengan demikian, banyak cara duduk 5 mahasiswa fakultas A dan 3 mahasiswa fakultas B yang masing-masing mengelompok adalah P(5, 5) x P(3, 3) = 5! X 3! = 720

b. Permutasi dari n unsur dimana beberapa unsur sama

Bila n unsur itu sedemikian rupa sehingga dari n unsur itu p unsur sama, q unsur yang lain sama, dan r unsur yang lain lagi sama, dan seterusnya, maka banyaknya permutasi dari n unsur dengan sekali pengambilan seluruhnya ialah:

Bukti:

Perhatikan

Dimana:

p ialah banyaknya bilangan (unsur) yang sama dari n

q ialah banyaknya bilangan lain yang sama dari n

r ialah banyaknya bilangan yang lain lagi yang sama dari n, dan seterusnya dan

P ialah banyaknya permutasi yang terjadi

Perhatikan bilangan yang sama yang banyaknya p pada permutasi P. Bila seandainya bilangan yang banyaknya p itu tidak sama, maka setiap permutasi dari P itu akan diperoleh p! permutasi (dengan menyusun kembali p unsur yang berbeda). Ini akan mengubah P permutasi menjadi P.p! permutasi.

Dengan jalan yang sama kita dapat mengganti bilangan yang sama yang banyaknya q itu dengan q bilangan yang berbeda, sehingga diperoleh P.p!q! Juga kita dapat mengganti bilangan yang banyaknya r itu dengan r bilangan yang berbeda. Maka kita akan memperoleh P.p!q!r!, dan seterusnya. Sehingga setelah semua bilangan yang sama itu diganti dengan bilang yang tidak sama, akan diperoleh P.p!q!r!... permutasi. Dari n bilangan yang berbeda dengan sekali pengambilan semuanya akan diperoleh n! permutasi. Maka

Sebagai ilustrasi ambillah 3 huruf a, b, dan c. permutasi dari 3 unsur itu dengan sekali pengambilan semuanya akan diperoleh permutasi, yaitu: abc, acb, bac, bca, cab, dan cba. Andaikan diantara 3 unsur itu ada dua unsur yang sama, misalnya huruf a, b, c itu menjadi a, x, x. maka permutasi abc, acb, bac, bca, cab, dan cba itu menjadi axx, axx, xax, xxa, xax, dan xxa, dimana permutasi yang berbeda ialah axx, xax, dan xxa. Jadi hanya ada 3. Ini dapat diperoleh dengan cepat dengan menggunakan rumus

Contoh

Berapa buah permutasi dapat terjadi dengan huruf-huruf pada perkataan “MAMMA” dengan sekali pengambilan semuanya?

Jawab:

Semua huruf pada perkataan “MAMMA” ada 5, dimana dari 5 huruf itu ada 3 huruf M dan 2 huruf A. Maka banyaknya permutasi adalah:

c. Permutasi lingkar (Circular permutation)

Jadi, dari 3 unsur hanya ada dua susunan yang berbeda atau hanya ada dua permutasi lingkar (siklis).

Bila kita akan menentukan banyaknya permutasi lingkar, kita harus memilih satu unsur yang tetap posisinya dan kemudian menghitung banyaknya permutasi dari unsur-unsur lainnya seolah-olah lingkaran itu merupakan garis. Jadi, n unsur yang berbeda dapat disusun menurut lingkaran dalam Cara.

Contoh

Andaikan ada 5 orang yang sedang rapat pada meja bundar. Berapa cara 5 orang itu dapat duduk?

Jawab:

Susunan kelima orang itu duduk ada (5-1)!=4!=4.3.2.1=24 Cara

BAB III

KESIMPULAN

III.1 Prinsip Inklusi-Ekslusi

Prinsip Inklusi dan Eksklusi merupakan perluasan ide dalam Diagram Venn beserta operasi irisan dan gabungan. Misalkan A dan B sembarang himpunan. Penjumlahan |A|+|B| menghitung banyaknya elemen A yang tidak terdapat dalam B dan banyaknya elemen B yang tidak terdapat dalam A tepat satu kali, dan banyaknya elemen yang terdapat dalam A ∩ B sebanyak dua kali. Oleh karena itu, pengurangan banyaknya elemen yang terdapat dalam A ∩ B dari |A|+|B| membuat banyaknya anggota A B dihitung tepat satu kali. Dengan demikian,

|A B|= |A|+|B| – |A ∩ B|.

Sehingga, untuk r buah himpunan berlaku teorema berikut:

III. 2 Permutasi

a. Permutasi dari n unsur yang berbeda dengan sekali pengambilan r unsur

b. Permutasi dari n unsur dimana beberapa unsur sama

c. Permutasi lingkar (Circular permutation)

Banyak permutasi siklik yang beranggotakan n adalah (n-1)! Cara.

DAFTAR PUSTAKA

Lipschutz, Seymour dan Lipson, Marc Lars. 2002. Seri Penyelesaian Soal Schaum Jilid Matematika Diskrit. Salemba Teknika: Jakarta.

Mosteller, Frederick, dkk. 1988. Peluang dengan Statistika Terapannya. ITB Bandung: Bandung.

Munir, Rinaldi. 2004. Matematika Diskrit. Informatika: Bandung.

Richard, Johnsonlaugh Richard. 1998. Matematika Diskrit. PT Aditya Media: Yogyakarta.

Ruseffendi. 1984. Dasar-dasar Matematika Modern dan Komputer untuk Guru Edisi Keempat. Tarsito: Bandung.

Suparman. 1985. Matematik. CV. Rajawali: Jakarta.

dll

Syukron ^^

Assalamu'alaikum warohmatullahi wabarokatuh... terima kasih telah membaca artikel di atas..Mudah-mudahan bermanfaat bagi kita semua... Jazakumullah khoiron