Classification of forbidden subsequences of length 4
This paper deals with the classification of forbidden subsequences of length 4, and here `sequence' (or subsequence of a permutation) refers to a sequence of distinct positive integers \((b_1,b_2,\dots,b_k)\). A permutation \(\pi\) is said to avoid a permutation \(\gamma\) if \(\pi\) has no subsequence of type \(\gamma\). The set of \(\gamma\)-avoiding permutations in \(s_n\) is denoted by \(s_n(\gamma)\), and we call \(\gamma\) a forbidden subsequence of \(s_n(\gamma)\). In order to show that \(|s_n(1,2,3,4)|=|s_n(4,1,2,3)|\) for all \(n\in \mathbb{N}\), specific switching operations on \(s_n(1,2,3)\) are constructed resulting in partitioning its elements into equivalence classes. This together with the fact that the tree \(T(1,2,3)\) can be embedded in \(T(1,2,3,4)\) and \(T(4,1,2,3)\) lead us to prove \(|s_n(1,2,3,4)|=|s_n(4,1,2,3)|\) for all \(n\in\mathbb{N}\).
- Forbidden subsequences
- A new class of Wilf-equivalent permutations
- Explicit enumeration of 321, hexagon-avoiding permutations
- Sorting with two ordered stacks in series.
- Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
- Generating trees and the Catalan and Schröder numbers
- Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind
- Reduced word manipulation: patterns and enumeration
- Set-valued Rothe tableaux and Grothendieck polynomials
- Permutation patterns and cell decompositions
- Nine classes of permutations enumerated by binomial transform of Fine's sequence
- Finitely labeled generating trees and restricted permutations
- Counting occurrences of 231 in an involution
- Decreasing subsequences in permutations and Wilf equivalence for involutions
- Wilf-equivalence for singleton classes
- Some results on the avoidance of vincular patterns by multisets
- Enumeration and Wilf-classification of permutations avoiding four patterns of length 4
- On the centrosymmetric permutations in a class
- Restricted permutations
- Permutations of a multiset avoiding permutations of length 3
- On permutation patterns with constrained gap sizes
- Combinatorial exploration: an algorithmic framework for enumeration
- Counting permutations by their rigid patterns
- Restricted Dumont permutations, Dyck paths, and noncrossing partitions
- Wilf classification of three and four letter signed patterns
This page was built for publication: Classification of forbidden subsequences of length 4
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1922878)
