OFFSET
0,3
COMMENTS
Conjectured to be the number of permutations of length n avoiding the partially ordered pattern (POP) {1>5, 2>5, 5>3, 5>4} of length 5. That is, conjectured to be the number of length n permutations having no subsequences of length 5 in which the fifth element is larger than the elements in positions 3 and 4, but smaller than the elements in positions 1 and 2. - Sergey Kitaev, Dec 13 2020
a(n) is also the number of inversion sequences of length n that avoid the patterns 201 and 210. - Jay Pantone, Oct 11 2023
The conjecture of Kitaev has been proven. It can be restated as the number of size n permutations avoiding 45123, 45213, 54123, 54213. There are nineteen sets of permutations avoiding four size five permutations that are known to match this sequence. A further four are conjectured to match this sequence. - Christian Bean, Jul 23 2024
LINKS
Jay Pantone, Table of n, a(n) for n = 0..200
Michael H. Albert, Christian Bean, Anders Claesson, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, PermPAL database.
Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding, The Electronic Journal of Combinatorics, Volume 31, Issue 3 (2024); arXiv preprint, arXiv:2312.07716 [math.CO], 2023.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016 [Section 2.29].
Benjamin Testart, Generating trees growing on the left for pattern-avoiding inversion sequences, arXiv:2411.05726 [math.CO], 2024. See p. 1.
Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.
FORMULA
G.f.: (2-x-x*(1-8*x)^(1/2))/(4*x^2-4*x+2). - Jay Pantone, Oct 11 2023
a(n) ~ 2^(3*n) / (25*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jul 22 2024
MATHEMATICA
CoefficientList[Series[(2 - x - x*(1 - 8*x)^(1/2))/(4*x^2 - 4*x + 2), {x, 0, 23}], x] (* Michael De Vlieger, Dec 19 2023 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, May 04 2012
EXTENSIONS
More terms from Jay Pantone, Oct 11 2023
STATUS
approved