1402/2014: Full Moon Derangement Valentine Day

Pada awalnya, melalui kalender saya hanya mengetahui bahwa Valentine day tahun 2014 bertepatan dengan bulan purnama.  Eksplorasi lebih lanjut menghasilkan sesuatu yang cukup unik dari sudut pandang kombinatorika (cabang matematika yang terkait dengan teknik pencacahan unsur-unsur suatu himpunan).  Apa itu?  Coba perhatikan susunan tanggal-bulan dengan tahunnya:

1	4	0	2
2	0	1	4

Selain susunan digit tanggal-bulannya merupakan salah satu permutasi (susunan berbeda) dari digit tahunnya, permutasi tersebut memiliki susunan digit yang semuanya berbeda dengan susunan digit tahunnya (1≠2, 4≠0, 0≠1, 2≠4).  Susunan yang berbeda semua dengan susunan awalnya inilah di dalam kombinatorika disebut  derangement.  Tentu saja, derangement seperti ini langka karena di waktu mendatang hanya muncul di tahun-tahun {2041, 2140, 4021, 4120, 4210}.

Saya jadi teringat dengan sebuah lagu Sunda berjudul “Anjeun” (Kamu).  Berikut penggalan lagunya:

Dasar kudu kanyahoan
Ngirim surat salah ngasupkeun eusina
Surat sial jeung cilaka
Putus ka ditu ka dieu…

Lagu tersebut berkisah tentang seorang cowok yang mengirimkan dua surat kepada dua ceweq teman dekatnya (sang cowoq tidak menerapkan konsep fungsi 1-1 :-) ).  Yang membuat dia sial, dia salah memasukkan suratnya ke dalam amplop yang telah disiapkannya; surat untuk si A dimasukkan ke amplop si B, surat untuk si B malah dimasukkannya ke amplop si A.  Tamatlah riwayatnya…  

Ini adalah contoh paling sederhana dari derangement dengan dua unsur yang menghasilkan hanya satu cara.  Andaikan kedua unsur tersebut kita lambangkan dengan {1, 2}, maka satu-satunya cara yang menghasilkan susunan yang semuanya berbeda adalah {2, 1}.  Kalau sang cowok mengirimkan suratnya untuk 3 orang teman dekatnya, {1, 2, 3}, maka nasibnya akan diputus oleh ketiganya bila ia memasukkan suratnya secara salah semuanya yang dalam hal ini ada sebanyak 2 cara, yakni: {2, 3, 1} dan {3, 1, 2}.

Derangement dari n unsur berbeda dilambangkan dengan d(n) atau !n (subfaktorial n) merupakan bentuk rekursif:

d(n) = !n = (n - 1) (d(n - 1) + d(n - 2)) , d(0) = 1, d(1) = 0

yang juga akan menghasilkan bentuk:

d(n) = n! (1/0! – 1/1! + 1/2! – … + (-1)ⁿ/n!)

Bentuk d(n) juga memiliki keterkaitan dengan bilangan Euler, e ≈ 2.71828… sbb.

d(n) = !n = [n!/e];   n ≥ 1

lambang [x] menyatakan bilangan bulat terdekat ke x (rounding).

Dengan demikian peluang bahwa dari permutasi n objek berbeda, akan menghasilkan susunan dengan posisi unsur yang berbeda semua adalah !n/n!.  Di dalam teori peluang, untuk n yang besar (n → ∞), peluang ini akan menjadi 1/e ≈ 0.3697…

Dengan Mathematica, derangement dari n unsur dapat dihitung dengan perintah Derangements[n] melalui package Combinatorica`.

Derangements[4]
{{2, 1, 4, 3}, {2, 3, 4, 1}, {2, 4, 1, 3}, {3, 1, 4, 2}, {3, 4, 1, 2}, {3, 4, 2, 1}, {4, 1, 2, 3}, {4, 3, 1, 2}, {4, 3, 2, 1}}

Berikut banyaknya susunan dari 10 derangement pertama dengan perintah Subfactorial.

Table[Subfactorial[n], {n, 1, 10}]
{0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961}

Happy Special Full Moon Derangement Valentine Day… :-)

Artikel terkait:
Teka-teki Matematika Valentine
Matematika Valentine