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

Offset: 1

Author

Andrew Woods, Mar 06 2015

Keywords

• nonn
• easy

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

Examples

			For n = 5, the a(5) = 6 solutions are 123456, 132456, 134256, 135246, 142356, and 143256.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..250 from Andrew Woods).
• Maria M. Gillespie, Kenneth G. Monks, and Kenneth M. Monks, Enumerating Anchored Permutations with Bounded Gaps, arXiv:1808.03573 [math.CO], 2018. Also Discrete Math.,343 (2020), #111957. (Proves the formulas and conjectures.)
• Index entries for linear recurrences with constant coefficients, signature (2,-1,2,1,1,0,-1,-1).

Crossrefs

Cf. A000930, A174700, A337654.

Programs

Magma

R:=PowerSeriesRing(Integers(), 41);
Coefficients(R!( x*(1-x-x^3)/(1-2*x+x^2-2*x^3-x^4-x^5+x^7+x^8) )); // G. C. Greubel, Sep 23 2024

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 *)

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

SageMath

def A249665_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x*(1-x-x^3)/(1-2*x+x^2-2*x^3-x^4-x^5+x^7+x^8) ).list()
a=A249665_list(41); a[1:] # G. C. Greubel, Sep 23 2024

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)