Partially ordered patterns (POPs) generalize the notion of classical patterns studied widely in the literature in the context of permutations, words, compositions and partitions. In an occurrence of a POP, the relative order of some of the elements is not important. Thus, any POP of length $k$ is defined by a partially ordered set on $k$ elements, and classical patterns correspond to $k$-element chains. The notion of a POP provides a convenient language to deal with larger sets of permutation patterns. This paper contributes to a long line of research on classical permutation patterns of length 4 and 5, and beyond, by conducting a systematic search of connections between sequences in the Online Encyclopedia of Integer Sequences (OEIS) and permutations avoiding POPs of length 4 and 5. As the result, we (i) obtain 13 new enumerative results for classical patterns of length 4 and 5, and a number of results for patterns of arbitrary length, (ii) collect under one roof many sporadic results in the literature related to avoidance of patterns of length 4 and 5, and (iii) conjecture 6 connections to the OEIS. Among the most intriguing bijective questions we state, 7 are related to explaining Wilf-equivalence of various sets of patterns, e.g. 5 or 8 patterns of length 4, and 2 or 6 patterns of length 5.
@article{10_37236_8605,
author = {Alice L. L. Gao and Sergey Kitaev},
title = {On partially ordered patterns of length 4 and 5 in permutations},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {3},
doi = {10.37236/8605},
zbl = {1418.05006},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8605/}
}
TY - JOUR
AU - Alice L. L. Gao
AU - Sergey Kitaev
TI - On partially ordered patterns of length 4 and 5 in permutations
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/8605/
DO - 10.37236/8605
ID - 10_37236_8605
ER -
%0 Journal Article
%A Alice L. L. Gao
%A Sergey Kitaev
%T On partially ordered patterns of length 4 and 5 in permutations
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/8605/
%R 10.37236/8605
%F 10_37236_8605
Alice L. L. Gao; Sergey Kitaev. On partially ordered patterns of length 4 and 5 in permutations. The electronic journal of combinatorics, Tome 26 (2019) no. 3. doi: 10.37236/8605
