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