A331347 Number of permutations w in S_n that form Boolean intervals [s, w] in the Bruhat order for every simple reflection s in the support of w.

1, 2, 6, 15, 37, 93, 238, 616, 1604, 4189, 10955, 28667, 75036, 196430, 514242, 1346283, 3524593, 9227481, 24157834, 63246004, 165580160, 433494457, 1134903191, 2971215095, 7778742072, 20365011098, 53316291198, 139583862471, 365435296189, 956722026069

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

Cf. A001519.

Sequence in context: A098790 A300344 A018019 * A306463 A034518 A260787

Adjacent sequences: A331344 A331345 A331346 * A331348 A331349 A331350

Keyword

easy,nonn

Author

Bridget Tenner, Jan 14 2020

Status

approved