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

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

Offset

1,2

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

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

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

Example

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

Crossrefs

Sequence in context: A145138 A000707 A129777 * A274484 A128729 A006027

Adjacent sequences: A108597 A108598 A108599 * A108601 A108602 A108603

Keyword

easy,nonn

Author

Vincent Vatter, Jun 11 2005

Status

approved