De Montmort-tal

De Montmort-tal eller subfakultet är inom matematik 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), M_n, 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 derangemang. 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:

$M(n)=nM(n-1)+(-1)^{n}$

eller

$M(n)=(n-1)(M(n-1)+M(n-2))\quad M(0)=1\quad M(1)=0$

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!, där Mⁿ kan läsas som M_n, 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

$-1\ \equiv \ (p-1)!\equiv \ (M+1)^{p-1}{\pmod {p}}$.

Enligt ovan fås att M_p = pM_{p - 1} + (-1)^p och således att $M_{p}\equiv \ -1{\pmod {p}}$ och därav erhålles sambandet, $M_{p}\equiv \ (M+1)^{p-1}{\pmod {p}}$. Det senare sambandet kan jämföras med de rekursiva umbrala sambanden för Belltal, där B_n = (B + 1)^{n - 1} och för Bernoullital, där B_n = (B + 1)ⁿ.

Källor

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