A257561 Number of permutations of length n that avoid the patterns 4231, 4312, and 4321.

1, 1, 2, 6, 21, 80, 322, 1346, 5783, 25372, 113174, 511649, 2338988, 10793251, 50205607, 235156609, 1108120540, 5249646137, 24987770893, 119443412277, 573125649031, 2759515312908, 13328311926552, 64559295743113, 313530998739472, 1526333617345412, 7447070497787110, 36409703715788374, 178353171835771153, 875224495042876048, 4302111437028045585

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

Sequence in context: A196345 A352703 A352704 * A150203 A106228 A150204

Adjacent sequences: A257558 A257559 A257560 * A257562 A257563 A257564

Keyword

nonn

Author

Jay Pantone, Apr 30 2015

Status

approved