cp's OEIS Frontend

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.

%I A058094 #30 Aug 21 2019 03:08:46
%S A058094 1,1,2,5,14,42,132,429,1426,4806,16329,55740,190787,654044,2244153,
%T A058094 7704047,26455216,90860572,312090478,1072034764,3682565575,
%U A058094 12650266243,43456340025,149282561256,512821712570,1761669869321,6051779569463,20789398928496,71416886375493
%N 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.
%C A058094 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 A058094 Alois P. Heinz, <a href="/A058094/b058094.txt">Table of n, a(n) for n = 0..1000</a>
%H A058094 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 A058094 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 A058094 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (6,-11,9,-4,-4,1).
%F A058094 a(n+1) = 6a(n) - 11a(n-1) + 9a(n-2) - 4a(n-3) - 4a(n-4) + a(n-5) for n >= 5.
%F A058094 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 A058094 Since the Catalan numbers count 321-avoiding permutations in S_n, a(8) = 1430 - 4 = 1426 subtracting the four forbidden hexagon patterns.
%p A058094 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 A058094 LinearRecurrence[{6,-11,9,-4,-4,1},{1,2,5,14,42,132},40] (* _Harvey P. Dale_, Nov 09 2012 *)
%Y A058094 Cf. A000108, A092489, A092490, A092491, A092492, A092493.
%K A058094 nice,nonn,easy
%O A058094 0,3
%A A058094 _Sara Billey_, Dec 03 2000
%E A058094 More terms from _Emeric Deutsch_, May 04 2004
%E A058094 a(0) prepended by _Alois P. Heinz_, Sep 21 2014