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

1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 3, 1, 0, 0, 0, 1, 6, 6, 1, 0, 0, 1, 10, 20, 10, 1, 1, 1, 15, 50, 50, 15, 6, 7, 21, 105, 175, 105, 36, 42, 49, 196, 490, 490, 231, 183, 217, 392, 1176, 1764, 1246, 785, 946, 1141, 2646, 5292, 5418, 3613, 3664, 4390, 6601, 14112, 19614

Offset

0,14

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

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

Formula

a(n) = a(n-3) + 2*a(n-6) + 3*a(n-7) - 2*a(n-9) - 2*a(n-10) - a(n-12) - 2a(n-13) - 3*a(n-14) + a(n-15) + a(n-16) + a(n-17) + a(n-21) for n >= 21.

G.f.: (1 - x)*(1 + x + x^2 - x^6 - 3*x^7 - 3*x^8 - 2*x^9 - x^10 - x^11 - x^12 - x^13)/(1 - x^3 - 2*x^6 - 3*x^7 + 2*x^9 + 2*x^10 + x^12 + 2*x^13 + 3*x^14 - x^15 - x^16 - x^17 - x^21).

Example

a(6) = 1: 561234.
a(7) = 1: 6712345.

Mathematica

CoefficientList[Series[1/((1-x^7-x^6-x^13/(1-x^7-x^6/(1-x^7/(1-x^3))))), {x, 0, 65}], x]

Crossrefs

See A376743 for other sequences related to strongly restricted permutations.

Cf. A377715, A001263.

Sequence in context: A049828 A342557 A377130 * A286131 A285631 A316836

Adjacent sequences: A378002 A378003 A378004 * A378006 A378007 A378008

Keyword

easy,nonn

Author

Michael A. Allen, Nov 13 2024

Status

approved