OFFSET
0,4
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..300
E. Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792v1 [math.CO], 2009.
FORMULA
E.g.f.: (exp(-x) * (1+x+x^2) - 1) / (1-x)^2.
a(n) = Sum(k*A161129(n,k), k=0..n-1).
Recurrence: (n-2)*a(n) = (n^2-2*n-1)*a(n-1) + (n-1)*n*a(n-2). - Vaclav Kotesovec, Oct 20 2012
a(n) ~ n!*n*(3/e-1). - Vaclav Kotesovec, Oct 20 2012
EXAMPLE
a(3)=2 because the non-derangements of {1,2,3} are 1'23', 1'32, 213', and 32'1 with differences between the largest and smallest fixed points (marked) equal to 2, 0, 0, and 0, respectively.
a(4)=13 because the non-derangements of {1,2,3,4} are 1'234', 1'2'43, 1'423, 1'324', 1'342, 1'43'2, 413'2, 3124', 213'4', 42'13, 2314', 243'1, 42'3'1, 32'14', and 32'41 with differences between the largest and smallest fixed points (marked) equal to 3, 1, 0, 3, 0, 2, 0, 0, 1, 0, 0, 0, 1, 2, and 0, respectively.
MAPLE
G := (exp(-x)*(1+x+x^2)-1)/(1-x)^2: Gser := series(G, x = 0, 25): seq(factorial(n)*coeff(Gser, x, n), n = 0 .. 22);
MATHEMATICA
CoefficientList[Series[(E^(-x)*(1+x+x^2)-1)/(1-x)^2, {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 20 2012 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jul 18 2009
STATUS
approved