Inclusion Exclusion Principle: Matching Problem

Jangan ngeri dulu ngeliat judulnya yang ribet. Sebetulnya ini prinsip inklusi eksklusi ini mudah. Langsung aja kita lihat contoh kasus "Matching Problem".

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).

Soal di atas identik dengan soal berikut:

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. :)

---

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:

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:

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.

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 .

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.

=======================================================================

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

Sumber:
http://www.math.hmc.edu/funfacts/ffiles/10001.4-6.shtml
http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle