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.

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

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

Cf. A000108, A092489, A092490, A092491, A092492, A092493.

Sequence in context: A261589 A036768 A287970 * A080938 A054394 A261590

Adjacent sequences: A058091 A058092 A058093 * A058095 A058096 A058097

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