login
Number of permutations p of {1,2,...,n} such that p(i)-i != 1 and p(i)-i != 2 for all i.
2

%I #24 Dec 20 2020 08:16:16

%S 1,1,1,1,5,23,131,883,6859,60301,591605,6405317,75843233,974763571,

%T 13512607303,200949508327,3190881283415,53880906258521,

%U 964039575154409,18217997734199113,362584510633666621,7580578211464070863,166099466140519353035,3806162403831340850651

%N Number of permutations p of {1,2,...,n} such that p(i)-i != 1 and p(i)-i != 2 for all i.

%H Alois P. Heinz, <a href="/A078509/b078509.txt">Table of n, a(n) for n = 0..450</a>

%F From _Vladeta Jovovic_, Jul 16 2007: (Start)

%F G.f.: x/(1+x)*Sum_{n>=0} (n+1)!*(x/(1+x)^2)^n.

%F a(n) = Sum_{k=1..n} (-1)^(n-k)*k!*binomial(n+k-2,2*k-2). (End)

%F a(n) ~ exp(-2) * n!. - _Vaclav Kotesovec_, Aug 25 2014

%p a:= proc(n) option remember; `if`(n<4, 1,

%p (n-1)*a(n-1) +(n-3)*a(n-2) +a(n-3))

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jan 10 2014

%t a = DifferenceRoot[Function[{y, n}, {-y[n] - n y[n+1] - (n+2) y[n+2] + y[n+3] == 0, y[0] == 1, y[1] == 1, y[2] == 1, y[3] == 1}]];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Dec 20 2020, after _Alois P. Heinz_ *)

%Y Cf. A000255, A055790, A001883, A001887, A075851, A075852.

%K nonn

%O 0,5

%A _Vladimir Baltic_, _Vladeta Jovovic_, Jan 05 2003

%E More terms from _Alois P. Heinz_, Jan 10 2014