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

Author

Jay Pantone, Apr 30 2015

Keywords

• nonn

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

Examples

			a(4) = 21 because there are 24 permutations of length 4, and 3 of them do not avoid 4231, 4312, and 4321.
		

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