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

1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 3, 1, 0, 0, 1, 6, 6, 1, 1, 1, 10, 20, 10, 5, 6, 15, 50, 50, 25, 30, 36, 105, 175, 125, 115, 141, 231, 490, 525, 435, 541, 673, 1246, 1820, 1695, 1901, 2361, 3361, 5501, 6301, 6601, 8295, 10440, 15820, 21410, 23286

Offset

0,12

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

Michael A. Allen and Kenneth Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, Lin. Multilin. Alg. 72:13 (2024) 2091-2103.

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 (0,0,1,0,2,2,0,-1,-2,-1,-1,-1,0,0,1).

Formula

a(n) = a(n-3) + 2*a(n-5) + 2*a(n-6) - a(n-8) - 2*a(n-9) - a(n-10) - a(n-11) - a(n-12) + a(n-15) for n >= 15.

G.f.: (1 - x^3 - x^5 - x^6 + x^9)/(1 - x^3 - 2*x^5 - 2*x^6 + x^8 + 2*x^9 + x^10 + x^11 + x^12 - x^15).

Example

a(5) = 1: 45123.
a(6) = 1: 561234.

Mathematica

CoefficientList[Series[(1 - x^3 - x^5 - x^6 + x^9)/(1 - x^3 - 2*x^5 - 2*x^6 + x^8 + 2*x^9 + x^10 + x^11 + x^12 - x^15), {x, 0, 56}], x]
LinearRecurrence[{0, 0, 1, 0, 2, 2, 0, -1, -2, -1, -1, -1, 0, 0, 1}, {1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 3, 1, 0, 0}, 57]

Crossrefs

See A376743 for other sequences related to strongly restricted permutations.

Sequence in context: A110319 A036872 A036871 * A036876 A229038 A229143

Adjacent sequences: A377712 A377713 A377714 * A377716 A377717 A377718

Keyword

easy,nonn

Author

Michael A. Allen, Nov 04 2024

Status

approved