login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 13:42 EST 2019. Contains 319271 sequences. (Running on oeis4.)