De Montmort-tal

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

De Montmort-tal eller subfakultet är inom matematik är de tal som anger hur många fixpunktsfria permutationer som finns av elementen i mängden N = {1,..., n}, med n som parameter. Det finns flera beteckningar för dessa tal, däribland M(n), h(n, 0), Mn, n¡ och !n. Den första beteckningen har sitt ursprung från den franske matematikern Pierre Rémond de Montmort och den andra från matematikern Donald Knuth.

På engelska kallas en fixpunktsfri permutation för "derangement", vilket kan översättas med oordning eller derangering. Antalet fixpunktsfria permutationer av elementen i mängden N, är antalet bijektiva avbildningar av mängden på sig själv, sådana att inget element avbildas på sig självt. Alternativt kan M(n) beskrivas som antalet sätt att dela in mängden N = {1,..., n} i cykler av längd n > 1. Antalet kan beräknas rekursivt:

eller

Således blir M(2) = 1, M(3) = 2, M(4) = 9, M(5) = 44, M(6) = 265, etc.

Det gäller även att (M + 1)n = n!, där Mn kan läsas som Mn, dvs så kallad umbral algebra tillämpas. Om n = p, där p är ett primtal, så fås med hjälp av Wilsons sats att

.

Enligt ovan fås att Mp = pMp - 1 + (-1)p och således att och därav erhålles sambandet, . Det senare sambandet kan jämföras med de rekursiva umbrala sambanden för Belltal, där Bn = (B + 1)n - 1 och för Bernoullital, där Bn = (B + 1)n.

Källor[redigera | redigera wikitext]

  • Donald E. Knuth, The Art of Computer Programming, Volume 1, Fundamental Algorithms, First Edition, 1968.
  • Concrete Mathematics, Graham, Knuth, Patashnik, Second Edition 1994.