A129777 Number of freely-braided hexagon-avoiding permutations in S_n; the freely-braided hexagon-avoiding permutations are those that avoid 3421, 4231, 4312, 4321, 46718235, 46781235, 56718234 and 56781234.

1, 2, 6, 20, 71, 260, 971, 3670, 13968, 53369, 204352, 783408, 3005284, 11533014, 44267854, 169935041, 652385639, 2504613713, 9615798516, 36917689075, 141737959416, 544175811783, 2089262741393, 8021347093432, 30796530585417, 118237818141689, 453953210838465

Offset

1,2

Comments

If w is freely-braided and hexagon-avoiding, there are simple explicit formulas for all the Kazhdan-Lusztig polynomials P_{x,w}.

References

Jozsef Losonczy, Maximally clustered elements and Schubert varieties, Ann. Comb. 11 (2007), no. 2, 195-212.

Links

Table of n, a(n) for n=1..27.

H. Denoncourt and B. Jones, The enumeration of maximally clustered permutations.

B. Jones, Kazhdan--Lusztig polynomials for maximally-clustered hexagon-avoiding permutations.

Index entries for linear recurrences with constant coefficients, signature (6, -9, 3, 1, -8, -1, 1).

Formula

G.f.: (-x^7-2x^6+2x^5+x^4-3x^3+4x^2-x) / (x^7-x^6-8x^5+x^4+3x^3-9x^2+6x-1).

Example

a(8)=3670 because there are 3670 permutations of size 8 that avoid 3421, 4231, 4312, 4321, 46718235, 46781235, 56718234 and 56781234.

Mathematica

LinearRecurrence[{6, -9, 3, 1, -8, -1, 1}, {1, 2, 6, 20, 71, 260, 971}, 27] (* Jean-François Alcover, Feb 02 2019 *)

Prog

(PARI) lista(nt) = { my(x = 'x + 'x*O('x^nt) ); P = (-x^7-2*x^6+2*x^5+x^4-3*x^3+4*x^2-x) / (x^7-x^6-8*x^5+x^4+3*x^3-9*x^2+6*x-1); print(Vec(P)); }  \\ Michel Marcus, Mar 17 2013

Crossrefs

Cf. A058094, A108600.

Sequence in context: A376792 A145138 A000707 * A108600 A274484 A128729

Adjacent sequences: A129774 A129775 A129776 * A129778 A129779 A129780

Keyword

nonn

Author

Brant Jones (brant(AT)math.washington.edu), May 17 2007

Extensions

More terms from Michel Marcus, Mar 17 2013

Status

approved