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

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.

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

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