login
A161130
Sum of the differences between the largest and the smallest fixed points over all non-derangement permutations of {1,2,...,n}.
2
0, 0, 1, 2, 13, 74, 523, 4178, 37609, 376082, 4136911, 49642922, 645357997, 9035011946, 135525179203, 2168402867234, 36862848742993, 663531277373858, 12607094270103319, 252141885402066362, 5294979593443393621
OFFSET
0,4
LINKS
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) = A000166(n+1) - A155521(n).
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