login
A257561
Number of permutations of length n that avoid the patterns 4231, 4312, and 4321.
5
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
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
KEYWORD
nonn
AUTHOR
Jay Pantone, Apr 30 2015
STATUS
approved