OFFSET
0,3
COMMENTS
a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {1>2, 1>3, 2>4} of length 4. That is, the number of length n permutations having no subsequences of length 4 in which the first element is the largest and the second element is larger than the fourth element. - Sergey Kitaev, Dec 09 2020
LINKS
Jay Pantone, Table of n, a(n) for n = 0..500
Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], 2015.
D. Callan, T. Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, arXiv:1705.00933 [math.CO] (2017), Table 1 No. 241.
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.
FORMULA
G.f. satisfies (2*x^2+8*x-1)*F(x)^4 + (x^3+4*x^2-46*x+5)*F(x)^3 + (3*x^3-21*x^2+94*x-9)*F(x)^2 + (x^3+12*x^2-82*x+7)*F(x) + 3*x^2+26*x-2 = 0. - Jay Pantone, Oct 01 2015
a(n) ~ (2*sqrt(phi) + phi^2)^n / (2*sqrt(Pi*c)*n^(3/2)), where phi = A001622 is the golden ratio and c = 0.8259440839165470204581761605617676911185302765... is the smallest positive real root of the equation 62742241 + 678297200*c - 490473522*c^2 - 749210300*c^3 + 314712204*c^4 - 33996440*c^5 + 1143417*c^6 - 1180*c^7 + c^8 = 0. - Vaclav Kotesovec, Jul 05 2024
EXAMPLE
a(4) = 21 because there are 24 permutations of length 4, and 3 of them do not avoid 4231, 4312, and 4321.
CROSSREFS
KEYWORD
nonn
AUTHOR
Jay Pantone, Apr 30 2015
STATUS
approved