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
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).
Programs
-
GAP
Concatenation([1], List([2..50], 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
-
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 *) -
PARI
vector(50, n, if(n<2, n, 2*n^2-7*n+8)) \\ 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
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
Comments