This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A249665 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. 1
 1, 1, 1, 2, 6, 14, 28, 56, 118, 254, 541, 1140, 2401, 5074, 10738, 22711, 48001, 101447, 214446, 453355, 958395, 2025963, 4282685, 9053286, 19138115, 40456779, 85522862, 180789396, 382176531, 807895636, 1707837203, 3610252689, 7631830480 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS 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 LINKS Andrew Woods, Table of n, a(n) for n = 1..250 Maria M. Gillespie, Kenneth G. Monks, Kenneth M. Monks, Enumerating Anchored Permutations with Bounded Gaps, arXiv:1808.03573 [math.CO], 2018. Prove the formulas and conjectures. Index entries for linear recurrences with constant coefficients, signature (2,-1,2,1,1,0,-1,-1). FORMULA Let a(1)=1, g(1)=h(1)=0. For all n<1, let a(n)=g(n)=h(n)=0. Then: a(n) = a(n-1) + g(n-1) + h(n-1), g(n) = a(n-2) + a(n-3) + a(n-4) - a(n-6) + g(n-2) + g(n-4) + h(n-2), 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). 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: a(n) = a(n-1)*b(1) + a(n-2)*b(2) + a(n-3)*b(3) + ... + a(1)*b(n-1). From Colin Barker, Mar 07 2015 and Aug 13 2018: (Start) 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). G.f.: x*(1 - x - x^3) / (1 - 2*x + x^2 - 2*x^3 - x^4 - x^5 + x^7 + x^8). (End) EXAMPLE For n = 5, the a(5) = 6 solutions are 123456, 132456, 134256, 135246, 142356, and 143256. MATHEMATICA (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 *) PROG (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 CROSSREFS Cf. A000930, A174700. Sequence in context: A050531 A290699 A027083 * A321027 A214907 A169948 Adjacent sequences:  A249662 A249663 A249664 * A249666 A249667 A249668 KEYWORD nonn AUTHOR Andrew Woods, Mar 06 2015 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 16 12:38 EDT 2019. Contains 325079 sequences. (Running on oeis4.)