A387021 Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-2,0,7} for all i=1,...,n.

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5, 7, 10, 13, 17, 21, 25, 30, 36, 46, 59, 81, 109, 153, 207, 277, 361, 463, 589, 743, 949, 1211, 1589, 2083, 2773, 3670, 4861, 6388, 8344, 10848, 14019, 18166, 23479, 30556, 39762, 52049, 68125, 89345, 117034, 153078, 199979, 260572, 339546, 441669, 575341

Offset

0,10

References

D. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), North-Holland, Amsterdam, 1970, pp. 755-770.

Links

Table of n, a(n) for n=0..55.

V. Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics, 4(1) (2010), 119-135.

Kenneth Edwards and Michael A. Allen, Strongly restricted permutations and tiling with fences, Discrete Applied Mathematics, 187 (2015), 82-90.

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,4,-3,3,-2,2,-1,1,0,0,-6,3,-6,2,-3,0,0,0,0,4,-1,3,0,0,0,0,0,0,-1).

Formula

a(n) = a(n-1) + 4*a(n-9) - 3*a(n-10) + 3*a(n-11) - 2*a(n-12) + 2*a(n-13) - a(n-14) + a(n-15) - 6*a(n-18) + 3*a(n-19) - 6*a(n-20) + 2*a(n-21) - 3*a(n-22) + 4*a(n-27) - a(n-28) + 3*a(n-29) - a(n-36) for n >= 36.

G.f.: (1 - 3*x^9 - 2*x^11 - x^13 + 3*x^18 + 2*x^20 - x^27)/ (1 - x - 4*x^9 + 3*x^10 - 3*x^11 + 2*x^12 - 2*x^13 + x^14 - x^15 + 6*x^18 - 3*x^19 + 6*x^20 - 2*x^21 + 3*x^22 - 4*x^27 + x^28 - 3*x^29 + x^36).

Example

a(9)=2: 123456789, 891234567.

Mathematica

CoefficientList[Series[(1 - 3*x^9 - 2*x^11 - x^13 + 3*x^18 + 2*x^20 - x^27)/ (1 - x - 4*x^9 + 3*x^10 - 3*x^11 + 2*x^12 - 2*x^13 + x^14 - x^15 + 6*x^18 - 3*x^19 + 6*x^20 - 2*x^21 + 3*x^22 - 4*x^27 + x^28 - 3*x^29 + x^36), {x, 0, 55}], x]
LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 0, 4, -3, 3, -2, 2, -1, 1, 0, 0, -6, 3, -6, 2, -3, 0, 0, 0, 0, 4, -1, 3, 0, 0, 0, 0, 0, 0, -1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5, 7, 10, 13, 17, 21, 25, 30, 36, 46, 59, 81, 109, 153, 207, 277, 361, 463, 589, 743, 949, 1211, 1589, 2083, 2773}, 56]

Crossrefs

Sequences for numbers of permutations such that p(i)-i is in {-2,0,d} for d=1,...,8: A000930, A006498, A080000, A224809, A387020, A224808, A387021, A224811.

Sequence in context: A090499 A229170 A022335 * A022780 A075353 A132278

Adjacent sequences: A387018 A387019 A387020 * A387022 A387023 A387024

Keyword

easy,nonn

Author

Michael A. Allen, Aug 13 2025

Status

approved