|
%I #54 Sep 29 2020 14:35:21
%S 1,1,1,2,6,14,28,56,118,254,541,1140,2401,5074,10738,22711,48001,
%T 101447,214446,453355,958395,2025963,4282685,9053286,19138115,
%U 40456779,85522862,180789396,382176531,807895636,1707837203,3610252689,7631830480
%N The number of permutations p of {1,...,n} such that p(1)=1, p(n)=n, and |p(i)-p(i+1)| is in {1,2,3} for all i from 1 to n-1.
%C These partitions are qualified as 3-bounded and anchored. The number of 2-bounded anchored partitions of [1..n] is A000930(n). - _Michel Marcus_, Aug 13 2018
%H Andrew Woods, <a href="/A249665/b249665.txt">Table of n, a(n) for n = 1..250</a>
%H Maria M. Gillespie, Kenneth G. Monks, and Kenneth M. Monks, <a href="https://arxiv.org/abs/1808.03573">Enumerating Anchored Permutations with Bounded Gaps</a>, arXiv:1808.03573 [math.CO], 2018. Also Discrete Math.,343 (2020), #111957. (Proves the formulas and conjectures.)
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,2,1,1,0,-1,-1).
%F Let a(1)=1, g(1)=h(1)=0. For all n<1, let a(n)=g(n)=h(n)=0. Then:
%F a(n) = a(n-1) + g(n-1) + h(n-1),
%F g(n) = a(n-2) + a(n-3) + a(n-4) - a(n-6) + g(n-2) + g(n-4) + h(n-2),
%F h(n) = 2*a(n-3) + 2*a(n-4) + a(n-5) - a(n-7) + g(n-3) + g(n-5) + h(n-3).
%F Alternatively, let a(1)=1, a(n)=0 for n<1. Let b(1)=1, b(2)=0, b(3)=1, b(4)=3, b(5)=4, b(6)=5, b(7)=7, b(8)=10, and b(n)=b(n-1)+b(n-3) for n>8. Then:
%F a(n) = a(n-1)*b(1) + a(n-2)*b(2) + a(n-3)*b(3) + ... + a(1)*b(n-1).
%F From _Colin Barker_, Mar 07 2015 and Aug 13 2018: (Start)
%F a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) + a(n-4) + a(n-5) - a(n-7) - a(n-8).
%F G.f.: x*(1 - x - x^3) / (1 - 2*x + x^2 - 2*x^3 - x^4 - x^5 + x^7 + x^8).
%F (End)
%e For n = 5, the a(5) = 6 solutions are 123456, 132456, 134256, 135246, 142356, and 143256.
%t (1 - x - x^3)/(1 - 2x + x^2 - 2x^3 - x^4 - x^5 + x^7 + x^8) + O[x]^33 // CoefficientList[#, x]& (* _Jean-François Alcover_, Sep 23 2018, after _Colin Barker_ *)
%o (PARI) Vec(x*(1 - x - x^3) / (1 - 2*x + x^2 - 2*x^3 - x^4 - x^5 + x^7 + x^8) + O(x^40)) \\ _Colin Barker_, Aug 13 2018
%Y Cf. A000930, A174700, A337654.
%K nonn
%O 1,4
%A _Andrew Woods_, Mar 06 2015
|
