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

1, 0, 1, 2, 9, 44, 168, 536, 1661, 5328, 18129, 62592, 214657, 726614, 2438656, 8192120, 27614544, 93315688, 315490856, 1065719578, 3597204049, 12138879608, 40968868129, 138302514360, 466929286109, 1576394674460, 5321736915096, 17964911573280, 60645076322201

Offset: 0

Author

Alois P. Heinz, Jul 05 2015

Keywords

• nonn
• easy

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

Column k=4 of A259776.

Cf. A260092.

Programs

Mathematica

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}]]];
A[n_, k_] := If[k == 0, If[n == 0, 1, 0], b[n, Range[Max[1, n-k], n], k]];
Table[A[n, 4], {n, 0, 30}] (* Jean-François Alcover, Oct 18 2021, after Alois P. Heinz in A259776 *)

Formula

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).