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

1, 1, 1, 1, 1, 1, 1, 2, 3, 5, 7, 10, 13, 16, 20, 25, 34, 46, 67, 94, 130, 175, 231, 305, 400, 540, 729, 999, 1363, 1855, 2510, 3370, 4531, 6070, 8180, 11026, 14921, 20197, 27322, 36940, 49820, 67204, 90528, 122091, 164686, 222344, 300316, 405574, 547768, 739291, 997794, 1346130

Offset: 0

Author

Michael A. Allen, Aug 13 2025

Keywords

• easy
• nonn

Examples

			a(7) = 2: 1234567, 6712345.
a(8) = 3: 12345678, 17823456, 67123458.
		

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

• Vladimir Baltić, 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,3,-2,2,-1,1,0,0,-3,1,-2,0,0,0,0,1).

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.

Programs

Mathematica

CoefficientList[Series[(1 - 2*x^7 - x^9 + x^14)/(1 - x - 3*x^7 + 2*x^8 - 2*x^9 + x^10 - x^11 + 3*x^14 - x^15 + 2*x^16 - x^21),{x,0,51}],x]
LinearRecurrence[{1, 0, 0, 0, 0, 0, 3, -2, 2, -1, 1, 0, 0, -3, 1, -2, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 2, 3, 5, 7, 10, 13, 16, 20, 25, 34, 46, 67, 94, 130}, 52]

Formula

a(n) = a(n-1) + 3*a(n-7) - 2*a(n-8) + 2*a(n-9) - a(n-10) + a(n-11) - 3*a(n-14) + a(n-15) - 2*a(n-16) + a(n-21) for n >= 21.

G.f.: (1 - 2*x^7 - x^9 + x^14)/((1 - x)*(1 - x + x^2 - 2*x^3 + x^4 - x^5 - x^7 + x^10)*(1 + x + x^3 + 2*x^4 + x^5 + 2*x^6 + 2*x^7 + x^8 + x^9 + x^10)).