inklusi-eksklusi · 2013-01-28 · tentukan banyaknya bilangan bulat n dari 1 sampai 100 yang tidak...

INKLUSI-EKSKLUSI

Kristiana Wijaya

Jurusan MatematikaFakultas MIPA

Universitas Jember

February 28, 2012

Kristiana Wijaya INKLUSI-EKSKLUSI

Inklusi-Eksklusi

Pendahuluan

Misalkan S himpunan dengan |S | = N dan c1, c2, · · · ct adalah subset dariS dengan kondisi tertentu. Subset-subset dari S boleh memenuhi lebihdari satu kondisi. Untuk setiap i = 1, 2, · · · , t, N(ci ) menyatakanbanyaknya unsur di S yang memenuhi kondisi ci ; N(cicj) untuk i 6= jmenyatakan banyaknya unsur di S yang memenuhi kondisi ci dan cj ;N(cicjck) untuk i 6= j 6= k menyatakan banyaknya unsur di S yangmemenuhi kondisi ci , cj dan ck ; begitu seterusnya.

Inklusi-Eksklusi

Pendahuluan

Untuk setiap i = 1, 2, · · · , t, N(c i ) = N − N(ci ) menyatakan banyaknyaunsur di S yang tidak memenuhi kondisi ci ; N(c ic j) untuk i 6= jmenyatakan banyaknya unsur di S yang tidak memenuhi kondisi ci atau cj ;N(cicjck) untuk i 6= j 6= k menyatakan banyaknya unsur di S yang tidakmemenuhi kondisi ci , cj atau ck ; begitu seterusnya. [CatatanN(c ic j) 6= N(cicj)]

Inklusi-Eksklusi

Ilustrasi Gambar

Figure:

Inklusi-Eksklusi

Ilustrasi Gambar

Figure:

Inklusi-Eksklusi

Theorema

Misalkan himpunan S dengan |S | = N dan kondisi ci untuk i = 1, 2, · · · , tdipenuhi oleh beberapa unsur di S . Banyaknya unsur di S yang tidakmemenuhi satupun kondisi ci dinotasikan N = N(c1, c2, c3, · · · , ct) adalah

N =N − [N(c1) + N(c2) + N(c3) + · · · + N(ct)]

+ [N(c1c2) + N(c1c3) + · · · + N(c1ct) + N(c2c3) + · · · + N(ct−1ct)]

− [N(c1c2c3) + N(c1c2c4) + · · ·N(c1c2ct) + · · ·N(ct−2ct−1ct)]

+ (−1)tN(c1c2c3 · · · ct)

Inklusi-Eksklusi

Example

Tentukan banyaknya bilangan bulat n dari 1 sampai 100 yang tidak bisadibagi 2, 3 atau 5.

Solution:

Dalam hal ini S = {1, 2, 3, · · · , 100} dan N = 100. Untuk n ∈ S , nmemenuhi

1 kondisi c1 jika n dapat dibagi 2,

3 kondisi c3 jika n dapat dibagi 5.

Bilangan bulat n yang tidak bisa dibagi 2, 3 atau 5 adalah N(c1c2c3).

Inklusi-Eksklusi

Example

Tentukan banyaknya bilangan bulat n dari 1 sampai 100 yang tidak bisadibagi 2, 3 atau 5.

Solution:

Dalam hal ini S = {1, 2, 3, · · · , 100} dan N = 100. Untuk n ∈ S , nmemenuhi

3 kondisi c3 jika n dapat dibagi 5.

Bilangan bulat n yang tidak bisa dibagi 2, 3 atau 5 adalah N(c1c2c3).

Inklusi-Eksklusi

Solution:

Maka N(c1) = b1002 c = 50, adalah bilangan bulat genap 2, 4, 6, · · · , 100.

N(c2) = b1003 c = 33, adalah bilangan bulat kelipatan 3, yaitu

3, 6, 9, · · · , 96.

5, 10, 15, · · · , 100.

N(c1c2) = b1006 c = 16, adalah bilangan bulat kelipatan 6, yaitu

6, 12, 18, · · · , 96.

10, 20, 30, · · · , 100.

Inklusi-Eksklusi

Solution:

3, 6, 9, · · · , 96.

5, 10, 15, · · · , 100.

6, 12, 18, · · · , 96.

10, 20, 30, · · · , 100.

Inklusi-Eksklusi

Solution:

3, 6, 9, · · · , 96.

5, 10, 15, · · · , 100.

6, 12, 18, · · · , 96.

10, 20, 30, · · · , 100.

Inklusi-Eksklusi

Solution:

3, 6, 9, · · · , 96.

5, 10, 15, · · · , 100.

6, 12, 18, · · · , 96.

10, 20, 30, · · · , 100.

Inklusi-Eksklusi

Solution:

3, 6, 9, · · · , 96.

5, 10, 15, · · · , 100.

6, 12, 18, · · · , 96.

10, 20, 30, · · · , 100.

Inklusi-Eksklusi

15, 30, 45, · · · , 90.

N(c1c2c3) = b10030 c = 3, adalah bilangan bulat kelipatan 30, yaitu

30, 60, 90.

N(c1c2c3) = N − [N(c1) + N(c2) + N(c3)]

+ [N(c1c2) + N(c1c3) + N(c2c3)] − N(c1c2c3)

= 100 − [50 + 33 + 20] + [16 + 10 + 6] − 3

26 bilangan yang tidak bisa dibagi 2,3 atau 5 dari 1 sampai 100 adalah1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83,89, 91 dan 97.

Inklusi-Eksklusi

15, 30, 45, · · · , 90.

30, 60, 90.

N(c1c2c3) = N − [N(c1) + N(c2) + N(c3)]

+ [N(c1c2) + N(c1c3) + N(c2c3)] − N(c1c2c3)

= 100 − [50 + 33 + 20] + [16 + 10 + 6] − 3

Inklusi-Eksklusi

15, 30, 45, · · · , 90.

30, 60, 90.

N(c1c2c3) = N − [N(c1) + N(c2) + N(c3)]

+ [N(c1c2) + N(c1c3) + N(c2c3)] − N(c1c2c3)

= 100 − [50 + 33 + 20] + [16 + 10 + 6] − 3

Inklusi-Eksklusi

15, 30, 45, · · · , 90.

30, 60, 90.

N(c1c2c3) = N − [N(c1) + N(c2) + N(c3)]

+ [N(c1c2) + N(c1c3) + N(c2c3)] − N(c1c2c3)

= 100 − [50 + 33 + 20] + [16 + 10 + 6] − 3

Inklusi-Eksklusi

15, 30, 45, · · · , 90.

30, 60, 90.

N(c1c2c3) = N − [N(c1) + N(c2) + N(c3)]

+ [N(c1c2) + N(c1c3) + N(c2c3)] − N(c1c2c3)

= 100 − [50 + 33 + 20] + [16 + 10 + 6] − 3

Inklusi-Eksklusi

Example

Tentukan banyaknya solusi bulat tak-negatif dari persamaanx1 + x2 + x3 + x4 = 18 jika xi ≤ 7 untuk 1 ≤ i ≤ 4.

Solution:

N = banyaknya solusi x1 + x2 + x3 + x4 = 18 dengan xi ≥ 0.

N = C (4 + 18 − 1, 18)

= C (21, 18)

= 1330.

Inklusi-Eksklusi

Example

Tentukan banyaknya solusi bulat tak-negatif dari persamaanx1 + x2 + x3 + x4 = 18 jika xi ≤ 7 untuk 1 ≤ i ≤ 4.

Solution:

N = banyaknya solusi x1 + x2 + x3 + x4 = 18 dengan xi ≥ 0.

N = C (4 + 18 − 1, 18)

= C (21, 18)

= 1330.

Inklusi-Eksklusi

Selanjutnya banyaknya solusi dari x1, x2, x3, x4 yang memenuhi kondisi ci

untuk 1 ≤ i ≤ 4 jika xi > 7 (atau xi ≥ 8) sama dengan banyaknya solusitak-negatif dari persamaan x1 + x2 + x3 + x4 = 10 jika xi ≥ 0 untuk setiap1 ≤ i ≤ 4.

Permasalahan kita adalah mencari N(c1c2c3c4)

N(c1) = N(c2) = N(c3) = N(c4) = C (4 + 10 − 1, 10) = C (13, 10)

Selanjutnya N(c1c2) adalah solusi bulat tak-negatif dari persamaanx1 + x2 + x3 + x4 = 2 jika xi ≥ 0 untuk setiap 1 ≤ i ≤ 4.Sehingga N(cicj) = C (4 + 2 − 1, 2) = C (5, 2) untuk i 6= j dengan1 ≤ i , j ≤ 4

Inklusi-Eksklusi

N(c1) = N(c2) = N(c3) = N(c4) = C (4 + 10 − 1, 10) = C (13, 10)

Inklusi-Eksklusi

N(c1) = N(c2) = N(c3) = N(c4) = C (4 + 10 − 1, 10) = C (13, 10)

Inklusi-Eksklusi

N(c1) = N(c2) = N(c3) = N(c4) = C (4 + 10 − 1, 10) = C (13, 10)

Inklusi-Eksklusi

Selanjutnya N(cicjck) = 0 dan N(c1c2c3c4) = 0

Dengan demikianN(c1c2c3c4) = C (21, 18) − 4C (13, 10) + 6C (5, 2) − 0 + 0 = 246

Jadi dari 1330 solusi tak-negatif dari persamaan x1 + x2 + x3 + x4 = 18hanya 246 yang memenuhi kondisi xi ≤ 7 untuk setiap 1 ≤ i ≤ 4.

Inklusi-Eksklusi

Example

Ada berapa cara 26 huruf dipermutasikan, sehingga tidak ada kata car,dog, fun atau byte.

Solution:

Misalkan S menyatakan semua permutasi dari 26 huruf.Maka |S | = 26!

Untuk setiap 1 ≤ i ≤ 4 permutasi di S yang memenuhi kondisi ci jikapermutasi memuat car, dog, fun atau byte secara berturut-turut.

N(c1) adalah banyaknya cara dari 24 simbol car, b, d, e, f, · · · , p, q, s, t,· · · , x, y, z dapat dipermutasikan. Sehingga N(c1) = 24!.

Inklusi-Eksklusi

Example

Solution:

Inklusi-Eksklusi

Example

Solution:

Inklusi-Eksklusi

Example

Solution:

Inklusi-Eksklusi

Dengan cara yang sama kita dapatkan:

N(c2) = N(c3) = 24!

N(c4) = 23!

N(c1c2) adalah banyaknya cara dari 22 simbol car, dog, b, e, f, h, i, · · · ,m, n, p, q, s, t, · · · , x, y, z dapat dipermutasikan. Sehingga N(c1c2) = 22!.

N(c1c3) = N(c2c3) = 22!

N(cic4) = 21! untuk i 6= 4

Inklusi-Eksklusi

N(c2) = N(c3) = 24!

N(c4) = 23!

N(c1c3) = N(c2c3) = 22!

N(cic4) = 21! untuk i 6= 4

Inklusi-Eksklusi

N(c2) = N(c3) = 24!

N(c4) = 23!

N(c1c3) = N(c2c3) = 22!

N(cic4) = 21! untuk i 6= 4

Inklusi-Eksklusi

Selanjutnya,N(c1c2c3) = 20!

N(cicjc4) = 19! untuk 1 ≤ i ≤ j ≤ 3

N(c1c2c3c4) = 17!

Jadi permutasi dari S yang tidak ada kata car, dog, fun atau byte adalah

N(c1c2c3c4) = N − [N(c1) + N(c2) + N(c3) + N(c4)]

− [N(c1c2) + N(c1c3) + N(c1c4) + N(c2c3) + N(c2c4)

+ N(c3c4)] − [N(c1c2c3) + N(c1c2c4) + N(c2c3c4)]

+ N(c1c2c3c4)

= 26! − [3(24!) + 23!] + [3(22!) + 3(21!)]

− [20! + 3(19!)] + 17!

Inklusi-Eksklusi

N(cicjc4) = 19! untuk 1 ≤ i ≤ j ≤ 3

N(c1c2c3c4) = 17!

N(c1c2c3c4) = N − [N(c1) + N(c2) + N(c3) + N(c4)]

+ N(c1c2c3c4)

= 26! − [3(24!) + 23!] + [3(22!) + 3(21!)]

− [20! + 3(19!)] + 17!

Inklusi-Eksklusi

N(cicjc4) = 19! untuk 1 ≤ i ≤ j ≤ 3

N(c1c2c3c4) = 17!

N(c1c2c3c4) = N − [N(c1) + N(c2) + N(c3) + N(c4)]

+ N(c1c2c3c4)

= 26! − [3(24!) + 23!] + [3(22!) + 3(21!)]

− [20! + 3(19!)] + 17!

Inklusi-Eksklusi

THANK YOU

inklusi-eksklusi · 2013-01-28 · tentukan banyaknya bilangan bulat n dari 1 sampai 100 yang tidak...

Documents