A116726 Number of permutations of length n which avoid the patterns 213, 1234, 2431.

1, 2, 5, 12, 26, 55, 113, 227, 449, 877, 1696, 3254, 6203, 11762, 22205, 41766, 78316, 146467, 273313, 509041, 946531, 1757541, 3259480, 6038576, 11176989, 20671462, 38204837, 70567516, 130275854, 240394475

Offset

1,2

Links

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

Michael Dairyko, Lara Pudwell, Samantha Tyner, Casey Wynn, Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From N. J. A. Sloane, Feb 01 2013

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

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

Formula

G.f.: A(x) = -(x^3-x+1)*x/((x-1)*(x^2+x-1)*(x^3+x^2+x-1)).

2*a(n) = 1 -2*A000045(n+4) +A303005(n+2). - R. J. Mathar, Jan 11 2024

Mathematica

CoefficientList[Series[-(x(x^3-x+1))/((x-1)(x^2+x-1)(x^3+x^2+x-1)), {x, 0, 50}], x] (* Stefano Spezia, Nov 29 2018 *)

Crossrefs

Sequence in context: A360785 A198896 A026688 * A228078 A125180 A073778

Adjacent sequences: A116723 A116724 A116725 * A116727 A116728 A116729

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved