A226430 The number of simple permutations of length n which avoid 1243 and 2431.

1, 2, 0, 2, 4, 10, 21, 44, 89, 178, 352, 692, 1355, 2648, 5171, 10100, 19744, 38646, 75761, 148772, 292653, 576678, 1138240, 2250152, 4454679, 8830640, 17525991, 34820264, 69244864, 137815978, 274487517, 547035452, 1090790465, 2176043098, 4342753696, 8669805020, 17313228899

Offset: 1

Author

Jay Pantone, Jun 06 2013

Keywords

• nonn

Links

• Jay Pantone, The Enumeration of Permutations Avoiding 3124 and 4312, arXiv:1309.0832 [math.CO], (2013)
• Wikipedia, Permutation classes avoiding two patterns of length 4
• Index entries for linear recurrences with constant coefficients, signature (4,-3,-4,3,2).

Crossrefs

The number of all permutations which avoid 1243 and 2431 is A165534.

Programs

Mathematica

Join[{1, 2}, LinearRecurrence[{4, -3, -4, 3, 2}, {0, 2, 4, 10, 21}, 40]] (* Jean-François Alcover, Jul 22 2018 *)

PARI

x='x+O('x^66); Vec((x-2*x^2-5*x^3+12*x^4+x^5-8*x^6-3*x^7)/((1-2*x)*(1-x-x^2)^2)) \\ Joerg Arndt, Jun 19 2013

Formula

G.f.: (x-2*x^2-5*x^3+12*x^4+x^5-8*x^6-3*x^7)/((1-2*x)*(1-x-x^2)^2).

a(n) = -2*A000045(n+1) +A191830(n+2) +2^(n-3), n>2. - R. J. Mathar, Dec 06 2013