Kalkulator Derangement Subfaktorial

Selamat datang di Kalkulator Derangement (Subfaktorial), alat kombinatorika komprehensif yang menghitung jumlah derangement untuk setiap himpunan n elemen. Derangement adalah permutasi di mana tidak ada elemen yang muncul di posisi aslinya, dilambangkan dengan !n atau D(n). Apakah Anda sedang mempelajari kombinatorika, memecahkan masalah klasik pengecekan topi, atau menjelajahi teori probabilitas, kalkulator ini menyediakan solusi langkah demi langkah yang terperinci dengan visualisasi interaktif.

Apa itu Derangement?

Sebuah derangement (juga disebut subfaktorial) adalah permutasi elemen-elemen dari suatu himpunan di mana tidak ada elemen yang muncul di posisi aslinya. Jumlah derangement dari n elemen ditulis sebagai !n (dengan tanda seru sebelum n) atau D(n).

Sebagai contoh, pertimbangkan tiga item dalam posisi {1, 2, 3}. Ada 3! = 6 total permutasi, tetapi hanya 2 yang merupakan derangement:

• (2, 3, 1) — item 1 pindah ke posisi 2, item 2 pindah ke posisi 3, item 3 pindah ke posisi 1
• (3, 1, 2) — item 1 pindah ke posisi 3, item 2 pindah ke posisi 1, item 3 pindah ke posisi 2

Jadi !3 = 2.

Rumus Derangement

Rumus Inklusi-Eksklusi

Rumus yang paling mendasar diturunkan dari prinsip inklusi-eksklusi:

Rumus Rekursif

Derangement juga dapat dihitung secara rekursif:

dengan kasus dasar: !0 = 1, !1 = 0.

Rumus Bilangan Bulat Terdekat

Untuk \(n \geq 1\), subfaktorial sama dengan bilangan bulat terdekat dengan \(n!/e\):

Masalah Pengecekan Topi (The Hat-Check Problem)

Aplikasi derangement yang paling terkenal adalah masalah pengecekan topi (problème des rencontres): jika n tamu menitipkan topi mereka dan topi-topi tersebut dikembalikan secara acak, berapa probabilitas bahwa tidak ada tamu yang mendapatkan topinya sendiri?

Jawabannya adalah \(!n / n!\), yang konvergen sangat cepat ke \(1/e \approx 0,3679\). Ini berarti sekitar 36,8% dari semua permutasi acak adalah derangement, terlepas dari berapa banyak item yang ada.

Cara Menggunakan Kalkulator Ini

1. Masukkan n: Masukkan jumlah elemen (0 hingga 170). Gunakan tombol contoh cepat untuk mencoba nilai umum.
2. Hitung: Klik "Hitung !n" untuk menghitung angka derangement.
3. Tinjau hasil: Lihat !n, n!, probabilitas derangement, dan rasio terhadap 1/e.
4. Jelajahi animasi: Untuk n kecil, berinteraksilah dengan animasi visual untuk melihat bagaimana derangement bekerja.
5. Pelajari langkah-langkahnya: Periksa rincian inklusi-eksklusi yang mendalam dan tabel derangement.

15 Angka Derangement Pertama

Aplikasi Derangement

Secret Santa / Pertukaran Kado

Saat mengatur pertukaran kado Secret Santa, setiap peserta mengambil sebuah nama. Pengambilan yang berhasil di mana tidak ada yang memilih nama mereka sendiri adalah sebuah derangement. Untuk sekelompok 10 orang, terdapat 1.334.961 pengaturan yang valid dari total 3.628.800.

Kriptografi dan Teori Pengkodean

Derangement muncul dalam analisis sandi substitusi dan kode koreksi kesalahan. Konsep "tidak ada titik tetap" (no fixed point) sangat mendasar untuk memahami kekuatan sandi dan enkripsi berbasis permutasi.

Pengocokan Kartu dan Permainan

Dalam permainan kartu, derangement mengukur probabilitas bahwa tidak ada kartu yang kembali ke posisi aslinya setelah dikocok. Ini berguna dalam menganalisis kualitas pengocokan dan keadilan permainan.

Teori Probabilitas

Derangement memberikan contoh elegan dari prinsip inklusi-eksklusi dan mengilustrasikan bagaimana probabilitas dapat berkonvergensi ke limit sederhana (1/e dalam kasus ini).

Properti Utama

• Rasio \(!n/n!\) konvergen ke \(1/e \approx 0,367879\) seiring \(n \to \infty\)
• Konvergensinya sangat cepat — sudah akurat hingga 6 tempat desimal pada n = 10
• \(!n\) memenuhi rekurensi: \(!n = n \cdot !(n-1) + (-1)^n\)
• Fungsi pembangkit eksponensialnya adalah \(e^{-x}/(1-x)\)
• \(!0 = 1\) (permutasi kosong secara hampa adalah derangement)

Pertanyaan yang Sering Diajukan

Apa itu derangement?

Derangement adalah permutasi dari suatu himpunan di mana tidak ada elemen yang muncul di posisi aslinya. Sebagai contoh, jika item diberi label {1, 2, 3}, permutasi (2, 3, 1) adalah derangement karena tidak ada item yang berada di tempat asalnya. Jumlah derangement dari n item dilambangkan !n (subfaktorial n).

Apa rumus untuk subfaktorial !n?

Subfaktorial !n dapat dihitung menggunakan rumus inklusi-eksklusi: \(!n = n! \times \sum_{k=0}^{n} (-1)^k / k!\). Ini juga dapat dihitung secara rekursif: \(!n = (n-1)(!(n-1) + !(n-2))\), dengan !0 = 1 dan !1 = 0. Rumus berguna lainnya adalah \(!n = \text{round}(n! / e)\) untuk \(n \geq 1\).

Berapa probabilitas bahwa permutasi acak adalah sebuah derangement?

Probabilitas bahwa permutasi acak dari n item adalah derangement mendekati \(1/e \approx 0,3679\) seiring bertambahnya n. Bahkan untuk n kecil, pendekatan ini sangat akurat. Untuk n = 5, probabilitas pastinya adalah 44/120 ≈ 0,3667, sudah sangat dekat dengan 1/e.

Apa itu masalah pengecekan topi?

Masalah pengecekan topi (juga dikenal sebagai problème des rencontres) adalah teka-teki probabilitas klasik: jika n orang menitipkan topi mereka di restoran dan topi-topi tersebut dikembalikan secara acak, berapa probabilitas bahwa tidak ada orang yang mendapatkan topinya sendiri kembali? Jawabannya adalah jumlah derangement !n dibagi dengan total permutasi n!, yang mendekati \(1/e \approx 36,79\%\).

Apa hubungan antara derangement dan faktorial?

Derangement (!n) dan faktorial (n!) berkaitan erat: \(!n = n! \times \sum(-1)^k/k!\) untuk k dari 0 sampai n. Rasio !n/n! memberikan probabilitas derangement, yang konvergen ke 1/e. Selain itu, !n adalah bilangan bulat terdekat dengan n!/e untuk \(n \geq 1\), membuat n!/e menjadi pendekatan yang sangat berguna.

Sumber Daya Tambahan

• Derangement - Wikipedia
• Prinsip Inklusi-Eksklusi - Wikipedia
• OEIS A000166 - Deret Subfaktorial