Prinsip Inklusi Eksklusi
Prinsip Inklusi Eksklusi
Prinsip Inklusi Eksklusi
KELOMPOK 3:
Alfisyahrin Z(1411440020)
Dian Rahma Maghfira (1411440022)
Ayu Puspita Sari (1411440024)
Fitrahlaelah Muh. Asri (1411440026)
Irma Sulistiawati (1411440028)
Ana Novianti (1411441002)
Irmayanti (1411441004)
Lu’lu Yu’tikan Nabila (1411441006)
Muhammad Yusmar (1411441010)
4.1 PENDAHULUAN
Misalkan S adalah suatu himpunan dari N obyek dan a1,a2, …, an adalah sifat-sifat
yang mungkin dimiliki oleh obyek-obyek yang ada di S. sebuah obyek di S mungkin saja
memiliki beberapa (bias nol) sifat dari sifat-sifat yang ada. Banyaknya obyek S yang
mempunyai sifat a, dilambangkan dengan N(ai) sedangkan N(ai’) menyatakan banyaknya
obyek S yang tidak memiliki sifat ai,. Dengan demikian
N = N(ai) +N(ai’)
Selanjutnya N(ai aj) menyatakan banyaknya objek S yang memiliki sifat ai dan aj, dan
N(ai’ aj’) melambangkan banyaknya objek yang tidak memiliki sifat ai maupun aj. Begitu
pula, N(ai’ aj) menyatakan banyaknya objek yang memiliki sifat aj tapi bukan sifat ai. Secara
umum N(ai1, ai2, …, aik) adalah banyaknya objek S yang memiliki sifat-sifat ai1, ai2, …, dan
aik.
Kita peroleh,
dan
Karena
maka
Sehingga diperoleh,
Dengan demikian, banyaknya obyek di S yang tidak memiliki sifat a1 dan tidak memiliki sifat
a2 adalah;
Dengan cara yang sama dapat ditunjukkan bahwa banyaknya obyek di S yang tidak memiliki
sifat di a1, a2, ataupun a3 adalah,
Persamaan (4.1.1) dan (4.1.2) adalah bentuk-bentuk khusus dari suatu prinsip yang disebut
prinsip inklusi-eksklusi.
Jika N adalah banyaknya obyek dalam himpunan S dan a1, . . . , ar sifat sifat yang mungkin
dimiliki oleh suatu obyek di S, maka banyaknya obyek di S yang tidak memiliki sifat a 1, a2, .
. . , ar adalah
N(a1’ , a2’ , . . . , ar’) = N - ∑𝑖 𝑁(ai) + ∑𝑖,𝑗 𝑁(aiaj) + ∑𝑖,𝑗,𝑘 𝑁(aiajak) + . . . + (-1)r N (a1, a2,
. . . , ar)
CATATAN :
Dalam persamaan (4.2.1) “sigma” pertama mencakup semua i ∈ (1, 2, 3, . . . , r) ; “sigma”
mencakup semua triple {i, j, k}, ∈ (1, 2, 3, . . . , r) dan i, j, k berbeda; dan seterusnya.
CONTOH 4.2.1 :
Penyelesaian :
a. N(a1 a2)
b. N(a1 a2 a3)
= | 1000/3 | = 333
= | 1000/5 | = 200
= | 1000/7 | = 142
= | 1000/21 | = 47
= | 1000/35 | = 28
= | 1000/105 | = 9
(b) N (a1 a2 a3) = N - N(a1 ) - N(a2) - N(a3) + N(a1 a2) + N(a1 a3) + N(a2 a3) +
N(a1 a2 a3)
= 457
CONTOH 4.2.2 :
Sebanyak n bola yang berbeda ditempatkan ke dalam k kotak yang berbeda. Berapakah
peluang bahwa tidak terdapat kotak yang kosong?
Penyelesaian :
Misal S adalah himpunan semua kejadian (pendistribusian) yang mungkin. Ei adalah kejadian
bahwa kotak ke I kosong dan ai adalah sifat bahwa kejadian Ei muncul. Dalam hal ini I ϵ
{1,2,3,…,k}.
Kita peroleh N = |S| = kn ; … dan seterusnya. Selanjutnya terdapat (𝑘1) cara memilih sifat ai ;
(𝑘2) cara memilih sifat ai dan aj ; (𝑘3) cara memilih sifat ai, aj, dan ak dan seterusnya. Sehingga
banyaknya cara menempatkan (mendistribusikan) n bola ke dalam n kotak sedemikian
sehingga tidak ada kotak yang kosong adalah :
𝑖
= ∑𝑘𝑖=0(−1)i(𝑘𝑖)(1 − 𝑘)n
CONTOH 4.2.3 :
Gunakan prinsip inklusi-eksklusi untuk menentukan banyaknya solusi bulat dari persamaan
berikut :
Penyelesaian :
N = |S| = (3+20−1
20
)= (22
20
) (lihat contoh 2.3.5 bab 2)
Sehingga,
= (3+14−1
14
) = (16
14
)
Selanjutnya,
= (3+8−1
8
) = (10
8
)
Dengan cara yang sama diperoleh
10
N(a1a2) = N(a1 dan a2) = ( ).
8
N (a1a2a3) = Banyaknya anggota S dengan sifat a1, a2, dan a3
= (3+2−1
2
) = (42)
22 16 16 16 10 10 10 4
=( )−( )−( )−( )+( )+( )+( )−( )
20 14 14 14 8 8 8 2
22 16 10 4
=( ) − 3( ) + 3( ) − ( ) = 0
20 14 8 2
Jadi banyak solusi bulat dari persamaan
adalah :
22 16 10 4
( ) − 3 ( ) + 3 ( ) − ( ).
20 14 8 2
dimana "sigma" mencakup semua kemungkinan memilih t sifat ai1,ai2,...,ait dari r sifat yang
ada. hubungan em dengan sm dapat dilihat di teorama berikut.
TEOREMA 4.3.1:
Misalkan a1,a2,a3,...,ar adalah sifat-sifat yang mungkin dimiliki oleh suatu objek di himpunan
S yang memiliki tepat m≤r sifat adalah:
em = sm - (𝑚+1
1
)Sm+1 + (𝑚+2
2
) Sm+2 - (𝑚+3
3
)Sm+3 + ... + (-1)p (𝑚+𝑝
𝑝
)Sm+p + ...(-1)r-m (𝑚+𝑟−𝑚
𝑟−𝑚
)Sr.
Contoh 4.3.1
Sebanyak n pasangan suami istri hadir dalam suatu pesta dansa. Dansa dilakukan serentak
dan seorang pria hanya berdansa dengan seorang wanita.
a. Berapakah peluang terdapat tepat satu pasang suami istri berdansa dalam pesta dansa
tersebut?
b. Berapakah peluang terdapat tepat tiga pasang suami istri berdansa bersama dalam
pesta dansa tersebut?
Penyelesaian :
Misalkan S adalah himpunan semua pasangan dansa yang mungkin, dan aᵢ menyatakan sifat
dimana suami ke i berpasangan dengan istrinya, 1 ≤ i ≤ n. Karena terdapat n pasang suami
istri, maka N =|S| = n!. Selanjutnya kita peroleh:
= (n-1)!
Begitu pula,
N(aᵢaj) = banyaknya pasangan yang mungkin dimana pasangan ke i dan j adalah pasangan
suami istri.
= (n-2)!
Karena ada (𝑛𝑘) cara memilih k sifat dari n sifat yang ada, maka:
1 1 1
= n! [1- 1! + 2! - ... (−1)𝑛−1 (𝑛−1)! ]
𝑛! 1 1 1
= 3! [1- 1! + 2! - ... +(−1)𝑛−1 (𝑛−3)! ]
Dengan demikian peluang terdapat tepat tiga pasang suami istri berdansa
bersama adalah:
𝑒₃ 1 1 1 1
= [1- 1! + 2! - ... +(−1)𝑛−1 (𝑛−3)! ]
𝑁 3!
TEOREMA 4.4.1.
Jika di dalam himpunanS terdapat r sifat, maka banyaknya obyek S yang memiliki sifat
sebanyak bilangan genap adalah:
1
e0 + e2 + e4 + …= 2 [So + ∑𝑟𝑡=0 (−2)t St]
dan banyak objeknya objek S yang memiliki sifat sebanyak bilangan ganjil adalah :
1
e1 + e3 + e5 + … = 2 [So + ∑𝑟𝑡=0 (−2)r St]
BUKTI:
Misal E(x) = ∑𝑚 m
𝑚=0 𝑒 mx adalah fungsi pembangkit biasa dari barisan (em). Dari
teorema 4.3.1 diperoleh:
E(x) = [ S0-S1+S2-S3-…+ (-1)rSt ]
…+ [Sm – (𝑚+1
1
) Sm+1 + (𝑚 2+ 2)Sm+2 - … + (-1)r-m (𝑟−𝑚
𝑟
) St ] xm+…
… + Stxt
Ekuivalen dengan
…+Sm[xm - (𝑚
1
)xm-1 + (𝑚
2
𝑚
)xm-2 + …+(-1)m-1(𝑚−1)x + (-1)m] + … + Sr[xr - (𝑟1)xr-1 + (𝑟2)xr-2n +
(-1)r]
Sehingga
Dengan demikian
𝐒0, jika m = 0
E(1) = { dan E(-1) = ∑𝑟𝑚=0(−2)mSm
0, jika m≥ 1
dan
1 1
∑∞
𝑖=0 e2t = 2[E(1) - E(-1)] = [ S0 - ∑𝑟𝑚=0(−2) mSm].
2
1. Tentukan banyak bilangan bulat dari 1 sampai dengan 10000 yang tidak habis dibagi
4, 6, 7, atau 10!
Jawab:
Misal: 𝑆 = {1, 2, 3, 4, 5, … , 10000}
𝑎1 = {𝑠𝑖𝑓𝑎𝑡 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 4}
𝑎2 = {𝑠𝑖𝑓𝑎𝑡 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 6}
𝑎3 = {𝑠𝑖𝑓𝑎𝑡 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 7}
𝑎4 = {𝑠𝑖𝑓𝑎𝑡 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 10}
N(𝑎1 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 4
10000
𝑁(𝑎1 ) = = 2500
4
N(𝑎2 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 6
10000
𝑁(𝑎2 ) = = 1666
6
N(𝑎3 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 7
10000
𝑁(𝑎3 ) = = 1428
7
N(𝑎4 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 10
10000
𝑁(𝑎4 ) = = 1000
10
N(𝑎1 𝑎2 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 4 𝑑𝑎𝑛 6
10000
𝑁(𝑎1 𝑎2 ) = = 416
24
N(𝑎1 𝑎3 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 4 𝑑𝑎𝑛 7
10000
𝑁(𝑎1 𝑎3 ) = = 357
28
N(𝑎1 𝑎4 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 4 𝑑𝑎𝑛 10
10000
𝑁(𝑎1 𝑎4 ) = = 250
40
N(𝑎2 𝑎3 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 6 𝑑𝑎𝑛 7
10000
𝑁(𝑎2 𝑎3 ) = = 238
42
N(𝑎2 𝑎4 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 6 𝑑𝑎𝑛 10
10000
𝑁(𝑎2 𝑎4 ) = = 166
60
N(𝑎3 𝑎4 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 7 𝑑𝑎𝑛 10
10000
𝑁(𝑎3 𝑎4 ) = = 142
70
N(𝑎1 𝑎2 𝑎3 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 4, 6 𝑑𝑎𝑛 7
10000
𝑁(𝑎1 𝑎2 𝑎3 ) = = 54
168
N(𝑎1 𝑎2 𝑎4 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 4, 6 𝑑𝑎𝑛 10
10000
𝑁(𝑎1 𝑎2 𝑎4 ) = = 41
240
N(𝑎2 𝑎3 𝑎4 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 6, 7 𝑑𝑎𝑛 10
10000
𝑁(𝑎2 𝑎3 𝑎4 ) = = 23
420
N(𝑎1 𝑎2 𝑎3 𝑎4 ) = 𝑏𝑎𝑛𝑦𝑎𝑘 𝑎𝑛𝑔𝑔𝑜𝑡𝑎 𝑆 𝑦𝑎𝑛𝑔 ℎ𝑎𝑏𝑖𝑠 𝑑𝑖𝑏𝑎𝑔𝑖 4, 6, 7 𝑑𝑎𝑛 10
10000
𝑁(𝑎1 𝑎2 𝑎3 𝑎4 ) = =5
1680
𝑁(𝑎11 𝑎12 𝑎13 𝑎14 )
= 𝑁 − ∑ 𝑁( 𝑎𝑖 ) + ∑ 𝑁( 𝑎𝑖 𝑎𝑗 ) ∑ 𝑁( 𝑎𝑖 𝑎𝑗 𝑎𝑘 ) + ∑ 𝑁( 𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 )
𝑖 𝑖,𝑗 𝑖,𝑗,𝑘 𝑖,𝑗,𝑘,𝑙
Misalkan : S = {1,2,3,…,1000000}
N = ISI = 1000000
5. Delapan kecelakaan terjadi dalam satu minggu. Dengan prinsip inklusi eksklusi,
hitung probabilitas bahwa terdapat paling sedikit satu satu kecelakaan tiap hari!
Jawab:
7 7 7 7 7 7 7
Banyak kecelakaan 1 2 3 4 5 6 7
Hari Sen Sel Rab Kam Jum Sab Ming
Misalkan: S : {semua kejadian kecelakaan yang mungkin terjadi}
𝑎1 : sifat bahwa hari kNe-i tidak terjadi kecelakaan dengan i = { sen sel rab kam jum
sab ming)
𝑁 = [5] = 78
𝑁 = [𝑎𝑛 ] = (7 − 1)8 , 𝐼 𝐸 {1, 2, … … … 7}
𝑁 = (𝑎𝑖 𝑎𝑗 ) = (7 − 2)8 ,𝑖 ≠ 𝑗
𝑁 = (𝑎𝑖 𝑎𝑗 𝑎𝑘 ) = (7 − 3)8 , 𝑖, 𝑗, 𝑘 𝑏𝑒𝑟𝑏𝑒𝑑𝑎
8
𝑁 = (𝑎𝑖 𝑎2……. 𝑎7 ) = (7 − 7) = 0
𝑁 = (𝑎𝑖 𝑎12 … … 𝑎17 ) = 𝑁 − ∑ 𝑁(𝑎𝑖 𝑎𝑗 ) − ⋯ … … … + (−1)7𝑁( (𝑎1 𝑎2……. 𝑎7 )
𝑖,𝑗 𝑏𝑒𝑟𝑏𝑒𝑑𝑎
= 7 − (17 )(7 − 1)8 + (27 )(7 − 2)8 − (37 )(7 − 3)8
8
7. Diketahui X={1, 2, 3, ... , k} dan Y={1, 2, 3, ... , n}. Dengan prinsip inklusi-eksklusi
tunjukkan bahwa banyaknya fungsi sujektif dari X ke Y adalah:
𝑛𝑘 − ∑𝑛𝑗=0(−1)𝑗−𝑖 (𝑛𝑗) (𝑛 − 𝑗)𝑘 .
10. Hitunglah banyaknya permutasi dari {1, 2, 3, … , n} sedemikian hingga terdapat tepat
k bilangan menempati tempatnya semula!