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,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) = 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

Cf. A000166, A000240, A155521, A161129

Sequence in context: A263840 A307288 A154357 * A192700 A007509 A077413

Adjacent sequences: A161127 A161128 A161129 * A161131 A161132 A161133

Keyword

nonn

Author

Emeric Deutsch, Jul 18 2009

Status

approved