login
A116735
Number of permutations of length n which avoid the patterns 231, 1234, 4312; or avoid the patterns 312, 1234, 1432, etc.
2
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
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.
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
KEYWORD
nonn,easy
AUTHOR
Lara Pudwell, Feb 26 2006
STATUS
approved