Derangement

Author

Eric W. Weisstein
July 29, 2022

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/Derangement.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Derangement.html.

©2022 Wolfram Research, Inc. except for portions noted otherwise

Enumeration

Combinatorica

Clear[Derangements]

<<Combinatorica`

WFR

https://resources.wolframcloud.com/FunctionRepository/resources/Derangements

ResourceFunction["Derangements"][3]

Length/@Table[ResourceFunction["Derangements"][n],{n,10}]//Timing

PermutationSupport

Permutations[Range[4]]

MyDerangements[l_List]:=With[{perms=Permutations[l]},{supp=PermutationSupport/@perms},
Pick[perms,Length/@supp,Length[l]]
]

MyDerangements[Range[4]]

{Length[%],Subfactorial[4]}

Length/@Table[MyDerangements[Range[n]],{n,10}]//Timing

Subfactorial[Range[8]]

Counts

Subfactorial

Subfactorial[Range[10]]

Recurrence

d[1]:=0
d[2]:=1
d[n_]:=(n-1)(d[n-1]+d[n-2])

Table[d[n],{n,10}]

FullSimplify[RSolve[{d[n]==(n-1)(d[n-1]+d[n-2]),d[1]==0,d[2]==1},d[n],n]]

FullSimplify[RSolve[{d[n]==n d[n-1]+(-1)^n,d[1]==0,d[2]==1},d[n],n]]

FunctionExpand[Table[((Gamma[1+n,-1])/E),{n,10}]]

n! (∑_(k=0)^n)((((-1))^k)/(k!))=((Γ(n+1,-1))/e)

FullSimplify[n!Sum[(-1)^k/k!,{k,0,n}]]

[((n!)/e)]

Table[Round[n!/E],{n,10}]

⌊((n!+1)/e)⌋

Table[Floor[(n!+1)/E],{n,10}]

Limit

<<Graphics`Colors`

ListPlot[Table[{n,((Gamma[n+1,-1])/E)/n!},{n,2,10}],PlotStyle->{PointSize[.02],Red},Prolog->{Blue,Dashing[{.02}],Line[{{0,#},{10,#}}]&[1/E]}]

Table[{n,(1/E)-((Gamma[n+1,-1])/E)/n!},{n,2,6}]//N//Chop

Limit[((#)/(n!)),n->∞]&/@{Subfactorial[n],((Gamma[n+1,-1])/E),Round[n!/E],Floor[(n!+1)/E]}

bug(330559): Limit[Round[n!/E]/n!, n -> Infinity] could return 1/E