Permutations avoiding certain partially-ordered patterns

DOI10.37236/10206MaRDI QIDQ2048546zbMATH OpenOpenAlexFDO

Authors Kai Ting Keshia Yap, David Wehlau, Imed Zaguia

Publication date 6 August 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2101.12061

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

avoidance setsFibonacci numbers

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Abstract: A permutation $pi$ contains a pattern $sigma$ if and only if there is a subsequence in $pi$ with its letters are in the same relative order as those in $sigma$. Partially ordered patterns (POPs) provide a convenient way to denote patterns in which the relative order of some of the letters does not matter. This paper elucidates connections between the avoidance sets of a few POPs with other combinatorial objects, directly answering five open questions posed by Gao and Kitaev cite{gao-kitaev-2019}. This was done by thoroughly analysing the avoidance sets and developing recursive algorithms to derive these sets and their corresponding combinatorial objects in parallel, which yielded a natural bijection. We also analysed an avoidance set whose simple permutations are enumerated by the Fibonacci numbers and derived an algorithm to obtain them recursively.

Review text

Summary: A permutation \(\pi\) contains a pattern \(\sigma\) if and only if there is a subsequence in \(\pi\) with its letters in the same relative order as those in \(\sigma\). Partially ordered patterns (POPs) provide a convenient way to denote patterns in which the relative order of some of the letters does not matter. This paper elucidates connections between the avoidance sets of a few POPs with other combinatorial objects, directly answering five open questions posed by \textit{A. L. L. Gao} and \textit{S. Kitaev} in [Electron. J. Comb. 26, No. 3, Research Paper P3.26, 31 p. (2019; Zbl 1418.05006)]. This was done by thoroughly analysing the avoidance sets and developing recursive algorithms to derive these sets and their corresponding combinatorial objects in parallel, which yielded natural bijections. We also analysed an avoidance set whose simple permutations are enumerated by the Fibonacci numbers and derived an algorithm to obtain them recursively.

Recommendations

• On permutations avoiding partially ordered patterns defined by bipartite graphs
• Partially ordered generalized patterns
• On partially ordered patterns of length 4 and 5 in permutations
• Pattern avoidance in poset permutations
• Partially ordered patterns and their combinatorial interpretations

Cites work

• Combinatorial methods
• Juggling Drops and Descents
• On partially ordered patterns of length 4 and 5 in permutations
• Patterns in permutations and words.
• Primitive Juggling Sequences
• Simple permutations and pattern restricted permutations
• The number of orthogonal permutations

Cited in

(14)

• Coloured permutations containing and avoiding certain patterns
• On partially ordered patterns of length 4 and 5 in permutations
• On permutations avoiding partially ordered patterns defined by bipartite graphs
• Pattern avoidance in poset permutations
• scientific article; zbMATH DE number 5831716 (Why is no real title available?)
• Avoidance of partially ordered patterns in compositions
• Partially ordered patterns and their combinatorial interpretations
• scientific article; zbMATH DE number 5138753 (Why is no real title available?)
• scientific article; zbMATH DE number 218835 (Why is no real title available?)
• Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding
• Proof of a conjecture on the shape-Wilf-equivalence for partially ordered patterns
• Distribution of maxima and minima statistics on alternating permutations, Springer numbers, and avoidance of flat POPs
• On (shape-)Wilf-equivalence of certain sets of (partially ordered) patterns
• King permutations and partially ordered patterns

This page was built for publication: Permutations avoiding certain partially-ordered patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2048546)