A058094 - OEIS

%I #30 Aug 21 2019 03:08:46

%S 1,1,2,5,14,42,132,429,1426,4806,16329,55740,190787,654044,2244153,

%T 7704047,26455216,90860572,312090478,1072034764,3682565575,

%U 12650266243,43456340025,149282561256,512821712570,1761669869321,6051779569463,20789398928496,71416886375493

%N 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.

%C 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.

%H Alois P. Heinz, <a href="/A058094/b058094.txt">Table of n, a(n) for n = 0..1000</a>

%H S. C. Billey and G. S. Warrington, <a href="https://arxiv.org/abs/math/0005052">Kazhdan-Lusztig Polynomials for 321-hexagon-avoiding permutations</a>, arXiv:math/0005052 [math.CO], 2000; J. Alg. Combinatorics, Vol. 13, No. 2 (March 2001), 111-136, DOI:<a href="https://doi.org/10.1023/A:1011279130416">10.1023/A:1011279130416</a>.

%H Z. Stankova and J. West, <a href="https://doi.org/10.1016/j.disc.2003.06.003">Explicit enumeration of 321, hexagon-avoiding permutations</a>, Discrete Math., 280 (2004), 165-189.

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (6,-11,9,-4,-4,1).

%F a(n+1) = 6a(n) - 11a(n-1) + 9a(n-2) - 4a(n-3) - 4a(n-4) + a(n-5) for n >= 5.

%F 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

%e Since the Catalan numbers count 321-avoiding permutations in S_n, a(8) = 1430 - 4 = 1426 subtracting the four forbidden hexagon patterns.

%p 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);

%t LinearRecurrence[{6,-11,9,-4,-4,1},{1,2,5,14,42,132},40] (* _Harvey P. Dale_, Nov 09 2012 *)

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

%K nice,nonn,easy

%O 0,3

%A _Sara Billey_, Dec 03 2000

%E More terms from _Emeric Deutsch_, May 04 2004

%E a(0) prepended by _Alois P. Heinz_, Sep 21 2014