login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A116768
Number of permutations of length n which avoid the patterns 1342, 3214, 4213.
1
1, 2, 6, 21, 73, 239, 738, 2178, 6220, 17351, 47595, 128985, 346492, 924788, 2456502, 6502017, 17164189, 45219875, 118954134, 312559974, 820560736, 2152792187, 5645155791, 14797355181, 38776269808, 101590174424, 266111693898, 696979788213, 1825297432705
OFFSET
1,2
LINKS
D. Callan, T. Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, arXiv:1705.00933 [math.CO] (2017), Table 2 No 85.
FORMULA
G.f.: x*(1 - 5*x + 10*x^2 - 6*x^3 + 3*x^4) / ((1 - x)^2*(1 - 2*x)*(1 - 3*x + x^2)).
a(n) = 2^(-1-n)*(-7*4^n+5*(3+sqrt(5))^n - sqrt(5)*(3+sqrt(5))^n + (3-sqrt(5))^n*(5+sqrt(5)) + 3*2^(1+n)*n). - Colin Barker, Nov 02 2017
a(n) = 3*n + 5*Fibonacci(2*n - 1) - 7*2^(n - 1). - Ehren Metcalfe, Nov 08 2017
MATHEMATICA
LinearRecurrence[{7, -18, 21, -11, 2}, {1, 2, 6, 21, 73}, 40] (* Harvey P. Dale, Jan 16 2019 *)
PROG
(PARI) Vec(x*(1 - 5*x + 10*x^2 - 6*x^3 + 3*x^4) / ((1 - x)^2*(1 - 2*x)*(1 - 3*x + x^2)) + O(x^30)) \\ Colin Barker, Nov 02 2017
CROSSREFS
Sequence in context: A116776 A116754 A294801 * A294694 A116740 A294802
KEYWORD
nonn,easy
AUTHOR
Lara Pudwell, Feb 26 2006
STATUS
approved