Düzensizlik (Derangement) Hesaplama

Bu hesaplama hakkında

Düzensizlik (derangement), hiçbir öğenin orijinal konumunda kalmadığı bir permütasyondur — klasik örneği “şapka kontrol problemi”dir: n kişi şapkasını bırakır ve her biri yanlış şapkayla geri döner. Düzensizlik sayısı, !n şeklinde yazılır ve !n = n! × Σ(−1)^k/k! (k = 0'dan n'e) formülünü izler; ayrıca !n = (n−1)(!(n−1) + !(n−2)) şeklindeki sade yineleme bağıntısını da sağlar.

Bu hesaplayıcı, herhangi bir öğe sayısı için !n'i ve rastgele bir permütasyonun bir düzensizlik olma olasılığını hesaplar — n büyüdükçe bu değer hızla 1/e ≈ %36,8'e yakınsar. Kombinatorik ve ayrık matematik derslerinde sıkça kullanılan bir örnektir; altında yatan mantık, sabit noktası olmayan permütasyonları içeren algoritma tasarımı ve kriptografi problemlerinde ve iyi bilinen “Gizli Noel Baba” hediye değişimi bulmacasında karşımıza çıkar.