On partially ordered patterns of length 4 and 5 in permutations

Alice L.L. Gao, Sergey Kitaev

Research output: Contribution to journalArticle

Abstract

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.
LanguageEnglish
Article numberP3.26
Number of pages31
JournalThe Electronic Journal of Combinatorics
Volume26
Issue number3
Publication statusPublished - 16 Aug 2019

Fingerprint

Roofs
Permutation
Chemical analysis
Integer Sequences
Partially Ordered Set
Bijective
Large Set
Partition
Equivalence

Keywords

  • permutation pattern
  • partially ordered patterns
  • enumeration
  • Wilf-equivalence

Cite this

@article{b265b05e73d840cf8d4aeeeb82a6f642,
title = "On partially ordered patterns of length 4 and 5 in permutations",
abstract = "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.",
keywords = "permutation pattern, partially ordered patterns, enumeration, Wilf-equivalence",
author = "Gao, {Alice L.L.} and Sergey Kitaev",
year = "2019",
month = "8",
day = "16",
language = "English",
volume = "26",
journal = "The Electronic Journal of Combinatorics",
issn = "1077-8926",
number = "3",

}

On partially ordered patterns of length 4 and 5 in permutations. / Gao, Alice L.L.; Kitaev, Sergey.

In: The Electronic Journal of Combinatorics, Vol. 26, No. 3, P3.26, 16.08.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On partially ordered patterns of length 4 and 5 in permutations

AU - Gao, Alice L.L.

AU - Kitaev, Sergey

PY - 2019/8/16

Y1 - 2019/8/16

N2 - 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.

AB - 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.

KW - permutation pattern

KW - partially ordered patterns

KW - enumeration

KW - Wilf-equivalence

UR - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i3p26

M3 - Article

VL - 26

JO - The Electronic Journal of Combinatorics

T2 - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

SN - 1077-8926

IS - 3

M1 - P3.26

ER -