A116735 Number of permutations of length n which avoid the patterns 231, 1234, 4312; or avoid the patterns 312, 1234, 1432, etc.

1, 2, 5, 12, 23, 38, 57, 80, 107, 138, 173, 212, 255, 302, 353, 408, 467, 530, 597, 668, 743, 822, 905, 992, 1083, 1178, 1277, 1380, 1487, 1598, 1713, 1832, 1955, 2082, 2213, 2348, 2487, 2630, 2777, 2928, 3083, 3242, 3405, 3572, 3743, 3918, 4097, 4280, 4467

Offset

1,2

Comments

a(n) is the number of permutations pi of length n such that pi and pi^2 both avoid 132 and 3421. - Colin Defant, Jul 24 2019

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Miklos Bona and Rebecca Smith, Pattern Avoidance in Permutations and Their Squares, arXiv:1901.00026 [math.CO], 2019.

Amanda Burcroff and Colin Defant, Pattern-Avoiding Permutation Powers, arXiv:1907.09451 [math.CO], 2019.

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

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

Formula

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

For n >= 2, a(n) = 2*n^2 - 7*n + 8. - Franklin T. Adams-Watters, Sep 16 2006

a(n) = A096376(n-2), n > 1. - R. J. Mathar, Aug 10 2008

E.g.f.: -8 - 2*x + (8 - 5*x + 2*x^2)*exp(x). - G. C. Greubel, Aug 10 2019

Maple

A116735:=n->`if`(n=1, 1, 2*n^2-7*n+8); seq(A116735(n), n=1..50); # G. C. Greubel, Aug 10 2019

Mathematica

Join[{1}, LinearRecurrence[{3, -3, 1}, {2, 5, 12}, 80]] (* Vladimir Joseph Stephan Orlovsky, Feb 18 2012 *)

Prog

(PARI) vector(50, n, if(n<2, n, 2*n^2-7*n+8)) \\ G. C. Greubel, Aug 10 2019
(Magma) [n lt 2 select n else 2*n^2-7*n+8: n in [1..50]]; // G. C. Greubel, Aug 10 2019
(Sage) [1]+[2*n^2-7*n+8 for n in (2..50)] # G. C. Greubel, Aug 10 2019
(GAP) Concatenation([1], List([2..50], n-> 2*n^2-7*n+8)); # G. C. Greubel, Aug 10 2019

Crossrefs

Sequence in context: A247658 A109653 A115520 * A096376 A357288 A326510

Adjacent sequences: A116732 A116733 A116734 * A116736 A116737 A116738

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved