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,2

Links

Table of n, a(n) for n=1..37.

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).

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

Mathematica

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

Prog

(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

Crossrefs

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

Sequence in context: A360860 A274414 A079550 * A067648 A279327 A052438

Adjacent sequences: A226427 A226428 A226429 * A226431 A226432 A226433

Keyword

nonn

Author

Jay Pantone, Jun 06 2013

Status

approved