A165545 Number of permutations of length n which avoid the patterns 2341 and 3421.

1, 1, 2, 6, 22, 89, 382, 1711, 7922, 37663, 182936, 904302, 4535994, 23034564, 118209806, 612165222, 3195359360, 16795435994, 88825567814, 472356139660, 2524292893556, 13549955878141, 73026827854516, 395017112175542, 2143881709415478, 11671226062503926

Offset

0,3

Comments

These permutations have an enumeration scheme of depth 4.

G.f. is conjectured to be non-D-finite (see Albert et al link). - Jay Pantone, Oct 01 2015

Links

Jay Pantone, Table of n, a(n) for n = 0..1000

Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], 2015.

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.

V. Vatter, Enumeration schemes for restricted permutations, Combin., Prob. and Comput. 17 (2008), 137-159.

Wikipedia, Permutation classes avoiding two patterns of length 4.

Example

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

Crossrefs

Cf. A053614, A106228, A165542, A165545, A257561, A257562.

Sequence in context: A165544 A150268 A369439 * A306023 A150269 A199822

Adjacent sequences: A165542 A165543 A165544 * A165546 A165547 A165548

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

a(0)=1 prepended by Jay Pantone, Oct 01 2015

Status

approved