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,10

References

Allen, Michael A., and Kenneth Edwards. "Identities relating permanents of some classes of (0, 1) Toeplitz matrices to generalized Fibonacci numbers." The Fibonacci Quarterly 63.2 (2025): 163-177.

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

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

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

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

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

Crossrefs

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

Sequence in context: A091349 A103483 A170934 * A058619 A198999 A095945

Adjacent sequences: A079996 A079997 A079998 * A080000 A080001 A080002

Keyword

nonn,easy

Author

Vladimir Baltic, Feb 10 2003

Status

approved