A387021 Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-2,0,7} for all i=1,...,n.
1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5, 7, 10, 13, 17, 21, 25, 30, 36, 46, 59, 81, 109, 153, 207, 277, 361, 463, 589, 743, 949, 1211, 1589, 2083, 2773, 3670, 4861, 6388, 8344, 10848, 14019, 18166, 23479, 30556, 39762, 52049, 68125, 89345, 117034, 153078, 199979, 260572, 339546, 441669, 575341
Offset: 0
Examples
a(9)=2: 123456789, 891234567.
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
- 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 (1,0,0,0,0,0,0,0,4,-3,3,-2,2,-1,1,0,0,-6,3,-6,2,-3,0,0,0,0,4,-1,3,0,0,0,0,0,0,-1).
Crossrefs
Programs
-
Mathematica
CoefficientList[Series[(1 - 3*x^9 - 2*x^11 - x^13 + 3*x^18 + 2*x^20 - x^27)/ (1 - x - 4*x^9 + 3*x^10 - 3*x^11 + 2*x^12 - 2*x^13 + x^14 - x^15 + 6*x^18 - 3*x^19 + 6*x^20 - 2*x^21 + 3*x^22 - 4*x^27 + x^28 - 3*x^29 + x^36),{x,0,55}],x] LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 0, 4, -3, 3, -2, 2, -1, 1, 0, 0, -6, 3, -6, 2, -3, 0, 0, 0, 0, 4, -1, 3, 0, 0, 0, 0, 0, 0, -1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5, 7, 10, 13, 17, 21, 25, 30, 36, 46, 59, 81, 109, 153, 207, 277, 361, 463, 589, 743, 949, 1211, 1589, 2083, 2773}, 56]
Formula
a(n) = a(n-1) + 4*a(n-9) - 3*a(n-10) + 3*a(n-11) - 2*a(n-12) + 2*a(n-13) - a(n-14) + a(n-15) - 6*a(n-18) + 3*a(n-19) - 6*a(n-20) + 2*a(n-21) - 3*a(n-22) + 4*a(n-27) - a(n-28) + 3*a(n-29) - a(n-36) for n >= 36.
G.f.: (1 - 3*x^9 - 2*x^11 - x^13 + 3*x^18 + 2*x^20 - x^27)/ (1 - x - 4*x^9 + 3*x^10 - 3*x^11 + 2*x^12 - 2*x^13 + x^14 - x^15 + 6*x^18 - 3*x^19 + 6*x^20 - 2*x^21 + 3*x^22 - 4*x^27 + x^28 - 3*x^29 + x^36).