Derangemang

Från Wikipedia
Hoppa till: navigering, sök

Inom matematiken är ett derangemang (ibland stavat derangement) en permutation utan fixpunkter på en mängd. Med andra ord är permutationen

\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, säg av storlek n, så är antalet derangemang på M

\sum_{k=0}^n (-1)^k \frac{n!}{k!} \,,

vilket man kan visa medelst principen om inklusion-exklusion. (Här betecknar n! 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 annolikheten 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.)