OFFSET
0,4
COMMENTS
a(n) is also the number of permutations of {1,2,...,n,n+1} having at least 2 fixed points. Example: a(3)=7 because we have 1234, 1243, 1324, 1432, 2134, 4231, and 3214.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..200
Emeric Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792 [math.CO], 2009.
FORMULA
a(n) = (n+1)*a(n-1) +n*(-1)^(n+1); a(0)=0.
E.g.f.: (1-(1+x^2)*exp(-x))/(1-x)^2.
a(n) = (n+1)!+(-1)^n-2(n+1)*d(n),
a(n) = (n+1)!-(n+1)*d(n)-d(n+1), where d(n)=A000166(n) are the derangement numbers.
a(n) ~ n!*n*(1-2/e). - Vaclav Kotesovec, Oct 20 2012
a(n) = Sum_{k=0..n-1} (k+1) * A047920(n-1,k). - Alois P. Heinz, Sep 01 2021
D-finite with recurrence a(n) +(-n+1)*a(n-1) +(-2*n+1)*a(n-2) +(-n+1)*a(n-3)=0. - R. J. Mathar, Jul 26 2022
EXAMPLE
a(3)=7 because the non-derangements of {1,2,3} are 123, 132, 213, 321 with smallest fixed points 1, 1, 3, 2.
MAPLE
a[0] := 0: for n to 25 do a[n] := (n+1)*a[n-1]+n*(-1)^(n+1) end do: seq(a[n], n = 0 .. 21);
MATHEMATICA
CoefficientList[Series[(1-(1+x^2)*E^(-x))/(1-x)^2, {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 20 2012 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Apr 21 2009
STATUS
approved