%I #15 Oct 08 2016 10:43:30
%S 0,0,1,2,13,74,523,4178,37609,376082,4136911,49642922,645357997,
%T 9035011946,135525179203,2168402867234,36862848742993,663531277373858,
%U 12607094270103319,252141885402066362,5294979593443393621
%N Sum of the differences between the largest and the smallest fixed points over all non-derangement permutations of {1,2,...,n}.
%H Vincenzo Librandi, <a href="/A161130/b161130.txt">Table of n, a(n) for n = 0..300</a>
%H E. Deutsch and S. Elizalde, <a href="http://arxiv.org/abs/0904.2792">The largest and the smallest fixed points of permutations</a>, arXiv:0904.2792v1 [math.CO], 2009.
%F E.g.f.: (exp(-x) * (1+x+x^2) - 1) / (1-x)^2.
%F a(n) = A000166(n+1) - A155521(n).
%F a(n) = Sum(k*A161129(n,k), k=0..n-1).
%F Recurrence: (n-2)*a(n) = (n^2-2*n-1)*a(n-1) + (n-1)*n*a(n-2). - _Vaclav Kotesovec_, Oct 20 2012
%F a(n) ~ n!*n*(3/e-1). - _Vaclav Kotesovec_, Oct 20 2012
%e 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.
%e 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.
%p 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);
%t CoefficientList[Series[(E^(-x)*(1+x+x^2)-1)/(1-x)^2, {x, 0, 20}], x]* Range[0, 20]! (* _Vaclav Kotesovec_, Oct 20 2012 *)
%Y Cf. A000166, A000240, A155521, A161129
%K nonn
%O 0,4
%A _Emeric Deutsch_, Jul 18 2009
|