8.1 Inklusi-eklusi.docx

8.1 Prinsip Inklusi-Ekslusi

Dari diagram Venn pada gambar 8.1 kita lihat bahwa jika N(ci) dinotasikan sebagai banyaknya anggota pada lingkaran sebelah kiri dan N(cj) dinotasikan sebagai banyaknya anggota pada lingkaran sebelah kanan, maka N(cicj) adalah banyaknya anggota pada daerah ̅ Cj ̅ ) menghitung elemen di luar gabungan lingkaran ini. yang tumpang tindih, dimana N(C𝑖 Konsekuensi dari gambar 8.1 adalah, Dengan cara yang sama, dari gambar 8.2 dapat diperoleh :

Teorema 8.1 (Prinsip Inklusi-Eklusi) Sebuah himpunan S, dengan |S|= N dan kondisi ci , 1 ≤ i ≤ t memenuhi untuk beberapa elemen pada S. Banyaknya anggota pada S yang tidak satupun memenuhi kondisi ci ,1 ≤ i ≤ t dinotasikan dengan Dimana ,

Corollary 8.1 Dibawah hipotesis pada teorema 8.1 banyaknya anggota S yang memenuhi setidaknya satu ̅ pada kondisi c1 dimana 1≤ i ≤ t, dirumuskan dengan N(c1 or c2 or ... or ct ) = N - 𝑁 Sebelum menyelesaikan beberapa contoh, kita dapat menulis bentuk sederhana dari pernyataan di teorema 8.1 sebagai berikut :

Dan secara umum :

Contoh 8.1 Temukan banyaknya bilangan bulat positif n dimana 1 ≤ n ≤ 100 dan n bukan merupakan bilangan yang dapat dibagi 2,3, atau 5. S= {1,2,3, … , 100} dan N=100.untuk n € S , n memenuhi : a. Kondisi ci , jika n dapat dibagi 2 b. Kondisi c2 , jika n dapat dibagi 3 dan c. Kondisi c3 , jika n dapat dibagi 5 ̅̅̅ ̅̅̅ ̅ (𝑐1 Maka jawaban pada masalah ini adalah 𝑁 𝑐2 ̅̅̅ 𝑐3) N(c1) = ⌊100/2⌋ = 50 (2,4,6,8,...,100) N(c2) = ⌊100/3⌋ = 33 (3,6,9,12,...,96,99) N(c3) = ⌊100/5⌋ =20 (5,10,...,100) N (c1c2) = ⌊100/6⌋ = 16 (6, 12, 18,...,96) N (c1c3) = ⌊100/10⌋ = 10 (10, 20,...,100) N (c2c3) = ⌊100/15⌋ = 6 (15, 30,..., 90) N (c1c2c3)= ⌊100/30⌋ = 3 (30,60,90) Dengan menerapkan prinsip Inklusi-Eklusi, kita menemukan :

26 bilangan tersebut adalah (1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,dan 97) Contoh 8.5

Untuk n € Z+ n≥2 misalkan Ø(n) adalah bilangan bulat positif m, dimana 1≤ m < n dan FPB (m,n) =1 maka m,n adalah relatif prima. Fungsi Inidisebut fungsi phi euler’s. Misalnya Ø(2) =1, Ø(4) = 2 dan untuk bilangan prima p maka Ø(p)= p-1. Diketahui : Ketika n= p, p bilangan prima, Sehingga untuk n=23100 kita dapat menemukan perhitungannya sebagai berikut :