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
Examples
Since the Catalan numbers count 321-avoiding permutations in S_n, a(8) = 1430 - 4 = 1426 subtracting the four forbidden hexagon patterns.
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).
Programs
-
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 *)
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
Extensions
More terms from Emeric Deutsch, May 04 2004
a(0) prepended by Alois P. Heinz, Sep 21 2014
Comments