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

1, 0, 0, 0, 1, 1, 1, 1, 1, 4, 4, 5, 7, 10, 16, 22, 29, 40, 60, 84, 118, 165, 230, 330, 466, 653, 919, 1297, 1831, 2585, 3640, 5124, 7233, 10201, 14380, 20272, 28572, 40289, 56816, 80096, 112912, 159196, 224449, 316456, 446164, 629004, 886821, 1250329, 1762801

Offset: 0

Author

Vladimir Baltic, Feb 10 2003

Keywords

• nonn
• easy
• changed

References

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

Links

• Michael A. Allen and Kenneth Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, Linear and Multilinear Algebra, 72:13 (2024), 2091-2103.
• Michael A. Allen and Kenneth Edwards, Identities relating permanents of some classes of (0,1) Toeplitz matrices to generalized Fibonacci numbers, Fibonacci Quarterly, 63:2 (2025), 163-177.
• Vladimir 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 (0,0,1,1,2,1,0,-1,0,-1).

Crossrefs

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014, A376743.

Programs

Mathematica

LinearRecurrence[{0,0,1,1,2,1,0,-1,0,-1},{1,0,0,0,1,1,1,1,1,4},50] (* Harvey P. Dale, Dec 12 2024 *)

Formula

Recurrence: a(n) = a(n-3) + a(n-4) + 2*a(n-5) + a(n-6) - a(n-8) - a(n-10) for n>=10.

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