A161130 Sum of the differences between the largest and the smallest fixed points over all non-derangement permutations of {1,2,...,n}.
0, 0, 1, 2, 13, 74, 523, 4178, 37609, 376082, 4136911, 49642922, 645357997, 9035011946, 135525179203, 2168402867234, 36862848742993, 663531277373858, 12607094270103319, 252141885402066362, 5294979593443393621
Offset: 0
Keywords
Examples
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.
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.
Programs
-
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 *)
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