A108600 Number of freely braided permutations of length n; the freely braided permutations are those that avoid 3421, 4231, 4312 and 4321.

1, 1, 2, 6, 20, 71, 260, 971, 3674, 14032, 53968, 208692, 810492, 3158760, 12346628, 48377494, 189952216, 747180999, 2943648824, 11612917815, 45869337526, 181372345723, 717856746216, 2843678131629, 11273602645942, 44725291921541, 177551518494116, 705264937798343

Offset: 0

Author

Vincent Vatter, Jun 11 2005

Keywords

• easy
• nonn

Examples

			a(5)=71 because there are 71 permutations of length 5 that avoid 3421, 4231, 4312 and 4321.
		

References

• R. M. Green and J. Losonczy, Freely braided elements of Coxeter groups, Ann. Comb. 6 (2002), 337-348.
• T. Mansour, On an open problem of Green and Losonczy: exact enumeration of freely braided permutations, Discrete Math. Comput. Sci. 6 (2004), 461-470.

Links

• V. Vatter, Enumeration scheme for freely braided permutations.

Formula

G.f. (1-3*x-2*x^2+(1+x)*sqrt(1-4*x)) / (1-4*x-x^2+(1-x^2)*sqrt(1-4*x)).

Conjecture: (1-n)*a(n) +(7*n-10)*a(n-1) +2*(1-4*n)*a(n-2) +8*(11-2*n)*a(n-3) +(n-1)*a(n-4) +3*(2-n)*a(n-5) +2*(11-2*n)*a(n-6)=0. - R. J. Mathar, Aug 24 2013

Extensions

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