A165541 Number of permutations of length n which avoid the patterns 4213 and 3142.

1, 2, 6, 22, 89, 379, 1664, 7460, 33977, 156727, 730619, 3436710, 16291842, 77758962, 373369867, 1802399037, 8742691627, 42590945206, 208300979739, 1022385319050, 5034470059883, 24865173540949, 123147075005750

Offset

1,2

Links

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

M. H. Albert, M. D. Atkinson, and V. Vatter, Inflations of geometric grid classes: three case studies, arXiv:1209.0425 [math.CO], 2012.

Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.

Darla Kremer and Wai Chee Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

Wikipedia, Permutation classes avoiding two patterns of length 4.

Formula

G.f. f satisfies: x^3*f^6+(7*x^3-7*x^2+2*x)*f^5+(x^4+14*x^3-21*x^2+10*x-1)*f^4+(4*x^4+8*x^3-19*x^2+11*x-2)*f^3+(6*x^4-5*x^3-2*x^2+2*x)*f^2+(4*x^4-7*x^3+4*x^2-x)*f+x^4-2*x^3+x^2 = 0.

Example

There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.

Mathematica

f = 0; m = 24;
Do[f = -(1/(x(4x^3 - 7x^2 + 4x - 1)))(x^3 f^6 + x(7x^2 - 7x + 2) f^5 + (x^4 + 14x^3 - 21x^2 + 10x - 1) f^4 + (1 - 2x)^2 (x^2 + 3x - 2) f^3 + x(6 x^3 - 5x^2 - 2x + 2) f^2 + (x-1)^2 x^2) + O[x]^m, {m}];
CoefficientList[f/x, x] (* Jean-François Alcover, Feb 17 2019 *)

Crossrefs

Sequence in context: A165540 A363809 A111053 * A165542 A165543 A049123

Adjacent sequences: A165538 A165539 A165540 * A165542 A165543 A165544

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

Reference corrected by Vincent Vatter, Sep 04 2012

Status

approved