login
A058094
Number of 321-hexagon-avoiding permutations in S_n, i.e., permutations of 1..n with no submatrix equivalent to 321, 56781234, 46781235, 56718234 or 46718235.
9
1, 1, 2, 5, 14, 42, 132, 429, 1426, 4806, 16329, 55740, 190787, 654044, 2244153, 7704047, 26455216, 90860572, 312090478, 1072034764, 3682565575, 12650266243, 43456340025, 149282561256, 512821712570, 1761669869321, 6051779569463, 20789398928496, 71416886375493
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
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.
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