A165546 Number of permutations of length n that avoid the patterns 3412 and 2413.

1, 1, 2, 6, 22, 90, 395, 1823, 8741, 43193, 218704, 1129944, 5937728, 31656472, 170892498, 932625326, 5138618526, 28554124650, 159874462032, 901243508380, 5111776163584, 29155580007964, 167139065156182, 962618219420046

Offset

0,3

Comments

a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {3>1, 3>4, 1>2, 4>2} of length 4. That is, the number of length n permutations having no subsequences of length 4 in which the third element is the largest and the second element is the smallest. - Sergey Kitaev, Dec 11 2020

Links

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

Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.

Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.

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.

Example

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

Crossrefs

Sequence in context: A006318 A103137 A340892 * A279568 A053617 A089449

Adjacent sequences: A165543 A165544 A165545 * A165547 A165548 A165549

Keyword

nonn,more

Author

Vincent Vatter, Sep 21 2009

Extensions

a(13)-a(14) (obtained by brute force enumeration) from Stephen DeSalvo, Sep 23 2015

a(15)-a(23) from David Bevan, Oct 03 2015

a(0)=1 prepended by Alois P. Heinz, Dec 09 2015

Status

approved