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

Author

Vincent Vatter, Sep 21 2009

Keywords

• nonn
• more

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

Examples

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

Links

• 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.

Crossrefs

Cf. A000257.

Programs

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 *)

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

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