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.

Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.

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.

Samuel Miner, Jay Pantone, Completing the Structural Analysis of the 2x4 Permutation Classes, arXiv:1802.00483 [math.CO], 2018.

Wikipedia, Permutation classes avoiding two patterns of length 4.

Formula

A(x*B(x)) = (B(x)-1)/(x*B(x)^2), where B(x) is the o.g.f. for A000257 and A(x) is the o.g.f. for A165546. This can be proven using the generating function equation at the end of section 3 of Miner and Pantone's paper. - Michael D. Weiner, Jul 02 2024

a(n) ~ 2^(5*n + 8) / (81 * sqrt(Pi) * n^(5/2) * 5^(n + 1/2)). - Vaclav Kotesovec, Jul 05 2024

G.f.: (x - F(x))/x^2, where F(x) is the compositional inverse of x*B(x) and B(x) is the o.g.f. for A000257. This follows from Michael Weiner's comment above. - Alexander Burstein, Aug 02 2024

Example

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

Mathematica

nmax = 30; A[_] = 0; Do[A[x_] = x^4*A[x]^3 + (5*x - 11)*x^2*A[x]^2 + (3*x + 10)*x*A[x] - 9*x + 1 + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] (* Vaclav Kotesovec, Jul 05 2024 *)

Crossrefs

Cf. A000257.

Sequence in context: A103137 A155069 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