OFFSET
0,3
COMMENTS
If y is 321-hexagon avoiding, there are simple explicit formulas for all the Kazhdan-Lusztig polynomials P_{x,y} and the Kazhdan-Lusztig basis element C_y is the product of C_{s_i}'s corresponding to any reduced word for y.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
S. C. Billey and G. S. Warrington, Kazhdan-Lusztig Polynomials for 321-hexagon-avoiding permutations, arXiv:math/0005052 [math.CO], 2000; J. Alg. Combinatorics, Vol. 13, No. 2 (March 2001), 111-136, DOI:10.1023/A:1011279130416.
Z. Stankova and J. West, Explicit enumeration of 321, hexagon-avoiding permutations, Discrete Math., 280 (2004), 165-189.
Index entries for linear recurrences with constant coefficients, signature (6,-11,9,-4,-4,1).
FORMULA
a(n+1) = 6a(n) - 11a(n-1) + 9a(n-2) - 4a(n-3) - 4a(n-4) + a(n-5) for n >= 5.
O.g.f.: 1 -x*(1-4*x+4*x^2-3*x^3-x^4+x^5)/(-1+6*x-11*x^2+9*x^3-4*x^4 -4*x^5 +x^6). - R. J. Mathar, Dec 02 2007
EXAMPLE
Since the Catalan numbers count 321-avoiding permutations in S_n, a(8) = 1430 - 4 = 1426 subtracting the four forbidden hexagon patterns.
MAPLE
a[0]:=1: a[1]:=1: a[2]:=2: a[3]:=5: a[4]:=14: a[5]:=42: for n from 5 to 35 do a[n+1]:=6*a[n]-11*a[n-1]+9*a[n-2]-4*a[n-3]-4*a[n-4]+a[n-5] od: seq(a[n], n=0..35);
MATHEMATICA
LinearRecurrence[{6, -11, 9, -4, -4, 1}, {1, 2, 5, 14, 42, 132}, 40] (* Harvey P. Dale, Nov 09 2012 *)
CROSSREFS
KEYWORD
nice,nonn,easy
AUTHOR
Sara Billey, Dec 03 2000
EXTENSIONS
More terms from Emeric Deutsch, May 04 2004
a(0) prepended by Alois P. Heinz, Sep 21 2014
STATUS
approved