A165539 Number of permutations of length n which avoid the patterns 4213 and 3421.

1, 1, 2, 6, 22, 88, 367, 1571, 6861, 30468, 137229, 625573, 2881230, 13388094, 62688448, 295504025, 1401195334, 6678877732, 31984089193, 153809536017, 742462191363, 3596290278723, 17473993136316, 85147347832182, 415997039428899, 2037323575386383

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

David Bevan, The permutation classes Av(1234, 2341) and Av(1243, 2314), arXiv:1407.0570 [math.CO], 2014.

Kremer, Darla and Shiu, Wai Chee; 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 = F(z) has minimal polynomial (z-3*z^2+2*z^3) - (1-5*z+8*z^2-5*z^3)*F + (2*z-5*z^2+4*z^3)*F^2 + z^3*F^3. - David Bevan, Jun 23 2014

Example

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

Mathematica

terms = 25;
F[_] = 0; Do[F[z_] = (z(1 - 3z + 2z^2 + z^2 F[z]^3 + (2 - 5z + 4z^2) F[z]^2 )) / (1 - 5z + 8z^2 - 5z^3) + O[z]^(terms+1), {terms+1}];
CoefficientList[F[z], z] // Rest (* Jean-François Alcover, Nov 25 2018 *)

Crossrefs

Sequence in context: A032351 A165537 A165538 * A109033 A049135 A049127

Adjacent sequences: A165536 A165537 A165538 * A165540 A165541 A165542

Keyword

nonn,changed

Author

Vincent Vatter, Sep 21 2009

Extensions

More terms from David Bevan, Feb 11 2014

Status

approved