Jangan ngeri dulu ngeliat judulnya yang ribet. Sebetulnya ini prinsip inklusi eksklusi ini mudah. Langsung aja kita lihat contoh kasus "Matching Problem".
Soal di atas identik dengan soal berikut:
=======================================================================Ada 10 bola dan 10 kotak. Setiap bola diberi label 1, 2, 3, ..., 10. Begitu pula dengan kotaknya, diberi label 1, 2, 3, ..., 10. Budi menaruh masing-masing bola ke masing-masing kotak secara acak, sehingga sekarang setiap kotak berisi masing-masing satu bola.Pertanyaannya: Berapakah peluang tidak ada satu pun label bola dan kotaknya yang cocok? (misalnya seperti ilustrasi di atas).
Seorang guru ingin mengembalikan sejumlah N PR (pekerjaan rumah) ke N siswa secara acak. Berapakah peluang bahwa tak ada satupun siswa yang mendapatkan PR-nya sendiri? Jika N adalah 30? Apa yang terjadi jika N lebih besar atau lebih kecil?
PENYELESAIAN
Jawabannya adalah 
.Yang mengejutkan adalah peluangnya cenderung mendekati 
atau sekitar 
, berapapun nilai N yang ingin kita ambil, asalkan 
. Silakan dicek sendiri dengan memasukkan nilai N ke fungsi di atas.. Lebih jauh, silakan kalian bereksperimen sendiri dengan memisalkan N, misalnya 3, 4, 5, dan seterusnya.. Lalu, bagaimana hasil tersebut didapat? Bagaimana tiba-tiba muncul nilai 
ini? Lihat lanjutannya di bawah. :)
atau sekitar , berapapun nilai N yang ingin kita ambil, asalkan . Silakan dicek sendiri dengan memasukkan nilai N ke fungsi di atas.. Lebih jauh, silakan kalian bereksperimen sendiri dengan memisalkan N, misalnya 3, 4, 5, dan seterusnya.. Lalu, bagaimana hasil tersebut didapat? Bagaimana tiba-tiba muncul nilai ini? Lihat lanjutannya di bawah. :)Prinsip Inklusi-Ekslusi
Cara untuk menyelesaikan kasus ini adalah dengan prinsip inklusi-eksklusi (atau dikenal dengan sieve prinsiple). Inclusion-Exclusion Prinsiple
________
________
________
________
________
________
________
________
Kalau kalian melihat di rumus di atas (wikipedia), rumus itu terlihat sangat menakutkan, tapi sesungguhnya mudah sekali dijelaskan dengan *bahasa manusia*.. Nah, di post ini, saya ingin menjelaskannya dengan bahasa yang mudah dimengerti.
Ambil contoh:
Misalkan kita punya 2 himpunan, yaitu himpunan
dan 
.
_______
.
_______
.
Untuk menentukan jumlah anggota
, kita gunakan formula berikut:
_______
_______
_______
_______
Jika digambarkan di diagram Venn adalah sbb:
Misalkan kita punya 2 himpunan, yaitu himpunan
dan ._______
._______
.Untuk menentukan jumlah anggota
, kita gunakan formula berikut:_______
_______
_______
_______
Jika digambarkan di diagram Venn adalah sbb:
Ambil contoh lagi:
Misalkan kita punya tiga himpunan, yaitu, , dan 
.
_______.
_______.
_______
Untuk menentukan jumlah anggota
, kita gunakan formula berikut:
Jika digambarkan di diagram Venn adalah sbb:
Misalkan kita punya tiga himpunan, yaitu
, , dan ._______
._______
._______
Untuk menentukan jumlah anggota
, kita gunakan formula berikut:Jika digambarkan di diagram Venn adalah sbb:
Pahami terlebih dahulu bagian yang di atas, karena sesungguhnya prinsipnya sangat mudah.
Untuk seterusnya, misalkan n = 4, berarti ada 4 himpunan, maka formulanya adalah sbb:
________________
________________
________________
Perhatikan bahwa tandanya berselang-seling, dari + ke -, lalu ke + dan ke - lagi. Ini dapat dibuktikan secara prinsip logika. Untuk selanjutnya, kita gunakan singkatan untuk penulisan formula di atas dengan notasi sigma dan pi sbb:
_______
Penyelesaian dengan Prinsip Inklusi-Eksklusi
Kita gunakan kasus bola dan kotak. Misalkan ada N bola dan N kotak.
Kita definisikan set-set himpunan sebagai berikut:
= himp semua urutan dimana urutan pertama pasti benar (bola 1 berpasangan dg kotak 1). = himp semua urutan dimana urutan kedua pasti benar (bola 2 berpasangan dg kotak 2). = himp semua urutan dimana urutan ketiga pasti benar (bola 3 berpasangan dg kotak 3).....
dan seterusnya.
= himpunan semua urutan dimana setidaknya ada 1 urutan (bola dan kotak) yang pasti cocok.Kita gunakan prinsip inklusi-eksklusi untuk menentukan nilai
. = ___________
___________
___________
___________
Keterangan:
berarti himpunan semua urutan dimana urutan ke i , j , ... hingga p benar.Sebagai contoh:
berarti himpunan semua urutan dimana urutan ke 2 dan urutan ke 6 pasti benar (bola 2 berpasangan dg kotak 2; bola 6 berpasangan dg kotak 6).
Perhatikan bahwa banyaknya himpunan itu tidak bergantung pada letak urutan, tapi hanya bergantung pada banyak urutan yang cocok (k). Sebagai contoh: banyaknya himpunan dimana urutan ke 3,6, dan 10 cocok sama dengan banyaknya himpunan dimana urutan ke 2, 8, 9 cocok, dan juga sama dengan banyaknya himpunan dimana urutan ke 1, 3, 4 cocok. Oleh karenanya, secara logika, kita tahu bahwa setiap notasi sigma dapat direpresentasikan sebagai
di mana k adalah jumlah urutan yang pasti benar.
berarti himpunan semua urutan dimana urutan ke 2 dan urutan ke 6 pasti benar (bola 2 berpasangan dg kotak 2; bola 6 berpasangan dg kotak 6).Perhatikan bahwa banyaknya himpunan itu tidak bergantung pada letak urutan, tapi hanya bergantung pada banyak urutan yang cocok (k). Sebagai contoh: banyaknya himpunan dimana urutan ke 3,6, dan 10 cocok sama dengan banyaknya himpunan dimana urutan ke 2, 8, 9 cocok, dan juga sama dengan banyaknya himpunan dimana urutan ke 1, 3, 4 cocok. Oleh karenanya, secara logika, kita tahu bahwa setiap notasi sigma dapat direpresentasikan sebagai
di mana k adalah jumlah urutan yang pasti benar.Jadi, formulanya sekarang adl sbb:
___
___
___
___
___
Untuk menghitung 
, kita tahu bahwa dari n urutan kartu, urutan pertama pasti benar. Oleh karenanya kita tinggal menghitung permutasi sisa urutannya, yaitu 
.
Untuk menghitung
, kita tahu bahwa dari n urutan kartu, ada 2 urutan yang pasti benar (yaitu di urutan pertama dan kedua). Oleh karenanya, banyaknya himpunan ini adalah permutasi sisa urutannya, yaitu 
.
, kita tahu bahwa dari n urutan kartu, urutan pertama pasti benar. Oleh karenanya kita tinggal menghitung permutasi sisa urutannya, yaitu .Untuk menghitung
, kita tahu bahwa dari n urutan kartu, ada 2 urutan yang pasti benar (yaitu di urutan pertama dan kedua). Oleh karenanya, banyaknya himpunan ini adalah permutasi sisa urutannya, yaitu .Untuk selanjutnya, memakai konsep yang sama.
Dengan demikian:
___
___
___
___
___
Kita gunakan notasi sigma untuk
:
Kita tahu bahwa
. Oleh karenanya, dapat disederhanakan menjadi:
Kita tahu banyaknya himpunan yang setidaknya memuat 1 pasang yang cocok. Oleh karenanya, kita dapat menentukan peluangnya.
Dengan demikian,
Berdasarkan deret Taylor, 
, maka untuk nilai n mendekati tak hingga: 
. Artinya, peluangnya mendekati atau sekitar .
Namun, untuk
, nilai ini sudah didekati dengan baik, dan dapat kita anggap bahwa nilai n tidak memberikan pengaruh yang signifikan.
, maka untuk nilai n mendekati tak hingga: . Artinya, peluangnya mendekati atau sekitar .Namun, untuk
, nilai ini sudah didekati dengan baik, dan dapat kita anggap bahwa nilai n tidak memberikan pengaruh yang signifikan.=======================================================================
PENUTUP
Penerapan prinsip eksklusi-inklusi yang lainnya masih banyak. Mungkin akan dijelaskan lain waktu di post yang berikutnya. :)
So, kasus "Matching Problem" sudah kita pecahkan. Karena kemungkinan berhasilnya kecil, jangan coba-coba untuk menjawab ngasal ketika kita menjawab soal bertipe menjodohkan, karena peluang mendapatkan nilai nol adalah 40%. Wakakak.
Ada yang kurang ngerti dengan pembahasan di atas? Sialakn ditanyakan di comment di bawah. :D
So, kasus "Matching Problem" sudah kita pecahkan. Karena kemungkinan berhasilnya kecil, jangan coba-coba untuk menjawab ngasal ketika kita menjawab soal bertipe menjodohkan, karena peluang mendapatkan nilai nol adalah 40%. Wakakak.
Ada yang kurang ngerti dengan pembahasan di atas? Sialakn ditanyakan di comment di bawah. :D
Click Here to Read More..
