A116725 Number of permutations of length n which avoid the patterns 132, 3421, 4231.

1, 2, 5, 12, 26, 52, 99, 184, 340, 632, 1189, 2268, 4382, 8556, 16839, 33328, 66216, 131888, 263113, 525428, 1049906, 2098692, 4196075, 8390632, 16779516, 33557032, 67111789, 134221004, 268439110, 536874972, 1073746319, 2147488608, 4294972752, 8589940576

Offset

1,2

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

Index entries for linear recurrences with constant coefficients, signature (6,-14,16,-9,2).

Formula

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

Row sums of triangle A134398. Also, binomial transform of [1, 1, 2, 2, 1, 1, 1, ...]. - Gary W. Adamson, Oct 23 2007

From Colin Barker, Oct 20 2017: (Start)

a(n) = (3*2^n + 2*n - 3*n^2 + n^3)/6.

a(n) = 6*a(n-1) - 14*a(n-2) + 16*a(n-3) - 9*a(n-4) + 2*a(n-5) for n>5.

(End)

Maple

seq((3*2^n +2*n -3*n^2 +n^3)/6, n=1..40); # G. C. Greubel, Nov 29 2019

Mathematica

Table[(3*2^n +2*n -3*n^2 +n^3)/6, {n, 40}] (* G. C. Greubel, Nov 29 2019 *)

Prog

(PARI) Vec(x*(1 -4*x +7*x^2 -6*x^3 +x^4)/((1-x)^4*(1-2*x)) + O(x^40)) \\ Colin Barker, Oct 20 2017
(PARI) vector(40, n, (3*2^n +2*n -3*n^2 +n^3)/6) \\ G. C. Greubel, Nov 29 2019
(Magma) [(3*2^n +2*n -3*n^2 +n^3)/6: n in [1..40]]; // G. C. Greubel, Nov 29 2019
(Sage) [(3*2^n +2*n -3*n^2 +n^3)/6 for n in (1..40)] # G. C. Greubel, Nov 29 2019
(GAP) List([1..40], n-> (3*2^n +2*n -3*n^2 +n^3)/6); # G. C. Greubel, Nov 29 2019

Crossrefs

Cf. A134398.

Sequence in context: A027927 A221948 A116717 * A193263 A221949 A262803

Adjacent sequences: A116722 A116723 A116724 * A116726 A116727 A116728

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved