inklusi-eksklusi · 2013-01-28 · tentukan banyaknya bilangan bulat n dari 1 sampai 100 yang tidak...
Post on 18-Jan-2020
44 Views
Preview:
TRANSCRIPT
INKLUSI-EKSKLUSI
Kristiana Wijaya
Jurusan MatematikaFakultas MIPA
Universitas Jember
February 28, 2012
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
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)]
Kristiana Wijaya INKLUSI-EKSKLUSI
Inklusi-Eksklusi
Ilustrasi Gambar
Figure:
Kristiana Wijaya INKLUSI-EKSKLUSI
Inklusi-Eksklusi
Ilustrasi Gambar
Figure:
Kristiana Wijaya INKLUSI-EKSKLUSI
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)
Kristiana Wijaya INKLUSI-EKSKLUSI
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,
2 kondisi c2 jika n dapat dibagi 3,
3 kondisi c3 jika n dapat dibagi 5.
Bilangan bulat n yang tidak bisa dibagi 2, 3 atau 5 adalah N(c1c2c3).
Kristiana Wijaya INKLUSI-EKSKLUSI
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,
2 kondisi c2 jika n dapat dibagi 3,
3 kondisi c3 jika n dapat dibagi 5.
Bilangan bulat n yang tidak bisa dibagi 2, 3 atau 5 adalah N(c1c2c3).
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
N(c3) = b1005 c = 20, adalah bilangan bulat kelipatan 5, yaitu
5, 10, 15, · · · , 100.
N(c1c2) = b1006 c = 16, adalah bilangan bulat kelipatan 6, yaitu
6, 12, 18, · · · , 96.
N(c1c3) = b10010 c = 10, adalah bilangan bulat kelipatan 10, yaitu
10, 20, 30, · · · , 100.
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
N(c3) = b1005 c = 20, adalah bilangan bulat kelipatan 5, yaitu
5, 10, 15, · · · , 100.
N(c1c2) = b1006 c = 16, adalah bilangan bulat kelipatan 6, yaitu
6, 12, 18, · · · , 96.
N(c1c3) = b10010 c = 10, adalah bilangan bulat kelipatan 10, yaitu
10, 20, 30, · · · , 100.
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
N(c3) = b1005 c = 20, adalah bilangan bulat kelipatan 5, yaitu
5, 10, 15, · · · , 100.
N(c1c2) = b1006 c = 16, adalah bilangan bulat kelipatan 6, yaitu
6, 12, 18, · · · , 96.
N(c1c3) = b10010 c = 10, adalah bilangan bulat kelipatan 10, yaitu
10, 20, 30, · · · , 100.
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
N(c3) = b1005 c = 20, adalah bilangan bulat kelipatan 5, yaitu
5, 10, 15, · · · , 100.
N(c1c2) = b1006 c = 16, adalah bilangan bulat kelipatan 6, yaitu
6, 12, 18, · · · , 96.
N(c1c3) = b10010 c = 10, adalah bilangan bulat kelipatan 10, yaitu
10, 20, 30, · · · , 100.
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
N(c3) = b1005 c = 20, adalah bilangan bulat kelipatan 5, yaitu
5, 10, 15, · · · , 100.
N(c1c2) = b1006 c = 16, adalah bilangan bulat kelipatan 6, yaitu
6, 12, 18, · · · , 96.
N(c1c3) = b10010 c = 10, adalah bilangan bulat kelipatan 10, yaitu
10, 20, 30, · · · , 100.
Kristiana Wijaya INKLUSI-EKSKLUSI
Inklusi-Eksklusi
N(c2c3) = b10015 c = 6, adalah bilangan bulat kelipatan 15, yaitu
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.
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
Inklusi-Eksklusi
N(c2c3) = b10015 c = 6, adalah bilangan bulat kelipatan 15, yaitu
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.
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
Inklusi-Eksklusi
N(c2c3) = b10015 c = 6, adalah bilangan bulat kelipatan 15, yaitu
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.
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
Inklusi-Eksklusi
N(c2c3) = b10015 c = 6, adalah bilangan bulat kelipatan 15, yaitu
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.
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
Inklusi-Eksklusi
N(c2c3) = b10015 c = 6, adalah bilangan bulat kelipatan 15, yaitu
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.
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
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
Kristiana Wijaya INKLUSI-EKSKLUSI
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
Kristiana Wijaya INKLUSI-EKSKLUSI
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
Kristiana Wijaya INKLUSI-EKSKLUSI
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
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
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.
Kristiana Wijaya INKLUSI-EKSKLUSI
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!.
Kristiana Wijaya INKLUSI-EKSKLUSI
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!.
Kristiana Wijaya INKLUSI-EKSKLUSI
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!.
Kristiana Wijaya INKLUSI-EKSKLUSI
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!.
Kristiana Wijaya INKLUSI-EKSKLUSI
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!.
Dengan cara yang sama kita dapatkan:
N(c1c3) = N(c2c3) = 22!
N(cic4) = 21! untuk i 6= 4
Kristiana Wijaya INKLUSI-EKSKLUSI
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!.
Dengan cara yang sama kita dapatkan:
N(c1c3) = N(c2c3) = 22!
N(cic4) = 21! untuk i 6= 4
Kristiana Wijaya INKLUSI-EKSKLUSI
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!.
Dengan cara yang sama kita dapatkan:
N(c1c3) = N(c2c3) = 22!
N(cic4) = 21! untuk i 6= 4
Kristiana Wijaya INKLUSI-EKSKLUSI
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!
Kristiana Wijaya INKLUSI-EKSKLUSI
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!
Kristiana Wijaya INKLUSI-EKSKLUSI
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!
Kristiana Wijaya INKLUSI-EKSKLUSI
Inklusi-Eksklusi
THANK YOU
Kristiana Wijaya INKLUSI-EKSKLUSI
top related