|
Search: id:A058094
|
|
|
| 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. |
|
+0
9
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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.
|
|
REFERENCES
|
Z. Stankova and J. West, Explicit enumeration of 321, hexagon-avoiding permutations, Discrete Math., 280 (2004), 165-189.
|
|
LINKS
|
S. C. Billey and G. S. Warrington, Kazhdan-Lusztig Polynomials for 321-hexagon-avoiding permutations, J. Alg. Combinatorics, 13, no. 2 (March 2001), 111-136.
|
|
FORMULA
|
a(n+1) = 6a(n) - 11a(n-1) + 9a(n-2) - 4a(n-3) - 4a(n-4) + a(n-5) for n >= 6.
O.g.f.: -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 (mathar(AT)strw.leidenuniv.nl), 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[1]:=1: a[2]:=2: a[3]:=5: a[4]:=14: a[5]:=42: a[6]:=132: for n from 6 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=1..35);
|
|
CROSSREFS
|
Cf. A000108, A092489-A092492.
Sequence in context: A024175 A054393 A036768 this_sequence A080938 A054394 A036769
Adjacent sequences: A058091 A058092 A058093 this_sequence A058095 A058096 A058097
|
|
KEYWORD
|
nice,nonn,easy
|
|
AUTHOR
|
Sara C. Billey (sara(AT)math.mit.edu), Dec 03 2000
|
|
EXTENSIONS
|
More terms from Emeric Deutsch (deutsch(AT)duke.poly.edu), May 04 2004
|
|
|
Search completed in 0.002 seconds
|
