A377715 - OEIS

%I #9 Nov 08 2024 11:37:56

%S 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,

%T 30,36,105,175,125,115,141,231,490,525,435,541,673,1246,1820,1695,

%U 1901,2361,3361,5501,6301,6601,8295,10440,15820,21410,23286

%N 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.

%D 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.

%H Michael A. Allen and Kenneth Edwards, <a href="https://doi.org/10.1080/03081087.2022.2107979">Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices</a>, Lin. Multilin. Alg. 72:13 (2024) 2091-2103.

%H V. Baltic, <a href="http://pefmath.etf.rs/vol4num1/AADM-Vol4-No1-119-135.pdf">On the number of certain types of strongly restricted permutations</a>, Applicable Analysis and Discrete Mathematics, 4(1) (2010), 119-135.

%H Kenneth Edwards and Michael A. Allen, <a href="https://doi.org/10.1016/j.dam.2015.02.004">Strongly restricted permutations and tiling with fences</a>, Discrete Applied Mathematics, 187 (2015), 82-90.

%H <a href="/index/Rec#order_15">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,1,0,2,2,0,-1,-2,-1,-1,-1,0,0,1).

%F 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.

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

%e a(5) = 1: 45123.

%e a(6) = 1: 561234.

%t 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]

%t 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]

%Y See A376743 for other sequences related to strongly restricted permutations.

%K easy,nonn

%O 0,12

%A _Michael A. Allen_, Nov 04 2024