### Abstract

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

Language | English |
---|---|

Pages | 1-38 |

Number of pages | 38 |

Journal | The Electronic Journal of Combinatorics |

Publication status | Accepted/In press - 4 Jul 2019 |

### Fingerprint

### Keywords

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

### Cite this

*The Electronic Journal of Combinatorics*, 1-38.

}

*The Electronic Journal of Combinatorics*, pp. 1-38.

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

Research output: Contribution to journal › Article

TY - JOUR

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

AU - Gao, Alice L.L.

AU - Kitaev, Sergey

PY - 2019/7/4

Y1 - 2019/7/4

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

M3 - Article

SP - 1

EP - 38

JO - The Electronic Journal of Combinatorics

T2 - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

SN - 1077-8926

ER -