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

Author

Bridget Tenner, Jan 14 2020

Keywords

• easy
• nonn

Examples

			a(4) = 15 because the permutations with this property in S_4 are all permutations of length < 4.
		

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

Crossrefs

Cf. A001519.

Programs

Magma

R:=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

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

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

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