Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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