login
Smallest fixed point summed over all non-derangement permutations of {1,2,...,n}.
10

%I #25 Jul 16 2023 05:35:46

%S 0,1,1,7,31,191,1331,10655,95887,958879,10547659,126571919,1645434935,

%T 23036089103,345541336531,5528661384511,93987243536671,

%U 1691770383660095,32143637289541787,642872745790835759,13500327661607550919

%N Smallest fixed point summed over all non-derangement permutations of {1,2,...,n}.

%C a(n) is also the number of permutations of {1,2,...,n,n+1} having at least 2 fixed points. Example: a(3)=7 because we have 1234, 1243, 1324, 1432, 2134, 4231, and 3214.

%H Vincenzo Librandi, <a href="/A155521/b155521.txt">Table of n, a(n) for n = 0..200</a>

%H Emeric Deutsch and S. Elizalde, <a href="http://arxiv.org/abs/0904.2792">The largest and the smallest fixed points of permutations</a>, arXiv:0904.2792 [math.CO], 2009.

%F a(n) = (n+1)*a(n-1) +n*(-1)^(n+1); a(0)=0.

%F E.g.f.: (1-(1+x^2)*exp(-x))/(1-x)^2.

%F a(n) = (n+1)!+(-1)^n-2(n+1)*d(n),

%F a(n) = (n+1)!-(n+1)*d(n)-d(n+1), where d(n)=A000166(n) are the derangement numbers.

%F a(n) ~ n!*n*(1-2/e). - _Vaclav Kotesovec_, Oct 20 2012

%F a(n) = Sum_{k=0..n-1} (k+1) * A047920(n-1,k). - _Alois P. Heinz_, Sep 01 2021

%F D-finite with recurrence a(n) +(-n+1)*a(n-1) +(-2*n+1)*a(n-2) +(-n+1)*a(n-3)=0. - _R. J. Mathar_, Jul 26 2022

%e a(3)=7 because the non-derangements of {1,2,3} are 123, 132, 213, 321 with smallest fixed points 1, 1, 3, 2.

%p a[0] := 0: for n to 25 do a[n] := (n+1)*a[n-1]+n*(-1)^(n+1) end do: seq(a[n], n = 0 .. 21);

%t CoefficientList[Series[(1-(1+x^2)*E^(-x))/(1-x)^2, {x, 0, 20}], x]* Range[0, 20]! (* _Vaclav Kotesovec_, Oct 20 2012 *)

%Y Cf. A000166, A047920.

%K nonn

%O 0,4

%A _Emeric Deutsch_, Apr 21 2009