OFFSET
1,2
LINKS
Colin Barker, Table of n, a(n) for n = 1..1000
B. E. Tenner, Interval structures in the Bruhat and weak orders, arXiv:2001.05011 [math.CO], 2020.
Index entries for linear recurrences with constant coefficients, signature (5,-8,5,-1).
FORMULA
a(n) = Fibonacci(2n-1) + n - 2 = A001519(n) + n - 2.
From Colin Barker, Jan 14 2020: (Start)
G.f.: x*(1 - 3*x + 4*x^2 - 4*x^3 + x^4) / ((1 - x)^2*(1 - 3*x + x^2)).
a(n) = 5*a(n-1) - 8*a(n-2) + 5*a(n-3) - a(n-4) for n>5.
(End)
E.g.f.: 1 + exp((1/2)*(3-sqrt(5))*x)*(3 + sqrt(5) + 2*exp(sqrt(5)*x))/(5 + sqrt(5)) + exp(x)*(x - 2). - Stefano Spezia, Jan 15 2020
EXAMPLE
a(4) = 15 because the permutations with this property in S_4 are all permutations of length < 4.
MATHEMATICA
Join[{1}, Table[Fibonacci[2n-1]+n-2, {n, 2, 30}]] (* or *) LinearRecurrence[ {5, -8, 5, -1}, {1, 2, 6, 15, 37}, 30] (* Harvey P. Dale, Feb 21 2020 *)
PROG
(PARI) Vec(x*(1 - 3*x + 4*x^2 - 4*x^3 + x^4) / ((1 - x)^2*(1 - 3*x + x^2)) + O(x^30)) \\ Colin Barker, Jan 14 2020
(Magma) R<x>:=PowerSeriesRing(Integers(), 30); Coefficients(R!( x*(1-3*x+4*x^2-4*x^3+x^4)/((1-x)^2*(1-3*x+x^2)))); // Marius A. Burtea, Jan 15 2020
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Bridget Tenner, Jan 14 2020
STATUS
approved