cp's OEIS Frontend

A259777 Number of permutations p of [n] with no fixed points and displacement of elements restricted by four: 1 <= |p(i)-i| <= 4.

%I A259777 #14 Oct 18 2021 11:15:48
%S A259777 1,0,1,2,9,44,168,536,1661,5328,18129,62592,214657,726614,2438656,
%T A259777 8192120,27614544,93315688,315490856,1065719578,3597204049,
%U A259777 12138879608,40968868129,138302514360,466929286109,1576394674460,5321736915096,17964911573280,60645076322201
%N A259777 Number of permutations p of [n] with no fixed points and displacement of elements restricted by four: 1 <= |p(i)-i| <= 4.
%H A259777 Alois P. Heinz, <a href="/A259777/b259777.txt">Table of n, a(n) for n = 0..1000</a>
%F A259777 G.f.: (-x^35 +4*x^33 +2*x^32 -3*x^31 -3*x^30 +9*x^29 -10*x^28 +8*x^27 -9*x^26 -61*x^25 -39*x^24 +62*x^23 -12*x^22 -176*x^21 +95*x^20 +36*x^19 -10*x^18 +58*x^17 +132*x^16 -81*x^15 +38*x^14 +166*x^13 -104*x^12 +35*x^11 -51*x^10 -135*x^9 +36*x^8 -10*x^7 +3*x^6 +27*x^5 -x^4 +2*x^2 +2*x -1) / (x^43 -5*x^41 -x^39 +x^38 +13*x^37 -5*x^36 +x^35 +15*x^34 +93*x^33 +15*x^32 +7*x^31 -11*x^30 +7*x^29 -7*x^28 -97*x^27 -215*x^26 -731*x^25 -437*x^24 +339*x^23 -323*x^22 -941*x^21 +85*x^20 +605*x^19 -61*x^18 +715*x^17 +1045*x^16 -317*x^15 +213*x^14 +535*x^13 -255*x^12 -151*x^11 -273*x^10 -323*x^9 -37*x^8 +9*x^7 +55*x^6 +47*x^5 +x^4 +3*x^2 +2*x -1).
%t A259777 b[n_, s_, k_] := b[n, s, k] = If[n == 0, 1, If[MemberQ[s, n + k], b[n - 1, Join[s ~Complement~ {n + k}] ~Union~ If[n - k > 1, {n - k - 1}, {}], k], Sum[If[j == n, 0, b[n - 1, Join[s ~Complement~ {j}] ~Union~ If[n - k > 1, {n - k - 1}, {}], k]], {j, s}]]];
%t A259777 A[n_, k_] := If[k == 0, If[n == 0, 1, 0], b[n, Range[Max[1, n-k], n], k]];
%t A259777 Table[A[n, 4], {n, 0, 30}] (* _Jean-François Alcover_, Oct 18 2021, after _Alois P. Heinz_ in A259776 *)
%Y A259777 Column k=4 of A259776.
%Y A259777 Cf. A260092.
%K A259777 nonn,easy
%O A259777 0,4
%A A259777 _Alois P. Heinz_, Jul 05 2015