|A U B|=|A|+|B|-|A ∩ B|
Contoh Soal 1:
Dalam sebuah kelas terdapat mahasiswa yang mengambil mata kuliah kalkulus atau kombinatorika atau ke-duanya. Bila 25 mahasiswa mengambil kelas Kalkulus dan 13 orang mengambil kelas Kombinatorika, sementara 8 mahasiswa mengambil 2 mata kuliah tersebut. Berapa banyak mahasiswa dalam kelas tersebut?
Jawab:
Bisa dimisalkan,
|A |= Kalkulus = 25
|B|= Kombinatorika = 13
|A∩B| = Kalkulus dan Kombinatorika = 8
|A U B|=|A|+|B|-|A ∩ B|
|A U B|= 25+13-8 =30
Contoh soal 2:
Berapa banyak bilangan bulat positif tidak melebihi 1000 yang dapat dibagi oleh 7 atau 11?
Jawab:
|A| = habis dibagi 7 = 1000/7
|B| = habis dibagi 11 = 1000/11
|A∩B| = habis dibagi 7 dan 11 = 1000/(7x11)
Karena 7 dan 11 relatif prima
Dengan rumus di atas didapat |A U B|=220.
Ini yang akan dikembangkan menjadi prinsip inklusi-ekslusi. Sebelumnya untuk banyak anggota gabungan 3 himpunan, misalkan A,B dan C digunakan rumus
|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|Kenapa demikian?
- Anggota A, B dan C dihitung sekali. |A|+|B|+|C|
- Anggota A dan juga anggota B terhitung 2x dari langkah 1, sebab terhitung di A dan terhitung di B. Oleh sebab itu maka harus dikurangi sekali. −|A∩B|
- Sama dengan kasus langkah 2 untuk anggota A dan C. −|A∩C|
- Juga untuk B dan C. −|B∩C|
- Sementara anggota A, B, C belum terhitung sehingga harus dihitung lagi, maka ditambahkan +|A∩B∩C|
Contoh Soal:
Sebuah lembaga pendidikan menyediakan tiga jurusan bahasa yaitu bahasa Inggris, Jepang, dan mandarin. Setiap pelajar dalam lembaga tersebut boleh memilih lebih dari satu jurusan. Misalkan ada 1232 pelajar yang mengambil jurusan bahasa Inggris, 879 orang mengambil jurusan bahasa Jepang, 114 orang mengambil jurusan bahasa Mandarin, 103 orang mengambil jurusan bahasa Inggris dan Jepang, 23 orang mengambil jurusan bahasa Inggris dan mandarin, dan 14 orang mengambil jurusan bahasa Jepang dan Mandarin. Jika jumlah pelajar dalam lembaga itu ada 2092 orang, berapakah banyaknya pelajar yangmengambil jurusan bahasa Inggris, Jepang, dan Mandarin?
Jawab: Misalkan I adalah himpunan pelajar yang mengambil jurusan bahasa Inggris, J adalah himpunan pelajar yang mengambil jurusan bahasa jepang, dan M adalah himpunan pelajar yang mengambil jurusan bahasa mandarin, maka
|S|=1231, |I∩J|=103,|F|=879, |R|=114,|I∩M|=23,|J∩M|=14
dan
|I∪J∪M|=2092
Jika kita mensubstitusikan nilai di atas pada persamaan
|I∪J∪M|=|I|+|J|+|M|−|I∩J|−|I∩M|−|J∩M|+|I∩J∩M|
akan diperoleh
2092=1232+879+114−103−23−14+|I∩J∩M|
Dengan menyelesaikan |I∩J∩M|, diperoleh |I∩J∩M|=7. Jadi, ada 7 pelajar yang mengambil jurusan bahasa Inggris, Jepang, dan Mandarin.
Teorema I:Prinsip Inklusi dan Ekslusi
Bagaimana jika terdapat 4 atau lebih himpunan? Misalkan terdapat n himpunan, bagaimana menentukan banyak gabungan semua himpunan tersebut. Di sini terdapat teorema yang memudahkan anda menentukan gabungan n himpunan.
Misal terdapat A1,A2,A3,...,An Himpunan, maka banyak anggota gabungan himpunan tersebut adalah:
|A1∪A2∪…∪An|=∑1≤i≤n|Ai|−∑1≤i<j≤n|Ai∩Aj|+∑1≤i<j<k≤n|Ai∩Aj∩Ak|−…+(−1)n|A1∩A2∩…∩An|
Contoh sederhana ambil untuk 4 himpunan. A1, A2, A3, A4
Jadi, n= 4. maka bisa ditulis,
|A1∪A2∪A3∩A4|=|A1|+|A2|+|A3|+|A4|−|A1∩A2|−|A1∩A3|−|A1∩A4|−|A2∩A3|−|A2∩A4|−|A3∩A4|+|A1∩A2∩A3|+|A1∩A2∩A4|+|A1∩A3∩A4|+|A2∩A3∩A4|−|A1∩A2∩A3∩A4|
Aplikasi Inklusi dan Ekslusi
Terdapat alternatif inklusi-ekslusi yang bisa digunakan dalam penyelesaia masalah mengenai penentuan banyaknya anggota dalam sebuah himpunan yang tak memiliki sifat P1,P2,...,Pn. Bentuk yang dimaksud adalah:
Misal Ai adalah himpunan bagian yang memuat anggota dengan sifat Pi Banyak anggota dengan semua sifat:
Pi1,Pi2,...,Pik dilambangkan dengan
N(Pi1,Pi2,...,Pik)
Banyak suku himpunan dengan sifat tersebut bisa ditulis,
|Ai1∩Ai2∩…∩Aik|=N(Pi1Pi2…Pik)
Jika banyaknya anggota yang tidak memiliki sifat P1,P2,…,Pn dinotasikan dengan N(P′1P′2…P′n)dan banyaknya anggota dalam himpunan dinotasikan dengan N, maka
N(P′1P′2…P′n)=N−|A1∪A2∪…∪An|
Dengan dasar prinsip inklusi-ekslusi di atas, akan diperoleh,
N(P′1P′2…P′n)=N−∑1≤i≤nN(Pi)+∑1≤i<j≤nN(PiPj)−∑1≤i<j<k≤nN(PiPjPk)+…+(−1)nN(P1P2…Pn)
Contoh Soal:
Berapa banyak solusi x1+x2+x3=11 jika semua nilai x positif dengan x1≤3, x2≤4, dan x3≤6?
Jawab:
Untuk menerapkan prinsip inklusi - eksklusi, misalkan sebuah solusi memiliki sifat P1 jika x1>3, sifat P2 jika x2>4, dan sifat P3 jika x3>6. Banyaknya solusi yang memenuhi pertidaksamaan x1≤3, x2≤4, dan x3≤6 adalah
N(P′1P′2P′3)=N−N(P1)−N(P2)−N(P3)+N(P1P2)+N(P1P3)+N(P2P3)−N(P1P2P3).
Dengan menggunakan rumus kombinasi (pengulangan diperbolehkan), didapatkan
Subtitusikan nilai di atas pada rumus:
N(P′1P′2P′3)=78−36−28−15+6+1+0−0=6.
Jadilah Komentator Pertama untuk "Inklusi dan Ekslusi dalam Kombinatorika"
Post a Comment