login
A116725
Number of permutations of length n which avoid the patterns 132, 3421, 4231.
2
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
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
KEYWORD
nonn,easy
AUTHOR
Lara Pudwell, Feb 26 2006
STATUS
approved