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
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).
Crossrefs
Cf. A134398.
Programs
-
GAP
List([1..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
-
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 *) -
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
-
Sage
[(3*2^n +2*n -3*n^2 +n^3)/6 for n in (1..40)] # G. C. Greubel, Nov 29 2019
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)