Derangemang

Inom matematiken är ett derangemang eller derangement, en permutation utan fixpunkter på en mängd. Med andra ord är permutationen

${\displaystyle \sigma :M\rightarrow M\,}$

ett derangemang, om σ(x) inte är lika med x för något enda x i M.

Om M är en ändlig mängd av storlek n, så är antalet derangemang på M

${\displaystyle \sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}}\,,}$ för n = 1, 2, 3, 4, 5, 6, blir denna summa respektive 0, 1, 2, 9, 44, 265.

Summan kan även beräknas rekursivt med formeln: ${\displaystyle M(n)=nM(n-1)+(-1)^{n}}$, vilka tal kallas för De Montmort-tal.

Summan kan beräknas medelst principen om inklusion-exklusion, där n! är fakulteten av n. För stora n betyder detta, att antalet derangemang ligger mycket nära n!/e, där e är basen för de naturliga logaritmerna.

En ofta förekommande sannolikhetsteoretisk formulering av detta illustreras av följande berättelse, eller av någon av variant av den:

Ett stort antal herrar har hängt av sig sina hattar inför en herrmiddag. Av någon orsak har herrarna när de skall åka hem inte längre lika stor sinnesnärvaro som förut, och därför tar var och en helt slumpmässigt en av hattarna. Fråga: Hur stor är sannolikheten att ingen herre kommer hem med sin egen hatt?

Svaret på frågan är alltså "Nästan precis e^-1". (Om antalet herrar var n, så är det exakta svaret summan ovan dividerad med n!, vilket är en delsumma i taylorutvecklingen av e^-1.)

Källa

• Donald E. Knuth, The Art of Computer Programming, Volume 1, Fundamental Algorithms, First Edition, 1968.