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, 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: 0

Author

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

Keywords

• nonn

Comments

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

Examples

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

References

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

Links

• 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).

Crossrefs

Cf. A058094, A108600.

Programs

Mathematica

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

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

Formula

G.f.: 1+(-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).

Extensions

More terms from Michel Marcus, Mar 17 2013

a(0)=1 prepended by Alois P. Heinz, Jan 12 2025